查找排序实验报告讲解.docx
- 文档编号:11396219
- 上传时间:2023-05-31
- 格式:DOCX
- 页数:41
- 大小:242.13KB
查找排序实验报告讲解.docx
《查找排序实验报告讲解.docx》由会员分享,可在线阅读,更多相关《查找排序实验报告讲解.docx(41页珍藏版)》请在冰点文库上搜索。
查找排序实验报告讲解
《编程实训》
实验报告书
专业:
计算机科学与技术
班级:
151班
学号:
姓名:
指导教师:
日期:
2016年6月30日
目录
一、需求分析…………………………………………………………………………………3
1.任务要求……………………………………………………………………………………3
2.软件功能分析………………………………………………………………………………3
3.数据准备……………………………………………………………………………………3
二、概要设计…………………………………………………………………………………3
1.功能模块图………………………………………………………………………………4
2.模块间调用关系…………………………………………………………………………4
3.主程序模块………………………………………………………………………………5
4.抽象数据类型描述…………………………………………………………………………5
三、详细设计…………………………………………………………………………………6
1.存储结构定义………………………………………………………………………………6
2.各功能模块的详细设计……………………………………………………………………7
四、实现和调试………………………………………………………………………………7
1.主要的算法………………………………………………………………………………7
2.主要问题及解决…………………………………………………………………………8
3.测试执行及结果……………………………………………………………………………8
五、改进………………………………………………………………………………………9
六、附录……………………………………………………………………………………9
1.查找源程序………………………………………………………………………………9
2.排序源程序………………………………………………………………………………9
目录
1 需求分析
1.1 任务要求
对于从键盘随机输入的一个序列的数据,存入计算机内,给出各种查找算法的实现;以及各种排序算法的实现。
1.2 软件功能分析
任意输入n个正整数,该程序可以实现各类查找及排序的功能并将结果输出。
1.3 数据准备
任意输入了5个正整数如下:
1223455678
2 概要设计(如果2,3合并可以省略2.4)
2.1 功能模块图(注:
含功能说明)
2.2 模块间调用关系
2.3 主程序模块
2.4 抽象数据类型描述
存储结构:
数据结构在计算机中的表示(也称映像)叫做物理结构。
又称为存储结构。
数据类型(datatype)是一个“值”的集合和定义在此集合上的一组操作的总称。
3 详细设计
3.1 存储结构定义
查找:
typedefintElemType;
//顺序存储结构
typedefstruct
{
ElemType*elem;//数据元素存储空间基址,建表时按实际长度分配,号单元留空
intlength;//表的长度
}SSTable;
排序:
typedefstruct
{//定义记录类型
intkey;//关键字项
}RecType;
typedefRecTypeSeqList[Max+1];//SeqList为顺序表,表中第0个元素作为哨兵
3.2 各功能模块的详细设计
查找:
voidCreate(SSTable*table,intlength);//构建顺序表
voidFillTable(SSTable*table)//无序表的输入
intSearch_Seq(SSTable*table,ElemTypekey);//哨兵查找算法
voidSort(SSTable*table)//排序算法
intSearch_Bin(SSTable*table,ElemTypekey)//二分法查找(非递归)
排序:
voidInsertSort(SeqListR)//对顺序表R中的记录R[1‥n]按递增序进行插入排序
voidBubbleSort(SeqListR)//自下向上扫描对R做冒泡排序
intPartition(SeqListR,inti,intj)//对R[i‥j]做一次划分,并返回基准记录的位置
voidQuickSort(SeqListR,intlow,inthigh)//R[low..high]快速排序
voidSelectSort(SeqListR)//直接选择排序
voidHeapify(SeqListR,intlow,inthigh)//大根堆调整函数
voidMergePass(SeqListR,intlength)//归并排序
4 实现和调试
4.1 主要的算法
查找:
①建立顺序存储结构,构建一个顺序表,实现顺序查找算法。
typedefstruct{
ElemType*elem;//数据元素存储空间基址,建表时按实际长度分配,号单元留空
intlength;//表的长度
}SSTable;
②对顺序表先排序后,实现行二分法查找相关操作。
③定义二叉树节点,根据节点的值进行查找,并且实现节点的插入,删除等操作。
typedefstructBiTnode{//定义二叉树节点
intdata;//节点的值
structBiTnode*lchild,*rchild;
}BiTnode,*BiTree;
④定义哈希表以及要查找的节点元素,创建哈希表,实现其相关查找操作。
typedefstruct{
intnum;
}Elemtype;//定义查找的结点元素
typedefstruct{
Elemtype*elem;//数据元素存储基址
intcount;//数据元素个数
intsizeindex;
}HashTable;//定义哈希表
排序:
2.排序相关实验内容及步骤。
①定义记录类型。
typedefstruct{
intkey;//关键字项
}RecType;
②实现直接插入排序:
每次将一个待排序的记录,按其关键字大小插入到前面已排序好的子文件中的适当位置,直到全部记录插入完成为止。
③实现冒泡排序:
设想被排序的记录数组R[1‥n]垂直排序。
根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上“漂浮”(交换),如此反复进行,直到最后任意两个气泡都是轻者在上,重者在下为止。
④实现快速排序:
在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录作为支点(又称基准记录)(pivot),将所有关键字比它小的记录放置在它的位置之前,将所有关键字比它大的记录放置在它的位置之后(称之为一次划分过程)。
之后对所分的两部分分别重复上述过程,直到每部分只有一个记录为止。
⑤实现直接选择排序:
第i趟排序开始时,当前有序区和无序区分别为R[1‥i-1]和R[i‥n](1≤i≤n-1),该趟排序则是从当前无序区中选择出关键字最小的记录R[k],将它与无序区的的第一个记录R[i]交换,有序区增加一个记录,使R[1‥i],和R[i+1‥n]分别为新的有序区和新的无序区。
如此反复进行,直到排序完毕。
⑥实现堆排序:
它是一种树型选择排序,特点是:
在排序的过程中,将R[1‥n]看成是一个完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关键字最大(或最小)的记录。
即:
把待排序文件的关键字存放在数组R[1‥n]子中,将R看成是一棵二叉树,每个结点表示一个记录,源文件的第一个记录R[1]作为二叉树的根,以下各记录R[2‥n]依次逐层从左到右排列,构成一棵完全二叉树,任意结点R[i]的左孩子是R[2i],右孩子是R[2i+1],双亲是R[i/2]。
⑦实现二路归并排序:
假设初始序列n个记录,则可看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到[n/2]个长度为2或1的有序子序列;再两两归并,……,如此重复,直到一个长度为n的有序序列为止。
4.2 主要问题及解决
在实验前对于各种查找和排序的算法不是很熟悉,所以花了一些时间去复习。
有些代码反复测试还是找不出错误,最后也是翻阅了书本并仔细思考才改进了算法并成功测试出了结果。
这次试验大大提升了我对排序算法及查找算法的熟练程度。
4.3 测试执行及结果
查找算法:
任意输入若干正整数并测试如下:
排序算法:
任意输入数字并测试如下:
5 改进
根据提示的代码,经过一系列调试后最终出了结果。
在一开始运行时总是出错,特别是二叉树的测试,代码有些小错误导致测试的时候程序总是出错。
最后改动了一下提高了程序的稳定性并成功运行出了结果。
6附录
【附录1----查找源程序】
#include"iostream"
#include"stdlib.h"
#include"stdio.h"
#include"malloc.h"
#defineMAX11
usingnamespacestd;
typedefintElemType;
//顺序存储结构
typedefstruct
{
ElemType*elem;//数据元素存储空间基址,建表时按实际长度分配,号单元留空
intlength;//表的长度
}SSTable;
voidCreate(SSTable*table,intlength);
voidDestroy(SSTable*table);
intSearch_Seq(SSTable*table,ElemTypekey);
voidTraverse(SSTable*table,void(*visit)(ElemTypeelem));
voidCreate(SSTable**table,intlength)//构建顺序表
{
SSTable*t=(SSTable*)malloc(sizeof(SSTable));//分配空间
t->elem=(ElemType*)malloc(sizeof(ElemType)*(length+1));
t->length=length;
*table=t;
}
voidFillTable(SSTable*table)//无序表的输入
{
ElemType*t=table->elem;
for(inti=0;i
{
t++;
scanf("%d",t);//输入元素
getchar();
}
}
voidDestroy(SSTable*table)//销毁表
{
free(table->elem);//释放元素空间
free(table);//释放表的空间
}
voidPrintTable(SSTable*table)//打印查找表
{
inti;//定义变量
ElemType*t=table->elem;
for(i=0;i
{
t++;
printf("%d",*t);//打印输出
}
printf("\n");
}
intSearch_Seq(SSTable*table,ElemTypekey)//哨兵查找算法
{
table->elem[0]=key;//设置哨兵
intresult=0;//找不到时,返回
inti;
for(i=table->length;i>=1;i--)
{
if(table->elem[i]==key)
{
result=i;
break;
}
}
returnresult;//返回结果
}
voidprintSeq()
{
SSTable*table;//先设置几个变量
intr;
intn;
ElemTypekey;
printf("请输入元素个数:
");
scanf("%d",&n);//输入元素个数
Create(&table,n);//建立表
printf("请输入");cout< "); FillTable(table);//输入无序表的值 printf("您输入的%d个值是: \n",n); PrintTable(table);//打印无序表 printf("请输入关键字的值: "); scanf("%d",&key); printf("\n"); printf("顺序查找法运行结果如下: \n\n"); Search_Seq(table,key);//哨兵查找算法 r=Search_Seq(table,key); if(r>0) { printf("关键字%d在表中的位置是: %d\n",key,r);//打印关键字在表中的位置 printf("\n"); } else//查找失败 { printf("查找失败,表中无此数据。 \n\n"); } } voidSort(SSTable*table)//排序算法 { inti,j; ElemTypetemp; for(i=table->length;i>=1;i--)//从前往后找 { for(j=1;j { if(table->elem[j]>table->elem[j+1]) { temp=table->elem[j]; table->elem[j]=table->elem[j+1]; table->elem[j+1]=temp; } } } } intSearch_Bin(SSTable*table,ElemTypekey)//二分法查找(非递归) { intlow=1; inthigh=table->length; intresult=0;//找不到时,返回 while(low<=high)//low不大于high时 { intmid=(low+high)/2; if(table->elem[mid]==key)//如果找到 { result=mid; break; } elseif(key { high=mid-1; } else { low=mid+1; } } returnresult;//返回结果 } voidprintBin() { SSTable*table;//声明变量 intr; intn; ElemTypekey; printf("请输入元素个数: "); scanf("%d",&n); Create(&table,n);//建立表 printf("请输入");cout< "); FillTable(table);//输入无序表的值 printf("您输入的%d个值是: \n",n); PrintTable(table);//打印无序表 printf("请输入关键字的值: "); scanf("%d",&key); printf("\n"); Sort(table);//对无序表进行排序 printf("数据排序后的顺序如下: \n\n"); PrintTable(table);//打印有序表 printf("\n"); printf("二分查找法的运行结果如下: \n\n"); r=Search_Bin(table,key);//二分(非递归)查找算法 if(r>0) printf("关键字%d在表中的位置是: %d\n",key,r); else { printf("查找失败,表中无此数据。 \n\n"); } } //二叉排序树 typedefstructBiTnode//定义二叉树节点 { intdata;//节点的值 structBiTnode*lchild,*rchild;//节点的左孩子,节点的右孩子 }BiTnode,*BiTree; //查找(根据节点的值查找)返回节点指针 BiTreesearch_tree(BiTreeT,intkeyword,BiTree*father) { BiTreep;//临时指针变量 *father=NULL;//先设其父亲节点指向空 p=T;//p赋值为根节点(从根节点开始查找) while(p&&p->data! =keyword)//如果不是p不指向空且未找到相同值的节点 { *father=p;//先将父亲指向自己(注意: 这里传过来的father是二级指针) if(keyword p=p->lchild;//就向自己的左孩子开始找 else p=p->rchild;//否则向自己的右孩子开始查找 } returnp;//如果找到了则返回节点指针 } BiTreecreat_tree(intcount) { BiTreeT,p;//设置两个临时变量T,p inti=1; while(i<=count) { if(i==1)//如果i=1,说明还是空树 { p=(BiTnode*)malloc(sizeof(BiTree));//使p指向新分配的节点 if(! p)//分配未成功 returnNULL; T=p;//分配成功,T=p(这里实际上T就是根节点) scanf("%d",&p->data);//输入p指向节点的值 p->lchild=p->rchild=NULL;//p的左孩子和右孩子都指向空 i++; } else { inttemp;//如果不是空树 scanf("%d",&temp);//输入节点的值 search_tree(T,temp,&p);//查找节点要插入的位置。 (T是根节点,插入的节点的值,父亲节点的地址) if(temp { p->lchild=(BiTnode*)malloc(sizeof(BiTnode));//那么就为父亲节点的左孩子分配一个节点空间,并指向这个空间 if(! p->lchild) returnNULL; p=p->lchild;//分配成功,p指向自己的左孩子 } else//如果插入的值大于父亲节点的值 { p->rchild=(BiTnode*)malloc(sizeof(BiTnode)); if(! p->rchild) returnNULL;//分配不成功,退出 p=p->rchild;//p指向自己的右孩子 } p->data=temp;//新分配的节点的值赋值为插入的值 p->lchild=p->rchild=NULL;//使其左右节点均为NULL i++; } } returnT;//返回根节点 } voidInOrder(BiTreeT) { if(T) { InOrder(T->lchild); printf("%d",T->data); InOrder(T->rchild); } } intinsert_tree(BiTree*T,intelem)//插入(根节点,插入的值)返回-1和,-1代表插入失败,代表成功 { BiTrees,p,father; s=(BiTnode*)malloc(sizeof(BiTnode));//s指向新开辟一个节点 if(! s)//为开辟成功 return-1;//返回值-1 s->data=elem;//新节点的值赋值为插入的值 s->lchild=s->rchild=NULL;//其左右孩子为空 p=search_tree(*T,elem,&father);//p赋值为要插入的节点 if(! p) return-1;//未开辟成功,返回-1 if(father==NULL)//如果父亲节点指向空,说明是空树 *T=s;//让根节点指向s elseif(elem father->lchild=s;//父亲的左孩子赋值为s else father->rchild=s;//否则父亲的右孩子赋值为s return0;//返回 } intdelete_tree(BiTree*T,intelem)//删除树结点的操作 { BiTrees,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);//释放p return0; } if(p==father->lchild)//如果p和father的左孩子相等 father->lchild=p->rchild;//将p的左孩子的值赋给father的左孩子 else father->rchild=p->rchild;//将p的左孩子的值赋给father的右孩子 free(p);//释放p return0; } else if(! p->rchild) { if(father==NULL)//如果father为空
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 查找 排序 实验 报告 讲解