目錄
- 2.5線性表的鏈式表示和實作
- 2.5.1單鏈表的定義與表示
- 2.5.2 單鏈表基本操作的實作
- 演算法2.6 初始化單鏈表
- 演算法2.7 單鏈表取值
- 演算法2.8 單鏈表的按值查找
- 演算法2.9 單鏈表插入
- 演算法2.10 單鏈表洗掉
- 演算法2.11 前插法創建單鏈表
- 演算法2.12 后插法創建單鏈表
- 單鏈表基本操作詳細代碼
2.5線性表的鏈式表示和實作
2.5.1單鏈表的定義與表示
線性表鏈式存盤結構的特點是：用一組任意的存盤單元存盤線性表的資料元素（這組存盤單元可以是連續的，也可以是不連續的）
- 結點：資料元素的存盤映像，
- 結點包括兩個域：存盤資料元素資訊的資料域，存盤直接后繼存盤位置的指標域，指標域中存盤的資訊稱為指標或鏈，n個結點鏈結成一個鏈表，即為線性表
(a1, a2;··, an)， - 單鏈表是由頭指標唯一確定，因此單鏈表可以用頭指標的名字來命名，
- 單鏈表：結點只有一個指標域的鏈表
- 雙鏈表：結點有兩個指標域的鏈表
- 回圈鏈表：首尾相接的鏈表
- 頭指標：鏈表中第一個結點的指標
- 首元結點：鏈表中存盤第一個資料元素的結點
- 頭結點：鏈表的首元結點之前附設的一個結點
如何表示空表？
- 無頭結點時，頭指標為空時表示空表
- 有頭結點時，當頭結點的指標域為空時表示空表
在鏈表中設定頭結點有什么好處？
- 便于首元結點的處理，首元結點的地址保存在頭結點的指標域中，所以在鏈表的第一個位置上的操作和其他位置一致，無需進行特殊處理
- 便于空表和非空表的統一處理，無論鏈表是否為空，頭指標都是指向頭節點的非空指標，因此空表和非空表的處理也就統一了
頭結點的資料域記憶體儲什么呢？
- 頭結點的資料域可以為空，也可以存放線性表長度等附加資訊，但此結點不能計入鏈表長度值，
鏈表的特點
-
結點在存盤器中的位置是任意的
-
訪問時只能通過頭指標進入鏈表，并通過每個結點的指標域依次向后順序掃描其余結點（順序存取法）
-
單鏈表的存盤結構
typedef struct LNode
{
ElemType date;//結點的資料域
struct LNode* next;//結點的指標域
}LNode ,* LinkList;//LinkList 為指向結構體 LNode 的指標型別
2.5.2 單鏈表基本操作的實作
演算法2.6 初始化單鏈表
單鏈表的初始化操作就是構造一個如圖2.10 (b)所示的空表，
【演算法描述】
①生成新結點作為頭結點，用頭指標L 指向頭結點
②頭結點的指標域置空，
Status InitList(LinkList& L)
{//構建一個空的單鏈表L
L = new LNode;//生成新的結點作為頭結點，用頭指標指向頭結點
if (!L->date)
{
printf("初始化失敗！\n");
return ERROR;
}
L->next = NULL;//頭結點的指標域置空
printf("初始化成功！\n");
return OK;
}
演算法2.7 單鏈表取值
和順序表不同，鏈表中邏輯相鄰的結點并沒有存盤在物理相鄰的單元中，這樣， 根據給定的結點位置序號i,在鏈表中獲取該結點的值不能像順序表那樣隨機訪問，而只能從鏈表的首元結點出發，順著鏈域 next 逐個結點向下訪問，
【演算法步驟】
①用指標p指向首元結點，用八故計數器初值賦為1，
②從首元結點開始依次順著鏈域 next 向下訪問，只要指向當前結點的指標 p 不為空(NULL), 并且沒有到達序號為I的結點，則回圈執行以下操作：
- p指向下一個結點
- 計數器j相應加l
③退出回圈時， 如果指標p為空， 或者計數器j大于i, 說明指定的序號i值不合法（i大于表長n或i小于等于0), 取值失敗回傳ERROR; 否則取值成功， 此時j=i時，p所指的結點就是要找的第i個結點，用引數e保存當前結點的資料域， 回傳OK，
【演算法描述】
Status GetElem(LinkList L, int i, ElemType& e)
{//在帶頭結點的單鏈表L中根據序號l.獲取元素的值，用e回傳L中第l.個資料元素的值
LNode* p = L->next;//初始化，p指向首元結點
int j = 1;//計數器
while (p && j < i)//順鏈域向后掃描，直到p為慷訓p指向第i個元素
{
p = p->next;//p指向下一個結點
++j;//計數器加一
}
if (!p || j > i)return ERROR;
e = p->date; //取第i個結點的資料域
return OK;
}
演算法2.8 單鏈表的按值查找
鏈表中按值查找的程序和順序表類似，從鏈表的首元結點出發， 依次將結點值和給定值e進行比較， 回傳查找結果 ，
【演算法步驟】
①用指標p指向首元結點 ，
②從首元結點開始依次順著鏈域next向下查找， 只要指向當前結點的指標p不為空， 并且p所指結點的資料域不等千給定值e, 則回圈執行以下操作： p指向下一個結點 ，
③回傳p，若查找成功，p此時即為結點的地址值，若查找失敗，p的值即為NULL，
【演算法描述】
LNode* LocateElem(LinkList L, ElemType e)
{//回傳結點的地址
LNode* p = L->next;//初始化，p指向首元結點
while (p && p->date != e)
p = p->next;
return p;
}
演算法2.9 單鏈表插入
假設要在單鏈表的兩個資料元素a和b之間插入一個資料元素X, 已知p為其單鏈表存盤結構中指向結點a的指標， 如圖2.11 (a) 所示，
【演算法步驟】
將值為 e 的新結點插人到表的第i個結點的位置上， 即插入到結點 \(a_{i-1}\) 與 \(a_i\) ;之間，具體插入程序如圖 2.12 所示， 圖中對應的 5 個步驟說明如下，
心查找結點 \(a_{i-1}\) 并由指標p指向該結點，
＠生成一個新結點s，
＠將新結點s 的資料域置為 e，
＠將新結點s 的指標域指向結點 \(a_i\) ，
＠將結點p 的指標域指向新結點*s，
【演算法描述】
Status ListInsert(LinkList& L, int i, ElemType e)
{//在帶頭結點的單鏈表L的第i個位置插入值為e的新結點
LNode* p = L;//初始化，p指向頭結點
int j = 0;//計數器
while (p && (j < i - 1))
{
p = p->next;//查找第i-1個結點，p指向該結點
++j;
}
if (!p || j > i - 1)return ERROR;
LNode* s = new LNode;//生成新結點s
s->date = e;//將結點*s的資料域置為e
s->next = p->next;//將結點*s的指標域指向結點ai
p->next = s;//將結點*p的指標域指向結點*s
return OK;
}
演算法2.10 單鏈表洗掉
【演算法步驟】
洗掉單鏈表的 第！個結點a的具體程序如圖2.14所示，圖中的對應的4個步驟說明如下，
①查找結點 \(a_{i-1}\) 并由指標p指向該結點，
②臨時保存待洗掉結點 \(a_i\) ; 的地址在q中 ，以備釋放，
③將結點*p的指標域指向 \(a_i\) 的直接后繼結點，
④釋放結點 \(a_i\) 的空間，
【演算法步驟】
Status ListDelete(LinkList& L, int i)
{//在帶頭結點的單鏈表L中，洗掉第i個元素
LNode* p = L;//初始化，p指向頭結點
int j = 0;//計數器
while ((p->next) && (j < i - 1))
{
p = p->next;//查找第i-1個結點，p指向該結點
++j;
}
if (!(p->next) || (j > i - 1))return ERROR;
LNode* q;
q = p->next;//臨時保存被洗掉結點的地址以備釋放
p->next = q->next;//改變洗掉結點前驅結點的指標域
delete q;//釋放洗掉結點的空間
return OK;
}
演算法2.11 前插法創建單鏈表
前插法是通過將新結點逐個插入鏈表的頭部（頭結點之后）來創建鏈表，每次申請一個新結點，讀入相應的資料元素值，然后將新結點插入到頭結點之后
【演算法步驟】
①創建一個只有頭結點的空鏈表，
②根據待創建鏈表包括的元素個數n, 回圈n次執行以下操作：
- 生成一個新結點*p;
- 輸入元素值賦給新結點*p的資料域；
- 將新結點*p插入到頭結點之后，
圖2.15所示為線性表(a,b,c,d,e)前插法的創建程序，因為每次插入在鏈表的頭部，所以應該逆位序輸入資料，依次輸入e、d、 C、b、a, 輸入順序和線性表中的邏輯順序是相反的，
【演算法描述】
void CreateList_H(LinkList& L, int n)
{//逆序輸入n個元素的值，建立帶頭結點的單鏈表L
LNode* p;
for (int i = 0; i < n; i++)
{
p = new LNode;//生成新節點*p
cout << "請輸入第" << n - i << "個元素：";
cin >> p->date; //輸入元素值賦給新結點* p的資料域
p->next = L->next; //將新結點* p插人到頭結點之后
L->next = p;
}
}
演算法2.12 后插法創建單鏈表
后插法是通過將新結點逐個插入到鏈表的尾部來創建鏈表， 同前插法一樣， 每次申請一個新結點， 讀入相應的資料元素值， 不同的是， 為了使新結點能夠插入到表尾， 需要增加一個尾指標r指向鏈表的尾結點，
【演算法步驟】
①創建一個只有頭結點的空鏈表，
②尾指標r初始化， 指向頭結點，
③根據創建鏈表包括的元素個數n, 回圈n次執行以下操作：
- 生成一個新結點*p;
- 輸入元素值賦給新結點*p 的資料域；
- 將新結點p 插入到尾結點r之后；
- 尾指標r指向新的尾結點*p，
圖2.16所示為線性表 (a,b,c,d,e) 后插法的創建程序， 讀入資料的順序和線性表中的邏輯順序是相同的，
void CreateList_r(LinkList& L, int n)
{//正序輸入n個元素的值，建立帶頭結點的單鏈表L
LNode* r = L; //尾指標r指向頭結點
LNode* p;
for (int i = 0; i < n; i++)
{
p = new LNode;//生成新節點*p
cout << "請輸入第" << n - i << "個元素：";
cin >> p->date; //輸入元素值賦給新結點* p的資料域
p->next = NULL; //將新結點* p插人尾結點* r之后
r->next = p;
r = p;
}
}
單鏈表基本操作詳細代碼
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <iostream>
#define OK 1
#define ERROR 0
using namespace std;
typedef int ElemType;
typedef int Status;
//定義單鏈表
typedef struct LNode
{
ElemType date;
struct LNode* next;
}LNode ,* LinkList;
//初始化單鏈表
Status InitList(LinkList& L)
{//構建一個空的單鏈表L
L = new LNode;//生成新的結點作為頭結點，用頭指標指向頭結點
if (!L->date)
{
printf("初始化失敗！\n");
return ERROR;
}
L->next = NULL;//頭結點的指標域置空
printf("初始化成功！\n");
return OK;
}
//前插法創建單鏈表
void CreateList_H(LinkList& L, int n)
{//逆序輸入n個元素的值，建立帶頭結點的單鏈表L
LNode* p;
for (int i = 0; i < n; i++)
{
p = new LNode;//生成新節點*p
cout << "請輸入第" << n - i << "個元素：";
cin >> p->date; //輸入元素值賦給新結點* p的資料域
p->next = L->next; //將新結點* p插人到頭結點之后
L->next = p;
}
}
//后插法創建單鏈表
void CreateList_r(LinkList& L, int n)
{//正序輸入n個元素的值，建立帶頭結點的單鏈表L
LNode* r = L; //尾指標r指向頭結點
LNode* p;
for (int i = 0; i < n; i++)
{
p = new LNode;//生成新節點*p
cout << "請輸入第" << i+1 << "個元素：";
cin >> p->date; //輸入元素值賦給新結點* p的資料域
p->next = NULL; //將新結點* p插人尾結點* r之后
r->next = p;
r = p;
}
}
//單鏈表取值
Status GetElem(LinkList L, int i, ElemType& e)
{//在帶頭結點的單鏈表L中根據序號i獲取元素的值，用e回傳L中第i個資料元素的值
LNode* p = L->next;//初始化，p指向首元結點
int j = 1;//計數器
while (p && j < i)//順鏈域向后掃描，直到p為慷訓p指向第i個元素
{
p = p->next;//p指向下一個結點
++j;//計數器加一
}
if (!p || j > i)return ERROR;
e = p->date; //取第i個結點的資料域
return OK;
}
//單鏈表查找
LNode* LocateElem(LinkList L, ElemType e)
{//回傳結點的地址
LNode* p = L->next;//初始化，p指向首元結點
while (p && p->date != e)
p = p->next;
return p;
}
//單鏈表插入
Status ListInsert(LinkList& L, int i, ElemType e)
{//在帶頭結點的單鏈表L的第i個位置插入值為e的新結點
LNode* p = L;//初始化，p指向頭結點
int j = 0;//計數器
while (p && (j < i - 1))
{
p = p->next;//查找第i-1個結點，p指向該結點
++j;
}
if (!p || j > i - 1)return ERROR;
LNode* s = new LNode;//生成新結點s
s->date = e;//將結點*s的資料域置為e
s->next = p->next;//將結點*s的指標域指向結點ai
p->next = s;//將結點*p的指標域指向結點*s
return OK;
}
//單鏈表洗掉
Status ListDelete(LinkList& L, int i)
{//在帶頭結點的單鏈表L中，洗掉第i個元素
LNode* p = L;//初始化，p指向頭結點
int j = 0;//計數器
while ((p->next) && (j < i - 1))
{
p = p->next;//查找第i-1個結點，p指向該結點
++j;
}
if (!(p->next) || (j > i - 1))return ERROR;
LNode* q;
q = p->next;//臨時保存被洗掉結點的地址以備釋放
p->next = q->next;//改變洗掉結點前驅結點的指標域
delete q;//釋放洗掉結點的空間
return OK;
}
//判斷單鏈表是否為空
Status ListEmpty(LinkList& L)
{//若L為空表，則回傳1，否則回傳0
if (L->next)
return ERROR;
return OK;
}
//單鏈表的銷毀
void DestoryList(LinkList& L)
{
LNode* p = new LNode;//或LinkList p;
while (L)
{
p = L;
L=L->next;
delete p;
}
}
//單鏈表的清空
Status ClearList(LinkList& L)//將L重置為空表，
{
LNode* p, * q;
p = L->next;
q = new LNode;
while (p)
{
q = p->next;
delete p;
p = q;
}
L->next = NULL;
return OK;
}
//獲取單鏈表長度
int ListLength(LinkList L)
{
int i = 0;
while (L->next)
{
i++;
L = L->next;
}
return i;
}
//遍歷單鏈表
Status PrintList(LinkList L)
{
LNode* p = L->next;
if (ListEmpty(L))
{
cout << "該單鏈表為空！" << endl;
return ERROR;
}
while (p)
{
cout << p->date <<" ";
p = p->next;
}
cout << endl;
return OK;
}
int main()
{
cout << "建立List1" << endl;
LinkList List1;//定義單鏈表
InitList(List1);//初始化單鏈表
CreateList_H(List1, 5);//前插法創建單鏈表
cout << "List1:";
PrintList(List1);//遍歷單鏈表
int* e = new int;
GetElem(List1, 2, *e);//取值
cout << "List1中第二位值為：" << *e << endl;
ListInsert(List1, 3, 100);//插入
cout << "List1中第三位插入100：" << endl;
PrintList(List1);//遍歷單鏈表
cout << "建立List2" << endl;
LinkList List2;
InitList(List2);
CreateList_r(List2, 5);//后插法創建單鏈表
cout << "List2:";
PrintList(List2);//遍歷單鏈表
ListDelete(List2, 4);//洗掉
cout << "List2中洗掉第四個元素：" << endl;
PrintList(List2);//遍歷單鏈表
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/423651.html
標籤：其他