数据结构——线性表.doc

数据结构实验报告

数学与计算机学院

实 验 报 告
（ 2011 / 2012 学年 第 1 学期）

课程名称
数据结构
课程代码
6014279
实验时间
2011
年
11
月
2
日
指导单位
软件工程系
指导教师
周立章

学生姓名
唐九零
年 级
2010级
学 号
312010080611427
专 业
软件工程
实验成绩

实验名称
学生成绩管理系统
指导教师
周立章
实验类型
设计
实验学时
2+10
实验时间

一、 实验目的和要求
（1）掌握线性表的顺序存储结构，在顺序存储结构基础上进行的插入、删除、查找等算法的思想和实现；
（2）掌握线性表的链式存储结构。掌握线性表的链式存储结构的建立。在链表中插入、删除和查找算法的思想和算法实现。
（3）掌握线性表在顺序存储、链式存储结构的基础进行的各种应用。
（4）掌握链表的定义和基础知识以及链表的存储和链式存储结构及其应用。
（5）掌握队列的基础知识，循环顺序队列、链队列及其应用。
（6）会用结构体正确描述每一条学生记录的信息，掌握链表结构存储所处理的数据。
（7）设计友好的人机交互菜单，通过相应的流程控制语句的正确使用，使得在主函数中体现对各功能模块的调用，从而实现一个完整的小型管理系统。
要求：课内实验学时2学时，课后学时要求为10学时。
二、实验环境(实验设备)
硬件: 微型计算机P4
软件: Windows XP+Microsoft Visual C++6.0
三、实验原理及内容
实验题目 利用链式存储结构存储学生的成绩信息，设计一个学生成绩管理系统，具有以下功能：
（1）定义学生结构体类型struct Student，每个学生包括学号、姓名、3门功课（课程名自己定义）、总分。
（2）建立双向循环链表：输入若干学生的信息（当输入学生的学号为0000时结束，要求自动计算总分），并按输入的顺序建立双向循环链表；
（3）输出学生成绩信息：遍历双向循环链表，输出所有学生的完整信息到屏幕；
（4）查找指定学号的学生信息。如果查找成功，输出所有学生信息，否则输出失败。
（5）插入学生信息：以队列的方式将新学生成绩信息插入到链表中；

（6）删除学生信息：给出学生姓名，删除链表所有相同姓名的学生的信息（即姓名相同的结点）；
（7）修改学生信息：给出学生学号，修改该生的三门课程成绩信息；
（8）按总分排序：在原来的双向循环链基础上按总分降序进行就地排列。即不能增加额外的空间开销；
实验前准备：完成上述(1)-(4)算法，并要求上机验证通过。
实验时完成(5)-(6)。
实验后，完成算法（7），(8) ,并要求上机验证通过。
实验解答：
1) 画出主函数的流程图

图1 流程图

2）数据类型定义
（1）学生成绩信息结构体类型的定义。
struct Student
{
string number;
string name;
string classes[3];
float C;
float Java;
float DataStruct;
float totallscore;
Student *prior,*next;
};
（2）双向链表结点的定义。是否将结点的数据类型定义为学生成绩信息结构体类型？
List::List()
{
head=new Student;
head->prior=head->next=head;
head->classes[0]="C";
head->classes[1]="Java";
head->classes[2]="DataStruct";
}
不将结点的数据类型定义为学生成绩信息结构体类型。

3）为了能够完成链表的各项操作，你给出的测试数据有哪些？主要用于测试哪些方面？
A、输入学生信息测试数据

B、输出学生信息测试数据

C、查找学生信息测试数据

D、插入学生信息此时数据

E、删除指定学号学生信息测试数据

F、修改学生信息测试数据

实 验 报 告
4)你是否在实验前完成了算法（1）-（4）？如果完成了难点在哪儿？。如果没有完成，理由是什么？
实验前我完成了算法（1）-（4）。难点在于双向循环链表的建立和学生信息的输入上。

5）建立双向循环链表，你采用的是后插法还是前插法？写出C++语言代码。
建立双向循环链表时，我采用的是前插法。
void List::Insert()
{
Student *p;
p=new Student;
cin>>p->number;
cin>>p->name;
cin>>p->C;
cin>>p->Java;
cin>>p->DataStruct;
p->totallscore=p->C+p->Java+p->DataStruct;
p->next=head;
p->prior=head->prior;
head->prior->next=p;
head->prior=p;
}
实 验 报 告
6）在遍历双向循环链表时，你是如何判断遍历结束的？如何控制对结点的访问？给出算法的代码。
在遍历双线循环链表时，当指针不等于头结点head时遍历结束。对结点中的数据依次进行访问，访问完后指针指向下一个结点。
while(p!=head)
{
cout<<setw(20)<<p->number<<setw(15)
<<p->name<<setw(10)<<p->C<<setw(10)<<p->Java<<setw(16)
<<p->DataStruct<<setw(6)<<p->totallscore<<endl;
p=p->next;
}

