1. 雙向鏈表
1.1 結(jié)構(gòu)與初始化
雙向鏈表
- 單向鏈表只能找到后驅(qū)鸡号。
- 雙向鏈表能輕松地獲取前驅(qū)和后繼琼牧。
- 插入時(shí)电爹，不管是單向還是雙向蔫仙，都需要先找對(duì)應(yīng)位置的前驅(qū)。
- 刪除時(shí)丐箩，由于雙向鏈表可以訪問(wèn)前驅(qū)和后繼摇邦，就不需要先找對(duì)應(yīng)位置的前驅(qū)。
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define NOT_FOUND -1
/* ElemType類型根據(jù)實(shí)際情況而定屎勘，這里假設(shè)為int */
typedef int ElemType;
/* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼施籍，如OK等 */
typedef int Status;
/*線性結(jié)構(gòu)使用順序表的方式存儲(chǔ)*/
//鏈表結(jié)構(gòu)設(shè)計(jì)
typedef struct Node {
struct Node *prior;
ElemType data;
struct Node *next;
} Node, *LinkList;
Status InitList(LinkList *L)
{
//產(chǎn)生頭結(jié)點(diǎn)，并使用L指向此頭結(jié)點(diǎn)
*L = (LinkList)malloc(sizeof(Node));
//存儲(chǔ)空間分配失敗
if (*L == NULL) return ERROR;
//將頭結(jié)點(diǎn)的指針域置空
(*L)->prior = NULL;
(*L)->next = NULL;
return OK;
}
1.2 遍歷
Status ListTraverse(LinkList L)
{
if (L == NULL) return ERROR; // 空表
LinkList p = L->next; // 跳過(guò)頭結(jié)點(diǎn)
while (p) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
return OK;
}
1.3 插入
插入節(jié)點(diǎn)
插入時(shí)概漱，需要前一個(gè)節(jié)點(diǎn)來(lái)找到后一個(gè)節(jié)點(diǎn)丑慎。
Status ListInsert(LinkList *L, int loc, ElemType elem)
{
if (*L == NULL) return ERROR; // 空表
LinkList p, q;
p = *L;
int i = 1;
for (; p && i < loc; p = p->next, i++); // 找到idx位置
if(!p || i > loc) return ERROR; // 第idx個(gè)元素不存在
q = (LinkList)malloc(sizeof(Node));
if (!q) return ERROR; // 沒(méi)創(chuàng)建出來(lái)報(bào)錯(cuò)
q->data = elem;
q->next = p->next; // q的后繼指向p的后繼，p-next可能為NULL犀概，q->next也不用顯式賦值NULL
p->next = q; // p的后繼指向q
if (q->next) q->next->prior = q; // q的后繼的前驅(qū)指向q立哑，最后可能為NULL
q->prior = p; // q的前驅(qū)指向p
return OK;
}
1.4 刪除
刪除節(jié)點(diǎn)
找到被刪除節(jié)點(diǎn)，讓前后牽手就行了姻灶。
Status ListDeleteLoc(LinkList *L, int loc, ElemType *elem)
{
if (*L == NULL) return ERROR; // 空表
LinkList p = (*L)->next;
int i = 1;
for (; p && i < loc; p = p->next, i++); // 找到idx位置
if(!p || i > loc) return ERROR; // 第idx個(gè)元素不存在
p->prior->next = p->next; // p的前驅(qū)的后繼指向p的后繼
if (p->next) p->next->prior = p->prior; // p的后繼的前驅(qū)指向p的前驅(qū)铛绰，最后可能為NULL
*elem = p->data;
free(p); // 釋放被刪除節(jié)點(diǎn)
return OK;
}
1.5 刪除指定元素
Status ListDeleteElem(LinkList *L, ElemType elem)
{
if (*L == NULL) return ERROR; // 空表
LinkList p = (*L)->next;
while (p && p->data != elem) p = p->next; // 找到對(duì)應(yīng)元素
if(!p) return ERROR; // 元素elem不存在
p->prior->next = p->next; // 將p的前驅(qū)指向p的后繼
if (p->next) p->next->prior = p->prior; // 將p的后繼指向p的前驅(qū)，最后可能為NULL
free(p); // 釋放被刪除節(jié)點(diǎn)
return OK;
}
1.6 更新指定位置
Status ListUpdateElem(LinkList L, int loc, ElemType elem)
{
if (L == NULL) return ERROR; // 空表
LinkList p = L->next;
int i = 1;
for (; p && i < loc; p = p->next, i++); // 找到idx位置
if(!p || i > loc) return ERROR; // 第idx個(gè)元素不存在
p->data = elem;
return OK;
}
2. 循環(huán)雙向鏈表
2.1 結(jié)構(gòu)與初始化
線性雙向鏈表
循環(huán)雙向鏈表
循環(huán)雙向鏈表的創(chuàng)建實(shí)際就是雙向鏈表的尾節(jié)點(diǎn)后驅(qū)指向頭結(jié)點(diǎn)产喉，頭結(jié)點(diǎn)前驅(qū)指向尾節(jié)點(diǎn)捂掰，最終形成一個(gè)環(huán)敢会。
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define NOT_FOUND -1
/* ElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */
typedef int ElemType;
/* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼这嚣，如OK等 */
typedef int Status;
/*線性結(jié)構(gòu)使用順序表的方式存儲(chǔ)*/
//鏈表結(jié)構(gòu)設(shè)計(jì)
typedef struct Node {
struct Node *prior;
ElemType data;
struct Node *next;
} Node, *LinkList;
Status InitList(LinkList *L, ElemType elem)
{
//產(chǎn)生頭結(jié)點(diǎn)鸥昏，并使用L指向此頭結(jié)點(diǎn)
*L = (LinkList)malloc(sizeof(Node));
//存儲(chǔ)空間分配失敗
if (*L == NULL) return ERROR;
//將頭結(jié)點(diǎn)的指針指向自己
(*L)->prior = *L;
(*L)->next = *L;
(*L)->data = elem;
return OK;
}
依次輸入創(chuàng)建雙向循環(huán)鏈表：
Status CreateList2(LinkList *L) {
ElemType elem;
LinkList tail = NULL;
while (1) {
scanf("%d", &elem); // 輸入數(shù)據(jù)
if (elem == 0) break; // 輸入0時(shí)結(jié)束
if (*L == NULL) { // 表是空的時(shí)候
*L = (LinkList)malloc(sizeof(Node)); // 創(chuàng)建表頭
if (*L == NULL) return ERROR; // 沒(méi)創(chuàng)建出來(lái)報(bào)錯(cuò)
(*L)->data = elem; // 存入數(shù)據(jù)
tail = *L; // 尾節(jié)點(diǎn)，方便后續(xù)添加
} else { // 表不為空
tail->next = (LinkList)malloc(sizeof(Node)); // 創(chuàng)建新節(jié)點(diǎn)
if (!tail->next) return ERROR; // 沒(méi)創(chuàng)建出來(lái)報(bào)錯(cuò)
tail->next->data = elem; // 存入數(shù)據(jù)
tail->next->prior = tail;
tail = tail->next; // 之前的尾節(jié)點(diǎn)指向新節(jié)點(diǎn)
}
}
tail->next = *L; // 形成環(huán)
(*L)->prior = tail;
return OK;
}
2.1 正向遍歷
Status ListTraverse(LinkList L)
{
LinkList p = L; // 從自己開(kāi)始
do {
printf("%d ",p->data);
p = p->next;
} while (p != L); // 到自己的時(shí)候停止
printf("\n");
return OK;
}
2.2 反向遍歷
Status ListTraverseBackwards(LinkList L)
{
LinkList p = L->prior;
do {
printf("%d ",p->data);
p = p->prior;
} while (p != L->prior);
printf("\n");
return OK;
}
2.3 插入
插入節(jié)點(diǎn)
插入時(shí)姐帚，不管是單向還是雙向吏垮，都需要先找對(duì)應(yīng)位置的前驅(qū)。
Status ListInsert(LinkList *L, int loc, ElemType elem)
{
if (*L == NULL || loc < 1) return ERROR; // 空表罐旗，位置非法
LinkList tmp = (LinkList)malloc(sizeof(Node)); // 創(chuàng)建新節(jié)點(diǎn)
if (!tmp) return ERROR; // 沒(méi)創(chuàng)建出來(lái)報(bào)錯(cuò)
tmp->data = elem; // 存入數(shù)據(jù)
LinkList target = *L; // 不管loc是多少膳汪，都是從頭開(kāi)始找
if (loc == 1) {
for (; target->next != *L; target = target->next); // 找到頭結(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)(尾節(jié)點(diǎn))
*L = tmp; // 頭結(jié)點(diǎn)變?yōu)樾鹿?jié)點(diǎn)
} else {
int idx = 1;
for (; target->next != *L && idx < loc - 1; target = target->next, ++idx); // 找到loc結(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
if (target->next == *L || idx > loc - 1) return ERROR; // 找了一圈了，還沒(méi)到指定位置九秀，越界
}
tmp->next = target->next; // 新節(jié)點(diǎn)的后驅(qū)指向前一個(gè)節(jié)點(diǎn)的后驅(qū)
target->next = tmp; // 前一個(gè)節(jié)點(diǎn)指向新節(jié)點(diǎn)
tmp->next->prior = tmp; // 新節(jié)點(diǎn)后繼的前驅(qū)指向新節(jié)點(diǎn)
tmp->prior = target; // 新節(jié)點(diǎn)的前驅(qū)指向前一個(gè)節(jié)點(diǎn)
return OK;
}
2.4 刪除
刪除節(jié)點(diǎn)
刪除時(shí)遗嗽，由于雙向鏈表可以訪問(wèn)前驅(qū)和后繼，就不需要先找對(duì)應(yīng)位置的前驅(qū)鼓蜒。
Status ListDeleteLoc(LinkList *L, int loc, ElemType *elem)
{
if (*L == NULL || loc < 1) return ERROR; // 空表痹换，位置非法
LinkList target = *L; // 不管loc是多少，都是從頭開(kāi)始找
if (loc == 1) {
if ((*L)->next == *L) { // 如果只有1個(gè)節(jié)點(diǎn)
free(*L);
*L = NULL;
return OK;
};
*L = (*L)->next; // 頭節(jié)點(diǎn)變?yōu)槲补?jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
} else {
int idx = 1;
for (; target->next != *L && idx < loc; target = target->next, ++idx); // 找到loc節(jié)點(diǎn)
if (target->next == *L || idx > loc) return ERROR; // 找了一圈了都弹，還沒(méi)到指定位置娇豫，越界
}
target->prior->next = target->next; // target的前驅(qū)指向target的后繼
target->next->prior = target->prior; // 將target的后繼的前驅(qū)指向target的前驅(qū)
*elem = target->data;
free(target); // 釋放被刪除節(jié)點(diǎn)
return OK;
}
2.5 刪除指定元素
Status ListDeleteElem(LinkList *L, ElemType elem)
{
if (*L == NULL) return ERROR; // 空表
LinkList target = *L; // 都是從頭開(kāi)始找
for (; target->next != *L && target->data != elem; target = target->next); // 找到elem元素所在節(jié)點(diǎn)
if (target->next == *L && target->data != elem) return ERROR; // 找了一圈了，沒(méi)有找到
if (target->next == target->prior) { // 前驅(qū)和后繼相等缔杉，說(shuō)明只有一個(gè)節(jié)點(diǎn)
free(target);
*L = NULL;
return OK;
}
target->prior->next = target->next; // target的前驅(qū)指向target的后繼
target->next->prior = target->prior; // 將target的后繼的前驅(qū)指向target的前驅(qū)
if (*L == target) *L = (*L)->next; // 如果是頭節(jié)點(diǎn)锤躁，移動(dòng)為下一個(gè)
free(target); // 釋放被刪除節(jié)點(diǎn)
return OK;
}
