C++數(shù)據(jù)結(jié)構(gòu)之單鏈表的實現(xiàn)
更新時間：2022年05月31日 17:02:29 作者：Kinght_123
線性表的鏈式存儲又稱為單鏈表，它是指通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素。本文將用C++實現(xiàn)單鏈表，需要的可以參考一下
一、單鏈表的定義
線性表的鏈式存儲又稱為單鏈表，它是指通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素。為了建立數(shù)據(jù)元素之間的線性關(guān)系，對每個鏈表結(jié)點，除存放元素自身的信息外，還需要存放一個指向其后繼的指針。
單鏈表中結(jié)點類型的描述如下：
typedef struct LNode{ // 定義單鏈表節(jié)點類型
ElemType data; // 數(shù)據(jù)域
struct LNode* next; // 指針域
};LNode, *LinkList;
二、單鏈表的基本操作的實現(xiàn)
1.初始化
單鏈表的初始化操作就是構(gòu)造一個空表。
具體代碼：
// 初始化單鏈表
void InitList(LinkList &L) // 構(gòu)造一個空的單鏈表L
{
L=new LNode; // 生成新節(jié)點作為頭節(jié)點，用頭指針L指向頭節(jié)點
L->next=NULL; // 頭節(jié)點的指針域置空
}
2.取值
和順序表不同，在鏈表中并沒有存儲在物理相鄰的單元中。所以我們只能從鏈表的首節(jié)點出發(fā)，順著鏈域next逐個節(jié)點向下訪問。
具體代碼：
// 單鏈表的取值
bool GetElem(LinkList L, int i, ElemType &e)
{
LinkList p=L->next;int j=1; // 初始化，p指向首元節(jié)點，計數(shù)器j初值為1
while(p&&j<i) // 順著鏈域向后查找，直到p為空或p指向第i個元素
{
p=p->next; // p指向下一個節(jié)點
++j; // 計數(shù)器j相應加1
}
if(!p||j>i)return false; // i值不合法
e=p->data; // 取第i個節(jié)點的數(shù)據(jù)域
return true;
}
3.查找
從鏈表的首元節(jié)點出發(fā)，依次將節(jié)點值和給定值e進行比較，返回查找結(jié)果。
具體代碼：
//單鏈表的查找
bool LocateElem(LinkList L, LNode*& p, ElemType e)
{
//在單鏈表中查找第一個數(shù)據(jù)為e的結(jié)點
p = L->next;//p指向首元結(jié)點
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個結(jié)點
{
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個結(jié)點刪除
LinkList p = L;
LNode* q;
int j = 0;
while (p->next && j < i - 1)//p指向第i-1個結(jié)點
{
p = p->next;
j++;
}
if (!(p->next) || i < 1)//i大于表長或小于1，刪除位置不合法
{
return false;
}
q = p->next;//臨時保存被刪結(jié)點的地址以備釋放
p->next = q->next;
e = q->data;//保存被刪結(jié)點的數(shù)據(jù)
delete q;//釋放被刪結(jié)點的空間
return true;
}
三、完整代碼
#include<iostream>
using namespace std;
#define ElemType int
typedef struct LNode{ // 定義單鏈表節(jié)點類型
ElemType data; // 數(shù)據(jù)域
struct LNode* next; // 指針域
}LNode,*LinkList;
// 初始化單鏈表
void InitList(LinkList &L) // 構(gòu)造一個空的單鏈表L
{
L=new LNode; // 生成新節(jié)點作為頭節(jié)點，用頭指針L指向頭節(jié)點
L->next=NULL; // 頭節(jié)點的指針域置空
}
//單鏈表的創(chuàng)建
void CreateList_H(LinkList& L)//前插法創(chuàng)建單鏈表
{
//創(chuàng)建一個長度為n的單鏈表L,逆序位插入
int n;
LNode *p;
cout << "請輸入創(chuàng)建的單鏈表長度：" << endl;
cin >> n;
for (int i = 0; i < n; i++) {
p = new LNode;
cout << "請輸入插入的第" << i + 1 << "個數(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é)點，計數(shù)器j初值為1
while(p&&j<i) // 順著鏈域向后查找，直到p為空或p指向第i個元素
{
p=p->next; // p指向下一個節(jié)點
++j; // 計數(shù)器j相應加1
}
if(!p||j>i)return false; // i值不合法
e=p->data; // 取第i個節(jié)點的數(shù)據(jù)域
return true;
}
//單鏈表的查找
bool LocateElem(LinkList L, LNode*& p, ElemType e)
{
//在單鏈表中查找第一個數(shù)據(jù)為e的結(jié)點
p = L->next;//p指向首元結(jié)點
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個結(jié)點
{
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個結(jié)點刪除
LinkList p = L;
LNode* q;
int j = 0;
while (p->next && j < i - 1)//p指向第i-1個結(jié)點
{
p = p->next;
j++;
}
if (!(p->next) || i < 1)//i大于表長或小于1，刪除位置不合法
{
return false;
}
q = p->next;//臨時保存被刪結(jié)點的地址以備釋放
p->next = q->next;
e = q->data;//保存被刪結(jié)點的數(shù)據(jù)
delete q;//釋放被刪結(jié)點的空間
return true;
}
四、測試一下代碼
#include<iostream>
using namespace std;
#define ElemType int
//************************單鏈表的存儲結(jié)構(gòu)********************
typedef struct LNode
{
ElemType data;//結(jié)點的數(shù)據(jù)域
struct LNode* next;//結(jié)點的指針域
}LNode, * LinkList;//LinkList為指向結(jié)構(gòu)體LNode的指針類型
//***********************單鏈表的基本操作函數(shù)******************
//單鏈表的初始化
void InitList(LinkList& L)
{
//構(gòu)造一個空的單鏈表
L = new LNode;
L->next = NULL;
}
//單鏈表的創(chuàng)建
void CreateList_H(LinkList& L)//前插法創(chuàng)建單鏈表
{
//創(chuàng)建一個長度為n的單鏈表L,逆序位插入
int n;
LNode* p;
cout << "請輸入創(chuàng)建的單鏈表長度：" << endl;
cin >> n;
for (int i = 0; i < n; i++)
{
p = new LNode;
cout << "請輸入插入的第" << i + 1 << "個數(shù)據(jù)值" << endl;
cin >> p->data;
p->next = L->next;
L->next = p;
}
}
void CreateList_R(LinkList& L)//后插法創(chuàng)建單鏈表
{
//創(chuàng)建一個長度為n的單鏈表L,正序位插入
int n;
LNode* p, * r;
r = L;//尾指針r指向頭結(jié)點
cout << "請輸入創(chuàng)建的單鏈表長度：" << endl;
cin >> n;
for (int i = 0; i < n; i++)
{
p = new LNode;
cout << "請輸入插入的第" << i + 1 << "個數(shù)據(jù)值" << endl;
cin >> p->data;
p->next = NULL;
r->next = p;
r = p;
}
}
//單鏈表的插入
bool ListInsert(LinkList& L, int i, ElemType e)
{
//在帶頭結(jié)點的單鏈表L的第i個結(jié)點前插入新結(jié)點
LinkList p = L;
LNode* s;
int j = 0;
while (p && j < i - 1)//p指向第i-1個結(jié)點
{
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個結(jié)點刪除
LinkList p = L;
LNode* q;
int j = 0;
while (p->next && j < i - 1)//p指向第i-1個結(jié)點
{
p = p->next;
j++;
}
if (!(p->next) || i < 1)//i大于表長或小于1，刪除位置不合法
{
return false;
}
q = p->next;//臨時保存被刪結(jié)點的地址以備釋放
p->next = q->next;
e = q->data;//保存被刪結(jié)點的數(shù)據(jù)
delete q;//釋放被刪結(jié)點的空間
return true;
}
//單鏈表的取值
bool GetElem(LinkList L, int i, ElemType& e)
{
//獲取單鏈表中第i個結(jié)點的數(shù)據(jù)
LinkList p = L;
int j = 0;
while (p->next && j < i - 1)//p指向第i-1個結(jié)點
{
p = p->next;
j++;
}
if (!(p->next) || i < 1)//i大于表長或小于1，第i個結(jié)點不存在
{
return false;
}
e = p->next->data;//獲取第i個結(jié)點的數(shù)據(jù)
return true;
}
//單鏈表的查找
bool LocateElem(LinkList L, LNode*& p, ElemType e)
{
//在單鏈表中查找第一個數(shù)據(jù)為e的結(jié)點
p = L->next;//p指向首元結(jié)點
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 << "請輸入要插入的數(shù)據(jù)：" << 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 << "請輸入要刪除數(shù)據(jù)的位置：" << endl;
cin >> i;
flag = ListDelete(L, i, e);
if (flag)
cout << "刪除成功，刪除的數(shù)據(jù)為：" << e << endl;
else
cout << "位置不對，刪除失敗！" << endl;
}
//3、取值
void GetElem(LinkList L)
{
ElemType e;
int i;
bool flag;
cout << "請輸入要獲取數(shù)據(jù)的位置：" << endl;
cin >> i;
flag = GetElem(L, i, e);
if (flag)
cout << "獲取的數(shù)據(jù)為：" << e << endl;
else
cout << "位置不對，獲取數(shù)據(jù)失敗！" << endl;
}
//4、查找
void LocateElem(LinkList L)
{
ElemType e;
LNode* p = NULL;
bool flag;
cout << "請輸入要查找的數(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、求長
void ListLength(LinkList L)
{
LinkList p = L->next;//p指向第一個結(jié)點
int i = 0;
while (p)//遍歷單鏈表，統(tǒng)計結(jié)點數(shù)
{
i++;
p = p->next;
}
cout << "鏈表的長度為：" << i << endl;
}
//7、清空
void ClearList(LinkList& L)
{
LNode* p, * q;
p = L->next;
while (p)//從首元結(jié)點開始，依次刪除
{
q = p->next;
delete p;
p = q;
}
L->next = NULL;//頭結(jié)點指針域置空
}
//8、銷毀
void DestroyList(LinkList& L)
{
LNode* p;
while (L)//從頭結(jié)點開始依次刪除
{
p = L;
L = L->next;
delete p;
}
}
//9、打印
void PrintList(LinkList L)
{
LinkList p = L->next;//p指向第一個結(jié)點
int i = 0;
while (p)//遍歷單鏈表
{
i++;
cout << "鏈表第" << i << "個數(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、求長*********************************" << endl;
cout << "***********************************7、清空*********************************" << endl;
cout << "***********************************8、銷毀*********************************" << endl;
cout << "***********************************9、打印*********************************" << endl;
cout << "***********************************0、退出*********************************" << endl;
cout << "***************************************************************************" << endl;
}
int main()
{
LinkList L;
InitList(L);
int select;
cout << "請先創(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 << "請輸入菜單序號：" << 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://求單鏈表的長度
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;
}
以上就是C++數(shù)據(jù)結(jié)構(gòu)之單鏈表的實現(xiàn)的詳細內(nèi)容，更多關(guān)于C++單鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要為大家詳細介紹了C++實現(xiàn)并查集，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07
這篇文章主要介紹了C語言二維數(shù)組的指針指向問題,文中不建議用二級指針來訪問二維數(shù)組,需要的朋友可以參考下2015-12-12
這篇文章主要介紹了C++多線程中的鎖和條件變量使用,非常不錯，具有一定的參考借鑒價值，需要的朋友可以參考下2018-11-11
這篇文章主要介紹了c++利用函數(shù)指針示例,需要的朋友可以參考下2014-04-04
這篇文章主要為大家詳細介紹了C++利用遞歸實現(xiàn)走迷宮，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
這篇文章主要為大家詳細介紹了C++編寫實現(xiàn)飛機大戰(zhàn)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
本篇文章是對ACE反應器(Reactor)模式進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了C++如何用智能指針管理內(nèi)存資源，幫助大家更好的理解和使用c++開發(fā)，感興趣的朋友可以了解下2020-08-08
這篇文章主要給大家介紹了關(guān)于c++11中regex正則表達式的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用c++11具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2019-11-11
這篇文章主要介紹了C語言編程中程序的一些基本的編寫優(yōu)化技巧,文中涉及到了基礎(chǔ)的C程序內(nèi)存方面的知識,非常推薦!需要的朋友可以參考下2021-07-07