第一篇：北邮数据结构实验报告-排序
北京邮电大学 数据结构试验报告
实验名称： 实验四
排序 学生姓名：
班
级：
班内序号：
学
号：
日
期： 2014年1月4日
实验目的
学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。实验内容
2.1 题目1 使用简单数组实现下面各种排序算法，并进行比较。排序算法：
1、插入排序
2、希尔排序
3、冒泡排序
4、快速排序
5、简单选择排序
6、堆排序（选作）
7、归并排序（选作）
8、基数排序（选作）
9、其他
要求：
1、测试数据分成三类：正序、逆序、随机数据
2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）
4、对2和3的结果进行分析，验证上述各种算法的时间复杂度
编写测试main()函数测试线性表的正确性。程序分析
3.1 存储结构
顺序存储结构——数组
3.2 关键算法分析
1.插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕
void Insertsort(int r[],int n,int* compare,int* move)//插入排序 {
*compare=0;*move=0;int i;int j;for(i=1;i
(*compare)++;
(*move)++;
r[j+1]=r[j];} if(j>=0)(*compare)++;r[j+1]=x;} } 2.希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序 void ShellInsert(int r[],int n,int* compare,int* move)//希尔排序 {
*compare=0;*move=0;int j;10 9 12 12 20 20 31 for(int d=n/2;d>=1;d=d/2)//间距越来越小 { for(int i=d;i<=n-1;i++)//从a[d]往后逐个元素确定是否需要前移 { if(r[i] { int x=r[i]; for(j=i-d;(j>=0)&&(x { (*compare)++; (*move)++; r[j+d]=r[j]; } if(j>=0)(*compare)++; r[j+d]=x;} else(*compare)++;} } } 3.冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止 void Bubblesort(int r[],int n,int* compare,int* move)//交换（冒泡）排序 { *compare=0;*move=0;int x;for(int j=0;j for(int i=n-1;i>j;i--) { if(r[i] { (*compare)++; (*move)+=3; x=r[i]; r[i]=r[i-1]; r[i-1]=x; } else(*compare)++; } } } 4.快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则大于基准，然后对两部分重复上述过程，直至整个序列排序完成 int Partion(int r[],int first,int end,int* compare,int* move)//快速排序中的轴定位 { int i=first;int j=end;int zhou=r[i];//默认第一个元素为轴 while(i { (*compare)++; j--;} if(i r[i]=r[j];//发现轴右侧的某数比轴值小，将其前置 } while((i (*compare)++; (*move)++; r[j]=r[i];//发现轴左侧的某数比轴值小，将其后置 } } r[i]=zhou;//最后确定轴的位置 return i;} void Qsort(int r[],int i,int j,int* compare,int* move)//快速排序 { if(i int min=i; for(int j=i+1;j { (*compare)++; if(r[j] min=j;//记录下当前找到的最小值的位置 } if(min!=i) {(*move)+=3; int Min; Min=r[min]; r[min]=r[i]; r[i]=Min; } } } 程序运行结果 4.1主函数流程图 4.2程序运行框图 实验心得 1.调试时出现的问题及解决的方法 在初期构思代码的时候，首先构造了各种算法的基本实现代码，封装成类，已经能够实现七种排序的基本功能，并且测试无误。 之后考虑如何能简化代码以实现多达七种排序算法的简单调用、乱序和顺序以及逆序数据的分别排序和性能指标统计（算法移动次数和比较次数的精确统计）。2.心得体会 程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。3.改进 本程序代码设计时运用了递归的调用方式，效率还可以通过将其转换为栈模拟的方式得以提高。另外还可以进一步考虑算法时间的精确统计，以便从时间角度比较这几种排序算法的优劣。 完整源代码 #include void Insertsort(int r[],int n,int* compare,int* move);void ShellInsert(int r[],int n,int* compare,int* move);void Bubblesort(int r[],int n,int* compare,int* move);int Partion(int r[],int first,int end,int* compare,int* move);void Qsort(int r[],int i,int j,int* compare,int* move);void Selectsort(int r[],int n,int* compare,int* move); void Insertsort(int r[],int n,int* compare,int* move)//插入排序 { *compare=0; { } } void ShellInsert(int r[],int n,int* compare,int* move)//希尔排序 { int x=r[i];for(j=i-1;x } if(j>=0)(*compare)++;r[j+1]=x;(*move)++;r[j+1]=r[j];*move=0;int i;int j;for(i=1;i (*compare)++; *compare=0; { for(int i=d;i<=n-1;i++)//从a[d]往后逐个元素确定是否需要前移 { } } } void Bubblesort(int r[],int n,int* compare,int* move)//交换（冒泡）排序 { { for(int i=n-1;i>j;i--) { if(r[i] { (*compare)++; (*move)+=3;*compare=0;*move=0;int x;if(r[i] int x=r[i]; for(j=i-d;(j>=0)&&(x }(*compare)++;(*compare)++;(*move)++;r[j+d]=r[j];*move=0;int j;for(int d=n/2;d>=1;d=d/2)//间距越来越小 if(j>=0) r[j+d]=x;} else(*compare)++;for(int j=0;j x=r[i]; r[i]=r[i-1]; r[i-1]=x; } } else(*compare)++; } } int Partion(int r[],int first,int end,int* compare,int* move)//快速排序中的轴定位 { int i=first;int j=end;int zhou=r[i];//默认第一个元素为轴 while(i { } if(i } if(i r[i]=r[j];//发现轴右侧的某数比轴值小，将其前置 (*move)++; r[j]=r[i];//发现轴左侧的某数比轴值小，将其后置 } } r[i]=zhou;//最后确定轴的位置 return i;} void Qsort(int r[],int i,int j,int* compare,int* move)//快速排序 { if(i void Selectsort(int r[],int n,int* compare,int* move)//选择排序 { { int min=i; for(int j=i+1;j { (*compare)++; if(r[j] min=j;//记录下当前找到的最小值的位置 } if(min!=i) {(*move)+=3; int Min; Min=r[min]; r[min]=r[i]; r[i]=Min; } } } void main(){ int i;int compare=0;int move=0;cout<<“请您先输入一个正序数组哦”< 北京邮电大学 数据结构试验报告 实验名称： 实验一 线性表 学生姓名： 班 级： 班内序号： 学 号： 日 期： 2014年1月3日 实验目的 熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 实验内容 2.1题目1 根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。 线性表存储结构（五选一）： 1、带头结点的单链表 2、不带头结点的单链表 3、循环链表 4、双链表 5、静态链表 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。程序分析 3.1 存储结构 单链表的存储结构： 3.2 关键算法分析 一、关键算法 1.头插法 自然语言描述：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.修改新结点的指针域 d.修改头结点的指针域,将新结点加入链表中 代码描述： template front = new Node } } s->next = front->next;front->next = s;时间复杂度：O(n) 2.尾插法 自然语言描述：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 代码描述: template front = new Node } } s->data = a[i];s->next = r->next;r->next= s;r=s;时间复杂度：O(n) 3.析构函数 自然语言描述：a.新建立一个指针，指向头结点 b.移动a中建立的指针 c.逐个释放指针 代码描述: template Node } } delete front;4.按位查找函数 自然语言描述: a.初始化工作指针p和计数器j，p指向第一个结点，j=1 b.循环以下操作，直到p为空或者j等于1 b1：p指向下一个结点 b2：j加1 c.若p为空，说明第i个元素不存在，抛出异常 d.否则，说明p指向的元素就是所查找的元素，返回元素地址 代码描述: template Node if(j } else break;p = p->next;j++; } if(!p)throw“查找位置非法”;else return p;} 时间复杂度：O(n) 5.按值查找函数 自然语言描述：a.初始化工作指针p和计数器j，p指向第一个结点，j=1 b.循环以下操作，找到这个元素或者p指向最后一个结点 b1.判断p指向的结点是不是要查找的值，如果是，返回j; b2.否则p指向下一个结点,并且j的值加一 c.如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息 代码描述: template Node } return-1;if(p->data == x)return j;else { p = p->next; j++;} } 时间复杂度：O(n)6.插入函数 自然语言描述： a.在堆中建立新结点 b.将要插入的结点的数据写入到新结点的数据域 c.修改新结点的指针域 d.修改前一个指针的指针域，使其指向新插入的结点的位置 代码描述: template Node } else throw“插入位置非法”;Node 自然语言描述：a.从第一个结点开始，查找要删除的位数i前一个位置i-1的结点 b.设q指向第i个元素 c.将q元素从链表中删除 d.保存q元素的数据 e.释放q元素 代码描述: template T x=q->data; } p->next = q->next;delete q;return x; 8.遍历打印函数 自然语言描述: a.判断该链表是否为空链表，如果是，报错 b.如果不是空链表，新建立一个temp指针 c.将temp指针指向头结点 d.打印temp指针的data域 e.逐个往后移动temp指针，直到temp指针的指向的指针的next域为空 代码描述: template } Node } cout< 自然语言描述： a.判断该链表是否为空链表，如果是，输出长度0 b.如果不是空链表，新建立一个temp指针，初始化整形数n为0 c.将temp指针指向头结点 d.判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return n e.使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n 代码描述: template } Node } return i-1;p = p->next;i++;4 程序运行结果 4.1主函数流程图 4.2程序运行框图 实验心得 1.调试时出现的问题及解决的方法 在编写按值查找函数时，由于没有处理好指针类型的原因，导致指针无法正常返回，屡屡报错。最后意识到c++没有指针强制类型的转换机制，经过细致检查后才改正错误使得程序正常运行。2.心得体会 了解了单链表的基本的操作函数实现，对链式存储结构有了较好的认识 3.下一步的改进 可以增加完善报错机制，增强程序的健壮性 完整源代码 #include template }; template }; //template Node template } template } template } front = p;p = p->next;delete front;front = new Node } Node } Node } Node } cout< template } template } Node } return-1;if(p->data == x)return j;else { } p = p->next; j++;Node } if(!p)throw“查找位置非法”;else return p;if(j } else break;p = p->next;j++; template } template } template } void main(){ Node } return i-1;p = p->next;i++;Node } else throw“插入位置非法”;Node T x=q->data; } int n;cout<<“将要输入的链表长度为：”;cin>>n;int *b=new int[n];cout<<“输入链表中的元素：”;for(int k=0;k 《数据结构》实验报告 排序 实验题目： 输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路： 1.插入排序：直接插入排序的基本操作是，将一个记录到已排好序的有序表中，从而得到一个新的，记录增一得有序表。 一般情况下，第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列r［1..i-1］中插入一个记录r［i］后，变成含有i个记录的有序子序列r［1..i］；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在 r［0］处设置哨兵。在自i-1起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。 2.快速排序：基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序的序列为{L.r[s]，L.r[s+1],„L.r[t]},首先任意选取一个记录(通常可选第一个记录L.r[s])作为枢轴（或支点）（pivot），然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所罗的位置i作为界线，将序列{L.r[s]，„，L.r[t]}分割成两个子序列{L.r[i+1],L.[i+2],„,L.r[t]}。这个过程称为一趟快速排序，或一次划分。 一趟快速排序的具体做法是：附设两个指针low和high，他们的初值分别为low和high，设枢轴记录的关键字为pivotkey，则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相 1 交换，重复这两不直至low=high为止。 具体实现上述算法是，每交换一对记录需进行3次记录移动（赋值）的操作。而实际上，在排列过程中对枢轴记录的赋值是多余的，因为只有在一趟排序结束时，即low=high的位置才是枢轴记录的最后位置。由此可以先将枢轴记录暂存在r[0]的位置上，排序过程中只作r[low]或r[high]的单向移动，直至一趟排序结束后再将枢轴记录移至正确位置上。 整个快速排序的过程可递归进行。若待排序列中只有一个记录，显然已有序，否则进行一趟快速排序后再分别对分割所得的两个子序列进行快速排序。 3.简单选择排序：其操作为，通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1≤i≤n）个记录交换之。 显然，对L.r[1„n]中的记录进行简单选择排序的算法为：令i从1至n-1，进行n-1趟选择操作。可以看出，简单选择排序过程中，所需进行记录移动的操作次数较少，其最小值为“0”，最大值为3（n-1）。然后，无论记录的初始排列如何，所需进行的关键字之间的比较次数相同，均为n(n-1)/2。 程序清单： 1．插入排序： #include for(i=1;i<=num.length;i++)printf(“%d ”,num.key[i]);} 测试用例： 输入：23 34 12 98 56 45 67 8 9 37 输出：charu：8 9 12 23 34 37 45 56 67 98 2快速排序： #include for(i=1;i<=num.length;i++)printf(“%d ”,num.key[i]);} 测试用例： 输入：23 34 12 98 56 45 67 8 9 37 输出：charu：8 9 12 23 34 37 45 56 67 98 3选择排序： #include intselectminkey(structsqlist *l,int a){ inti,j=a;for(i=a;i<=l->length;i++)if(l->key[i] for(i=1;i<=num.length;i++)printf(“%d ”,num.key[i]);} 测试用例： 输入：23 34 12 98 56 45 67 8 9 37 输出：charu：8 9 12 23 34 37 45 56 67 98 编程感想： 本次编程总共使用了三种排序方法，而这三种编程方法放在一起进行编写时，很容易就让我们对齐难易程度有了更深刻的了解。 首先，三种排序中，我们都像查表那样，设置了哨兵，而哨兵的使用可以减少对整个表的验空操作，使程序更加节省空间。 其次，对于插入排序，每次都要对一段序列进行检索，每排一次所要检索的序列长度减一，其时间发杂度为O（n^2）。 接着，对于快速排序，这个程序是比较复杂的，总共是3个函数，并且使用了递归的方法，这是但是，这种算法却是最优越的，平均性能也是最好的，我在编这个程序时，对其排序的思想有了进一步的了解，并努力拿他与冒泡排序进行比较，看出了些许其优越性。 还有，就是选择排序，简单选择排序思路简单，易于进行，但其时间发杂度与简单插入排序方法一样，都是O（n^2），性能不如快速排序。 最后，本次试验是数据结构课的最后一次实验，经过数据结构试验课的锻炼，使我对数据结构有了更深刻的理解，对我对其知识起到了重要的影响，增加了我编程的实践活动，为我将来进一步学习打下了基础。 一、实验目的 1、了解内排序都是在内存中进行的。 2、为了提高数据的查找速度，需要对数据进行排序。 3、掌握内排序的方法。 二、实验内容 1、设计一个程序exp10—1.cpp实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。 （1）源程序如下所示： //文件名:exp10-1.cpp #include //线性表中最多元素个数 typedef int KeyType;typedef char InfoType[10];typedef struct //记录类型 { KeyType key; //关键字项 InfoType data;//其他数据项,类型为InfoType } RecType;void InsertSort(RecType R[],int n)//对R[0..n-1]按递增有序进行直接插入排序 { int i,j,k;RecType temp;for(i=1;i { temp=R[i]; j=i-1; //从右向左在有序区R[0..i-1]中找R[i]的插入位置 while(j>=0 && temp.key { R[j+1]=R[j];//将关键字大于R[i].key的记录后移 j--; } R[j+1]=temp; //在j+1处插入R[i] printf(“i=%d,”,i);//输出每一趟的排序结果 printf(“插入%d,结果为: ”,temp); for(k=0;k printf(“%3d”,R[k].key); printf(“n”);} } void main(){ int i,k,n=10; KeyType a[]={9,8,7,6,5,4,3,2,1,0};RecType R[MAXE];for(i=0;i R[i].key=a[i];printf(“初始关键字: ”);//输出初始关键字序列 for(k=0;k printf(“%3d”,R[k].key);printf(“n”);InsertSort(R,n);printf(“最后结果: ”);//输出初始关键字序列 for(k=0;k printf(“%3d”,R[k].key);printf(“n”);}（2）运行的结果如下图所示： 2、设计一个程序exp10—2.cpp实现希尔插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。 （1）源程序如下所示： //文件名:exp10-2.cpp #include //线性表中最多元素个数 typedef int KeyType;typedef char InfoType[10];typedef struct //记录类型 { KeyType key;//关键字项 InfoType data;//其他数据项,类型为InfoType } RecType;void ShellSort(RecType R[],int n)//希尔排序算法 { int i,j,d,k;RecType temp;d=n/2; //d取初值n/2 while(d>0) { for(i=d;i { j=i-d; while(j>=0 && R[j].key>R[j+d].key) { temp=R[j]; //R[j]与R[j+d]交换 R[j]=R[j+d]; R[j+d]=temp; j=j-d; } } printf(“d=%d: ”,d);//输出每一趟的排序结果 for(k=0;k printf(“%3d”,R[k].key); printf(“n”); d=d/2; //递减增量d } } void main(){ int i,k,n=10;KeyType a[]={9,8,7,6,5,4,3,2,1,0};RecType R[MAXE];for(i=0;i R[i].key=a[i];printf(“初始关键字: ”);//输出初始关键字序列 for(k=0;k printf(“%3d”,R[k].key);printf(“n”);ShellSort(R,n);printf(“最后结果: ”); //输出初始关键字序列 for(k=0;k printf(“%3d”,R[k].key);printf(“nn”);}（2）结果如下图所示： 3、设计一个程序exp10—3.cpp实现冒泡排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。 （1）源程序如下所示： //文件名:exp10-3.cpp #include //线性表中最多元素个数 typedef int KeyType;typedef char InfoType[10];typedef struct //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据项,类型为InfoType } RecType;void BubbleSort(RecType R[],int n)//冒泡排序算法 { int i,j,k;RecType temp;for(i=0;i { for(j=n-1;j>i;j--)//比较,找出本趟最小关键字的记录 if(R[j].key { temp=R[j];//R[j]与R[j-1]进行交换,将最小关键字记录前移 R[j]=R[j-1]; R[j-1]=temp; } printf(“i=%d,冒出的最小关键字:%d,结果为: ”,i,R[i].key);//输出每一趟的排序结果 for(k=0;k printf(“%2d”,R[k].key); printf(“n”);} } void main(){ int i,k,n=10;KeyType a[]={9,8,7,6,5,4,3,2,1,0};RecType R[MAXE];for(i=0;i R[i].key=a[i];printf(“初始关键字: ”);//输出初始关键字序列 for(k=0;k printf(“%2d”,R[k].key);printf(“n”);BubbleSort(R,n);printf(“最后结果: ”);//输出初始关键字序列 for(k=0;k printf(“%2d”,R[k].key);printf(“n”);}（2）结果如下图所示： 电 子 科 技 大 学 实 验 报 告 学生姓名：XXX 学 号：20*** 指导教师：刘峤 实验地点：信软机房306 实验时间：2014/6/20 一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法—排序与查找 三、实验学时：4 四、实验原理： 快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是： 1）设置两个变量I、J，排序开始的时候I：=1，J：=N 2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]； 3）从J开始向前搜索，即（J：=J-1），找到第一个小于X的值，两者交换； 4）从I开始向后搜索，即（I：=I+1），找到第一个大于X的值，两者交换； 5）重复第3、4步，直到I=J。 二分法查找（折半查找）的基本思想： （1）确定该区间的中点位置：mid=（low+high）/2 min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置 （2）将待查a值与结点mid的关键字（下面用R[mid].key）比较，若相等，则查找成功，否则确定新的查找区间： A)如果R[mid].key>a，则由表的有序性可知，R[mid].key右侧的值都大于a，所以等于a的关键字如果存在，必然在R[mid].key左边的表中,这时high=mid-1; B)如果R[mid].key C)如果R[mid].key=a，则查找成功。 （3）下一次查找针对新的查找区间，重复步骤（1）和（2） （4）在查找过程中，low逐步增加，high逐步减少，如果high 五、实验目的： 本实验通过实现快速排序和折半查找算法，使学生理解如何实现快速查找和排序的基本算法思想。通过练习，加强对算法的理解，提高编程能力。 六、实验内容： （1）实现数据序列的输入; （2）实现快速排序算法,并对输入的序列排序后输出； （3）实现折半查找算法,并在步骤(2)排序后的序列上,进行任意地 查找,并输出查询结果。 七、实验器材（设备、元器件）： 八、数据结构及程序 #include #define MAX_LEN 100 void Sort(int *data,int left,int right){ int i,j,temp; i=left; j=right; temp=data[left]; if(left>right) return; while(i!=j){ while(data[j]>=temp&&j>i) j--; if(j>i) data[i++]=data[j]; while(data[i]<=temp&&j>i) i++; if(j>i) data[j--]=data[i]; } data[i]=temp; Sort(data,left,i-1);PC机一台，装有C/C++语言集成开发环境。 Sort(data,i+1,right);} int Search(int *data,int start,int end,int key,int num){ int result; int p =(start + end)/ 2; if(data[p] == key&&start<=end){ result = p; num++; if(data[p] > key) result = Search(data, start, p, key,num); else result = Search(data, p + 1, end, key,num); return result; } else if(num==0&&start>end){ result =-1; printf(“n 404 NO FOUNDn”); return result; } else if(num!=0&&start>end){ result=-1; if(num==1) printf(“nFounded number only one”); else printf(“nFounded number more than one”); return result; } else if(result!=-1){ if(data[p] > key) result = Search(data, start, p-1, key, num); else result = Search(data, p + 1, end, key, num); return result; } else { result=-1; return result; } } void loadFile(int *data,char *filename,int n){ int i; FILE *pfile=NULL; pfile=fopen(filename,“r”); if(!pfile){ printf(“Open file failn”); exit(0); } else printf(“Open file success!n”); for(i = 0;i < n;i++) fscanf(pfile , “%d ”,&data[i]);} int main(int argc, const char * argv[]){ int input=1,data[MAX_LEN],num=0,key=1,i,cmd; char filename[100]; printf(“Choose Mode :n 1.Input Mode 2.File Moden”); scanf(“%d”,&cmd); if(cmd==1){ printf(“Input data :(Enter 0 to detemine)n”); while(input!=0){ printf(“Enter the %d data :”,num+1); scanf(“%d”,&input); if(input!=0){ data[num]=input; num++; } } } else{ printf(“nInput the address of the file: ”); scanf(“%s”,filename); printf(“nInput the number of elem: ”); scanf(“%d”,&num); loadFile(data,filename,--num); } Sort(data, 0, num); printf(“nSort result: ”); for(i=1;i<=num;i++) printf(“%d ”,data[i]); printf(“nn”); while(key!=0){ printf(“nInput a key to search :(Enter 0 to detemine)”); scanf(“%d”,&key); if(key!=0) Search(data, 0, num, key, 0); } return 0;} 九、程序运行结果： 1.打开程序： 2.尝试手动输入模式： 3.搜索已存在数： 4.搜索不存在数： 5.尝试文件读入模式并搜索 实验成功。 十、实验结论： 使用好的排序与查找算法对于程序的运行效率至关重要，一个好的算法，适合的算法能使计算机对数据的处理事半功倍，而选用错误的算法，不但可能事倍功半，还有可能造成不稳定因素。 快速排序的时间复杂度为n（log2n）,是排序算法中最为快速的一种，但是不稳定，对基本有序的序列效率较差。 二分查找算法在查找算法中，速度快，效率高，但是要求数据要有序。 十一、总结及心得体会： 当空间充足，对稳定性要求不高的情况，排序算法宜使用快速排序。 快速排序和二分查找配合，可以以较高的效率查找目标元素。第三篇：《数据结构》实验报告——排序
第四篇：数据结构内排序实验报告
第五篇：数据结构实验报告-排序与查找
鲁公网安备37028302000876号