溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“c語言線性表的鏈式存儲結構是什么”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“c語言線性表的鏈式存儲結構是什么”吧！
頭指針：鏈表中第一個節點的存儲位置叫頭指針。
頭結點：第一個結點前放的一個不存儲任何數據的結點。
頭結點與頭指針的區別：
1、頭指針是指鏈表指向第一個結點的指針，若鏈表有頭結點，則是指向頭結點的指針；
2、頭指針具有標識作用，所以常用頭指針冠以鏈表的名字；
3、無論鏈表是否為空，頭指針均不為空。頭指針是鏈表的必要元素。
4、頭結點是為了操作的統一和方便而設立的，放在第一元素的借點之前，其數據域一般無意義（也可存儲鏈表的長度）；
5、有了頭結點，對在第一個元素節點點之前插入結點和刪除第一個結點，其他操作與其他結點的操作統一了；
6、頭結點不一定是鏈表的必要元素
文字描述還是很抽象，讓我們來看圖，這樣更直觀：
理清了這幾個概念，接下來我們開始用c語言實現單鏈表的基本操作（這里會把帶頭結點與不帶頭結點分別實現并區別兩者的異同）：
準備工作：定義節點類型，一些聲明：
#pragma once
#define ElemType int
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status;
typedef int DataType;
//定義結點類型
typedef struct Node
{
ElemType data;
struct Node *next;
}SeqNode;
typedef struct Node *LinkList; //定義指針類型
初始化：
//帶頭結點的初始化，建立一個只有頭結點的空鏈表,頭結點的數據域記錄表長，并且頭結點不計入長度。
//初始化成功返回OK,失敗返回ERROR
Status Init_Head_SeqNode(LinkList *Head)
{
*Head = (LinkList)malloc(sizeof(SeqNode));
if((*Head) == NULL)
{
printf("out of memory\n");
return ERROR;
}
(*Head)->next = NULL;
(*Head)->data = 0;
return OK;
}
//不帶頭結點的初始化，建立一個只有頭結點的空鏈表
Status Init_SeqNode(LinkList *Head)
{
*Head = NULL;
return TRUE;
}
頭插：下邊分別是帶頭結點與不帶頭結點的頭插方式，直接上代碼，可能有些抽象，我自己畫了一些圖，來幫助理解，希望可以也可以幫助大家理解:
帶頭結點的頭插：
不帶頭結點的頭插：
頭插代碼：
//帶頭結點頭插,插入成功返回TRUE，失敗返回ERROR
Status Insert_Head_Fr(LinkList Head,ElemType x)
{
LinkList new_node; //保存新申請的結點
new_node = (LinkList)malloc(sizeof(Node));
if(NULL == new_node)
{
printf("out of memory\n");
return FALSE;
}
new_node->data = x; //把要插入的值賦值給新申請的結點的數據域
new_node->next = Head->next; //第一步：把頭結點的下一元素即就是首元結點地地址賦給新的結點
Head->next = new_node; //第二步：把新申請的結點賦值給頭結點
(Head->data)++; //帶頭結點的頭節點的數據域用來保存鏈表的個數，每添加一個元素加1
return TRUE;
}
//不帶頭結點的頭插，插入成功返回TRUE,失敗返回FALSE
Status Isert_No_Head_Node(LinkList *Head,ElemType x)
{
LinkList new_node; //保存新申請的結點
new_node = (LinkList)malloc(sizeof(Node));
if(NULL == new_node)
{
printf("out of memory\n");
return FALSE;
}
new_node->data = x;
new_node->next = (*Head);
//第一步：先讓新申請的結點指向首元結點，因為不帶頭結點的鏈表頭指針保存首元結點的地址，那么就需要這樣賦值
(*Head) = new_node; //第二步：讓頭指針指向新申請的結點。
return TRUE;
}
尾插：同樣我也給出一些我自己繪的圖：
帶頭結點的尾插：
不帶頭結點的尾插：
尾插代碼：
/*不帶頭結點的與帶頭結點的進行尾插的時候，有人會認為兩者是沒有區別的，
**我想你可能忽略了當鏈表中沒有元素時兩著的插入還是有區別的。
*/
//帶頭結點尾插,插入成功返回TRUE，失敗返回ERROR
Status Insert_Head_Ba(LinkList Head,ElemType x)
{
LinkList new_node; //保存新申請的結點
LinkList temp = Head; //找到尾結點
new_node = (LinkList)malloc(sizeof(Node));
if(NULL == new_node )
{
printf("out of memory\n");
return FALSE;
}
//利用臨時變量遍歷所有鏈表，找到尾結點，因為temp本身是指向當前節點的next的，所以當temp等于NULL時就到了鏈表的最后一個結點
while(NULL != temp->next)
{
temp = temp->next;
}
new_node->data = x;
new_node->next = NULL;
temp->next = new_node;
Head->data++; //帶頭結點的頭節點的數據域用來保存鏈表的個數，每添加一個元素加1
return TRUE;
}
//不帶頭結點尾插,插入成功返回TRUE，失敗返回ERROR
Status Insert_No_Head_Ba(LinkList *Head,ElemType x)
{
LinkList new_node;
LinkList temp = (*Head); //保護頭指針
new_node = (LinkList)malloc(sizeof(Node)); //為新申請的結點分配空間
if(NULL == new_node)
{
printf("out of menory\n");
return FALSE;
}
if(NULL == (*Head)) //空鏈表
{
new_node->next = NULL;
new_node->data = x;
(*Head) = new_node;
return TRUE;
}
else
{
//利用臨時變量遍歷所有鏈表，找到尾結點，因為temp本身是指向當前節點的next的，所以當temp等于NULL時就到了鏈表的最后一個結點了
while(NULL != temp->next)
{
temp = temp->next;
}
new_node->data = x;
new_node->next = NULL;
temp->next = new_node;
return TRUE;
}
}
按照位置插入：同樣先看圖：
帶頭結點的按位置插入：
不帶頭結點按照位置插入：
//帶頭結點的按照位置插入如元素，頭節點不計入位置，插入時分為空鏈表和非空鏈表，由于帶頭結點所以所有操作是一樣的
//插入成功返回TRUE，并且頭結點的數據元素加1,插入失敗返回FALSE。
Status Insert_Head_Pos_SeqNode(LinkList Head, ElemType x, int pos)
{
LinkList temp = Head; //保護頭指針
LinkList temp_pre = Head; //保存定位的pos位置地址
LinkList new_node;
new_node = (LinkList)malloc(sizeof(Node)); //為新申請的結點分配空間
if(NULL == new_node)
{
printf("out of memory\n");
return FALSE;
}
if(pos > Head->data)
{
printf("插入位置出錯，%d不能插入\n",x);
return FALSE;
}
//通過遍歷找到要放數據位置的結點，但是由于單鏈表的當前結點只能找到下一個結點，
//而插入數據時，需要知道當前結點的位置，所以就需要定義一個變量來保存當前前結點的前一個結點
for(int i = 0; i < pos;i++)
{
temp = temp->next;
temp_pre = temp_pre->next;
}
new_node->data = x; //為新申請的節點的數據域賦值
new_node->next = temp;
//第一步：首先讓新結點指向要插入的位置，也就是當前結點的前一個結點保存的位置
temp_pre->next = new_node; //第二步：讓當前結點的前一個結點指向指向新結點
Head->data++; //插入成功，鏈表個數加1
return TRUE;
}
//不帶頭結點的按位置插入，分為兩種情況，如果是空鏈表，就要修改頭指針的指向，那么修改指針的指向，就要用二級指針接收
//如果不是空鏈表，只需要遍歷鏈表，找到位置，這兩種情況都要考慮插入位置是否正確
//插入成功返回TRUE，插入失敗返回FALSE。
Status Inser_No_Head_Pos_SeqNode(LinkList *Head, int pos, ElemType x)
{
int Num = 0; //計算鏈表一共多少個結點
LinkList temp = (*Head); //保護頭指針
LinkList temp_pre = (*Head); //保存pos 位置的地址
LinkList new_node;
new_node = (LinkList)malloc(sizeof(Node)); //為新申請的結點分配空間
if(NULL == new_node ) //防止開辟內存失敗
{
printf("out of memory\n");
return FALSE;
}
//處理空鏈表的情況
if(NULL == (*Head) )
{
if(pos > 0)
{
printf("插入位置出錯，%d不能插入\n",x);
return FALSE;
}
else
{
new_node->data = x; //為開辟的新結點賦值
new_node->next = NULL; //第一步：先讓新申請的節點指向要插入 的結點的下一個結點
(*Head) = new_node; //讓頭指針指向新結點
return TRUE;
}
}
//處理非空鏈表的情況
else
{
//通過遍歷找到要放數據位置的結點，但是由于單鏈表的當前結點只能找到下一個結點，
//而插入數據時，需要知道當前結點的位置，所以就需要定義一個變量來保存當前前結點的前一個結點
while(NULL != temp)
{
Num++;
temp = temp->next;
}
if(pos+1 > Num) //如果插入位置出錯直接跳出
{
printf("插入位置出錯，%d不能插入\n",x);
return FALSE;
}
else if(0 == pos)
{
new_node->data = x; //為開辟的新結點賦值
new_node->next = (*Head);
(*Head) = new_node;
}
else
{
//當遍歷確定pos位置正確后，此時幾個指針的指向已經發生改變，需要重新指向頭指針，遍歷找到需要插入的結點
temp = *Head;
for(int i = 0; i < pos - 1; i++) //定位到要刪除的結點的前一個結點
{
temp = temp->next;
}
new_node->data = x; //給新結點的數據域賦值
new_node->next = temp->next;
//第一步：首先讓新結點指向要插入的位置，也就是當前結點的前一個結點保存的位置
temp->next = new_node; // 第二步：讓當前結點的前一個結點指向指向新結點
}
}
return TRUE;
}
頭刪：對與刪除操作，與插入操作類比，不在畫圖，兩者是類同的。
//不帶頭結點的頭刪，需要考慮鏈表是否為空鏈表，或者或一個元素的時候，當只有一個元素的時候，頭刪除就需要，修改頭指針的指向，其他地方的刪除，順序都一樣，用x放回刪除的數據
//刪除成功返回TRUE，失敗返回FALSE
Status Delite_No_Head_SeqNode(LinkList *Head,ElemType *x)
{
LinkList temp_node = (*Head); //防止頭指針被修改
if(NULL == temp_node)
{
printf("鏈表已空，已經沒有元素可以刪除了\n");
return FALSE;
}
if(NULL == temp_node->next)
{
*x = temp_node->data; //把要刪除的結點的值保存的x中去
(*Head) = NULL;
free(temp_node); //釋放刪除的結點，防止內存泄露
temp_node = NULL;
return TRUE;
}
else //處理鏈表中有一個以上的結點的刪除
{
*x = temp_node->data; //把要刪除的結點的值保存的x中去
*Head = temp_node->next; //修該頭指針的指向
free(temp_node); //釋放刪除的結點，防止內存泄露
temp_node = NULL;
return TRUE;
}
}
//帶頭結點的頭刪，不論是有一個元素還是多和元素，刪除操作都不需要修該頭指針指向，因而也就不需要修該頭指針指向，用x放回刪除的數據
//刪除成功返回TRUE，失敗返回FALSE；
Status Delite_Head_Fr_SeqList(LinkList Head,ElemType *x)
{
LinkList temp = Head->next; //定義臨時變量防止頭指針被修改
if(NULL == temp->next)
{
printf("鏈表已空，已經沒有元素刪除\n");
return FALSE;
}
*x = temp->next->data; //把要刪除的結點的值保存的x中去
temp = temp->next; //第一步：讓臨時結點指向要刪除的結點的下一個結點
free(Head->next); //第二步：釋放首元結點的內存，防止內存泄露
Head->next = temp; //第三步：修改頭指針的指向
return TRUE;
}
尾刪：同樣也不在給出示意圖：對比尾插的圖。
//帶頭結點的尾刪，因為有頭結點所有操作都一樣
Status Delite_Head_Br_SeqNode(LinkList Head,ElemType *x)
{
//定義臨時變量防止頭指針被修改 ,首先讓指向首元結點,尾刪用它來定位最后一個結點，
//由于單鏈表，只知道當前節點的下一個結點的位置，那么，就需要定義一個變量保存當前結點的地址
LinkList temp = Head->next; //定位最后一個指針
LinkList temp_node_pre = Head; //保存最后一個結點的地址
if(NULL == temp)
{
printf("鏈表已空，已經沒有元素刪除\n");
return FALSE;
}
while(NULL != temp->next)
{
temp = temp->next;
temp_node_pre = temp_node_pre->next;
}
*x = temp->data; //保存最后一個結點的數據域的值
temp_node_pre->next = NULL; //修改原來結點的倒數第二個結點的指向
free(temp); //此時temp_node指向最后一個結點，防止內存泄露，釋放最后一個結點的內存
temp =NULL;
return TRUE;
}
//不帶頭結點的尾刪，由于當鏈表只有一個元素時，刪除最后一個結點就要修改指針指向，因而就要用二級指針接收頭指針，用x放回刪除的數據
//刪除成功返回TRUE，失敗返回FALSE；
Status Delite_No_Head_Br_SeqNode(LinkList *Head,ElemType *x)
{
//定義臨時變量防止頭指針被修改 ,首先讓指向首元結點,尾刪用它來定位最后一個結點，
//由于單鏈表，只知道當前節點的下一個結點的位置，那么，就需要定義一個變量保存當前結點的地址
LinkList temp_node = (*Head)->next;
LinkList temp_node_pre = (*Head);
if(NULL == (*Head))
{
printf("鏈表已空，已無元素可以刪除\n");
return FALSE;
}
while(NULL != temp_node->next)
{
temp_node = temp_node->next;
temp_node_pre = temp_node_pre->next;
}
*x = temp_node->data; //保存最后一個結點的數據域的值
temp_node_pre->next = NULL; //修改原來結點的倒數第二個結點的指向
free(temp_node); //此時temp_node指向最后一個結點，防止內存泄露，釋放最后一個結點的內存
return TRUE;
}
//帶頭結點的按照位置刪除，首先要考慮刪除的位置是否存在，然后由于帶頭結點，所以無論是一個元素，還是多個元素刪除操作都一樣
Status Delite_Head_Pos_SeqNode(LinkList Head,int pos, ElemType *x)
{
//定義臨時變量防止頭指針被修改 ,首先讓指向首元結點,尾刪用它來定位最后一個結點，
//由于單鏈表，只知道當前節點的下一個結點的位置，那么，就需要定義一個變量保存當前結點的地址
LinkList temp = Head->next; //定位最后一個指針需要刪除的結點的前一個結點
LinkList temp_node_pre = Head; //保存即將刪除的結點的地址
if(NULL == temp)
{
printf("鏈表已空，已經沒有元素刪除\n");
return FALSE;
}
if(pos > temp_node_pre->data ) //判斷刪除的位置是否存在
{
printf("刪除位置出錯\n");
return FALSE;
}
for(int i = 0; i < pos-1;i++) //遍歷鏈表找到鏈表要刪除的結點的前一個結點
{
temp = temp->next; //定位要刪除的位置
}
*x = temp->next->data; //用x返回需要刪除結點的值
temp_node_pre = temp->next;
temp->next = temp->next->next; //讓刪除的前一個結點指向要刪除的下一個結點
free(temp_node_pre); //此時temp_node指向刪除的結點，防止空間泄露，釋放內存
temp_node_pre = NULL;
Head->data--; //頭結點保存著鏈表的長度，刪除以后減去一個
return TRUE;
}
按照位置刪除：同樣也不在給出示意圖：對比按照位置刪除的圖。
//不帶頭結點按照位置刪除，由于當只有一個結點的刪除需要修改頭指針指向需要特別處理
Status Delite_No_Head_Pos_SeqNode(LinkList *Head, int pos, ElemType *x)
{
int NUM = 0; //統計一共鏈表一共多少個結點
//定義臨時變量防止頭指針被修改 ,首先讓指向首元結點,尾刪用它來定位最后一個結點，
//由于單鏈表，只知道當前節點的下一個結點的位置，那么，就需要定義一個變量保存當前結點的地址
LinkList temp = (*Head);
if(NULL == temp)
{
printf("鏈表已空，已無元素可以刪除\n");
return FALSE;
}
else if(NULL == temp->next) //處理只有一個結點的情況
{
*x = temp->data; //用x返回需要刪除結點的值
(*Head) = NULL; //頭結點置空
free(temp); //釋放第一個結點的空間，防止內存泄露
temp = NULL; //防止指向非法空間
return TRUE;
}
else
{
while(NULL != temp)
{
NUM++;
temp = temp->next;
}
if(pos > NUM)
{
printf("刪除位置出錯");
return FALSE;
}
if(0 == pos)
{
temp = *Head;
*x = temp->data;
*Head = temp->next;
free(temp);
temp = NULL;
}
else
{
//當遍歷確定pos位置正確后，此時幾個指針的指向已經發生改變，需要重新指向頭指針，遍歷找到需要插入的結點
temp = *Head;
for(int i = 0; i < pos-1; i++)
{
temp = temp->next;
}
*x = temp->next->data; //用x返回需要刪除結點的值
LinkList free_node = temp->next; //free_node用與保存即將刪除的結點
temp->next = temp->next->next;
free(free_node); //釋放第一個結點的空間，防止內存泄露
free_node = NULL;
}
}
return TRUE;
}
打印輸出所有數據：
//帶頭結點打印輸出所有數據
Status Show_Node(LinkList Head)
{
LinkList temp = Head->next;
while(NULL != temp)
{
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
return TRUE;
}
//不帶頭結點打印輸出所有數據
Status Show_Node_No_Head(LinkList Head)
{
LinkList temp = Head;
while(NULL != temp)
{
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
return TRUE;
}
清空鏈表：釋放所有有效結點，對于帶頭結點鏈表，要把頭結點的 數據域置0
//不帶頭結點的清空鏈表，釋放所有的結點
Status Clean_No_Head_SeqNode(LinkList *Head )
{
LinkList temp_node = *Head;
LinkList temp_node_pre = *Head;
*Head = NULL;
while(NULL != temp_node)
{
temp_node = temp_node->next; //因為頭結點不空，讓臨時指針指向下一個結點
free(temp_node_pre); //釋放第一結點的空間
temp_node_pre = temp_node; //指向下一個空間
}
return TRUE;
}
//帶頭結點的清空鏈表，釋放除頭結點以外的空間
Status Clean_Head_SeqNode(LinkList Head)
{
LinkList temp_node = Head->next;
LinkList temp_node_pre = Head->next;
Head->next = NULL;
Head->data = 0;
while(NULL != temp_node->next)
{
temp_node = temp_node->next;
free(temp_node_pre);
temp_node_pre = temp_node;
}
return TRUE;
}
排序：對于排序，首先可以采用各種排序方法，然后就是排序過程中，我提一點就是只需要把值交換并不需要交換結點。這里采用冒泡排序。
//排序，由于只需要交換兩個鏈表中的值就好了，不用修改指針指向所以帶與不帶頭結點操作差不多,只是有細微的差別
Status Sort_No_Head_SeqNode(LinkList Head)
{
LinkList temp_node_i = Head;
LinkList temp_node_j = Head;
LinkList temp_node_pre = Head;
ElemType temp; //用與交換值
if(NULL == temp_node_i)
{
printf("鏈表為空，無法排序\n");
return FALSE;
}
for(temp_node_i = temp_node_i->next; NULL != temp_node_i; temp_node_i = temp_node_i->next)
{
for( temp_node_j = temp_node_j; NULL != temp_node_j; temp_node_j = temp_node_j->next)
{
if(temp_node_j->data > temp_node_pre->data)
{
temp = temp_node_j->data;
temp_node_j->data = temp_node_pre->data;
temp_node_pre->data = temp;
temp_node_pre = temp_node_pre->next;
}
temp_node_pre = temp_node_pre->next;
}
}
return TRUE;
}
//排序帶頭結點
Status Sort_Head_SeqNode(LinkList Head)
{
LinkList temp_node_i = Head->next;
LinkList temp_node_j = Head->next;
LinkList temp_node_pre = Head->next;
ElemType temp; //用與交換值
if(NULL == temp_node_i)
{
printf("鏈表為空，無法排序\n");
return FALSE;
}
for(temp_node_i = temp_node_i; NULL != temp_node_i->next; temp_node_i = temp_node_i->next)
{
for(temp_node_j = Head; NULL != temp_node_j->next; temp_node_j = temp_node_j->next)
{
if(temp_node_j->data > temp_node_j->next->data)
{
temp = temp_node_j->next->data;
temp_node_j->next->data = temp_node_j->data;
temp_node_j->data = temp;
}
}
}
return TRUE;
}
以上對單鏈表帶頭結點與不帶頭結點的頭插、尾插、按照位置插、頭刪、尾刪、按照位置刪除、清空鏈表、排序、打印輸出做了盡可能詳盡的注釋，都做了測試，但是沒有給出主函數，數據結構中，這里不是重點，并且限于篇幅，因而沒有給出主函數。當然以上代碼只是我的理解，大家可以如果發現那塊有錯誤，希望指正。
最后，細心的大家會發現這里邊有好多重發的代碼：比如生成新結點，定位要插入刪除的位置，有好多重復的代碼，那么就可以把它寫成一個函數，簡化代碼，更有，這種結構的結構體，操作起來有些不方便，如果采用下邊這種結構，更會簡化，并且便于理解。
typedef struct node //節點類型
{
type value;
struct node *next;
}Node;
typedef struct list
{
Node *phead;
Node *ptail;
}List;
感謝各位的閱讀，以上就是“c語言線性表的鏈式存儲結構是什么”的內容了，經過本文的學習后，相信大家對c語言線性表的鏈式存儲結構是什么這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
