数据结构——链表报告

发表于 | 分类于

返回目录

一、设计方式

结点结构：
包含数据域以及指针域，数据域通过模板可以实现不同类型的数据类型。

1
2
3
4
5
6
template <class T>
struct Node
{
	T data;
	Node<T> *next;
};

链表结构：
包含头结点，用于数据的存储，包含一系列函数，用于数据的访问及管理。

1
2
3
4
5
6
7
8
9
template <class T>
class LinkList
{ 
    /*
    略去一系列成员函数
    */
private:
    Node<T> *pHead;		//节点，包含数据域和指针域
};

文件结构：

  • LinkList.cpp
  • LinkList.h
  • test.cpp

LinkList.cpp与LinkList.h用于实现链表模板
test.cpp用于测试模板的正确性

二、具体实现

2.1 LinkList类设计

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
template <class T>
class LinkList
{ 
//**********
//基本函数
//**********
public:
	LinkList();					//无参构造函数
	~LinkList();				//析构函数，作垃圾回收
	LinkList(T a[], int n,string flag);		//构造函数

//**********
//功能函数
//**********
public:
	int ListLength();				//返回链表长度
	T& Get(int pos);				//按位返回元素引用
	int Locate(T item);				//按值找位
	void PrintListLink();			//遍历打印
	void Insert(int pos, T item);	//按位插值
	void Delete(int i);				//按位删值
	void Invert();					//逆序链表
	void Merge(LinkList<T> &L);		//归并链表
	void SelectSort();				//选择排序
	LinkList<T>& operator=(LinkList<T>* L);//重载赋值，便于合并
	friend LinkList<T>* Merge(LinkList<T> &LA, LinkList<T>&LB);
	friend void Merge_1(LinkList<T> &LA, LinkList<T>&LB);
//**********
//成员变量
//**********
private:
	Node<T> *pHead;		//节点，包含数据域和指针域
};

2.1.1 单链表的初始化

单链表可以有两种初始化，无参初始化，只生成头结点的空链表，有参初始化，可以实现带元素节点的链表。

单链表的无参构造函数：

1
2
3
4
5
6
7
8
9
10
11
12
/**
* 无参数构造函数
* 作用:生成头结点
* @param[in] 无
* @param[out] 无
*/
template <class T>
LinkList<T>::LinkList()
{
	pHead = new Node<T>;
	pHead->next = NULL;
}

单链表的有参构造函数：

本函数提供三种插入方法：

  • 头插法（head）
  • 顺序插法（sorted）
  • 尾插法（tail）

根据所给标志不同，选择不同构造方法。

1
2
template <class T>
LinkList<T>::LinkList(T a[],int n,string flag)

1、 头插法（head）

1
2
3
4
5
6
7
8
9
10
11
12
if (flag=="head")
	{
		pHead = new Node<T>;
		pHead->next = NULL;
		for (int i = 0; i < n; i++)
		{
			Node<T> *p = new Node<T>;
			p->data = a[i];
			p->next = pHead->next;
			pHead->next = p;
		}		
	}

头插法每次生成的节点插在头结点的后面，操作简单。

2、顺序插法（sorted）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
else if (flag == "sorted")
	{
		pHead = new Node<T>;	pHead->next = NULL;
		Node<T> *p, *front, *current;
		for (int i = 0; i < n; i++)
		{
			front = pHead;
			p = new Node<T>;
			p->data = a[i];
			current = pHead->next;
			while ((current != NULL) && (current->data < p->data))
			{
				front = current;
				current = current->next;
			}
			p->next = current;
			front->next = p;
		}
	}

顺序插法，在构造的时候，考虑顺序，使得构造函数完成的同时链表有序，时间复杂度为$O(n^2)$，p是新建节点，front以及current确定插入位置。

3、尾插法（tail）

1
2
3
4
5
6
7
8
9
10
11
12
13
else if (flag == "tail")
	{
		pHead = new Node<T>;
		Node<T> * rear = pHead;
		for (int i = 0; i < n; i++)
		{
			Node<T> *p = new Node<T>;
			p->data = a[i];
			rear->next = p;
			rear = p;
		}
		rear->next = NULL;
	}

尾插法，每次生成的节点放在链表尾部，rear指针指向最后一个节点，无须重新遍历。便于插入操作。

  • 其他情况 程序提示错误
    1
    2
    3
    4
    else
    	{
    		cerr << "error at flag choosing!" << endl;
    	}

###2.1.2求链表长度
遍历链表，通过计数器计数，并返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* int ListLength()
* 作用:返回链表节点数
* @param[in] 无
* @param[out] int
*/
template <class T>
int LinkList<T>::ListLength()
{
	int num = 0;
	Node<T> *p = pHead->next;
	while (p!=NULL)
	{
		p = p->next;
		num++;
	}
	return num;
}

