数据结构与算法-列表(双向链表)设计及其排序算法_双链表排序算法

0 概述

本文主要涵盖列表(双向链表)的设计及其排序算法的总结。列表是一种典型的动态存储结构。其中的数据，分散为一系列称作节点(node)的单位，节点之间通过指针相互索引和访问。为了引入新节点或删除原有节点，只需在局部调整少量相关节点之间的指针。这就意味着，采用动态存储策略，可以大大降低动态操作的成本。

1 列表(双向链表)设计

1.1 结点的设计
列表是由一个个结点链接而成，其基本结构便是节点(下文称节点为Node)。Node的良好设计可以减少列表的设计难度。根据列表的特性，一个Node一般包括数据、指向前驱的指针和指向后继的指针。很显然我们需要将其封装入一个结构体(C++增强了结构体的功能，可以作为类使用)或类内，为了优化列表的设计、简化Node的使用，
1）我们可以设计Node的构造函数并在构造函数内为其指定前驱和后继；
2）除此以外，我们还可以定义插入当前节点之前和之后的插入函数，这可以简化列表的Node的插入操作。
Node的设计函数如下所示：

//列表结点的设计
struct MyListNode
{
	//数据定义
	T m_data;
	//指向前驱的指针
	MyListNode<T>* m_pred;
	//指向后继的指针
	MyListNode<T>* m_succ;
	
	//构造函数
	//默认构造函数，前驱和后继为nullptr
	MyListNode() { m_pred = nullptr; m_succ = nullptr; }
	//可以指向前驱和后继的构造函数
	MyListNode(T data, MyListNode<T>* pred=nullptr, MyListNode<T>* succ= nullptr)
		:m_data(data),m_pred(pred),m_succ(succ){}

	//操作接口
	//由于创建新节点时已经创建好一条链接关系
	//若作为当前节点的前驱插入，则注意：1谁作为当前节点的前驱 2谁的后继是当前节点
	//若作为当前节点的后继插入，则注意：1当前节点是谁的前驱 2当前节点的后继是谁

	//作为当前节点前驱插入
	MyListNode<T>* InsertAsPred(const T& data)
	{         
		//创建新节点，以当前节点的前驱作为前驱，以当前节点作为后继 则  pred<-- new node -->this
		MyListNode<T>* p_node = new MyListNode<T>(data, m_pred, this);
		
		//由于构造新结点时已经为新结点指定了前驱和后继
		//故这里只需将当前节点的前驱后继设为新节点，当前节点的前驱设为新节点
		//  pred--> new node <-- this
		
		//将当前节点的后继设为新节点
		m_pred->m_succ = p_node;

		//将当前节点的前驱设为新节点
		m_pred = p_node;
		
		return p_node;
	}

	//作为当前节点后继插入
	MyListNode<T>* InsertAsSucc(const T& data)
	{
		//插入原理 与InsertAsPred 类似
		//创建新节点，以当前节点作为前驱，当前节点的后继作为后继  this <-- new node --> succ
		MyListNode<T>* p_node = new MyListNode<T>(data, this, m_succ);
		
		// 由于构造新结点时已经为新结点指定了前驱和后继
		//故这里只需将当前节点的前驱后继设为新节点，当前节点的前驱设为新节点
		// this <-- new node <-- succ
		
		//当前节点的后继指向新节点
		m_succ = p_node;

		//当前节点的后继指向新节点
		m_succ->m_pred = p_node;

		return p_node;
	}
};
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

1.2 列表的设计
列表是在节点的基础上设计的，良好的节点设计可以大大简化列表的设计。
列表的设计包括一个私有的头节点(header)和尾节点(tailer)，二者对外不可见，仅用于对数据的管理和跟踪，不用于数据的存储。
列表的第1个元素为header的后继，最后1个元素为tailer的前驱。若列表内没有元素则header的后继为tailer，tailer的前驱为header。
综上，列表的结构如下：

2 列表的搜索算法

由于列表不可随机存取，故列表只能根据提供的起始节点进行逐一对比查找，故其查找的复杂度O(n).
但是根据其查找的用途不同，我们根据列表是否有序进行不同的查找，返回不同的结果。
1）对于无序列表，若找不到需要的数据，则直接返回nullptr即可；
2）但是对于有序列表的查找，我们一般需要使用其返回结果进行插入、排序之类的操作，所以对其返回结果有特别的要求。
2.1 无序列表的查找
找到直接返回对应节点的地址，找不到直接返回nullptr.

