数据结构及算法的设计与实现.doc

沈 阳 工 程 学 院

课 程 设 计

设计题目: 数据结构及算法的设计与实现

系 别 信息系 班级
学生姓名 学号
指导教师 职称
起止日期:2009年12月28日起-—至2010年1月8日止

沈 阳 工 程 学 院
计算机组成原理课程设计成绩评定表
系（部）： 信息工程系 班级： 学生姓名：
指 导 教 师 评 审 意 见
评价内容
具 体 要 求
权重
评 分
加权分
调研
论证
能独立查阅文献，收集资料；能制定课程设计方案和日程安排。
0。1
5
4
3
2

工作能力
态度
工作态度认真,遵守纪律,出勤情况是否良好,能够独立完成设计工作,
0。2
5
4
3
2

工作量
按期圆满完成规定的设计任务，工作量饱满,难度适宜。
0.2
5
4
3
2

说明书的质量
说明书立论正确，论述充分，结论严谨合理，文字通顺,技术用语准确，符号统一，编号齐全,图表完备，书写工整规范。
0。5
5
4
3
2

指导教师评审成绩
（加权分合计乘以8）
分
加权分合计

指 导 教 师 签 名：
年 月 日
评 阅 教 师 评 审 意 见
评价内容
具 体 要 求
权重
评 分
加权分
查阅
文献
查阅文献有一定广泛性；有综合归纳资料的能力
0。2
5
4
3
2

工作量
工作量饱满,难度适中.
0.5
5
4
3
2

说明书的质量
说明书立论正确，论述充分，结论严谨合理,文字通顺,技术用语准确,符号统一，编号齐全，图表完备，书写工整规范。
0.3
5
4
3
2

评阅教师评审成绩
（加权分合计乘以4)
分
加权分合计

评 阅 教 师 签 名：
年 月 日
答 辩 小 组 评 审 意 见
评价内容
具 体 要 求
权重
评 分
加权分
学生汇报
汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。
0.5
5
4
3
2

答 辩
思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。
0。5
5
4
3
2

答辩小组评审成绩
（加权分合计乘以8)
分
加权分合计

答辩小组教师签名：
年 月 日

数据结构课程设计任务书

一、 设计目的

数据结构是计算机专业的核心课程，是一门实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段,要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C（C++）程序并上机调试的基本方法，还要求学生在完成程序设计的同时能够写出比较规范的设计报告.严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用.

二、设计要求

1、课程设计题目每组三题，每个学生必须独立完成;
2、课程设计时间为2周;
3、设计语言C（C++）不限;
4、课余时间完成源程序和课程设计报告等文档书写工作，上机时间只能做调试工作。上机时带上源程序、数据结构教材、C语言教材.
5、上机任务
1）选择合适的数据结构，并定义数据结构的结构体；
2）根据程序所要完成的基本要求，设计出完整的算法;
3）设计出主程序（main函数）,使其成为完整的程序。
6、上机时间：按照实验室上机时间安排计划执行
7、无论在校外、校内，都要严格遵守学校和所在单位的学习和劳动纪律、规章制度,学生有事离校必须请假。课程设计期间，无故缺席按旷课处理;缺席时间达四分之一以上者,其成绩按不及格处理。

三、报告书写格式

1．封皮
2．成绩单
3．任务书
4．目录
5．正文
6．参考文献

四、成绩评定

评定成绩根据课程设计表现、成绩测验、课程设计报告等进行综合评定。评定等级：不及格、及格、中、良好、优秀。

五、设计题目