7）在循环双向链表中，有几种方法可以取链表中的首元结点？写出表达式。
在循环双线链表中，有3中可以取链表中的首元结点。
1、 q=head->next;
2、 q=head->prior->next->next;
3、 q=head->next->next->prior;

8）插入算法：当按队列的方式进行插入运算时，新学生信息是插入到什么位置？写出算法。
当按队列方式进行插入运算时，新学生信息插到链表尾部。
void List::Insert()
{
Student *p;
p=new Student;
cin>>p->number;
cin>>p->name;
cin>>p->C;
cin>>p->Java;
cin>>p->DataStruct;
p->totallscore=p->C+p->Java+p->DataStruct;
p->next=head;
p->prior=head->prior;
head->prior->next=p;
head->prior=p;
}

9）如果要求将新学生信息插入到链表中指定的i位置，写出插入算法的代码，并给出时间复杂度。

void List::Insert()
{
Student *p,*q;
q=head->next;
int j=1;
p=new Student;
cin>>p->number;
cin>>p->name;
cin>>p->C;
cin>>p->Java;
cin>>p->DataStruct;
p->totallscore=p->C+p->Java+p->DataStruct;
while(q!=head)
{
if(j==i)
{
p->next=q;
p->prior=q->prior;
q->prior->next=p;
q->prior=p;
break;
}
q=q->next;
j++;
}
}
时间复杂度 O(n)=n。

10）删除操作：在该删除中，时间开销主要用在什么地方？写出删除算法的代码，给出时间复杂度。它与顺序表中同样的删除上有什么不同？你是如何保证删除了所有姓名相同的结点的？
在该删除中，时间开销主要用在遍历链表查找学生上面。O(n)=n
void List::Delete()
{
string nam;
Student *p,*q;
p=head->next;
cin>>nam;
while(p!=head)
{
if(p->name==nam)
{
q=p->next;
p->prior->next=p->next;
p->next->prior=p->prior;
delete(p);
p=q;
}
else
p=p->next;
}
}
它与顺序表中同样的删除上它更简单，而顺序表却要移动元素。为了保证所有的同名学生，将指针遍历链表；在删除时，用指针记录下要删除结点的下一个结点。

11）写出修改学生成绩的代码。
void List::Alter()
{
Student *p;
string num,num1;
p=head->next;
cin>>num;
while(p!=head)
{
if(p->number==num)
{
cout<<setw(20)<<p->number<<setw(15)
<<p->name<<setw(10)<<p->C<<setw(10)<<p->Java<<setw(16)
<<p->DataStruct<<setw(6)<<p->totallscore<<endl;
while(1)
{
cin>>p->C;
break;
}
}
p=p->next;
}

12）按总分排序时，你是否增加了空间？写出该算法的代码。
按总分排序时，我增加了空间。
void List::ScoreSort()
{
Student *p,*q;
Student *Maxnum;
string num;
string nam;
float C;
float J;
float D;
float t;
p=head->next;
while(p!=head)
{
q=p->next;
Maxnum=p;
while(q!=head)
{
if((Maxnum->totallscore)<(q->totallscore))
Maxnum=q;
q=q->next;
}
if(Maxnum!=p)
{
num=Maxnum->number;
nam=Maxnum->name;
C=Maxnum->C;
J=Maxnum->Java;
D=Maxnum->DataStruct;
t=Maxnum->totallscore;
Maxnum->number=p->number;
Maxnum->name=p->name;
Maxnum->C=p->C;
Maxnum->Java=p->Java;
Maxnum->DataStruct=p->DataStruct;
Maxnum->totallscore=p->totallscore;
p->number=num;
p->name=nam;
p->C=C;
p->Java=J;
p->DataStruct=J;
p->totallscore=t;
}
p=p->next;
}
}

实 验 报 告
四、实验小结（包括问题和解决方法、心得体会、意见与建议等）
1．在使用链表存储学生信息进行编程时，你所遇到的主要问题是什么，如何解决的？
我遇到的主要问题是无法将信息正确的加入链表中。通过向同学询问，成功地解决了这个问题。

2．链栈的进栈操作需什么条件？栈操作的特点是什么？
链栈的进栈操作需栈顶指针，栈操作的特点是后进先出。

3．队列操作的特点是什么？如果Q表示是循环顺序队列，则表示Q为空的条件和满的条件是什么？
队列操作的特点是先进先出。如果Q表示是循环顺序队列，则表示
Q为空的条件为rear=front;Q为满的条件是（rear+1）/max=front;

4．在删除算法中，你准备的测试数据是什么？是否都按算法姓名相同的都删除？
删除钱所有学生信息

删除过程

删除后所有学生信息

结果都按算法姓名相同的都删除

5.对学生的成绩信息进行相关操作，你认为使用链式存储结构合理吗？说明理由。
对学生的成绩信息进行相关操作，我认为使用链式存储结构合理。
因为对学生的成绩信息进行相关操作时，要添加和删除学生信息，用链式结构比较方便。

五、指导教师评语

成 绩

批阅人

日 期

11