鏈表是一種物理存盤單元上非連續、非順序的存盤結構,資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的,
線性表的順序存盤結構缺點是每一次插入和洗掉元素,大量元素的移動會導致時間效率低下,為了改進順序存盤結構的缺點,引入鏈式存盤結構,即為鏈表,
鏈式存盤結構的特點是用一組任意的存盤單元來存盤線性表中的資料元素,這樣在插入和洗掉元素時,可以通過直接修改指標完成操作,時間效率大大提高,但因為鏈式存盤結構的存盤單元不連續,所以需要通過指標來訪問它的后續元素,
為了表示每個資料元素與其直接后繼資料元素之間的邏輯關系,我們需要存出一個其直接后繼的存盤位置,我們把存盤資料元素資訊的域成為資料域,把存盤后繼位置的域稱為指標域,這兩部分構成一個節點,
n個節點鏈接成一個鏈表,即為線性表的鏈式存盤結構,因為每個節點只有一個指標域,所以又將這樣的鏈表稱為單鏈表,
下面介紹單鏈表的幾種基本操作:
單鏈表的基本操作
- 鏈表的創建
- 鏈表的初始化
- 判斷鏈表是否為空
- 回傳鏈表元素個數
- 清空鏈表
- 回傳給定位置的元素值
- 查找資料
- 洗掉元素
- 插入元素
- 建立有頭結點的單鏈表(頭插法)
- 建立有頭結點的單鏈表(尾插法)
鏈表的創建
鏈表的一個節點由指標域和資料域構成,
鏈表的整體思想其實并不難懂,但一旦讓他和指標結合在一起時,就容易讓人摸不得頭腦,
可以這樣理解:在鏈表的創建中,添加一個指向下一個節點的指標,這個指標保存的是下一個節點的地址,我們說這個指標指向下一個節點,
那么指標的型別是什么呢?當然是Node了,因為指標不僅僅指向資料域,同時也指向指標域,
下面引入一段話來幫助理解:
將某個變數賦值給指標,實際上就是將這個變數的地址賦值給指標,或者反過來說,指標中存盤了這個變數的記憶體地址,指向了這個變數,通過指標就能找到這個變數,
代碼實作:
struct Node{
ElemType data;
struct Node *next;
};
鏈表的初始化
- 引數的傳入:涉及改變鏈表的操作統統用指標傳鏈表,不然函式呼叫完成之后,為傳入的鏈表分配的的記憶體會自動釋放,鏈表不會有任何改變,
- 創建頭結點,為頭結點分配記憶體,
- 令頭節點的指標為空指標(指標不初始化容易出現很多問題)
PS:這里為什么要動態分配記憶體呢?
因為這就是陣列和鏈表的區別呀:線性表的順序存盤結構用陣列實作,而陣列占用的是一整塊記憶體,陣列元素分布很集中,需要提前預定陣列的長度,
而鏈表是一種動態結構,它所占用的大小和位置是不需要提前分配的,可以根據自身的需求即時生成,
代碼實作:
void InitList(LinkList *L){
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
}
判斷鏈表是否為空
如果鏈表頭結點指標域不為空,證明鏈表不為空,反之鏈表為空,(因為頭結點指標域存盤的就是鏈表的第一個元素的地址)
bool EmptyList(LinkList L){
if(L->next)
return false;
else
return true;
}
回傳鏈表元素個數
因為鏈表中沒有定義表長,所以要用到“作業指標后移”的思想,就是從第一個節點指標開始依次后移,直到節點為空為止,這時回圈執行的的次數就是表長,
- 宣告一個節點指標 p 指向鏈表的第一個節點,
- 當 p 不為空時,使指標 p 不斷后移,
- 用 i 計數,回圈結束后回傳,
代碼實作:
int LengthList(LinkList L){
int i = 0;
LinkList p = L->next;
//L是頭結點,L->next 代表鏈表的第一個節點,
//LinkList其實是 Node * ,所以p指向鏈表的鏈表的第一個節點,
while(p){
i++;
p = p->next;
}
//指標一直后移,直到節點不存在為止,
return i;
}
清空鏈表
這里仍然用到了“作業指標后移”的思想,從第一個節點開始,每一個節點依次釋放記憶體,直到最后一個節點停止,
- 宣告節點q,p,
- 將第一個節點賦值給p,
- 將下一個節點賦值給q,釋放q,將q賦值給q,
- 往復回圈,直到全部節點的記憶體釋放完成,
代碼實作:
void ClearList(LinkList *L){
LinkList p,q;
p = (*L)->next;
while(p){
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;
}
思考:while回圈里的值能不能為:
free(p);
p = p->next;
答:肯定會出錯,
因為這里的free釋放的是 p 整個節點,指標域也會消失,指標域消失后運行第二行代碼時會報錯,
回傳給定位置的元素值
節點指標從第一個節點開始后移,直到指標移動到到指定位置時,若節點不為空,直接回傳其值,
- 創建一個節點指標p指向鏈表的第一個節點,初始化cnt從1開始
(為什么從1開始,因為位置最小是1) - 當 cnt < i 時,遍歷鏈表,使p的指標不斷后移
- 當 cnt = i 時,回傳該節點資料域的值,
- 如果鏈表末尾p為空,則說明第i個元素不存在
代碼實作:
Status(LinkList L,int i,Elemtype *e){
int cnt = 1;
LinkList p = L->next;
while(p && cnt < i){
p = p->next;
cnt++;
}
if(!p)
return ERROR;
*e = p->data;
return OK;
}
查找資料
結合“作業指標后移”的思想,以下的代碼應該不難理解,
- 宣告一個節點 p 指向鏈表的第一個節點,初始化 i 從0開始,
- 依次對每一個 p 節點的指標域與 e 進行對比,相等則回傳對應值,不相等則回傳0,
- 當 p 不為空時,使 p 指標不斷后移,
代碼實作:
int LocateList(LinkList L,Elemtype *e){
int i = 0;
LinkList p = L->next;
while(p){
i++;
if(p->data == e)
return i;
p = p->next;
}
return 0;
}
洗掉元素
節點指標依次后移,到指定位置后,如果節點不為空,回傳其資料域,釋放該節點前,要將前一個節點的指標指向該洗掉節點的后繼元素,
- 宣告一節點 p 指向鏈表的頭結點,初始化 cnt 為 1,
- 當 cnt 小于 i 時,遍歷鏈表,然p的指標不斷后移,不斷指向下一個節點,cnt 逐次加1,
- 如果鏈表末尾 p 不存在,說明要查找的元素不存在,
- 將要洗掉的節點賦值給 q,
- 將 q 的后繼賦值給 p 的后繼,
- 回傳 q 的資料域給 e,
- 系統回收 q 節點,釋放q的記憶體,
代碼實作:
Status ListDelete(LinkList *L,int i,ElemType *e){
int cnt = 1;
LinkList q,p;
p = (*L);
//此時 p 為頭節點,p->next為第一個節點,對應cnt的值為1,
while( p->next && cnt < i){
p = p->next;
cnt++;
}
//第一個節點不為空,并且 cnt 小于要洗掉的節點位置,開始回圈
if(!(p->next))
return ERROR;
//與上方呼應,p->next是要洗掉的元素,也就是下文的q,
q = p->next;
p->next = q->next; //將p節點的指標指向q的下一個節點
*e = q->data; //保留要洗掉節點的資料域
free(q);
return OK;
}
插入元素
插入操作的思路和洗掉有點類似,大體步驟為找到要插入的位置,創建新節點,使前一個節點的指標指向新節點,使新節點的指標指向原節點后面的節點,
- 宣告一節點 p 指向鏈表的頭結點,初始化 cnt 為 1,
- 當 cnt 小于 i 時,遍歷鏈表,然p的指標不斷后移,不斷指向下一個節點,cnt 逐次加1,
- 如果鏈表末尾 p 不存在,說明插入位置有誤,
- 查找成功就創建新節點 s ,并為 s 節點分配記憶體,
- 將要插入的元素的值 e 賦值給s->data,
- 將 p 節點的指標域賦值給 s 節點的指標域(使兩者的后繼元素相同),
- 使 p 節點的指標指向 s ,
代碼實作:
Status ListInsert(LinkList *L,int i,ElemType e){
LinkList p,s;
p = (*L);
int cnt = 1;
while(p && cnt < i){
cnt++;
p = p->next;
}
if(!p)
return ERROR;
s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
亂數:
在講下面的兩個操作之前,先說明一下如何產生亂數:
亂數的產生與兩個函式相關:srand函式和rand函式,兩者配合使用可以產生偽亂數序列,頭檔案為:<stdlib. h>,
rand函式:
rand函式在產生亂數前,需要系統提供的生成偽亂數序列的種子,rand根據這個種子的值產生一系列亂數,如果系統提供的種子沒有變化,每次呼叫rand函式生成的偽亂數序列都是一樣的,
srand函式:
srand()通過引數seed改變系統提供的種子值,從而可以使得每次呼叫rand函式生成的偽亂數序列不同,從而實作真正意義上的“隨機”,
生成亂數序列的方法:
通常可以利用系統時間來改變系統的種子值,即srand(time(NULL)),可以為rand函式提供不同的種子值,進而產生不同的亂數序列,
示例:
#include<stdlib.h>//頭檔案包含rand和srand函式
#include<stdio.h>
#include<time.h>
int main(){
srand(time(0));//選取種子檔案
int k;
for(int i = 0; i < 20; i++){
k = rand() % 101; //輸出0-100之間的亂數
printf("k = %d\n",k);
}
return 0;
}
建立有頭結點的單鏈表(頭插法)
- 宣告一指標節點 p
- 初始化亂數種子
- 建立一個帶頭結點的鏈表
- 在回圈里執行如下操作:生成新節點 p,為新節點 p 的資料域隨機賦值,將 p 插入到表頭,執行 n 次
代碼實作:
void CreateListHead(LinkList *L,int n){
LinkList p;
srand(time(0));
//初始化亂數種子
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
//初始化鏈表
for(int i = 0 ; i < n ; i++){
p = (LinkList)malloc(sizeof(Node)); //建立新節點 p
p->data = rand()%100 + 1; //資料域賦值
p->next = (*L)->next;
//將p節點的指標指向頭結點后面的節點
(*L)->next = p;
//將節點 p 插入到表頭
}
}
建立有頭結點的單鏈表(尾插法)
尾插法和頭插法大體類似,不過尾插法需要另外一個指向尾部的結點 r ,在鏈表中插入元素時,只需要將 r 的指標指向 p 即可,然后將 p 賦值給 r ,這樣可以使 r 始終在鏈表尾部,并且將要插入的元素置于 r 的后方,也就是鏈表的尾部,插入結束后,將鏈表尾部的元素的指標指向NULL,
- 宣告兩節點指標 p,r
- 初始化亂數種子
- 初始化 r 的值和空鏈表
- 在回圈里執行如下操作:生成新節點 p,為新節點 p 的資料域隨機賦值,將 r 的指標指向 p,將 p 賦值給 r ,執行 n 次,
代碼實作:
void CreateListTail(LinkList *L,int n){
LinkList p,r;
srand(time(0));
*L = (LinkList)malloc(sizeof(Node));
r = *L;
for(int i = 0 ; i < n ; i++){
p = (LinkList)malloc(sizeof(Node));
p->data = rand()%100 + 1;
r->next = p;
r = p;
}
r->next = NULL;
}
個人的一點感受:
首先就是鏈表的確很難,在學鏈表之前,最好先把指標搞懂,明白指標到底是一個什么東西,再來看鏈表中的指標,這一節的指標太多,很容易把自己搞懵,其實還是需要一點時間來理解,
還有就是最好用筆在紙上寫寫畫畫,大致理解有關鏈表的一些基本操作,然后上機手撕代碼,要想真正的把鏈表吃透,還是需要多敲,多悟,多練(刷題),
個人雖然可以基本上實作這些基本操作,但有些地方還是似懂非懂,有什么操作和表述上不妥的地方,還望大家指出,
下面給出完整代碼的實作(加入測驗):
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
#define MAXSIZE 20
#define ERROR 0
#define OK 1
typedef int Status;
typedef int ElemType;
struct Node{
ElemType data;
struct Node * next;
};
typedef struct Node *LinkList;
void InitList(LinkList *L){
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
}
bool ListEmpty(LinkList L){
if(L->next)
return false;
else
return true;
}
void ClearList(LinkList *L){
LinkList p,q;
p = (*L)->next;
while(p){
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;
}
int ListLength(LinkList L){
int i = 0;
LinkList p = L->next;
while(p){
i++;
p = p->next;
}
return i;
}
Status GetElem(LinkList L,int i,ElemType *e){
int cnt = 1;
LinkList p = L->next;
while(p && cnt < i){
p = p->next;
cnt++;
}
if(!p)
return ERROR;
*e = p->data;
return OK;
}
int LocateElem(LinkList L,ElemType e){
int cnt = 0;
LinkList p = L->next;
while(p){
cnt++;
if(p->data == e)
return cnt;
p = p->next;
}
return 0;
}
Status ListInsert(LinkList *L,int i,ElemType e){
LinkList p,s;
p = (*L);
int cnt = 1;
while(p && cnt < i){
cnt++;
p = p->next;
}
if(!p)
return ERROR;
s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
Status ListDelete(LinkList *L,int i,ElemType *e){
int cnt = 1;
LinkList q,p;
p = (*L);
//此時 p 為頭節點,p->next為第一個節點
while( p->next && cnt < i){
p = p->next;
cnt++;
}
//第一個節點不為空,并且 cnt 小于要洗掉的節點位置,開始回圈
if(!(p->next))
return ERROR;
q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
Status ListTraverse(LinkList L){
LinkList p = L->next;
while(p){
printf("%d ",p->data);
p = p->next;
}
printf("\n");
return OK;
}
void CreateListHead(LinkList *L,int n){
LinkList p;
srand(time(0));
*L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
for(int i = 0 ; i < n ; i++){
p = (LinkList)malloc(sizeof(Node));
p->data = rand()%100 + 1;
p->next = (*L)->next;
(*L)->next = p;
}
}
void CreateListTail(LinkList *L,int n){
LinkList p,r;
srand(time(0));
*L = (LinkList)malloc(sizeof(Node));
r = *L;
for(int i = 0 ; i < n ; i++){
p = (LinkList)malloc(sizeof(Node));
p->data = rand()%100 + 1;
r->next = p;
r = p;
}
r->next = NULL;
}
int main(){
ElemType e;
Status r;
LinkList L;
InitList(&L);
printf("初始化L后:ListLength(L) = %d \n",ListLength(L));
for(int i = 1;i <= 5;i++){
r = ListInsert(&L,1,i);
}
printf("在表頭依次插入1-5后:L.data = ");
ListTraverse(L);
printf("ListLength(L) = %d \n",ListLength(L));
r = ListEmpty(L);
printf("L是否為空:r = %d (1:是 0:否)\n",r);
ClearList(&L);
printf("清空L后,ListLength(L) = %d \n",ListLength(L));
r = ListEmpty(L);
printf("L是否為空:r = %d (1:是 0:否) \n",r);
for(int i = 1; i <= 10 ; i++){
ListInsert(&L,i,i);
}
printf("在L的表尾依次插入1-10后,L.data = ");
ListTraverse(L);
printf("ListLength(L) = %d\n",ListLength(L));
ListInsert(&L,1,0);
printf("在表頭插入0后:L.data = ");
ListTraverse(L);
printf("ListLength(L) = %d\n",ListLength(L));
GetElem(L,5,&e);
printf("第5個元素的值為%d\n",e);
for(int i = 3 ; i <= 4 ;i++){
r = LocateElem(L,i);
if(r)
printf("第%d位元素的值為%d\n",r,i);
else
printf("不存在值為%d的元素\n",i);
}
int l = ListLength(L);
for(int i = l + 1; i >= l ; i--){
r = ListDelete(&L,i,&e);
if(r == ERROR)
printf("洗掉第%d個元素失敗\n",i);
else
printf("洗掉第%d個元素值為: %d\n",i,e);
}
printf("依次輸出L的元素: ");
ListTraverse(L);
r = 5;
ListDelete(&L,r,&e);
printf("洗掉的第%d個元素的值為:%d\n",r,e);
printf("依次輸出L的元素: ");
ListTraverse(L);
ClearList(&L);
printf("\n清空L后,ListLength = %d\n",ListLength(L));
CreateListHead(&L,20);
printf("整體創建L的元素(頭插法): ");
ListTraverse(L);
ClearList(&L);
printf("\n清空L后,ListLength = %d\n",ListLength(L));
CreateListTail(&L,20);
printf("整體創建的元素(尾插法):");
ListTraverse(L);
return 0;
}
第二次發博客,希望大家多多關注呀,哈哈!!
轉載請註明出處,本文鏈接:https://www.uj5u.com/ruanti/278577.html
標籤:其他
上一篇:圖書館操作管理系統