//对无序列表进行查找，若没有找到则直接返回nullptr
//该查找向前查找，向后查找与此类似
// data   ：需要查找的数据
// num    ：向前查找的数据数目
// p_node ：查找的起始点
//若查找整个序列 则为 Find(data,myList.Size(),myList.Last());
template<typename T>
MyListNode<T>* MyList<T>::Find(T data,int num, MyListNode<T>* p_node)
{
	//依次向前查找逐一比对
	while ((num--) && ((p_node =p_node->m_pred)!= m_header))
	{
		if (data == p_node->m_data)
		{
			return p_node;
		}
	}

	//若找不到则返回nullptr
	return nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.2 有序列表的查找
对于有序列表的查找，我们一般需要使用其查找结果。假设有序列表升序排列(也就是从小到大排列，也可能有重复数据)，如果我们需要将一数据A插入到当前列表List且仍保持List有序，那么
1）如果能在列表中找到该数据A，则我们希望其插入到重复数据的最后一个；
2）如果不能找到该数据A，则我们希望返回小于该数据的第一个数据B的位置Addr_B，那么我们可以将数据A插入数据B的后面而保持List有序。
为了满足上述要求，则有序列表的查找算法的返回值应为上述情况对应的值，查找算法如下设计：

//适合有序列表的查找方法,返回小于当前元素的第一个位置
//或者返回等于该元素的重复元素的最后一个位置
//如果没有找到小于或等于当前元素的元素，则返回左边界的前驱.有可能是m_header
//该查找向前查找，向后查找与此类似
// data   ：需要查找的数据
// num    ：向前查找的数据数目
// p_node ：查找的起始点
//若查找整个序列 则为 Find(data,myList.Size(),myList.Last());
template<typename T>
MyListNode<T>* MyList<T>::Search(T data, int num, MyListNode<T>* p_node)
{
	while (num-- >= 0)
	{
		if ((p_node = p_node->m_pred)->m_data <= data)
			break;
		//找到小于等于指定元素的元素则终止查找，返回小于当前元素的第一个位置
		//或者返回重复元素的最后一个位置
	}

	return p_node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3 列表的排序算法

列表的排序算法主要包括插入排序、选择排序和归并排序
3.1 插入排序
插入排序的算法的思路为：
1）设当前节点p_node之前的数据为有序的(设为front_list)，之后为无序的；
2）利用有序查找Search函数，找到当前节点p_node在front_list中的位置，将当前节点插入到front_list;
3)p_node移动到下一节点，删除已经插入到front_list的节点。
示意图如下

实现如下：

/插入排序实现
//p_node ：开始排序的起点
//num     ：要排序的节点数目
//example：对全列表排序InsertionSort(myList.First(),myList.Size();
template<typename T>
void MyList<T>::InsertionSort(MyListNode<T>* p_node,int num)
{
	for (int i = 0; i < num; i++)
	{
		//查找当前节点p_node在p_node之前的(有序)数据中应在的位置insert_index
		MyListNode<T*> insert_index = Search(p_node->m_data, i, p_node);
		//将当前节点插入 insert_index
		InsertAsAfter(insert_index, p_node->m_data);
		//移至下一节点
		p_node = p_node->m_succ;
		//删除已插入有序数据的原节点
		Remove(p_node->m_pred);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.2 选择排序
选择排序的基本思路为:
1）将列表分为两部分，前半部分的数据为无序的(设为front_list)，后半部分的数据为有序的(设为rear_list)；
2) 查找front_list中的的最大值max_node并将其从front_list中移除；
3）将max_node插入到front_list的最后端，也是有序列表第一位之前；
4）front_list减少1节点，rear_list增加1节点，再循环2-4步骤；
示意图如下：

代码实现如下：

/选择排序
//p_node  :排序的起点
//num     :要排序的节点的数目
//示例    :对全list排序  SeletcionSort(myList.First(),myList.Size());
template<typename T>
void MyList<T>::SelectionSort(MyListNode<T>* p_node, int num)
{
	//定义有序列表的第一个元素位置
	MyListNode<T>* tailer = p_node;

	//定义无序列表的第一个位置的前驱
	MyListNode<T>* header = p_node->m_pred;
	
	//显然，选择排序需要从后往前排序
	//该步骤循环往后，定义有序列表的第一个元素位置
	//若当前有序列表为空，则为待排序列表最后一个元素的后继，可能为m_tailer
	for (int i = 0; i < num; i++)
		tailer = tailer->m_succ;
	
	for (int i = num; i >1; i--)
	{
		//寻找无序列表的最大值
		MyListNode<T>* max_node = SelectMax(header->m_succ, i);
		//移除无序列表中的最大值max_node，并将最大值插入到无序列表的最后一位，也是有序列表第一位之前
		//相当于交换二者的值
		InsertAsBefore(tailer,Remove(max_node));

		//有序列表的第一位元素向前移动一位
		//有序序列增加一个节点
		tailer = tailer->m_pred;
		
		//for循环中的i-- 表示无序序列减少1个节点，SelectMax查找的节点数目减少1个
	}
}
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
27
28
29
30
31
32
33
34

3.3归并排序
归并排序的基本思路为：
1）分而治之，将无序列表逐次分为前列表(front_list)和后列表(rear_list)，直至两个列表只有一个元素;
2)将front_list与rear_list按照顺序合并,由于列表分割是从大到小，故合并后仍为列表的一部分设为half_list，然后与对应的另一半other_half_list进行有序合并，循环往复直至归并完成，排序也相应完成。
示意图如下所示：
代码实现如下所示：

//p_node   ：需要归并的列表P(当前列表)的起始点
//p_num    ：需要归并的列表P(当前列表)的节点数目
//src_list ：需要归并的列表Q
//q_node   ：需要归并的列表Q的起始点
//q_num    ：需要归并的列表Q的节点数目
//该函数是将q_node开始的q_num个节点归并到p_node开始的列表内
template<typename T>
void MyList<T>::Merge(MyListNode<T>* &p_node, int p_num, MyList<T> &src_list,MyListNode<T>* q_node, int q_num)
{
	//保存当前列表P的起始点p_node的前驱作为归并后列表的前驱
	//这一点很重要，因为后边列表的变更可能修改第一项从而导致无法寻项
	MyListNode<T>* header = p_node->m_pred;
	
	//下列程序中将p_node作为归并列表(MergeList)中最后一个元素的后继来使用
	//q_num==0 表示Q列表归并完成
	while (0<q_num)
	{
		//如果P列表未归并完成且p_node->m_data <= q_node->m_data则p_node插入到归并列表MergeList
		if ((0 < p_num) && (p_node->m_data <= q_node->m_data))
		{
			//p_node被归并后移动到下一节点
			p_node = p_node->m_succ;
			//若干p_node==q_node,则P列表已归并完成
			if(q_node==p_node)
				break;
			//P列表虚归并的节点数目减1
			p_num--;
		}
		else
		{
			//若P列表归并完成或者p_node->m_data > q_node->m_data则q_node插入到汇报列表MergeList
			InsertAsBefore(p_node, q_node->m_data);
			//q_node被归并后移动到下一节点
			q_node = q_node->m_succ;
			//移除已经归并后的q_node
			src_list.Remove(q_node->m_pred);

			//Q列表需归并的节点数目减1
			q_num--;
		}
	}
	p_node = header->m_succ;
}


//归并排序的实现
//p_node  ：要排序列表的起始节点
//num     ：要排序节点的数目
template<typename T>
void MyList<T>::MergeSort(MyListNode<T>* &p_node, int num)
{
	if (num < 2)
		return;
	//求出列表的中点
	int mid = num >> 1;           

	//求出后半列表的起始节点
	MyListNode<T>* q_node = p_node;
	for (int i = 0; i < mid; i++)
	{
		q_node = q_node->m_succ;
	}
	MergeSort(p_node, mid);                       //对前半部分列表进行递归划分
	MergeSort(q_node, num - mid);                 //对后半部分列表进行递归划分
	Merge(p_node, mid, *this, q_node, num - mid); //对划分好的前后列表进行归并，依次迭代直至归并完成，排序也完成
}

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68