《第一学期数据结构实验报告》由会员分享，可在线阅读，更多相关《第一学期数据结构实验报告（16页珍藏版）》请在金锄头文库上搜索。
1、2008-2009第一学期数据结构实验报告课件名称：数据结构用C语言描述 姓 名： 班 级：2007级信息1班 学 号： 指导老师： 实验日期：2008年12月17日 目录一、实验题目-1二、实验目的-1三、实验内容-1四、实验要求-1五、实验环境-1六、实验过程-1七、实验结果-9一、实验题目排序算法验证二、实验目的1掌握常用排序方法的基本思想及其实现技术2了解各种排序方法的优缺点和适用范围三、实验内容实现冒泡排序、直接插入排序、选择排序和快速排序，并比较各种排序算法的运行速度。四、实验要求1采用顺序表存放排序的记录，设关键字类型为典型。2设计一个菜单，以菜单方式选择上述排序方法。3程序执行
2、时，能按趟输出排序的结果。4对每种基本排序方法改进算法，再给出改进算法前后的实验结果：（1）随机生成10个随机数进行排序的结果；（2）分别给出升序和降序的随机数排序的结果。5对上述四种算法给出结论性意见，说明改进算法后的效果明显或不明显的原因。五、实验环境软件需求：C语言硬件需求：微型计算机六、实验过程1实验步骤（1）理解顺序表排序的基本实验原理；（2）仔细分析实验内容，给出其算法和流程图；（3）用C语言实现该算法；（4）给出测试数据，并分析其结果；（5）在实验报告册上写出实验过程。2算法步骤（1）文件的类型说明typedef struct keytype key; infotype othe
3、rinfo; rectype; typedef rectype seqlistn+1; （2）主函数调用void main() 生成需要排序的关键字，选择调用各排序的算法；（3）算法调用void insertsort(); 插入排序算法，输入趟数，按趟输出排序的结果；void rubblesort(); 起泡排序算法，输入趟数，按趟输出排序的结果；void quicksort(int low,int high); 快速排序算法，调用int partition(int i,int j)函数对Rlow到Rhigh做划分，输入趟数，按趟输出排序的结果；void selectsort(); 选择排序算
4、法，输入趟数，按趟输出排序的结果；（4）返回主函数3算法修改随机生成10个随机数进行升序和降序的随机数排序的程序如下：#include stdio.h#include stdlib.h1#define n 10 #define FALSE 0 #define TRUE 1 #define Maxsize 100typedef int keytype;typedef char infotype;typedef struct keytype key; infotype otherinfo; rectype; typedef rectype seqlistn+1;typedef rectype te
5、mlistn+1;int VMaxsizen+1;int m,num; int a=1,b=1;seqlist R;temlist T;void insertsort(); void rubblesort(); void quicksort(); void quicksort2();void selectsort(); int partition(int i,int j); int partition2(int i,int j);void main() seqlist s; temlist u; int i; char ch1,ch2; for(i=1;i=n;i+) si.key=rand(
6、)%1000; for(i=1;i=n;i+) ui.key=si.key; printf(Have generated randomly 10 sort numbers:n); for(i=1;i=n;i+)printf(%5d,si.key);printf(n); ch1=y; while(ch1=y|ch1=Y) printf(*Menu*n); printf(Please select option:n); printf( 1-Updata data-n); printf( 2-Insert sort-n); printf( 3-Rubble sort-n); printf( 4-Qu
7、ick sort-n); printf( 5-Select sort-n); printf( 6-Quit sort-n); 2 printf(Please select operating type:); scanf(n%c,&ch2); switch(ch2) case1: for(i=1;i=n;i+) si.key=rand()%1000; printf(Have again generated randomly 10 sort numbers:n); for(i=1;i=n;i+) printf(%5d,si.key); printf(n); for(i=1;i=n;i+) ui.k
8、ey=si.key; break; case2: printf(Please enter number of times for result:); scanf(%d,&m); for(i=1;i=n;i+) Ri.key=si.key; Ti.key=ui.key; insertsort(); break; case3: printf(Please enter number of times for result:); scanf(%d,&m); for(i=1;i=n;i+) Ri.key=si.key; Ti.key=ui.key; rubblesort(); break; case4:
9、 printf(Please enter number of times for result:); scanf(%d,&m); for(i=1;i=n;i+) Ri.key=si.key; Ti.key=ui.key; num=0; quicksort(1,n); quicksort2(1,n); break; case5: printf(Please enter number of times for result:); scanf(%d,&m); for(i=1;i=n;i+) Ri.key=si.key; 3 Ti.key=ui.key; selectsort(); break; case6: ch1=n; break; default: ch1=n; void insertsort() int i,j,k;for(i=2;i=n;i+) if(Ri.keyRi-1.key) R0=Ri; j=i-1; while(R0.keyTi-1.key) T0=Ti; j=i-1; while(T0.keyTj.key) Tj+1=Tj; j-; Tj+1=T0; if(i-1=m) printf(The ascending result is:%dn,m); for(k=1;k
