信息工程学院50124

1、信息工程学院信息管理与信息系统专业09级数据结构课程设计任务书信息工程学院2012-12数据结构课程设计任务书设计题目排序综合技术参数设计要求利用随机函数或人工输入产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求：至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。设计内容设计步骤1、 结点结构的设计2、 算法设计与分析3、 程序设计、实现、调试4、 课程设计说明书设计计划进度安排1、 设计工作1周2、 实现与调试1周设计考核1、 课程设计说明书50%2、 结果正确

2、50%3、 以上设计符合课程设计教学大纲，可获的2学分。 附件：课程设计模版数据结构课程设计Course Design of Data Structure院系：信息工程学院专业：信息管理与信息系统姓名：xxxxx学号：xxxxx指导老师：xxxxx完成时间：2012年 12月 30日目 录1需求分析说明2概要设计说明3详细设计代码4调试分析5测试结果 排序计算器平面设计图需求分析说明内部排序教学软件的总体功能要求：内部排序的总体目标：在VC+ 的开发环境下，利用所学C+语言和数据结构的相关知识，开发一个具有良好人机界面的内部排序教学软件，实现各种内部排序，并能使用户通过其显示结果对每种排序方法

3、的性能有一个直观的了解，从而达到教学的目的。基本功能如下：（1）界面友好，易与操作。采用菜单或其它人机对话方式进行选择。（2）实现各种内部排序。包括冒泡排序，直接插入排序，直接选择排序，希尔排序，快速排序，堆排序。（3）待排序的元素的关键字为整数。可用随机数据和用户输入数据作测试比较。比较的指标为有关键字参加的比较次数和关键字的移动次数。（4）演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标的列表，以便比较各种排序的优劣。模块调用图：主模块图形界面子模块排序功能及输出子模块封面和结束画面子模块输入子模块鼠标现模块 2概要设计说明    

4、0;            软件的概要设计又称为软件系统（程序系统）的设计，本文件应说明软件系统即程序系统设计的总体考虑，包括系统的基本处理流程、软件 系统的组织结构、模块划分、功能分配、数据结构、接口、运行、    出错处理和系统维护等方面的设计，为详细设计提供基础。           引言     &#

5、160; 1.1      编写目的                 说明编写本设计说明书的目的，指出预期的读者。       1.2      背景         &

6、#160;       a.    说明待开发软件系统的名称。                 b.    列出开发此软件系统的提出者、开发者、和用户。       1.3     

7、; 基线                 说明本系统设计的设计基线。       1.4      范围                 说明本设计说

8、明书所涉及的设计内容范围。       1.5      定义             列出本设计说明书中用到的专门术语和外文字母组词的原词组。       1.6      参考资料     

9、60;           a.    属于项目的其他已发表的文件；                 b.    本设计说明书中引用到的文件、资料，包括所用到的软件开发标准。       &

10、#160; 列出这些文件资料的标题、编号、发表日期、出版单位和查找来源。       2      总体设计           2.1      概述       2.1.1      需

11、求规定                 说明本系统主要的输入、处理、输出的功能和性能要求等。         2.2.2      运行环境              &

12、#160;  说明本系统运行的硬件环境和支持环境。       2.2      设计       2.2.1      设计构思                  &#

13、160;说明对本系统设计的构思、采用的关键技术、主要算法和关键数据结构。       2.2.2      系统流程       a.    用流程图示出本系统的主要控制流程和处理流程；                 

14、b.    用流程图示出本系统主要的数据通路，并说明处理的主要阶段。       2.2.3      结构设计                 a.    系统元素       

15、          确定本系统的元素及其功能，用一览表说明本系统的系统元素（各层模块、子程序、公用程序等）的划分，按层次给出它们的标识符和功能。                 b.    系统层次结构         

16、        用框图分层次地给出各个系统元素之间的控制和被控制的关系。       2.2.4      功能需求与程序的关系                 用功能需求与程序的矩阵图表形式    

17、，示出各项功能的实现与各系统元素之间的分配关系。       3      系统数据结构设计       3.1      数据结构                 列出本系统所使用的主要数据结构，包

18、括名称、标识符及数据项等。       3.2      数据结构与系统元素之间的关系                           用数据结构与系统元素之间的矩阵图表形式，示出各个数据结构与访问这些数据结构的系统

19、元素之间的关系。       4接口设计       4.1      用户接口                 说明本系统向用户提供的命令、语法结构及系统回答信息等。       4.2 

20、     外部接口       说明本系统的软件同硬件和支持软件之间的接口。       4.3      内部接口             说明本系统内部相关模块之间的接口。      &

21、#160;5      运行设计       5.1      系统初始化                 说明本系统初始化过程。           

22、;      5.2      运行模块组合                 说明本系统每项外界运行需经过哪些内部模块的组合和支持软件。             5.3   

23、60;  运行控制                 说明每项外界运行的控制方式、方法和操作步骤。             5.4      运行时间        

24、60;        说明每项运行模块组合预计占用各种资源的时间。             5.5      运行安全                 说明系统安全运行的控制。&#

25、160;            6      信息结构设计（当有相关需求或软件规格定义有要求时）           按逻辑结构和物理结构给出本软件有关信息的设计要点。       6.1      逻辑结构设

26、计       6.1.1      图形设计           6.1.2      中文（包括单个汉字、短语、词组。）设计       6.2      物理结构设计  &#

