C語言線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)詳解
前言
線性表的順序表示指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，而線性表的鏈?zhǔn)酱鎯μ攸c則是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素。這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的。
對于鏈?zhǔn)酱鎯Φ拿總€數(shù)據(jù)元素而言，除了存儲其本身的信息之外，還需要存儲一個指示其直接后繼的信息，即直接后繼的存儲位置。這兩部分信息組成了數(shù)據(jù)元素的存儲映像，稱為結(jié)點。
鏈?zhǔn)酱鎯Φ慕Y(jié)構(gòu)包含兩個域：一個用于存儲數(shù)據(jù)元素的信息，另一個用于存儲直接后繼的存儲位置；存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，存儲直接后繼存儲位置的域稱為指針域。
圖示：
數(shù)據(jù)結(jié)構(gòu)中，在單鏈表的開始結(jié)點之前一般要附設(shè)一個類型相同的結(jié)點，稱之為頭結(jié)點。頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息，頭結(jié)點的指針域存儲指向開始結(jié)點的指針，即第一個元素結(jié)點的存儲位置。
附設(shè)頭結(jié)點的作用：
- 防止單鏈表是空的而設(shè)的。當(dāng)鏈表為空的時候，帶頭結(jié)點的頭指針就指向頭結(jié)點，如果當(dāng)鏈表為空的時候，單鏈表沒有帶頭結(jié)點，那么它的頭指針就為NULL
- 方便單鏈表的特殊操作，插入在表頭或者刪除第一個結(jié)點，加入頭結(jié)點的話就可以保持單鏈表操作的統(tǒng)一性
- 當(dāng)單鏈表加上頭結(jié)點之后，無論單鏈表是否為空，頭指針始終指向頭結(jié)點，因此空表和非空表的處理也就統(tǒng)一了，方便了單鏈表的操作，也減少了程序的復(fù)雜性和出現(xiàn)bug的機會
鏈?zhǔn)奖硎疽獙崿F(xiàn)的功能：
實現(xiàn)工具：Dev C++
- 構(gòu)造一個空的頭結(jié)點
- 對線性表進行賦值
- 對線性表進行銷毀
- 對線性表進行重置
- 判斷線性表是否為空
- 獲取線性表的長度
- 獲取線性表某一位置對應(yīng)的元素
- 在線性表某一位置插入元素
- 刪除線性表某一位置的元素
- 求線性表某一元素的前驅(qū)
- 求線性表某一元素的后繼
- 打印線性表
- 退出
準(zhǔn)備工作：
打開Dev C++后新建一個Source File文件即可 File>new>Source File
代碼實現(xiàn)
在實現(xiàn)線性表的鏈?zhǔn)酱鎯r導(dǎo)入的頭文件有
#include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<windows.h>
在這里我調(diào)用windows頭文件是為了在后面的代碼中修改控制臺的名稱，在實現(xiàn)線性表的鏈?zhǔn)酱鎯r真正用到的只有前三個頭文件
在寫各種函數(shù)之前先對一些表示結(jié)果狀態(tài)的字符進行預(yù)定義
//函數(shù)結(jié)果狀態(tài)代碼 #define TRUE 1 //代碼中出現(xiàn)TRUE相當(dāng)于出現(xiàn)了1 #define FALSE 0 //出現(xiàn)FALSE相當(dāng)于出現(xiàn)了0 #define OK 1 //出現(xiàn)OK相當(dāng)于出現(xiàn)了1 #define ERROR 0 //出現(xiàn)ERROR相當(dāng)于出現(xiàn)了0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; //定義函數(shù)的返回狀態(tài) typedef int ElemType;
在這里使用了typedef定義了Status和ElemType為int類型，也就是說之后的代碼當(dāng)中如果出現(xiàn)了Status和ElemType，它們與int作用相同
1. 單鏈表的結(jié)點構(gòu)造
typedef struct LNode{
ElemType data; //數(shù)據(jù)域
struct LNode * next; //指針域,指向一整個結(jié)點(結(jié)構(gòu)體,該結(jié)構(gòu)體中包含數(shù)據(jù)域和指針域)
}LNode , * LinkList;
代碼中的* LinkList指的是結(jié)點的類型，在之后的代碼中出現(xiàn)了它就相當(dāng)于出現(xiàn)了指向這個結(jié)點的指針
2. 構(gòu)造一個空的頭結(jié)點
//構(gòu)造一個空的頭結(jié)點
Status InitList_L(LinkList &L){
L = (LinkList)malloc(sizeof(LNode)); //產(chǎn)生頭結(jié)點，并使L指向該頭結(jié)點(L也稱頭指針)
if(!L) return ERROR; //如果存儲空間分配失敗，返回ERROR
L->next = NULL; //將指針域賦值為NULL
printf("空的頭結(jié)點創(chuàng)建成功\n");
return OK;
}
在該函數(shù)傳參時一定要在L之前加"&"符號，表示引用傳遞，保證形參和實參同時改變。之前在寫代碼時因為沒有輸入"&"符號，沒有使用引用傳遞也就意味著沒有開辟了新的內(nèi)存空間，所以在之后賦值的時候會出現(xiàn)無法賦值的情況 在這里要強調(diào)一點："->"是一個指針類型的運算符，它是用于指向結(jié)構(gòu)體子數(shù)據(jù)的指針
3. 對線性表進行賦值
//對線性表進行賦值
Status ValueList_L(LinkList &L,ElemType e){
LinkList s,p;
p = L;
while(p->next){
p = p->next;
}
s = (LinkList)malloc(sizeof(LNode)); //生成一個新結(jié)點
s->data = e; //將e賦值給新結(jié)點的數(shù)據(jù)域
s->next = p->next; //將新結(jié)點與后一個結(jié)點的地址連接
p->next = s;
return OK;
}
因為要實現(xiàn)構(gòu)造一個單鏈表，所以在main函數(shù)中會循環(huán)調(diào)用ValueList_L方法，所以通過以下的循環(huán)是用來使p指向要賦值的位置
while(p->next){
p = p->next; }
之后利用malloc()函數(shù)開辟新的結(jié)點來存放數(shù)據(jù)和下一個結(jié)點的位置即可，因為malloc()函數(shù)開辟空間之后返回的不是LinkList結(jié)點類型，所以在利用malloc()函數(shù)開辟新的結(jié)點時要將其通過強制類型轉(zhuǎn)換使其轉(zhuǎn)換成LinkList類型
4.對線性表進行銷毀
//對線性表進行銷毀
Status DistoryList_L(LinkList &L) {
if(!L){ //如果線性表不存在，返回ERROR
printf("線性表不存在\n");
return ERROR;
}
LinkList q = L->next; //使q指向單鏈表的首元結(jié)點
while(q != NULL){ //當(dāng)q結(jié)點不為空時一直進入循環(huán)
free(L); //釋放L結(jié)點
L = q; //將q結(jié)點賦值給L結(jié)點
q = L->next; //將q結(jié)點賦值給L結(jié)點以后使q結(jié)點指向L的下一個結(jié)點
}
free(L); //此時q的值為NULL，L指向尾結(jié)點，將其釋放
L = NULL;
printf("線性表已銷毀\n");
}
在對單鏈表進行銷毀操作時，從頭結(jié)點開始逐一釋放，釋放前使q指向開始釋放的結(jié)點，當(dāng)開始結(jié)點不為空時，執(zhí)行釋放過程，先釋放頭結(jié)點，然后將L，q都向后移，依次釋放，因為q始終是L的后繼，所以最后一定是L留到最后，最后釋放L結(jié)點
L = NULL;
為什么在feel(L);之后還要將L賦值為空？
因為free函數(shù)只是將之前動態(tài)分配給L的內(nèi)存歸還給系統(tǒng)，但是指針類型的結(jié)點L仍然存在，為了防止之后發(fā)生野指針訪問，將L賦值為NULL
5.對線性表進行重置
//對線性表進行重置
Status ClearList_L(LinkList &L)
{
if(!L->next){
printf("線性表為空表，不需要重置\n");
return ERROR;
}
LinkList p,q;
p = L->next; //將單鏈表的頭結(jié)點賦值給p
while(p){
q = p->next; //將單鏈表的首元結(jié)點賦值給q
free(p);
p = q;
}
L->next = NULL; //將頭結(jié)點的指針域賦值為空
printf("線性表已重置\n");
return OK;
}
在對線性表進行重置前首先要判斷線性表是為空表，當(dāng)其不為空時構(gòu)造兩個LinkList類型的結(jié)點p和q，使p指向L的首元結(jié)點，當(dāng)p不為空即單鏈表不為空時進入while循環(huán)，將p的下一個結(jié)點復(fù)制給q，將p釋放后再將q賦值給p。p為空時說明此時單鏈表只剩下了頭結(jié)點，將頭結(jié)點的指針域設(shè)置為NULL，完成單鏈表的重置（因為LinkList為指針類型的數(shù)據(jù)，所以賦值的內(nèi)容都是地址）
圖示：
6.判斷線性表是否為空
//判斷線性表是否為空
Status ListEmpty_L(LinkList L)
{
if(L){
if(L->next == NULL) //如果首元結(jié)點不存在
printf("線性表是空表\n");
else
printf("線性表不是空表\n");
}
else{
printf("線性表不存在，無法判斷\n");
}
return OK;
}
在判斷線性表是否為空時，首先判斷頭結(jié)點是否存在，當(dāng)頭結(jié)點存在時看頭結(jié)點的指針域是否為空，當(dāng)指針域為空時說明首元結(jié)點不存在，單鏈表是空表；當(dāng)指針域不為空時說明存在首元結(jié)點，單鏈表不是空表。如果頭結(jié)點不存在的話說明單鏈表不存在，無法判斷是否為空表。
7.獲取線性表的長度
//獲取線性表的長度
Status ListLength_L(LinkList L,int count)
{
//L為帶頭結(jié)點的單鏈表的頭指針，count為計數(shù)器
LinkList p = L->next; //定義p為單鏈表L的指針域
while(p){
p = p->next;
count++;
}
return count;
}
獲取線性表長度的核心思路是遍歷單鏈表，定義LinkList類型的變量p，將單鏈表的首元結(jié)點賦值給p。在該函數(shù)中count為計數(shù)器，形參count傳來的值始終為1，count的值為1代表從首元結(jié)點開始計數(shù)，所以才將L->next賦值給p，目的是為了讓count與存儲數(shù)據(jù)元素的結(jié)點位置對應(yīng)一致。（在單鏈表中有頭結(jié)點的存在，所以這種方法計算出的長度最后的值要比線性表的實際長度大1）進入循環(huán)后每當(dāng)p不斷向后移動，每當(dāng)p后移一次，計數(shù)器count的值就加1，直到p為空，此時count的位置就對應(yīng)著最后一個存儲著數(shù)據(jù)元素的結(jié)點位置。
8.獲取線性表某一位置對應(yīng)的元素
//獲取線性表某一位置對應(yīng)的元素
Status GetElem_L(LinkList L,int index)
{
LinkList p;
p = L->next; //使p指向L的首元結(jié)點
int count = 1; //count為計數(shù)器 ，賦值等于1的原因是從首元結(jié)點開始計數(shù)
while(p && count < index){ //順著指針向后查找，直到p指向第index個元素或p為空
p = p->next;
count++; //此時p一直指向第count個元素
}
if(!p || count > index){
printf("當(dāng)前位置沒有元素\n");
return ERROR;
}
printf("第%d個元素的值是：%d\n",index,p->data);
return OK;
}
與獲取單鏈表的長度思路一樣，獲取單鏈表某一位置的元素也需要遍歷單鏈表，只不過什么時候停止遍歷由自己決定，可能不需要全部遍歷。定義LinkList類型的變量p并且將首元結(jié)點的地址賦值給p。定義計數(shù)器count的初始值為1之后，進入while循環(huán)，循環(huán)判斷有兩個：
- p 因為p一直指向第count個結(jié)點，所以此循環(huán)判斷條件的意思是當(dāng)?shù)赾ount個結(jié)點存在時才能進入循環(huán)
- count < index 當(dāng)count還不是我們想要獲取的結(jié)點位置時繼續(xù)循環(huán)
退出循環(huán)以后p指向的位置就是我們想要獲取的結(jié)點位置，這個時候要先進行越界判斷，!p的意思是如果在之前的循環(huán)中index的值大于單鏈表的長度，那么退出循環(huán)的原因就是p為NULL，那么!p就為true，滿足if語句中的條件，返回ERROR，所以 !p的作用就是限制index不大于單鏈表的長度。 count > index的目的是為了限制index的值小于1
9.在線性表某一位置插入元素
//在線性表某一位置插入元素
Status ListInsert_L(LinkList &L,int index,ElemType e)
{
LinkList p,q;
p = L; //將線性表的頭結(jié)點賦值給p
int count = 0; //count為計數(shù)器
while(p && count < index - 1){ //尋找第index-1個結(jié)點
p = p->next; //此時的p結(jié)點指向第index-1個結(jié)點
count++;
}
if(!p || count > index -1){ //越界判斷,index小于1或是index大于表長加1
printf("當(dāng)前結(jié)點無法插入元素\n");
return ERROR;
}
q = (LinkList)malloc(sizeof(LNode));
q->data = e; //將e賦值到q的數(shù)據(jù)域當(dāng)中
q->next = p->next;
p->next = q;
printf("元素插入成功\n");
return OK;
}
與尋找某個位置結(jié)點的值思路一致，需要先找到要插入結(jié)點的位置。但是這里不同的地方在于要插入結(jié)點的話，可以在單鏈表的表尾插入元素，也可以在頭結(jié)點和首元結(jié)點間插入元素，所以計數(shù)器count的初值為0（為了保證從頭結(jié)點開始遍歷，count的值與實際的結(jié)點位置相匹配），所以判斷條件變?yōu)閕ndex - 1。在結(jié)束循環(huán)和越界判斷結(jié)束后p之后的位置就是要插入結(jié)點的位置，先構(gòu)造出一個空結(jié)點并賦值給q，將p的下一個結(jié)點位置賦值給q的指針域，再將p的下一個結(jié)點位置賦值給q完成插入操作。
圖示：
10.刪除線性表某一位置的元素
//刪除線性表某一位置的元素
Status DeleteList_L(LinkList &L,int index)
{
LinkList p,q;
p = L; //將線性表的頭結(jié)點賦值給p
int count = 0; //計數(shù)器
while(p->next && count < index - 1){
p = p->next;
count++; //此時p一直指向第count個結(jié)點
}
if(!(p->next) || count > index - 1){ //越界判斷
printf("當(dāng)前位置無法刪除元素\n");
return ERROR;
}
q = p->next;
p->next = q->next;
free(q);
q = NULL;
printf("當(dāng)前位置元素已刪除\n");
return OK;
}
刪除某一結(jié)點的思路仍然是從頭結(jié)點開始遍歷，找到要刪除的結(jié)點的位置的前一個結(jié)點，此時p就是要刪除結(jié)點位置的前一個結(jié)點。將p的后一個結(jié)點賦值給q，此時q就是要刪除的結(jié)點，將q的下一個結(jié)點與p的下一個結(jié)點連接，釋放q結(jié)點，完成刪除操作。
11.求線性表某一元素的前驅(qū)
//求線性表某一元素的前驅(qū)
Status PriorElem_L(LinkList L,int index)
{
LinkList p;
int count = 0; //count為計數(shù)器
p = L;
while(p->next && count < index - 1){ //尋找第index-1個結(jié)點
p = p->next; //p一直指向第count個結(jié)點
count++;
}
if(!(p->next) || count > index - 1){ //越界判斷
printf("當(dāng)前位置無法求該元素的前驅(qū)\n");
return ERROR;
}
if(p != L) //如果要獲取第一個元素的前驅(qū)，就是獲取頭結(jié)點數(shù)據(jù)域的值
printf("該元素的前驅(qū)為：%d\n",p->data);
else
printf("該位置的前驅(qū)是頭結(jié)點\n頭結(jié)點的數(shù)據(jù)域中存儲的值為：%d\n",p->data);
return OK;
}
和刪除結(jié)點的思路完全一致，只不過求前驅(qū)時不需要進行刪除結(jié)點，在循環(huán)中控制循環(huán)條件使p在index - 1位置結(jié)束循環(huán)，此時p指向的就是第index的前驅(qū)，直接將p結(jié)點的數(shù)據(jù)域輸出即可
12.求線性表某一元素的后繼
//求線性表某一元素的后繼
Status NextElem_L(LinkList L,int index)
{
LinkList p;
int count = 0;
p = L->next;
while(p && count < index){ //不斷遍歷尋找第index之后的結(jié)點
p = p->next; //p一直指向index-1的后一個結(jié)點
count++;
}
//!p的目的是為了確保i不大于表長-1，count>index的目的是為了確保index不小于0
if(!p || count > index){ //越界判斷
printf("當(dāng)前位置無法求該元素的后繼\n");
return ERROR;
}
printf("該元素的后繼為：%d\n",p->data);
}
在聲明LinkList類型變量p時將L的首元結(jié)點賦值給p，在循環(huán)中p一直指向第index的下一個結(jié)點，所以直接將p結(jié)點的數(shù)據(jù)域輸出即可
13.打印線性表
//打印線性表
Status PrintList_L(LinkList L)
{
if(!L){ //如果線性表不存在，返回ERROR
printf("線性表不存在，無法打印\n");
return ERROR;
}
LinkList p;
p = L->next; //將L的首元結(jié)點賦值給p ,為了不將頭結(jié)點打印出來
while(p){
printf(" %d",p->data); //將p結(jié)點的數(shù)據(jù)域輸出
p = p->next; //結(jié)點不斷的向后移動
}
printf("\n");
return OK;
}
打印單鏈表的思路也是進行對單鏈表的遍歷，在遍歷的過程中將每個結(jié)點的數(shù)據(jù)域中存儲的值輸出
運行結(jié)果演示
為了方便演示，在這里為單鏈表一次賦值為1，2，3，4，5
構(gòu)造一個空的頭結(jié)點
賦值操作
判斷此時線性表是否為空
獲取單鏈表的長度
獲取2號位置的元素
在3號位置插入520并打印單鏈表
獲取此時單鏈表的長度
刪除3號位置的元素并打印單鏈表
求3號位置元素的前驅(qū)和后繼
重置單鏈表并獲取長度以及判斷是否為空表
銷毀單鏈表并進行賦值和判斷是否為空
以上便是線性表鏈?zhǔn)奖硎竞蛯崿F(xiàn)，由于鏈表在空間的合理利用上和插入、刪除是不需要移動等的優(yōu)點，因此在很多場合下它
是線性表的首選存儲結(jié)構(gòu)。然而，它也存在著實現(xiàn)某些基本操作的缺點，比如：求線性表長度時不如順序存儲結(jié)構(gòu)......
源碼
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<windows.h>
//函數(shù)結(jié)果狀態(tài)代碼
#define TRUE 1 //代碼中出現(xiàn)TRUE相當(dāng)于出現(xiàn)了1
#define FALSE 0 //出現(xiàn)FALSE相當(dāng)于出現(xiàn)了0
#define OK 1 //出現(xiàn)OK相當(dāng)于出現(xiàn)了1
#define ERROR 0 //出現(xiàn)ERROR相當(dāng)于出現(xiàn)了0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status; //定義函數(shù)的返回狀態(tài)
typedef int ElemType;
typedef struct LNode{
ElemType data; //數(shù)據(jù)域
struct LNode * next; //指針域,指向一整個結(jié)點(結(jié)構(gòu)體,該結(jié)構(gòu)體中包含數(shù)據(jù)域和指針域)
}LNode , * LinkList; //* LinkList是結(jié)點的類型，在之后的代碼中出現(xiàn)了它就相當(dāng)于出現(xiàn)了指向這個結(jié)點的指針
//構(gòu)造一個空的頭結(jié)點
Status InitList_L(LinkList &L){ //之前因為沒有輸入"&"符號,沒有使用引用傳遞也就意味著沒有開辟了新的內(nèi)存空間，所以在之后賦值的時候會出現(xiàn)無法賦值的情況
L = (LinkList)malloc(sizeof(LNode)); //產(chǎn)生頭結(jié)點，并使L指向該頭結(jié)點(L也稱頭指針)
if(!L) return ERROR; //如果存儲空間分配失敗，返回ERROR
L->next = NULL; //將指針域賦值為NULL,在這里要強調(diào)一點："->"是一個整體，它是用于指向結(jié)構(gòu)體子數(shù)據(jù)的指針
printf("空的頭結(jié)點創(chuàng)建成功\n");
return OK;
}
//對線性表進行賦值
Status ValueList_L(LinkList &L,ElemType e){
LinkList s,p;
p = L;
while(p->next){
p = p->next;
}
s = (LinkList)malloc(sizeof(LNode)); //生成一個新結(jié)點
s->data = e; //將e賦值給新結(jié)點的數(shù)據(jù)域
s->next = p->next; //將新結(jié)點與后一個結(jié)點的地址連接
p->next = s;
return OK;
}
//對線性表進行銷毀
Status DistoryList_L(LinkList &L) {
/*從頭結(jié)點開始逐一釋放，釋放前使p指向頭結(jié)點，q指向開始釋放的結(jié)點
當(dāng)開始結(jié)點不為空時，執(zhí)行釋放過程
先釋放頭結(jié)點，然后將p，q都向后移，依次釋放
因為q始終是p的后繼，所以最后一定是p留到最后，最后釋放p
*/
if(!L){ //如果線性表不存在，返回ERROR
printf("線性表不存在\n");
return ERROR;
}
LinkList q = L->next; //使q指向單鏈表的首元結(jié)點
while(q != NULL){ //當(dāng)q結(jié)點不為空時一直進入循環(huán)
free(L); //釋放L結(jié)點
L = q; //將q結(jié)點賦值給L結(jié)點
q = L->next; //將q結(jié)點賦值給L結(jié)點以后使q結(jié)點指向L的下一個結(jié)點
}
free(L); //此時q的值為NULL，L指向尾結(jié)點，將其釋放
L = NULL; //free函數(shù)只是將之前動態(tài)分配給L的內(nèi)存歸還給系統(tǒng)，但是指針類型的結(jié)點L仍然存在
//為了防止之后發(fā)生野指針訪問，將L賦值為NULL
printf("線性表已銷毀\n");
}
//對線性表進行重置
Status ClearList_L(LinkList &L)
{
if(!L->next){
printf("線性表為空表，不需要重置\n");
return ERROR;
}
LinkList p,q;
p = L->next; //將單鏈表的頭結(jié)點賦值給p
while(p){
q = p->next; //將單鏈表的首元結(jié)點賦值給q
free(p);
p = q;
}
L->next = NULL; //將頭結(jié)點的指針域賦值為空
printf("線性表已重置\n");
return OK;
}
//判斷線性表是否為空
Status ListEmpty_L(LinkList L)
{
if(L){
if(L->next == NULL) //如果首元結(jié)點不存在
printf("線性表是空表\n");
else
printf("線性表不是空表\n");
}
else{
printf("線性表不存在，無法判斷\n");
}
return OK;
}
//獲取線性表的長度
Status ListLength_L(LinkList L,int count)
{
//L為帶頭結(jié)點的單鏈表的頭指針，count為計數(shù)器
LinkList p = L->next; //定義p為單鏈表L的指針域
while(p){
p = p->next;
count++;
}
return count;
}
//獲取線性表某一位置對應(yīng)的元素
Status GetElem_L(LinkList L,int index)
{
LinkList p;
p = L->next; //使p指向L的首元結(jié)點
int count = 1; //count為計數(shù)器 ，賦值等于1的原因是從首元結(jié)點開始計數(shù)
while(p && count < index){ //順著指針向后查找，直到p指向第index個元素或p為空
p = p->next;
count++; //此時p一直指向第count個元素
}
if(!p || count > index){
printf("當(dāng)前位置沒有元素\n");
return ERROR;
}
printf("第%d個元素的值是：%d\n",index,p->data);
return OK;
}
//在線性表某一位置插入元素
Status ListInsert_L(LinkList &L,int index,ElemType e)
{
LinkList p,q;
p = L; //將線性表的頭結(jié)點賦值給p
int count = 0; //count為計數(shù)器
while(p && count < index - 1){ //尋找第index-1個結(jié)點
p = p->next; //此時的p結(jié)點指向第index-1個結(jié)點
count++;
}
if(!p || count > index -1){ //越界判斷,index小于1或是index大于表長加1
printf("當(dāng)前結(jié)點無法插入元素\n");
return ERROR;
}
q = (LinkList)malloc(sizeof(LNode));
q->data = e; //將e賦值到q的數(shù)據(jù)域當(dāng)中
q->next = p->next;
p->next = q;
printf("元素插入成功\n");
return OK;
}
//刪除線性表某一位置的元素
Status DeleteList_L(LinkList &L,int index)
{
LinkList p,q;
p = L; //將線性表的頭結(jié)點賦值給p
int count = 0; //計數(shù)器
while(p->next && count < index - 1){
p = p->next;
count++; //此時p一直指向第count個結(jié)點
}
if(!(p->next) || count > index - 1){ //越界判斷
printf("當(dāng)前位置無法刪除元素\n");
return ERROR;
}
q = p->next;
p->next = q->next;
free(q);
q = NULL;
printf("當(dāng)前位置元素已刪除\n");
return OK;
}
//求線性表某一元素的前驅(qū)
Status PriorElem_L(LinkList L,int index)
{
LinkList p;
int count = 0; //count為計數(shù)器
p = L;
while(p->next && count < index - 1){ //尋找第index-1個結(jié)點
p = p->next; //p一直指向第count個結(jié)點
count++;
}
if(!(p->next) || count > index - 1){ //越界判斷
printf("當(dāng)前位置無法求該元素的前驅(qū)\n");
return ERROR;
}
if(p != L) //如果要獲取第一個元素的前驅(qū)，就是獲取頭結(jié)點數(shù)據(jù)域的值
printf("該元素的前驅(qū)為：%d\n",p->data);
else
printf("該位置的前驅(qū)是頭結(jié)點\n頭結(jié)點的數(shù)據(jù)域中存儲的值為：%d\n",p->data);
return OK;
}
//求線性表某一元素的后繼
Status NextElem_L(LinkList L,int index)
{
LinkList p;
int count = 0;
p = L->next;
while(p && count < index){ //不斷遍歷尋找第index之后的結(jié)點
p = p->next; //p一直指向index-1的后一個結(jié)點
count++;
}
//!p的目的是為了確保i不大于表長-1，count>index的目的是為了確保index不小于0
if(!p || count > index){ //越界判斷
printf("當(dāng)前位置無法求該元素的后繼\n");
return ERROR;
}
printf("該元素的后繼為：%d\n",p->data);
}
//打印線性表
Status PrintList_L(LinkList L)
{
if(!L){ //如果線性表不存在，返回ERROR
printf("線性表不存在，無法打印\n");
return ERROR;
}
LinkList p;
p = L->next; //將L的首元結(jié)點賦值給p ,為了不將頭結(jié)點打印出來
while(p){
printf(" %d",p->data); //將p結(jié)點的數(shù)據(jù)域輸出
p = p->next; //結(jié)點不斷的向后移動
}
printf("\n");
return OK;
}
int main(){
SetConsoleTitle("Dream_飛翔"); //控制windows終端控制臺的名稱
//system("mode con cols=60 lines=30"); 這條語句可以控制windows終端控制臺的大小
LinkList L = NULL; //聲明線性表的頭結(jié)點，但是并未進行初始化
int choose,index,e,Num,Value,k;
while(1){
printf("*****************************************\n");
printf("* *\n");
printf("* 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)： *\n");
printf("* *\n");
printf("* 1. 構(gòu)造一個空的頭結(jié)點 *\n");
printf("* 2. 對線性表進行賦值 *\n");
printf("* 3. 對線性表進行銷毀 *\n");
printf("* 4. 對線性表進行重置 *\n");
printf("* 5. 判斷線性表是否為空 *\n");
printf("* 6. 獲取線性表的長度 *\n");
printf("* 7. 獲取線性表某一位置對應(yīng)的元素 *\n");
printf("* 8. 在線性表某一位置插入元素 *\n");
printf("* 9. 刪除線性表某一位置的元素 *\n");
printf("* 10. 求線性表某一元素的前驅(qū) *\n");
printf("* 11. 求線性表某一元素的后繼 *\n");
printf("* 12. 打印線性表 *\n");
printf("* 13. 退出 *\n");
printf("* *\n");
printf("*****************************************\n");
printf("請做出您的選擇：");
scanf("%d",&choose);
switch(choose){
case 1:InitList_L(L);break;
case 2:{
if(L){ //對線性表賦值的前提是線性表的頭結(jié)點存在
printf("請輸入線性表元素的個數(shù)：");
scanf("%d",&Num);
if(Num > 0){
for(int i = 1;i <= Num;i++){
printf("請輸入第%d個元素的值：",i);
scanf("%d",&Value);
ValueList_L(L,Value);
}
printf("線性表賦值成功\n");
}
else
printf("請輸入一個有效數(shù)字\n");
}
else
printf("線性表不存在，無法賦值\n");
}
break;
case 3:DistoryList_L(L);break;
case 4:ClearList_L(L);break;
case 5:ListEmpty_L(L);break;
case 6:{
int count = ListLength_L(L,1);
printf("線性表的長度為：%d\n",count-1);
};break;
case 7:{
printf("請輸入要獲取元素的位置：");
scanf("%d",&index);
GetElem_L(L,index);
}
break;
case 8:{
printf("請輸入插入元素的位置：");
scanf("%d",&index);
printf("請輸入插入元素的值：");
scanf("%d",&e);
ListInsert_L(L,index,e);
}
break;
case 9:{
printf("請輸入要刪除元素的位置：");
scanf("%d",&index);
DeleteList_L(L,index);
}
break;
case 10:{
if(L){
printf("請輸入想要查找哪一個元素的前驅(qū)：");
scanf("%d",&index);
PriorElem_L(L,index);
}
else
printf("線性表不存在，無法獲取其中元素的前驅(qū)\n");
}
break;
case 11:{
if(L){
printf("請輸入想要查找哪一個元素的后繼：");
scanf("%d",&index);
NextElem_L(L,index);
}
else
printf("線性表不存在，無法獲取其中元素的后繼\n");
}
break;
case 12:PrintList_L(L);break;
case 13:exit(0);
}
}
return 0;
}以上就是C語言線性表的鏈?zhǔn)奖硎炯皩崿F(xiàn)詳解的詳細內(nèi)容，更多關(guān)于C語言線性表鏈?zhǔn)奖硎镜馁Y料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C++的類型轉(zhuǎn)換(強轉(zhuǎn))你了解嗎
這篇文章主要為大家詳細介紹了C++的類型轉(zhuǎn)換，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
這篇文章主要介紹了C++設(shè)計模式之單例模式,本文同時給出了4種單例模式的實現(xiàn)代碼,需要的朋友可以參考下2014-09-09
C語言中typedef的用法以及#define區(qū)別詳解
這篇文章主要給大家介紹了關(guān)于C語言中typedef用法以及#define區(qū)別的相關(guān)資料,typedef 是用來定義一種類型的新別名的,它不同于宏（#define）,不是簡單的字符串替換。而#define只是簡單的字符串替換（原地擴展）,需要的朋友可以參考下2021-07-07
這篇文章主要為大家詳細介紹了如何基于Qt實現(xiàn)可拖動自定義控件，文中的示例代碼講解詳細，具有一定的借鑒價值，感興趣的小伙伴可以了解一下2023-04-04
C++ win系統(tǒng)如何用MinGW編譯Boost庫
這篇文章主要介紹了C++ win系統(tǒng)如何用MinGW編譯Boost庫問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12
C++的靜態(tài)成員變量和靜態(tài)成員函數(shù)詳解
這篇文章主要為大家介紹了C++的靜態(tài)成員變量和靜態(tài)成員函數(shù)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-12-12
實戰(zhàn)開發(fā)為單片機的按鍵加一個鎖防止多次觸發(fā)的細節(jié)
今天小編就為大家分享一篇關(guān)于實戰(zhàn)開發(fā)為單片機的按鍵加一個鎖防止多次觸發(fā)的細節(jié)，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
《C++ Primer》隱式類類型轉(zhuǎn)換學(xué)習(xí)整理
在本篇文章里小編給大家整理的是關(guān)于《C++ Primer》隱式類類型轉(zhuǎn)換學(xué)習(xí)筆記內(nèi)容，需要的朋友們參考下。2020-02-02
這篇文章主要為大家詳細介紹了基于C語言代碼實現(xiàn)點餐系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-01-01
這篇文章主要為大家詳細介紹了opencv如何識別圖片上帶顏色的圓，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-07-07