在前幾章對C語言的學習中，我們學到了：
- 基本的C語法和簡單算法
- 面向過程的編程思想
而在數據結構這一篇章，我們將要學習：
- 常用的數據存儲結構
- 算法
- 面向對象的編程思想
數據結構
在正式開始學習之前，我們先來了解一下什么是數據結構：
什么是數據結構？
所謂數據結構，就是用來組織和存儲數據的，而存儲 ， 即存儲變量、數組（在數據結構里稱為順序表）等；程序 = 數據結構 + 算法，了解數據的存放佐以數據的算法，就構成了程序。
數據與數據之間的關系
1）邏輯結構 ：數據元素與元素之間的關系
- ?集合：元素與元素之間平等獨立的集合關系
- 線性結構：數據元素與元素之間存在一對一的關系(順序表、鏈表、隊列、棧)
- 樹形結構：數據元素與元素之間存在一對多的關系（二叉樹）
- 圖形結構：數據元素與元素之間存在多對多的關系 (網狀結構)
2）物理結構 ：數據元素在計算機內存中的存儲方式
順序結構：
在內存中選用一段連續的內存空間（線性結構）進行存儲
- ?數據訪問方便（O（1））
- 插入和刪除數據時需要移動大量數據
- 需要預內存分配
- 可能造成大量的內存碎片??
內存碎片：
- 內內存碎片：如結構體struct里空出的空間；
- 外內存碎片：申請大連續空間（malloc）剩余的空間；
順序結構的存儲如圖所示：
像數組一樣，依次進入存儲空間，如果要插入數據或刪除數據都要把該數據前后的數據修改一下。
鏈式結構：
可以在內存中選用一段非連續的內存空間進行存儲
- 數據訪問時必須要從頭遍歷（O（n））
- 插入和刪除元素方便
- 不需要預內存分配，是一種動態存儲的方式
- 可以充分使用內存空間
鏈式結構的存儲方式如圖所示：
鏈式結構存儲是通過元素后的指針指向下一元素進行鏈接的，當最后一個元素后的指針是一個空指針時就表示停止。
順序結構和鏈式結構的時間復雜度如圖所示：
索引結構：
將要存儲的數據的關鍵字和存儲位置之間構建一個索引表，也就是給下面的哈希函數建立一個表。
散列結構（哈希結構）：
將數據的存儲位置與數據元素之間的關鍵字建立起對應的關系（哈數函數），根據該關系進行數據存儲和快速查找
哈希結構存儲方式如下圖：
中間關鍵字key 和addr的表就是索引結構
基本功能
數據結構的基本功能就是：
- 快捷使用指針
- 結構體（封裝）
- 實現動態內存分配
數據結構的內容
數據結構包含一下內容（帶*的為重點）
? ? ?1. 鏈式表
單向鏈表*
雙向鏈表*
循環鏈表
內核鏈表
2. 棧*
3. 隊列*
4. 二叉樹
5. 哈希表
6.常用算法*
單向鏈表
單向鏈表的組成
鏈表：對象（存儲數據的對象）、屬性（變量）、行為（函數）
單向鏈表是由鏈表對象與各個結點組成的：
結點：
單向鏈表的結點是由上方的數據域data和下方的指針域pnext（指向下一個結點）組成的。
鏈表對象
鏈表對象是由phead（保存頭結點地址，指向下一節點），clen（節點個數），以及其他屬性組成的。
單向鏈表代碼
1. 創建鏈表對象
首先我們要先在聲明? link . h? 里封裝結構體：
#ifndef __LINK_H__
#define __LINK_H__/*鏈表存儲的數據的數據類型*/
typedef int Data_type_t;/*鏈表的結點類型*/
typedef struct node
{Data_type_t data;struct node *pnext;
}Node_t;/*鏈表對象類型*/
typedef struct link
{Node_t *phead;int clen;
}Link_t;
#endif然后我們在函數文件里創建函數：
#include "link.h"
#include <stdlib.h>
#include <stdio.h>/*創建單向鏈表*/
Link_t *create_link()
{Link_t *plink = malloc(sizeof(Link_t));if (NULL == plink){printf("malloc error!\n");return NULL;}plink->phead = NULL;plink->clen = 0;return plink;
}
在堆區開辟空間創建鏈表對象，如果沒有申請到空間，即打印出錯；如果申請成功，將鏈表對象指向結點的指針初始化為空指針，節點個數設置為0；
在主函數調用函數：
#include <stdio.h>
#include "link.h"int main(int argc, const char *argv[])
{Link_t *plink = create_link();if (NULL == plink){return -1;}return 0;
}2. 插入數據（頭插、尾插）
頭插
頭插即是從鏈表對象后開始插入數據：
/*向單向鏈表的頭部插入數據*/
int insert_link_head(Link_t *plink, Data_type_t data)
{//申請結點Node_t *pnode = malloc(sizeof(Node_t));if (NULL == pnode){printf("malloc error!");return -1;}//初始化結點pnode->data = data;pnode->pnext = NULL;//頭插2步插入結點pnode->pnext = plink->phead;plink->phead = pnode;plink->clen++;return 0;
}首先，申請空間存放節點，后對結點進行初始化；我們要先讓待插入的結點指向當前鏈表對象指向的結點；后再讓鏈表對象指向當前待插入的結點。不然如果先讓鏈表對象指向待插入的結點，后一位結點的位置將會丟失，不能再進行鏈接：
尾插
尾插即是從鏈表末尾開始插入數據：
int insert_link_back(Link_t *plink , Data_type_t data)
{Node_t *pnode = malloc(sizeof(Node_t));if(NULL == pnode){printf("malloc error!");return -1;}pnode -> data = data;pnode -> pnext =NULL;if(plink -> phead == NULL){plink -> phead = pnode;pnode -> pnext = NULL;plink -> clen++;return 0;}else{Node_t *ptmp = plink -> phead;while(ptmp -> pnext != NULL){ptmp = ptmp-> pnext;}ptmp -> pnext = pnode;plink ->clen++;return 0;}
尾插的一些邏輯算法和頭插一致，但不同的是，先判斷是否是一個空鏈表：如果是一個空鏈表，那就直接改變鏈表對象的指向與結點的指向即可；如果不是一個空指針，要先遍歷一遍結點，找到末尾的結點，修改它的指針域指向待插入結點。
3. 刪除數據（頭刪、尾刪）
頭刪
頭刪即是從鏈表對象指向的結點開始銷毀空間：
int delete_link(Link_t *plink)
{Node_t*ptmp = plink -> phead;plink -> phead = ptmp -> pnext;if(plink -> phead == NULL){return 0;}else{free(ptmp);plink -> clen--;ptmp = NULL;return 1;}
}先設定一個指針來指向第一個結點，此時設定鏈表對象指向下一個結點；如果此時是一個空鏈表，即不再運行、如果非空鏈表，就解放當前指針ptmp指向的第一個結點的空間，同時讓節點個數-1，別忘了此時ptmp是野指針，將ptmp設為空指針。
尾刪
尾刪即是從鏈表的最后一個結點開始刪除：
int delete_linkback(Link_t *plink)
{if (plink -> phead == NULL){free(plink);return -1;}Node_t*ptmp = plink -> phead;if (ptmp -> pnext == NULL){delete_link(plink);return 0;}else{while(ptmp -> pnext -> pnext != NULL){ptmp = ptmp -> pnext;}free(ptmp -> pnext);plink -> clen--;ptmp -> pnext = NULL;return 1;}
}這種刪除數據的方法要找到尾部結點的前一個結點，故使用ptmp尋找它指向結點的下一結點的指向是否指向空指針；如果不是，則繼續遍歷、如果是，則解放當前指針指向結點的下一結點；同時要記得判斷空鏈表與鏈表只有一個節點的情況；
4. 查找數據
查找數據時要遍歷所有結點的數據域，然后輸出找到的地址：
Node_t *find_tdata(Link_t *plink , Data_type_t n)
{Node_t *ptmp = plink->phead;while(ptmp != NULL){if(n == ptmp -> data){return ptmp;}ptmp = ptmp -> pnext;}return ptmp;}這個只需要先讓指針指向第一個結點，后一一遍歷比較即可。
5. 修改數據
修改數據可以直接調用查找數據的函數，然后直接改變其結點的數據域即可：
Node_t *find_tdata(Link_t *plink , Data_type_t n)
{Node_t *ptmp = plink->phead;while(ptmp != NULL){if(n == ptmp -> data){return ptmp;}ptmp = ptmp -> pnext;}return ptmp;}
int change_linkdata(Link_t *plink , Data_type_t oldata , Data_type_t newdata)
{Node_t*ptmp = find_tdata(plink , oldata);if(ptmp == NULL){return 0;}else{ptmp -> data = newdata;return 1;}
}6. 銷毀鏈表
銷毀鏈表不能直接使用free函數調用指向鏈表的指針plink，這樣會導致剩余的結點的位置全部丟失，導致剩下很多結點的存儲空間未被銷毀。所以要先使用刪除數據，銷毀所有結點空間，后再進行銷毀鏈表對象空間：
Link_t *destroy_link(Link_t *plink)
{int n;if(plink -> phead == NULL){free(plink);plink = NULL;return plink;}else{while(plink -> phead != NULL){n = delete_link(plink);if(n == 0){plink = NULL;return plink;}}}
}調用刪除數據函數進行循環，直到鏈表變為空鏈表為止，后進行銷毀；
以上就是和大家分享的內容！！！！單向鏈表的理解需要指針扎實的基礎和結構體的應用，感謝你的閱讀！！！！如有遺漏和錯誤，歡迎評論區進行批評和指正！！
 A-C)
