双链表的实现方式

实现方式：不带头结点和带头结点。

同理，使用带头结点的策略。

个人认为，双链表考算法大题可能性不大，但是以防万一还是写一个模板

双链表的重难点应该是边界判断，比如它的指定位置插入元素、指定位置删除元素。

双链表的类型描述

1
2
3
4
typedef struct DNode{
	int data;// 数据域
	struct DNode * prior,* next;// 前驱和后继指针
}DNode, * DLinkList;

初始化

1
2
3
4
5
6
7
8
9
// 初始化
void InitList(DLinkList & list){
	// 给头结点分配内存
	list = (DNode *)malloc(sizeof(DNode));
	
	// 张开双手的双链表的空表状态
	list -> prior = NULL;
	list -> next = NULL;
}

判空

1
2
3
4
5
6
// 空表判断
bool Empty(DLinkList list){
	// 如果头结点指向的下一个结点是NULL
	if(!list -> next) return true;
	else return false;
}

后插操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 将元素x后插到节点p
bool InsertNextNode(DNode * p, int x){
	// 不能插入到NULL后面
	if(!p) return false;
	
	// 创建元素x的载体，并且初始化
	DNode * s = (DNode *)malloc(sizeof(DNode));
	s -> data = x;
	
	// 双链表最后一个节点插入比较特殊，因此需要特判
	// 只有当不是双链表最后一个节点才操作 p -> next -> prior
	if(p -> next) p -> next -> prior = s;
	s -> next = p -> next;
	p -> next = s;
	s -> prior = p;
	
	return true;
}

尾插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 尾插法
void TailInsert(DLinkList & list){
	InitList(list);
	
	// 记录尾指针（一开始是指向头结点）
	DNode * r = list;
	
	int x;
	cin >> x;
	
	while(x != 9999){
		// 1.创建新节点
		DNode * p = (DNode *)malloc(sizeof(DNode));
		p -> data = x;
		// 2.插入
		p -> next = r -> next;
		r -> next = p;
		p -> prior = r;
		// 3.更新尾指针
		r = p;
		cin >> x;
	}
	
	// 尾指针置空
	r -> next = NULL;
}

按位查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 按位查找
DNode * GetElem(DLinkList list, int i){
	// 如果是第0个位置返回头结点
	if(i == 0) return list;
	// 非法输入
	if(i < 0) return NULL;
	
	// 从第一个节点开始计数（可能为空）
	int j = 1;
	DNode * p = list -> next;
	
	// 查找（不为空，且小于要找到的位序）
	while(p && j < i){
		p = p -> next;
		j++;
	}
	// 如果没那么长，也会返回p，此时p为NULL
	return p;
}

在指定位置插入元素

1
2
3
4
5
6
// 在第 i 个位置，插入元素 x
void Insert(DLinkList & list, int i, int x){
	// 找到第 i - 1 个节点执行后插操作
	DNode * p = GetElem(list, i - 1);
	InsertNextNode(p, x);
}

在指定位置删除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 删除第 i 个位置的元素
void Delete(DLinkList & list, int i){
	// 删除位置是否合法
	if(i < 1 || i > Length(list)){
		cout<<"delete failed: index is wrong."<<endl;
		return;
	}
	
	// 找到第 i - 1 个元素
	DNode * p = GetElem(list, i - 1);
	// 被删除的元素
	DNode * q = p -> next;
	
	// 警惕！如果删除的是最后一个节点，那么需要特判
	// 只有删除的不是最后一个节点
	if(q -> next){
		q -> next -> prior = p;
	}
	p -> next = q -> next;
	free(q);
}