2.1.3按位找值

从第一个元素点开始，计数器i初始化为1，找到位序pos后，返回该位置元素的引用，注意此返回值的修改，会对链表值进行改动。同时，需要考虑异常情况，保证程序安全。

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
/**
* T& Get(int pos)
* 作用:获得指定pos位的元素的引用
* @param[in] pos
* @param[out] T
*/
template <class T>
T& LinkList<T>::Get(int pos)
{
	Node<T> *p = pHead->next;
	int i = 1;
	while (p!=NULL && i!=pos)
	{
		p = p->next;
		i++;
	}
	if (p == NULL||i>pos)
	{
		cerr << "数据非法，异常退出。";
		system("pause");
		exit(1);
	}
	else
		return p->data;
}

2.1.4遍历单链表

遍历单链表，并输出各节点元素数据域值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* PrintListLink()
* 作用:遍历并打印链表数据
* @param[in] 
* @param[out] 
*/
template<class T>
void LinkList<T>::PrintListLink()
{
	Node<T> *p = pHead->next;
	while (p!=NULL)
	{
		cout << p->data<<"\t";
		p = p->next;
	}
}

2.1.5单链表的按位插值

遍历查找到第pos-1个节点，插入元素item

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
/**
* Insert(int pos,T item)
* 作用:在pos位置插入元素item
* @param[in]  位置pos 元素item
* @param[out]
*/
template<class T>
void LinkList<T>::Insert(int pos,T item)
{
	Node<T> *p = pHead;
	int j = 0;
	while (p!=NULL && j<pos-1)
	{
		p = p->next;
		j++;
	}
	if (p == NULL)
	{
		cout << "已至链表尾，放弃插入位置，自动插入尾部";
		Node<T> *tmp = new Node<T>;
		tmp->data = item;
		tmp->next = NULL;
		p->next = tmp;
	}
	else
	{
		Node<T> *tmp = new Node<T>;
		tmp->data = item;
		tmp->next = p->next;
		p->next = tmp;
	}
}

2.1.7按位删除

删除第i个元素值，必找到第i-1个节点，并使之链接到i+1个节点上， 同时销毁第i个元素的空间，同时置为NULL。

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
/**
* Delete(int i)
* 作用:按照位序i删除节点
* @param[in]  位置i
* @param[out]
*/
template<class T>
void LinkList<T>::Delete(int i)
{
	Node<T> *p = pHead;
	int j = 0;
	while (p!=NULL && j<i-1)
	{
		p = p->next;
		j++;
	}
	if (p == NULL || p->next == NULL || j > i-1 )
	{
		cerr << "删除位置不在表内，异常退出";
		exit(1);
	}
	else
	{
		Node<T> *tmp = p->next;
		p->next = tmp->next;
		delete tmp;
		tmp=NULL;
	}
}

2.1.8 单链表的逆置

实际就是使用头插法，重新组织链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* Invert()
* 作用:逆序该链表
* @param[in]  
* @param[out]
*/
template<class T>
void LinkList<T>::Invert()
{
	Node<T> *p =  pHead->next;
	pHead->next = NULL;
	while (p != NULL)
	{
		Node<T> *q = p;
		p = p->next;
		q->next = pHead->next;
		pHead->next= q;;
	}
}

2.1.9 合并单链表

这块采用了三种方式合并链表：

  • 成员函数调用
  • 友元无返回值合并
  • 友元有返回值合并

下面来一一介绍。

首先，合并单链表的前提是有序，所以假定传进来的表都是有序的。这边不做有序的判断。

  • 成员函数调用

作为链表的成员函数调用，把传入的链表，归并到调用链表中。由于是成员函数，所以在其中访问私有成员没有问题。

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
/**
* Merge(LinkList<T> &L)
* 作用:将L链表数据合并到调用表 
* @param[in]	
* @param[out]
*/
template <class T>
void LinkList<T>::Merge(LinkList<T> &L)
{
	Node<T> *p3 = pHead;
	Node<T> *p1 = pHead->next;
	Node<T> *p2 = L.pHead->next;
	while ((p1 != NULL) && (p2 != NULL))
	{
		if ((p1->data) < (p2->data))
		{
			p3->next = p1;
			p1 = p1->next;
			p3 = p3->next;
		}
		else
		{
			p3->next = p2;
			p2=p2->next;
			p3 = p3->next;
		}
	}
	if (p1 != NULL) p3->next = p1;
	if (p2 != NULL) p3->next = p2;
	delete L.pHead;
	L.pHead = NULL;
}

  • 友元无返回值合并

