《数据结构》课程设计指导书
欧阳勇
湖北工业大学计算机学院
2009.12.2
课程设计名称：数据结构课程设计
指导老师：欧阳勇联系电话159********
课程设计周（时）数：1周
指导方式：集体辅导与个别辅导相结合
课程设计适用专业：网络工程系
一．课程设计的目的
1、掌握数据结构与算法的设计方法，初步具备根据应用需求选择合理数据结构并进行算法设计的能力；
2、进一步提升C语言的应用能力；
2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风；
5、提升文档写作能力。
二．课程设计要求
1、认真分析课题内容和要求，明确设计任务。
2、仔细分析课题，合理设计算法。
3、一人一题，必须独立完成。
4、统一用A4的纸打印，与光盘一起装入“课程设计袋”中于2010年4月14日之前提交至计算机学院教学办。注：必须在规定的时间内完成并提交课设任务，否则该课程无成绩。
5、严禁抄袭，否则取消答辩资格或成绩作废。
6、设计达到一定工作量（300行以上代码）。
7、课程设计说明书不少于15页（不包括代码）。
三、课程设计方法与步骤
1、问题定义与需求分析：根据设计题目的要求，充分地分析和理解问题，确定功能需求和限制条件。
2、数据结构设计：对问题描述中涉及的操作对象定义相应的数据类型和各抽象数据类型，写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)。
3、总体设计：采用结构化设计方法，按照以数据结构为中心的原则划分模块，设计软件层次结构和模块间的调用关系，定义主程序，画出模块之间的调用关系图。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试。
4、详细设计：定义数据存储结构，各个主要模块的算法定义。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，用伪码写出
函数的算法。
5、程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解，使程序中逻辑概念清楚。要求用C语言编写。
6、程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。
7、设计结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。
8、编写课程设计报告。
四、设计选题：
1．在围棋比赛中，某一方（假设为黑方）在棋盘的某个位置（i，j）下子后，有可能提取对方（白方的一串子）。以W[19][19]表示一个棋盘，若W[i][j]=0表示在位置(i,j)上没有子，W[i][j]=1表示该位置上的是黑子，W[i][j]=-1表示该位置上是白子。模拟实现五子棋功能。
2．商店货架以栈的形式摆放商品，生产日期越近的越靠近栈底,出栈是从栈顶取货，一天营业结束，如果货架不满,则需上货，如果直接将商品摆放到货架上，则会使生产日期越近的越靠近栈顶.这就需要倒货架，仍使生产日期越近的越靠近栈底。写出货物进栈、出栈算法。
3．银行业务模拟：
银行业务模拟问题描述：
客户业务分为两种。第一种是申请从银行得到一笔资金，即取款或借款。第二种是向银行投入一笔资金，即存款或还款。银行有两个服务窗口，相应的有两个队列。客户到达银行后先排第一个队。处理每个客户业务时，如果属于第一种，且申请额超出银行现存资金总额而得不到满足，则立即排入第二队等候，直至满足时才离开银行，否则业务处理完后立即离开银行。每接待完一个第二种业务的客户，则顺序检查和处理（如果可能）第二个队列的客户，对能满足的申请者予以满足，不能满足者重新排到第二个队列的队尾。注意，在此检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最后一个客户（第二种业务）被接待之前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检查（因为此时已不可能还有能满足者）转而继续接待第一个队列的客户。任何时刻都只开一个窗口。假设检查不需要时间。营业时间结束时所有客户立即离开银行。写一个上述银行业务的事件驱动模拟系统，通过模拟方法求出客户在银行内逗留的平均时间。
4．运动会分数统计程序的设计
任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w 个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20）
功能要求：
1). 可以输入各个项目的前三名或前五名的成绩；
2)．能统计各学校总分，
3)．可以按学校编号、学校总分、男女团体总分排序输出；
4). 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。
规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）
输出形式：有中文提示，各学校分数为整形
界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；
测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；
5．八皇后问题
问题描述：
八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
基本要求：
在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相"冲突"（在每一横列竖列斜列只有一个皇后）。
6.图书管理基本业务模拟
1)书的登记内容包括书号、书名、著作者、现存量和库存量；
2)号建立索引表（线性表）以提高查找效率；
3）主要功能如下：
a) 采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；
b) 借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；
c) 归还：注销对借阅者的登记，改变该书的现存量。
输出形式：能按书号、书名、著作者查找库存的书籍信息
能按学生的借书证号显示学生信息和借阅信息
书籍入库
借书功能实现
还书功能实现
7.漫步迷宫
问题描述：
用m行n列的m*n个正方格表示一个迷宫，其中划有斜线的方格表示不可通行，未划有斜线的方格表示可以通行。请编写寻找从入口到出口的一条最短路径的程序。
基本要求：
1)迷宫的规格（即行数与列数）,状态设置(即各方格能否通行的状态)，以及入口和出口的位置，均应由输入随机确定。
2)求得的最短路径，应该以从入口到出口的路径上的各个方格的坐标的线性序列输出。当无通路时，应该报告无路径的信息。
3)尽量采用结构化程序设计方法，要求对各个模块的功能及参数作必要的说明。
实现提示：
(1)迷宫可以采用matrix类型的二维数组A表示。A.rownum与A.colnum分别表示迷宫的实际的行数与列数。而A.maze[i][j]表示迷宫中第i行第j列的一个方格，用A.maze[i][j]=0表示该方格可以通行，用A.maze[i][j]=1表示该方格不可以通行。
(2)由于要寻找从入口到出口的一条最短路径，最好将迷宫看作是一个图结构。则问题转化为寻找从对应于入口顶点到对应于出口顶点的一条最短路径的问题。该问题可以采用从入口顶点出发，进行广度优先搜索遍历，直到遇到出口顶点或者遍历完毕也没有遇到出口顶点为止。这二种情况分别对应于最短路径探索成功与查无通路的事实。
(3)基于上述分析，涉及到数据结构的转换，即将二维数组表示的迷宫A转换为以adjlist
类型的邻接表表示的图结构G。在图结构中，将迷宫中的每个方格看作是一个顶点。不可通行的方格都是孤立顶点；相邻的可通行的方格所对应的顶点之间看作是有边相连。因此迷宫
可以看作是由m*n个顶点及无向边构成的一个非连通的无向图。尽管图是不连通的，但不影响本问题的求解，而且本问题有解的条件是：入口顶点与出口顶点在同一个连通分量中。
图结构G中，G.adj[k]表示编号为k的顶点的邻接情况的单链表的头指针；G.vexnum表示图G中的实际顶点数，而且具有如下关系：G.vexnum=A.rownum*A.colnum
(4)为了避免迷宫数据的重复输入，我们期望A能够自动地转换为G。因此应该设计一个转换算法create_adjlist(A,G)。而图结构中顶点是要编号的，我们约定以行为序，顺序给迷宫A中的方格所对应的顶点编号。这样迷宫中方格的坐标（即行row和列col）与图G中所对应的顶点的编号（即verno）之间具有如下关系：
verno=（row-1）* n + col
row=（verno-1）/ n + 1
col=（verno-1）% n + 1
(5)在广度优先搜索遍历求解最短路径过程中，应该设置一个队列queue作为辅助数据结构；路径采用一个整数数组pred来表示。这二个数据结构的存储结构类型均为list类型，其说明定义如下：typedef int list[MAXVER]；
队列queue应该设置front和rear分别指示列首与列尾，queue[k]表示第k个入列的顶点编号。采用pred记录路径，pred[i]表示顶点i在广度优先搜索遍历过程中的前趋顶点的编号，它表明是经过边（pred[i]，i）达到顶点i的。这样，当路径探索成功时，我们可以从出口顶点倒推出从入口到出口的一条路径来。当然要涉及到从顶点编号向方格坐标的反转换，这个公式在上面已经给出了。
测试数据：
设有如下5行10列的迷宫
| 0 1 1 1 1 1 1 1 1 1 |
| 0 1 0 0 1 0 0 0 1 1 |
| 0 0 0 1 1 0 1 0 0 1 | 入口坐标为[1,1]
A.maze=| 0 1 1 0 0 0 1 1 0 1 |
B.| 0 0 0 0 1 0 0 0 0 1 | 出口坐标为[6,10]
C.| 1 1 1 1 1 1 1 1 0 0 |
则输出的最短路径应该是:
[6,10]--[6,9]--[5,9]--[5,8]--[5,7]
--[5,6]--[4,6]--[4,5]--[4,4]--[5,4]
--[5,3]--[5,2]--[5,1]--[4,1]--[3,1]
--[2,1]--[1,1]
8. 交通咨询系统（最短路径问题）
问题描述：
设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短路径或最低费用或最少时间等问题。对于不同咨询要求，可以输入城市间的路程或所需要时间或所需费用。设计分三个部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；最后再实现两个城市顶点之间的最短路径问题。
基本要求：
1)、对城市信息(城市名、城市间的里程)进行编辑：具备添加、修改、删除功能；
2)、对城市间的两种交通工具：飞机和火车。对飞机航班和列车时刻表进行编辑：里程、航班和列车班次的添加、修改、删除；
3)、提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具，
可以不考虑回程；
4)、旅途中的耗费的总时间应包括中转站的等候时间。其中飞机至少二小时，
火车至少一小时；
5)、咨询以用户和计算机对话方式进行，要注意人机交互的屏幕界面。由用户选择最优决策原则和交通工具，输入起始站、终点站、出发时间，输出信息：最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间，并详细说明依次于何时何地乘坐哪一趟班机或列车何时到达何地。
实现提示：
1)、算法思路
(1) 数据存储。城市信息(城市名、代码)、交通信息(城市间的里程、各航班和列车时刻)存储于磁盘文件。建议把城市信息存于文件前面，交通信息存于文件的后面，用fread和fwrite函数操作。
(2) 数据的逻辑结构。根据设计任务的描述，其城市之间的旅游交通问题是典型的图结构，可看作为有向图，图的顶点是城市，边是城市之间所耗费的时间（要包括中转站的等候时间）或旅费。
(3) 数据的存储结构。采用邻接表和邻接矩阵都可作为数据的存储结构，但当邻接边不多时，宜采用邻接表，以提高空间的存储效率。这里建议采用邻接表作为数据的存储结构。
(4) 用不同的功能模块对城市信息和交通信息进行编辑。添加、修改、删除功能可用菜单方式或命令提示方式。只要能方便的对城市信息和交通信息进行管理即可，但要注意人机界面，具体实现由学生自行设计，也可参考有关程序(届时在网上提供)。这些工作有不小的工作量。
(5) 最优决策功能模块(fast or province)。
① 读入城市信息和交通信息，用邻接表生成含权网络，表头数组中的元素存放城市名及对方城市到达该元素所代表城市的所有信息；表头数组中的元素所对应的单链表存放与该元素所代表的城市有交通联系的城市(代码、里程、航班、列车车次)。
② 根据具体最优决策的要求，用Dijkstra算法求出出发城市到其它各城市的最优值(最短时间或最小的费用)，搜索过程中所经过城市的局部最优信息都保存在邻接表的表头数组中。其目的城市所代表的元素中就保存了所需的最优决策结果。这过程中，要用队列或栈保存局部最优决策值(局部最短的时间或最省的费用)变小的城市，其相应的初始值可为∞，并在表头数组对应的城市元素中保存响应的信息。开始时，栈(队)中只有出发地城市，随着对栈(队)顶(首)城市有交通联系的城市求得决策值(最短时间或最小的费用)，若该值是局部最优值且该城市不在栈(队)中，则进栈(队)，直至栈(队)为空。
③ 输出结果。从目的城市出发，搜索到出发城市，所经过的城市均入栈，再逐一出栈栈中的城市，输出保存在表头数组中对应城市的信息(对方城市的出发信息，里程、时间、费用等)及最终结
果。即输出依次于何时何地乘坐几点的飞机或火车于何时到达何地；最终所需的最快需要多长时间才能到达及旅费，或者最少需要多少旅费才能到达及时间。
(6) 主程序可以有系统界面、菜单；也可用命令提示方式；选择功能模块执行，要求在程序运行过程中可以反复操作。
测试数据：
飞机最快到达咨询：北京到乌鲁木齐，北京11点出发；
火车最快到达咨询：广州到哈尔滨，广州10点出发；
飞机最省钱到达咨询：乌鲁木齐到南京，乌鲁木齐12点出发；
火车最省钱到达咨询：沈阳到杭州，沈阳12点出发；
五.课程设计考核标准
考核时主要有如下几项参考：
1．初步设计内容的考核：是否有查阅资料能力？是否有设计思想？
2．程序编码能力调试能力的考核：程序是否清晰、易读？在技算计上是否可独立完成程序的调试，是否熟练？
3．说明书质量的考核：设计结构是否合理？叙述是否正确？方案是否可行？
4．答辩：设计结果的调试能力，对自己设计是否熟练？
六．课程设计报告的内容
设计结束后要写出课程设计报告,以作为整个课程设计评分的书面依据和存档材料.设计报告以规定专用课程设计报告书来写,版面整洁，图,表要清楚,工整.
正文包括以下12个内容:
1．设计目的
2．设计内容与要求
3．课题分析：以无歧义的陈述说明程序设计的任务,强调的是程序要做什么，需要什么结果、所能达到的功能.
4．算法思想：阐述要达到课题分析功能准备采用的算法思路。
例如：
本程序是扫描一个c源程序，有Hash表存储程序中出现的关键字，并统计该程序中的关键字出现的频度。用线性探测法解决Hash冲突。设Hash函数为：Hash(key)=[(key的第一个字母序号)*100+（key的最后一个字母序号）] MOD 41。
算法思想如下:
建立一个结构体数组的hash表,存放读入的关键字和其出现的次数。先初始化并建立该hash 表,先初始化为”0”,0,再从文件中一个个读入所有关键字，存放在hash表中相应位置。
从另一文件中一行行读入，找出其中非注释中的，也非“”中的，长度2-8个字符的小写字符串，用hash查找，看该单词是否关键字，如是其出现次数加一,若不是就继续下一个这样的字符串，直至文件尾。在找这样的字符串途中，遇到无法匹配的单或双引号打印出出现在第几行。
Hash表建立好后打印出来。
其中核心算法分为两块:1.hash表的建立和hash查找。2.寻找上述的字符串。
1.建立Hash表的算法:
该函数实参为已建立的hash表和在c源程序中找到的一个小写字母字符串。
从该字符串key为下标处依次开始查找，到数组末尾是返回数组头(key=(key+1)%44;),分两种情况：
①若先找到空位，说明该字符串不是关键字。则不改变hash表。
②若先找到了该关键字的纪录，则该字符串是关键字，++hash[key].num；
2.寻找疑似关键字字符串的算法
功能:依次找出被非标识符且非”、//、/*、*/隔开的，长度为2-8个字符,非注释中的，也非“”中的小写字母字符串,因为它可能是关键字。
首先,一行行读入c源程序,用续行符相连的几行当一行一起读入。
(1)、case 0和case 1：双引号中的不算，跳过。
①“”匹配中，“……\”不算,“……\\”算。
②单引号中的双引号不算，而且单引号中不会有关键字，所以单引号中的也跳过。
③‘’匹配中,‘\’不算，‘\\’算
(2)、case 2:注释中的不算，跳过。分为/*……*/ //
①设一个标志符flag,当找到/* 但在该行没找到*/ 时，flag=1;此时在下行中寻找*/ ，以此类推，直至找到*/ 后flag=0，以后字符恢复有效。
②当找到//时放弃该行之后的所有字符，读入下一行……
(3)、case 3:读到大写字母、下划线或数字时，肯定该字符串不是关键字，则清除已存在s中的字符串，并跳过紧接在后面的允许在标识符中出现的字符。
(4)、case 4:读到的是小写字母，则存放到字符串s中。
(5)、case 5:本算法以除“、‘、//、/*、*/之外的不能在标识符中出现的字符隔开整行字符串，并判断被隔开的长度2-8个字符，不含大写字母、下划线、数字的字符串（即小写字母字符串）是否关键字，是则增加其统计个数（判断方法为hash查找）。
5．概要设计: 说明本程序中用到的所有抽象数据类型的定义,主程序的流程以及各程序模块之间的层次(调用)关系.包括数据结构定义、程序结构、界面设计。
例如：
（1）数据结构定义
struct edgenode{
int adjvex; //该弧所指向的顶点的位置
edgenode * next; //指向下条条弧的指针
}; //定义邻接表的边结点类型
typedef edgenode * * adjlist; //定义邻接表类型
（2）程序结构
如图,main()函数调用了四个子函数, chu_shi_hash()、create_hash()、Guan_Jian_Zi()、print()。
其中，chu_shi_hash()把hash表初始化为“0000” 0，标记空位，便于以后操作。C
create_hash()实现hash表的创建，从放关键字的文件一个个关键字，它调用了两个子函数，equal()判断两数组是否相等,用来确定某处是否空位.copy()把一个数组赋给另一数组,在确定插入位置插入该关键字。
Guan_Jian_Zi()从c源程序中依次找到可能是关键字的字符串，然后用hash查找判断它是否关键字，是则增加其统计次数。它调用了两个子函数：PanDuan(char) 和chang_hash(Hash,const char ch[])，前者用来判断一个字符的的类别，后者在hash表中查找判断ch[]是否关键字，是则增加其在hash表中的统计量。而chang_hash()调用了函数equal(),用来确定某处是否空位或ch[]。
print(hash)用来打印hash表。
(3)界面设计(略)
6．详细设计:进一步细化概要设计中定义的各模块或函数功能，画出算法实现流程图.
7．测试数据定义：定义典型的测试输入数据，包括各种体现课设正常功能的数据，也包括各种异常测试数据。测试数据应与课题分析所要求的目标一致。
8．源码：打印
9．测试结果：打印
例如：
10．算法分析：算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；
12.使用说明:
13．总结与体会：要写出自己的真实感受。
例如一：
转眼，为期两周的《数据结构》课程设计实习即将结束了。在这次实习中，自己的C语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解决问题的方法。总结起来，自己主要有以下几点体会：
1.必须牢固掌握基础知识。由于C语言是大一所学知识，有所遗忘，且未掌握好这学期所学的《数据结构》这门课，所以在实习之初感到棘手。不知如何下手，但在后来的实习过程中自己通过看书和课外资料，并请教其他同学，慢慢地对C语言和数据结构知识有所熟悉。这时才逐渐有了思路。所以，这次实习之后，我告诫自己：今后一定要牢固掌握好专业基础知识。
2.必须培养严谨的科学态度。自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的科学态度。我想这不仅是对于程序设计，做任何事都应如此。
3.这次课程设计也让我充分认识到《数据结构》这门课的重要性。它给我们一个思想和大纲，让我们在编程时容易找到思路，不至于无章可循。同时它也有广泛的实际应用。
总之，在这次实习中，自己的C语言以及数据结构知识得到提高，编程能力也得到了提高。
例如二：
经过一学期的数据结构课程的学习，我现在编程已经比以前模块化多了，这样既不容易出错，而且出了错也较容易查出，其可读性也加强了。
其次，我现在已习惯编程时写注释了，好像它成了我程序不可缺少的一部分似的，这不仅提高了程序的可读性，因为我是直接上机编的，这也让我的思维更清晰，逻辑更分析的更快些。
对于这次课程设计编的程序，关于hash表的建立和查找，老师上课是讲过的，这一点上没遇到困难，而在于建立和查找的具体环节，会遇到哪几种情况，这些分析上，开始我并没有想周全，漏洞是在调试的时候发现改正的。这说明我想的还是不够细的，要是程序很大是，出现这种逻辑问题就很难发现了。
最重要的是，我开始没能很好的理解题意，最先的程序是为了建hash表而建的，这种思维是不对的，经过吉老师的点播后，恍然大悟，这个思想上的突破很有帮助。
还有开始编的程序是以空格分开单词，这样局限性就很大，经过思考和改良，编了这个和编译器识别关键字同样效果的程序，它以标识符允许之外的字符隔开单词，其实际应用性就很好了。程序的实用性是很重要的，这就是我的收获。
另外，由于编程的积累，我发现调试程序的速度明显加快了，这是个很好的进步，不过，我编程的速度仍然有待提高，我思考过了，导致慢的原因可能有以下几点：
1、打字速度慢。（这点的确的克服）
2、算法没有很熟，只是想一想能出来，而远没有应到的境界。
3、对于数组之类的边界问题浪费了一定的时间，看来用笔画一下比空想是明智些的。
4、编程时精神不能太集中，不过这点一比以前好多了。
5、这是最后，也是最重要的一点，编的程序还不够多，所谓熟能生巧嘛。
综上所述，我还是要好好努力，继续历练的，以提高编程能力目标而继续热情的奋斗！
14．参考文献：列出参考的相关资料和书籍.
例如：
1．杨路明C语言程序设计教程北京邮电大学出版社
2．徐孝凯数据结构课程实验清华大学出版社
3．严蔚敏吴伟民数据结构（C语言版）清华大学出版社