数据结构设计报告.docx

数据结构设计报告.docx

《数据结构设计报告.docx》由会员分享，可在线阅读，更多相关《数据结构设计报告.docx（25页珍藏版）》请在冰点文库上搜索。

数据结构设计报告

西安工業大學

数据结构课程设计报告

班级：

081001

姓名：

***

学号：

********

指导教师：

***

完成日期：

2010-12-24

题目1.Joseph环

1.问题描述：

编号是1，2，……，n的n个人按照顺时针方向围坐一圈，每个人持有一个密码（正整数）。

一开始任选一个正整数作为报数上限（开始）值m（m＜n），从第一个人开始沿顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，然后在从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。

设计一个程序来求出出列顺序。

基本要求：

利用单项循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。

输入数据：

建立输入处理输入数据，输入m、n、的初值和每个人的编号，建立单循环链表。

输出形式：

建立一个输出函数，将正确的序列输出。

测试数据：

m的初值为20，n=7,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？

2需求分析:

1．本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即n个人的编号和密码）初始密码和每个人的密码为1～20，人数为1～7，先输入初始密码m，再输入人数n，接下来输入n个正整数，数与数之间用逗号隔开，作为这n个人的密码。

2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示"提示信息"之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。

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

1）构造单向循环链表；2）提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。

4．测试数据

m的初值为20；n=7，7个人的密码依次为：

3，1，7，2，4，8，4，首先m值为6（正确的出列顺序为6，1，4，7，2，3，5）。

3.概要设计

1．单向循环链表的抽象数据类型定义为：

ADTList｛

数据对象：

D=｛ai|ai∈正整数，I=1，2，......，n,n≥0｝

数据关系：

R1=｛<ai-1，ai>|，ai-1，ai∈D,I=1，2，......，n｝

基本操作：

InitList（&L）

操作结果：

构造一个最大长度ms内容为空的有序表L。

ClearList（&L）

初始条件：

线性表L已经存在。

操作结果：

将L重置为空表。

EmptyList（L）

初始条件：

线性表L已经存在。

操作结果：

若L为空表返回TRUE，否则返回FALSE。

ListLength（L）

初始条件：

线性表L已经存在。

操作结果：

返回L中数据元素个数。

GetElem（L,pos,&e）

初始条件：

线性表L已经存在，1≤i≤ListLength（L）。

操作结果：

用e返回L中第i个数据元素的值。

LocateElem（L,e）

初始条件：

线性表L已经存在。

操作结果：

返回L中第1个与e相同的元素的位序。

若不存在返回0。

ListInsert（L,i,e）

初始条件：

线性表L已经存在。

操作结果：

在L中的第i个元素的位置之前插入新元素e,L的长度加1。

ListDelete（L,pos,e）

初始条件：

线性表L已经存在，1≤i≤ListLength（L）。

操作结果：

删除L的第i个数据元素，并用e返回其值，L的长度减1。

ListTraverse（L）

初始条件：

线性表L已经存在。

操作结果：

依次对L的每个数据元素进行访问。

}ADTSqList

本程序包含以下模块：

（1）主程序模块：

其中又包括建立线性表和模拟约瑟夫环处理两大过程

voidmain（）

{

   初始化；

   输入数据；

   执行功能；

显示结果；

}

（2）线性表模块：

实现线性表的抽象数据类型

（3）元素结构单元模块：

定义线性表每个元素的结构

（2）各功能模块——实现顺序表的各项功能。

各模块的调用关系：

主程序

  ↓

各功能模块

4.详细设计

（1）定义了一个结构体

typedefstructNode

{

intnum;//  表示该元素的编号

intcipher;-----//  表示该元素的顺序位置

structNode*next;

}node,*hu;--------//结点类型，指针类型

（2）设定了init（intn）函数来模拟所输入的N个数以线性循环单链表的形式进入和输出：

init（intn）

{

inti;-----------\设定第i个数

intcipher；--------//定义元素的顺序位置

huL;------------//定义指向下一个元素的指针节点L

if（n>=1）----------//定义循环的输入的条件

{

scanf（"%d",&cipher）;

H=（hu）malloc（sizeof（node））;---------//生成头结点;

H->number=1;

H->cipher=cipher;

H->next=H;

for（i=1;i

{

scanf（"%d",&cipher）;

L=（hu）malloc（sizeof（node））;----------//生成副结点;

L->number=i+1;

L->cipher=cipher;

L->next=H->next;

H->next=L;

H=L;

}

H=H->next;------------//循环单链表的生成;

}

else

printf（"TheN'svaluethatyouinputtedisinvalid!

"）;

}

