C語言線性表的鏈式表示及實現(xiàn)詳解
前言
線性表的順序表示指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，而線性表的鏈式存儲特點則是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素。這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的。
對于鏈式存儲的每個數(shù)據(jù)元素而言，除了存儲其本身的信息之外，還需要存儲一個指示其直接后繼的信息，即直接后繼的存儲位置。這兩部分信息組成了數(shù)據(jù)元素的存儲映像，稱為結(jié)點。
鏈式存儲的結(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è)的。當鏈表為空的時候，帶頭結(jié)點的頭指針就指向頭結(jié)點，如果當鏈表為空的時候，單鏈表沒有帶頭結(jié)點，那么它的頭指針就為NULL
- 方便單鏈表的特殊操作，插入在表頭或者刪除第一個結(jié)點，加入頭結(jié)點的話就可以保持單鏈表操作的統(tǒng)一性
- 當單鏈表加上頭結(jié)點之后，無論單鏈表是否為空，頭指針始終指向頭結(jié)點，因此空表和非空表的處理也就統(tǒng)一了，方便了單鏈表的操作，也減少了程序的復雜性和出現(xiàn)bug的機會
鏈式表示要實現(xiàn)的功能：
實現(xiàn)工具：Dev C++
- 構(gòu)造一個空的頭結(jié)點
- 對線性表進行賦值
- 對線性表進行銷毀
- 對線性表進行重置
- 判斷線性表是否為空
- 獲取線性表的長度
- 獲取線性表某一位置對應的元素
- 在線性表某一位置插入元素
- 刪除線性表某一位置的元素
- 求線性表某一元素的前驅(qū)
- 求線性表某一元素的后繼
- 打印線性表
- 退出
準備工作：
打開Dev C++后新建一個Source File文件即可 File>new>Source File
代碼實現(xiàn)
在實現(xiàn)線性表的鏈式存儲時導入的頭文件有
#include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<windows.h>
在這里我調(diào)用windows頭文件是為了在后面的代碼中修改控制臺的名稱，在實現(xiàn)線性表的鏈式存儲時真正用到的只有前三個頭文件
在寫各種函數(shù)之前先對一些表示結(jié)果狀態(tài)的字符進行預定義
//函數(shù)結(jié)果狀態(tài)代碼 #define TRUE 1 //代碼中出現(xiàn)TRUE相當于出現(xiàn)了1 #define FALSE 0 //出現(xiàn)FALSE相當于出現(xiàn)了0 #define OK 1 //出現(xiàn)OK相當于出現(xiàn)了1 #define ERROR 0 //出現(xiàn)ERROR相當于出現(xiàn)了0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; //定義函數(shù)的返回狀態(tài) typedef int ElemType;
在這里使用了typedef定義了Status和ElemType為int類型，也就是說之后的代碼當中如果出現(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)了它就相當于出現(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){ //當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é)點，當開始結(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;
}
在對線性表進行重置前首先要判斷線性表是為空表，當其不為空時構(gòu)造兩個LinkList類型的結(jié)點p和q，使p指向L的首元結(jié)點，當p不為空即單鏈表不為空時進入while循環(huán)，將p的下一個結(jié)點復制給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é)點是否存在，當頭結(jié)點存在時看頭結(jié)點的指針域是否為空，當指針域為空時說明首元結(jié)點不存在，單鏈表是空表；當指針域不為空時說明存在首元結(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é)點位置對應一致。（在單鏈表中有頭結(jié)點的存在，所以這種方法計算出的長度最后的值要比線性表的實際長度大1）進入循環(huán)后每當p不斷向后移動，每當p后移一次，計數(shù)器count的值就加1，直到p為空，此時count的位置就對應著最后一個存儲著數(shù)據(jù)元素的結(jié)點位置。
8.獲取線性表某一位置對應的元素
//獲取線性表某一位置對應的元素
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("當前位置沒有元素\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)判斷條件的意思是當?shù)赾ount個結(jié)點存在時才能進入循環(huán)
- count < index 當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("當前結(jié)點無法插入元素\n");
return ERROR;
}
q = (LinkList)malloc(sizeof(LNode));
q->data = e; //將e賦值到q的數(shù)據(jù)域當中
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("當前位置無法刪除元素\n");
return ERROR;
}
q = p->next;
p->next = q->next;
free(q);
q = NULL;
printf("當前位置元素已刪除\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("當前位置無法求該元素的前驅(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("當前位置無法求該元素的后繼\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ū)和后繼
重置單鏈表并獲取長度以及判斷是否為空表
銷毀單鏈表并進行賦值和判斷是否為空
以上便是線性表鏈式表示和實現(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相當于出現(xiàn)了1
#define FALSE 0 //出現(xiàn)FALSE相當于出現(xiàn)了0
#define OK 1 //出現(xiàn)OK相當于出現(xiàn)了1
#define ERROR 0 //出現(xiàn)ERROR相當于出現(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)了它就相當于出現(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é)點
當開始結(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){ //當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;
}
//獲取線性表某一位置對應的元素
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("當前位置沒有元素\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("當前結(jié)點無法插入元素\n");
return ERROR;
}
q = (LinkList)malloc(sizeof(LNode));
q->data = e; //將e賦值到q的數(shù)據(jù)域當中
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("當前位置無法刪除元素\n");
return ERROR;
}
q = p->next;
p->next = q->next;
free(q);
q = NULL;
printf("當前位置元素已刪除\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("當前位置無法求該元素的前驅(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("當前位置無法求該元素的后繼\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("* 線性表的鏈式表示和實現(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. 獲取線性表某一位置對應的元素 *\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語言線性表的鏈式表示及實現(xiàn)詳解的詳細內(nèi)容，更多關(guān)于C語言線性表鏈式表示的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
現(xiàn)在很多游戲都有抽獎抽卡的功能，其實這個就類似于猜數(shù)字，生成一個隨機數(shù)，然后你去猜，猜對了就得獎。猜到一定次數(shù)就會保底。要實現(xiàn)猜數(shù)字的小游戲，首先是要讓程序生成隨機數(shù)，這就要用到rand、srand和time這三個函數(shù)，其次要了解時間戳2022-07-07
c++中臨時變量不能作為非const的引用參數(shù)的方法
下面小編就為大家?guī)硪黄猚++中臨時變量不能作為非const的引用參數(shù)的方法。小編覺得挺不錯的現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
這篇文章主要介紹了C++獲取字符串長度的幾個函數(shù)方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-12-12
這篇文章主要介紹了C語言的變量，變量是C語言語法和語義中一個很重要的知識點，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-05-05
本文主要介紹了C語言中指針常量和常量指針的區(qū)別，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡單五子棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
這篇文章主要介紹了break的使用for循環(huán)嵌套示例,需要的朋友可以參考下2014-02-02
函數(shù)重載是一種特殊情況，C++允許在同一作用域中聲明幾個類似的同名函數(shù)，這些同名函數(shù)的形參列表（參數(shù)個數(shù)，類型，順序）必須不同，常用來處理實現(xiàn)功能類似數(shù)據(jù)類型不同的問題。這篇文章主要給大家介紹了關(guān)于C++基礎(chǔ)學習之函數(shù)重載的相關(guān)資料，需要的朋友可以參考下2019-01-01
C++應用Eigen庫對應實現(xiàn)matlab中部分函數(shù)問題
這篇文章主要介紹了C++應用Eigen庫對應實現(xiàn)matlab中部分函數(shù)問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12
這篇文章主要介紹了C語言中函數(shù)的聲明、定義及使用的入門教程,重點講述了main函數(shù)的相關(guān)知識,需要的朋友可以參考下2015-12-12