數(shù)據(jù)結(jié)構(gòu)02-鏈表(單/雙/向普通及循環(huán)鏈表)
鏈表通常由一連串節(jié)點(diǎn)組成桅咆，每個(gè)節(jié)點(diǎn)包含任意的實(shí)例數(shù)據(jù)（data fields）和一個(gè)用來(lái)指向下一個(gè)節(jié)點(diǎn)地址的指針(next指針)涤姊。
- 數(shù)組內(nèi)存連續(xù)筑舅，需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)凤巨；
- 鏈表結(jié)構(gòu)內(nèi)存不需要連續(xù)味廊，可以充分利用計(jì)算機(jī)內(nèi)存空間介汹，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理巡雨。但失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)棍辕，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域暮现，空間開銷比較大
鏈表在插入的時(shí)候可以達(dá)到O⑴的復(fù)雜度，但是查找一個(gè)節(jié)點(diǎn)或者訪問(wèn)特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間楚昭。
1：?jiǎn)蜗蜴湵?/h1>
單向鏈表：指存放鏈表的結(jié)點(diǎn)中只有一個(gè)指針栖袋，指向它的下一個(gè)結(jié)點(diǎn)，而鏈表中最后一個(gè)結(jié)點(diǎn)的next指針為NULL抚太。
頭結(jié)點(diǎn)：鏈表中的第一個(gè)結(jié)點(diǎn)塘幅。只要知道了鏈表的頭結(jié)點(diǎn)，就可以通過(guò)next指針尿贫，遍歷整個(gè)鏈表电媳。因此，一般在函數(shù)中庆亡，我們使用頭結(jié)點(diǎn)來(lái)代表整個(gè)鏈表匆背，將頭結(jié)點(diǎn)傳參給函數(shù)。
單向鏈表的存儲(chǔ)結(jié)構(gòu)：
typedef struct _node {
int val;//值域身冀，可以增加更多的值域钝尸，這里僅以int類型為代表
struct _node *next;//指針域括享，指向下一個(gè)結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)指向NULL
} Node, *PNode;
單鏈表.png
1.1：創(chuàng)建
在創(chuàng)建鏈表過(guò)程中珍促，將新分配的一個(gè)鏈表結(jié)點(diǎn)插入到已知的鏈表中铃辖，可以分為兩種情況：從頭部插入和從尾部插入。
image.png
1.1.1：頭部插入創(chuàng)建
分析：
image.png
//從頭部插入創(chuàng)建鏈表算法
node *create_linklist_head() {
node *h = NULL;
while(1) {
node *p = (node*)malloc(sizeof(node));
if(p==NULL) {
return h;
}
memset(p,0,sizeof(node));
printf("Please input a data\n");
scanf_s("%d",&(p->val));
p->next = NULL;
if(h==NULL) {//頭結(jié)點(diǎn)指針為空猪叙，創(chuàng)建第一個(gè)結(jié)點(diǎn)
h=p;
} else {
p->next = h;
h=p;
}
if(p->value==0) {
break;
}
}
return h;
}
1.1.2：尾部插入創(chuàng)建
分析：
image.png
//從尾部插入鏈表算法
node *create_linklist_tail() {
node *h=NULL;
while(1) {
node *p = (node *)malloc(sizeof(node));
if(p==NULL) {
return h;
}
memset(p,0,sizeof(node));
printf("Please input a data\n");
scanf_s("%d",&p->value);
p->next = NULL;
if(h==NULL) { //頭結(jié)點(diǎn)指針為空娇斩，創(chuàng)建第一個(gè)結(jié)點(diǎn)
h=p;
} else {
node *q = h;//需要從頭部遍歷到尾部
while(q->next) {
q=q->next;
}
q->next = p;//q為尾部，q->next=p穴翩，將新建結(jié)點(diǎn)設(shè)置為尾部
p->next = NULL;
}
if(p->value==0) {//輸入為零犬第，則停止創(chuàng)建鏈表
break;
}
}
return h;
}
1.2：遍歷
void traverse_list(node *h) {
node *p = h;
while(p) {
printf("%d ",p->value);
p=p->next;
}
printf("\n");
}
1.3：插入
將鏈表結(jié)點(diǎn)插入到某個(gè)指定的結(jié)點(diǎn);
分析：
image.png
//在頭結(jié)點(diǎn)之前插入某節(jié)點(diǎn)
bool insert_linklist_in_head_front(Node **h, int data) {
Node *p = *h;
if (p == NULL) {
return false;
}
Node *node = (Node *)malloc(sizeof(Node));
if (node == NULL) {
return false;
}
memset(node, 0, sizeof(Node));
node->val = data;
node->next = p;
*h = node;//改變h的值，需要傳h的地址
return true;
}
//在尾結(jié)點(diǎn)之后插入某節(jié)點(diǎn)
bool insert_linklist_in_tail_behead(Node *h, int data) {
Node *p = h;
if (p == NULL) {
return false;
}
Node *node = (Node *)malloc(sizeof(Node));
if (node == NULL) {
return false;
}
memset(node, 0, sizeof(Node));
node->val = data;
node->next = NULL;//node之后要變?yōu)槲补?jié)點(diǎn)
while (p->next) {
printf("%d ", p->val);
p = p->next;
}
p->next = node;
return true;
}
//index_in_front(從0開始)
bool insert_linklist(Node **h, int index, int data) {//在鏈表h第index節(jié)點(diǎn)插入data
Node *p = *h;
if (!p) {
return false;
}
Node *node = (Node *)malloc(sizeof(Node));
if (node == NULL) {
return false;
}
memset(node, 0, sizeof(Node));
node->val = data;
node->next = NULL;//node防止野指針
if (index == 0) {
node->next = p;
*h = node;//改變h的值芒帕，需要傳h的地址
printf("0位置插入成功\n");
return true;
}
int i = 0;
Node *swap;
while (i < index - 1) {
p = p->next;
++i;
}
swap = p->next;//把下一個(gè)節(jié)點(diǎn)的地址歉嗓，給用于交換的swap
p->next = node;//把要插入的節(jié)點(diǎn)的地址，給上個(gè)節(jié)點(diǎn)的指針域
node->next = swap;//把插入節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的地址背蟆，給插入節(jié)點(diǎn)的指針域
return true;
}
int main(int argc, const char * argv[]) {
printf("頭部插入節(jié)點(diǎn)創(chuàng)建鏈表: Please creat_linklist_head\n");
Node *head1 = creat_linklist_head();//
printf("遍歷節(jié)點(diǎn)head1: Please traverse_list\n");
traverse_list(head1);
//在尾結(jié)點(diǎn)之后插入某節(jié)點(diǎn)
printf("插入某節(jié)點(diǎn): Please input a data\n");
int k;
scanf("%d", &k);
printf("插入節(jié)點(diǎn)的位置index：\n");
int index;
scanf("%d", &index);
bool binsert_linklist = insert_linklist(&head1, index, k);
if (binsert_linklist) {
printf("插入成功遍歷節(jié)點(diǎn)head1: Please traverse_list\n");
traverse_list(head1);
} else {
printf("插入錯(cuò)誤\n");
}
}
1.3：刪除
分析：
image.png
void del_list_node(node **h,int value) {
if(h==NULL) {
return;
}
node *p = *h;
node *q = NULL;
while(p) {
if(p->value==value) {
if(p==h) {
//改變指針的值鉴分，需要在傳參時(shí)傳二級(jí)指針
*h=(*h)->next;
free(p);
p = NULL;
return;
} else {
q->next=p->next;
free(p);
p = NULL;
}
return;
}
q=p;
p = p->next;
}
}
1.5：銷毀
void destroy_list(node \*p) {
node \*p =h;
while(p) {
node *q=p;//先用q保存這個(gè)待刪除的結(jié)點(diǎn)
p=p->next;//p指向下一個(gè)結(jié)點(diǎn)
free(q);//現(xiàn)在可以刪除q了
}
}
1.6：?jiǎn)蜗蜓h(huán)鏈表
循環(huán)鏈表：最后一個(gè)結(jié)點(diǎn)的指針是指向該循環(huán)鏈表的第一個(gè)結(jié)點(diǎn)或者表頭結(jié)點(diǎn)，從而構(gòu)成一個(gè)環(huán)形的鏈带膀。
單向循環(huán)鏈表的遍歷：判斷該結(jié)點(diǎn)鏈域的值是否是表頭結(jié)點(diǎn)志珍，當(dāng)鏈域值等于表頭指針時(shí)，說(shuō)明已到表尾垛叨。而非循環(huán)單鏈表判斷鏈域值是否為NULL伦糯。
單向循環(huán)鏈表的4種不同的形式：
image.png
1.6.1：?jiǎn)蜗蜓h(huán)鏈表的創(chuàng)建
Node *create_list_loop() {
Node *h = NULL;
while(1) {
Node *node = (Node *)malloc(sizeof(Node));
if(node == NULL) {
return h;
}
memset(node, 0, sizeof(Node));
printf("Please input a data\n");
scanf("%d",&(node->val));
node->next = NULL;
if(h == NULL) {//如果頭結(jié)點(diǎn)指針為空，表明這是創(chuàng)建的第一個(gè)結(jié)點(diǎn)
h = node;
node->next = h;//單個(gè)節(jié)點(diǎn)的循環(huán)鏈表
} else {
Node *q = h;
while(q->next != h) {//q->next如果等于h嗽元，那么q就是最后一個(gè)結(jié)點(diǎn)
q = q->next;
}
q->next = node;
node->next = h;//將p的next指針指向h舔株，構(gòu)成一個(gè)循環(huán)
}
if(node->val == 0) {
break;
}
}
return h;
}
1.6.2：?jiǎn)蜗蜓h(huán)鏈表的遍歷
void traverse_loop_list(node *h) {
if(h==NULL)
return;
node *p = h;
do {
printf("%d ",p->value);
p = p->next;
} while(p != h);
printf("\n");
}
1.6.3：?jiǎn)蜗蜓h(huán)鏈表的銷毀
void destroy_loop_list(node *h) {
if(h==NULL)
return;
node *p = h->next;//防止頭結(jié)點(diǎn)銷毀,所以從第二個(gè)開始
do {
node *q = p;
p = p->next;
free(q);
} while (p != h);
free(h);
}
1.6.4：判斷鏈表是否含有循環(huán)
//步長(zhǎng)法判斷鏈表是否含有循環(huán)
//思路是：定義2個(gè)指針遍歷該鏈表，1個(gè)指針跑一步还棱，1個(gè)指針跑兩步载慈；
//那么如果兩個(gè)指針相遇，則表示有循環(huán)珍手，否則無(wú)循環(huán)办铡。
bool is_a_loop_list(node *h) {
node *p = h;
node *q = h->next;
while(p&&q&&q!=p&&q->next) {
p=p->next;
q=q->next->next;
}
if(p==q) {//循環(huán)退出，p和q相等了琳要，表示鏈表中存在循環(huán)
return true;
}
return false;
}
2：雙向鏈表
雙向鏈表：結(jié)點(diǎn)除含有數(shù)據(jù)域外寡具，還有兩個(gè)鏈域，一個(gè)存儲(chǔ)直接后繼結(jié)點(diǎn)地址稚补，一般稱之為右鏈域童叠；一個(gè)存儲(chǔ)直接前驅(qū)結(jié)點(diǎn)地址，一般稱之為左鏈域。
雙向鏈表的存儲(chǔ)結(jié)構(gòu)定義如下：
typedef struct _dnode {
int data;
struct _dnode *pre;//前向指針厦坛，指向結(jié)點(diǎn)左邊的結(jié)點(diǎn)
struct _dnode *next;//后繼指針五垮，指向結(jié)點(diǎn)右邊的結(jié)點(diǎn)
} dnode, *pdnode;
image.png
2.1：創(chuàng)建
創(chuàng)建雙向鏈表，將一個(gè)新建的結(jié)點(diǎn)p杜秸，插入已知的雙向鏈表中放仗，有2種插入方法：
- 直接插入頭部
- 直接插入尾部
image.png
//1. 從頭部插入方法創(chuàng)建雙向鏈表：
dnode *create_dobulelist_head() {
dnode *h = NULL;
while(1) {
dnode *p = (dnode *)malloc(sizeof(dnode));
if(p == NULL) {
return h;
}
memset(p, 0, sizeof(p));
printf("Please input your data\n");
scanf_s("%d",&p->value);
p->next = p->pre = NULL;
if(h==NULL){ //如果頭結(jié)點(diǎn)指針為空，表明這是創(chuàng)建的第一個(gè)結(jié)點(diǎn)
h = p;
} else {
p->next = h;
h->pre = p;
h = p;
}
if(p->value==0) {
break;
}
}
return h;
}
//2. 從尾部插入創(chuàng)建雙向鏈表：
dnode *create_dobulelist_tail() {
dnode *h = NULL;
while(1) {
dnode *p = (dnode *)malloc(sizeof(dnode));
if(p==NULL){
return h;
}
memset(p,0,sizeof(p));
printf("Please input your data\n");
scanf_s("%d",&p->value);
p->next = p->pre = NULL;
if (h==NULL) {//如果頭結(jié)點(diǎn)指針為空撬碟，表明這是創(chuàng)建的第一個(gè)結(jié)點(diǎn)
h = p;
} else {
dnode *q = h;
while(q->next) {//需要先從頭結(jié)點(diǎn)開始遍歷到尾結(jié)點(diǎn)
q=q->next;
}
q->next = p;
p->pre=q;
p->next = NULL;
}
if(p->value==0) {//創(chuàng)建循環(huán)退出
break;
}
}
return h;
}
2.2：插入
如圖：將一個(gè)結(jié)點(diǎn)p插入到雙向鏈表q的后面下面演示順序插入
image.png
dnode *create_sorted_dlist() {
dnode *h = NULL;
while(1) {
dnode *p = (dnode *)malloc(sizeof(dnode));
if(p == NULL) {
return h;
}
memset(p, 0, sizeof(p));
printf("Please input your data\n");
scanf_s("%d", &(p->value));
p->next = p->pre = NULL;
if(h==NULL){ //如果頭結(jié)點(diǎn)指針為空诞挨，表明這是創(chuàng)建的第一個(gè)結(jié)點(diǎn) h = p;
} else {
dnode *q = h;
dnode *r = NULL;
while(q && q->val<p->val) {
r = q;//用r記錄下q的前一個(gè)結(jié)點(diǎn)
q = q->next
}
//q非空，說(shuō)明在鏈表中找到了一個(gè)節(jié)點(diǎn)呢蛤，值比p->val大惶傻，此時(shí)p應(yīng)插入到q的前面，r的后面
if(q) {//q非空
if (q == h) {
p->next = h;
h->pre = p;
h = p;
} else {
r->next = p;//r->next->pre = p;
p->pre = r;//
p->next = q;//p->next = r->next;
q->pre = p;//r->next->pre = p;
}
} else {//q為空其障，r為尾節(jié)點(diǎn)
r->next = p;
p-pre = r;
}
p->next = h;
h->pre = p;
h = p;
}
if(p->value==0) {
break;
}
if(p->value==0) {//創(chuàng)建循環(huán)退出
break;
}
}
return h;
}
2.3：遍歷
void traverse_dlist_next(dnode *h) {
dnode *p=h;
while(p) {
printf("%d ",p->value);
p = p->next;
}
printf("\n");
}
2.4：銷毀
void destroy_dlist(dnode *h) {
dnode *p = h;
while(p) {
dnode *q = p;
p = p->next;
free(q);
}
}
2.5：刪除
雙向鏈表中项郊，將一個(gè)結(jié)點(diǎn)p從雙向鏈表中刪除方法：
image.png
int del_dlist_value(dnode **h, int value) {
if (*h == NULL) {
return 0;
}
node *p = *h;
while(p) {
if(p->value == value) {
if(p == *h) {//頭結(jié)點(diǎn)
*h = (*h)->next;
(*h)->pre = NULL;
} else if (p->next == NULL) {
p->pre->next = NULL;
} else {
p->pre->next = p->next;
p->next->pre = p->pre;
}
free(p);
}
p = p->next;
}
}
2.6：雙向循環(huán)鏈表
雙向循環(huán)鏈表既是雙向鏈表包竹，又是循環(huán)鏈表愉择。頭結(jié)點(diǎn)的左鏈域指向最后一個(gè)結(jié)點(diǎn)严衬，最后一個(gè)結(jié)點(diǎn)的右鏈域指向頭結(jié)點(diǎn)巡李。
image.png
