數據結構——線性表（C語言實現）

寫在前面：

? ? ? ? 在前面C語言的結構體學習中，我提及了鏈表的操作，?學習數據結構我認為還是需要對C語言的數組、函數、指針、結構體有一定的了解，不然對于結構體的代碼可能很難理解，特別是一些書籍上面用的還是偽代碼，就很難理解。所以我建議大家可以看看我前面C語言的篇章，其實在C語言的結構體這篇博客中我已經引入了數據結構中——鏈表的使用，只不過相對簡單，其動態鏈表對應的就是本章的單鏈表的一些內容，所以有了那篇博客，就能很好的順應到數據結構上來。

C語言——結構體-CSDN博客

一、線性表概述

? ? ? ? 線性結構包括：線性表、棧、隊列、串和數組；

? ? ? ? 線性結構的特點是：除了第一個元素沒有前驅，最后一個元素沒有后繼以外，其余的元素的都有前驅和后繼。

? ? ? ? 線性表是最常用的線性結構，由有限個特性相同的元素構成的序列稱為線性表；

線性表的特點：

1、存在唯一的元素被稱為“第一個”數據元素；

2、存在唯一的元素被稱為“最后一個”數據元素；

3、除第一個元素外，結構中每個元素都有一個前驅；

4、除最后一個元素外，結構中每一個元素都有一個后繼；

線性表按照存儲方式分為：順序存儲與鏈式存儲。?

二、順序表

線性表的順序存儲——順序表；

線性表的鏈式存儲——鏈表；?

順序表基本上就是數組，其邏輯上是相鄰的元素，其物理地址也是相鄰的。

2.1靜態初始化

? ? ? ? 這個靜態和動態如何區分呢？

? ? ? ? 在前面的C語言的結構體中，我們指出動態內存分配；

? ? ? ? 我們講，全局變量定義在內存的靜態存儲區，局部變量定義在內存中的動態存儲區；這個存儲區稱為棧區。

? ? ? ? 除此之外，內存還允許建立動態分配區域，用來存放臨時的數據，這些數據需要時隨時開辟，不需要時隨時釋放，這個區域稱為堆區。

? ? ? ? 對于內存的動態分配是通過系統提供的庫函數實現的，主要有malloc,calloc,free,recalloc函數。

????????也就是說，我們直接定義一個數組，那這個數組就是靜態的，我們利用動態庫函數定義一個數組，那這個數組就是動態存儲的。

#include <stdio.h>
#define MAXSIZE 10
typedef struct //創建一個結構體，其成員有兩個一個是data數組，用來存放數據，一個是變量length，用來存放數據長度。
{int data[MAXSIZE];int length;
}SeqList;//靜態初始化
void InitList(SeqList *L)
{for (int i = 0; i < MAXSIZE; i++){L->data[i] = 0;}L->length =0;
}int main()
{SeqList L;InitLink(&L);return 0;
}

?運行結果：創建靜態順序表，沒有什么輸出；只不過先定義了一個結構體，然后將數組作為一個成員存放在里面， 然后結構體里面還有一個變量，用來表示當前順序表的長度。

后面的增刪查改基本上和動態表是一樣的，所以就只介紹動態順序表的使用；?

?2.2動態初始化

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
typedef struct //創建一個結構體類型
{int * data;//指向動態分配數組的指針int Max;//順序表的最大容量int length;//順序表目前的長度
}SeqList;void InitList(SeqList * L)
{L->data = (int *)malloc(MAXSIZE*sizeof(int));L->length = 0;L->Max = MAXSIZE;
}int main()
{SeqList L;InitList(&L);
}

????????運行結果與上面一樣；我們需要注意的是，在使用動態順序表初始化的時候，我們并沒有直接定義數組，而是利用malloc函數動態的創建了一塊內存地址，這個地址的大小是由規則的小空間組成，所存儲的數據性質是一樣的，

2.2.1增

? ? ? ? 增也可以說是插入，就是在原有的線性表基礎上再插入一個元素；需要注意的是：

1、插入一次只能插入一個元素；

2、插入元素的位置要合理。即下圖：

3、插入元素前，順序表的大小要小于最大容量；

????????上圖表中，最大長度和位置為上面數組12345678910；數組的編號是從a[0]開始，那也就需要注意，第i個位置的元素對應的是數組的a[i-1];

????????當length的長度為0，也就是空表的時候，我們只能往1的那位置插入。?

????????當length的長度為1，我們只能往1和2的那位置插入。往1插入23就會移到后面2的位置，1中為新插入的數據。

? ? ? ? 所以插入元素的位置要合理——i>1 以及?i<=length + 1;插入位置不能為0，沒有0這個位置，插入位置不能大于長度+1，不然就不連續，長度+1的位置就會空出來。

