综合算法设计实验报告学生学号学生实验报告书实验课程名称应用数据结构开课学院指导教师姓名学生姓名学生专业班级2012 — 2013 学年第 2 学期实验项目名称综合算法设计同组者无实验日期2013年 06 月 18日第一部分：实验预习报告1、实验目的、意义1)掌握查找的含义2)掌握基本查找操作的算法和实现3)掌握动态查找算法的实现、应用场合与优缺点4)能够针对具体问题，灵活选用适宜的查找算法5)掌握排序的基本概念，对排序的稳定性及排序的时间复杂度有深刻的认识6)对比折半插入排序和Shell排序的异同7)掌握选择排序中堆排序的基本思想和算法实现8)掌握快速排序的基本思想和算法实现9)了解归并排序算法的基本思想和程序实现10)了解基数排序算法的基本思想和程序实现11)掌握Hash排序算法的基本思想和程序实现12)在上述内容的基础上，将所有查找及排序算法整合在一个程序中2、实验基本原理与方法本实验涉及各类查找和排序算法。

静态查找，折半查找的思想为：设查找表中的元素存放在数组r中，数据元素的下标范围为[low, high]，要查找的关键字值为key，中间元素的下标为mid=|_(low + high) /2_|（向下取整），令key与r[mid]的关键字比较：①若key=r[mid].key，查找成功，下标为m的记录即为所求，返回mid。

②若key<r[mid].key，所要找的记录只能在左半部分记录中，再对左半部分使用折半查找法继续进行查找，搜索区间缩小了一半。

③若key>r[mid].key，所要找的记录只能在右半部分记录中，再对右半部分使用折半查找法继续进行查找，搜索区间缩小了一半。

重复上述过程，直到找到查找表中某一个数据元素的关键字的值等于给定的值key，说明查找成功；或者出现low的值大于high的情况，说明查找不成功。

动态查找，编程实现一个开放式的高校本科招生最低录取分数线的查询系统，供师生和家长等查询，高校自愿放入该校的信息，可能随时有高校加入。

要求实现的查询功能有：①查询等于用户给定分数的高校；②查询大于（或小于）用户给定分数的高校③查询最低录取分数线在用户给定的分数段中的高校。

直接插入排序：将当前无序区的第一个记录插入到有序区中适当位置。

折半查找法：在有序表中进行，先确定表的中点位置，再通过比较确定下一步查找哪个半区。

