课程设计
题目链式简单选择排序
学院计算机科学与技术
专业计算机科学与技术
班级
姓名
指导教师
2012 年 6 月22 日
武汉理工大学《数据结构》课程设计说明书
课程设计任务书
学生姓名：专业班级：
指导教师：工作单位：计算机科学系
题目:链式简单选择排序
初始条件：
试写一个程序，以单链表作为存储结构，实现简单选择排序。
（1）待排序表的数据不得少于100项；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数。
（2）在课程设计报告中应对你的算法进行时间复杂度分析；
（3）自行设计测试用例。
要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：
1. 问题描述
简述题目要解决的问题是什么。
2. 设计
存储结构设计、主要算法设计（用类C/C++语言或用框图描述）、测试用例设计；
3. 调试报告
调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。
4. 经验和体会（包括对算法改进的设想）
5. 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。
说明：
1. 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。
2. 凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0分记。
时间安排：
1、6月15日～6月21日完成。
2、6月22日上午和下午在实验中心检查程序、交课程设计报告、源程序（U盘）。
指导教师签名： 2012年6月14日
系主任（或责任教师）签名：年月日
武汉理工大学《数据结构》课程设计说明书
目录
1、课程设计问题描述及问题分析
1.1 课程设计问题描述
1.2 问题分析
2、课程设计要求
3、课程设计开发平台
4、程序设计
4.1 存储结构设计
4.2 主要算法设计
4.2.1 链表的尾插法创建及数据的伪随机产生
4.2.2 待排序数据的矩阵输出
4.2.3 链式简单选择排序方法
4.3 主函数算法设计
5、程序调试过程
6、运行结果及说明
6.1创建程序主界面及链表
6.2 从小到大排序及从大到小排序
6.3比较五组不同输入数据的排序
7、时间复杂度分析
8、经验与体会
9、参考文献
10、附：课程设计源程序
1、课程设计问题描述及问题分析
1.1 课程设计问题描述
试写一个程序，以单链表作为存储结构，实现对待排序表中的数据的简单选择排序，并输出排序结果
1.2 问题分析
由本次课程设计的课题内容分析可得，解决问题的实际就是要建立一个单链表，将待排序的整型数据以结点的形式存储在建立的单链表中。然后，依次对单链表中的结点数据进行简单选择排序，其中排序分为从大到小排序和从小到大排序两种方式，分别用这两种方法实现所要求的排序得到结果。
2、课程设计要求
(1)以单链表作为存储结构，实现简单选择排序。待排序的数据不得少于100
项，其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据进行比较；比较的指标为有关键字参加的比较次数。
（2）在课程设计报告中要对所设计的算法进行时间复杂度分析。
（3）设计完成后，自行设计测试用例，要有完整的调试过程和运行结果。
3、课程设计开发平台
本课程设计需要采用支持标准C/C++的Visual C++编译器（6.0或更高版本），并采用最基础的Win32控制台程序。
4、程序设计
本程序设计基本思想是:链式简单选择排序的是每一趟在n-i+1（i=1,2,...,n-1)个记录中选取关键字最大或最小的记录作为有序序列中第i个记录。而本课程设计题目中要求以单链表为存储结构，待排序的数据由伪随机函数产生。因此，首先需要创建一个单链表，将待排序数据存储在单链表中，然后用指针实现关键字的从大到小或者从小到大的排序。
4.1存储结构设计
本课程设计要求使用线性表的链式存储结构来存储待排序的数据，而线性表的链式存储结构特点是用一组任意的可以是不连续的存储单元存储线性表的数据元素。它包括两个域：存储数据元素信息的称为数据域，存储直接后继存储位置的域称为指针域。
单链表结构体的定义如下：
typedef struct LNode
{
int key; //值域
struct LNode *next; //指针域
}Link;
其中，值域key以整型存储了所要排序的关键字值，而指针域next以指针型存储了指向下一个结点的地址。Link是定义的一个全局结构体变量，可以在下面的任何函数中调用。
4.2 主要算法设计
本课程设计的程序中主要包括：创建链表函数Create_Link(Link *),打印链表函数Print_Link(Link *),以及核心部分简单选择排序从小到大排序函数SortFromMin(Link *)以及从大到小SortFromMax(Link *)。
4.2.1链表的尾插法创建及数据的伪随机产生
在VC++中，有两个函数可以产生伪随机数，分别为rand（void）和srand（seed）。rand()产生的随机整数是在0~RAND_MAX之间平均分布的，其用法是先调用srand 函数，如srand( (unsigned)time( NULL ) )。这样可以使得每次产生的随机数序列不同。
如果计算伪随机序列的初始数值（称为种子）相同，则计算出来的伪随机序列就是完全相同的。要解决这个问题，需要在每次产生随机序列前，先指定不同的种子，这样计算出来的随机序列就不会完全相同了。以time函数值（即当前时间）作为种子数，因为两次调用rand函数的时间通常是不同的，这样就可以保证随机性了。也可以使用srand函数来人为指定种子数。
Link *Creat_Link( )
{
int in,count=0,n; //数据输入保存变量和计数器变量
srand((unsigned)time(NULL));
cout<<"请输入要产生的表长:";
cin>>n;
LNode *head,*p,*s; //
head=new Link; //给头结点分配存储控间
p=head; //p初始指向头结点，用来控制输入的循环
cout<<"产生的数据为：";
while(count { in=rand()%1000; //随机产生数 if(count%10==0) cout< cout< s=new Link; //在内存中分配任意的链表结构体空间 s->key=in; p->next=s; p=s; count++; } cout<<"\n"; p->next=NULL; head=head->next; return (head); } 4.2.2待排序数据的矩阵输出 本课程设计要求的待排序数据是用随机函数rand( )产生，并且，数据输出采用矩阵的形式表现。以矩阵的形式输出所随机产生的数据实现代码如下： void Print_Link(Link * head) //循环输出链表的所有值域的数据 { while(head) { cout< cout<<" "; head=head->next; } cout<<"\n"; } 4.2.3链式简单选择排序方法 链式简单选择排序方法主要包括：从小到大排序的SortFromMin(Link *)和从大到小排序的SortFromMax(Link *)。两个函数都包含了关键字参加的比较次数，共同构成了本程序的主体部分，其基本实现思想是一样的。即，从链表的首结点起依次往下检索，选择在指定结点之后所有结点中最小（最大）的那个结点删除并插入到此结点后，循环到最后一个结点为止。函数实现代码如下： Link *SortFromMin(Link *head) //简单选择，从小到大排序 { LNode *h,*p,*q,*r,*s; int c=compCount; h=p=(LNode *)malloc(sizeof(LNode)); p->next=head; while(p->next!=NULL) //p 控制循环比较的次数 { r=p; q=p->next; while(q->next!=NULL) //求r 指向最小值前面一个结点 { if(q->next->key < r->next->key) { r=q; c++; } q=q->next; } if(r!=p) //如果从小到大序列，r==p,不必排列 { s=r->next; // s指向p后面剩下的最小的结点 r->next=s->next; s->next=p->next; p->next=s; } p=p->next; } cout<<"关键字比较次数: "< head=h->next; delete h; return head; } Link *SortFromMax(Link *head) //简单选择方法，实现从大到小排序，其实现代码同理见附表实验代码。 4.3主函数算法设计 本程序的主函数通过定义一个链表结构体指针head，用以指向链表头结点； 设计一个循环输入变量in(int)，控制相关方法的调用来实现链表的建立及对数据的排序。其中，变量in所指向调用的函数情况如下: While(1){ If in=1,调用Create_Link(Link *)，重新创建一个链表,; If in=2,调用SortFromMin(Link *)，进行从小到大的排序，并打印结果; If in=3,调用SortFromMax(Link *)，进行从大到小的排序，并打印结果； If in=0，break; } 5、程序调试过程 在本课程设计的程序调试过程中，出现错误提示如下： （1）--------------------Configuration: 345- Win32 Debug-------------------- Compiling... 链式简单选择排序.cpp D:\Microsoft Visual Studio\Common\MSDev98\Bin\345.cpp(19) : error C2065: 'printf' : undeclared identifier Error executing cl.exe. 原因分析：缺少预处理命令“#include （2）--------------------Configuration: 345- Win32 Debug-------------------- Compiling... 链式简单选择排序.cpp D:\Microsoft VisualStudio\Common\MSDev98\Bin\345.cpp(39) : error C2664: 'Print_Link' : cannot convert parameter 1 from 'struct LNode *' to 'struct LNode' No constructor could take the source type, or constructor overload resolution was ambiguous D:\Microsoft Visual Studio\Common\MSDev98\Bin\345.cpp(46) : error C2664: 'Print_Link' : cannot convert parameter 1 from 'struct LNode *'to 'struct LNode' No constructor could take the source type, or constructor overload resolution was ambiguous D:\Microsoft Visual Studio\Common\MSDev98\Bin\345.cpp(54) : error C2664: 'Print_Link' : cannot convert parameter 1 from 'struct LNode *' to 'struct LNode' No constructor could take the source type, or constructor overload resolution was ambiguous Error executing cl.exe. 原因分析：程序中“void Print_Link(Link );”，声明函数时形参设置有误，导致程序无法正常运行，无法以矩阵的方式输出待排序数据，应改为“void Print_Link(Link * );”。 6、运行结果及说明 6.1创建程序主界面及链表 以time函数值（即当前时间）作为种子数，利用随机数产生待排序数据，例如：输入100，产生100个随机数，输出的结果如下： 6.2从小到大排序及从大到小排序 对一组由伪随机函数产生的数据进行链式简单选择排序后的结果如下图： 6.3比较五组不同输入数据的排序 分别输入表长大于100五组待排序数据，按从小到大的顺序进行链式简单选择排序后，比较五组数据的结果，比较指标为有关键字参加的比较次数。 结论： 以time 函数值（即当前时间）作为种子数，因为两次调用rand 函数的时间通常是不同的，这样就可以保证随机性了。 由上图可得，单链表长度为127时，关键字参与的比较次数为462,；长度为108时，关键字比较次数为356；长度为133时，关键字比较次数为387；长度为113时，关键字比较次数为447；长度为103时，关键字比较次数为328。待排序数据的个数与关键字比较次数并不成正比越多，产生数据的伪随机函数也影响排序的时间复杂度。 7、时间复杂度分析 链式简单选择排序的时间复杂度为0（n*n)，其中主要的两个排序函数中嵌套了两个while循环，其中里面一个是循环比较最小（最大值）结点返回，外面一个是返回结点的插入过程。创建函数的时间复杂度为n ;两个打印函数为2*n 。此简单链式选择排序函数的时间复杂度在最坏的情况是n*(n+1)/2,最好的情况是n。 8、经验与体会 本课程设计是一个比较难的，其中涉及到了数据结构中链表和排序两个知识点，待排序数据要由伪随机函数产生，还有比较关键字参与的比较次数。通过本次实验，我对链表的一些操作：如链表的创建、插入、删除以及简单选择排序有了更深的了解和掌握；掌握了如何利用链表实现从大到小和从小到大排序，如何使用随机函数来产生数据；通过编写数据输出的程序，我学会了如何以矩阵的形式输出数据。 在实验中，我也遇到很多困难，但是我并没有气馁，因为失败是成功之母，只有不断的犯错误，我们才能知道自己有哪些不足。在程序实现过程中，我反复修改代码，不论是语法错误还是逻辑错误，我都认真的找出并修正，务必将实验要求最好的实现。如果，自己实在找不出错误的所在，那么我会向周围的同学请教。虽然大家的课题不一样，但所做的程序设计都是出于数据结构知识的应用，因此，我会简单的向他们讲解一下课题要求，指出自己认为有可能不对的地方，然后听取他们的意见。一人计短，二人计长。错误正是在实践中改正的。 此次课程设计中，我又重新学习了简单选择排序。它是最基本的排序方法之一，比之于其他的排序方法而言思路更清晰操作更简单。对于用线性顺序表结构实现简单选择排序的算法描述，数据结构书本算法10.4已经给出了，而用链式存储结构来实现的区别是循环方式的差别：顺序表用一个for循环实现从下标1到n的排序，链式表的实现是一个while 循环从头结点开始直到最后一个结点。 链式简单选择排序的时间复杂度为0（n*n);除此之外，可以使用树形选择排序。树形 选择排序，又称锦标赛排序方法，是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在其中【n/2】个段之间再进行两两比较，如此重复，直至选择出最小的关键字的记录为止。这个过程可用一颗有n个叶子结点的完全二叉树表示。每个非终端结点中的关键字等于其左右孩子结点中较小的关键字。在输出最小关键字之后，根据关系的可传递性，欲选出次小关键字，仅需将叶子结点中的最小关键字改为最大值，然后从该叶子结点开始，和其左右兄弟的关键字进行比较，修改从叶子结点到根的路径上各结点的关键字，则根结点的关键字即为次小关键字。 总之，通过实验，我学会了独立思考问题，独立写程序，独立修正问题，并且能主动向大家学习。无论在何地、何时，有朋友帮忙指正所得到工作成就远比一个人独立打拼的成就多得多。所以，我不仅要提高自身的编程素质，也要在平时的编程训练中培养团队合作精神。 9、参考文献 [1]《数据结构——用面向对象方法与C++语言描述（第二版）》，殷人昆编著，清华大学出版社，出版或修订时间：2009年9月 [2]《数据结构(C语言版)》，严蔚敏，吴伟民编著，出版社：清华大学出版社，出版或修订时间：1997年4月 [3]《数据结构习题集(C语言版)》，严蔚敏，吴伟民，米宁编著，清华大学出版社，出版或修订时间：1999年2月 10、附：课程设计源程序 #include #include #include #include typedef struct LNode //定义结链表构体 { int key; //值域 struct LNode *next; //指针域 }Link; long compCount; //关键字比较计数 void Print_Link(Link * ); //显示链表 Link *Creat_Link( ); //创建链表 Link *SortFromMin(Link *head); //链表从小到大简单选择排序 Link *SortFromMax(Link *head); //从大到小的排序 int main() { int in; Link *head; //定义链表头结点 cout<<"/*** 用链表实现简单选择排序 ***/\n"; cout< cout<<"/*** 1, 创建一个新链表 ***/\n"; cout<<"/*** 2，从小到大排序 ***/\n"; cout<<"/*** 3, 从大到小排序 ***/\n"; cout<<"/*** 0，退出 ***/\n"; cout<<"\n"; cout<<"按1创建一个链表或按0退出： "; cin>>in; cout<<"\n"; while(in!=1&&in!=0) { cout<<"请输入正确选项： "; cin >>in; } while(1){ if(in==1){ head=Creat_Link( ); cout<<"按2或3选择一个排序的方法或按0退出： "; cin>>in; } if(in==2){ cout<<"\n"; cout<<"/****从小到大排序后的输出结果为:*****/\n"; head=SortFromMin(head); Print_Link(head); cout<<"\n"; cout<<"按1重新建立一个链表，或者按0退出： "; cin>>in; } if(in==3){ cout<<"\n\n"; cout<<"/****从大到小排序后的输出结果为：****/\n"; head=SortFromMax(head); Print_Link(head); cout<<"\n"; cout<<"按1重新建立一个链表或者按0退出： "; cin>>in; } if(in==0) break; } return 0; } Link *Creat_Link( ) { int in,count=0,n; //数据输入保存变量和计数器变量 srand((unsigned)time(NULL)); cout<<"请输入要产生的表长:"; cin>>n; LNode *head,*p,*s; // head=new Link; //给头结点分配存储控间 p=head; //p初始指向头结点，用来控制输入的循环 cout<<"产生的数据为："; while(count { in=rand()%1000; //随机产生数 if(count%10==0) cout< cout< s=new Link; //在内存中分配任意的链表结构体空间 s->key=in; p->next=s; p=s; count++; } cout<<"\n"; p->next=NULL; head=head->next; return (head); } void BeforeSort(){ compCount=0; }//计数清零 void Print_Link(Link * head) //循环输出链表的所有值域的数据 { while(head) { cout< cout<<" "; head=head->next; } cout<<"\n"; } Link *SortFromMin(Link *head) //简单选择方法，实现从小到大排序 { LNode *h,*p,*q,*r,*s; int c=compCount; h=p=(LNode *)malloc(sizeof(LNode)); p->next=head; //将h和p的next域都指向链表头结点，即在链表中插入一 个头结点，以方便后面选择最小结点并插入的操作 while(p->next!=NULL) //p 控制循环比较的次数 { r=p; q=p->next; while(q->next!=NULL) //求r 指向最小值前面一个结点 { if(q->next->key < r->next->key) { r=q; c++; } q=q->next; } if(r!=p) //如果从小到大序列，r==p,不必排列 { s=r->next; // s指向p后面剩下的最小的结点 r->next=s->next; s->next=p->next; p->next=s; } p=p->next; } cout<<"关键字比较次数: "< head=h->next; delete h; return head; } Link *SortFromMax(Link *head) //从大到小的排序 { LNode *h,*p,*q,*r,*s; int d=compCount; h=p=(LNode *)malloc(sizeof(LNode)); p->next=head; while(p->next!=NULL) { r=p; q=p->next; while(q->next!=NULL) { if(q->next->key > r->next->key) //此处与从小到大排序不同{ r=q; d++; } q=q->next; } if(r!=p) { s=r->next; r->next=s->next; s->next=p->next; p->next=s; } p=p->next; } cout<<"关键字比较次数: "< head=h->next; delete h; return head; } 本科生课程设计成绩评定表 班级：姓名：学号： 及格（60-69分）、60分以下为不及格 指导教师签名： 201 年月日 1.一元稀疏多项式计算器 [问题描述] 设计一个一元稀疏多项式简单计算器。 [基本要求] 输入并建立多项式； 输出多项式，输出形式为整数序列：n, c1, e1, c2, e2,……, cn, en ，其中n是多项式的项数，ci, ei分别是第i项的系数和指数，序列按指数降序排序； 多项式a和b相加，建立多项式a+b; 多项式a和b相减，建立多项式a-b; [测试数据] (2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7) (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9-x+12x-3) (1+x+x2+x3+x4+x5)+(-x3-x4)=(x5+x2+x+1) (x+x3)+(-x-x3)=0 (x+x2+x3)+0=(x3+x2+x) [实现提示] 用带头结点的单链表存储多项式，多项式的项数存放在头结点中。 2.背包问题的求解 [问题描述] 假设有一个能装入总体积为T的背包和n件体积分别为w1, w2, …,wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+…+wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积为{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2）、（1，4，5）、（8，2）、（3，5，2） [实现提示] 可利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后顺序选取物品转入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。 由于回溯求解的规则是“后进先出”因此自然要用到栈。 3.完全二叉树判断 用一个二叉链表存储的二叉树，判断其是否是完全二叉树。 4.最小生成树求解（1人） 任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。 5.最小生成树求解（1人） 任意创建一个图，利用普里姆算法，求出该图的最小生成树。 6.树状显示二叉树 编写函数displaytree(二叉树的根指针，数据值宽度，屏幕的宽度)输出树的直观示意图。输出的二叉树是垂直打印的，同层的节点在同一行上。 [问题描述] 假设数据宽度datawidth=2,而屏幕宽度screenwidth为64=26,假设节点的输出位置用 （层号，须打印的空格数）来界定。 第0层：根在（0，32）处输出； 《数据结构I》三级项目报告 大连东软信息学院 电子工程系 ××××年××月 三级项目报告注意事项 1. 按照项目要求书写项目报告，条理清晰，数据准确； 2. 项目报告严禁抄袭，如发现抄袭的情况，则抄袭者与被抄袭者均 以0分计； 3. 课程结束后报告上交教师，并进行考核与存档。 三级项目报告格式规范 1. 正文：宋体，小四号，首行缩进2字符，1.5倍行距，段前段后 各0行； 2. 图表：居中，图名用五号字，中文用宋体，英文用“Times New Roman”，位于图表下方，须全文统一。 目录 一项目设计方案 (3) 二项目设计分析 (4) 三项目设计成果 (4) 四项目创新创业 (5) 五项目展望 (6) 附录一：项目成员 (6) 附录二：相关代码、电路图等 (6) 一项目设计方案 1、项目名称: 垃圾回收 2、项目要求及系统基本功能： 1）利用数据结构的知识独立完成一个应用系统设计 2）程序正常运行，能够实现基本的数据增加、删除、修改、查询等功能3）体现程序实现算法复杂度优化 4）体现程序的健壮性 二项目设计分析 1、系统预期实现基本功能： （结合本系统预期具体实现，描述出对应基本要求(增、删、改、查等)的具体功能） 1. 2. 3. 4. 5. 6. 7. 2、项目模块功能描述 （基本分为组织实施组织、程序功能模块编写、系统说明撰写等。其中程序功能子模块实现） 模块一： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块二： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块n： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 1、冒泡排序 1.1、简介与原理 冒泡排序算法运行起来非常慢，但在概念上它是排序算法中最简单的，因此冒泡排序算法在刚开始研究排序技术时是一个非常好的算法。 冒泡排序原理即：从数组下标为0的位置开始，比较下标位置为0和1的数据，如果0号位置的大，则交换位置，如果1号位置大，则什么也不做，然后右移一个位置，比较1号和2号的数据，和刚才的一样，如果1号的大，则交换位置，以此类推直至最后一个位置结束，到此数组中最大的元素就被排到了最后，之后再根据之前的步骤开始排前面的数据，直至全部数据都排序完成。 1.2、代码实现 public class ArraySort { public static void main(String[] args) { int[] array = {1, 7, 3, 9, 8, 5, 4, 6}; array = sort(array); for (int i = 0; i < array.length; i++) { System.out.println(array[i]); } } public static int[] sort(int[] array) { for (int i = 1; i < array.length; i++) { for (int j = 0; j < array.length-i; j++) { if (array[j] > array[j+1]) { int temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } } } return array; } } 1.3、效率 (一)基本思想 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果： ①初始状态：无序区为R[1..n]，有序区为空。 ②第1趟排序 在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 …… ③第i趟排序 第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 [编辑本段]排序过程 【示例】： 初始关键字[49 38 65 97 76 13 27 49] 第一趟排序后13 ［38 65 97 76 49 27 49] 第二趟排序后13 27 ［65 97 76 49 38 49] 第三趟排序后13 27 38 [97 76 49 65 49] 第四趟排序后13 27 38 49 [49 97 65 76] 第五趟排序后13 27 38 49 49 [97 65 76] 第六趟排序后13 27 38 49 49 65 [97 76] 第七趟排序后13 27 38 49 49 76 [97 76] 最后排序结果13 27 38 49 49 76 76 97 (二)C语言过程 void selectionSort(Type* arr,long len) { long i=0,j=0;/*iterator value*/ long maxPos; assertF(arr!=NULL,"In InsertSort sort,arr is NULL\n"); for(i=len-1;i>=1;i--) { maxPos=i; for(j=0;j 数据结构课程设计 课程名称：内部排序算法比较 年级/院系：11级计算机科学与技术学院 姓名/学号： 指导老师： 第一章问题描述 排序是数据结构中重要的一个部分，也是在实际开发中易遇到的问题，所以研究各种排算法的时间消耗对于在实际应用当中很有必要通过分析实际结合算法的特性进行选择和使用哪种算法可以使实际问题得到更好更充分的解决！该系统通过对各种内部排序算法如直接插入排序，冒泡排序，简单选择排序，快速排序，希尔排序，堆排序、二路归并排序等，以关键码的比较次数和移动次数分析其特点，并进行比较，估算每种算法的时间消耗，从而比较各种算法的优劣和使用情况！排序表的数据是多种不同的情况，如随机产生数据、极端的数据如已是正序或逆序数据。比较的结果用一个直方图表示。 第二章系统分析 界面的设计如图所示： |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| |******************************| 请选择操作方式： 如上图所示该系统的功能有： （1）：选择1 时系统由客户输入要进行测试的元素个数由电脑随机选取数字进行各种排序结果得到准确的比较和移动次数并 打印出结果。 （2）选择2 时系统由客户自己输入要进行测试的元素进行各种排序结果得到准确的比较和移动次数并打印出结果。 （3）选择0 打印“谢谢使用！！”退出系统的使用！！ 第三章系统设计 （I）友好的人机界面设计：（如图3.1所示） |******************************| |-------欢迎使用---------| |-----（1）随机取数-------| |-----（2）自行输入-------| |-----（0）退出使用-------| 《数据结构与算法》课程设计报告 学号： 班级序号： 姓名： 指导教师： 成绩： 中国地质大学信息工程学院地理信息系统系 2011年12 月 1．需求规格说明 【问题描述】 利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储空间。但是，这要求在首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使用时，再对压缩文件进行解压缩，也就是译码，复原原有文件。试为完成此功能，写一个压缩/解压缩软件。 【基本要求】 一个完整的系统应具有以下功能： （1）压缩准备。读取指定被压缩文件，对文件进行分析，建立哈夫曼树，并给出分析结果（包括数据集大小，每个数据的权值，压缩前后文件的大小），在屏幕上输出。 （2）压缩。利用已建好的哈夫曼树，对文件进行编码，并将哈夫曼编码及文件编码后的数据一起写入文件中，形成压缩文件(*.Haf)。 （3）解压缩。打开已有压缩文件(*.Haf)，读取其中的哈夫曼编码，构建哈夫曼树，读取其中的数据，进行译码后，写入文件，完成解压缩。 （4）程序使用命令行方式运行 压缩命令：SZip A Test.Haf 1.doc 解压缩命令：SZip X Test.Haf 2.doc或SZip X Test.Haf 用户输入的命令不正确时，给出提示。 （5）使用面向对象的思想编程，压缩/解压缩、哈夫曼构建功能分别构建类实现。 2．总体分析与设计 （1）设计思想： 1、压缩准备：1> 读文件，逐个读取字符，统计频率 2> 建立哈夫曼树 3> 获得哈弗曼编码 2、压缩过程： 1> 建立一个新文件，将储存权值和字符的对象数组取存储在文件头 数据结构实验总结报告 一、调试过程中遇到哪些问题？ （1）在二叉树的调试中，从广义表生成二叉树的模块花了较多时间调试。 由于一开始设计的广义表的字符串表示没有思考清晰，处理只有一个孩子的节点时发生了混乱。调试之初不以为是设计的问题，从而在代码上花了不少时间调试。 目前的设计是： Tree = Identifier(Node,Node) Node = Identifier | () | Tree Identifier = ASCII Character 例子：a(b((),f),c(d,e)) 这样便消除了歧义，保证只有一个孩子的节点和叶节点的处理中不存在问题。 （2）Huffman树的调试花了较长时间。Huffman编码本身并不难处理，麻烦的是输入输出。①Huffman编码后的文件是按位存储的，因此需要位运算。 ②文件结尾要刷新缓冲区，这里容易引发边界错误。 在实际编程时，首先编写了屏幕输入输出（用0、1表示二进制位）的版本，然后再加入二进制文件的读写模块。主要调试时间在后者。 二、要让演示版压缩程序具有实用性，哪些地方有待改进？ （1）压缩文件的最后一字节问题。 压缩文件的最后一字节不一定对齐到字节边界，因此可能有几个多余的0，而这些多余的0可能恰好构成一个Huffman编码。解码程序无法获知这个编码是否属于源文件的一部分。因此有的文件解压后末尾可能出现一个多余的字节。 解决方案： ①在压缩文件头部写入源文件的总长度（字节数）。需要四个字节来存储这个信息（假定文件长度不超过4GB）。 ②增加第257个字符（在一个字节的0~255之外）用于EOF。对于较长的文件， 会造成较大的损耗。 ③在压缩文件头写入源文件的总长度%256的值，需要一个字节。由于最后一个字节存在或不存在会影响文件总长%256的值，因此可以根据这个值判断整个压缩文件的最后一字节末尾的0是否在源文件中存在。 （2）压缩程序的效率问题。 在编写压缩解压程序时 ①编写了屏幕输入输出的版本 ②将输入输出语句用位运算封装成一次一个字节的文件输入输出版本 ③为提高输入输出效率，减少系统调用次数，增加了8KB的输入输出缓存窗口 这样一来，每写一位二进制位，就要在内部进行两次函数调用。如果将这些代码合并起来，再针对位运算进行一些优化，显然不利于代码的可读性，但对程序的执行速度将有一定提高。 （3）程序界面更加人性化。 Huffman Tree Demo (C) 2011-12-16 boj Usage: huffman [-c file] [-u file] output_file -c Compress file. e.g. huffman -c test.txt test.huff -u Uncompress file. e.g. huffman -u test.huff test.txt 目前的程序提示如上所示。如果要求实用性，可以考虑加入其他人性化的功能。 三、调研常用的压缩算法，对这些算法进行比较分析 （一）无损压缩算法 ①RLE RLE又叫Run Length Encoding，是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效，但它有的时候却非常有用（例如，JPEG就使用它）。 变体1：重复次数+字符 文本字符串：A A A B B B C C C C D D D D，编码后得到：3 A 3 B 4 C 4 D。 一、问题描述 1、排序问题描述 排序是计算机程序设计的一种重要操作，他的功能是将一组任意顺序数据元素（记录），根据某一个（或几个）关键字按一定的顺序重新排列成为有序的序列。简单地说，就是将一组“无序”的记录序列调整为“有序”的记录序列的一种操作。 本次课程设计主要涉及几种常用的排序方法，分析了排序的实质，排序的应用，排序的分类，同时进行各排序方法的效率比较，包括比较次数和交换次数。我们利用java语言来实现本排序综合系统，该系统包含了：插入排序、交换排序、选择排序、归并排序。其中包括： （1）插入排序的有关算法：不带监视哨的直接插入排序的实现； （2）交换排序有关算法：冒泡排序、快速排序的实现； （3）选择排序的有关算法：直接选择排序、堆排序的实现； （4）归并排序的有关算法：2-路归并排序的实现。 2、界面设计模块问题描述 设计一个菜单式界面，让用户可以选择要解决的问题，同时可以退出程序。界面要求简洁明了，大方得体，便于用户的使用，同时，对于用户的错误选择可以进行有效的处理。 二、问题分析 本人设计的是交换排序，它的基本思想是两两比较带排序记录的关键字，若两个记录的次序相反则交换这两个记录，直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有冒泡排序和快速排序。 冒泡排序的基本思想是：将待排序的数组看作从上到下排列，把关键字值较小的记录看作“较轻的”，关键字值较大的纪录看作“较重的”，较小关键字值的记录好像水中的气泡一样，向上浮；较大关键字值的纪录如水中的石块向下沉，当所有的气泡都浮到了相应的位置，并且所有的石块都沉到了水中，排序就结束了。 冒泡排序的步骤： 1)置初值i=1； 2)在无序序列｛r[0],r[1],…，r[n-i]｝中，从头至尾依次比较相邻的两个记录r[j] 与r[j+1]（0<=j<=n-i-1）,若r[j].key>r[j+1].key，则交换位置； 3)i=i+1； 4)重复步骤2）和3），直到步骤2）中未发生记录交换或i=n-1为止； 要实现上述步骤，需要引入一个布尔变量flag，用来标记相邻记录是否发生交换。 快速排序的基本思想是：通过一趟排序将要排序的记录分割成独立的两个部分，其中一部分的所有记录的关键字值都比另外一部分的所有记录关键字值小，然后再按此方法对这两部分记录分别进行快速排序，整个排序过程可以递归进行，以此达到整个记录序列变成有序。 快速排序步骤： 1)设置两个变量i、j，初值分别为low和high，分别表示待排序序列的起始下 课程设计说明书 课程名称：数据结构 专业：班级： 姓名：学号： 指导教师：成绩： 完成日期：年月日 任务书 题目：黑白棋系统 设计内容及要求： 1.课程设计任务内容 通过玩家与电脑双方的交替下棋，在一个8行8列的方格中，进行棋子的相互交替翻转。反复循环下棋，最后让双方的棋子填满整个方格。再根据循环遍历方格程序，判断玩家与电脑双方的棋子数。进行大小判断，最红给出胜负的一方。并根据y/n选项，判断是否要进行下一局的游戏。 2.课程设计要求 实现黑白两色棋子的对峙 开发环境：vc++6.0 实现目标： （1）熟悉的运用c语言程序编写代码。 （2）能够理清整个程序的运行过程并绘画流程图 （3）了解如何定义局部变量和整体变量； （4）学会上机调试程序，发现问题，并解决 （5）学习使用C++程序来了解游戏原理。 （6）学习用文档书写程序说明 摘要 本文的研究工作在于利用计算机模拟人脑进行下黑白棋，计算机下棋是人工智能领域中的一个研究热点，多年以来，随着计算机技术和人工智能技术的不断发展，计算机下棋的水平得到了长足的进步 该程序的最终胜负是由棋盘上岗双方的棋子的个数来判断的，多的一方为胜，少的一方为负。所以该程序主要运用的战术有削弱对手行动战术、四角优先战术、在游戏开局和中局时，程序采用削弱对手行动力战术，即尽量减少对手能够落子的位置；在游戏终局时则采用最大贪吃战术，即尽可能多的吃掉对手的棋子；而四角优先战术则是贯穿游戏的始终，棋盘的四角围稳定角，不会被对手吃掉，所以这里是兵家的必争之地，在阻止对手进角的同时，自己却又要努力的进角。 关键词：黑白棋；编程；设计 /******************************************************* 三种基本排序演示程序 说明：此程序适用于理解三种基本排序原理（简单排序，选择排序，插入排序）以及排序的每一个步骤。并且在重要部分有注释. 本人是一家计算机培训机构的兼职教师（培训计算机C二级的），看到许多同学对于排序非常头疼，当然这是二级C的必考点之一，也是贯穿C语言各种知识点的拿分大项。 本程序是自己按照原理写的原创代码，所以定为1分吧（辛苦费吧，一般我搜集的都是免费的(*^__^*) ……，望大家支持下） 此程序我调试运行成功的，如果你复制到编译器不成功，可能是编译器区别造成的。 如果能自己写出这三种排序的同学，我觉得其对C语言基础知识学习就比较牢固了。 时间：2012年12月3日 ********************************************************/ #include 《数据结构》课程设计报告 专业 班级 姓名 学号 指导教师 起止时间 课程设计：排序综合 一、任务描述 利用随机函数产生n个随机整数（20000以上），对这些数进行多种方法进行排序。（1）至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 （2）统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 要求：根据以上任务说明，设计程序完成功能。 二、问题分析 1、功能分析 分析设计课题的要求，要求编程实现以下功能： （1）随机生成N个整数，存放到线性表中； （2）起泡排序并计算所需时间； （3）简单选择排序并计算时间； （4）希尔排序并计算时间； （5）直接插入排序并计算所需时间； （6）时间效率比较。 2、数据对象分析 存储数据的线性表应为顺序存储。 三、数据结构设计 使用顺序表实现，有关定义如下： typedef int Status; typedef int KeyType ; //设排序码为整型量 typedef int InfoType; typedef struct { //定义被排序记录结构类型 KeyType key ; //排序码 I nfoType otherinfo; //其它数据项 } RedType ; typedef struct { RedType * r; //存储带排序记录的顺序表 //r[0]作哨兵或缓冲区 int length ; //顺序表的长度 } SqList ; //定义顺序表类型 四、功能设计 （一）主控菜单设计 编号 课程设计 题目 1、一元稀疏多项式计算器 2、模拟浏览器操作程序 3、背包问题的求解 4、八皇后问题 二级学院计算机科学与工程学院 专业计算机科学与技术 班级 2011级 37-3班 学生姓名 XX 学号 XXXXXXXXXX 指导教师 XXXXX 评阅教师 时间 1、一元稀疏多项式计算器 【实验内容】 一元稀疏多项式计算器。 【问题描述】 设计一个一元稀疏多项式简单计算器。 【需求分析】 其基本功能包括： （1）输入并建立多项式； （2）输出多项式，输出形式为整数序列为：n,c1,e1,c2,e2,……,cn,en,其中n 是多项式的项数，ci，ei分别是第i项的系数和指数，序列按指数降序排序；（3）多项式a和b相减，建立多项a+b； （4）多项式a和b相减，建立多项式a-b； （5）计算多项式在x处的值； （6）计算器的仿真界面（选做）； 【概要设计】 -=ADT=- { void input(Jd *ha,Jd *hb)； void sort(dnode *h) dnode *operate(dnode *a,dnode *b) float qiuzhi(int x,dnode *h) f",sum); printf("\n"); } 【运行结果及分析】 （1）输入多项式： （2）输出多项式（多项式格式为：c1x^e1+c2x^e2+…+cnx^en）： （3）实现多项式a和b相加： （4）实现多项式a和b相减： （5）计算多项式在x处的值： 2、模拟浏览器操作程序 【实验内容】 模拟浏览器操作程序 【问题描述】 标准Web浏览器具有在最近访问的网页间后退和前进的功能。实现这些功能的一个方法是：使用两个栈，追踪可以后退和前进而能够到达的网页。在本题中，要求模拟实现这一功能。 【需求分析】 需要支持以下指令： BACK：将当前页推到“前进栈”的顶部。取出“后退栈”中顶端的页面，使它成为当前页。若“后退栈”是空的，忽略该命令。 FORWARD：将当前页推到“后退栈”的顶部。取出“前进栈”中顶部的页面，使它成为当前页。如果“前进栈”是空的，忽略该命令。 VISIT 题目: 链式简单选择排序 初始条件： 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 1、系统应具备的功能： （1）用户自己输入数据的个数和数据； （2）建立链表； （3）基于链表的排序算法实现。 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括： （1）设计题目； （2）摘要和关键字； （3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、结果分析、设计体会等； （4）结束语； （5）参考文献。 时间安排：2007年7月2日－7日（第18周） 7月2日查阅资料 7月3日系统设计，数据结构设计，算法设计 7月4日-5日编程并上机调试 7月6日撰写报告 7月7日验收程序，提交设计报告书。 指导教师签名： 2007年7月2日 系主任（或责任教师）签名： 2007年7月2日 链式简单选择排序 摘要：单链表为存储结构，并在这个基础上实现简单选择排序。一趟简单选择排序的操作为：通过n-1次关键字之间的比较，从n-i+1个记录中选出最小的记录并将这个记录并入 一个新的链表中，在原链表中将这个结点删除。 关键字：单链表，简单选择排序，结点，记录 0. 引言 《数据结构》是计算机科学与技术、软件工程及相关学科的专业基础课，也是软件设计的技术基础。《数据结构》课程的教学要求之一是训练学生进行复杂的程序设计的技能和培养良好程序设计的风格，其重要程度决不亚于理论知识的传授，因此课程设计环节是一个至关重要的环节，是训练学生从事工程科技的基本能力，是培养创新意识和创新能力的极为重要的环节。基本要求如下： (1) 熟练掌握基本的数据结构； (2) 熟练掌握各种算法； (3) 运用高级语言编写质量高、风格好的应用程序。 因此在这个课程设计中我选择的是链式简单选择排序。这个实验的实验要求是利用单链表作为记录（数据）的存储结构，并且在记录好用户输入了数据之后对这组数据进行输出，然后对其进行排序，并且输出排序好的数据。 1.需求分析 （1）在这个实验中的数据的存储结构要求是用单链表，不是用数组，也不是循环链表也不是循环链表。 （2）这组数据的大小（即这组数据的个数）是由用户输入的。 （3）用户输入完数据之后，程序能自动的将这些数据（记录）用单链表存储起来。（4）用户输入完数据之后，程序要输出这些数据，以便用户查看自己是否输入错误。（5）对用户输入的数据要自动进行排序操作。 （6）排序完了之后，程序可以自动的输出排序好的数据。 2.数据结构设计 在这个程序中用的存储结构是单链表，对于单链线性表的声明和定义如下： #define datatype int typedef struct Lnode { datatype data;//结点的数据域 struct Lnode *next;//结点的指针域 精品文档 这次课程设计的心得体会通过实习我的收获如下1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。从刚开始得觉得很难，到最后把这个做出来，付出了很多，也得到了很多，以前总以为自己对编程的地方还不行，现在，才发现只要认真做，没有什么不可能。 编程时要认真仔细，出现错误要及时找出并改正，（其中对英语的要求也体现出来了，因为它说明错误的时候都是英语）遇到问题要去查相关的资料。反复的调试程序，最好是多找几个同学来对你的程序进行调试并听其对你的程序的建议，在他们不知道程序怎么写的时候完全以一个用户的身份来用对你的用户界面做一些建议，正所谓当局者迷旁观者清，把各个注意的问题要想到；同时要形成自己的编写程序与调试程序的风格，从每个细节出发，不放过每个知识点，注意与理论的联系和理论与实践的差别。另外，要注意符号的使用，注意对字符处理，特别是对指针的使用很容易出错且调试过程是不会报错的，那么我们要始终注意指针的初始化不管它怎么用以免不必要麻烦。 通过近两周的学习与实践，体验了一下离开课堂的学习，也可以理解为一次实践与理论的很好的连接。特别是本组所做的题目都是课堂上所讲的例子，在实行之的过程中并不是那么容易事让人有一种纸上谈兵的体会，正所谓纸上得来终觉浅绝知此事要躬行。实训过程中让我们对懂得的知识做了进一步深入了解，让我们的理解与记忆更深刻，对不懂的知识与不清楚的东西也做了一定的了解，也形成了一定的个人做事风格。 通过这次课程设计，让我对一个程序的数据结构有更全面更进一步的认识，根据不同的需求，采用不同的数据存储方式，不一定要用栈，二叉树等高级类型，有时用基本的一维数组，只要运用得当，也能达到相同的效果，甚至更佳，就如这次的课程设计，通过用for的多重循环，舍弃多余的循环，提高了程序的运行效率。在编写这个程序的过程中，我复习了之前学的基本语法，哈弗曼树最小路径的求取，哈弗曼编码及译码的应用范围，程序结构算法等一系列的问题它使我对数据结构改变了看法。在这次设计过程中，体现出自己单独设计模具的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，也从中发现自己平时学习的不足和薄弱环节，从而加以弥补。 精品文档 排序算法： (1) 直接插入排序 (2) 折半插入排序(3) 冒泡排序 (4) 简单选择排序 (5) 快速排序(6) 堆排序 (7) 归并排序 【算法分析】 （1）直接插入排序；它是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好的序的有序表中，从而得到一个新的、记录数增加1的有序表。 （2）折半插入排序：插入排序的基本操作是在一个有序表中进行查找和插入，我们知道这个查找操作可以利用折半查找来实现，由此进行的插入排序称之为折半插入排序。折半插入排序所需附加存储空间和直接插入相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。 （3）冒泡排序：比较相邻关键字，若为逆序（非递增），则交换，最终将最大的记录放到最后一个记录的位置上，此为第一趟冒泡排序；对前n-1记录重复上操作，确定倒数第二个位置记录；……以此类推，直至的到一个递增的表。 (4)简单选择排序：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换之。 (5)快速排序:它是对冒泡排序的一种改进，基本思想是，通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 (6)堆排序: 使记录序列按关键字非递减有序排列，在堆排序的算法中先建一个“大顶堆”，即先选得一个关键字为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1记录进行筛选，重新将它调整为一个“大顶堆”，如此反复直至排序结束。 (7)归并排序:归并的含义是将两个或两个以上的有序表组合成一个新的有序表。假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序称为2-路归并排序。 【算法实现】 （1）直接插入排序： void InsertSort(SqList &L){ for(i=2;i<=L.length ;i++) if(L.elem[i] 数据结构课程设计 设计说明书 TSP 问题 起止日期：2016 年 6 月27 日至2016 年7 月 1 日 学生姓名 班级 学号 成绩 指导教师( 签字) 2016 年7 月 1 日 目录 第1 章需求分析.................................................................................1... 1.1 简介 (1) 1.2 系统的开发背景 (1) 1.3 研究现状 (1) 第2 章概要设计.................................................................................2... 2.1 系统开发环境和技术介绍 (2) 2.2 系统需求分析 (2) 2.2.1 总体功能分析 (2) 2.2.2 核心功能分析 (3) 第3 章详细设计...................................................................................4... 3.1 系统开发流程 (4) 3.2 系统模块设计 (4) 3.3 系统结构 (6) 3.2 系统流程图 (6) 第4 章调试分析...................................................................................7... 4.1 程序逻辑调试 (7) 4.2 系统界面调试 (8) 第5 章测试结果...................................................................................9... 5.1 测试环境 (9) 5.2 输入输出测试项目 (9) 5.3 测试结果 (10) 结论.....................................................................................................1..1.. 参考文献................................................................................................1..1. 附录.......................................................................................................1..2.. 上海应用技术学院课程设计报告 课程名称《数据结构课程设计》 设计题目猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统；院系计算机科学与信息工程专业计算机科学与技术班级 姓名学号指导教师日期 一.目的与要求 1. 巩固和加深对常见数据结构的理解和掌握 2. 掌握基于数据结构进行算法设计的基本方法 3. 掌握用高级语言实现算法的基本技能 4. 掌握书写程序设计说明文档的能力 5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力 二.课程设计内容说明 1. 项目一 (1) 对设计任务内容的概述 学生成绩管理** 任务：要求实现对学生资料的录入、浏览、插入和删除等功能。 输入：设学生成绩以记录形式存储，每个学生记录包含的信息有：学号和各门课程的成绩，设学生成绩至少3门以上。存储结构：采用线性链式结构。 (2) 详细设计 LinkList *create()：输入学生成绩记录函数； void print(LinkList *head)：显示全部记录函数 LinkList *Delete(LinkList *head)：删除记录函数 LinkList *Insert(LinkList *head)：插入记录函数 void menu_select()：菜单选择 void ScoreManage()：函数界面 (3) 程序流程图 (4) 程序模块及其接口描述 该程序可以分为以下几个模块： 1、菜单选择：void menu_select(); 提供五种可以选择的操作，在main函数中通过switch语句调用菜单menu_select()函数，进入不同的功能函数中完成相关操作。 武汉理工大学华夏学院课程设计报告书 课程名称：数据结构课程设计 题目：用C语言实现成绩统计程序的设计系名：信息工程系 专业班级：计算机1121 姓名：吴涛 学号：10210412104 指导教师:司晓梅 2016年3 月20日 武汉理工大学华夏学院信息工程系 课程设计任务书 课程名称：数据结构课程设计指导教师：司晓梅班级名称：计算机1121 开课系、教研室：信息系计算机 一、课程设计目的与任务 《数据结构》课程设计是为训练学生的数据组织能力和提高程序设计能力而设置的增强实践能力的课程。目的：学习数据结构课程，旨在使学生学会分析研究数据对象的特性，学会数据的组织方法，以便选择合适的数据的逻辑结构和存储结构以及相应操作，把现实世界中的问题转换为计算机内部的表示和处理，这就是一个良好的程序设计技能训练的过程。提高学生的程序设计能力、掌握基本知识、基本技能，提高算法设计质量与程序设计素质的培养就是本门课程的课程设计的目的。 任务：根据题目要求，完成算法设计与程序实现，并按规定写出课程设计报告。 二、课程设计的内容与基本要求 设计题目：用C语言实现成绩统计程序的设计 〔问题描述〕给出n个学生的m门课程的考试成绩信息，每条信息由姓名、课程代号与分数组成，要求设计算法： （1）输入每个人的各门课程的成绩，计算每人的平均成绩； （2）按平均成绩的高低次序，打印出个人的名次，平均成绩相同的为同一名次； （3）按名次列出每个学生的姓名和各科成绩； 〔基本要求〕学生的考试成绩必须通过键盘输入，且需对输出进行格式控制； 〔算法提示〕可以用选择排序、冒泡排序等多种排序算法求解； 具体要完成的任务是： A. 编制完成上述问题的C语言程序、进行程序调试并能得出正确的运行结果。 B. 写出规范的课程设计报告书； 三、课程设计步骤及时间进度和场地安排 时间：1周地点：现代教育中心 具体时间安排如下： 第一天：布置题目，确定任务、查找相关资料 第二天～第四天：功能分析，编写程序，调试程序、运行系统； 第五天上午：撰写设计报告； 第五天下午：程序验收、答辩。 四、课程设计考核及评分标准 课程设计 题目链式简单选择排序 学院计算机科学与技术 专业计算机科学与技术 班级 姓名 指导教师 2012 年 6 月22 日 武汉理工大学《数据结构》课程设计说明书 课程设计任务书 学生姓名：专业班级： 指导教师：工作单位：计算机科学系 题目:链式简单选择排序 初始条件： 试写一个程序，以单链表作为存储结构，实现简单选择排序。 （1）待排序表的数据不得少于100项；其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数。 （2）在课程设计报告中应对你的算法进行时间复杂度分析； （3）自行设计测试用例。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容： 1. 问题描述 简述题目要解决的问题是什么。 2. 设计 存储结构设计、主要算法设计（用类C/C++语言或用框图描述）、测试用例设计； 3. 调试报告 调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。 4. 经验和体会（包括对算法改进的设想） 5. 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。 说明： 1. 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。 2. 凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0分记。 时间安排： 1、6月15日～6月21日完成。 2、6月22日上午和下午在实验中心检查程序、交课程设计报告、源程序（U盘）。 指导教师签名： 2012年6月14日 系主任（或责任教师）签名：年月日数据结构课程设计
数据结构课程设计报告模板
基础排序总结(冒泡排序、选择排序)
C语言 选择排序
数据结构课程设计(内部排序算法比较_C语言)
数据结构课程设计报告
数据结构实验总结报告
数据结构课程设计-排序
数据结构课程设计报告模板
C语言三种基本排序(简单排序,选择排序,插入排序)演示程序(含注释、每一个步骤,原创) -修订
数据结构课程设计排序实验报告
数据结构课程设计报告
链式简单选择排序
最新数据结构实训总结
数据结构课程设计排序算法总结
数据结构课程设计报告
数据结构课程设计(附代码)
数据结构课程设计报告-学生成绩管理系统[]
链式简单选择排序 数据结构课程设计
相关主题
文本预览