设计题目一 教学计划安排检验程序（拓扑排序）
【问题描述】针对学院的计算机系本科课程，根据课程之间的依赖关系，制定课程安排计划,并满足各学期课程数大致相同。按照用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出每学期应学的课程。
(1）输入的形式和输入值的范围：输入间用空格隔开。要求用户输入的课程数小于20，学期数小于或是等于8，课程名的长度小于等于10个字符。
（2）程序所能达到的功能：按照用户的输入，给出每学期应学的课程。
（3）测试数据：输入:学期数：５，课程数:12，课程间的先后关系数：16,课程的代表值：v1,v2，v3，v4,v5,v6，v7,v8，v9,v10,v11,v12。课程间两两间的先后关系：v1 v2,v1 v3, v1 v4，v1 v12，v2 v3，v3 v5，v3 v7，v3 v8，v4 v5, v5 v7,v6 v8,v9 v10, v9 v11 , v9 v12,v10 v12，v11 v6
输出：第1学期应学的课程：v1 v9
第2学期应学的课程：v2 v4 v10 v11
第3学期应学的课程：v3 v6 v12
第4学期应学的课程：v5 v8
第5学期应学的课程：v7
设计题目二 停车场问题
【基本要求】
停车场是一条可以停放n辆车的狭窄通道，且只有一个大门汽车停放安到达时间的先后依次由北向南排列（大门在最南端,最先到达的第一辆车停在最北端)若停车场已经停满n辆车，后来的汽车在便道上等候，一旦有车开走，排在便道上的第一辆车可以开入；当停车场的某辆车要离开时,停在他后面的车要先后退为他让路，等它开出后其他车在按照原次序开入车场,每两停在车场的车要按时间长短缴费。 要求：以栈模拟停车场,以队列车场外的便道，按照从终端输入的数据序列进行模拟管理。每一组数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码、以及到达或离去的时刻。对每一组数据进行操作后的信息为：若是车辆到达，则输出汽车在停车场的内或便道上的位置：若是车辆离去则输出汽车在停车场内的停留时间和应缴纳的费用（在便道上的停留时间不收费）。栈以顺序结构实现，队列以链表结构实现.
设计题目三 编写一个猜数字游戏,有一定的容错功能,界面友好，功能齐全。
游戏规则:
a，一个四位数，各位上的数字不重复，从1到9。
b，按以下提示猜出这个四位数。
c，每次猜测输入的数据给出类似的提示＊A＊B。
d,其中A前的＊代表你本次猜对了多少个数字。
e，其中B前的＊代表你本次猜对的数字并且位置正确的个数。
设计题目四 设计实现关键路径的程序
设计内容与步骤
选择合适的数据结构
结点结构的设计
算法设计与分析
程序设计、实现、调试
课程设计说明书
进度安排
设计工作4学时
实现与调试12学时
课程设计说明书4学时
设计考核要求
考勤20%
课程设计说明书50％
答辩30%

五、参考书目

