欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

实验二 线性表综合实验(双链表)

程序员文章站 2022-06-06 13:39:19
...

一.实验目的

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


.  实验内容

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



双链表 源代码

#include <iostream>
#include<string>
using namespace std;


struct Student
{
	string name;
	int Chinese;
	int Math;
	int English;
	int Sum;

};
ostream& operator << (ostream& os, const Student &ob)
{
	os << ob.name << "\t";
	os << ob.Chinese << "\t";
	os << ob.Math << "\t";
	os << ob.English << "\t";
	os << ob.Sum << "\t";
	return os;
}
template <class DataType>
struct Node
{
	DataType data;
	Node<DataType> *prior, *next;
};

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

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

};

template <class DataType>
void DoubleLink<DataType> ::PrintList()
{
	Node<DataType>*p;
	p = first->next;  //工作指针P初始化
	cout << "-------------------------------------" << endl;
	cout << "姓名" << "\t" << "语文" << "\t" << "数学" << "\t" << "英语" << "\t" << "总分" << "\t" << endl;
	for (int i = 0; i < length; i++)
	{
		cout << p->data << endl;
		p = p->next;
	}
	cout << "-------------------------------------" << endl;

}

template <class DataType>
int DoubleLink<DataType>::Length()
{
	return length;
}
template <class DataType>
DataType DoubleLink<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 DoubleLink<DataType>::Locate(string x)
{
	Node<Student>*p = NULL;
	p = first->next;
	int count = 1;
	while (p != first)
	{
		if (p->data.name == x)
			return count;
		p = p->next;
		count++;
	}

	return 0;
}

template <class DataType>
void DoubleLink<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->prior = p;
		s->next = p->next;
		(p->next)->prior = s;
		p->next = s;
		s->data.Sum = s->data.Chinese + s->data.Math + s->data.English;
		length++;
	}

}

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


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


template <class DataType>
DataType DoubleLink<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
	{			
		DataType x = p->data;
		(p->prior)->next = p->next;
		(p->next)->prior = p->prior;
		delete p;
		length--;
		return x;
	}

}

template <class DataType>
DoubleLink <DataType>::~DoubleLink()
{
	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()
{

	Student stu[100]; //最大容纳量
	int num;
	string TempName;
	cout << "请输入学生人数:";
	cin >> num;

	for (int i = 0; i < num; i++)
	{
		cout << "输入“break”退出输入" << endl;
		cout << "请输入第" << i + 1 << "名学生姓名:";
		cin >> TempName;
		if (TempName == "break")
		{
			num = i;
			break;

		}
		stu[i].name = TempName;
		cout << "请输入第" << i + 1 << "名学生语文成绩:";
		cin >> stu[i].Chinese;
		cout << "请输入第" << i + 1 << "名学生数学成绩:";
		cin >> stu[i].Math;
		cout << "请输入第" << i + 1 << "名学生英语成绩:";
		cin >> stu[i].English;
		stu[i].Sum = stu[i].Chinese + stu[i].Math + stu[i].English;
		cout << "-------------------------------------" << endl;
	}

	DoubleLink<Student> demo(stu, num);	
	demo.PrintList();
	cout << "链表总长为:";
	cout << demo.Length()<<endl;
	cout << "-------------------------------------" << endl;

	cout << "查找第三名学生成绩:" << endl;
	cout << "-------------------------------------" << endl;
	cout << "姓名" << "\t" << "语文" << "\t" << "数学" << "\t" << "英语" << "\t" << "总分" << "\t" << endl;
	cout << demo.Get(3) << endl;
	cout << "-------------------------------------" << endl;

	cout << "查找姓名为“霜降”的位置:" << demo.Locate("霜降") << endl;
	cout << "-------------------------------------" << endl;

	cout << "在第三与第四间插入“秋分”同学的成绩" << endl;
	demo.Insert({ "秋分",95,86,93}, 5);
	demo.PrintList();
	cout << "链表总长为:";
	cout << demo.Length()<<endl;
	cout << "-------------------------------------" << endl;
	cout << "删除第2位同学的成绩" << endl;
	demo.Delete(2);
	demo.PrintList();
	return 0;
}


实验截图:

输入
实验二 线性表综合实验(双链表)          


  输出:

实验二 线性表综合实验(双链表)



实验总结与个人心得;

本实验中的双链表代码,基于上篇循环链表的源代码改写。

双链表与循环链表的区别,只是在于双链表多了一个prior前驱指针,这样可以更快速确定表中任一结点的前驱结点,让链表的操作更灵活。

由于区别不太大,因此改写难度也不大。 只需改写 构造、插入、删除函数即可。(书本上并没有提及构造函数的修改,经过实验后发现,不修改构造函数是无法确定结点间的前驱关系。)

如何改写函数,不再赘述。下面着重写如何实现结构体链表。

在前几次实验中,只能输入与输出数字,数据不够清晰和明确,满足不了实验对 学生成绩的要求。因此在本次实验中,本人在输入与输出方面进行了较大的改写。

定义了一个Student结构体

struct Student
{
string name;
int Chinese;
int Math;
int English;
int Sum;
};

创建结构体数组stu,并对该结构体的进行赋值初始化后,将stu作为参数传入链表构造函数,建立结构体链表

DoubleLink<Student> demo(stu, num);

此时,链表已经创建完毕。但无法进行输出。因为Student是自定义类型,系统无法进行判别。

同时会报错 “错误C2679 二进制“<<”: 没有找到接受“Student”类型的右操作数的运算符(或没有可接受的转换)DoubleLink”

有两种方式可以解决这个问题

第一:重载左移运算符“<<”,使系统能识别并输出 Student类型的数据

ostream& operator << (ostream& os, const Student &ob)
{
os << ob.name << "\t";
os << ob.Chinese << "\t";
os << ob.Math << "\t";
os << ob.English << "\t";
os << ob.Sum << "\t";
return os;
}

第二:在每个函数创建工作指针P时,将指针P指定为<Student>类型。

Node<DataType>*p = NULL; 改写为Node<Student>*p = NULL;

这样就可以分别对结构体内各个变量调用。

使用方法为:p->data.变量名

第二种方式较为灵活,在删除、查找、插入、输出等函数都会用到,推荐使用



提醒:本实验中涉及到字符串string的操作,头文件中必须引入#include<string>,不然会被坑死!

   实验中如果出现语法正常,但程序运行结果错误,推荐使用逐步调试、观察变量的方式,排除逻辑错误。这种方法相对麻烦,也可以在程序增添输出语句,输出变量,判断其变化情况是否满足预期。

   

存在的问题:

本次实验中,涉及许多输入的操作,而没有对输入进行规范,用户的误输入就会导致程序崩溃,大大降低了程序的健壮性。

考虑到本次实验目的是考察对链表操作的熟悉程度,又迫于时间,并未作完善。



相关标签: 链表