? ? ? ? 此外，插入位置之前，lengh的長度要小于最大容量，因為插入后length+1最多只能和最大容量一樣大，要不然就會溢出。

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
typedef struct //創建一個結構體
{int * data;//指向動態分配數組的指針int Max;//順序表的最大容量int length;//順序表目前的長度
}SeqList;void InitList(SeqList * L)
{L->data = (int *)malloc(MAXSIZE*sizeof(int));L->length = 0;L->Max = MAXSIZE;
}int InsertList(SeqList * L, int i,int e)
{if (i<1 || i> L->length + 1){printf("插入位置不合法\n");return 0;}if (L->length >= L->Max){printf("當前存儲空間已滿\n");}for (int j = L->length; j >= i; j--){L->data[j] = L->data[j - 1];}L->data[i - 1] = e;L->length++;return 1;
}
void PrintfList(SeqList  L)
{for (int i = 1; i <= L.length; i++){printf("%d->", L.data[i - 1]);}printf("NULL\n");}int main()
{SeqList L;InitList(&L);PrintfList(L);InsertList(&L, 1, 1);//在第一個位置插入數據1；PrintfList(L);InsertList(&L, 1, 2);//在第一個位置插入數據2；PrintfList(L);InsertList(&L, 2, 3);//在第二個位置插入數據3；PrintfList(L);InsertList(&L, 4, 4);//在第四個位置插入數據4；PrintfList(L);InsertList(&L, 6, 1);//在第六個位置插入數據1；PrintfList(L);}

2.2.2刪

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
typedef struct //創建一個結構體
{int * data;//指向動態分配數組的指針int Max;//順序表的最大容量int length;//順序表目前的長度
}SeqList;void InitList(SeqList * L)
{L->data = (int *)malloc(MAXSIZE*sizeof(int));L->length = 0;L->Max = MAXSIZE;
}int InsertList(SeqList * L, int i,int e)
{if (i<1 || i> L->length + 1){printf("插入位置不合法\n");return 0;}if (L->length >= L->Max){printf("當前存儲空間已滿\n");}for (int j = L->length; j >= i; j--){L->data[j] = L->data[j - 1];}L->data[i - 1] = e;L->length++;return 1;
}int DeleteLink(SeqList * L, int i)
{if (i<1 || i> L->length + 1){printf("刪除位置不合法\n");return 0;}if (L->length <= 0){printf("當前存儲空間為0\n");}int e = L->data[i - 1];for (int j = i; j < L->length; j++){L->data[j-1] = L->data[j];}L->length--;return e;}void PrintfList(SeqList  L)
{for (int i = 1; i <= L.length; i++){printf("%d->", L.data[i - 1]);}printf("NULL\n");}int main()
{int e;SeqList L;InitList(&L);InsertList(&L, 1, 1);InsertList(&L, 1, 2);InsertList(&L, 2, 3);InsertList(&L, 4, 4);PrintfList(L);e=DeleteLink(&L, 2);printf("刪除的元素的值為：%d\n", e);PrintfList(L);
}

運行結果：?

2.2.3查

????????查找分為按位查找與按值查找，按位查找直接利用L->data[i-1]就可以把第i位的值查找出來，沒有多大意義，我們重點來說一下按位查找；

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
typedef struct //創建一個結構體
{int * data;//指向動態分配數組的指針int Max;//順序表的最大容量int length;//順序表目前的長度
}SeqList;void InitList(SeqList * L)
{L->data = (int *)malloc(MAXSIZE*sizeof(int));L->length = 0;L->Max = MAXSIZE;
}int InsertList(SeqList * L, int i,int e)
{if (i<1 || i> L->length + 1){printf("插入位置不合法\n");return 0;}if (L->length >= L->Max){printf("當前存儲空間已滿\n");}for (int j = L->length; j >= i; j--){L->data[j] = L->data[j - 1];}L->data[i - 1] = e;L->length++;return 1;
}int DeleteLink(SeqList * L, int i)
{if (i<1 || i> L->length + 1){printf("刪除位置不合法\n");return 0;}if (L->length <= 0){printf("當前存儲空間為0\n");}int e = L->data[i - 1];for (int j = i; j < L->length; j++){L->data[j-1] = L->data[j];}L->length--;return e;}int ReserchList(SeqList  L, int e)
{for (int i = 0; i < L.length; i++){if (e = L.data[i]){return i + 1;}}printf("查找失敗，沒有該元素的值；\n");return 0;
}void PrintfList(SeqList  L)
{for (int i = 1; i <= L.length; i++){printf("%d->", L.data[i - 1]);}printf("NULL\n");}int main()
{int e;SeqList L;InitList(&L);InsertList(&L, 1, 1);InsertList(&L, 1, 2);InsertList(&L, 2, 3);InsertList(&L, 4, 4);PrintfList(L);e = ReserchList(L, 2);printf("查找后，該值的位置為%d\n", e);}

2.2.4擴容

? 擴容是只針對動態內存的，擴容的步驟：

1、生成指向原來順序表的存儲空間的指針；
2、為順序表開辟新的一塊更大的空間
3、數據轉移；
4、修改順序表的最大長度；
5、用free釋放掉原有的空間。

int IncreatSize(SeqList * L, int len)
{
?? ?int * p = L->data;

?? ?L->data = (int*)malloc((L->Max + len)*sizeof(int));

?? ?for (int i = 0; i < L->length; i++)
?? ?{
?? ??? ?L->data[i] = p[i];
?? ?}
?? ?L->Max += len;
?? ?free(p);
?? ?return 0;
}

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10
typedef struct //創建一個結構體
{int * data;//指向動態分配數組的指針int Max;//順序表的最大容量int length;//順序表目前的長度
}SeqList;void InitList(SeqList * L)
{L->data = (int *)malloc(MAXSIZE*sizeof(int));L->length = 0;L->Max = MAXSIZE;
}int InsertList(SeqList * L, int i,int e)
{if (i<1 || i> L->length + 1){printf("插入位置不合法\n");return 0;}if (L->length >= L->Max){printf("當前存儲空間已滿\n");}for (int j = L->length; j >= i; j--){L->data[j] = L->data[j - 1];}L->data[i - 1] = e;L->length++;return 1;
}int DeleteLink(SeqList * L, int i)
{if (i<1 || i> L->length + 1){printf("刪除位置不合法\n");return 0;}if (L->length <= 0){printf("當前存儲空間為0\n");}int e = L->data[i - 1];for (int j = i; j < L->length; j++){L->data[j-1] = L->data[j];}L->length--;return e;}int ReserchList(SeqList  L, int e)
{for (int i = 0; i < L.length; i++){if (e = L.data[i]){return i + 1;}}printf("查找失敗，沒有該元素的值；\n");return 0;
}void PrintfList(SeqList  L)
{for (int i = 1; i <= L.length; i++){printf("%d->", L.data[i - 1]);}printf("NULL\n");}//擴容：
/*
1、生成指向原來順序表的存儲空間的指針；
2、為順序表開辟新的一塊更大的空間
3、數據轉移；
4、修改順序表的最大長度；
5、用free釋放掉原有的空間。
*/
int IncreatSize(SeqList * L, int len)
{int * p = L->data;L->data = (int*)malloc((L->Max + len)*sizeof(int));for (int i = 0; i < L->length; i++){L->data[i] = p[i];}L->Max += len;free(p);return 0;
}

三、單鏈表

3.1概述

? ? ? ? 鏈表：邏輯上相鄰的數據元素，其物理地址不一定相鄰；用一組任意的存儲單元存儲線性表的元素（這組存儲單元可以是連續的，也可以是不連續的。）因此，為了表示每個數據元素與前后元素的關系，對于某個元素來說，存儲的不僅是本身的信息，還需要指定下一個元素的信息；

? ? ? ? 這種由兩部分組成的數據元素的存儲，稱為結點；它包括兩個域：

????????存儲數據元素信息的區域稱為數據域；

????????存儲后繼元素位置的區域稱為指針域；

? ? ? ? 由于線性表的鏈式存儲，每個節點中只包含一個指針域，故稱為線性鏈表或者單鏈表；

一般情況下，為了處理方便，在單鏈表的第一個節點之前附設一個節點，稱之為頭結點。如圖紅色框中的結點；

?首元結點：指鏈表中存儲第一個數據元素的結點，上圖中，數據區域為1的結點。

?頭結點：是在首元結點之前附設的一個節點，其指針域指向首元結點，頭結點的數據域不存儲任何信息，也可以存儲一些附加信息。例如：如果當數據域的元素為整數型時，頭結點的數據域可存放該線性表的長度。

?頭指針：指向鏈表的第一個結點的指針，若鏈表設有頭結點，則頭指針所指結點為頭結點，如果不設頭結點，頭指針指向首元結點。

3.2單鏈表

?3.2.1初始化

在初始化之前我們先創建鏈表所需要的結點——即定義結構體類型：

typedef struct Node//定義一個結構體，并用typedef進行替換，即struct Node——Node；
{int data;			//數據域，本次采用整形；struct Node * next;//指針域，指針類型為結構體指針；
}Node;

初始化單鏈表：

? ? ? ? 生成一個新的節點，用頭指針指向頭結點。頭結點的指針域置空；

Node * InitList() //定義一個初始化函數，其返回值為結構體指針，即將構建的鏈表首地址返回；
{Node * head;//定義一個頭指針；head= (Node *)malloc(sizeof(Node));//創建一個節點，并讓頭指針指向該節點，該節點也就是頭結點；head->data = 0;//頭結點的數據域為0；head->next = NULL;//頭結點的指針域為空；return head;//返回頭結點的地址
}

3.2.2插入?

前插法：

? ? ? ? 前插法是將新的結點逐個插入鏈表的頭部（頭結點的后面），每次申請一個新的節點，將其進行插入。

void HeadInsert(Node * L,int data)//定義一個前插函數，函數的參數分別為，鏈表的地址，以及新插入的元素值；
{Node * node = (Node *) malloc(sizeof(Node));//構建一個新的結點，然后返回其地址；node->data = data;//將傳入的數據存放在新節點的數據域；node->next = L->next;//將原來的頭結點的指針域的值，存放在新節點的指針域中；L->next = node;//將新節點的地址存放在頭指針的指針域；L->data++;//頭結點的數值域的數值加1，表示鏈表增加一個長度；
}

后插法：

? ? ? ? 后插法是通過將新節點逐個插入到鏈表的尾部，同前插法相同，每次申請一個新結點，將數值進行存放，不同的是，為了使新結點能夠插入到末尾，需要增加一個尾指針，尾指針指向鏈表的尾結點；

void TailInsert(Node * L, int data)//定義一個后插函數，函數的參數分別為，鏈表的地址，以及新插入的元素值；
{Node * node=L;//定義一個指針，類型為結構體指針；int i ;for (i = 0; i < L->data; i++)//將指針指向尾結點；{node = node->next;}Node * n = (Node *) malloc(sizeof(Node));//創建一個新的結點，將創建的結點的地址先放在n中；node->next = n;//將新結點的地址存放在尾結點的指針域；n->data = data;//將新元素的數據存放在新結點的數據域；n->next = NULL;//新結點重新作為尾結點，其指針域為空；L->data++;//頭結點的數值域數值加1；表示鏈表的長度+1；
}

3.2.3刪除?

? ? ? ? ?刪除指定位置的結點，首先應該找到該位置的前驅結點，在單鏈表刪除之前應將前驅結點的指針域的地址改為其后繼結點的地址。

int  DeleteList(Node * L, int data)//定義一個刪除函數，函數的參數分別為，鏈表的地址，以及刪除的元素值；
{Node * p1 = L;//定義一個指針，類型為結構體指針，準備用來表指向前驅結點；Node * p2 = L->next;//定義一個指針，類型為結構體指針，準備用來表指向刪除的結點；while (p2)//逐個判斷其數值是否與鏈表中的一直，直到每一個對比完。{if (p2->data == data)//判斷是不是要刪除的元素{						//如果是p1->next = p2->next;//將該節點的指針域的值放在前驅結點的指針域中；free(p2);//釋放該節點的空間L->data--;//鏈表的長度減1；return 1;//刪除成功，返回1；}					//如果不是p1 = p2;			//依次向后移到下一個結點；p2 = p2->next;}return 0;//沒有要刪除的元素，返回0；
}

2.3.4打印?

void PrintList(Node * L)//定義一個打印函數，函數的參數為，鏈表的地址
{Node * node = L->next;//定義一個指針，類型為結構體指針,用來進行數據的移動；while (node)//當該結點的指針域為空時，表示打印結束；{printf("%d ", node->data);//打印結點的數據node = node->next;//指向下一個結點；}printf("\n");
}

2.3.5案例?

? ? ? ? 創建一個新鏈表，利用前插插入5個數，利用后插插入5個數，打印出來鏈表，然后刪除其中一些結點，再打印出來；

#include <stdio.h>
#include <stdlib.h>//定義鏈表結構體節點typedef struct Node//定義一個結構體，并用typedef進行替換，即struct Node——Node；
{int data;			//數據域，本次采用整形；struct Node * next;//指針域，指針類型為結構體指針；
}Node;//初始化鏈表Node * InitList() //定義一個初始化函數，其返回值為結構體指針，即將構建的鏈表首地址返回；
{Node * head;//定義一個頭指針；head= (Node *)malloc(sizeof(Node));//創建一個節點，并讓頭指針指向該節點，該節點也就是頭結點；head->data = 0;//頭結點的數據域為0；head->next = NULL;//頭結點的指針域為空；return head;//返回頭結點的地址
}//鏈表頭插：
void HeadInsert(Node * L,int data)//定義一個前插函數，函數的參數分別為，鏈表的地址，以及新插入的元素值；
{Node * node = (Node *) malloc(sizeof(Node));//構建一個新的結點，然后返回其地址；node->data = data;//將傳入的數據存放在新節點的數據域；node->next = L->next;//將原來的頭結點的指針域的值，存放在新節點的指針域中；L->next = node;//將新節點的地址存放在頭指針的指針域；L->data++;//頭結點的數值域的數值加1，表示鏈表增加一個長度；
}//鏈表尾插;
void TailInsert(Node * L, int data)//定義一個后插函數，函數的參數分別為，鏈表的地址，以及新插入的元素值；
{Node * node=L;//定義一個指針，類型為結構體指針；int i ;for (i = 0; i < L->data; i++)//將指針指向尾結點；{node = node->next;}Node * n = (Node *) malloc(sizeof(Node));//創建一個新的結點，將創建的結點的地址先放在n中；node->next = n;//將新結點的地址存放在尾結點的指針域；n->data = data;//將新元素的數據存放在新結點的數據域；n->next = NULL;//新結點重新作為尾結點，其指針域為空；L->data++;//頭結點的數值域數值加1；表示鏈表的長度+1；
}//鏈表刪除int  DeleteList(Node * L, int data)//定義一個刪除函數，函數的參數分別為，鏈表的地址，以及刪除的元素值；
{Node * p1 = L;//定義一個指針，類型為結構體指針，準備用來表指向前驅結點；Node * p2 = L->next;//定義一個指針，類型為結構體指針，準備用來表指向刪除的結點；while (p2)//逐個判斷其數值是否與鏈表中的一直，直到每一個對比完。{if (p2->data == data)//判斷是不是要刪除的元素{						//如果是p1->next = p2->next;//將該節點的指針域的值放在前驅結點的指針域中；free(p2);//釋放該節點的空間L->data--;//鏈表的長度減1；return 1;//刪除成功，返回1；}					//如果不是p1 = p2;			//依次向后移到下一個結點；p2 = p2->next;}return 0;//沒有要刪除的元素，返回0；
}//鏈表打印void PrintList(Node * L)//定義一個打印函數，函數的參數為，鏈表的地址
{Node * node = L->next;//定義一個指針，類型為結構體指針,用來進行數據的移動；while (node)//當該結點的指針域為空時，表示打印結束；{printf("%d ", node->data);//打印結點的數據node = node->next;//指向下一個結點；}printf("\n");
}int main()
{Node * L= InitList();HeadInsert(L, 1);HeadInsert(L, 2);HeadInsert(L, 3);HeadInsert(L, 4);HeadInsert(L, 5);TailInsert(L, 6);TailInsert(L, 7);TailInsert(L, 8);TailInsert(L, 9);TailInsert(L, 10);PrintList(L);int ret =DeleteList(L, 1);if (ret == 1){printf("sucess delete\n");}else{printf("fail delete\n");}PrintList(L);return 0;
}

運行結果：?

3.3單循環鏈表

????????循環鏈表是另一種形式的鏈式存儲結構，其特點是表中的追后一個節點的指針域指向頭結點，整個鏈表形成一個環，由此，鏈表的任何一個節點出發均可以找到表中的其他節點。

單循環鏈表的操作和單鏈表基本一致，差別進在于：當鏈表遍歷時，判別當前指針P是指向表尾結點的終止條件不同。

單鏈表：判別條件為P!=NULL;或者P->next!=NULL;?

單循環鏈表：判別條件為P!=L;或者P->next!=L;

案例：

#include <stdio.h>
#include <stdlib.h>#define  True  1
#define  False 0typedef struct Node
{	int data;struct Node * next;
}Node;Node * Init_Link()
{Node* head = (Node *)malloc(sizeof(Node));head->data = 0;head->next = head;return head;
}void HeadInsert(Node * L, int data)
{Node * n = (Node *)malloc(sizeof(Node));n->data = data;n->next = L->next;L->next = n;L->data++;
}
void TailInsert(Node * L, int data)
{Node * n = (Node *)malloc(sizeof(Node));Node * b = L->next;while (b->next!= L){b = b->next;}b->next = n;n->data = data;n->next = L;L->data++;
}void PrintLink(Node * L)
{Node * L1 = L->next;while (L1 != L){printf("%d->", L1->data);L1 = L1->next;}printf("NULL\n");
}int DeleteLink(Node * L, int data)
{Node * n1 = L;Node * n2 = L->next;while (n2 != L){if (n2->data == data){n1->next = n2->next;free(n2);L->data--;return True;}n1 = n2;n2 = n2->next;}return False; 
}int main()
{Node* node = Init_Link();HeadInsert(node, 1);HeadInsert(node, 2);HeadInsert(node, 3);HeadInsert(node, 4);HeadInsert(node, 5);TailInsert(node, 6);TailInsert(node, 7);TailInsert(node, 8);TailInsert(node, 9);TailInsert(node, 10);PrintLink(node);DeleteLink(node, 5);DeleteLink(node, 6);PrintLink(node);return 0;
}

運行結果：?

四、雙向鏈表?

4.1雙向鏈表

? ? ? ? 以上討論的鏈式存儲結構的節點只有一個指示直接后繼的指針域，也就是說從某個節點出發只能順指針向后進行查找。若要尋查結點的直接前驅，則必須要從表頭指針出發。

? ? ? ? 為了克服單鏈表這種單向性的缺點，可以利用雙向鏈表。

? ? ? ? 顧名思義，雙向鏈表的節點由兩個指針域，一個指向直接后繼，一個指向直接前驅。結點的結構如下圖所示：

#include <stdio.h>
#include <stdlib.h>#define True 1
#define False 2typedef struct Node
{int data;struct Node * pre;struct Node * next;
}Node;Node * InitLink()
{Node * head = (Node*)malloc(sizeof(Node));head->data = 0 ;head->next = NULL;head->pre = NULL; 
}void HeadInsert(Node * L, int data)
{Node * n = (Node *)malloc(sizeof(Node));n->data = data;if (L->next == NULL){n->pre = L;n->next = L->next;L->next = n;}else{n->next = L->next;n->pre = L;L->next->pre = n;L->next = n;}L->data++;
}void TailInsert(Node * L,int data)
{Node * n = (Node *)malloc(sizeof(Node));n->data = data;Node * n1=L;while (n1->next ){n1 = n1->next;}n->pre = n1;n->next = n1->next;n1->next = n;L->data++;
}
int DeleteLink(Node * L, int data)
{Node * n = L;while (n){if (n->data == data){n->pre->next = n->next;if (n->next){n->next->pre = n->pre;}free(n);L->data--;return True;}n = n->next;}return False;}void PrintLint(Node * L)
{Node * n = L->next;while (n){printf("%d->", n->data);n = n->next;}printf("NULL\n");}int main(){Node *L = InitLink();HeadInsert(L, 1);HeadInsert(L, 2);HeadInsert(L, 3);HeadInsert(L, 4);HeadInsert(L, 5);TailInsert(L, 6);TailInsert(L, 7);TailInsert(L, 8);TailInsert(L, 9);TailInsert(L, 10);PrintLint(L);DeleteLink(L, 5);DeleteLink(L, 6);DeleteLink(L, 10);PrintLint(L);return 0;}

運行結果：?

?4.2雙循環鏈表

???循環鏈表是另一種形式的鏈式存儲結構，其特點是表中的追后一個節點的指針域指向頭結點，整個鏈表形成一個環，由此，鏈表的任何一個節點出發均可以找到表中的其他節點。

? ? ? ? 雙向循環鏈表的是結合雙鏈表和循環鏈表的特點，其基本的算法與前文相似，需要注意的是插入和刪除時有很大的不用，在雙鏈表種需要需改多個指針。

#include <stdio.h>
#include <stdlib.h>#define True 1
#define False 0typedef struct Node
{int data;struct Node * pre;struct Node * next;
}Node;Node * InitLink()
{Node * head = (Node*)malloc(sizeof(Node));head->data = 0;head->next =head;head->pre = head;return head;
}void HeadInter(Node* L, int data)
{Node* node = (Node*)malloc(sizeof(Node));node->data = data;node->next = L->next;node->pre = L;L->next->pre = node;L->next = node;L->data++;
}
void TailInter(Node * L, int data)
{Node * node = L;while (node->next != L){	node = node->next;}Node * n = (Node *)malloc(sizeof(Node));n->data = data;n->pre = node;n->next = L;L->pre = n;node->next = n;L->data++;
}
int DeleteLink(Node* L, int data)
{Node * node = L->next;while (node!= L){if (node->data == data){node->pre->next = node->next;node->next->pre = node->pre;free(node);L->data--;return True;}node = node->next;}return False;	
}void PrintLink(Node *L)
{Node* node = L->next;while (node!=L){printf("%d->", node->data);node = node->next;}printf("NULL\n");
}int main()
{Node * L = InitLink();HeadInter(L, 1);HeadInter(L, 2);HeadInter(L, 3);HeadInter(L, 4);HeadInter(L, 5);TailInter(L, 6);TailInter(L, 7);TailInter(L, 8);TailInter(L, 9);TailInter(L, 10);PrintLink(L);DeleteLink(L,7);DeleteLink(L,6);DeleteLink(L,5);DeleteLink(L,1);PrintLink(L);return 0;
}

運行結果：

需要注意的時，在指針進行交換的時候，一定需要注意順序；例如：

?在頭插法中:

void HeadInter(Node* L, int data)
{
?? ?Node* node = (Node*)malloc(sizeof(Node));
?? ?node->data = data;
?? ?node->next = L->next;
?? ?node->pre = L;
?? ?L->next->pre = node;
?? ?L->next = node;
?? ?L->data++;
}

????????如果上述兩個代碼的順序發生錯誤，就會在刪除頭插數據時出現錯誤，因為其連接發生錯誤。

????????當增加指針時，一定注意，先修改新插的節點，再修改后繼節點，最后再修改前驅節點。不然就會發生錯誤。

總結：

? ? ? ? 本節介紹了線性表的順序存儲——順序表，以及鏈式存儲——鏈表，我們發現，存取元素順序表更方便，插入和刪除元素，鏈表更方便。線性變也是數據結構的基礎，能夠很好的將C語言同數據結構后面的內容聯系起來。大家可以多多練習；

創作不易，感謝大家多多點贊支持！

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/44457.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/44457.shtml
英文地址，請注明出處：http://en.pswp.cn/web/44457.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

OpenGL筆記一之基礎窗體搭建以及事件響應

OpenGL筆記一之基礎窗體搭建以及事件響應

OpenGL筆記一之基礎窗體搭建以及事件響應 總結自bilibili趙新政老師的教程 code review! 文章目錄 OpenGL筆記一之基礎窗體搭建以及事件響應1.運行2.目錄結構3.main.cpp4.CMakeList.txt 1.運行 2.目錄結構 01_GLFW_WINDOW/ ├── CMakeLists.txt ├── glad.c ├── main…
閱讀更多...
Linux基于centos7指令初學3

Linux基于centos7指令初學3

date指令 作用&#xff1a; date指令可以查看時間 這個指令可以進行格式化 格式&#xff1a;date %想要的內容 Y&#xff1a;年份 m&#xff1a;月份 d&#xff1a;日 H&#xff1a;時 M&#xff1a;分 S&#xff1a;秒 時間分界線可以由…
閱讀更多...
GIT相關操作，推送本地分支到遠程倉庫流程記錄學習

GIT相關操作，推送本地分支到遠程倉庫流程記錄學習

git流程 切換到源文件夾&#xff1a;cd 源文件夾克隆遠程倉庫&#xff1a;git clone [ssh]進入項目文件夾&#xff1a;cd .\project\查看本地分支&#xff1a;git branch獲取遠程倉庫更新&#xff0c;使遠程同步&#xff1a;git fetch查看所有分支&#xff08;包括遠程分支&am…
閱讀更多...
OJ-0712

OJ-0712

示例1&#xff1a; input 8 123 124 125 121 119 122 126 123 output 1 2 6 5 5 6 0 0示例2&#xff1a; input 2 95 100 output 1 0示例3&#xff1a; input 2 100 95 output 0 1package com.wsdcode.od;import java.util.Scanner;public class Main {public static void m…
閱讀更多...
LabVIEW比例壓力控制閥自動測試系統

LabVIEW比例壓力控制閥自動測試系統

開發了一套基于LabVIEW編程和PLC控制的比例控制閥自動測試系統。該系統能夠實現共軌管穩定的超高壓供給&#xff0c;自動完成比例壓力控制閥的耐久測試、流量滯環測試及壓力-流量測試。該系統操作簡便&#xff0c;具有高精度和高可靠性&#xff0c;完全滿足企業對自動化測試的需…
閱讀更多...
安裝jenkins最新版本初始化配置及使用JDK1.8構建項目詳細講解

安裝jenkins最新版本初始化配置及使用JDK1.8構建項目詳細講解

導讀 1.安裝1.1.相關網址1.2.準備環境1.3.下載安裝 2. 配置jenkins2.1.安裝插件2.2.配置全局工具2.3.系統配置 3. 使用3.1.配置job3.2.構建 提示&#xff1a;如果只想看如何使用jdk1.8構建項目&#xff0c;直接看3.1即可。 1.安裝 1.1.相關網址 Jenkins官網&#xff1a;https…
閱讀更多...
RabbitMq如何保證消息的可靠性和穩定性

RabbitMq如何保證消息的可靠性和穩定性

RabbitMq如何保證消息的可靠性和穩定性 rabbitMq不會百分之百讓我們的消息安全被消費&#xff0c;但是rabbitMq提供了一些機制來保證我們的消息可以被安全的消費。 消息確認 消息者在成功處理消息后可以發送確認&#xff08;ACK&#xff09;給rabbitMq&#xff0c;通知消息已…
閱讀更多...
Hadoop-25 Sqoop遷移 增量數據導入 CDC 變化數據捕獲 差量同步數據 觸發器 快照 日志

Hadoop-25 Sqoop遷移 增量數據導入 CDC 變化數據捕獲 差量同步數據 觸發器 快照 日志

章節內容 上節我們完成了如下的內容&#xff1a; Sqoop MySQL遷移到HiveSqoop Hive遷移數據到MySQL編寫腳本進行數據導入導出測試 背景介紹 這里是三臺公網云服務器&#xff0c;每臺 2C4G&#xff0c;搭建一個Hadoop的學習環境&#xff0c;供我學習。 之前已經在 VM 虛擬機…
閱讀更多...
計算機的錯誤計算（二十九）

計算機的錯誤計算（二十九）

摘要 &#xff08;1&#xff09;討論近似值的錯誤數字個數。有時&#xff0c;遇到數字9或0, 不太好確認近似值的錯誤數字個數。&#xff08;2&#xff09;并進一步解釋確認計算機的錯誤計算&#xff08;二十八&#xff09;中一個函數值的錯誤數字個數。 理論上&#xff0c;我…
閱讀更多...
py2neo常用語句

py2neo常用語句

1.連接數據庫 Neo4j服務器默認的端口號就是7474,所以本地的主機就是"http://localhost:7474" 。 默認的用戶名密碼都是neo4j&#xff0c; # 連接數據庫&#xff0c;輸入個人配置 graph Graph("http://localhost:7474//browser/", auth("neo4j"…
閱讀更多...
百日筑基第十九天-一頭扎進消息隊列2

百日筑基第十九天-一頭扎進消息隊列2

百日筑基第十九天-一頭扎進消息隊列2 消息隊列的通訊協議 目前業界的通信協議可以分為公有協議和私有協議兩種。公有協議指公開的受到認可的具有規 范的協議&#xff0c;比如 JMS、HTTP、STOMP 等。私有協議是指根據自身的功能和需求設計的協 議&#xff0c;一般不具備通用性&…
閱讀更多...
數學建模·熵權法

數學建模·熵權法

熵權法 一種計算評價指標之間權重的方法。熵權法是一種客觀的方法&#xff0c;沒有主觀性&#xff0c;比較可靠。 具體定義 熵權法的核心在于計算信息熵&#xff0c;信息熵反映了一個信息的紊亂程度&#xff0c;體現了信息的可靠性 具體步驟 Step1正向化處理 將所以評價指標轉…
閱讀更多...
智能家居裝修怎么布線?智能家居網絡與開關插座布置

智能家居裝修怎么布線?智能家居網絡與開關插座布置

打造全屋智能家居。計劃的智能家居方案以米家系列為主&#xff0c;智能家居聯網方案以無線為主。裝修前為了裝備智能家居做了很多準備工作&#xff0c;本文深圳僑杰智能分享一個智能家居裝修和布線方面的心得與實戰知識。希望能對大家的裝修有所幫助。 ?1.關于網絡 如果房子比…
閱讀更多...
HTML基本標簽（二）

HTML基本標簽（二）

HTML基本標簽&#xff08;二&#xff09; 表格標簽 table媒體元素audio 音頻vido 視頻 form 表單元素 表格標簽 table <!-- caption 代表表格標題相關屬性border 邊框cellpadding 設置單元格內填充cellspacing 設置單元格間空隙width 設置表格寬度&#xff0c;默認是內容撐…
閱讀更多...
Python-數據爬取（爬蟲）

Python-數據爬取（爬蟲）

~~~理性爬取~~~ 杜絕從入門到入獄 1.簡要描述一下Python爬蟲的工作原理&#xff0c;并介紹幾個常用的Python爬蟲庫。 Python爬蟲的工作原理 發送請求&#xff1a;爬蟲向目標網站發送HTTP請求&#xff0c;通常使用GET請求來獲取網頁內容。解析響應&#xff1a;接收并解析HTTP響…
閱讀更多...
結合實體類型信息1——基于本體的知識圖譜補全深度學習方法

結合實體類型信息1——基于本體的知識圖譜補全深度學習方法

1 引言 1.1 問題 目前KGC和KGE提案的兩個主要缺點是:(1)它們沒有利用本體信息;(二)對訓練時未見的事實和新鮮事物不能預測的。 1.2 解決方案 一種新的知識圖嵌入初始化方法。 1.3 結合的信息 知識庫中的實體向量表示&#xff0b;編碼后的本體信息——>增強 KGC 2基…
閱讀更多...
基于AT89C51單片機超聲波水位液位控制系統設計（含文檔、源碼與proteus仿真，以及系統詳細介紹）

基于AT89C51單片機超聲波水位液位控制系統設計（含文檔、源碼與proteus仿真，以及系統詳細介紹）

本篇文章論述的是基于AT89C51單片機的1616點陣LED顯示器字符滾動顯示設計的詳情介紹&#xff0c;如果對您有幫助的話&#xff0c;還請關注一下哦&#xff0c;如果有資源方面的需要可以聯系我。 目錄 設計任務與要求 原理圖 仿真圖 代碼 系統論文 資源下載 設計任務與要求…
閱讀更多...
處理線程安全的列表CopyOnWriteArrayList 和Collections.synchronizedList

處理線程安全的列表CopyOnWriteArrayList 和Collections.synchronizedList

ConcurrentModificationException 是 Java 中的一種異常&#xff0c;用于指示在迭代集合時&#xff0c;該集合的結構發生了并發修改。 在 Java 中&#xff0c;許多集合類&#xff08;如 ArrayList, HashMap 等&#xff09;都不是線程安全的。如果一個線程在迭代集合的同時&…
閱讀更多...
IDEA的JAVA版本沒有8怎么辦

IDEA的JAVA版本沒有8怎么辦

問題&#xff1a; 很多小伙伴會出現如下的情況&#xff0c;java的版本很高&#xff0c;沒有8 解決 更換IDEA內置的Server URL的鏡像地址 就是這個 把其中的地址換成 https://start.aliyun.com/ https://start.aliyun.com/ 我們可以看到JAVA 8就出現了
閱讀更多...
Vue Router 4：構建高效單頁面應用的路由管理

Vue Router 4：構建高效單頁面應用的路由管理

引言 Vue Router的重要性在于它極大地簡化了單頁面應用(SPA)的開發流程。通過Vue Router&#xff0c;開發者可以輕松地將URL映射到對應的組件&#xff0c;實現頁面的無刷新跳轉&#xff0c;從而提升用戶體驗。 安裝和設置Vue Router 4 如何在Vue 3項目中安裝Vue Router 4 1…
閱讀更多...
最新文章

Copyright @ 2022~2023