[1] 佟伟光，杨政 《实用数据结构》（第二版） 科学出版社
[2］ 严蔚敏 《数据结构》(C语言版） 清华大学出版社
[3] 李保春编著,《数据结构习题与解析》，清华大学出版 2001年第一版
[4] 徐孝凯编著，《数据结构课程实验》，清华大学出版 2002年第一版
[5] 张乃笑编著，《数据结构与算法》，电子工业出版社 2004年10月
[6］ 王卫东编著,《数据结构辅导课》，西安电子科技大学出版社 2001年
［7] 陈文博 朱青著，《数据结构与算法》，机械工业出版社 1996年
［8］ 赵文静等编，《数据结构辅导》，西安交通大学出版社 1999年

摘 要
“数据结构”是一门专业技术基础课。它的教学要求是：学会分析研究计算机加工的数据结构的特征，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法,并初步掌握算法的时间分析和空间分析的技术.另一方面，本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。
在学习中，先要学习程序设计课程的目的掌握设计程序的思路,学习会用计算机语言编写程序，以实现所需要处理的任务。要正确处理算法与语法的关系，算法是程序的核心、是灵魂，语法是外壳、是工具。不应把学习重。点放在语法规则上，语法是重要的，不掌握语法规则就无法编写出正确的程序.一定要把重点放在解题的思路上，通过思考，和大量的阅读,来构造一个完整的程序.请记住：重要的是学会编程,而不是背语法。
程序设计是为了锻炼我们的实际动手能力，在一定程度上，又增加了我们的各方面的知识，特别是一些联系实际的课程设计，它的完成需要自己平时积累的大量知识、并且需要勤于思考的能力和无限的激情。本次课设主要是学习程序设计的方法,进行程序设计的基本训练，大多数的学生应该把精力放在最基本，最常用的内容上,学好基本功。
最后,感谢老师在我们程序设计的过程中辛勤的指导和不倦的教诲。

关键词 ：线性表,栈和队列，二叉树，图，查找，排序
目 录

数据结构及算法课程设计成绩评定表………………………………………。。。….。。Ⅰ
课程设计任务书…………………………………………………………...…….….。Ⅱ
摘要………………………………………………………………………。……。。。。..。。。Ⅴ
1.停车场问题……………………………………………………………………………………。2
1.1问题分析.。…………………………………………………………………………………2
1.2数据结构与算法分析..…………………………………………………………2
1。3。核心代码………………………………………………………………………………。。…4
1。4运行结果…………………………………………………………………………………11
2。关键路径的程序………………………………………………………………………。..。..。。.14
2.1问题分析。.……………………………………………………………………………。.…14
2.2数据结构与算法分析.。………………………………………………………………。..14
2.3核心代码………………………………………………………………………15
2.4运行结果…………………………………………………………………………………19
3。教学计划安排检验程序（拓扑排序)………………………………………….…21
3.1问题分析.。…………………………………………………………………。.…21
3。2数据结构与算法分析 ………………………………………………………。.21
3。3核心代码………………………………………………………………………22
3。4运行结果…………………………………………………………………………….。。…27
4.猜数字游戏……………………………………………………………………………….。。…29
4。1问题分析.,……………………………………………………………………………….。29
4。2数据结构与算法分析.。……………………………………………………………...…29
4.3核心代码……………………………………………………………………………。.。…29
4。4运行结果…………………………………………………………………………………33
结论…………………………………………………………………………………………….。。.35
致谢…………………………………………………………………………………………....。.。.36
1停车场问题
1。1问题分析

停车场是一条可以停放n辆车的狭窄通道，且只有一个大门汽车停放安到达时间的先后依次由北向南排列（大门在最南端，最先到达的第一辆车停在最北端)若停车场已经停满n辆车，后来的汽车在便道上等候，一旦有车开走，排在便道上的第一辆车可以开入；当停车场的某辆车要离开时，停在他后面的车要先后退为他让路，等它开出后其他车在按照原次序开入车场，每两停在车场的车要按时间长短缴费。 要求：以栈模拟停车场，以队列车场外的便道,按照从终端输入的数据序列进行模拟管理。每一组数据包括三个数据项：汽车“到达"或“离去"信息、汽车牌照号码、以及到达或离去的时刻.对每一组数据进行操作后的信息为：若是车辆到达，则输出汽车在停车场的内或便道上的位置：若是车辆离去则输出汽车在停车场内的停留时间和应缴纳的费用（在便道上的停留时间不收费)。栈以顺序结构实现，队列以链表结构实现。

1。2数据结构与算法分析

本任务要求应用动态存储结构,并且需要两个栈和一个队列，栈用来模拟停车场，队列模拟便道。栈的特点是后进先出，队列的特点是先进先出。

本任务应用了C语言中的类来自定义头文件，将任务分成多个的模块,增强了可读性和简单性，同时为日后的编写,调试,维护提供了极大地方便。

该程序的基本流程图如图1-1所示。主要流程图如图1—2所示。

图1—1 基本流程图

图1-2 主流程图

1.3核心代码

