網(wǎng)站首頁(yè) 編程語(yǔ)言 正文
C++數(shù)據(jù)結(jié)構(gòu)之單鏈表的實(shí)現(xiàn)_C 語(yǔ)言
作者：Kinght_123 ? 更新時(shí)間： 2022-07-29 編程語(yǔ)言一、單鏈表的定義
線性表的鏈?zhǔn)酱鎯?chǔ)又稱為單鏈表，它是指通過(guò)一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中的數(shù)據(jù)元素。為了建立數(shù)據(jù)元素之間的線性關(guān)系，對(duì)每個(gè)鏈表結(jié)點(diǎn)，除存放元素自身的信息外，還需要存放一個(gè)指向其后繼的指針。
單鏈表中結(jié)點(diǎn)類型的描述如下：
typedef struct LNode{ // 定義單鏈表節(jié)點(diǎn)類型
ElemType data; // 數(shù)據(jù)域
struct LNode* next; // 指針域
};LNode, *LinkList;
二、單鏈表的基本操作的實(shí)現(xiàn)
1.初始化
單鏈表的初始化操作就是構(gòu)造一個(gè)空表。
具體代碼：
// 初始化單鏈表
void InitList(LinkList &L) // 構(gòu)造一個(gè)空的單鏈表L
{
L=new LNode; // 生成新節(jié)點(diǎn)作為頭節(jié)點(diǎn)，用頭指針L指向頭節(jié)點(diǎn)
L->next=NULL; // 頭節(jié)點(diǎn)的指針域置空
}
2.取值
和順序表不同，在鏈表中并沒(méi)有存儲(chǔ)在物理相鄰的單元中。所以我們只能從鏈表的首節(jié)點(diǎn)出發(fā)，順著鏈域next逐個(gè)節(jié)點(diǎn)向下訪問(wèn)。
具體代碼：
// 單鏈表的取值
bool GetElem(LinkList L, int i, ElemType &e)
{
LinkList p=L->next;int j=1; // 初始化，p指向首元節(jié)點(diǎn)，計(jì)數(shù)器j初值為1
while(p&&j<i) // 順著鏈域向后查找，直到p為空或p指向第i個(gè)元素
{
p=p->next; // p指向下一個(gè)節(jié)點(diǎn)
++j; // 計(jì)數(shù)器j相應(yīng)加1
}
if(!p||j>i)return false; // i值不合法
e=p->data; // 取第i個(gè)節(jié)點(diǎn)的數(shù)據(jù)域
return true;
}
3.查找
從鏈表的首元節(jié)點(diǎn)出發(fā)，依次將節(jié)點(diǎn)值和給定值e進(jìn)行比較，返回查找結(jié)果。
具體代碼：
//單鏈表的查找
bool LocateElem(LinkList L, LNode*& p, ElemType e)
{
//在單鏈表中查找第一個(gè)數(shù)據(jù)為e的結(jié)點(diǎn)
p = L->next;//p指向首元結(jié)點(diǎn)
while (p && p->data != e)
{
p = p->next;
}
if (p)
{
return true;
}
return false;
}4.插入
// 單鏈表的插入
bool ListInsert(LinkList &L, int i, ElemType e)
{
LinkList p = L;
LNode* s;
int j = 0;
while (p && j < i - 1)//p指向第i-1個(gè)結(jié)點(diǎn)
{
p = p->next;
j++;
}
if (!p || i < 1)//i大于表長(zhǎng)+1或小于1，插入位置不合法
{
return false;
}
s = new LNode;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
5.刪除
//單鏈表的刪除
bool ListDelete(LinkList& L, int i, ElemType& e)
{
//將單鏈表的第i個(gè)結(jié)點(diǎn)刪除
LinkList p = L;
LNode* q;
int j = 0;
while (p->next && j < i - 1)//p指向第i-1個(gè)結(jié)點(diǎn)
{
p = p->next;
j++;
}
if (!(p->next) || i < 1)//i大于表長(zhǎng)或小于1，刪除位置不合法
{
return false;
}
q = p->next;//臨時(shí)保存被刪結(jié)點(diǎn)的地址以備釋放
p->next = q->next;
e = q->data;//保存被刪結(jié)點(diǎn)的數(shù)據(jù)
delete q;//釋放被刪結(jié)點(diǎn)的空間
return true;
}
三、完整代碼
#include<iostream>
using namespace std;
#define ElemType int
typedef struct LNode{ // 定義單鏈表節(jié)點(diǎn)類型
ElemType data; // 數(shù)據(jù)域
struct LNode* next; // 指針域
}LNode,*LinkList;
// 初始化單鏈表
void InitList(LinkList &L) // 構(gòu)造一個(gè)空的單鏈表L
{
L=new LNode; // 生成新節(jié)點(diǎn)作為頭節(jié)點(diǎn)，用頭指針L指向頭節(jié)點(diǎn)
L->next=NULL; // 頭節(jié)點(diǎn)的指針域置空
}
//單鏈表的創(chuàng)建
void CreateList_H(LinkList& L)//前插法創(chuàng)建單鏈表
{
//創(chuàng)建一個(gè)長(zhǎng)度為n的單鏈表L,逆序位插入
int n;
LNode *p;
cout << "請(qǐng)輸入創(chuàng)建的單鏈表長(zhǎng)度：" << endl;
cin >> n;
for (int i = 0; i < n; i++) {
p = new LNode;
cout << "請(qǐng)輸入插入的第" << i + 1 << "個(gè)數(shù)據(jù)值" << endl;
cin >> p->data;
p->next = L->next;
L->next = p;
}
}
// 單鏈表的取值
bool GetElem(LinkList L, int i, ElemType &e)
{
LinkList p=L->next;int j=1; // 初始化，p指向首元節(jié)點(diǎn)，計(jì)數(shù)器j初值為1
while(p&&j<i) // 順著鏈域向后查找，直到p為空或p指向第i個(gè)元素
{
p=p->next; // p指向下一個(gè)節(jié)點(diǎn)
++j; // 計(jì)數(shù)器j相應(yīng)加1
}
if(!p||j>i)return false; // i值不合法
e=p->data; // 取第i個(gè)節(jié)點(diǎn)的數(shù)據(jù)域
return true;
}
//單鏈表的查找
bool LocateElem(LinkList L, LNode*& p, ElemType e)
{
//在單鏈表中查找第一個(gè)數(shù)據(jù)為e的結(jié)點(diǎn)
p = L->next;//p指向首元結(jié)點(diǎn)
while (p && p->data != e)
{
p = p->next;
}
if (p)
{
return true;
}
return false;
}
// 單鏈表的插入
bool ListInsert(LinkList &L, int i, ElemType e)
{
LinkList p = L;
LNode* s;
int j = 0;
while (p && j < i - 1)//p指向第i-1個(gè)結(jié)點(diǎn)
{
p = p->next;
j++;
}
if (!p || i < 1)//i大于表長(zhǎng)+1或小于1，插入位置不合法
{
return false;
}
s = new LNode;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
//單鏈表的刪除
bool ListDelete(LinkList& L, int i, ElemType& e)
{
//將單鏈表的第i個(gè)結(jié)點(diǎn)刪除
LinkList p = L;
LNode* q;
int j = 0;
while (p->next && j < i - 1)//p指向第i-1個(gè)結(jié)點(diǎn)
{
p = p->next;
j++;
}
if (!(p->next) || i < 1)//i大于表長(zhǎng)或小于1，刪除位置不合法
{
return false;
}
q = p->next;//臨時(shí)保存被刪結(jié)點(diǎn)的地址以備釋放
p->next = q->next;
e = q->data;//保存被刪結(jié)點(diǎn)的數(shù)據(jù)
delete q;//釋放被刪結(jié)點(diǎn)的空間
return true;
}
四、測(cè)試一下代碼
#include<iostream>
using namespace std;
#define ElemType int
//************************單鏈表的存儲(chǔ)結(jié)構(gòu)********************
typedef struct LNode
{
ElemType data;//結(jié)點(diǎn)的數(shù)據(jù)域
struct LNode* next;//結(jié)點(diǎn)的指針域
}LNode, * LinkList;//LinkList為指向結(jié)構(gòu)體LNode的指針類型
//***********************單鏈表的基本操作函數(shù)******************
//單鏈表的初始化
void InitList(LinkList& L)
{
//構(gòu)造一個(gè)空的單鏈表
L = new LNode;
L->next = NULL;
}
//單鏈表的創(chuàng)建
void CreateList_H(LinkList& L)//前插法創(chuàng)建單鏈表
{
//創(chuàng)建一個(gè)長(zhǎng)度為n的單鏈表L,逆序位插入
int n;
LNode* p;
cout << "請(qǐng)輸入創(chuàng)建的單鏈表長(zhǎng)度：" << endl;
cin >> n;
for (int i = 0; i < n; i++)
{
p = new LNode;
cout << "請(qǐng)輸入插入的第" << i + 1 << "個(gè)數(shù)據(jù)值" << endl;
cin >> p->data;
p->next = L->next;
L->next = p;
}
}
void CreateList_R(LinkList& L)//后插法創(chuàng)建單鏈表
{
//創(chuàng)建一個(gè)長(zhǎng)度為n的單鏈表L,正序位插入
int n;
LNode* p, * r;
r = L;//尾指針r指向頭結(jié)點(diǎn)
cout << "請(qǐng)輸入創(chuàng)建的單鏈表長(zhǎng)度：" << endl;
cin >> n;
for (int i = 0; i < n; i++)
{
p = new LNode;
cout << "請(qǐng)輸入插入的第" << i + 1 << "個(gè)數(shù)據(jù)值" << endl;
cin >> p->data;
p->next = NULL;
r->next = p;
r = p;
}
}
//單鏈表的插入
bool ListInsert(LinkList& L, int i, ElemType e)
{
//在帶頭結(jié)點(diǎn)的單鏈表L的第i個(gè)結(jié)點(diǎn)前插入新結(jié)點(diǎn)
LinkList p = L;
LNode* s;
int j = 0;
while (p && j < i - 1)//p指向第i-1個(gè)結(jié)點(diǎn)
{
p = p->next;
j++;
}
if (!p || i < 1)//i大于表長(zhǎng)+1或小于1，插入位置不合法
{
return false;
}
s = new LNode;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
//單鏈表的刪除
bool ListDelete(LinkList& L, int i, ElemType& e)
{
//將單鏈表的第i個(gè)結(jié)點(diǎn)刪除
LinkList p = L;
LNode* q;
int j = 0;
while (p->next && j < i - 1)//p指向第i-1個(gè)結(jié)點(diǎn)
{
p = p->next;
j++;
}
if (!(p->next) || i < 1)//i大于表長(zhǎng)或小于1，刪除位置不合法
{
return false;
}
q = p->next;//臨時(shí)保存被刪結(jié)點(diǎn)的地址以備釋放
p->next = q->next;
e = q->data;//保存被刪結(jié)點(diǎn)的數(shù)據(jù)
delete q;//釋放被刪結(jié)點(diǎn)的空間
return true;
}
//單鏈表的取值
bool GetElem(LinkList L, int i, ElemType& e)
{
//獲取單鏈表中第i個(gè)結(jié)點(diǎn)的數(shù)據(jù)
LinkList p = L;
int j = 0;
while (p->next && j < i - 1)//p指向第i-1個(gè)結(jié)點(diǎn)
{
p = p->next;
j++;
}
if (!(p->next) || i < 1)//i大于表長(zhǎng)或小于1，第i個(gè)結(jié)點(diǎn)不存在
{
return false;
}
e = p->next->data;//獲取第i個(gè)結(jié)點(diǎn)的數(shù)據(jù)
return true;
}
//單鏈表的查找
bool LocateElem(LinkList L, LNode*& p, ElemType e)
{
//在單鏈表中查找第一個(gè)數(shù)據(jù)為e的結(jié)點(diǎn)
p = L->next;//p指向首元結(jié)點(diǎn)
while (p && p->data != e)
{
p = p->next;
}
if (p)
{
return true;
}
return false;
}
//*********************************單鏈表的基本功能函數(shù)******************************
//1、插入
void ListInsert(LinkList& L)
{
ElemType e;
int i;
bool flag;
cout << "請(qǐng)輸入要插入的數(shù)據(jù)：" << endl;
cin >> e;
cout << "請(qǐng)輸入要插入的位置：" << endl;
cin >> i;
flag = ListInsert(L, i, e);
if (flag)
cout << "插入成功!" << endl;
else
cout << "位置不對(duì)，插入失??！" << endl;
}
//2、刪除
void ListDelete(LinkList& L)
{
ElemType e;
int i;
bool flag;
cout << "請(qǐng)輸入要?jiǎng)h除數(shù)據(jù)的位置：" << endl;
cin >> i;
flag = ListDelete(L, i, e);
if (flag)
cout << "刪除成功，刪除的數(shù)據(jù)為：" << e << endl;
else
cout << "位置不對(duì)，刪除失?。? << endl;
}
//3、取值
void GetElem(LinkList L)
{
ElemType e;
int i;
bool flag;
cout << "請(qǐng)輸入要獲取數(shù)據(jù)的位置：" << endl;
cin >> i;
flag = GetElem(L, i, e);
if (flag)
cout << "獲取的數(shù)據(jù)為：" << e << endl;
else
cout << "位置不對(duì)，獲取數(shù)據(jù)失敗！" << endl;
}
//4、查找
void LocateElem(LinkList L)
{
ElemType e;
LNode* p = NULL;
bool flag;
cout << "請(qǐng)輸入要查找的數(shù)據(jù)：" << endl;
cin >> e;
flag = LocateElem(L, p, e);
if (flag)
cout << "查找成功，該數(shù)據(jù)的地址為：" << p << endl;
else
cout << "查找失??！" << endl;
}
//5、判空
void ListEmpty(LinkList L)
{
if (L->next)
cout << "鏈表不為空！" << endl;
else
cout << "鏈表為空！" << endl;
}
//6、求長(zhǎng)
void ListLength(LinkList L)
{
LinkList p = L->next;//p指向第一個(gè)結(jié)點(diǎn)
int i = 0;
while (p)//遍歷單鏈表，統(tǒng)計(jì)結(jié)點(diǎn)數(shù)
{
i++;
p = p->next;
}
cout << "鏈表的長(zhǎng)度為：" << i << endl;
}
//7、清空
void ClearList(LinkList& L)
{
LNode* p, * q;
p = L->next;
while (p)//從首元結(jié)點(diǎn)開(kāi)始，依次刪除
{
q = p->next;
delete p;
p = q;
}
L->next = NULL;//頭結(jié)點(diǎn)指針域置空
}
//8、銷毀
void DestroyList(LinkList& L)
{
LNode* p;
while (L)//從頭結(jié)點(diǎn)開(kāi)始依次刪除
{
p = L;
L = L->next;
delete p;
}
}
//9、打印
void PrintList(LinkList L)
{
LinkList p = L->next;//p指向第一個(gè)結(jié)點(diǎn)
int i = 0;
while (p)//遍歷單鏈表
{
i++;
cout << "鏈表第" << i << "個(gè)數(shù)據(jù)為：" << p->data << endl;
p = p->next;
}
}
//菜單
void menu()
{
cout << "***************************************************************************" << endl;
cout << "***********************************1、插入*********************************" << endl;
cout << "***********************************2、刪除*********************************" << endl;
cout << "***********************************3、取值*********************************" << endl;
cout << "***********************************4、查找*********************************" << endl;
cout << "***********************************5、判空*********************************" << endl;
cout << "***********************************6、求長(zhǎng)*********************************" << endl;
cout << "***********************************7、清空*********************************" << endl;
cout << "***********************************8、銷毀*********************************" << endl;
cout << "***********************************9、打印*********************************" << endl;
cout << "***********************************0、退出*********************************" << endl;
cout << "***************************************************************************" << endl;
}
int main()
{
LinkList L;
InitList(L);
int select;
cout << "請(qǐng)先創(chuàng)建單鏈表：1、前插法！ 2、后插法！" << endl;
cin >> select;
switch (select)
{
case 1://插入
CreateList_H(L);
system("pause");//按任意鍵繼續(xù)
break;
case 2://刪除
CreateList_R(L);
system("pause");
break;
default:
cout << "輸入有誤,創(chuàng)建失??！" << endl;
system("pause");
break;
}
while (1)
{
system("CLS");//清屏操作
menu();
cout << "請(qǐng)輸入菜單序號(hào)：" << endl;
cin >> select;
switch (select)
{
case 1://插入
ListInsert(L);
system("pause");//按任意鍵繼續(xù)
break;
case 2://刪除
ListDelete(L);
system("pause");
break;
case 3://取值
GetElem(L);
system("pause");
break;
case 4://查找
LocateElem(L);
system("pause");
break;
case 5://判斷鏈表是否為空
ListEmpty(L);
system("pause");
break;
case 6://求單鏈表的長(zhǎng)度
ListLength(L);
system("pause");
break;
case 7://清空
ClearList(L);
system("pause");
break;
case 8://銷毀
DestroyList(L);
system("pause");
return 0;
break;
case 9://打印
PrintList(L);
system("pause");
break;
case 0:
cout << "歡迎下次使用!" << endl;//退出
system("pause");
return 0;
break;
default:
cout << "菜單序號(hào)輸入有誤！" << endl;
system("pause");
break;
}
}
system("pause");
return 0;
}
原文鏈接：https://blog.csdn.net/Kinght_123/article/details/125065824
相關(guān)推薦
- 2022-04-20 Python基礎(chǔ)筆記之struct和格式化字符_python
- 2022-05-23 一起來(lái)學(xué)習(xí)Python的列表_python
- 2022-07-20 詳解Go程序添加遠(yuǎn)程調(diào)用tcpdump功能_Golang
- 2022-08-30 使用Angular FormBuilder初始化新建FormGroup
- 2022-04-10 C++?反匯編之關(guān)于Switch語(yǔ)句的優(yōu)化措施_C 語(yǔ)言
- 2023-04-06 分布式系統(tǒng)CAP定理中的P原理解析_相關(guān)技巧
- 2022-11-16 python?sklearn與pandas實(shí)現(xiàn)缺失值數(shù)據(jù)預(yù)處理流程詳解_python
- 2022-05-12 Kotlin 接口 interface 默認(rèn)實(shí)現(xiàn)了open。并且可以提供默認(rèn)實(shí)現(xiàn)
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運(yùn)行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲(chǔ)小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過(guò)濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡(jiǎn)單動(dòng)態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對(duì)象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速