（3）按照约瑟夫的思想进行程序的循环,使顺序出列并重新排列：

Joseph（intm,huh）

{

inti;//---------定义第i个数

hul;------//定义副节点指针L

l==h;-------//初始化L

i=1;--------//初始化i

while（i!

=m）//-------循环出列的条件

{

i=i+1;

l=h;

h=h->next;

}

printf（"%3d",h->number）-------;//输出第i个满足条件的值

m=h->cipher;//------给m重新赋值为出列的下一个位置

l->next=h->next;

free（h）;--------/释放h节点

h=l->next;

if（h!

=l）

Joseph（m,h）;//---------如果h不等于1则继续调用Joseph（m,h）

else

{

printf（"%3d",h->number）;

free（h）;----------/释放h节点

}

}

（4）主程序利用循环链表来输入和循环输出并用约瑟夫函数来模拟输出过程

main（）

{

intm;---------定义循环的长度

intn;---------所输入的数的总个数

inti;-----------定义第i个查阅的数

clrscr（）;

printf（"PleaseinputthestartingvalueofM（theupperlimitworthofM）:

"）;------//输入M的上限

scanf（"%d",&m）;---//-输入m的值

printf（"Pleaseinputtheman'sfigurewhohaveahandin:

"）;

scanf（"%d",&n）;-----//输入总个数n

printf（"Pleaseinputthecipherfromnumber1tonumber%d:

",n）;-------//输入n个数

init（n）;--------//调用init（n）

printf（"TheorderofDequeueis:

"）;

Joseph（m,H）;

}

5.调试结果

6．调试分析：

a．调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析：

调试时没有运行结果，后来发现没有在主程序里加上getch（）函数，加上后正确。

m的初值（上限值）为20；n=7，7个人的密码依次为：

3，1，7，2，4，8，4，

m值为6结果为：

6，1，4，7，2，3，5。

　b．算法的时空分析：

在init（）中共循环了n次。

在约瑟夫函数中最坏的情况下要n次，所以时间复杂度为0（n）

改进方法：

我认为要使用双向循环链表可以更好的降低事件复杂度，而循环链表就能很好的节省空间。

题目2图遍历的程序设计

一．需求分析

1.本演示程序以邻接多重表为存储结构，实现连通无向图的深度和广度优先遍历。

2．对一个交通网（25个城市）进行，以一个作为起点进行图的两种遍历。

即深度优先遍历和广度优先遍历。

最后输出每种遍历下的结点访问序列和相应生成树的边集。

3.测试数据（附后）。

二．概要设计

1.抽象数据类型图的定义如下：

ADTGraph{

数据对象V：

V是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：

R={VR}

VR={|v,w

V,表示v和w之间存在路径}

基本操作P:

CreatGraph（&G,V,VR）

初始条件:

V是图的顶点集,VR是图中弧的集合.

操作结果:

按V和VR是定义构造图G.

DestroyGraph（&G）

初始条件:

图G存在

操作结果:

销毁图G

LocateVex（G,u）

初始条件:

图G存在,u和G中顶点有相同的特征

操作结果:

若图G中存在顶点u,则返回该顶点在图中的位置;否则返回。

其他信息。

GetVex（G,v）

初始条件:

图G存在,v是G中顶点

操作结果:

返回v的值

FirstAjvex（G,v）

初始条件:

图G存在,v是G中顶点

操作结果:

返回v的第一个邻接顶点,若顶在图中没有邻接顶点,则返回为空。

NextAjvex（G,v,w）

初始条件:

图G存在,v是G中顶点,w是v的邻接顶点

操作结果:

返回v的下一个邻接顶点,若w是v的最后一个邻接顶点,则返回空。

DeleteVexx（&G,v）

初始条件:

图G存在,v是G中顶点

操作结果:

删除顶点v已经其相关的弧

DFSTraverse（G,visit（））

初始条件:

图G存在,visit的顶点的应用函数

操作结果:

对图进行深度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败

BFSTraverse（G,visit（））

初始条件:

图G存在,visit的顶点的应用函数

操作结果:

对图进行广度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败

}ADTGraph

