王道数据结构C语言双链表基本操作实现

---

一、定义

#define _CRT_SECURE_NO_WARNINGS
#include
#include
typedef struct {//双链表结点类型
	int data;//数据域
	DNode* prior;//前驱
	DNode* next;//后继
}DNode,*DLinkList;
1
2
3
4
5
6
7
8

二、初始化

//初始化（带头结点）
bool InitDLinkList(DLinkList *L) {
	(*L) = (DNode*)malloc(sizeof(DNode));
	if (*L == NULL) {
		return false;//内存不足，分配失败
	}
	(*L)->prior = NULL;//头结点prior永远是NULL
	(*L)->next = NULL;//当前头结点的后继暂时还没有结点
	return true;
}
1
2
3
4
5
6
7
8
9
10

三、判空

//双链表判空
//就看它的头结点的next是否为空就行
bool Empty(DLinkList L) {
	if (L->next == NULL) {
		return true;
	}
	else {
		return false;
	}
}
1
2
3
4
5
6
7
8
9
10

四、插入

给p结点和s结点，要求在p之后插入s

对于双链表插入有个口诀：先右边再左边，先连后断
就是先把s和右边的结点全处理完
再处理s和左边的结点（p）

示意图如下：
先处理右边
第一步：先连

第二步：后断

再处理左边
第三步：先连

第四步：后断

上面步骤也不唯一，但是也不是任意的，必须保证第12步在第4步之前执行
如果只是简单实现，就用我上面的口诀：先右边再左边，先连后断

//插入
//在p结点后插入s结点
bool InsertNextDNode(DNode* p, DNode* s) {
	if (p == NULL || s == NULL) {//非法参数
		return false;
	}
	//先处理右边
	//先连
	s->next = p->next;
	//后断
	if (p->next != NULL) {
		//这里优化一下，防止p后面没有结点是NULL，那你插了s之后，NULL是不需要指向s的
		p->next->prior = s;
	}
	//再处理左边
	//先连
	s->prior = p;
	//后断
	p->next = s;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

五、删除

给结点p，让你删它的后继结点q
这个和单链表删除大差不差，都挺简单的

先让p连上q的后继结点

然后q后继结点的前驱连上p

最后把q释放掉就完了

bool DeleteNextDNode(DNode* p) {//给p，删它后面一个结点
	if (p == NULL) {//非法输入
		return false;
	}
	DNode* q = p->next;
	if (q == NULL) {//p后面没有结点
		return false;
	}
	p->next = q->next;
	if (q->next != NULL) {//如果q后面没结点，就不用往前连了
		q->next->priro = p;
	}
	free(q);
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15