網站首頁 編程語言 正文
一、單鏈表的定義
線性表的鏈式存儲又稱為單鏈表，它是指通過一組任意的存儲單元來存儲線性表中的數據元素。為了建立數據元素之間的線性關系，對每個鏈表結點，除存放元素自身的信息外，還需要存放一個指向其后繼的指針。
單鏈表中結點類型的描述如下：
typedef struct LNode{ // 定義單鏈表節點類型
ElemType data; // 數據域
struct LNode* next; // 指針域
};LNode, *LinkList;
二、單鏈表的基本操作的實現
1.初始化
單鏈表的初始化操作就是構造一個空表。
具體代碼：
// 初始化單鏈表
void InitList(LinkList &L) // 構造一個空的單鏈表L
{
L=new LNode; // 生成新節點作為頭節點，用頭指針L指向頭節點
L->next=NULL; // 頭節點的指針域置空
}
2.取值
和順序表不同，在鏈表中并沒有存儲在物理相鄰的單元中。所以我們只能從鏈表的首節點出發，順著鏈域next逐個節點向下訪問。
具體代碼：
// 單鏈表的取值
bool GetElem(LinkList L, int i, ElemType &e)
{
LinkList p=L->next;int j=1; // 初始化，p指向首元節點，計數器j初值為1
while(p&&j<i) // 順著鏈域向后查找，直到p為空或p指向第i個元素
{
p=p->next; // p指向下一個節點
++j; // 計數器j相應加1
}
if(!p||j>i)return false; // i值不合法
e=p->data; // 取第i個節點的數據域
return true;
}
3.查找
從鏈表的首元節點出發，依次將節點值和給定值e進行比較，返回查找結果。
具體代碼：
//單鏈表的查找
bool LocateElem(LinkList L, LNode*& p, ElemType e)
{
//在單鏈表中查找第一個數據為e的結點
p = L->next;//p指向首元結點
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個結點
{
p = p->next;
j++;
}
if (!p || i < 1)//i大于表長+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個結點刪除
LinkList p = L;
LNode* q;
int j = 0;
while (p->next && j < i - 1)//p指向第i-1個結點
{
p = p->next;
j++;
}
if (!(p->next) || i < 1)//i大于表長或小于1，刪除位置不合法
{
return false;
}
q = p->next;//臨時保存被刪結點的地址以備釋放
p->next = q->next;
e = q->data;//保存被刪結點的數據
delete q;//釋放被刪結點的空間
return true;
}
三、完整代碼
#include<iostream>
using namespace std;
#define ElemType int
typedef struct LNode{ // 定義單鏈表節點類型
ElemType data; // 數據域
struct LNode* next; // 指針域
}LNode,*LinkList;
// 初始化單鏈表
void InitList(LinkList &L) // 構造一個空的單鏈表L
{
L=new LNode; // 生成新節點作為頭節點，用頭指針L指向頭節點
L->next=NULL; // 頭節點的指針域置空
}
//單鏈表的創建
void CreateList_H(LinkList& L)//前插法創建單鏈表
{
//創建一個長度為n的單鏈表L,逆序位插入
int n;
LNode *p;
cout << "請輸入創建的單鏈表長度：" << endl;
cin >> n;
for (int i = 0; i < n; i++) {
p = new LNode;
cout << "請輸入插入的第" << i + 1 << "個數據值" << 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指向首元節點，計數器j初值為1
while(p&&j<i) // 順著鏈域向后查找，直到p為空或p指向第i個元素
{
p=p->next; // p指向下一個節點
++j; // 計數器j相應加1
}
if(!p||j>i)return false; // i值不合法
e=p->data; // 取第i個節點的數據域
return true;
}
//單鏈表的查找
bool LocateElem(LinkList L, LNode*& p, ElemType e)
{
//在單鏈表中查找第一個數據為e的結點
p = L->next;//p指向首元結點
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個結點
{
p = p->next;
j++;
}
if (!p || i < 1)//i大于表長+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個結點刪除
LinkList p = L;
LNode* q;
int j = 0;
while (p->next && j < i - 1)//p指向第i-1個結點
{
p = p->next;
j++;
}
if (!(p->next) || i < 1)//i大于表長或小于1，刪除位置不合法
{
return false;
}
q = p->next;//臨時保存被刪結點的地址以備釋放
p->next = q->next;
e = q->data;//保存被刪結點的數據
delete q;//釋放被刪結點的空間
return true;
}
四、測試一下代碼
#include<iostream>
using namespace std;
#define ElemType int
//************************單鏈表的存儲結構********************
typedef struct LNode
{
ElemType data;//結點的數據域
struct LNode* next;//結點的指針域
}LNode, * LinkList;//LinkList為指向結構體LNode的指針類型
//***********************單鏈表的基本操作函數******************
//單鏈表的初始化
void InitList(LinkList& L)
{
//構造一個空的單鏈表
L = new LNode;
L->next = NULL;
}
//單鏈表的創建
void CreateList_H(LinkList& L)//前插法創建單鏈表
{
//創建一個長度為n的單鏈表L,逆序位插入
int n;
LNode* p;
cout << "請輸入創建的單鏈表長度：" << endl;
cin >> n;
for (int i = 0; i < n; i++)
{
p = new LNode;
cout << "請輸入插入的第" << i + 1 << "個數據值" << endl;
cin >> p->data;
p->next = L->next;
L->next = p;
}
}
void CreateList_R(LinkList& L)//后插法創建單鏈表
{
//創建一個長度為n的單鏈表L,正序位插入
int n;
LNode* p, * r;
r = L;//尾指針r指向頭結點
cout << "請輸入創建的單鏈表長度：" << endl;
cin >> n;
for (int i = 0; i < n; i++)
{
p = new LNode;
cout << "請輸入插入的第" << i + 1 << "個數據值" << endl;
cin >> p->data;
p->next = NULL;
r->next = p;
r = p;
}
}
//單鏈表的插入
bool ListInsert(LinkList& L, int i, ElemType e)
{
//在帶頭結點的單鏈表L的第i個結點前插入新結點
LinkList p = L;
LNode* s;
int j = 0;
while (p && j < i - 1)//p指向第i-1個結點
{
p = p->next;
j++;
}
if (!p || i < 1)//i大于表長+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個結點刪除
LinkList p = L;
LNode* q;
int j = 0;
while (p->next && j < i - 1)//p指向第i-1個結點
{
p = p->next;
j++;
}
if (!(p->next) || i < 1)//i大于表長或小于1，刪除位置不合法
{
return false;
}
q = p->next;//臨時保存被刪結點的地址以備釋放
p->next = q->next;
e = q->data;//保存被刪結點的數據
delete q;//釋放被刪結點的空間
return true;
}
//單鏈表的取值
bool GetElem(LinkList L, int i, ElemType& e)
{
//獲取單鏈表中第i個結點的數據
LinkList p = L;
int j = 0;
while (p->next && j < i - 1)//p指向第i-1個結點
{
p = p->next;
j++;
}
if (!(p->next) || i < 1)//i大于表長或小于1，第i個結點不存在
{
return false;
}
e = p->next->data;//獲取第i個結點的數據
return true;
}
//單鏈表的查找
bool LocateElem(LinkList L, LNode*& p, ElemType e)
{
//在單鏈表中查找第一個數據為e的結點
p = L->next;//p指向首元結點
while (p && p->data != e)
{
p = p->next;
}
if (p)
{
return true;
}
return false;
}
//*********************************單鏈表的基本功能函數******************************
//1、插入
void ListInsert(LinkList& L)
{
ElemType e;
int i;
bool flag;
cout << "請輸入要插入的數據：" << endl;
cin >> e;
cout << "請輸入要插入的位置：" << endl;
cin >> i;
flag = ListInsert(L, i, e);
if (flag)
cout << "插入成功!" << endl;
else
cout << "位置不對，插入失敗！" << endl;
}
//2、刪除
void ListDelete(LinkList& L)
{
ElemType e;
int i;
bool flag;
cout << "請輸入要刪除數據的位置：" << endl;
cin >> i;
flag = ListDelete(L, i, e);
if (flag)
cout << "刪除成功，刪除的數據為：" << e << endl;
else
cout << "位置不對，刪除失敗！" << endl;
}
//3、取值
void GetElem(LinkList L)
{
ElemType e;
int i;
bool flag;
cout << "請輸入要獲取數據的位置：" << endl;
cin >> i;
flag = GetElem(L, i, e);
if (flag)
cout << "獲取的數據為：" << e << endl;
else
cout << "位置不對，獲取數據失敗！" << endl;
}
//4、查找
void LocateElem(LinkList L)
{
ElemType e;
LNode* p = NULL;
bool flag;
cout << "請輸入要查找的數據：" << endl;
cin >> e;
flag = LocateElem(L, p, e);
if (flag)
cout << "查找成功，該數據的地址為：" << p << endl;
else
cout << "查找失敗！" << endl;
}
//5、判空
void ListEmpty(LinkList L)
{
if (L->next)
cout << "鏈表不為空！" << endl;
else
cout << "鏈表為空！" << endl;
}
//6、求長
void ListLength(LinkList L)
{
LinkList p = L->next;//p指向第一個結點
int i = 0;
while (p)//遍歷單鏈表，統計結點數
{
i++;
p = p->next;
}
cout << "鏈表的長度為：" << i << endl;
}
//7、清空
void ClearList(LinkList& L)
{
LNode* p, * q;
p = L->next;
while (p)//從首元結點開始，依次刪除
{
q = p->next;
delete p;
p = q;
}
L->next = NULL;//頭結點指針域置空
}
//8、銷毀
void DestroyList(LinkList& L)
{
LNode* p;
while (L)//從頭結點開始依次刪除
{
p = L;
L = L->next;
delete p;
}
}
//9、打印
void PrintList(LinkList L)
{
LinkList p = L->next;//p指向第一個結點
int i = 0;
while (p)//遍歷單鏈表
{
i++;
cout << "鏈表第" << i << "個數據為：" << 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、求長*********************************" << endl;
cout << "***********************************7、清空*********************************" << endl;
cout << "***********************************8、銷毀*********************************" << endl;
cout << "***********************************9、打印*********************************" << endl;
cout << "***********************************0、退出*********************************" << endl;
cout << "***************************************************************************" << endl;
}
int main()
{
LinkList L;
InitList(L);
int select;
cout << "請先創建單鏈表：1、前插法！ 2、后插法！" << endl;
cin >> select;
switch (select)
{
case 1://插入
CreateList_H(L);
system("pause");//按任意鍵繼續
break;
case 2://刪除
CreateList_R(L);
system("pause");
break;
default:
cout << "輸入有誤,創建失敗！" << endl;
system("pause");
break;
}
while (1)
{
system("CLS");//清屏操作
menu();
cout << "請輸入菜單序號：" << endl;
cin >> select;
switch (select)
{
case 1://插入
ListInsert(L);
system("pause");//按任意鍵繼續
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://求單鏈表的長度
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 << "菜單序號輸入有誤！" << endl;
system("pause");
break;
}
}
system("pause");
return 0;
}
原文鏈接：https://blog.csdn.net/Kinght_123/article/details/125065824
相關推薦
- 2023-05-14 opencv繪制矩形和圓的實現_python
- 2022-09-13 一文帶你了解Go語言中的單元測試_Golang
- 2022-10-31 Python?NumPy矩陣對象詳解及方法_python
- 2022-07-16 【Maven】多模塊構建項目的維護
- 2022-08-21 C語言實現棧的示例詳解_C 語言
- 2022-04-20 Android實現左側滑動菜單_Android
- 2022-07-13 Docker技術_Docker與傳統虛擬機以及傳統容器的差異
- 2022-08-02 Python+Selenium實現瀏覽器標簽頁的切換_python
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速