查找排序实验报告

1、编程实训实验报告书专 业：计算机科学与技术 班 级：151班 学 号： 姓 名： 指导教师： 日 期：2016年6月30日 目录一、需求分析31.任务要求32.软件功能分析33.数据准备3二、概要设计31.功能模块图42.模块间调用关系43.主程序模块54.抽象数据类型描述5三、详细设计61.存储结构定义62.各功能模块的详细设计7四、实现和调试71.主要的算法72.主要问题及解决83.测试执行及结果8五、改进9六、附录91.查找源程序92.排序源程序9 目录1 需求分析   1.1 任务要求 对于从键盘随机输入的一个序列的数据，存入

2、计算机内，给出各种查找算法的实现；以及各种排序算法的实现。1.2 软件功能分析任意输入n个正整数，该程序可以实现各类查找及排序的功能并将结果输出。1.3 数据准备任意输入了5个正整数如下：12 23 45 56 782 概要设计（如果2，3合并可以省略2.4）   2.1 功能模块图（注：含功能说明）2.2 模块间调用关系   2.3 主程序模块 2.4 抽象数据类型描述存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。又称为存储结构。数据类型（

3、data type）是一个“值”的集合和定义在此集合上的一组操作的总称。3 详细设计3.1 存储结构定义查找：typedef int ElemType ;/顺序存储结构typedef structElemType *elem; /数据元素存储空间基址，建表时按实际长度分配，号单元留空int length; /表的长度SSTable;排序：typedef struct /定义记录类型int key; /关键字项RecType;typedef RecType SeqListMax+1; /SeqList为顺序表，表中第0个元素作为哨兵3.2 各功能模块的详细设计查找：

4、void Create(SSTable *table, int length);/ 构建顺序表void FillTable(SSTable *table) / 无序表的输入int Search_Seq(SSTable *table, ElemType key);/哨兵查找算法void Sort(SSTable *table ) / 排序算法int Search_Bin(SSTable *table, ElemType key) / 二分法查找（非递归）排序：void InsertSort(SeqList R) /对顺序表R中的记录R1n按递增序进行插入排序void BubbleSort(Seq

5、List R) /自下向上扫描对R做冒泡排序int Partition(SeqList R,int i,int j)/对Rij做一次划分，并返回基准记录的位置void QuickSort(SeqList R,int low,int high) /Rlow.high快速排序void SelectSort(SeqList R) /直接选择排序void Heapify(SeqList R,int low,int high) /大根堆调整函数void MergePass(SeqList R,int length) /归并排序4 实现和调试4.1 主要的算法查找：建立顺序存储结构，构

6、建一个顺序表，实现顺序查找算法。 typedef struct ElemType *elem; /数据元素存储空间基址，建表时按实际长度分配，号单元留空 int length; /表的长度 SSTable; 对顺序表先排序后，实现行二分法查找相关操作。 定义二叉树节点，根据节点的值进行查找，并且实现节点的插入，删除等操作。 typedef struct BiTnode /定义二叉树节点 int data; /节点的值 struct BiTnode *lchild,*rchild; BiTnode,*BiTree; 定义哈希表以及要查找的节点元素，创建哈希表，实现其相关查找操作。 typedef

7、 struct int num; Elemtype; /定义查找的结点元素 typedef struct Elemtype *elem; /数据元素存储基址 int count; /数据元素个数 int sizeindex; HashTable;/定义哈希表排序：2. 排序相关实验内容及步骤。 定义记录类型。 typedef struct int key; /关键字项 RecType; 实现直接插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已排序好的子文件中的适当位置，直到全部记录插入完成为止。 实现冒泡排序：设想被排序的记录数组R1n垂直排序。根据轻气泡不能在重气泡之下的原则，从

8、下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“漂浮”（交换），如此反复进行，直到最后任意两个气泡都是轻者在上，重者在下为止。 实现快速排序：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录作为支点（又称基准记录）（pivot），将所有关键字比它小的记录放置在它的位置之前，将所有关键字比它大的记录放置在它的位置之后(称之为一次划分过程)。之后对所分的两部分分别重复上述过程，直到每部分只有一个记录为止。 实现直接选择排序：第i趟排序开始时，当前有序区和无序区分别为R1i-1和Rin（1in-1），该趟排序则是从当前无序区中选择出关键字最小的记录Rk，将它与无序区的的第一个

