有的時(shí)候，處于內存中的數據并不是連續的。那么這時(shí)候，我們就需要在數據結構中添加一個(gè)屬性，這個(gè)屬性會(huì )記錄下面一個(gè)數據的地址。有了這個(gè)地址之后，所有的數據就像一條鏈子一樣串起來(lái)了，那么這個(gè)地址屬性就起到了穿線(xiàn)連結的作用。
相比較普通的線(xiàn)性結構，鏈表結構的優(yōu)勢是什么呢？我們可以總結一下：
（1）單個(gè)節點(diǎn)創(chuàng )建非常方便，普通的線(xiàn)性?xún)却嫱ǔＴ趧?chuàng )建的時(shí)候就需要設定數據的大小
（2）節點(diǎn)的刪除非常方便，不需要像線(xiàn)性結構那樣移動(dòng)剩下的數據
（3）節點(diǎn)的訪(fǎng)問(wèn)方便，可以通過(guò)循環(huán)或者遞歸的方法訪(fǎng)問(wèn)到任意數據，但是平均的訪(fǎng)問(wèn)效率低于線(xiàn)性表
那么在實(shí)際應用中，鏈表是怎么設計的呢？我們可以以int數據類(lèi)型作為基礎，設計一個(gè)簡(jiǎn)單的int鏈表：
（1）設計鏈表的數據結構
- typedef struct _LINK_NODE
- {
- int data;
- struct _LINK_NODE* next;
- }LINK_NODE;
- LINK_NODE* alloca_node(int value)
- {
- LINK_NODE* pLinkNode = NULL;
- pLinkNode = (LINK_NODE*)malloc(sizeof(LINK_NODE));
-
- pLinkNode->data = value;
- pLinkNode->next = NULL;
- return pLinkNode;
- }
（3）刪除鏈表
- void delete_node(LINK_NODE** pNode)
- {
- LINK_NODE** pNext;
- if(NULL == pNode || NULL == *pNode)
- return ;
-
- pNext = &(*pNode)->next;
- free(*pNode);
- delete_node(pNext);
- }
- STATUS _add_data(LINK_NODE** pNode, LINK_NODE* pDataNode)
- {
- if(NULL == *pNode){
- *pNode = pDataNode;
- return TRUE;
- }
-
- return _add_data(&(*pNode)->next, pDataNode);
- }
-
- STATUS add_data(const LINK_NODE** pNode, int value)
- {
- LINK_NODE* pDataNode;
- if(NULL == *pNode)
- return FALSE;
-
- pDataNode = alloca_node(value);
- assert(NULL != pDataNode);
- return _add_data((LINK_NODE**)pNode, pDataNode);
- }
- STATUS _delete_data(LINK_NODE** pNode, int value)
- {
- LINK_NODE* pLinkNode;
- if(NULL == (*pNode)->next)
- return FALSE;
-
- pLinkNode = (*pNode)->next;
- if(value == pLinkNode->data){
- (*pNode)->next = pLinkNode->next;
- free(pLinkNode);
- return TRUE;
- }else{
- return _delete_data(&(*pNode)->next, value);
- }
- }
-
- STATUS delete_data(LINK_NODE** pNode, int value)
- {
- LINK_NODE* pLinkNode;
- if(NULL == pNode || NULL == *pNode)
- return FALSE;
-
- if(value == (*pNode)->data){
- pLinkNode = *pNode;
- *pNode = pLinkNode->next;
- free(pLinkNode);
- return TRUE;
- }
-
- return _delete_data(pNode, value);
- }
（6）查找數據
- LINK_NODE* find_data(const LINK_NODE* pLinkNode, int value)
- {
- if(NULL == pLinkNode)
- return NULL;
-
- if(value == pLinkNode->data)
- return (LINK_NODE*)pLinkNode;
-
- return find_data(pLinkNode->next, value);
- }
- void print_node(const LINK_NODE* pLinkNode)
- {
- if(pLinkNode){
- printf("%d\n", pLinkNode->data);
- print_node(pLinkNode->next);
- }
- }
- int count_node(const LINK_NODE* pLinkNode)
- {
- if(NULL == pLinkNode)
- return 0;
-
- return 1 + count_node(pLinkNode->next);
- }
