北京理工大学数据结构实验报告一.docx

北京理工大学数据结构实验报告一.docx

《北京理工大学数据结构实验报告一.docx》由会员分享，可在线阅读，更多相关《北京理工大学数据结构实验报告一.docx（21页珍藏版）》请在冰点文库上搜索。

北京理工大学数据结构实验报告一

实验报告一：

线性表

班级：

05111451姓名：

任子龙学号：

1120140167

1、需求分析

1.学生成绩利用单链表存储，方便随时插入和删除学生成绩记录，实现动态管理，一个学生的成绩信息作为一个结点。

2.程序以用户和计算机对话的方式执行，即在计算机终端上显示“提示信息”之后，用户在键盘上输入规定的数据，回车后，运算结果显示在其后。

3.程序执行的命令包括：

1）获取学生成绩；2）添加学生成绩；3）修改学生成绩；4）删除学生成绩；5）结束。

4.在输入不当时，输出相应的错误提示信息。

5.测试数据：

Student1：

“11120140001张三9090959990”；

Student2：

“21120140002李四9898989898”。

（1）查询：

输入：

1

输出：

序号：

1

学号：

1120140001

姓名：

张三

该学生五门课的成绩：

9090959990

（2）修改

输入：

1120140001/3/王二

输出：

已修改该学生成绩信息！

（3）删除：

输入：

1

输出：

已删除该学生成绩信息！

（4）非法输入：

如查询时

输入：

3

输出：

查无此人，请核实信息！

2、概要设计

为实现上述功能，以链表表示学生成绩。

所以抽象数据类型为单向链表。

1.

