数据结构课程设计.docx

《数据结构课程设计.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计.docx（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、安徽理工大学计算机科学与技术系第页数据结构课程设计Course Design of Data Structure计算机系 02-3姓名：连加凯 学号：200222056指导老师：胡胜利 2005 年 1 月 9 日安徽理工大学计算机科学与技术系第页目 录1需求分析说明 -32概要设计说明 -43详细设计说明 -54调试分析 -75用户使用说明 -86课程设计总结 -107测试结果 -108参考书目 -12安徽理工大学计算机科学与技术系第页需求分析说明内部排序教学软件的总体功能要求：内部排序教学软件的总体目标：在 TURBO C2.0 的开发环境下，利用所学C 语言和数据结构的相关知识，开发一个

2、具有良好人机界面的内部排序教学软件，实现各种内部排序，并能使用户通过其显示结果对每种排序方法的性能有一个直观的了解，从而达到教学的目的。基本功能如下：（1）界面友好，易与操作。采用菜单或其它人机对话方式进行选择。（2）实现各种内部排序。包括冒泡排序，直接插入排序，直接选择排序，希尔排序，快速排序，堆排序。（3）待排序的元素的关键字为整数。可用随机数据和用户输入数据作测试比较。比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以 3 次计)。（4）演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标的列表，以便比较各种排序的优劣。以下是各功能模块的功能描述：1主函数模块本模块

3、的主要功能是初始化图形界面，调用各模块，实现软件功能。2排序功能及输出子模块本模块的主要功能是根据用户的选择进行数组的创建，并对输入数据或者随机产生的数据使用六种排序方法进行排序并统计每种方法的移动次数和比较次数，然后输出以表格形式输出。3封面和结束画面子模块本模块的主要功能是当用户打开本软件时模拟软件加载，延时数秒后关闭，并进入图形界面，在用户退出软件时显示结束画面，延时数秒后关闭程序。4图形界面子模块本模块的主要功能是根据用户的选择显示不同的画面，引导用户使用软件所提供的各种功能，并在用户提供必要数据，并选择排序功能时调用排序模块，并显示结果画面。5输入子模块本模块的主要功能是进行光标定位

4、，输出提示文字，并对用户输入数据进行处理，创建数组。6.鼠标实现模块本模块的主要功能是为用户提供鼠标操作支持，使用户能使用鼠标进行功能的选择。安徽理工大学计算机科学与技术系第页测试数据：1：随机数若干组2：升序数组1，2，3，4 ，5，6，7，8，9，103：降序数组9，8，7，6 ，5，4，3，2，1，0概要设计说明模块调用图：可排序表的抽象数据类型定义为：ADT Orderablelist 数据对象：D=Ai | Ai Integer,i=1,2,n, n=0数据关系：R=|Ai-1,AiD,i=1,2,n基本操作：#define MAXSIZE 200/*数组最大长度*/int MOV_

5、CNT; /*移动次数*/int CMP_CNT; /*比较次数 */void Exchange( int num, int i, int j ) /*交换数组元素 i,j*/void ShellSort( int num, int n ) /*希尔排序*/void QuickSort(int p,int c,int d)/*快速排序*/void SIFT( int num, int s, int n ) /*调整建堆函数*/void HeapSort( int num, int n )/*堆排序*/void ChooseSort( int num, int n )/*选择排序*/void B

6、ubbleSort( int num, int n )/*冒泡排序*/void Insertsort( int num,int n )/*插入排序*/主模块图形界面子模块排序功能及输出子模块封面和结束画面子模块输入子模块鼠标实现模块安徽理工大学计算机科学与技术系第页void Sort( int array, int n ) /*调用六种排序方法并输出移动次数和比较次数*/void CreatRan( int array, int n ) /*建立随机数组*/void CreatUp( int array, int n )/* 建立升序数组*/void CreatDown( int array,

7、 int n ) /*建立降序数组*/int InputLen()/*输入数组长度 */void InputArray( int array, int n ) /*建立人工输入的数组*/void Locate( int row, int col ) /* 光标定位*/void MouseMath()/*计算鼠标的样子*/void MouseOn( int x, int y ) /*鼠标光标显示*/void MouseSetX( int lx, int rx ) /*设置鼠标左右边界*/ void MouseSetY( int uy, int dy ) /*设置鼠标上下边界*/void Mous