27、160;    6.2.1      图形设计       6.2.2      中文（包括单个汉字、短语、词组。）设计       6.3      信息结构与程序的关系         

28、    用信息结构与系统元素之间的矩阵图表形式，示出各个信息结构与访问这些信息结构的系统元素之间的关系。             7出错处理和维护       7.1      出错信息            

29、     用一览表列出本系统各种可能出错或故障的信息形式及其含义。       7.2      补救措施                 说明系统故障出现后可能采取的变通措施，包括：       a.

30、0;   后备技术当系统原始数据一旦丢失时，启用副本的建立和启动技术；             b.    降效技术使用另一效率稍低的方法以求得所需结果的某些部份，如手工操作和人工记录数据；             c.    恢复及再启动技术让系统

31、从故障点恢复执行或系统从新启动运行的方法等。           7.3      系统维护                 说明专门安排用于系统检测与维护的检测点和系统检测维护的专用模块等。3.详细设计代码 (1)希尔排序代码void ShellInsert(int array

32、,long dk,long n) int sentinel; /哨兵 for(long i=dk;i<n;i+) if(arrayi<arrayi-dk) sentinel=arrayi; for(long j=i-dk;(j>=0)&&(sentinel<arrayj);j-=dk) arrayj+dk=arrayj; arrayj+dk=sentinel; / return;void ShellSort(int array,long n,long t) /for(int i=0;i<t;i+)cout<<dltai<<&

33、quot; "cout<<endl; long *dlta=new longt; if(t>0)dlta0=1; long temp=1; for(long i=1;i<t;i+) dltai=temp+1; temp*=2; for(i=t-1;i>=0;i-) ShellInsert(array,dltai,n); /dlta=.9,5,3,2,1也可以预先用一数组存放好这个数列! delete dlta; return;（2）选择排序代码#include<iostream> using namespace std; int main()

34、 int num10 = 9,8,10,3,4,6,4,7,2,1; cout<<"排序前："<<endl; for (int m = 0;m < 10;m+) cout<<numm<<" " for (int i = 0;i < 9;i+) int pos = i; for (int j = i+1;j < 10;j+) if (numpos > numj) pos = j; int tem; tem = numpos; numpos = numi; numi = tem; cou

35、t<<endl<<"排序后："<<endl; for (int m = 0;m < 10;m+) cout<<numm<<" " return 0; （3）快速排序代码#include <cstdio>#include <cstdlib>#include <cstring>#include <iostream>using namespace std;int n,a100000;void Init() scanf("%d",

36、&n); for(int i=0;i!=n;+i) scanf("%d",&ai);void Qsort(int l,int r) int i,j,mid,t; i=l; j=r; mid=a(i+j)>>1;/选择中间元素作为基准 while(i<=j) while(ai<mid) +i;/找到一个在mid左边且不小于mid的元素 while(aj>mid) -j;/找到一个在mid右边且不大于mid的元素 if(i<=j) swap(ai,aj);/交换 +i; -j; if(i<r) Qsort(i,r);/递

37、归 if(l<j) Qsort(l,j);/递归 void Print() for(int i=0;i!=n;+i) printf("%d ",ai);int main() Init();/读入 Qsort(0,n-1);/快速排序 Print();/输出 return 0;（4）直接排序代码#include<iostream> using namespace std; #define NUM 10 void DirectInsert(int *list,int n) int i; int j； int x;for (i=1;i<n;i+) x =

38、listi; for (j=i-1;j>=0;j-) if (listj>x) listj+1 = listj; else break; listj+1 = x; void Print(int *list,int n) int i; for (i=0;i<5;i+) cout << listi << "," cout << endl; int main() int arrNUM; int i; srand(1); /初始化随机数发生器 for(i=0;i<NUM;i+) arri=rand()%100;/随机数在0

39、到99范围内 cout << "before sorting :" << endl; Print(arr,sizeof(arr)/sizeof(int); DirectInsert(arr,sizeof(arr)/sizeof(int); cout << "after sorting :" << endl; Print(arr,sizeof(arr)/sizeof(int); return 0; （5）冒泡排序代码#include<iostream>void sort(int array,int

40、 n)using namespace std;int i,j,min=0;for(j=0;j<n-1;j+)for(i=0;i<n-1-j;i+)if(arrayi>arrayi+1)min=arrayi;arrayi=arrayi+1;arrayi+1=min;for(i=0;i<n;i+)cout<<arrayi<<" " if(i=n-1) cout<<"n"void main()using namespace std;cout<<"Please input the

41、number of Numbers(输入数字的个数): "int n;cin>>n;cout<<"Enter the array(输入数据): "int array100,i;for(i=0;i<n;i+)cin>>arrayi;sort(array,n);（4）调试分析 语法错误 ：    请检查是否缺少了分号（行结束符），if、else是否匹配、switch 语句用法是否对等。注意，宏定义、包含文件定义结束不需分号，而类定义结束需要分号。     变量、函数未定义、重定义：     请检查变量大小写、是否包含了相应的头文件（包括你自己的和 MFC、Windows 的）。     连接错误：    这种错误一般发生在你的程序中使用了动态连结库(dll)的时候（不管是你的还是Windows本身的）。此时，可以察看是哪个函数出错。比如你调用了一个 Windows API，而MSDN中的说明写到这个函数需要包含哪个头文件(.h)、输入哪个库(.lib)，那么就要在你的工程