2、设定栈的抽象数据类型：

ADTStack{

数据对象：

D={ai|ai∈CharSet，i=1，2，……，n，n≥0}

数据关系：

R1={|ai-1,ai∈D,i=2，……，n}

基本操作：

InitStack（&S）

操作结果：

构造一个空栈S。

DestroyStack（&S）

初始条件：

栈S已存在。

操作结果：

栈S被销毁。

Push（&S,e）;

初始条件：

栈S已存在。

操作结果：

在栈S的栈顶插入新的栈顶元素e。

Pop（&S,e）;

初始条件：

栈S已存在。

操作结果：

删除S的栈顶元素，并以e返回其值。

StackEmpty（S）

初始条件：

栈S已存在。

操作结果：

若S为空栈，则返回TRUE，否则返回FALSE。

}ADTStack

3、设定队列的抽象数据类型：

ADTQueue{

数据对象:

D={ai|ai属于Elemset,i=1,2….,n,n>=0}

数据关系:

R1={|ai-1,ai属于D,i=1,2,…,n}

约定ai为端为队列头,an为队列尾

基本操作:

InitQueue（&Q）

操作结果:

构造一个空队列Q

DestryoQueue（&Q）

初始条件：

队列Q已存在。

操作结果：

队列Q被销毁，不再存在。

EnQueue（&Q,e）

初始条件:

队列Q已经存在

操作结果:

插入元素e为Q的新的队尾元素

DeQueue（&Q,&E）

初始条件:

Q为非空队列

操作结果:

删除Q的队尾元素,并用e返回其值

QueueEmpty（Q）

初始条件:

队列已经存在

操作结果:

若队列为空,则返回TRUE,否则返回FLASE

}ADTQueue

三．详细设计

1.顶点,边和图类型

#defineMAXQUEUE70/*伫列的最大容量*/

structnode/*图形顶点结构宣告*/

{

intvertex;/*顶点资料*/

structnode*nextnode;/*指下一顶点的指标*/

};

typedefstructnode*graph;/*图形的结构新型态*/

structnodehead[61];/*图形顶点结构数组*/

intvisited[61];/*遍历记录数组*/

intqueue[MAXQUEUE];/*伫列的数组宣告*/

intfront=-1;/*伫列的前端*/

intrear=-1;/*伫列的后端*/

/*2、建立图形*/

voidcreategraph（int*node,intnum）

{

graphnewnode;/*新顶点指标*/

graphptr;

intfrom;/*边线的起点*/

intto;/*边线的终点*/

inti;

for（i=0;i

{

from=node[i*2];/*边线的起点*/

to=node[i*2+1];/*边线的终点*/

/*建立新顶点记忆体*/

newnode=（graph）malloc（sizeof（structnode））;

newnode->vertex=to;/*建立顶点内容*/

newnode->nextnode=NULL;/*设定指标初值*/

ptr=&（head[from]）;/*顶点位置*/

while（ptr->nextnode!

=NULL）/*遍历至链表尾*/

ptr=ptr->nextnode;/*下一个顶点*/

ptr->nextnode=newnode;/*插入结尾*/

}

}

/*3、伫列资料的存入*/

intenqueue（intvalue）

{

if（rear>=MAXQUEUE）/*检查伫列是否全满*/

return-1;/*无法存入*/

rear++;/*后端指标往前移*/

queue[rear]=value;/*存入伫列*/

return0;

}

/*4、伫列资料的取出*/

intdequeue（）

{

if（front==rear）/*检查伫列是否是空*/

return-1;/*无法取出*/

front++;/*前端指标往前移*/

returnqueue[front];/*伫列取出*/

}

/*5、图形的广度优先搜寻法*/

voidbfs（intcurrent）

{

graphptr;/*处理第一个顶点*/

enqueue（current）;/*将顶点存入伫列*/

visited[current]=1;/*记录已遍历过*/

printf（"[%d]",current）;/*印出遍历顶点值*/

while（front!

=rear）/*伫列是否是空的*/

{

current=dequeue（）;/*将顶点从伫列取出*/

ptr=head[current].nextnode;/*顶点位置*/

while（ptr!

=NULL）/*遍历至链表尾*/

{

if（visited[ptr->vertex]==0）/*如过没遍历过*/

{

enqueue（ptr->vertex）;/*递回遍历呼叫*/

visited[ptr->vertex]=1;/*记录已遍历过*/

/*印出遍历顶点值*/

printf（"[%d]",ptr->vertex）;

}

ptr=ptr->nextnode;/*下一个顶点*/

}

}

}