8、eSetXY(int x,int y) /*设置鼠标当前位置*/int MouseStatus( int *x, int *y, int *state )/*鼠标坐标及按键情况*/int StartScreen()/*开始界面的进度条*/int MainWin( int x1, int y1, int x2, int y2 )/*主窗口*/int CloseButton( int y1, int x2, int close )/*关闭按钮*/void Button( int buttonx1, int buttony1, int buttonx2, int buttony2, char *na

9、me, int state )/*功能按钮*/void Clear()/*清屏*/void Screen( int sn )/*界面*/void CloseScreen()/*结束画面*/int Mouse()/*鼠标事件处理*/int Run( int bn, int sn )/*功能调用*/详细设计说明1 主函数模块首先调用 initgraph 函数进行图形驱动的初始化，然后调用 StartScreen 函数显示进度条，模拟软件加载，然后调用 Mouse 函数，再调用 closegraph 函数关闭图形模式。2 排序功能及输出子模块在实现排序功能时，每调用一种排序方法前首先应该把原始数组

10、array复制到 num ，把移动次数 MOV_CNT 和比较次数 CMP_CNT 置零，然后对 num进行一种排序，同时进行记数，最后进行光标定位，输出次数。这样进行六次，就可以把六种排序方法的移动次数和比较次数统计出来。再这里，光标的定位是利用软中断方式实现的，这样做可以直接利用 scanf和 printf 进行输入输出，而不必进行数字和字符串之间的转化。安徽理工大学计算机科学与技术系第页3 封面和结束画面子模块软件的封面是一个模拟软件加载的一个进度条。其设计思路是，先利用 bar函数画出一个浅蓝色的矩形条，然后进行光标定位，输出“Loading”字符串，然后将分十段将矩形条用蓝色填充，同

11、时在字符串同一行的右边几个字符的距离输出百分数。由于输出的是利用字符函数，而非图形函数，字符的背景色会覆盖上一次的数字，造成百分数不断增加，进度条不断前进的动画效果。4 图形界面子模块这个模块是软件最为复杂，开发时间最长，修改次数最多的一个模块。这个界面主要是仿照传统的WINDOWS 界面。主窗口是由四部分组成，蓝色的屏幕背景、灰色的窗体、蓝色的标题栏和关闭按钮。窗口和按钮的突起效果是现在屏幕上画一浅色形状，再将纵横坐标增加一两点，画深色形状，从而造成突起效果。为了体现动画的效果，按钮分三种状态，突起状态，平面状态和凹陷状态。凹陷效果可由深色形状在浅色形状的大小基础上缩小一两个像素点得到。一个

12、界面包括提示文字和功能按钮。软件一共有6 个界面，其中界面 0 是用户一开始看到的界面，界面 1，2，3，4 分别对应于功能按钮 1，2，3，4，界面 5 是显示结果的界面。 这个模块的关键在于鼠标控制。鼠标状态 state 为0 时，没有鼠标键按下，为 1 时鼠标左键被按下。鼠标在哪个按钮上是利用鼠标的坐标值是否在按钮的坐标范围内进行判断的。判断用户是否选择了某一功能是利用鼠标在哪个按钮上同时 state=1 进行判断的。当鼠标在非按钮区域按下左键时程序会直接进入下一个循环。界面 0 的四个功能按钮名为：“Random”,”OrderUp”,”OrderDn”,”Input”,代表产生数组的