Shell排序：先取定一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一个组中，在各组内进行直接插入排序；然后取第二个增量重复上述分组和排序，直至所取的增量dt =1(dt<dt-1<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

堆排序是利用大顶堆（或小顶堆）来选取当前无序区中关键字最大（或最小）的记录实现排序快速排序是对冒泡法的改进，其基本思想是：通过一趟排序将待排文件分割成独立的两部分，其中一部分记录的关键字值均比另一部分记录的关键字小，然后分别对这两部分进行排序，以达到整个序列有序。

归并的思想：将两个或两个以上的有序表合并成一个有序表。

利用归并的思想实现排序，假设初始的序列含有n个记录，可以看成n个有序的子序列，每个子序列的长度为m，然后把i(≥2)个子序列归并，得到n/i个长度为i的子序列；再继续归并，如此重复直到得到一个长度为n的有序序列为止。

通常使用的是i=2的二路归并法。

基数排序的基本思想是采用多关键字的排序。

设记录关键字R[i]由d个分量ki 1, ki2, …, kid组成，设每个分量的取值范围为{ti|i=1, 2, …, m，且t1<t2<…<tm}。

准备m个箱子，先按低位分箱再按序号一次将各个非空箱子里的记录收集起来，再对新收集起来的元素依次按较高的位分箱，直到最高位。

分箱即将第s个关键字等于ti的全部记录装入第i个箱子里。

按最高位分箱后，按序号一次将各个非空箱子里的记录收集起来，得到的元素序列就是有序的。

Hash排序是在Hash查找的基础上演变而来。

对待排序列采用单调的Hash函数，并用链地址法处理冲突，最后用一定规则收集存储好的数据从而得到有序序列。

3、主要仪器设备及耗材安装有VC++ 6.0运行环境的电脑，无耗材要求。

4、实验方案或技术路线本实验含有五部分内容——静态查找、动态查找、插入排序与选择排序、快速排序与归并排序、查找及排序算法集成。

A．静态查找部分查找表的存储结构为有序表，即表中记录按关键字大小排序存放。

输入待查数据元素的关键字进行查找。

为了简化算法，记录只含一个整型量关键字字段，记录的其余数据部分忽略不考虑。

此程序中要求对整型量关键字数据的输入按从小到大排序输入。

B．动态查找部分主要的功能是查找，查找表为高校最低录取分数信息的集合。

根据题意可知，该查找表中的元素个数可能随时增减，所以它是一个动态查找表，可采用树状结构保存。

为了提高查询速度，可建立二叉排序树并在二叉排序树中实现查找。

C．排序部分考虑对20个整数的随机输入进行排序，各排序功能基本上都可以成为独立调用的模块，因此可以先写出排序算法，然后用主函数调用。

D．查找及排序算法集成部分此部分需要学生自行设计，本指导书不给出具体算法。

第二部分：实验过程记录实验原始记录（包括实验数据记录，实验现象记录，实验过程发现的问题等）1．概要设计（说明本程序中用到的所有抽象数据类型的定义，主程序的流程以及各程序模块之间的层次或调用关系）1.1抽象数据类型：队列：ADT Queue{数据对象：D＝{ ai | ai∈ElemSet, i=1,2,...,n, n≥0 }数据关系：R1＝{ <ai-1, ai>|ai-1, ai∈D, i=2,...,n }基本操作：void init_Q(Queue &Q);操作结果：构造空队列Qint Q_empty(Queue Q);初始条件：队列Q存在操作结果：若Q为空队列，则返回TRUE,否则FALSEint Q_length(Queue Q);初始条件：队列Q存在操作结果：返回队列Q的元素个数，即队列长度int gethead_Q(Queue Q);初始条件：队列Q存在操作结果：返回队列Q的队头元素void en_Q(Queue &Q,int e);初始条件：队列Q存在操作结果：插入元素e为Q的新的队尾元素。

void de_Q(Queue &Q,int &e);初始条件：队列Q存在操作结果：删除Q的队头元素。

}ADT Queue线性表：ADT List{数据对象：D={ai|1<=i<=n,n>=o,ai属于elementtype类型}数据关系：R={<ai，ai+1>|ai,ai+1属于D,i=1,...,n-1}基本运算：InitList(&l)DestroyList(&l);......}图：ADT Graph{数据对象：D={ai|1<=i<=n,n>=0,ai属于ELEMTYPE类型}类型标识符数据关系：R={<ai,aj>|ai,aj属于D,1<=i<=n,1<=j<=n,其中每个元素可以有零个或多个直接前驱，可以有多个直接后继}基本运算：InitGraph(&g)ClearGraph(&g)DFS(g)BFS(g)...}1.2小问题：A .随机数的产生：srand（）函数用于设置随机数种，rand（）用于产生一个随机数。

B.数据的储存：由于100000个int型数的数组，所以我采用了malloc（）函数来动态分配一数组存储它。

对于一些特别大的数据可以用文件存储，在采用外排序的方式排序。

C.屏幕上无法显示100000条数据，故将数据存储在两个文本文件中。

一个是没排好序的，另一个是排好序后的数据。

1.3主要数据结构设计：归并排序：typedef int KeyType;typedef int DataType;typedef struct{ KeyType key; /* 排序码字段 *//*DataType info; 记录的其它字段 */ } RecordNode;typedef struct{ int n; /* n为文件中的记录个数，n<MAXNUM */RecordNode record[MAXNUM]; } SortObject;基数排序:typedef int KeyType;typedef int DataType;typedef struct Node RadixNode;struct Node{ KeyType key[D];/* DataType info;*/RadixNode *next;};typedef RadixNode *RadixList;typedef struct QueueNode{ RadixNode *f; /* 队列的头指针 */RadixNode *e; /* 队列的尾指针 */}Queue;Hash排序：typedef struct hnode{ int data;struct hnode *next;}HNODE;typedef struct point{ struct hnode *pt;}POINT;1.4主程序流程：主程序main（）输入随机数产生随机数，并存在选择排序方法1.折2.希尔3.堆4.快速5.归并选择排序方法，并存在queue.txt文退出程序6.基数7.哈希主函数在main.cpp 中，排序算法的在各自的头文件中。

选择排序方法后，调用选择的排序方法。

1．5各函数调用关系：2．详细设计（实现程序模块的具体算法）2.1主函数： void main() {int *p,n,way,dlta[4]={5,3,2,1},L=11; long i;FILE *fp,*fp1;if(!(fp=fopen("queue.txt","w+")))printf("打开文件 queue.txt 失败!"); if(!(fp1=fopen("nonqueue.txt","w+")))printf("打开文件 nonqueue.txt 失败!"); printf("请输入随机种子:\n"); scanf("%d",&n);p=(int *)malloc(MAX*sizeof(int)); for(i=1;i<MAX;i++) {p[i]=rand();fprintf(fp1,"%-8d",p[i]); }maiBinsertSShellSoHeapSoQuickS mergeSoRadixSfopefclosran sranPartitShellInsfclose(fp1);printf("\n\t\t ******************************************\n"); printf("\t\t| 请选择排序方式 |\n"); printf("\t\t| |\n"); printf("\t\t| 1.折半插入排序算法 |\n"); printf("\t\t| 2.希尔排序算法 |\n"); printf("\t\t| 3:堆排序算法 |\n"); printf("\t\t| 4.快速排序算法 |\n"); printf("\t\t| 5.归并排序算法 |\n"); printf("\t\t| 6.基数排序算法 |\n"); printf("\t\t| 7.哈希排序算法 |\n"); printf("\t\t| 0.退出程序 |\n"); printf("\t\t ******************************************\n"); printf("请输入你的选择：\n");scanf("%d",&way);switch(way){case 0:exit(1);case 1:BinsertSort(p, MAX-1);break;case 2:ShellSort(p,MAX-1,dlta,4);break;case 3:HeapSort(p,MAX-1);break;case 4: QuickSort(p,MAX-1);break;case 5:{vector.n = MAX-1;for(i=0;i<MAX-1;i++)vector.record [i].key =p[i+1];mergeSort(&vector);for(i=0;i<MAX-1;i++)fprintf(fp,"%-8d",vector.record [i].key );fclose(fp);exit(1);}case 6:{RadixList hp;for(i=0;i<MAX-1;i++){element[i].key[0]=0;element[i].key[1]=p[i+1]/10000%10;element[i].key[2]=p[i+1]/1000%10;element[i].key[3]=p[i+1]/100%10;element[i].key[4]=p[i+1]/10%10;element[i].key[5]=p[i+1]%10;element[i].next=NULL;}for (i=0; i<MAX-1; i++)element[i].next=&element[i+1];element[MAX-1].next=NULL;hp=element;radixSort(&hp,6,10);hp=hp->next;while(hp){fprintf(fp,"%-8d",hp->key[1]*10000+hp->key[2]*1000+hp->key[3]*100+ hp->key[4]*10+hp->key[5]);hp=hp->next;}fclose(fp);exit(1);}case 7:HashSort(p,MAX-1,MAX-1);break;}for(i=1;i<MAX;i++)fprintf(fp,"%-8d",p[i]);fclose(fp);}2.2各排序算法：(1)归并排序：#define MAX 100001#define MAXNUM 100001#define TRUE 1#define FALSE 0typedef int KeyType;typedef int DataType;typedef struct{ KeyType key; /* 排序码字段 *//*DataType info; 记录的其它字段 */ } RecordNode;typedef struct{ long n; /* n为文件中的记录个数，n<MAXNUM */RecordNode record[MAXNUM]; } SortObject;void merge(RecordNode r[], RecordNode r1[], long low, long m, long high){ long i=low, j=m+1, k=low;while ( i<=m &&j<=high ) /* 反复复制两个段的第一个记录中较小的 */if (r[i].key<=r[j].key) r1[k++]=r[i++];else r1[k++]=r[j++];while (i<=m) r1[k++]=r[i++]; /* 复制第一个段的剩余记录 */while (j<=high) r1[k++]=r[j++];/* 复制第二个段的剩余记录 */}/* 对 r 做一趟归并，结果放到 r1 中 */void mergePass(RecordNode r[], RecordNode r1[], long n, long length) { long i=0, j; /* length为本趟归并的有序子段的长度 */ while (i+2*length-1<n){ merge(r,r1,i,i+length-1,i+2*length-1); /*归并长length的两个子段*/i+=2*length; }if(i+length-1<n-1) /* 剩下两段，后一段长度小于length */merge(r, r1, i, i+length-1, n-1);else for(j=i; j<n; j++) r1[j]=r[j]; /* 将剩下的一段复制到数组r1 */ }void mergeSort(SortObject * pvector){ RecordNode record[MAXNUM];long length = 1;while (length<pvector->n) /*一趟归并，结果存放在数组record中*/ { mergePass(pvector->record, record, pvector->n, length);length*=2;/* 一趟归并，结果存回 */mergePass(record, pvector->record, pvector->n, length);length *= 2; }}SortObject vector ;(2)折半插入排序：void BinsertSort(int D[], long L){ long i, j, l, r, m;for (i=2; i<=L; i++){ D[0]=D[i];l=1;r=i-1;while (l<=r) { m=(l+r)/2;if(D[0]<D[m]) r=m-1;else l=m+1; }for (j=i-1; j>=r+1; j--) D[j+1]=D[j];D[r+1]=D[0]; }}(3)Shell排序：void ShellInsert(int D[], long L, long dk){ long i, j;for (i=dk+1; i<=L; i+=dk)if ( D[i]<D[i-dk] ){ D[0]=D[i];for (j=i-dk; j>0 && D[0]<D[j]; j=j-dk) D[j+dk]=D[j];D[j+dk]=D[0]; }}void ShellSort (int D[], long L, int dlta[], long t){ long k;for (k=0; k<t; k++) ShellInsert(D, L, dlta[k]);}(4)堆排序算法：void HeapAdjust(int D[], long s, long m){ long j;D[0]=D[s];for (j=2*s; j<=m; j*=2){ if (j<m && D[j]<D[j+1]) j++; /* j指向结点值大的孩子 */if (D[0]>=D[j]) break; /* 已经符合堆定义，无须浪费时间 */D[s]=D[j];s=j; } /* 交换，并使s指向新堆 */D[s]=D[0]; /* 找到合适的地点就将原堆顶元装进去 */}void HeapSort(int D[], long L){ long i;for (i=L/2; i>0; i--) HeapAdjust(D, i, L); /* 将原始序列调整为堆 */ for (i=L; i>1; i--) { D[0]=D[1];D[1]=D[i];D[i]=D[0];HeapAdjust(D, 1, i-1); }}(5)快速排序算法：int Partition(int D[], long l, long r){ D[0]=D[l];while (l<r) { while (l<r && D[0]<D[r]) r--;D[l]=D[r];while (l<r && D[0]>=D[l]) l++;D[r]=D[l]; }D[r]=D[0];return r;}void Qsort(int D[], long l, long r){ long p;if (l<r) { p=Partition(D, l, r);Qsort(D, l, p-1);Qsort(D, p+1, r); }}void QuickSort(int D[], long L){ Qsort(D, 1, L);}(6)基数排序：typedef int KeyType;typedef int DataType;typedef struct Node RadixNode;struct Node{KeyType key[6];/* DataType info;*/RadixNode *next;};typedef RadixNode *RadixList;typedef struct QueueNode{RadixNode *f; /* 队列的头指针 */RadixNode *e; /* 队列的尾指针 */}Queue;Queue queue[10];void radixSort(RadixList *plist, int d, int r){int i,j,k;RadixNode *p, *head=(*plist)->next;for(j=d-1; j>=0; j--) /* 进行d次分配和收集*/{p=head;for(i=0; i<r; i++){queue[i].f=NULL;queue[i].e =NULL; } /* 清队列 */while(p){k=p->key[j]; /* 按排序码的第j个分量进行分配*/if (!queue[k].f)queue[k].f=p; /* 若第k个队列空，当前记录为队首*/else(queue[k].e)->next=p; /* 否则当前记录链接到第k队的队尾*/queue[k].e=p;p=p->next; }for(i=0; queue[i].f==NULL; i++) ; /* 找出第一个非空队列*/p=queue[i].e;head=queue[i].f; /* head为收集链表的头指针*/for(i++; i<r; i++)if(queue[i].f != NULL){p->next=queue[i].f; /* 收集非空队列 */p=queue[i].e;}p->next=NULL;}(*plist)->next=head;}struct Node element[MAX-1]={0,0,0,0,0,0,NULL,/*表头*/0,0,0,0,3,6,NULL,/*36*/0,0,0,0,0,5,NULL,/*5*/0,0,0,0,1,6,NULL,/*16*/0,0,0,0,9,8,NULL,/*98*/0,0,0,0,9,5,NULL,/*95*/0,0,0,0,4,7,NULL,/*47*/0,0,0,0,3,2,NULL,/*32*/0,0,0,0,3,6,NULL,/*36*/0,0,0,0,4,8,NULL,/*48*/0,0,0,0,1,0,NULL /*10*/};(7)Hash排序:typedef struct hnode{int data;struct hnode *next;}HNODE;typedef struct point{struct hnode *pt;}POINT;void HashSort(int D[],int L,int m){HNODE *h,*g;POINT *p;int i,j;p=(POINT *)calloc(m,sizeof(POINT));for (i=0; i<m; i++)(p+i)->pt=NULL;for (i=1; i<=L; i++){j=D[i]/2;h=(HNODE *)malloc(sizeof(HNODE));h->data=D[i];h->next=NULL;if ((p+j)->pt){g=(p+j)->pt;if (g->data>h->data){h->next=g;(p+j)->pt=h;}else{while (g->next){if(g->next->data<=h->data) g=g->next;else{h->next=g->next;break;}}g->next=h;}}else (p+j)->pt=h;}j=0;h=p->pt;for(i=1;i<=L;){while(h){D[i++]=h->data;h=h->next;}free((p+j++)->pt);h=(p+j)->pt;}free(p);}3．调试分析（内容包括：a）调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；b)算法的时空分析——包括基本操作和相关算法的时间复杂度和空间复杂度的分析以及改进设想；c) 经验和体会等）3.1调试过程中的问题及解决方案：在本次程序的编写和调试过程中，我曾多次修改代码，并根据调试显示的界面一次次调整代码。