單鏈表

---

鏈表的基本概念

一、什么是鏈表？
鏈表是數(shù)據(jù)結(jié)構(gòu)中線性表的一種，其中的每個元素實際上是一個單獨的結(jié)構(gòu)體對象，而所有對象都通過每個元素中的指針鏈接在一起。

什么是結(jié)點：鏈表中每個結(jié)構(gòu)體對象叫做結(jié)點。

什么是首元結(jié)點：其中第一個數(shù)據(jù)結(jié)點。

什么是頭結(jié)點：如果第一個結(jié)點不用于存儲數(shù)據(jù)，只用于代表鏈表的起始點，則這個結(jié)點稱為鏈表的頭結(jié)點。

二、單鏈表的特點

1、單鏈表沒有固定的長度，可以自由增加節(jié)點。

2、單鏈表能夠?qū)崿F(xiàn)快速的插入刪除數(shù)據(jù)。

3、與數(shù)組類似，單鏈表也是一種線性數(shù)據(jù)結(jié)構(gòu)。

4、單鏈表的尾結(jié)點的后繼必定指向空。

單鏈表和數(shù)組的區(qū)別：數(shù)組是順序存儲的，而單鏈表是鏈式存儲的。

鏈表的結(jié)構(gòu)示意圖：

單鏈表功能的實現(xiàn)

鏈表的基本操作：增、刪、改、查。
單鏈表節(jié)點的插入和刪除結(jié)構(gòu)示意圖：

單鏈表的初始化

單鏈表新結(jié)點的創(chuàng)建

單鏈表頭插法

單鏈表的輸出

單鏈表的查找

單鏈表修改

單鏈表的刪除

• 單鏈表刪除結(jié)點的補充：
  

單鏈表所有數(shù)據(jù)結(jié)點釋放

源代碼