13、四种方式随机、升序、降序、人工输入。界面 1，2，3，4 的两个功能按钮名为：”Input”,”Static”, 代表确定数组长度的方式人工输入、默认。界面 5 包含一个“Restart”按钮，用来返回到界面 0。5 输入子模块是否初始化鼠标画主窗口画界面 0读取鼠标状态是否在非按钮区域是否在关闭按钮上显示结束画面结束开始是是否在功能按钮区域是判断界面号判断按钮号产生按钮下陷效果安徽理工大学计算机科学与技术系第页当选择好功能以后，分 4 种情况，随机数组、升序数组、降序数组、人工输入的数组。长度分两种，Input是先进行光标定位，然后输出提示文字，当用户输入长度后，把值赋给 n，而 Stati

14、c 是直接把 10 赋给 n。6 鼠标实现模块软件的鼠标最初使用的系统自带的样式，通过BIOS 中断 INT 33H 实现。可以 调试分析我遇到的问题： 同一数组排序六次由于要对同一数组排序六次，必须在排序前先将数组保存起来，每次排序只对数组副本进行操作。 鼠标在 WIN2000，XP 下不能正常显示鼠标使用软中断方式在 WIN98 下能正常工作，但是更高版本如WIN2000，XP 下都不能显示鼠标，即鼠标处于隐形状态。经过思考和查找资料,我决定用自已画一个鼠标指针形状,并根据中断提供的坐标值绘制在屏幕的相应坐标上。当鼠标移动时，先将原始位置的鼠标消去，然后在新的位置绘制出指针形状。 屏幕和按

15、钮不停闪烁经过检查，发现是屏幕重绘频率过快引起的，在每次绘图以后加上一定延时，在有意识的控制循环的频率即可解决。 图形界面下输入数据图形界面下的输入一般为字符串，为了不进行数字和字符串之间的转化，我利用了中断定位光标，直接利用 scanf 进行输入。 在程序显示结果后无法返回界面 0在结果界面上增加一个按钮 Restart，利用 goto 语句即可返回到界面 0。是读取鼠标状态判断鼠标左键是否按下调用 Run 函数图 2： Mouse()的流程图否安徽理工大学计算机科学与技术系第页用户使用说明用户打开软件后，首先见到的是进度条屏幕，如图 3 所示，随后进入了如图4 所示的界面 0。图 3图 4

16、界面 0 的四个功能按钮名为：“Random”,”OrderUp”,”OrderDn”,”Input”,代表产生数组的四种方式随机、升序、降序、人工输入。点选任意一个功能按钮，将会进入如图 5 所示界面。Input 按钮是人工输入数组长度， Static 按钮是使用默认长度 10。当用户点选 Input 按钮时，进入输入长度的界面。当用户点选 Static 按钮时，进入界面 5 或输入数据界面然后进入界面 5。安徽理工大学计算机科学与技术系第页图 5图 6 输入长度界面图 7 输入数组元素界面安徽理工大学计算机科学与技术系第页用户在看到输入长度界面界面后，即可使用键盘输入长度，但要求长度不超过

17、 200，按回车键确认。同理，用户在看到输入数组元素界面后，即可输入元素，元素之间用空格隔开。最后是结果界面。点击 Restart 按钮可回到界面 0。点击关闭按钮即可退出。图 8 结果界面课程设计总结通过这次数据结构课程设计，使我对软件的界面设计有了一个比较深刻的了解，对各种内部排序方法的性能有了清晰的认识，使我感觉到到，一个优秀的软件，不仅仅是可以运行的，更应该具有人性化的界面，协调的布局，合理的结构，良好的性能和一定的容错性。一个人要完成所有的工作是非常困难和耗时的。在以后的学习中我会更加注意各个方面的能力的协调发展，选择一两门技术进行深入研究，成为一个既可以统筹全局，又有一定技术专长的优秀的程序开发人员。测试结果下面对几组数据进行测试。数组： 19，65，85，79，62，33，55，44，77，11排序方法 移动次数 比较次数堆排序 27 13冒泡排序 135 45插入排序 18 9快速排序 27 45选择排序 27 9希尔排序 36 18