這篇文章主要介紹了C++數據結構之單鏈表如何實現的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇C++數據結構之單鏈表如何實現文章都會有所收獲，下面我們一起來看看吧。
線性表的鏈式存儲又稱為單鏈表，它是指通過一組任意的存儲單元來存儲線性表中的數據元素。為了建立數據元素之間的線性關系，對每個鏈表結點，除存放元素自身的信息外，還需要存放一個指向其后繼的指針。
單鏈表中結點類型的描述如下：
typedef struct LNode{ // 定義單鏈表節點類型
ElemType data; // 數據域
struct LNode* next; // 指針域
};LNode, *LinkList;單鏈表的初始化操作就是構造一個空表。
具體代碼：
// 初始化單鏈表
void InitList(LinkList &L) // 構造一個空的單鏈表L
{
L=new LNode; // 生成新節點作為頭節點，用頭指針L指向頭節點
L->next=NULL; // 頭節點的指針域置空
}和順序表不同，在鏈表中并沒有存儲在物理相鄰的單元中。所以我們只能從鏈表的首節點出發，順著鏈域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;
}從鏈表的首元節點出發，依次將節點值和給定值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;
}// 單鏈表的插入
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;
// 初始化單鏈表
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;
}關于“C++數據結構之單鏈表如何實現”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“C++數據結構之單鏈表如何實現”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