#include<stdio.h>
#include<stdlib.h>
#define TYPE int //數(shù)據(jù)類型通過定義宏的形式來進行靈活運用
#define PRINT(a) printf("%d-->", a)
#define PRINTINDEX(b, c) printf("元素值是%d\t 位置是%d\n\n", b,c)
//結(jié)點的類型 聲明結(jié)點的類型
struct NODE
{int data; //數(shù)據(jù)域struct NODE*next; //指針域保存下一個結(jié)點的地址 struct NODE*//next是一個成員
};//頭結(jié)點類型 鏈表結(jié)構(gòu)
struct List
{int len; //保存單鏈表中的結(jié)點個數(shù)（不包括頭結(jié)點）struct NODE*front; //頭指針 指向首元結(jié)點struct NODE*back; //尾指針 指向尾結(jié)點
};//創(chuàng)建單鏈表結(jié)構(gòu) 從堆區(qū)來申請內(nèi)存 把首地址返回給list
struct List*initList()
{//申請單鏈表結(jié)構(gòu)內(nèi)存struct List*temp = (struct List*)malloc(sizeof(struct List));//初始化單鏈表結(jié)構(gòu)的成員temp->len = 0;temp->front = NULL;temp->back = NULL;return temp;
}//單鏈表結(jié)點的創(chuàng)建
struct NODE*CreateNode(TYPE data)
{struct NODE*temp = (struct NODE*)malloc(sizeof(struct NODE));temp->data = data; //把數(shù)據(jù)放進新結(jié)點temp->next = NULL; //防止野指針的出現(xiàn)return temp;
}//單鏈表結(jié)點的插入 頭插法
void insertHead(struct List*head, TYPE data) //list表示要增加數(shù)據(jù)的單鏈表
{//1、作為第一個數(shù)據(jù)結(jié)點插入單鏈表中  頭指針與尾指針都需要改變指向if (head->front == NULL) //或者head->len == 0{//1、要生成一個新的結(jié)點//2、讓頭指針和尾指針都指向這個新結(jié)點head->front = head->back = CreateNode(data);head->len++;//單鏈表結(jié)點的數(shù)量+1}else//不是第一個數(shù)據(jù)結(jié)點 只需改變頭指針的指向{//生成一個新的結(jié)點struct NODE*S = CreateNode(data);//新結(jié)點S指針域保存原來的首元結(jié)點的地址S->next = head->front;//更新頭指針，指向新結(jié)點Shead->front = S;head->len++; //單鏈表結(jié)點的數(shù)量+1}
}//輸出單鏈表中所有的數(shù)據(jù)
void print(struct List*head)
{struct NODE*p = head->front;while (p != NULL){PRINT(p->data); //輸出p指向的結(jié)點里面的數(shù)據(jù)p = p->next; //p指向下一個結(jié)點//p++;不能使用，單鏈表的物理內(nèi)存不連續(xù)}printf("\n\n");
}//單鏈表元素的查找 根據(jù)指定值來查找元素，并且輸出元素的位置
void find(struct List*head, int val) //head=list val表示要查找的數(shù)據(jù)
{struct NODE*p = head->front;//p指向首元結(jié)點int index = 0; //index表示指定元素的位置while (p != NULL){index++;if (p->data == val){PRINTINDEX(p->data, index);//輸出元素值和位置}p = p->next; //p指向下一個結(jié)點}
}//單鏈表元素的修改 根據(jù)指定值
void modify(struct List*head, TYPE val, TYPE data)
//val要被修改的數(shù)據(jù) data要修改成的數(shù)據(jù)
{struct NODE*p = head->front; //p指向首元結(jié)點while (p != NULL){if (p->data == val){p->data = data;//修改數(shù)據(jù)}p = p->next; //p指向下一個結(jié)點}
}//單鏈表的刪除 根據(jù)指定值來刪除數(shù)據(jù)
void delete(struct List*head, TYPE val) //head=list val表示要被刪除的數(shù)據(jù)
{//1、要找到要被刪除的數(shù)據(jù)struct NODE*p1 = head->front; //p指向首元結(jié)點struct NODE*p2 = NULL;while (p1 != NULL){if (p1->data == val) //找到了要被刪除的數(shù)據(jù){//情況一：p1指向是首元結(jié)點，需要更新頭指針的指向if (p1 == head->front){head->front = p1->next; //讓p1的直接后繼結(jié)點成為新的首元結(jié)點free(p1);p1 = head->front; //讓p1指向新的首元結(jié)點}//情況二：p1指向的是尾結(jié)點，需要更新尾指針else if (p1 == head->back){p2->next = p1->next; //給尾指針的結(jié)點域置空head->back = p2;free(p1);p1 = NULL;}//情況三：p1指向的結(jié)點是中間結(jié)點else{//p2的指針域指向p1的后繼結(jié)點p2->next = p1->next;//釋放刪除結(jié)點free(p1);//更新p1p1 = p2->next;}}else //p2指向p1的前驅(qū)節(jié)點{p2 = p1;p1 = p1->next;}}
}//假設(shè)頭結(jié)點也是struct node
void delete2(struct NODE*head, TYPE val) //val表示要被刪除的數(shù)據(jù)
{struct NODE*p1 = head;struct NODE*p2 = head->next;while (p2 != NULL){if (p2->data = val){p1->next = p2->next;free(p2);p2->next = p1->next;}else{p1 = p1->next;p2 = p2->next;}}
}//整個單鏈表結(jié)點的釋放 釋放所有的數(shù)據(jù)結(jié)點 不是釋放頭節(jié)點
void AllClear(struct List*head)
{struct NODE*p = head->front; //p指向首元結(jié)點while (p != NULL){head->front = p->next;free(p);p = head->front;}head->front = head->back = NULL;//防止野指針出現(xiàn)
}int main()
{struct List *list = NULL; //list指向單鏈表 通過list來管理這個單鏈表list = initList(); //調(diào)用創(chuàng)建單鏈表函數(shù)//插入5個數(shù)據(jù)for (int j = 1; j <= 5; j++){insertHead(list, j);}print(list);//find(list, 4);//modify(list, 5, 9);//print(list);delete(list, 4);print(list);AllClear(list);print(list);return 0;
}