实验二 线性表综合实验(双链表)
一.实验目的
巩固线性表的数据结构的存储方法和相关操作,学会针对具体应用,使用线性表的相关知识来解决具体问题。
二. 实验内容
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>,不然会被坑死!
实验中如果出现语法正常,但程序运行结果错误,推荐使用逐步调试、观察变量的方式,排除逻辑错误。这种方法相对麻烦,也可以在程序增添输出语句,输出变量,判断其变化情况是否满足预期。
存在的问题:
本次实验中,涉及许多输入的操作,而没有对输入进行规范,用户的误输入就会导致程序崩溃,大大降低了程序的健壮性。
考虑到本次实验目的是考察对链表操作的熟悉程度,又迫于时间,并未作完善。
上一篇: php的cli简介(转)
下一篇: 线性表之链表(单链表)