/*6.图形的深度优先搜寻法*/

voiddfs（intcurrent）

{

graphptr;

visited[current]=1;/*记录已遍历过*/

printf（"[%d]",current）;/*印出遍历顶点值*/

ptr=head[current].nextnode;/*顶点位置*/

while（ptr!

=NULL）/*遍历至链表尾*/

{

if（visited[ptr->vertex]==0）/*如过没遍历过*/

dfs（ptr->vertex）;/*递回遍历呼叫*/

ptr=ptr->nextnode;/*下一个顶点*/

}

}

/*7.主程序*/

voidmain（）

{

//clrscr（）;

system（"cls"）;

while

（1）

{

charc,a;

graphptr;

inti;

intnode[60][2]={{1,10},{10,1},/*边线数组*/

{2,10},{10,2},

{2,3},{3,2},

{3,4},{4,3},

{3,12},{12,3},

{4,13},{13,4},

{4,5},{5,4},

{5,6},{6,5},

{5,7},{7,5},

{7,8},{8,7},

{9,10},{10,9},

{10,11},{11,10},

{11,14},{14,11},

{11,12},{12,11},

{12,15},{15,12},

{12,13},{13,12},

{13,16},{16,13},

{14,17},{17,14},

{14,18},{18,14},

{15,19},{19,15},

{16,20},{20,16},

{17,18},{18,17},

{18,23},{23,18},

{18,19},{19,18},

{19,23},{23,19},

{19,24},{24,19},

{19,20},{20,19},

{20,21},{21,20},

{22,23},{23,22},

{24,25},{25,24}

};

system（"cls"）;

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

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

printf（"/*欢迎使用本程序*/\n"）;

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

printf（"/*作者：

巩雪*/\n"）;

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

printf（"/*功能：

有关图的遍历的算法演*/\n"）;

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

printf（"如果有不足之处敬请原谅!

\n\n"）;

printf（"请问你是否要运行以下的程序:

\n\n"）;

printf（"图的深度遍历和广度遍历?

Y/N?

\n"）;

c=getchar（）;

if（c!

='y'&&'Y'）

exit（0）;

system（"cls"）;

printf（"\n\n"）;

printf（"请注意以下为各城市的代码:

\n\n"）;

printf（"1:

乌鲁木齐;2:

呼和浩特;3:

北京;4:

天津;5:

沈阳;\n"）;

printf（"6:

大连;7:

长春;8:

哈尔滨;9:

西宁;10:

兰州;\n"）;

printf（"11:

西安;12:

郑州;13:

徐州;14:

成都;15:

武汉;\n"）;

printf（"16:

上海;17:

昆明;18:

贵阳;19:

株州;20:

南昌;\n"）;

printf（"21:

福州;22:

南宁;23:

柳州;24:

广州;25:

深圳.\n"）;

getchar（）;

for（i=1;i<=25;i++）

{

head[i].vertex=i;/*设定顶点值*/

head[i].nextnode=NULL;/*清除图形指标*/

visited[i]=0;/*设定遍历初值*/

}

//creategraph（node,60）;/*建立图形*/

creategraph（&node[0][0],60）;

printf（"图形的邻接链表内容:

\n"）;

for（i=1;i<=25;i++）

{

if（i%3==0）printf（"\n"）;

printf（"顶点%d=>",head[i].vertex）;/*顶点值*/

ptr=head[i].nextnode;/*顶点位置*/

while（ptr!

=NULL）/*遍历至链表尾*/

{

printf（"%d",ptr->vertex）;/*印出顶点内容*/

ptr=ptr->nextnode;/*下一个顶点*/

}

}

printf（"\n\n"）;

printf（"请选择你需要的操作\n"）;

printf（"1、图形的广度优先遍历请输入:

'g'或'G'\n"）;

printf（"2、图形的深度优先遍历请输入:

's'或'S'\n"）;

c=getchar（）;

switch（c）

{

case'g':

case'G':

printf（"\n请输入你需要的顶点名称:

\n"）;

scanf（"%