ADTLinklist{

数据对象：

D={ai|aiϵElemtype,i=1,2,...,n,n≧0}

数据关系：

R={|ai-1,aiϵD,ai-1

基本操作：

Input（&L）

操作结果：

构造一个带头结点的空链表L。

Show（L,id）

初始条件：

链表L存在。

操作结果：

若L存在学号为id的元素，则输出该元素；否则，返回错误信息。

Modify（&L，i）

初始条件：

链表L存在。

操作结果：

若1≤i≤n，则修改L的第i个元素。

Insert（&L,i，e）

初始条件：

链表L存在。

操作结果：

若1≤i≤n，则在L的第i个元素后面插入新元素e。

Deletenode（&L,i）

初始条件：

链表L存在。

操作结果：

若1≤i≤n，则删除L的第i个元素。

}ADTLinklist

2.本程序包括两个模块：

1）主程序模块：

voidmain（）//主函数//

{

while（flag）//标记//

{

输出操作提示信息；

scanf（"%d",&a）;

switch（a）//判断语句，根据CASE的数字依次选择函数

{

选择命令；

执行命令；

}

}

}

2.链表单元模块——实现链表的抽样数据类型。

模块的调用关系如下：

主程序模块→链表单元模块

三、详细设计

1.结点类型

typedefstructstudent{

intnum;

intstudentnum;

charname[15];

intscore[5];

structstudent*next;

}student;//结点类型

2.有序链表的基本操作设置如下：

voidinput（&L）；

//构造一个带结点的有序链表

voidShow（L,id）;

//若L存在学号为id的元素，则输出该元素；否则，返回错误信息。

voidModify（&L，i）;

//若1≤i≤n，则修改L的第i个元素。

voidInsert（&L,i，e）;

//若1≤i≤n，则在L的第i个元素后面插入新元素e。

voidDeletenode（&L,i）;

//若1≤i≤n，则删除L的第i个元素。

其中，部分操作的伪码算法如下：

voidinput（）{//输入学生成绩信息//

inti=0,j=0,n;

p=（student*）malloc（sizeof（student））;//申请空间，创建带头结点的空指针

p->next=NULL;

head=p;

printf（"\t输入需要录入信息的学生人数\n"）;

scanf（"%d",&n）;

for（i=0;i

{q=（student*）malloc（sizeof（student））;

q->num=i+1;

printf（"输入序号为%d的学生学号：

",i+1）;scanf（"%d",&q->studentnum）;

printf（"输入序号为%d的学生姓名：

",i+1）;scanf（"%s",&q->name）;

for（j=0;j<5;j++）//该循环语句用来输入一个学生的五门成绩//

{

printf（"输入第%d个学生第%d门课的成绩:

",i+1,j+1）;scanf（"%d",&q->score[j]）;

}q->next=NULL;p->next=q;p=q;

printf（"\n"）;

}

}//input

voidshow（）//输出函数，输出指定学号的学生信息//

{intstdnum;//需要查询的学生学号

intflag=1,j;

printf（"\t请输入需要查询的学生学号：

\n"）;

scanf（"%d",&stdnum）;

p=head;

if（！

p）{printf（"提示：

系统尚未录入任何信息！

\n"）;exit（0）;

}

p=head->next;

while（flag&&p）

{

if（p->studentnum==stdnum）

{

printf（"学生的成绩信息如下:

\n"）;

printf（"序号：

%d\n",p->num）;

printf（"学号：

%d\n",p->studentnum）;

printf（"姓名：

%s\n",p->name）;

printf（"该学生五门课的成绩：

"）;

for（j=0;j<5;j++）

printf（"%d",p->score[j]）;

printf（"\n"）;

flag=0;

}

p=p->next;

}

if（flag）printf（"查无此人，请核实信息\n"）;

}//show

voiddeletenode（）//删除指定序号学生信息//

{intnumber,j;

student*r;

p=head->next;

printf（"请输入需要删除信息的学生序号：

\n"）;

scanf（"%d",&number）;

if（number==1）

{

head->next=head->next->next;q=head->next;

}

else

{

while（p!

=NULL）

{

if（p->num==number-1）

{r=p->next;

p->next=p->next->next;

q=p->next;

free（r）;

break;

}

}

}

while（q）{q->num--;q=q->next;}

printf（"已删除该学生成绩信息！

\n"）;

}//deletenode

3.main函数的伪码算法

voidmain（）//主函数//

{inta,flag=1;

while（flag==1）//标记//

{printf（"\n****************************************************************\n"）;

printf（"\t请输入指令码：

\n\t1--录入学生信息\n\t2--查询学生信息\n\t3--修改学生信息\n"）;

printf（"\t4--插入学生信息\n\t5--删除学生信息\n\t0--退出成绩管理系统\n"）;

printf（"****************************************************************\n\n"）;

scanf（"%d",&a）;

switch（a）//判断语句，根据CASE的数字依次选择函数

{

case1:

input（）;break;

case2:

show（）;break;

case3:

modify（）;break;

case4:

insert（）;break;

case5:

deletenode（）;break;

case0:

printf（"系统提示：

已退出！

\n"）;

flag=0;break;//FLAG=0，结束运算/default:

printf（"请输入正确的指令码！

"）

}

}

}//main

四.调试分析

1.由于各个功能都是链表的基本操作，所以函数编写起来并不难。

2.刚开始忽略了switch语句每一个case语句都应该有break，今后应该注意。

3.本程序编写过程大多时间花在增强程序的健壮性上，对于非法的输入给予提示信息，来让使用者更好更快地了解其用法。

如，在没有录入信息的情况下，执行其它功能会提示“系统尚未录入任何信息”，如果序号或学号输入错误、指令码输入错误，都会有相应的错误提示。

4.算法的时空分析

由于链表的特点，各操作的时间复杂度比较合理。

input函数要读入n个元素，时间复杂度为O（n）。

其它四个函数都要利用循环，之后再对某一个结点操作，所以它们的时间复杂度也都为O（n）。

五、测试结果

1.在没有输入学生信息之前，如果直接执行命令“2”、“3”、“4”或“5”，会弹出错误提示信息，具体如下：

2.执行“获取”功能

这里采取手动输入的方式，按提示逐步录入：

3.执行“查询”功能

输入指令码--2

3.执行“修改”功能

如把学号为1120140167的同学的第一门课成绩改为99；

之后，对同一同学再进行一次成绩查询，发现成绩已修改：

4.执行“插入”功能

如插入序号为2的学生“张三”，之后再查询该学生成绩，结果如下面两张图所示：

5.执行“删除”功能

再把“张三”同学（序号为2）的信息删除，提示“已删除该学生成绩信息！

”；然后查询，结果“查无此人，请核实信息”，说明删除成功。

6、附录

#include

#include

/*runthisprogramusingtheconsolepauseroraddyourowngetch,system（"pause"）orinputloop*/

typedefstructstudent{

intnum;

intstudentnum;

charname[15];

intscore[5];

structstudent*next;

}student;

student*head,*p,*q;

voidinput（）{//输入学生成绩信息//

inti=0,j=0,n;

p=（student*）malloc（sizeof（student））;

p->next=NULL;

head=p;

printf（"\t输入需要录入信息的学生人数\n"）;

scanf（"%d",&n）;

for（i=0;i

{q=（student*）malloc（sizeof（student））;

q->num=i+1;

printf（"输入序号为%d的学生学号：

",i+1）;scanf（"%d",&q->studentnum）;

printf（"输入序号为%d的学生姓名：

",i+1）;scanf（"%s",&q->name）;

for（j=0;j<5;j++）//该循环语句用来输入一个学生的五门成绩//

{

printf（"输入第%d个学生第%d门课的成绩:

",i+1,j+1）;scanf（"%d",&q->score[j]）;

}q->next=NULL;p->next=q;p=q;

printf（"\n"）;

}

}

voidshow（）//输出函数，输出指定学号的学生信息//

{intstdnum;

intflag=1,j;

printf（"\t请输入需要查询的学生学号：

\n"）;

scanf（"%d",&stdnum）;

p=head;

if（p==NULL）{printf（"提示：

系统尚未录入任何信息！

\n"）;exit（0）;

}

p=head->next;

while（flag&&p!

=NULL）

{

if（p->studentnum==stdnum）

{

printf（"学生的成绩信息如下:

\n"）;

printf（"序号：

%d\n",p->num）;

printf（"学号：

%d\n",p->studentnum）;

printf（"姓名：

%s\n",p->name）;

printf（"该学生五门课的成绩：

"）;

for（j=0;j<5;j++）

printf（"%d",p->score[j]）;

printf（"\n"）;

flag=0;

}

p=p->next;

}

if（flag）printf（"查无此人，请核实信息\n"）;

}

voidmodify（）//修改指定学号学生信息//

{

intstdnum;

intflag=1,j,t;

printf（"\t请输入需要修改信息的学生学号：

\n"）;

scanf（"%d",&stdnum）;

p=head;

if（p==NULL）

{printf（"提示：

尚未录入任何信息\n"）;exit（0）;

}

p=head->next;

while（flag&&p!

=NULL）

{

if（p->studentnum==stdnum）

{printf（"\t请选择需要修改的学生信息：

\n"）;

printf（"\t1--序号\n\t2--学号\n\t3--姓名\n\t4--第一门课成绩\n\t5--第二门课成绩\n"）;

printf（"\t6--第三门课成绩\n\t7--第四门课成绩\n\t8--第五门课成绩\n\t9--取消\n"）;

scanf（"%d",&t）;

switch（t）

{case1:

printf（"输入该学生的序号：

"）;scanf（"%d",&p->num）;break;

case2:

printf（"输入该学生的学号：

"）;scanf（"%d",&p->studentnum）;break;

case3:

printf（"输入该学生的姓名：

"）;scanf（"%s",&p->name）;break;

case4:

printf（"输入该学生的第一门课成绩：

"）;scanf（"%d",&p->score[0]）;break;

case5:

printf（"输入该学生的第二门课成绩：

"）;scanf（"%d",&p->score[1]）;break;

case6:

printf（"输入该学生的第三门课成绩：

"）;scanf（"%d",&p->score[2]）;break;

case7:

printf（"输入该学生的第四门课成绩：

"）;scanf（"%d",&p->score[3]）;break;

case8:

printf（"输入该学生的第五门课成绩：

"）;scanf（"%d",&p->score[4]）;break;

case9:

printf（"已取消“修改”操作！

\n"）;break;

default:

printf（"请输入正确的指令码！

\n"）;break;

}

flag=0;

}

p=p->next;

}

if（flag）printf（"查无此人，请核实信息！

\n"）;

}

voidinsert（）//指定序号后面添加学生信息//

{intnumber,j;

student*pp;

p=head->next;

printf（"请输入需要添加信息的学生序号：

\n"）;

scanf（"%d",&number）;

while（p!

=NULL）

{

if（p->num==number-1）

{pp=（student*）malloc（sizeof（student））;

pp->next=p->next;p->next=pp;

printf（"\t请输入该学生信息：

\n"）;

printf（"输入该学生的序号：

"）;scanf（"%d",&pp->num）;

printf（"输入该学生的学号：

"）;scanf（"%d",&pp->studentnum）;

printf（"输入该学生的姓名：

"）;scanf（"%s",&pp->name）;

for（j=0;j<5;j++）//该循环语句用来输入一个学生的五门成绩//

{

printf（"输入该学生第%d门课的成绩:

",j+1）;scanf（"%d",&pp->score[j]）;

}

while（pp->next）

{pp->next->num++;pp=pp->next;

}

break;

}

}

}

voiddeletenode（）//删除指定序号学生信息//

{intnumber;

intj;

student*r;

p=head->next;

printf（"请输入需要删除信息的学生序号：

\n"）;

scanf（"%d",&number）;

if（number==1）

{

head->next=head->next->next;q=head->next;

}

else

{

while（p!

=NULL）

{

if（p->num==number-1）

{r=p->next;

p->next=p->next->next;

q=p->next;

free（r）;

break;

}

}

}

while（q）{q->num--;q=q->next;}

printf（"已删除该学生成绩信息！

\n"）;

}

voidmain（）//主函数//

{inta,flag=1;

while（flag==1）//标记//

{

printf（"\n****************************************************************\n"）;

printf（"\t请输入指令码：

\n\t1--录入学生信息\n\t2--查询学生信息\n\t3--修改学生信息\n"）;

printf（"\t4--插入学生信息\n\t5--删除学生信息\n\t0--退出成绩管理系统\n"）;

printf（"****************************************************************\n\n"）;

scanf（"%d",&a）;

switch（a）//判断语句，根据CASE的数字依次选择函数//

{

case1:

input（）;break;

case2:

show（）;break;

case3:

modify（）;break;

case4:

insert（）;break;

case5:

deletenode（）;break;

case0:

printf（"系统提示：

已退出！

\n"）;

flag=0;break;//FLAG=0，结束运算//

default:

printf（"请输入正确的指令码！

"）;

}

}

}