＃include<stdio。h〉
#include〈stdlib.h>
#include〈string.h〉
＃define MAX 2//车库容量 为了便于观察这里把车库容量设置为2
#define price 0.05 //每分钟每辆车的费用
typedef struct time｛
int hour;
int min;
}Time;//时间结点
typedef struct node{
char num[10］;
Time reach；
Time leave；
｝CarNode;//车辆信息结点
typedef struct NODE｛
CarNode *stack[MAX+1];
int top；
｝SeqStackCar;//模拟车站
typedef struct car{
CarNode *data；
struct car *next；
}QueueNode;
typedef struct Node｛
QueueNode *front；
QueueNode ＊rear;
｝LinkQueueCar；//模拟通道
///////////////////////////////////////////////////*定义方法＊/
void InitStack（SeqStackCar＊）;//初始化车站
int InitQueue（LinkQueueCar＊）；//初始化便道
int Arrival（SeqStackCar*，LinkQueueCar*);//车辆到达
void Leave（SeqStackCar＊,SeqStackCar＊,LinkQueueCar＊）；//车辆离开
void List（SeqStackCar，LinkQueueCar）；//显示存车信息
/////////////////////////////////////////////＊主函数＊/
void main(）
｛
SeqStackCar Enter，Temp;
LinkQueueCar Wait；
int ch；
InitStack（&Enter）；//构造一个空栈
InitStack（＆Temp）；//
InitQueue（&Wait);//构造一个空队列
while（1）
｛
//printf（”\n请选择：1 2 3 4\n”）；
printf（"\n＆&＆&＆＆＆&＆＆＆＆＆&＆&＆＆＆＆&&&＆＆& 1。 车辆到达 &＆&&＆&&＆&＆＆＆＆＆&&＆&&&&＆＆& ");
printf（”\n&＆&&＆&＆&&＆&＆&&＆＆＆&&&＆＆&＆&＆ 2. 车辆离开 &&＆＆&＆&&&&＆&＆&＆&＆＆&＆＆&&＆"）；
printf("\n＆＆＆＆&&&&&&&&&＆＆&&&&&＆&＆＆&& 3. 列表显示 &＆＆＆&＆&＆&&&＆&＆&&＆＆&&&&&&")；
printf（"\n&&&&＆＆&＆＆&&&＆＆&＆＆&&&＆＆&&&＆ 4。 退出系统 ＆&&＆＆＆&&＆＆＆＆&&＆&&&＆&＆&＆＆\n”);
scanf（”％d”,＆ch)；
if（ch〈1&&ch〉4)//当不符合要求时重新进行选择
｛
break;
｝
else
｛//否则则进行方法的操作
switch(ch）
｛
case 1: Arrival（&Enter,&Wait)；break；//车辆到达的操作
case 2： Leave(&Enter,&Temp,&Wait）; break；//车辆离开的操作
case 3: List(Enter,Wait）; break;//列表显示的操作
case 4: exit（0）;//退出系统的操作
default： break;
｝
}
}
｝

