單鏈表

---

鏈表的基本概念

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

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

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

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

二、單鏈表的特點(diǎn)

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

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

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

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

單鏈表和數(shù)組的區(qū)別：數(shù)組是順序存儲(chǔ)的，而單鏈表是鏈?zhǔn)酱鎯?chǔ)的。

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

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

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

單鏈表的初始化

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

單鏈表頭插法

單鏈表的輸出

單鏈表的查找

單鏈表修改

單鏈表的刪除

• 單鏈表刪除結(jié)點(diǎn)的補(bǔ)充：
  

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

源代碼

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