9、记录Ri交换，有序区增加一个记录，使R1i,和Ri+1n分别为新的有序区和新的无序区。如此反复进行，直到排序完毕。 实现堆排序：它是一种树型选择排序，特点是：在排序的过程中，将R1n看成是一个完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的记录。即：把待排序文件的关键字存放在数组R1n子中，将R看成是一棵二叉树，每个结点表示一个记录，源文件的第一个记录R1作为二叉树的根，以下各记录R2n依次逐层从左到右排列，构成一棵完全二叉树，任意结点Ri的左孩子是R2i，右孩子是R2i+1，双亲是Ri/2。 实现二路归并排序：假设初始序列n

10、个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如此重复，直到一个长度为n的有序序列为止。4.2 主要问题及解决在实验前对于各种查找和排序的算法不是很熟悉，所以花了一些时间去复习。有些代码反复测试还是找不出错误，最后也是翻阅了书本并仔细思考才改进了算法并成功测试出了结果。这次试验大大提升了我对排序算法及查找算法的熟练程度。4.3 测试执行及结果查找算法：任意输入若干正整数并测试如下：排序算法：任意输入数字并测试如下：5 改进根据提示的代码，经过一系列调试后最终出了结果。在一开始运行时总是出错

11、，特别是二叉树的测试，代码有些小错误导致测试的时候程序总是出错。最后改动了一下提高了程序的稳定性并成功运行出了结果。6 附录【附录1-查找源程序】#include"iostream"#include"stdlib.h"#include"stdio.h"#include "malloc.h"#define MAX 11 using namespace std;typedef int ElemType ;/顺序存储结构typedef structElemType *elem; /数据元素存储空间基址，建表时按实际长度分

