数据结构C语言课程设计任务书

数据结构课程设计报告

题目一、同学管理系统的设计与实现

一•采纳挨次表结构实现

题目二、图的算法实现

―-采纳邻接表和邻接矩阵结构实现

班级：—计算机101

姓名：—刘文辉

指导老师：—董跃华

成绩：_____________________________

2月理J大学信息工程学院

2012年06月18日

目录

1需求分析...................................................................3

1.1目的....................................................................3

1.2功能....................................................................3

2具体设计..................................................................3

2.1数据类型...............................................................4

2.2总体功能流程图..........................................................4

2.3伪码算法...............................................................5

3调试分析...................................................................14

3.1遇到的问题..............................................................14

3.2算法的时空分析.........................................................14

3.3改进设想................................................................14

3.4阅历体会................................................................14

4测试结果...................................................................15

5参考文献错误!未定义书签。

1、需求分析

1.1>目的

设计并实现一个同学管理系统，即定义一个包含同学信息(学号，姓名，成果)的的挨

次表，可以不考虑重名的状况

①娴熟查找和排序的数据结构算法

②娴熟把握数据结构

③复习C语言的各个学问点

1.2、功能

(1)依据指定同学个数，逐个输入同学信息；

(2)逐个显示同学表中全部同学的相关信息；

(3)给定一个同学信息，插入到表中指定的位置；

(4)删除指定位置的同学纪录；

(5)统计表中同学个数；

(6)采用直接插入排序或者折半插入排序依据姓名进行排序；

(7)采用快速排序依据学号进行排序；

(8)依据姓名进行折半查找，要求使用递归算法实现，胜利返回此同学的学号和成果；

(9)依据学号进行折半查找，要求使用非递归算法实现，胜利返回此同学的姓名和成果。

2、具体设计

2.1、数据类型

1、本次程序采纳挨次存储结构，采用结构体数组的优点进行设计。

ADTList{

数据对象：D={ai|aiGElemset,i=l,2,.......n,n>=0}

数据关系:R1={<a(i-1),a(i)>|a(i-1),a(i)GD,i=2,...........n)

基本操作：Last_locate()

操作结果：得到最终一个元素的位置

基本操作：Stu_Insert()

操作结果：同学信息的插入

基本操作：Stu_Insert_appoint()

操作结果：同学信息插入到指定位置

基本操作：Stu_Delete_appoint()

操作结果：删除藁位置上的同学信息

基本操作：Stu_OutAll()

操作结果：同学信息的输出

基本操作：Stu_Count()

操作结果：同学个数的统计

基本操作：InsertSort。

操作结果：按姓名直接排序

基本操作：Stu_Partition(intlow,inthigh)

操作结果：按学号快速排序

基本操作：Stu_Search_Bin()

操柞结果：非递归折半查找

基本操作：DG_Stu_Search_Bin(charkey[10],intlow,inthigh)

操作结果：递归折半查找

}ADTList

2.2、总体功能流程图

1、功能模块

2、主界面流程图

2.3、伪码算法

1、插入操作的伪代码及流程图

