实验二 线性表综合实验（循环链表）

一．实验目的

        巩固线性表的数据结构的存储方法和相关操作，学会针对具体应用，使用线性表的相关知识来解决具体问题。

二.  实验内容

1.建立一个由n个学生成绩的顺序表，n的大小由自己确定，每一个学生的成绩信息由自己确定，实现数据的对表进行插入、删除、查找等操作。分别输出结果。

循环链表 源代码

#include <iostream>
using namespace std;

template <class DataType>
struct Node
{
	DataType data;
	Node<DataType> *next;
};

template <class DataType>
class CircleLinkList
{
public:
	CircleLinkList();
	CircleLinkList(DataType a[], int n);
	~CircleLinkList();
	int Length();
	DataType Get(int i);
	int Locate(DataType x);
	void Insert(DataType x, int i);
	DataType Delete(int i);
	void PrintList();

private:
	Node<DataType> * first;  // 定义头指针
	int length;

};

template <class DataType>
void CircleLinkList<DataType> ::PrintList()
{
	Node<DataType>*p;
	p = first->next;  //工作指针P初始化
	cout << "[";
	for (int i = 0; i < length; i++)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << "]" << endl;
}

template <class DataType>
int CircleLinkList<DataType>::Length()
{
	return length;
}
template <class DataType>
DataType CircleLinkList<DataType>::Get(int i)
{
	Node<DataType>*p = NULL;
	p = first->next;
	int count = 1;
	while (p != NULL&&count<i)
	{
		p = p->next;
		count++;
	}
	if (p == first) throw"输入位置异常";
	else
	{
		return p->data;
	}
}

template <class DataType>
int CircleLinkList<DataType>::Locate(DataType x)
{
	Node<DataType>*p = NULL;
	p = first->next;
	int count = 1;
	while (p != first)
	{
		if (p->data == x)
			return count;
		p = p->next;
		count++;
	}

	return 0;
}

template <class DataType>
void CircleLinkList<DataType>::Insert(DataType x, int i)
{
	Node<DataType>*p, *s;
	p = first->next;
	int count = 1;
	while (p != first && count < i-1)
	{
		p = p->next;
		count++;
	}
	if (p == first)throw "插入位置异常";
	else
	{
		s = new Node<DataType>;
		s->data = x;
		s->next = p->next;
		p->next = s;	
		length++;
	}
	
}

template <class DataType>
CircleLinkList <DataType>::CircleLinkList()
{
	first = new Node<DataType>;
	first->next = first;
	length = 0;
}


template <class DataType>
CircleLinkList<DataType>::CircleLinkList(DataType a[], int n) //尾插法
{
	Node<DataType> *s, *last; //s为工作指针 last为尾指针
	first = new Node<DataType>;
	last = first;			//尾指针初始化
	for (int i = 0; i < n; i++)
	{
		s = new Node<DataType>; //为每个数组元素建立一个结点
		s->data = a[i];
		last->next = s;			//将结点s插入到终端结点之后
		last = s;
		length++;
	}
	last->next = first;			//链接建立完毕，将终端结点的指针域指向头指针
}


template <class DataType>
DataType CircleLinkList<DataType>::Delete(int i)
{
	Node<DataType>*p;
	p = first->next;
	int count = 0;
	while (p != first&&count < i - 1)
	{
		p = p->next;
		count++;
	}
	if (p == first || p->next == NULL)
		throw "删除位置异常";
	else
	{
		Node<DataType>*q = NULL; //工作指针初始化
		q = p->next;
		DataType x = q->data;
		p->next = q->next;
		delete q;	
		length--;
		return x;
	
	}
	
}

template <class DataType>
CircleLinkList <DataType>::~CircleLinkList()
{
	Node<DataType>*p = first; //工作结点p初始化
	
	for (int i = 0; i < length; i++)
	{
		p = first;
		first = first->next;
		delete p;
	}
	length = 0;
	cout << "链表已成功删除。" << endl;

}
int main()
{
	int num;
	cout << "请输入学生人数：";
	cin >> num;
	//	int stu[100];  //最大容纳量
	//	for (int i = 0; i < num; i++)
	//	{
	//		cout << "请输入第"<<i+1<<"名学生成绩:";
	//		cin >> stu[i];
	//	}
	int studemo[] = { 50,60,70,80,90 };
	CircleLinkList<int> demo(studemo, num);

	demo.PrintList(); //展示学生成绩
	cout << "--------------------" << endl;
	cout << "查找第三名学生成绩:" << demo.Get(3) << endl;
	cout << "--------------------" << endl;
	cout << "查找成绩为90的学生的位置:" << demo.Locate(90) << endl;
	cout << "--------------------" << endl;
	cout << "在第四与第五之间插入成绩85:" << endl;
	cout << "结果为：";
	demo.Insert(85, 5);
	demo.PrintList();
	cout << "--------------------" << endl;
	cout << "链表总长为：";
	cout << demo.Length() << endl;
	cout << "--------------------" << endl;
	cout << "删除第6位成绩：";
	cout << demo.Delete(5) << endl;
	cout << "结果为：";
	demo.PrintList();
	cout << "--------------------" << endl;
	cout << "链表总长为：";
	cout << demo.Length() << endl;
	demo.PrintList();
	cout << "--------------------" << endl;	
	cout << "析构链表" << endl;
	demo.~CircleLinkList();
	return 0;
}

实验截图：

  

实验总结与个人心得;

循环链表与单链表比较相似，只是循环链表的终端结点指向头结点，使链表从任一结点开始便可以遍历整个链表。进一步增加了链表操作的灵活性。

在从单链表改写为循环链表的过程中，须将终端结点指向头结点，即last->next = first; 但需要重点注意的是， 循环链表中没有明显的尾端，如果采用单链表中的（p！=NULL）作为循环跳出的条件，会导致死循环。

在本次实验中，本人采用两种方式避免死循环。

第一，通过判断用作循环变量的工作指针是否等于某指定指针（如头指针或尾指针），以判定工作指针是否扫描了整个循环链表

p=first->next;

while(p!=first){ p=p->next; }

第二，定义代表表长的变量length，通过for(int i=0;i<length;i++)遍历链表。