12、配，号单元留空int length; /表的长度SSTable; void Create(SSTable *table, int length);void Destroy(SSTable *table);int Search_Seq(SSTable *table, ElemType key);void Traverse(SSTable *table, void (*visit)(ElemType elem);void Create(SSTable *table, int length) / 构建顺序表 SSTable *t = (SSTable*) malloc(sizeof(SSTable)

13、;/分配空间t->elem=(ElemType*)malloc(sizeof(ElemType)*(length+1);t->length=length;*table=t;void FillTable(SSTable *table) / 无序表的输入ElemType *t=table->elem; for(int i=0; i<table->length; i+) /for循环，输入各个元素t+;scanf("%d", t); /输入元素getchar();void Destroy(SSTable *table) / 销毁表 free(tabl

14、e->elem);/释放元素空间free(table);/释放表的空间void PrintTable(SSTable *table) / 打印查找表 int i; /定义变量ElemType *t=table->elem;for(i=0; i<table->length; i+) /进入循环，依次打印表中元素 t+;printf("%d ", *t); /打印输出printf("n");int Search_Seq(SSTable *table, ElemType key) /哨兵查找算法table->elem0=key;

15、/设置哨兵int result=0; / 找不到时，返回int i;for (i=table->length; i>=1;i-) if (table->elemi=key) result=i;break;return result; /返回结果void printSeq()SSTable *table; /先设置几个变量int r;intn;ElemType key;printf("请输入元素个数:"); scanf("%d",&n); /输入元素个数Create(&table, n); /建立表printf("

16、;请输入");cout<<n;printf("个值：");FillTable(table); /输入无序表的值printf("您输入的%d 个值是：n",n);PrintTable(table); /打印无序表printf("请输入关键字的值:");scanf("%d",&key);printf("n");printf("顺序查找法运行结果如下：nn ");Search_Seq(table,key); /哨兵查找算法r=Search_Seq(ta

17、ble,key);if(r>0)printf(" 关键字%d 在表中的位置是：%dn",key, r);/打印关键字在表中的位置printf("n");else /查找失败printf ("查找失败，表中无此数据。nn");void Sort(SSTable *table ) / 排序算法 int i, j;ElemType temp; for (i=table->length; i>=1 ;i-) / 从前往后找 for (j=1; j<i; j+)if(table->elemj>table-&g

18、t;elemj+1)temp=table->elemj;table->elemj=table->elemj+1;table->elemj+1=temp; int Search_Bin(SSTable *table, ElemType key) / 二分法查找（非递归）int low=1;int high=table->length;int result=0; / 找不到时，返回while(low <= high) /low不大于high时int mid=(low+high)/2;if(table->elemmid=key) /如果找到result=mi

19、d;break;else if(key<table->elemmid) /如果关键字小于mid对应的值high=mid-1;else low=mid+1;return result; /返回结果void printBin()SSTable *table; /声明变量int r;intn;ElemType key;printf("请输入元素个数:");scanf("%d",&n);Create(&table, n); /建立表printf("请输入");cout<<n;printf("个

20、值：");FillTable(table); /输入无序表的值printf("您输入的%d 个值是：n",n);PrintTable(table); /打印无序表printf("请输入关键字的值:");scanf("%d",&key);printf("n");Sort(table); /对无序表进行排序printf("数据排序后的顺序如下：nn ");PrintTable(table); /打印有序表printf("n");printf("二分查找

21、法的运行结果如下：nn ");r=Search_Bin(table,key); /二分（非递归）查找算法if( r>0)printf("关键字%d 在表中的位置是：%dn",key, r);else printf ("查找失败，表中无此数据。nn");/二叉排序树typedef struct BiTnode /定义二叉树节点int data; /节点的值struct BiTnode *lchild,*rchild; /节点的左孩子，节点的右孩子BiTnode,*BiTree;/查找（根据节点的值查找）返回节点指针BiTree search

22、_tree(BiTree T,int keyword,BiTree *father)BiTree p; / 临时指针变量*father = NULL; /先设其父亲节点指向空p = T; /p赋值为根节点（从根节点开始查找）while (p && p->data!=keyword) /如果不是p不指向空且未找到相同值的节点*father = p;/先将父亲指向自己（注意：这里传过来的father是二级指针）if (keyword < p->data) /如果要找的值小于自己的值p = p->lchild; / 就向自己的左孩子开始找elsep = p-&

23、gt;rchild; /否则向自己的右孩子开始查找return p; /如果找到了则返回节点指针BiTree creat_tree(int count)BiTree T,p; /设置两个临时变量T,pint i = 1;while (i <= count)if (i = 1) /如果i=1，说明还是空树p = (BiTnode *)malloc(sizeof(BiTree);/使p指向新分配的节点if (!p)/分配未成功return NULL;T = p;/分配成功,T=p( 这里实际上T就是根节点)scanf("%d",&p->data);/输入p指

24、向节点的值p->lchild = p->rchild = NULL;/p的左孩子和右孩子都指向空i+;elseint temp;/ 如果不是空树scanf("%d",&temp);/输入节点的值search_tree(T,temp,&p);/查找节点要插入的位置。（T是根节点，插入的节点的值，父亲节点的地址）if (temp < p->data)/如果插入的值小于父亲节点的值p->lchild = (BiTnode *)malloc(sizeof(BiTnode);/那么就为父亲节点的左孩子分配一个节点空间，并指向这个空间if

25、(!p->lchild)return NULL;p = p->lchild;/分配成功，p指向自己的左孩子else/ 如果插入的值大于父亲节点的值p->rchild = (BiTnode *)malloc(sizeof(BiTnode);if (!p->rchild)return NULL;/分配不成功，退出p = p->rchild;/p指向自己的右孩子p -> data = temp;/新分配的节点的值赋值为插入的值p -> lchild = p->rchild = NULL;/使其左右节点均为NULLi+;return T;/返回根节点vo

26、id InOrder(BiTree T)if(T)InOrder(T->lchild);printf("%d ",T->data);InOrder(T->rchild);int insert_tree(BiTree *T,int elem)/插入（根节点，插入的值）返回-1和,-1代表插入失败，代表成功BiTree s,p,father;s = (BiTnode *)malloc(sizeof(BiTnode);/s指向新开辟一个节点if (!s)/为开辟成功return -1;/ 返回值-1s->data = elem;/新节点的值赋值为插入的值s

27、->lchild = s->rchild = NULL;/其左右孩子为空p = search_tree(*T,elem,&father);/p赋值为要插入的节点if (!p)return -1;/未开辟成功，返回-1if (father = NULL)/如果父亲节点指向空，说明是空树*T = s;/让根节点指向selse if (elem < father->data)/否则如果插入的值小于父亲的值father->lchild = s;/父亲的左孩子赋值为selsefather->rchild = s;/否则父亲的右孩子赋值为sreturn 0;/返

28、回int delete_tree(BiTree *T,int elem) /删除树结点的操作BiTree s,p,q,father;/声明变量p = search_tree(*T,elem,&father);/查找if(!p)return -1;if(!p->lchild)/如果p的左孩子为空if (father = NULL)*T = p->rchild;/T指向左孩子free(p);/释放preturn 0;if (p = father->lchild)/如果p和father的左孩子相等father->lchild = p->rchild; /将p的左

29、孩子的值赋给father的左孩子elsefather->rchild = p->rchild;/将p的左孩子的值赋给father的右孩子free(p);/释放preturn 0;elseif(!p->rchild)if (father = NULL)/如果father为空*T = p->lchild;/将p的左孩子赋给Tfree(p);/释放preturn 0;if (p = father->lchild)/如果p等于father的左孩子的值father->lchild = p->lchild; /将p的左孩子的值赋给father的左孩子elsefat

30、her->rchild = p->lchild; /将p的左孩子的值赋给father的右孩子free(p);return 0;elseq = p;s = p->lchild;/将p的左孩子赋给swhile (s->rchild)q = s;s = s->rchild;p->data = s->data;/将s的值赋给pif (q != p)/如果q不等于pq->rchild = s->lchild; /将s的左孩子值赋给p的右孩子elseq->lchild = s->lchild; /将s的左孩子值赋给p的右孩子free(s);

31、/释放sreturn 0;void print1() /定义print1（）以便调用printf("t*n");printf("t1,输出中序遍历n");printf("t2,插入一个结点n");printf("t3,删除一个结点n");printf("t4,查找一个结点n");printf("t5,返回主菜单n");printf("t*n");void printTree()BiTree T,p; /声明变量T=NULL;inti,n;ElemType

32、key;printf("请输入结点个数：n");scanf("%d",&n);/输入值printf("请输入");cout<<n;printf("个值：");T=creat_tree(n);/建立树print1();scanf("%d",&i);/输入各个值while(i!=5)/i不等于5时switch(i)case 1:printf("中序遍历二叉树结果如下：n");InOrder(T);/中序遍历break;case 2:printf(&qu

33、ot;请输入要插入的结点值：");scanf("%d",&key);/输入要查找的关键字if(insert_tree(&T,key)/如果插入成功printf("插入成功！");elseprintf("已存在此元素！");break;case 3:printf("请输入要删除的结点值：");scanf("%d",&key); /输入要删除的关键字if(!(delete_tree(&T,key)/如果删除成功printf("删除成功！"

34、);elseprintf("不存在此元素！");break;case 4:printf("请输入要查找的结点值：");scanf("%d",&key); /输入要查找的关键字if(search_tree(T,key,&p)/如果查找成功printf("查找成功！");elseprintf("不存在此元素！");break;default:printf("按键错误！");printf("n");print1();scanf("%d&

35、quot;,&i);/哈希表typedef struct int num; Elemtype;/定义查找的结点元素typedef struct Elemtype *elem; /数据元素存储基址int count; /数据元素个数int sizeindex; HashTable;/定义哈希表int Hash(int num) int p; p=num%11; return p; /定义哈希函数/冲突处理函数，采用二次探测再散列法解决冲突int collision(int p,int &c)int i,q;i=c/2+1;while(i<MAX)if(c%2=0)c+;q=

36、(p+i*i)%MAX;if(q>=0) return q;else i=c/2+1;elseq=(p-i*i)%MAX;c+;if(q>=0)return q;elsei=c/2+1;return 0;void InitHash(HashTable *H)/创建哈希表 int i; H->elem=(Elemtype *)malloc(MAX*sizeof(Elemtype); H->count=0; H->sizeindex=MAX; for(i=0;i<MAX;i+) H->elemi.num=0;/初始化，使SearHash函数能判断到底有没有

37、元素在里面 int SearHash(HashTable H,int key,int *p)/查找函数 *p=Hash(key); while(H.elem*p.num!=key&&H.elem*p.num!=0) *p=*p+1; if(H.elem*p.num=key) return 1; else return 0; void InsertHash(HashTable *H,Elemtype e) /如果查找不到就插入元素int p; SearHash(*H,e.num,&p); /查找H->elemp=e; +H->count; void print

38、Hash()/调用哈希表 HashTable H; int p,key,i,n; Elemtype e; InitHash(&H);printf("输入数据个数(<11 ):");scanf("%d",&n);printf("请输入各个值：");for(i=0;i<n;i+) /输入n个元素scanf("%d",&e.num);/输入数字if(!SearHash(H,e.num ,&p) InsertHash(&H,e );/插入元素 else printf(&q

39、uot;已经存在n");/否则就表示元素的数字已经存在 printf("输入查找的数字:"); scanf("%d",&key);/输入要查找的数字if(SearHash(H,key,&p)/能查找成功 printf("查找成功！");/输出位置 else printf(" 不存在此元素！"); void print()printf("t*n");printf("t1,顺序查找n");printf("t2,二分查找n");prin

40、tf("t3,二叉排序树n");printf("t4,哈希查找n");printf("t5,退出n");printf("t*n");printf("请选择查找方式：n");/ 主函数int main(int argc, char* argv)int i;/定义变量print();scanf("%d",&i);/输入要数字选择要使用的查找方法while(i!=5)/i不等于5时switch(i) case 1:/i=1时printf("顺序查找法：n"

41、;);printSeq();/顺序查找法break;/跳出循环case 2:printf("二分查找法：n");printBin();/二分查找法break; /跳出循环case 3:printf("二叉排序树：n");printTree();/二叉排序树break; /跳出循环case 4:printf("哈希查找法：n");printHash();/哈希查找法break; /跳出循环default:printf("按键错误！");printf("n");print();/调用函数print(

42、)scanf("%d",&i);return 0;/返回0【附录2-排序源程序】#include <stdio.h>#include <stdlib.h>#include <string.h>#define Max 100 typedef struct /定义记录类型int key; /关键字项RecType;typedef RecType SeqListMax+1; /SeqList为顺序表，表中第0个元素作为哨兵int n; /顺序表实际的长度/1、 直接插入排序的基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已排

43、序好的子文件中的适当位置，直到全部记录插入完成为止。/=直接插入排序法=void InsertSort(SeqList R) /对顺序表R中的记录R1n按递增序进行插入排序 int i,j;for(i=2;i<=n;i+) /依次插入R2，Rnif(Ri.key<Ri-1.key) /若Ri.key大于等于有序区中所有的keys，则Ri留在原位 R0=Ri;j=i-1; /R0是Ri的副本 do /从右向左在有序区R1i-1中查找Ri 的位置 Rj+1=Rj; /将关键字大于Ri.key的记录后移 j-; while(R0.key<Rj.key); /当Ri.keyRj.ke

44、y 是终止Rj+1=R0; /Ri插入到正确的位置上/2、 冒泡排序的基本思想：设想被排序的记录数组R1n垂直排序。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"（交换），如此反复进行，直到最后任意两个气泡都是轻者在上，重者在下为止。/=冒泡排序=typedef enumFALSE,TRUE Boolean; /FALSE为0，TRUE为1void BubbleSort(SeqList R) /自下向上扫描对R做冒泡排序int i,j; Boolean exchange; /交换标志 for(i=1;i<n;i+)

45、 /最多做n-1趟排序exchange=FALSE; /本趟排序开始前，交换标志应为假for(j=n-1;j>=i;j-) /对当前无序区Rin 自下向上扫描if(Rj+1.key<Rj.key) /两两比较，满足条件交换记录R0=Rj+1; /R0不是哨兵，仅做暂存单元Rj+1=Rj;Rj=R0;exchange=TRUE; /发生了交换，故将交换标志置为真if(! exchange) /本趟排序未发生交换，提前终止算法return; /3、 快速排序的基本思想：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录作为支点（又称基准记录）（pivot），将所有关键字比它

46、小的记录放置在它的位置之前，将所有关键字比它大的记录放置在它的位置之后(称之为一次划分过程)。之后对所分的两部分分别重复上述过程，直到每部分只有一个记录为止。/1.=一次划分函数=int Partition(SeqList R,int i,int j) /对Rij做一次划分，并返回基准记录的位置 RecType pivot=Ri; /用第一个记录作为基准while(i<j) /从区间两端交替向中间扫描，直到i=jwhile(i<j &&Rj.key>=pivot.key) /基准记录pivot相当与在位置i上j-; /从右向左扫描，查找第一个关键字小于pivot.key的记录Rjif(i<j) /