///////////////////////////////////////////＊车场的初始化 栈＊/
void InitStack（SeqStackCar ＊s)//
{
int i;
s-〉top=0；//栈为空
for(i=0;i〈=MAX;i++）
s-〉stack[s->top］=NULL;//初值为空
}

///////////////////////////////////////////////＊便道的初始化 队列的链式结构*/
int InitQueue(LinkQueueCar ＊Q）
{
Q->front=（QueueNode*）malloc(sizeof（QueueNode））;
if（Q—〉front!=NULL）
｛
Q—〉front->next=NULL;//队列头结点为空
Q—〉rear=Q—〉front；
return (1）;
｝else｛
return （0）；
｝
}

///////////////////////////////////////////////*离站所进行的操作*/
void PRINT（CarNode *p,int room）｛
int A1，A2，B1，B2;
printf（”\n请输入离开的时间："）；
scanf（”%d:％d”，&（p—〉leave。hour）,&（p->leave。min)）；
printf（”\n离开车辆的车牌号为：”）;
puts(p—〉num）;
printf（”\n其到达时间为:%d:%d"，p->reach.hour,p—〉reach。min）;
printf（”离开时间为：％d：％d",p->leave。hour,p-〉leave。min);
A1=p—〉reach。hour;
A2=p—〉reach.min；
B1=p—〉leave.hour;
B2=p—>leave.min;
printf("\n应缴费用为：%2。1f元",(（B1—A1）*60+（B2—A2))＊price）;
free（p)；
｝

//////////////////////////////////////////////*车辆到达＊/
int Arrival(SeqStackCar *Enter，LinkQueueCar *W）
{
CarNode ＊p;
QueueNode *t；
p=（CarNode ＊）malloc（sizeof（CarNode））；//生成结点
//flushall（）；//清除所有缓冲区
printf（"\n请输入车牌号:”）；
scanf（"%s”，&p->num）；//得到车牌号
if（Enter—〉top<MAX）{//判断 如果停车场未满 则进入
Enter->top++；//top指针加一
printf（"\n车辆在停车场内的第％d位置”,Enter-〉top)；
printf（”\n请输入到达时间：")；
scanf（"％d:％d",＆（p—〉reach。hour）,＆（p->reach.min)）；
Enter—>stack［Enter->top］=p;//车辆进栈
return （1）；
}else{
printf(”\n该车须在便道等候！”）;
t=(QueueNode＊）malloc（sizeof（QueueNode)）;
t—〉data=p；//把车辆信息存入队列的结点 即车辆停在便道
t—>next=NULL；//t结点的下一个结点为空
W->front-〉next=t；//头指针的下一个为t
W->rear=t;//尾指针指向t
return （1）;
}
}

//////////////////////////////////////////*出栈＊/
void Leave（SeqStackCar ＊Enter，SeqStackCar ＊Temp，LinkQueueCar *W）
｛
int i，room;
CarNode ＊p，＊t；
QueueNode ＊q;
/＊判断车场内是否有车＊/
if（Enter->top>0）
｛
while(1）
{
printf(”\n请输入车在车场的位置:"，Enter->top）;
scanf(”％d"，＆room）;
if(room〈1&&room>=Enter—〉top）
{
break;
}
while(Enter-〉top〉room）
｛
Temp—>top++；//top指针加一
Temp—>stack［Temp—>top］=Enter-〉stack［Enter—>top］；//把停车场里的车放 入temp中
Enter—>stack［Enter—>top］=NULL；//把停车场里的位置清空
Enter->top--;//top指针减一同时
}
p=Enter—〉stack［Enter—〉top]；
Enter->stack［Enter—〉top]=NULL;
Enter-〉top——；
while（Temp—〉top〉=1）
{
Enter—>top++；//当车出去后原来的车回到停车场
Enter-〉stack［Enter-〉top]=Temp—>stack［Temp—〉top]；
Temp-〉stack［Temp—>top］=NULL;
Temp—〉top-—；
｝
PRINT(p，room）；//离开停车场的信息
if((W->front!=W->rear）&＆Enter-〉top<MAX）//如果便道上有车,并且停车里有 空位
｛
q=W->front-〉next；//把便道里的车赋给q
t=q—>data；//车的信息赋给t
Enter->top++;
printf（"\n便道的％s号车进入车场第%d位置。",t—>num，Enter-〉top）;
printf（"\n请输入现在的时间：”）;
scanf（"％d：%d"，＆(t-〉reach。hour），&(t-〉reach.min)）；
W—>front—〉next=q—>next;//头指针指向q的下一个
if(q==W—〉rear）//如果便道里没车
{
W—>rear=W-〉front;//清空
Enter—〉stack[Enter->top]=t；//进入停车场
printf（"\n便道里没车\n"）；
free（q）；
｝
break;
｝
else
｛
printf（"\n车场里没车。”);
}
break;
｝
}
}

//////////////////////////////////////////////////*列表的显示信息*/
void List1（SeqStackCar *s）
｛
int i;
if(s—>top〉0）
｛
printf（"\n车场")；
printf（"\n位置 到达时间 车牌号\n”）；
for(i=1;i〈=s—〉top；i++）
｛
printf(”％d%10d：％d %s\n", i, s->stack[i]—>reach.hour， s—〉stack［i］-〉reach.min,s-〉stack［i]-〉num）；
// puts(s-〉stack[i]-〉num）;
}
｝
else printf（”\n车场里没车”)；
}

/////////////////////////////////////＊便道里的信息＊/
void List2（LinkQueueCar ＊w）
{
QueueNode *p;
p=w—〉front—〉next；
if（w—>front!=w—〉rear）
｛
printf（”\n等待的车辆的号码为:"）；
while（p!=NULL）
{
puts（p->data->num）;
printf（”\n"）；
p=p—〉next；
｝
｝
else printf("\n便道里没有车。”）；
｝

//////////////////////////////////////////////////////
void List(SeqStackCar s，LinkQueueCar w）
｛
int flag，m;
flag=1;
while(flag）
｛
printf（"\n请选择 1 2 3"）;
printf("\n1。车场 \n2.便道 \n3.返回”）;
while(1)
｛
scanf（”％d",＆m)；
if（m>=1||m〈=3） break；
else printf("\n”）;
｝
switch（m)
{
case 1： List1（&s); break；
case 2： List2（&w）; break;
case 3: flag=0; break;
default：
break；
｝
}
｝

1.4运行结果

1。运行程序，打开停车场主菜单，如图1—3所示。
图1-3 主菜单

2。根据菜单提示，输入“1”，然后输入停车车牌“辽A888888”和时间“8:30"，如图1-4所示。

图1—4 输入停车信息

3.程序默认两个车道，当要求继续停车时，就停入便道里，如图1—5所示。

图1—5 便道停车

4.根据提示,输入“3"后，再分别输入“1”和“2”，输出车道信息和便道信息,分别如图1-6和1-7所示。

图1—6 车道信息

图1—7 便道信息

5.返回主菜单后，输入“2"，然后输入车离开的位置和时间,便显示车离开的信息费用以及便道的车进入车道要求输入信息,如图1—8所示，完成后便显示便道车的信息,如图1—9所示.

图1—8 车离开

图1—9 便道车进入停车场

2 关键路径

2。1问题分析

关键路径（CPM）是管理科学中的一个重要方法,广泛应用于大型工程计划工作，也称之为“统筹法”。关键路径法采用边表示活动的网络，简称为AOE网络。AOE网络是一个带权的有向无环路图，其中，每个顶点代表一个事件，事件说明某些活动或某些活动的完成，即阶段的结果。通常，利用AOE网络可以研究一下两个问题：
⑴完成整个工程至少需要多少时间
⑵哪些活动是影响工程进度的关键
但是完成整个工程所需的时间取决于从开始点到结束点的最长路径长度，此长度最大路径称作为关键路径.

2.2数据结构与算法分析

首先得构造一个图来存储整个工程的顶点数和活动数。
在描述关键路劲的算法时,设a活动由弧(j，k）表示，要确定如下几个相关的量：
⑴事件V的最早出现时间和活动的最早开始时间，从源点v1到顶点v的最长路径长度称作事件j的最早出现时间，表示成e［j]。
⑵活动a的最迟开始时间：在不影响整个工程按时完成的前提下，此项活动最迟的必须开始时间，表示成L［i］。只要某活动a有L[i]=e[i]的关系，就称a为关键活动。
事件j的最迟出现时间：事件j在不延误整个工程的前提下允许发生的最迟时间，表示为L［j］。对某条指向顶点V的边所代表的活动a 可得到L[i]=L［j]—（活动a所需时间）。

该程序的主要流程图如图2-1所示.

图2—1 关键路径主要流程图

2。3核心代码

#include〈stdio。h>
#include<stdlib。h>
＃include〈iomanip。h>
＃include 〈process。h>

typedef struct node
｛
int adjvex；
int dut;
struct node *next;
｝edgenode；
typedef struct
｛
int projectname；
int