原文連結
1 數組
1.1 數組含義
數組：相同元素構成有序的元素集合。數組中存儲的元素類型是一緻的，數組也是學習程式設計時最先接觸的資料集合。
1.2 存儲方式
數組在記憶體中采用連續的存儲方式，也就是說資料在記憶體中存放是連續的。例如：
當程式執行如下代碼：
int array[10] //在棧上配置設定一個有10個int元素的數組
printf("array的位址:%pn", &array);
for(int i = 0; i < 10; i++){
printf("buf[%d]的位址:%pn", i, &array[i]);
} 輸出結果：
array的位址 :00000000006ffe20
array[0]的位址:00000000006ffe20
array[1]的位址:00000000006ffe24
array[2]的位址:00000000006ffe28
array[3]的位址:00000000006ffe2c
array[4]的位址:00000000006ffe30
array[5]的位址:00000000006ffe34
array[6]的位址:00000000006ffe38
array[7]的位址:00000000006ffe3c
array[8]的位址:00000000006ffe40
array[9]的位址:00000000006ffe44 int 類型資料占據 4 個位元組空間，是以位址內插補點為 4 。通過輸出結果可以看出，數組的存儲空間是連續的，并且array 與 array[0] 的位址是相同的。
1.3 存儲缺點
由于數組采用連續的存儲方式，在開辟數組空間時需要保證記憶體有足夠的連續記憶體才能保證記憶體配置設定。例如：當記憶體結構如圖所示：
當程式需要記憶體為 1000 個資料大小的記憶體空間，但是由于記憶體中最大的連續空間為 600 ，則會導緻程式配置設定記憶體失敗。但是我們發現記憶體的使用空間為 1500 ，剩餘空間仍有 1400 個資料空間，但由于這 1400 個資料空間不連續，導緻建立數組失敗。
2 指針
2.1 含義
指針：是一個特殊的變量，它裡面存儲的值為記憶體裡的一個位址。指針的值是指針本身存儲的數值，這個值将被編譯器當作一個位址，而不是一個一般的數值。例如：在 32 位程式裡，所有類型的指針的值都是一個 32 位整數，因為 32 位程式裡記憶體位址全都是 32 位長。
int a = 0;
//定義一個整型變量
int *p = &a;
//建立指針變量，并将指針指向變量a
printf("a的值 = %dn", a );
//輸出變量值
printf("a的位址 = %pn" , &a);
//輸出變量位址
printf("p的内容 = %pn", p);
//輸出指針變量的内容
printf("通過指針通路資料a = %dn", *p); a的值 = 0
a的位址 = 00000000006ffe3c
p的内容 = 00000000006ffe3c
通過指針通路資料a = 0 通過輸出可以看出，指針 p 中存儲的是是變量 a 的位址。
2.2 指針大小
指針占據的記憶體大小隻要用函數 sizeof(指針的類型) 即可計算出。例如：在 32 位平台裡，指針本身占據了 4 個位元組的長度，在 64 位平台，指針占據 8 個位元組大小。
測試程式：
int a = 1;
double b = 1.4f;
int *p = &a;
double *q = &b;
printf("int類型指針大小 = %dn", sizeof(p));
printf("double類型指針大小 = %dn", sizeof(q)); int類型指針大小 = 8double類型指針大小 = 8 2.3 指針意義
在 1.3 節中介紹了數組存儲方式引發的記憶體配置設定問題。那麼，如何利用指針解決這一問題呢？
首先，指針中存儲的是一塊記憶體的位址，并且通過該位址可以擷取變量的内容。那麼同樣的配置設定大小為N的數組，我們可以通過指針将 N 個元素分别存儲到可用記憶體空間中，在通路資料時可以通過指針去擷取後繼元素的内容。
存儲圖示：
通過指針可以将大小為N的資料分别存儲至 M1、M2 和 M3 大小空間内。這種方式可以避免連續記憶體不足引發的記憶體配置設定失敗問題。
3 資料節點
3.1 含義
資料節點是研究資料結構與算法中最為常用的術語，通常節點指的事最小的資料單元。
3.2 單連結清單節點
在 2.3 節中，構造的既能存儲資料又能存儲位址的資料單元稱為單連結清單節點，單連結清單節點分為兩部分：
- 資料域：存儲資料
- 指針域：存儲後續節點的記憶體位址，即指向下一個節點。
定義資料結構：
struct Node{
int value;//資料域，以int為例
Node * next;//指針域，指向下一個節點
}; 節點圖示：
各個節點資料通過指針的方法串聯起來，構成連結清單。由于Node中隻有單向的指針next，是以構成的連結清單為單連結清單。
單連結清單圖示：
3.3 頭結點
頭結點不存儲實際的資料元素，用于輔助資料元素的定位，友善插入和删除操作，通常頭結點标記為head。
帶有頭節點單連結清單：
4 單連結清單
4.1 單連結清單建立
建立過程：
建立程式：
//建立連結清單int create_List(Node **p) {
int data = 0;
int ret = 0;
Node *pHead = NULL; //頭結點指針
Node *node = NULL;
Node *tmp = NULL;
pHead = (Node *)malloc(sizeof(Node));//建立一個頭結點
if(pHead == NULL) {
ret = -1;
}
tmp = pHead;
printf("請輸入一個整數資料n");//等待使用者輸入整數資料，輸入-1結束
scanf("%d", &data);
while(data != -1) {
node = (Node *)malloc(sizeof(Node));//建立新節點
if(node == NULL) {
ret = -1;
printf("List_Create erron");
}
node->data = data;//為新節點指派
tmp->next = node;//将目前節點添加至目前連結清單末尾
tmp = node;//将目前指向的節點指針指向新節點
printf("請輸入一個整數資料n");
scanf("%d", &data);
}
node->next = NULL;
*p = pHead;
return ret;
} 4.2 單連結清單周遊
單連結清單的周遊十分簡單，隻需從連結清單頭開始，沿着指針指向順序依次輸出元素即可。
周遊過程：
周遊程式：
void traverse_List(Node* pHead) {
Node* pCur;//建立用于周遊連結清單的指針
if(pHead == NULL || pHead->next == NULL) {
printf("LinkList is NULLn");//表為空
}
pCur = pHead;//将pCurrent指向頭節點
while(pCur->next) { //目前節點不為最後的節點
printf("%d ", pCur->next->data);//輸出資料值
pCur = pCur->next;//将目前節點指針後移，指向下一個節點
}
} 4.3 單連結清單查找
單連結清單的資料查找需要周遊整個連結清單，在周遊過程中，将節點資料與查找資料比較。
查找程式：
//查找資料為value的節點
Node* find_List(Node *pHead, int value){
Node *pTmp; //周遊連結清單指針
if(pHead == NULL || pHead->next == NULL) {
printf("Node is NULLn");
return NULL;
}
pTmp = pHead;
while(pTmp->next) {//周遊連結清單
printf("%d ", pTmp->next->data);
if(pTmp->next->data == value){//判斷值是否相等
pTmp = pTmp->next;//查找到目标節點
return pTmp; //傳回目标節點
}
pTmp = pTmp->next;//繼續向下查找
}
return NULL;//查找失敗
} 4.4 單連結清單插入
插入過程：
插入代碼：
//p節點後插入值為i的節點void insert_Node(Node *p, int i){
Node* node = new Node;
node->value = i;
node->next = p->next;
p->next = node;
} 4.5 單連結清單删除
删除過程：
删除代碼：
void delete_List(Node * pHead, int data){
if(pHead == NULL || pHead->next == NULL) {
printf("Node is NULLn");
return NULL;
}
while(1){
int flag=-1;
Node* pCur;//指向目前節點的指針
Node* pPre;//指向目前節點的上一個節點指針
pCur = pHead->next;
pPre= pHead;
while(pCur){
if(pCur->data==data){//元素比較
//将目前節點的前驅節點的next指向目前節點的後繼節點
pPre->next = pCur->next;
flag = 1;
break;
}
//繼續向後查找
pCur = pCur->next;
pPre = pPre->next;
}
if(flag==1){
free(pCur);//釋放目前節點占據空間
printf("節點删除成功n");
}else{
printf("此連結清單找不到這個值n");
break;
}
}
} 4.6 單連結清單逆序
單連結清單逆序是筆試題中出現頻率較高的考點。逆序即将目前連結清單順序進行反轉。
逆序：
逆序過程：
逆序代碼：
//單連結清單逆序
void reverseLinkList(Node* pHead) {
Node* pPre = NULL;//指向目前節點的上一個節點
Node* pCur = NULL;//指向目前節點的指針
Node* pTmp = NULL;
if(pHead == NULL || pHead->next == NULL || pHead->next->next == NULL) {
return;
}
pPre = pHead->next;
pCur = pHead->next->next;
while(pCur) {//周遊整個連結清單
//交換順序，實作逆序
pTmp = pCur->next;
pCur->next = pPre;
pPre = pCur;
pCur = pTmp;
}
pHead->next->next = NULL;
pHead->next = pPre;
} 5 總結
單連結清單優缺點：
優點：
1：插入、删除操作不需移動其他元素, 隻需改變指針。
2：連結清單各個節點在記憶體中空間不要求連續，空間使用率高。
缺點：
1：通路數組元素效率低
來源 | 五分鐘學算法
作者 | 程式員小吳