intStu」nsert(){

scanf(,,%d'\&n);

fbr(i=O;i<n;i++)

{scanf(',%d,,,&stu[i].number);

scanf(%sn,&stu[i].name);

scanf("%dn,&stu[i].score);

return1;

2、插入同学信息到指定位置的伪代码及流程图

intStu_Insert_appoint()

scanf(H%d",&j);//j为插入的位置

for(i=Last」ocate();iv=j;i--)〃进行元素后移操作

tu[i+l].numbei-stu[i].number;

stu[i+1].name[15]=stu[i].name[15];

stu[i+1].score=stu[i].score;

scanf(n%dn,&stu[j].number);

scanf(n%sn,&stu[j].name);

scanf("％d\&stu「j].score);

输入J

StufHll-stufi]

输入number、

name、score

v

结束

3、删除指定位置的同学信息的伪代码及流程图

intStu_Delete_appoint(){

scanf(”％d”,&j);

free(stu[j])

for(i=j+l；i<=Last_locate();i++)

stu[i-l]=stu[i];

retum1;

Stu[M]-stu[i]

4、同学信息的全部结果输出的伪代码及流程图

intStu_OutAll()

inti=0;

while(stu[i].number)

printf("%d\t\t",stu[i].number);

printf("%s\t\tn,stu[i].name);

printf(',%d\t\t\nn,stu[i].score);

i++;

return1;

5、同学数量统计的伪代码及流程图

intStu_Count()

(

inti=0;

while(stufi].number)

(

i++；

)

printf("同学总人数:\t");

printf("%d",i);

return1;

6、快速排序的伪代码及流程图

intScore_Partition()

(

Privotkey=stuflow].key;

While(low<high)

(

While(low<high&&stu[high].key>=privotkey)-high;

Stuflow]<-->Stu[high]

While(low<high&&Stu[low].key<=privotkey)++low

Stuflow]<-->Stufhigh]

returnlow;

Privotkey-

yuflowl.ke

Low<high

ow<high&&stu[hi

h].key>-privotkev

5(u[low]<.

>stu[highl

z

xzLow<high&&stu[hi

hl.key<-privockev

Stu[low]<-

>stu[highl

结束

7、直接插入排序伪代码及流程图

VoidInsertSort()

(

For(i=2;i<=LastJocate();++i)

(

If(LT(stu[i].key,stu.[i-1].key))

(

Stu[0]=stu[i]

Stu[i]=stu[i-1]

For(j=i-2;LT(stu[0].key,stu[j].key);-j)

Stu[j+l]=stu[j];

Stu[j+l]=stu[O]

}

8、折半查找非递归伪代码及流程图

intSearch_Bin(SSTableST,intkey){

intlow,high,mid;

low=1;high=ST.length;

while(low<=high){

mid=(low+high)/2;

if(key==ST.elem[mid].key)returnmid;

elseif(key<ST.elem[mid].key)high=mid-1;

elselow=mid+1;

return0;

)

9、折半查找递归伪代码及流程图

intDGSearch_Bin(SSTableST,intlowjnthigh){

intIo,hig,mi;

low=1;hig=ST.Iength;

mid=(Io+hig)/2;

if(ST.elem[mi].key==key)returnmid;

if(ST.elem[mi].key>key)returnD(ST,key,lo,mi-1);

if(ST.elem[mi].key<key)returnD(ST,key,mid+1,high);

return0;

3、调试设计

3.1、遇到的问题

几乎没什么大问题

3.2、算法的时空分析

T(n)=O(n2)

3.3、改进设想

在进入某个功能模块时，或者某个功能的某个步骤时，可以允许消失输入错

误，因此，要实现进入某个步骤时实现撤销操作…

3.4、阅历体会

由于第一次写这么简单的程序，开头有点无从下手，在选择合适的数据结构

的时候不知道怎么去选，只能一个一个的去试，最终从结合了c语言的结构体

和程序需要用到的算法中渐渐摸索到了合适的数据结构，写程序时会消失好多小

的语法问题或者规律问题，一点点规律问题就会让人抓狂。但最终还是静下心来

梳理心情，渐渐的找到了问题。开头的时候没有好好理解折半插入排序。便把第

o个位置也存了信息。导致哨兵没地方放。然后又全部修改了。或许哨兵不肯定

要放在第0个位置。但开头遇到的这个问题时，脑子里就只有一个想法，就是全

部把信息结构修改一遍,虽然这看起来不是个好方法，但对于这种小程序来说，

还是比较简单修改。总体来说，收获很大。。。。

4、测试结果

欢迎使用学生信息管理系统

田8系统功能菜单XXXXXXXXXXXXXXXX.X

输

息

生

入

<1>趁1i

一

息

生

式

<2>普^

一

位置

1喜

<3>生t

m定

心

<4>的

显

定M

记录

父

生

w置

-T馨-

<5>人

千

理

排序

入

6半

<>生

o排

学

红

进

<7>速

半查

序

恁

涯

归

回

霞

名

<8>递

折半

学

普

递

仃

进

号

9找

<>非

王

面

<0>界

作者：刘文辉

请选择您需要的菜单项:

4.2查询同学信息

生

学生学号姓名学生分数

及辉

201000199

何

201000298

。

2010003一97

4.3添加同学信息到指定位置

请选择您需要的菜单项;

的