这是通过友元的方式，无须调用者，函数目的是把两个链表的值，归并到第一个链表中，友元的声明，使其能够方便的使用私有成员。

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
/**
	* LinkList<T>* Merge(LinkList<T> &, LinkList<T>&)
	* 作用:通过友元方式，把LB元素合并到LA中
	* 注意：LA,LB需有序
	* @param[in] LA,LB
	* @param[out] 
	*/
	friend void Merge_1(LinkList<T> &LA, LinkList<T>&LB){
		Node<T> *p1 = LA.pHead->next;
		Node<T> *p2 = LB.pHead->next;
		Node<T> *p3 = LA.pHead;
		while (p1 != NULL && p2 != NULL)
		{
			if (p1->data<p2->data)
			{
				p3->next = p1;
				p1 = p1->next;
				p3 = p3->next;
			}
			else{
				p3->next = p2;
				p2 = p2->next;
				p3 = p3->next;
			}
		}
		if (p1 != NULL) p3 = p1->next;
		if (p2 != NULL) p3 = p2->next;
		delete LB.pHead;
		LB.pHead = NULL;
	}

  • 友元有返回值合并

这个函数与上个函数的区别在于，这个函数，合并两个链表，并返回这个合并的链表。为了接受这个返回的链表，在类中，重载了赋值运算符“=”。

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
/**
* LinkList<T>* Merge(LinkList<T> &, LinkList<T>&)
* 作用:通过友元方式，合并链表LA,LB元素，并返回合并后链表
* 注意：LA,LB需有序
* @param[in] LA,LB
* @param[out] 合并后链表LC
*/
friend LinkList<T>* Merge(LinkList<T> &LA, LinkList<T>&LB)
{
	LinkList<T> *LC = new LinkList<T>;
	Node<T> *p1 = LA.pHead->next;
	Node<T> *p2 = LB.pHead->next;
	Node<T> *p3 = LC->pHead;
	while (p1 != NULL && p2 != NULL)
	{
		if (p1->data < p2->data)
		{
			p3->next = p1;
			p1 = p1->next;
			p3 = p3->next;
		}
		else
		{
			p3->next = p2;
			p2 = p2->next;
			p3 = p3->next;
		}
	}
	if (p1 != NULL)
		p3->next = p1;
	else
		p3->next = p2;
	delete LA.pHead; LA.pHead = NULL;
	delete LB.pHead; LB.pHead = NULL;
	return LC;
}

重载赋值运算符：
若链表本身为空，使用插值的方法生成链表。若本身不空，可以再次调用归并，是两者进行归并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template<class T>
LinkList<T>& LinkList<T>::operator = (LinkList<T> *L)
{
	
	if (this->pHead->next==NULL)
	{
		Node<T> *p = L->pHead->next;
		while (p != NULL)
		{
			this->Insert(this->ListLength()+1,p->data);
			p = p->next;
		}
		L->~LinkList();
		//因为尝试的是值复制，所以显示调用析构函数删除空间
	}
	else{
		this->Merge(*L);
	}
	 return *this;
}

2.1.10链表的排序

这里选用插入排序法，将链表按照升序排列。

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
/**
* SelectSort()
* 作用:将L链表按升序排列
* @param[in]
* @param[out]
*/
template <class T>
void LinkList<T>::SelectSort()
{
	//选择排序,每次选择未排序部分的最小值交换到前面 
	if (pHead->next == NULL) return; //链表为空  
	if (pHead->next->next == NULL) return; //只有一个节点  
	Node<T> *Pre_Sorting = pHead->next; //记录正在排序的点  
	while (Pre_Sorting != NULL)
	{
		Node<T> *pTemp = Pre_Sorting->next; //从pSorting开始往后遍历  
		Node<T> *pMin = Pre_Sorting; //暂存从pSorting开始的最小的点  
		while (pTemp != NULL)
		{
			if (pTemp->data < pMin->data)
				pMin = pTemp;
			pTemp = pTemp->next;
		}
		//进行交换  
		T temp = Pre_Sorting->data;
		Pre_Sorting->data = pMin->data;
		pMin->data = temp;
		//排序下一个点  
		Pre_Sorting = Pre_Sorting->next;
	}
}

至此，链表功能基本说明完毕。下面进入测试阶段。

三、测试

3.1有参构造函数测试

部分代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
	int a[10] = {8,6,2,4,5,1,3,9,7,10};
	LinkList<int> L1(a, 10, "head");
	LinkList<int> L2(a, 10, "sorted");
	LinkList<int> L3(a, 10, "tail");
	cout << endl << "链表L1(头插)为：" << endl;
	L1.PrintListLink();
	cout << endl << "链表L2（顺序插）为：" << endl;
	L2.PrintListLink();
	cout << endl << "链表L3（尾插）为：" << endl;
	L3.PrintListLink();
    ………………
}

