一、什么是數(shù)據(jù)結(jié)構(gòu)

1.1、組織存儲數(shù)據(jù)

????????---------》內(nèi)存（存儲）

1.2、研究目的

• 如何存儲數(shù)據(jù)（變量，數(shù)組....)
• 程序=數(shù)據(jù)結(jié)構(gòu)+算法

1.3、常見保存數(shù)據(jù)的方法

1. 數(shù)組：保存自己的數(shù)據(jù)
2. 指針：是間接訪問已經(jīng)存在的空間------------》操作數(shù)據(jù)，并不能銷毀別人的數(shù)據(jù)
3. 指針數(shù)組：并不保存數(shù)據(jù)，也是指向那個空間，并不能保存數(shù)組
4. 二維數(shù)組：保存數(shù)據(jù)的
5. 數(shù)據(jù)庫也其實數(shù)據(jù)結(jié)構(gòu)，實質(zhì)上是對復(fù)雜數(shù)據(jù)的一種封裝

二、數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系

2.1、數(shù)據(jù)的邏輯結(jié)構(gòu)

????????數(shù)據(jù)元素與元素之間的關(guān)系

1. 集合：關(guān)系平等
2. 線性：元素之間一對一的關(guān)系（表，數(shù)組，鏈表）
3. 有當(dāng)前數(shù)據(jù)出發(fā)，向后最多能找一個后繼，先前找最多只能有一個前驅(qū)
4. 樹形：元素之間一對多（二叉樹），從當(dāng)前找，后繼有多個，前驅(qū)只有1個
5. 圖型結(jié)構(gòu)：元素之間多對多的關(guān)系（網(wǎng)狀結(jié)構(gòu)）
6. 后繼有多個，前驅(qū)有多個

2.2、數(shù)據(jù)的物理結(jié)構(gòu)

1、順序存儲：采用一段連續(xù)的內(nèi)存空間保存元素。
優(yōu)點:空間連續(xù)，訪問方便缺點:插入刪除需要移動大量的元素需要預(yù)分配內(nèi)存空間容易造成存儲空間碎片
2、鏈?zhǔn)酱鎯?采用一組非連續(xù)的內(nèi)存空間保存元秦
缺點:訪問元秦效率低優(yōu)點:插入和刪除數(shù)據(jù)方便不需要預(yù)分配內(nèi)存
3、索引存儲:通過關(guān)鍵字構(gòu)建索引表，通過索引表來來找到數(shù)據(jù)的存儲位置

索引：維護(hù)索引表，關(guān)鍵字和其對應(yīng)得地址

4、散列存儲(哈希存儲):將數(shù)據(jù)元素的存儲位置與關(guān)鍵碼之間建立確定對應(yīng)關(guān)系從而實現(xiàn)查找的存儲方式

散列：選取關(guān)鍵字，經(jīng)過計算，算出對應(yīng)位置，下次只需要，拿著這個名字，經(jīng)過計算，就找到位置

2.3、數(shù)組與鏈表區(qū)別

2.3.1、數(shù)組 線性順序存儲結(jié)構(gòu)

1、空間連續(xù)

2、訪問數(shù)據(jù)方便（O(1))

3、數(shù)據(jù)插入、刪除復(fù)雜,需要移動大量數(shù)據(jù)（O(n)）

4、預(yù)分配內(nèi)存空間

5、容易產(chǎn)生內(nèi)存碎片

1、按照指定字節(jié)對齊

2、注意結(jié)構(gòu)成員分布

2.3.2、鏈表 線性鏈?zhǔn)浇Y(jié)構(gòu)

1、空間不連續(xù)

2、訪問數(shù)據(jù)不方便（O(n))

3、數(shù)據(jù)的插入、刪除方便，時間復(fù)雜度（O(1))

4、不需要預(yù)分配空間，只需申請一個新的節(jié)點插入進(jìn)去即可

5、能夠利用內(nèi)存空間中比較小的碎片

注意：說數(shù)據(jù)屬于那種關(guān)系的時候，兩種都說。

2.4、物理結(jié)構(gòu)

1、線性結(jié)構(gòu)：

順序表：-----》數(shù)組

鏈?zhǔn)奖?#xff1a;-----》鏈表

2、鏈表：

單向鏈表：

有頭鏈表：有一個頭結(jié)點進(jìn)行操作，只不過沒有數(shù)據(jù)

無頭鏈表：沒有上述的東西

3、封裝

--------》高內(nèi)聚、低耦合

低耦合，關(guān)聯(lián)程度低

高內(nèi)聚，一個函數(shù)干一件事

面向過程的編程思想：第一步干什么，第二步3干什么....

面向?qū)ο蟮木幊趟枷?#xff0c;封裝性比較好

用什么來做什么

冰箱----------------------》

屬性：特性（變量）

行為：裝東西（函數(shù)）

大象-----------------------》

三、鏈表的操作

1、創(chuàng)建頭結(jié)

Link_t *Create_link()
{Link_t *link = malloc(sizeof(link));if(NULL == link){perror("create error");return NULL;}link->clen = 0;link->phead = NULL;return link;
}

2、頭插

int push_link_join(Link_t *plink,DATATYPE data)
{Link_Node_t *pnode = malloc(sizeof(Link_Node_t));if(NULL == pnode){perror("fail node");return -1;}pnode->data = data;pnode->pnext = NULL;pnode->pnext = plink->phead;plink->phead = pnode;plink->clen++;return 0;
}

3、尾插

int tail_insert(Link_t *plink,DATATYPE data)
{Link_Node_t *pnode = malloc(sizeof(Link_Node_t));if(NULL == pnode){perror("fail node");return -1;}pnode->data = data;pnode->pnext = NULL;Link_Node_t *p;p = plink->phead;if(p == NULL){p = pnode;}while(p->pnext){p = p->pnext;}pnode->data = data;pnode->pnext = NULL;p->pnext = pnode;plink->clen++;printf("%d\n",pnode->data);
}

4、遍歷

int travel_link(Link_t *plink)
{int i = 0;Link_Node_t *p ;p = plink->phead;while(p != NULL){printf("num = %d,data = %d\n",i,p->data);++i;p = p->pnext;}
}

5、頭刪

int delete_link_first(Link_t *plink)
{Link_Node_t *pnode;if(plink->phead == NULL){return 0;}else{pnode = plink->phead;plink->phead = pnode->pnext;free(pnode);plink->clen--;}return 0;
}

6、尾刪?

int delete_link_tail(Link_t *plink)
{Link_Node_t *pnode;if(plink->phead == NULL){return 0;}else if(plink->clen == 1){delete_link_first(plink);}else{pnode = plink->phead;while(pnode->pnext->pnext != NULL){pnode = pnode->pnext;}free(pnode->pnext);pnode->pnext = NULL;}
}

7、查對應(yīng)結(jié)點

Link_Node_t *select_link(Link_t *link,DATATYPE data)
{Link_Node_t *pnode  = link->phead;while(pnode->data != data){pnode = pnode->pnext;}printf("num = %d\n",pnode->data);return pnode;
}

8、改

Link_Node_t *alter_link(Link_t *link,DATATYPE data,DATATYPE wishdata)
{Link_Node_t *pnode = select_link(link,data);pnode->data  = wishdata;printf("wishdata = %d\n",pnode->data);return pnode;
}

9、銷毀

int destory_link(Link_t *link)
{Link_Node_t *pnode = link->phead;if(pnode == NULL){free(link);return 0;}else{while(link->clen != 0){delete_link_first(link);}return 0;}free(link);
}