鏈表 linked list
定義
就是一些包含數(shù)據(jù)的獨(dú)立數(shù)據(jù)結(jié)構(gòu)的集合唱歧。鏈表中每個(gè)節(jié)點(diǎn)通過鏈或指針連接在一起宪摧。程序通過指針訪問鏈表中節(jié)點(diǎn)。
單鏈表
每個(gè)節(jié)點(diǎn)包含一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針颅崩，鏈表最后一個(gè)節(jié)點(diǎn)的指針字段的值為NULL几于，提示鏈表后不再有其他節(jié)點(diǎn)。
- 通過鏈表第一個(gè)節(jié)點(diǎn)可以訪問剩余所有的節(jié)點(diǎn)沿后。
- 根指針（root pointer）指向鏈表的第一個(gè)節(jié)點(diǎn)沿彭。
typedef struct NODE{
struct NODE *link;
int value;
}Node；
單鏈表的插入
將新節(jié)點(diǎn)插入到一個(gè)有序的單鏈表中
- 插入函數(shù)需要檢查是否到達(dá)鏈表的尾部
- root是一個(gè)指針
- 為新節(jié)點(diǎn)分配內(nèi)存時(shí)是否成功
#define FALSE 0
#define TRUE 1
int sll_insert(Node **linkp,int new_value){
Node *current;
Mode *new;
//尋找正確插入位置：按序訪問鏈表
while((current = *linkp) != NULL && current->value < new_value)
linkp = ¤t -> link;
// 為新節(jié)點(diǎn)分配內(nèi)存
new = (Node *)malloc(sizeof(Node));
// 如果內(nèi)存分配失敗返回false
if(new == NULL)
return FALSE;
// 將新值存到新節(jié)點(diǎn)中
new->value = new_value;
new->link = current;
return TRUE；
}
雙鏈表
每個(gè)節(jié)點(diǎn)都包含兩個(gè)指針：指向前一個(gè)節(jié)點(diǎn)的指針和指向后一個(gè)節(jié)點(diǎn)的指針
typedef struct NODE{
struct NODE *fwd;
struct NODE *bwd;
int value;
}Node；
根節(jié)點(diǎn)
- 根節(jié)點(diǎn)fwd字段指向鏈表的第一個(gè)節(jié)點(diǎn)
- 根節(jié)點(diǎn)bwd字段指向鏈表的最后一個(gè)節(jié)點(diǎn)
- 如果量表為空储狭，則兩個(gè)字段都為NULL
雙鏈表的插入
編寫一個(gè)當(dāng)插入值原先不存在于鏈表中才插入的插入函數(shù)
將節(jié)點(diǎn)插入到鏈表中，可能出現(xiàn)的四種情況
- 新值插入到鏈表的中間位置
- 新值插入到鏈表的起始位置
- 新值插入到鏈表的結(jié)束位置
- 原鏈表為空的情況下饱搏，插入的位置既是起始位置又是結(jié)束位置
int dll_insert(Node *rootp,int value){
Node *this;
Node *next;
Node *new;
for(this = rootp;(next = this->fwd) != NULL;this = next){
if(next->value == value)
return 0;
if(next->value>value)
break;
}
new = (Node *)malloc(sizeof(node));
if(new == NULL)
return -1;
new->value = value;
newnode->fwd = next;
this->fwd = new;
if(this != rootp)
new->bwd = this;
else
new->bwd = NULL;
if(next != NULL)
next->bwd = new;
else
rootp->bwd - new;
return 1;
}