测试截图：
无

3.2返回链表长度测试

部分代码：

1
2
3
4
5
6
int a[10] = { 8, 6, 2, 4, 5, 1, 3, 9, 7, 10 };
LinkList<int> L(a, 10, "head");
cout << endl << "链表L为：" << endl;
L.PrintListLink();
cout << "返回链表长度：" << endl 
	<< L.ListLength()<<endl;

测试截图：
此处输入图片的描述

3.3按位返回元素引用测试

部分代码：

1
2
3
4
5
6
   int a[10] = { 8, 6, 2, 4, 5, 1, 3, 9, 7, 10 };
LinkList<int> L(a, 10, "head");
cout << endl << "链表L为：" << endl;
L.PrintListLink();
cout << "返回位序5的元素值：" << endl 
	<< L.Get(5)<< endl;

测试截图：
此处输入图片的描述

3.4 按值找位测试

部分代码：

1
2
3
4
5
6
7
int a[10] = { 8, 6, 2, 4, 5, 1, 3, 9, 7, 10 };
LinkList<int> L(a, 10, "head");
cout << endl << "链表L为：" << endl;
L.PrintListLink();
int A = 7;
cout << "返回元素A(7)的位序值：" << endl
	<< L.Locate(A) << endl;

测试截图：
此处输入图片的描述

3.5按位插值测试

部分代码：

1
2
3
4
5
6
7
8
   int a[10] = { 8, 6, 2, 4, 5, 1, 3, 9, 7, 10 };
LinkList<int> L(a, 10, "head");
cout << endl << "链表L为：" << endl;
L.PrintListLink();
cout<< "按位(4)插值(11)：" << endl;
L.Insert(4, 11);	
L.PrintListLink();
cout << endl;

测试截图：
此处输入图片的描述

3.6按位删值测试

部分代码：

1
2
3
4
5
6
7
   int a[10] = { 8, 6, 2, 4, 5, 1, 3, 9, 7, 10 };
LinkList<int> L(a, 10, "head");
cout << endl << "链表L为：" << endl;
L.PrintListLink();
cout << "按位(1)删值：" << endl;
L.Delete(1);
L.PrintListLink();

测试截图：
此处输入图片的描述

3.7逆序链表测试

部分代码：

1
2
3
4
5
6
7
int a[10] = { 8, 6, 2, 4, 5, 1, 3, 9, 7, 10 };
LinkList<int> L(a, 10, "head");
cout << endl << "链表L为：" << endl;
L.PrintListLink();
cout<< "逆序链表：" << endl;
L.Invert();
L.PrintListLink();

测试截图：
此处输入图片的描述

3.8 归并测试

部分代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
cout <<  "归并链表(成员函数)：" << endl;
int b[6] = { 1, 3, 5, 7, 9, 11 };
int c[6] = {2,4,6,8,10,12};
LinkList<int> LB(b, 6, "tail");
LinkList<int> LC(c, 6, "tail");
cout << endl << "链表LB为：" << endl;
LB.PrintListLink();
cout << endl << "链表LC为：" << endl;
LC.PrintListLink();
LB.Merge(LC);
cout << endl << "归并后的链表LB为：" << endl;
LB.PrintListLink(); 
cout << endl;

测试截图：
此处输入图片的描述

3.9有返回值归并友元函数测试

部分代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
cout <<  "归并链表(有返回值函数)：" << endl;
int b[6] = { 1, 3, 5, 7, 9, 11 };
int c[6] = {2,4,6,8,10,12};
LinkList<int> LB(b, 6, "tail");
LinkList<int> LC(c, 6, "tail");
cout << endl << "链表LB为：" << endl;
LB.PrintListLink();
cout << endl << "链表LC为：" << endl;
LC.PrintListLink();
LinkList<int> L;
cout << endl;
cout << endl << "合并后的L链表：" << endl;
L = Merge(LB, LC);
L.PrintListLink();
cout << endl;

测试截图：
此处输入图片的描述

3.10 无返回值归并链表测试

部分代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
cout <<  "归并链表(无返回值函数)：" << endl;
int b[6] = { 1, 3, 5, 7, 9, 11 };
int c[6] = {2,4,6,8,10,12};
LinkList<int> LB(b, 6, "tail");
LinkList<int> LC(c, 6, "tail");
cout << endl << "链表LB为：" << endl;
LB.PrintListLink();
cout << endl << "链表LC为：" << endl;
LC.PrintListLink();
cout << endl;
cout << endl << "合并后的LB链表：" << endl;
Merge_1(LB, LC);
LB.PrintListLink();

测试截图：
此处输入图片的描述

陈实
2015年3月29日