數據結構
????????在數據結構部分，研究數據在內存中如何存儲。
????????數據存儲的形式有兩種：變量和數組（數據結構的順序表）。
一、什么是數據結構？
????????數據類型被用來組織和存儲數據。
? ? ? ? 程序設計 = 數據結構 + 算法
二、數據與數據之間的關系
1、邏輯結構
????????數據元素與元素之間的關系。
?????1）集合：元素與元素之間平等的集合關系。
?????2）線性結構：元素與元素之間存在一對一的關系(eg. 順序表、鏈表、隊列、棧)。
?????3）樹形結構：元素與元素之間存在一對多的關系(eg. 二叉樹)。
?????4）圖形結構（網狀結構）：元素與元素之間存在多對多的關系。
? ? ? ? 內存為線形存儲結構。
2、物理結構
????????數據元素在計算機內存中的存儲方式。
????????1）順序結構：在內存中選用一段連續的內存空間進行存儲。
? ? ? ? ? ? ? ? 特點：(1) 數據訪問方便 (算法復雜度O(1) )。
? ? ? ? ? ? ? ? ? ? ? ? ? ?(2) 插入和刪除數據時需要移動大量數據。
? ? ? ? ? ? ? ? ? ? ? ? ? ?(3) 需要域內存分配 (連續的) 。
? ? ? ? ? ? ? ? ? ? ? ? ? ?(4) 可能造成大量內存碎片 (分為內內存碎片和外內存碎片兩種 )。
| 內存碎片分類 | 內存碎片特點 |
| 內內存碎片 | 操作系統已分配給程序的內存中部分小內存空間不能再被使用，例如結構體數據類型存儲時的中間空閑塊 |
| 外內存碎片 | 內存中存在大量不連續的空閑塊，因分散在內存的不同位置而不能合并成一塊連續的大空間，導致程序無法被加載到內存中 |
????????2）鏈式結構：可以在內存中選用一段不連續的內存空間進行存儲。
? ? ? ? ? ? ? ? 給內存元素后加上指針，指針指向元素訪問下一個元素。
? ? ? ? ? ? ? ? 特點：(1) 數據訪問必須從頭遍歷 (算法復雜度O(n) )；
? ? ? ? ? ? ? ? ? ? ? ? ? ?(2) 插入和刪除元素方便；
? ? ? ? ? ? ? ? ? ? ? ? ? ?(3) 不需要與內存分配 (離散的)，是一種動態內存操作 (只要有部分內存空間能放下部分數據，直至存放完全部數據就行)。
????????3）索引結構：將要存儲的數據的關鍵字和存儲位置之間構建一個索引表。
????????4）散列結構（哈希結構）：將數據的存儲位置與數據元素之間的關鍵字建立起對應的關系( 哈希函數?)。
? ? ? ? 索引結構與散列結構都用于快速定位數據。
三、基本功能
????????指針、結構體、動態內存分配。
四、數據結構內容
? ? ? ?數據結構內容包含：順序表、鏈式表（單向鏈表、雙向鏈表、循環鏈表、內核鏈表）、棧、隊列、二叉樹、哈希表、常用算法。
五、單向鏈表
1、概念
????????單向鏈表是一種常見的線形數據結構，由多個節點組成，每個節點包含兩部分：
? ? ? ? 1) 數據域：存儲結點本身的信息（如數值、字符等）。
? ? ? ? 2) 指針域：存儲下一個結點的地址，用于指向鏈表中的下一個結點。
示意圖如下：
????????特點：整個鏈表的訪問需從第一個結點開始，依次通過指針域找到下一個節點，最后一個結點的指針域為空指針(NULL)，單向鏈表無法訪問前一個結點。
2、鏈表的對象
? ? ? ? 鏈表的對象是存儲數據的對象。
? ? ? ? 鏈表對象的屬性特征(變量)：第一個結點、結點的個數。
? ? ? ? 鏈表對象的行為(函數)：創建鏈表對象、插入數據、刪除數據、修改數據、查找數據、銷毀鏈表。
3、單項鏈表的應用
?????1）單向鏈表的封裝
????????(1) 封裝結點（存放在聲明文件中）
/*鏈表的結點類型*/
typedef struct node
{Data_type_t data;struct node *pnext;
}Node_t;????????(2) 封裝對象（存放在聲明文件中）
/*鏈表對象類型*/
typedef struct link
{Node_t *phead;int clen;
}Link_t;
????????(3) 創建單向鏈表函數封裝
/*創建單向鏈表*/
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;
}????????(4) 單向鏈表---頭部插入數據函數的封裝
/*向單向鏈表的頭部插入數據*/
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;
}????????(5) 單向鏈表---遍歷函數的封裝
//遍歷
void link_for_each(Link_t *plink)
{Node_t *ptmp = plink->phead;while(ptmp != NULL){printf("%d ", ptmp->data);ptmp = ptmp->pnext;}printf("\n");
}????????(6)?單向鏈表---查找函數的封裝
//查找
Node_t *find_link(Link_t *plink, Data_type_t mydata)
{Node_t *ptmp = plink->phead;while(ptmp != NULL){if(mydata == ptmp->data){return ptmp;}ptmp = ptmp->pnext;}return NULL;
}????????(7)?單向鏈表---遍歷函數的封裝
//修改
int change_link(Link_t *plink, Data_type_t olddata, Data_type_t newdata)
{Node_t *ptmp = find_link(plink, olddata);if(ptmp != NULL){ptmp->data = newdata;return 0;}return -1;
}????????(8)單向鏈表---頭刪函數的封裝（刪除前需判斷是不是空結點）
/*是不是空結點*/
int is_empty_link(Link_t *plink)
{return NULL == plink->phead;
}//刪除
int delete_link_head(Link_t *plink)
{if(is_empty_link(plink)){return -1;}Node_t *ptmp;ptmp = plink->phead;plink->phead = ptmp->pnext;free(ptmp);plink->clen--;return 0;
}? ? ? ? (9) 單向鏈表---尾部插入數據的函數的封裝
/*向單向鏈表的尾部插入數據*/
int insert_link_tail(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(is_empty_link(plink) == 0){plink->phead = pnode;pnode->pnext = NULL;plink->clen++;}else{Node_t *ptmp = plink->phead;while(ptmp->pnext != NULL){ptmp = ptmp->pnext;}ptmp->pnext = pnode;plink->clen++;}return 0;
}? ? ? ? (10) 單向鏈表---尾刪函數的封裝
//尾刪
int delete_link_tail(Link_t *plink)
{if(is_empty_link(plink) == 0){return -1;}Node_t *ptmp = plink->phead;if(NULL == ptmp->pnext){delete_link_head(plink);}else{while(ptmp->pnext->pnext != NULL){ptmp = ptmp->pnext;}ptmp->pnext = NULL;plink->clen--;//free(ptmp->pnext);}return 0;
}
? ? ? ? (11) 單向鏈表---鏈表銷毀函數的封裝
//銷毀
void destroy_link(Link_t *plink)
{while(is_empty_link(plink) != 0){delete_link_head(plink);}free(plink);printf("success!\n");
}
????????(11) 上述代碼在封裝函數框需包含以下三種頭文件，其中“link.h”是自己命名的聲明文件，在后續內容中說明
#include<stdio.h>
#include<stdlib.h>
#include"link.h"
?????2）單向鏈表的函數聲明
#ifndef _LINK_H
#define _LINK_H/*鏈表存儲的數據的數據類型*/
typedef int Data_type_t;extern Link_t *create_link();
extern int insert_link_head(Link_t *plink, Data_type_t data);
extern void link_for_each(Link_t *plink);
extern Node_t *find_link(Link_t *plink, Data_type_t mydata);
extern int change_link(Link_t *plink, Data_type_t olddata, Data_type_t newdata);
extern int delete_link_head(Link_t *plink);
extern int insert_link_tail(Link_t *plink, Data_type_t data);
extern int delete_link_tail(Link_t *plink);
extern void destroy_link(Link_t *plink);#endif???? 3）單向鏈表的上述函數在主函數中的運行格式
#include<stdio.h>
#include"link.h"int main(int argc, const char *argv[])
{Node_t *ret = NULL;Link_t *plink = create_link();if(NULL == plink){return -1;}insert_link_head(plink, 1);insert_link_head(plink, 2);insert_link_head(plink, 3);insert_link_head(plink, 4);insert_link_head(plink, 5);link_for_each(plink);ret = find_link(plink, 4);if(ret == NULL){printf("not found\n");}else{printf("found %d\n", ret->data);}change_link(plink, 4, 15);link_for_each(plink);delete_link_head(plink); link_for_each(plink);*/尾插、尾刪、銷毀insert_link_tail(plink, 1);insert_link_tail(plink, 2);insert_link_tail(plink, 3);insert_link_tail(plink, 4);insert_link_tail(plink, 5);link_for_each(plink);delete_link_tail(plink);link_for_each(plink);destroy_link(plink);*/return 0;
}【END】
)
