北理工数据结构实验报告
- 格式:doc
- 大小:103.50 KB
- 文档页数:10
《数据结构与算法设计》实验报告——实验一学院:班级:学号:姓名:一、实验目的1.通过实验实践、巩固线性表的相关操作;2.熟悉VC环境,加强编程、调试的练习;3.用C语言编写函数,实现循环链表的建立、插入、删除、取数据等基本操作;4.理论知识与实际问题相结合,利用上述基本操作实现约瑟夫环。
二、实验内容1、采用单向环表实现约瑟夫环。
请按以下要求编程实现:①从键盘输入整数m,通过create函数生成一个具有m个结点的单向环表。
环表中的结点编号依次为1,2,……,m。
②从键盘输入整数s(1<=s<=m)和n,从环表的第s个结点开始计数为1,当计数到第n个结点时,输出该第n结点对应的编号,将该结点从环表中消除,从输出结点的下一个结点开始重新计数到n,这样,不断进行计数,不断进行输出,直到输出了这个环表的全部结点为止。
三、程序设计1、概要设计为实现上述程序功能,应用单向环表寄存编号,为此需要建立一个抽象数据类型:单向环表。
(1)、单向环表的抽象数据类型定义为:ADT Joseph{数据对象:D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0}数据关系:R1={ <ai-1,ai>|ai∈D,i=1,2,……,n}基本操作:create(&L,n)操作结果:构造一个有n个结点的单向环表L。
show(L)初始条件:单向环表L已存在。
操作结果:按顺序在屏幕上输出L的数据元素。
Josephf( L,m,s,n)初始条件:单向环表L已存在, s>0,n>0,s<m。
操作结果:返回约瑟夫环的计算结果。
}ADT Joseph(2)、主程序流程主程序首先调用create(&L,n)函数,创建含有m个节点的单向环表L,然后调用show(L)函数,顺序输出链表中的数据,最后调用Josephf( L,m,s,n)函数,依次输出报的数。
(3)、函数调用关系图2、详细设计(1)、数据类型设计typedef int ElemType; //定义元素类型typedef struct Lnode{ElemType data;struct Lnode *next;}Lnode,*Linklist; //定义节点类型,指针类型(2)、操作算法程序实现:void create(Linklist &L,int m){//生成一个具有m个结点的单向环表,环表中的结点编号依次为1,2,……,m Linklist h,p;L=(Linklist)malloc(sizeof(Lnode));L->data = 1;h=L;for(int i=2;i<=m;i++){p = (Linklist)malloc(sizeof(Lnode));p->data = i; //生成新节点,数据为节点编号h->next = p;h = p; //插入链表}h->next = L; //形成循环链表}void show(Linklist L,int m){//从第一个节点开始依次输出节点编号printf("The numbers of the list are: \n"); //提示用户Linklist h;h=L;for(int i=1;i<=m;i++){printf("%d ",h->data);h = h->next;}printf("\n");}void Josephf(Linklist &L,int m,int s,int n){//实现约瑟夫环Linklist h,q;h = L;q = L;while(h->data != s) //定位开始的节点h = h->next;while(q->next!=h) //定位在开始位置的上一个节点q = q->next;for(int j=1;j<=m;j++){int i=1;while(i<n){q=q->next;i++;}printf("%d ",q->next->data); //依次输出报号为n的节点q->next = q->next->next; //删除已输出节点}printf("\n");}(3)、主程序的代码实现:int main(){int s,m,n;Linklist L;printf("请输入节点数m:\n");scanf("%d",&m);create(L,m); //建立循环链表show(L,m); //输出链表数据printf("请输入起始位置s:\n");scanf("%d",&s);printf("请输入报的数n:\n");scanf("%d",&n);Josephf(L,m,s,n); //输出所报数字return 0;}四、程序调试分析1.引用标识符&不符合C语言语法,应使用C++;2.为了实现循环链表,建立时应该不设头结点且第一个节点就存储编号数据;3.删除节点时要定位到前一个指针,所以在定位开始位置后还要再定位到前一个指针;4.输出时要注意增加“ ”(空格)和“\n”(换行),使输出易于辨识。
数据结构实验报告实验总结本次数据结构实验主要涉及线性表、栈和队列的基本操作以及链表的应用。
通过实验,我对这些数据结构的特点、操作和应用有了更深入的了解。
下面对每一部分实验进行总结。
实验一:线性表的基本操作线性表是一种常见的数据结构,本实验要求实现线性表的基本操作,包括插入、删除、查找、遍历等。
在实验过程中,我对线性表的结构和实现方式有了更清晰的认识,掌握了用数组和链表两种方式实现线性表的方法。
实验二:栈的应用栈是一种后进先出(LIFO)的数据结构,本实验要求利用栈实现简单的括号匹配和后缀表达式计算。
通过实验,我了解到栈可以方便地实现对于括号的匹配和后缀表达式的计算,有效地解决了对应的问题。
实验三:队列的应用队列是一种先进先出(FIFO)的数据结构,本实验要求利用队列实现银行排队和迷宫求解。
通过实验,我对队列的应用有了更加深入的了解,了解到队列可以解决需要按顺序处理的问题,如排队和迷宫求解等。
实验四:链表的应用链表是一种常用的数据结构,本实验要求利用链表实现学生信息管理系统。
通过实验,我对链表的应用有了更深入的了解,了解到链表可以方便地实现对于数据的插入、删除和修改等操作,并且可以动态地调整链表的长度,适应不同的需求。
通过本次实验,我掌握了线性表、栈、队列和链表的基本操作,并了解了它们的特点和应用方式。
同时,通过实际编程的过程,我对于数据结构的实现方式和效果有了更直观的认识,也锻炼了自己的编程能力和解决问题的能力。
在实验过程中,我遇到了一些问题,如程序逻辑错误和内存泄漏等,但通过调试和修改,最终成功解决了这些问题,对自己的能力也有了更多的信心。
通过本次实验,我深刻体会到了理论与实践的结合的重要性,也对于数据结构这门课程有了更加深入的理解。
总之,本次数据结构实验给予了我很多有益的启发和收获,对于数据结构的概念、特点和应用有了更深入的理解。
在以后的学习中,我会继续加强对数据结构的学习和研究,不断提高自己的编程能力和解决问题的能力。
一、实验背景数据结构是计算机科学中一个重要的基础学科,它研究如何有效地组织和存储数据,并实现对数据的检索、插入、删除等操作。
为了更好地理解数据结构的概念和原理,我们进行了一次数据结构实训实验,通过实际操作来加深对数据结构的认识。
二、实验目的1. 掌握常见数据结构(如线性表、栈、队列、树、图等)的定义、特点及操作方法。
2. 熟练运用数据结构解决实际问题,提高算法设计能力。
3. 培养团队合作精神,提高实验报告撰写能力。
三、实验内容本次实验主要包括以下内容:1. 线性表(1)实现线性表的顺序存储和链式存储。
(2)实现线性表的插入、删除、查找等操作。
2. 栈与队列(1)实现栈的顺序存储和链式存储。
(2)实现栈的入栈、出栈、判断栈空等操作。
(3)实现队列的顺序存储和链式存储。
(4)实现队列的入队、出队、判断队空等操作。
3. 树与图(1)实现二叉树的顺序存储和链式存储。
(2)实现二叉树的遍历、查找、插入、删除等操作。
(3)实现图的邻接矩阵和邻接表存储。
(4)实现图的深度优先遍历和广度优先遍历。
4. 算法设计与应用(1)实现冒泡排序、选择排序、插入排序等基本排序算法。
(2)实现二分查找算法。
(3)设计并实现一个简单的学生成绩管理系统。
四、实验步骤1. 熟悉实验要求,明确实验目的和内容。
2. 编写代码实现实验内容,对每个数据结构进行测试。
3. 对实验结果进行分析,总结实验过程中的问题和经验。
4. 撰写实验报告,包括实验目的、内容、步骤、结果分析等。
五、实验结果与分析1. 线性表(1)顺序存储的线性表实现简单,但插入和删除操作效率较低。
(2)链式存储的线性表插入和删除操作效率较高,但存储空间占用较大。
2. 栈与队列(1)栈和队列的顺序存储和链式存储实现简单,但顺序存储空间利用率较低。
(2)栈和队列的入栈、出队、判断空等操作实现简单,但需要考虑数据结构的边界条件。
3. 树与图(1)二叉树和图的存储结构实现复杂,但能够有效地表示和处理数据。
《数据结构与算法统计》实验报告——实验三学院:班级:学号:姓名:一、实验目的1 熟悉VC环境,学会使用C++解决关于二叉树的问题。
2 在上机、调试的过程中,加强对二叉树的理解和运用。
3 锻炼动手编程和独立思考的能力。
二、实验内容遍历二叉树。
请输入一棵二叉树的扩展的前序序列,经过处理后生成一棵二叉树,然后对于该二叉树输出前序、中序和后序遍历序列。
三、程序设计1、概要设计为实现上述程序功能,首先需要二叉树的抽象数据结构。
⑴二叉树的抽象数据类型定义为:ADT BinaryTree {数据对象D:D是具有相同特性的数据元素的集合。
数据关系R:若D=Φ,则R=Φ,称BinaryTree为空二叉树;若D≠Φ,则R={H},H是如下二元关系;(1)在D中存在惟一的称为根的数据元素root,它在关系H下无前驱;(2)若D-{root}≠Φ,则存在D-{root}={D1,Dr},且D1∩Dr =Φ;(3)若D1≠Φ,则D1中存在惟一的元素x1,<root,x1>∈H,且存在D1上的关系H1 ⊆H;若Dr≠Φ,则Dr中存在惟一的元素xr,<root,xr>∈H,且存在上的关系Hr ⊆H;H={<root,x1>,<root,xr>,H1,Hr};(4)(D1,{H1})是一棵符合本定义的二叉树,称为根的左子树;(Dr,{Hr})是一棵符合本定义的二叉树,称为根的右子树。
基本操作:CreatBiTree(BiTree &T)操作结果:按先序次序建立二叉链表表示的二叉树TPreOrderTraverse(BiTree T,int (*visit)(char e))初始条件:二叉树T已经存在,visit是对结点操作的应用函数操作结果:先序遍历二叉树T ,对每个结点调用visit函数仅一次;一旦visit()失败,则操作失败。
InOrderTraverse(BiTree T,int (*visit)(char e))初始条件:二叉树T已经存在,visit是对结点操作的应用函数操作结果:中序遍历二叉树T ,对每个结点调用visit函数仅一次;一旦visit()失败,则操作失败。
《数据结构与算法统计》实验报告学院:班级:学号:姓名:一、实验目的1.熟悉VC++6.0环境,学习使用C++实现链表的存储结构;2.通过编程,上机调试,进一步理解线性表、链表的基本概念。
二、实验内容归并顺序表(选作)。
请按以下要求编程实现:①从键盘输入两个升序排列的整数序列linka和linkb,每个序列以输入0为结束标记。
②将链表linka和linkb归并为linkc,linkc仍然为升序排列。
归并完成后,linka和linkb为空表。
输出linkc。
③对linkc进行处理,保持升序不变,删除其中重复的整数,对重复的整数只保留一个,输出删除重复整数后的链表。
例如:linka输入为:10 20 30 40 50 0linkb输入为:15 20 25 30 35 40 45 50 0归并后的linkc为:10 15 20 20 25 30 30 35 40 40 45 50 50删除重复后的linkc为:10 15 20 25 30 35 40 45 50三、程序设计1、概要设计说明程序的主要功能,主程序的流程以及各个程序模块之间的调用关系,给出主要流程图。
应用单链线性表寄存数字序列。
⑴单链线性表的抽象数据类型线性表的定义如下:ADT LinkList {数据对象:D = { ai | ai ∈ElemSet, i=1,…,n,n≥0 }数据关系:R1 = { <ai-1, ai> | ai-1,ai ∈D, i=2, …,n }基本操作:Creat(LinkList &L)操作结果:构造单链线性表L。
MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)初始条件:单链线性表La,Lb,Lc已经存在。
操作结果:归并La,Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列。
Delete(LinkList &L)初始条件:链表L已经存在。
《数据结构与算法设计》实验报告——实验二学院:自动化学院班级:06111001学号:**********姓名:宝竞宇一、实验目的掌握栈的建立,输入,删除,出栈等基本操作。
应用栈解决实际问题。
二、实验内容实现简单计算器的功能,请按照四则运算加、减、乘、除、幂(^)和括号的优先关系和惯例,编写计算器程序。
要求支持运算符:+、-、*、/、%、()和=:①从键盘输入一个完整的表达式,以回车作为表达式输入结束的标志;②输入表达式中的数值均为大于等于零的整数,如果中间计算过程中出现小数也只取整进行计算。
例如,输入:4+2*5= 输出:14输入:(4+2)*(2-10)= 输出:-48三、程序设计1、概要设计抽象数据类型定义:两个栈结构,分别用来储存数据和计算符号宏定义:函数“成功”,“失败的返回值”在主程序程序中先依次输入各表达式,存入相应各栈,然后,调用“判断函数”来判断计算符的优先次序,然后再利用计算函数来计算,表达式值。
其中还有,取栈顶元素函数,存入栈函数。
2、详细设计数据类型实现:struct t{ char dat[200];int top;}prt;入栈函数:存入数组,栈顶指针上移void pushd(long int a){ prd.dat[prd.top++]=a;}出栈:取出对应值,栈顶指针下移long int popd( ){ return prd.dat[--prd.top];}比较优先级:建立数组,比较返回大于小于号。
计算函数:以字符型输入,运算符号,用switch来分支计算判断,返回计算数值long int operation ( long int x, long int y, char a){ s witch(a){ case '+': return x+y;case '-': return x-y;case '*': return x*y;case '/': if ( y )return x/y;else{ printf("Divide 0.\n");return 0;}case '%': return (long int) fmod(x,y);case '^': if (y>=0 ) return (long int) pow(x,y);else return (0);default: printf("Error No. 3\n");return 0;}}主程序:在主程序内,以字符串的形式输入表达式,然后分别调用函数存入各相应栈,然后用数组判断,比较运算符的优先顺序。
数据结构课程实验报告一、实验目的。
本次实验旨在通过对数据结构课程所学知识的应用,加深对数据结构相关算法和数据操作的理解,提高学生的编程能力和实际应用能力。
二、实验内容。
1. 实现顺序表、链表、栈、队列等数据结构的基本操作;2. 设计并实现数据结构相关算法,如查找、排序等;3. 进行实验数据的输入、输出和结果展示;4. 对实验结果进行分析和总结。
三、实验过程。
1. 针对顺序表、链表、栈、队列等数据结构,首先进行了相关操作的实现。
在实现过程中,需要考虑数据结构的特点和操作规则,确保操作的正确性和高效性。
2. 针对数据结构相关算法,如查找、排序等,设计并实现了相应的算法。
在实现过程中,需要考虑算法的时间复杂度和空间复杂度,确保算法的效率和稳定性。
3. 进行了实验数据的输入、输出和结果展示。
通过编写测试用例,对实现的数据结构和算法进行了测试,验证其正确性和可靠性。
4. 对实验结果进行了分析和总结。
通过对实验数据和测试结果的分析,总结了实验中遇到的问题和解决方法,以及实验的收获和体会。
四、实验结果。
经过实验测试,实现的数据结构和算法均能正确运行并得到预期的结果。
通过实验,加深了对数据结构相关知识的理解,提高了编程能力和实际应用能力。
五、实验总结。
本次实验使我对数据结构相关知识有了更深入的理解,同时也提高了我的编程能力和实际应用能力。
在未来的学习和工作中,我将继续努力,不断提升自己的能力,为将来的发展打下坚实的基础。
六、实验感想。
通过本次实验,我深刻感受到了数据结构在实际应用中的重要性,也意识到了自己在数据结构方面的不足之处。
在今后的学习和工作中,我将更加努力地学习和应用数据结构知识,不断提高自己的能力,为未来的发展做好充分的准备。
七、参考文献。
1. 《数据结构与算法分析》。
2. 《C语言程序设计》。
3. 《数据结构课程实验指导书》。
以上就是本次数据结构课程实验的报告内容,希望能对大家有所帮助。
感谢您的阅读!。
数据结构实验报告及心得体会一、引言数据结构是计算机科学中的重要基础课程,通过实验环节的学习,我们能够更好地掌握和应用数据结构的概念、算法和操作。
本报告旨在总结和分享我们进行的数据结构实验,并提出相应的心得体会。
二、实验一:线性表的实现与应用1. 实验目的本实验旨在通过实现和应用线性表的基本操作,掌握线性表的存储结构和算法。
2. 实验内容我们选择了顺序表和链表两种线性表的实现方式,并实现了插入、删除和查找等基本操作。
通过实验,我们发现顺序表适用于元素个数较少、频繁查找的情况,而链表适用于插入和删除操作较多、元素个数不确定的情况。
3. 实验心得通过实验一,我们深刻认识到数据结构的不同实现方式对算法的影响。
选择合适的数据结构可以提高算法效率,提高程序的性能。
同时,我们也意识到了在实际应用中,根据问题的具体特点选择不同的数据结构才能得到最优解。
三、实验二:栈与队列的应用本实验旨在通过实现和应用栈和队列的基本操作,掌握栈和队列的特性及其在实际应用中的作用。
2. 实验内容我们分别实现了顺序栈、链式栈、顺序队列和链式队列,并实现了入栈、出栈、入队和出队等基本操作。
我们发现栈适用于实现回溯算法、递归算法等,而队列适用于广度优先搜索、线程池等场景。
3. 实验心得通过实验二,我们进一步理解了栈和队列在实际编程中的运用。
它们提供了方便的数据结构,帮助我们解决了许多实际问题。
同时,实验过程中,我们也发现了栈溢出的问题,意识到了合理管理栈空间的重要性。
四、实验三:树与二叉树的实现与应用1. 实验目的本实验旨在通过实现和应用树和二叉树的基本操作,掌握树和二叉树的存储结构和算法。
2. 实验内容我们实现了树和二叉树的基本操作,包括创建、插入、删除和遍历等。
通过实验,我们发现树在表示具有部分层次结构的问题时更合适,而二叉树在表示递归结构时更加方便。
通过实验三,我们深入理解了树和二叉树的特性及其应用。
树和二叉树是许多高级数据结构的基础,熟练掌握它们的操作对于解决实际问题非常重要。
实验四图书管理系统姓名:任子龙学号:1120140167 班级:05111451一。
需求分析(1)问题描述有一个小型书库保管了大量图书,关于图书有大量信息需要处理,这些信息包括图书的分类、书名、作者名、购买日期、价格等。
现要求编写一个程序以便于对图书的管理。
(2)基本要求:a.建立图书信息.b.提供查找功能,按照多种关键字查找需要的书籍。
例如按书名查找,输入书名后,将显示出该图书的所有信息,或显示指定信息。
c.提供排序功能,按照多种关键字对所有的书籍进行排序,例如按出版日期进行排序。
d.提供维护功能,可以对图书信息进行添加、修改、删除等功能。
(3)数据结构与算法分析将每一本书看作是一个基本单元。
由于涉及添加、修改操作,这里使用了链表作为数据存储结构;同时,考虑到排序功能,尝试使用双向链表。
其中,每本书作为一个结点,数据域包含char 型变量,指针域含有左右指针left和right。
二.概要设计1。
抽象数据类型的定义为实现上述功能,程序中使用了双向链表,只需要定义一种数据类型:typedef struct book{char number[10];char title[20];char author[10];char date[15];char price[10];struct book *right;struct book *left;}BK;注意结点的指针域有left和right两个。
2.本程序包含两个模块(1)主程序模块主函数只包含了Menu_select()函数。
目的是进入主菜单界面,进行功能选择;直到输入操作码0,退出系统;(2)双向链表单元模块——实现书籍信息的链式存储的抽象数据类型.各函数之间的调用关系:三。
详细设计1。
结点类型typedef struct book{char number[10];char title[20];char author[10];char date[15];char price[10];struct book *right;struct book *left;}BK;2.子函数(1)功能菜单调用函数Menu_select()使用户进入主菜单界面,进行功能选择;先进入无限循环,输入操作码进行系统管理工作,直到输入操作码0,退出系统;(2)各种功能函数Initialize()//初始化图书系统信息;Insert()//添加新的图书信息;Sort()//对图书进行排序,本程序可以实现按“图书编号”、“出版日期"、“图书价格”多种关键字进行排序;Search()//实现对图书的查找功能,本程序可以实现按“图书编号"、“出版日期”、“图书价格”多种关键字进行查找;deletebook()//删除无效的图书信息;Print_book()//打印全部图书信息。
《数据结构与算法统计》实验报告——实验四学院:班级:学号:姓名:一、实验目的1、熟悉VC 环境,学会使用C 语言利用顺序表解决实际问题。
2、通过上机、编程调试,加强对线性表的理解和运用的能力。
3、锻炼动手编程,独立思考的能力。
二、实验内容从键盘输入10个数,编程实现分别用插入排序、交换排序、选择排序算法进行排序,输出排序后的序列。
三、程序设计1、概要设计为了实现排序的功能,需要将输入的数字放入线性表中,进行进一步的排序操作。
(1)抽象数据类型:ADT SqList{数据对象:D={|,1,2,,,0}i i a a ElemSet i n n ∈=≥数据关系:R1=11{,|,,1,2,,}i ii i a a a a D i n --<>∈= 基本操作: Input(Sqlist & L)操作结果:构造一个线性表L 。
output(SqList L)初始条件:线性表L 已存在。
操作结果:按顺序在屏幕上输出L 的数据元素。
BiInsertionsort (Sqlist L)初始条件:线性表L 已存在。
操作结果:对L 的数据元素进行折半插入排序。
QuickSort (Sqlist L)初始条件:线性表L 已存在。
操作结果:对L 的数据元素进行交换排序。
SelectSort(SqList &L)初始条件:线性表L 已存在。
操作结果:对L 的数据元素进行选择排序。
}ADT SqList⑵ 宏定义#define KeyType int#define MAXSIZE 10#define ok 1#define error 0⑶主程序流程由主程序首先调用Input(L)函数创建顺序表,先调用BiInsertionsort (L)函数进行折半插入排序,调用output(L)函数显示排序结果。
再调用QuickSort (L)函数进行交换排序,调用output (L)函数显示排序结果。
最后调用SelectSort(L)函数进行选择排序,调用output(L)函数显示排序结果。
⑷模块调用关系由主函数模块调用创建顺序表模块,排序模块与显示输出模块。
(5)流程图2、详细设计(1)数据类型设计/* 顺序存储结构*/typedef struct{KeyType Key; //关键字项} RedType;typedef struct{RedType r[MAXSIZE+1];int length; // =MAXSIZE;} Sqlist; //定义顺序表类型(2)操作算法设计/* 输入数据*/int Input(Sqlist & L){for(int i=1;i<=MAXSIZE;i++)scanf("%d",&L.r[i].Key);L.length=MAXSIZE;return ok;}/* 输出排好的数字*/int output(Sqlist L){for(int i=1;i<=MAXSIZE;i++)printf("%-4d",L.r[i].Key);printf("\n");return ok;}/* 折半插入排序法*/void BiInsertionsort (Sqlist L){int i,j,low,high,m;for(i=2;i<=L.length;i++){L.r[0].Key=L.r[i].Key; //把要插入的当成哨兵low=1; high=i-1;while(low<=high) //折半法找到要插入的位置{m=(low+high)/2;if(L.r[0].Key<L.r[m].Key) high=m-1;else low=m+1;}for(j=i-1;j>=high+1;j--) //插入位置后的袁术后移一位.r[j+1]=L.r[j];L.r[high+1]=L.r[0]; //插入元素}//lowprintf("折半插入排序:\n");output(L);}//BiInsertionsort/* 快速交换排序法*/int Partition(Sqlist &L,int low,int high){int pivotkey;L.r[0].Key=L.r[low].Key; //用子表的第一个记录作枢轴记录pivotkey=L.r[low].Key; //枢轴记录关键字while(low<high) //从表的两端交替地向中间扫描{while(low<high&&L.r[high].Key>=pivotkey){--high;//将比枢轴记录小的记录移到低端}//whileL.r[low].Key=L.r[high].Key;while(low<high&&L.r[low].Key<=pivotkey){++low;//将比枢轴记录大的记录移到高端}//whileL.r[high].Key=L.r[low].Key;}//whileL.r[low].Key=L.r[0].Key;//枢轴记录到位return low;//返回枢轴位置}//Partitionvoid QSort(Sqlist &L,int low,int high){int pivotloc;if(low<high)//长度大于1{pivotloc=Partition(L,low,high);//将L.r[low…high]一分为二QSort(L,low,pivotloc-1);//对低子表递归排序,pivotloc是枢轴位置QSort(L,pivotloc+1,high);//对高子表递归排序}//if}//QSortvoid QuickSort(Sqlist &L) //对顺序表L做快速排序{QSort(L,1,L.length);printf("交换排序:\n");output(L);}//QuickSort/* 选择排序法*/void SelectSort(Sqlist L){int i,j,k,temp;for(i=1;i<=L.length;i++){ k=i; //要确定排序元素的位置for(j=i+1;j<=L.length;j++){if(L.r[k].Key>L.r[j].Key) k=j; //若后面有更小的记录下其位置}temp=L.r[i].Key; 输出线性表LL.r[i].Key=L.r[k].Key;L.r[k].Key=temp;}//forprintf("选择排序:\n");output(L);}//SelectSort⑶主函数设计int main(){Sqlist L;Input(L); //输入要排的数字,创建线性表LBiInsertionsort(L); //对L进行插入排序, 输出线性表LBubbleSort(L); //对L进行交换排序,输出线性表LSelectSort(L); //对L进行选择排序, 输出线性表Lreturn ok;}四、程序调试分析1、由于本次实验中存储数据的线性表是在Input函数中进行的,所以开始时忘了将l.length初始化,出现报错,开始我直接在定义线性表的结构中赋值为MAXSIZE,还是有问题,原来是定义结构时不能直接在内部赋初值!通过这次错误让我对数组的用法有了一个更深的了解,实践后记得更深。
2、对于快速排序一直都不太理解,编译时出现了各种报错提示,后来我又回头仔仔细细的看了书上的内容,重新理解快排的算法思想,先设置枢轴,进行一趟简单的分大小,再进行递归调用,直到排序结束,重新写了一遍程序,调试了几次就成功了,对于快排有了一个较深的把握与理解。
3、一直对于快排的交换环节存有疑虑,当出现第一个比枢轴小的关键字时就进行这句L.r[low].Key=L.r[high].Key;原以为这样后low空间里的关键字被换成了high的了,那low 里的关键字就缺失了,但是调试却没有问题,经过单步运行后,发现原来low里的为枢轴量,放在了首单元地址里,后来又换回来了,所以没有缺失。
4、在选择排序中,刚开始我的程序是比较后就直接交换的,后来看书上是记住数组的下标全部比较后进行一次交换就可以了,少了不少的交换次数,效率提高了不少,让我看到了优化程序的重要性,在实现的基础上不断地去优化程序,让程序变得更好。
五、用户使用说明1、本程序的运行环境为DOS操作系统,执行文件为:排序.exe。
2、进入程序后,输入所需排序的十个整数,回车运行程序。
3、程序运行后即在屏幕上输出计算结果。
六、程序运行结果七、程序清单#include"stdio.h"/* 宏定义*/#define KeyType int#define MAXSIZE 10#define ok 1#define error 0/* 顺序存储结构*/typedef struct{KeyType Key;} RedType;typedef struct{RedType r[MAXSIZE+1];int length; // =MAXSIZE;} Sqlist;/* 输入数据*/int Input(Sqlist & L){for(int i=1;i<=MAXSIZE;i++)scanf("%d",&L.r[i].Key);L.length=MAXSIZE;return ok;}/* 输出排好的数字*/int output(Sqlist L){for(int i=1;i<=MAXSIZE;i++)printf("%-4d",L.r[i].Key);printf("\n");return ok;}/* 折半插入排序法*/void BiInsertionsort (Sqlist L){int i,j,low,high,m;for(i=2;i<=L.length;i++){L.r[0].Key=L.r[i].Key; //把要插入的当成哨兵low=1; high=i-1;while(low<=high) //折半法找到要插入的位置{m=(low+high)/2;if(L.r[0].Key<L.r[m].Key) high=m-1;else low=m+1;}for(j=i-1;j>=high+1;j--) //插入位置后的袁术后移一位L.r[j+1]=L.r[j];L.r[high+1]=L.r[0]; //插入元素}//lowprintf("折半插入排序:\n");output(L);}//BiInsertionsort/* 快速交换排序法*/int Partition(Sqlist &L,int low,int high){int pivotkey;L.r[0].Key=L.r[low].Key;//用子表的第一个记录作枢轴记录pivotkey=L.r[low].Key;//枢轴记录关键字while(low<high)//从表的两端交替地向中间扫描{while(low<high&&L.r[high].Key>=pivotkey){--high;//将比枢轴记录小的记录移到低端}//whileL.r[low].Key=L.r[high].Key;while(low<high&&L.r[low].Key<=pivotkey){++low;//将比枢轴记录大的记录移到高端}//whileL.r[high].Key=L.r[low].Key;}//whileL.r[low].Key=L.r[0].Key;//枢轴记录到位return low;//返回枢轴位置}//Partitionvoid QSort(Sqlist &L,int low,int high){int pivotloc;if(low<high)//长度大于1{pivotloc=Partition(L,low,high);//将L.r[low…high]一分为二QSort(L,low,pivotloc-1);//对低子表递归排序,pivotloc是枢轴位置QSort(L,pivotloc+1,high);//对高子表递归排序}//if}//QSortvoid QuickSort(Sqlist &L) //对顺序表L做快速排序{QSort(L,1,L.length);printf("交换排序:\n");output(L);}//QuickSort/* 选择排序法*/void SelectSort(Sqlist L){int i,j,k,temp;for(i=1;i<=L.length;i++){ k=i; //要确定排序元素的位置for(j=i+1;j<=L.length;j++){if(L.r[k].Key>L.r[j].Key) k=j; //若后面有更小的记录下其位置}temp=L.r[i].Key;L.r[i].Key=L.r[k].Key;L.r[k].Key=temp;}//forprintf("选择排序:\n");output(L);}//SelectSortint main(){Sqlist L;Input(L); //输入要排的数字BiInsertionsort(L);QuickSort(L);SelectSort(L);return ok;}。