查找、排序综合实验

更新时间：2023-07-24 16:08:01 阅读量：实用文档文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

对记录序列(查找表)：{55,13,23,72,109,67,2,78,13}分别实现如下操作：1)顺序查找;2)分别使用直接插入排序、冒泡排序、快速排序对原纪录序列进行排序(暂时人工排序);3)对排好序的纪录序列表进行折半查找;4)利用原纪录序列建立一颗二叉排序树,并在其上实现特定关键字值结点的查找;5)按照“除留余数法”哈希构造函数和线性探测再散列的冲突处理方法创建表长为m=11的哈希表

淮海工学院计算机科学系实验报告书课程名：题

《数据结构》

目：查找、排序综合实验

班学姓

级：号：名：

评语：

成绩：

指导教师：批阅时间：年月日

《

数据结构

》实验报告

-1-

排序、查找的应用实验报告要求1 目的与要求:1)查找、排序是日常数据处理过程中经常要进行的操作和运算，掌握其算法与应用对于提高学生数据处理能力和综合应用能力显得十分重要。 2)本次实验前，要求同学完整理解有关排序和查找的相关算法和基本思想以及种算法使用的数据存储结构； 3)利用 C 或 C++语言独立完成本次实验内容或题目，程序具有良好的交互性(以菜单机制实现实验程序的交互运行)和实用性； 4)本次实验在机房现场验收和平分，希望同学们认真对待，并按时完成实验任务； 5)认真书写实验报告(包括程序清单及相关实验数据与完整运行结果) ,并于 16 周周五前提交，综合实验纸质报告每班收 10 份。

2 实验内容或题目题目：对记录序列(查找表) :{55,13,23,72,109,67,02,78,13}分别实现如下操作： 1) 顺序查找； 2) 分别使用直接插入排序、冒泡排序、快速排序对原纪录序列进行排序(本次要做) ; 3) 对排好序的纪录序列表进行折半查找； 4) 利用原纪录序列建立一颗二叉排序树，并在其上实现特定关键字值结点的查找； 5) 按照 “除留余数法” 哈希构造函数和线性探测再散列的冲突处理方法创建表长为 m=11 的哈希表 (本次实验做) ; 6) 实现 5)创建哈希表上的查找。 7) 看懂书上“链式基数排序”方法的分配收集排序举例，并以书上例题为例，实现这种排序方法。 (选作)

3 实验步骤与源程序#include <iostream.h> #include <malloc.h> #define maxsize 12 #define TRUE 1 #define FALSE 0 #define NULL 0 #define listsize 9 #define keysize 9 #define MAX 100 #define radix 9 typedef int keytype; typedef struct { int key;

《

数据结构

》实验报告

-2-

int flag; }Elemtype; typedef struct { Elemtype *elem; int sizeindex; int count; }HashTable; typedef struct node { int key; struct node *lchild,*rchild; }bstnode,*bstree; typedef struct { int key; int next; }recordtype; typedef struct { keytype key[keysize]; int type; int next; }recordtype1; typedef struct { recordtype1 r[keysize +1]; int length; int keynum; }slinklist; typedef struct { recordtype r[listsize +1]; int length; }recordlist; typedef int pvector[radix]; //创建哈希表 int CreatHashTable(HashTable* H,int m) { int i,keys,p,len; H->elem = (Elemtype *)malloc( sizeof(Elemtype)); H->sizeindex = MAX;

《

数据结构

》实验报告

-3-

H->count=0; cout<<"请输入该组关键字的个数:"<<endl; cin>>m; cout<<"请输入表长 len:"<<endl; cin>>len; H->sizeindex = len; for(i = 0;i

< m;++i) { H->elem[i].flag = 0; } cout<<"请输入该组关键字："<<endl; for(i = 0;i < m;++i) { cin>>keys; p = keys %m; while(H->elem[p].flag == 1) { int d=1; p = (p +d)% m; d++; } H->elem[p].key = keys; H->elem[p].flag = 1; H->count++; } for(int j=H->count;j<len;j++) H->elem[j].key=0; cout<<"哈希表创建完毕!"<<endl; cout<<"下标关键字"<<endl; for(i = 0;i<len;i++) { cout<<i<<" "; cout<<H->elem[i].key<<endl; } return 1; } void SearchHashTable(HashTable* H) { int keys,p; cout<<"请输入您要查找的关键字："<<endl; cin>>keys; for(int i=0;i<H->count;i++) { if( keys == H->elem[i].key) p=i; }

《

数据结构

》实验报告

-4-

if(p>-1&&p<H->count) { cout<<"查找成功!"<<endl; cout<<"该关键字在哈希表中的下标为："<<p<<endl; } else cout<<"查找失败，表中无此关键字!"<<endl; } //初始化 void initrecord(recordlist * l) { l->r[1].key=55; l->r[2].key=13; l->r[3].key=23; l->r[4].key=72; l->r[5].key=109; l->r[6].key=67; l->r[7].key=2; l->r[8].key=78; l->r[9].key=13; } //顺序查找 int seqsearch(recordlist * l,int k) { int i=l->length ; while(i>=1&&l->r[i].key!=k)i--; if(i>=1) { cout<<"存在该元素："<<l->r[i].key<<endl; cout<<"该元素所在位置："<<i<<endl; return(i); } else { cout<<"不存在该元素！"<<endl; return(0); } } //直接插入排序 void inssort(recordlist * l) { int j; for(int i=2;i<=l->length;i++) { l->r[0].key=l->r[i].key;

《

数据结构

》实验报告

-5-

j=i-1; while(l->r[0].key<l->r[j].key) { l->r[j+1].key =l->r[j].key ; j=j-1; } l->r[j+1].key=l->r[0].key; } for(int m=1;m<=l->length;m++) cout<<l->r[m].key<<" "; cout<<endl; } //冒泡排序 void bubblesort(recordlist * l) { int i,j,x; int change=TRUE; for(i=1;i<=l->length && change;++i) { change=FALSE; for(j=1;j<=l->length-i;++j) if(l->r[j].key>l->r[j+1].key) { x=l->r[j].key; l->r[j].key=l->r[j+1].key ; l->r[j+1].key=x; change=TRUE; } } for(int m=1;m<=l->length;m++) cout<<l->r[m].key<<" "; cout<<endl; } //快速排序 int qkpass(recordlist * l,int left,int right) { int x=l->r[left].key; int low=left; int high=right; while(low<high) { while(low<high && l->r[high].key >=x) high--; if(low<high) { l->r[low].key =l->r[high].key ;

《

数据结构

》实验报告

-6-

low++; } while(low<high && l->r[high].key<x) low++; if(low<high) { l->r[high].key=l->r[low].key; high--; } } l->r[low].key=x; return low; } void qksort(recordlist *l,int low,int high) { int pos; if(low<=high) { pos=qkpass(l,low,high); qksort(l,low,pos-1); qksort(l,pos+1,high); } } //折半查找 int binsrch(recordlist * l,int k) { int low=1,high=l->length,mid; while(low<=high) { mid=(low+high)/2; if(k==l->r[mid].key) { cout<<"存在该元素："<<l->r[mid].key<<endl; cout<<"该元素所在位置："<<mid<<endl; return(1); } else if(k<l->r[mid].key) high=mid-1; else low=mid+1; } cout<<"查找失败!"<<endl; return(0); } //建立平衡二叉排序树

《

数据结构

》实验报告

-7-

void insertbst(bstree *bst,int k) { bstree s; if(*bst==NULL)

{ s=(bstnode*)malloc(sizeof(bstnode)); s->key=k; s->lchild=NULL; s->rchild=NULL; *bst=s; } else if(k<(*bst)->key) insertbst(&((*bst)->lchild),k); else if(k>(*bst)->key) insertbst(&((*bst)->rchild),k); } void creatbstree(bstree *bst) { int k; *bst=NULL; cout<<"输入元素:"<<endl; cin>>k; while(k!=0) { insertbst(bst,k); cout<<"输入元素:"<<endl; cin>>k; } } //二叉树查找 int searchbst(bstree bst,int k) { if(!bst)return NULL; else if(bst->key==k) { cout<<"输出特定元素："<<bst->key<<endl; return 1; } else if(k<bst->key) searchbst(bst->lchild,k); else searchbst(bst->rchild,k); return 0; }

《

数据结构

》实验报告

-8-

//简单排序 void selectsort(recordlist * l) { int i,j,k,x; for(i=1;i<=l->length;++i) { k=i; for(j=1;j<=l->length;++j) { if(l->r[j].key<l->r[k].key) k=j; if(k!=i) { x=l->r[i].key; l->r[i].key=l->r[k].key; l->r[k].key=x; } } } } void main() { int f=1,e,k,r,q; char s; recordlist * L; slinklist * L1; HashTable* h; h=(HashTable*)malloc(sizeof(HashTable)); bstree * B; L1=(slinklist *)malloc(sizeof(slinklist)); L=(recordlist*)malloc(sizeof(recordlist)); B=(bstree *)malloc(sizeof(bstree) ); cout<<"输入所创顺序表的长度："<<endl; cin>>r; L->length=r; cout<<"输入表的元素："<<endl; for(int i=1;i<=L->length;i++) cin>>L->r[i].key; while(f) { cout<<endl; cout<<"-------------请输入序号:-----------------"<<endl; cout<<"顺序查找请输入:A "<<endl; cout<<"直接插入排序请输入:B"<<endl; cout<<"冒泡排序请输入:C"<<endl;

《

数据结构

》实验报告

-9-

cout<<"快速排序请输入:D"<<endl; cout<<"折半查找请输入:E"<<endl; cout<<"建立二叉排序树请输入:F"<<endl; cout<<"查找二叉树特定关键字请输入:G"<<endl; cout<<"建立哈希表请输入:H"<<endl; cout<<"哈希表上查找请输入:I"<<endl; cout<<"简单排序请输入:J"<<endl; cout<<"退出请输入:K"<<endl; cout<<"输入操作序号："<<endl; cin>>s; switch(s) { case 'A': cout<<"进行顺序查找："<<endl; cout<<"输入要查找的元素："<<endl; cin>>k; seqsearch(L,k); break; case 'B': cout<<"进行直接插入排序："<<endl; inssort(L); break; case 'C': cout<<"进行还原："<<endl; initrecord(L); for( e=1;e<=L->length;e++) cout<<L->r[e].key<<" "; cout<<endl; cout<<"进行冒泡排序："<<endl; bubblesort(L); break; case 'D': cout<<"进行还原："<<endl; initrecord(L); for( e=1;e<=L->length;e++) cout<<L->r[e].key<<" "; cout<<endl; cout<<"快速排序:"<<endl; qksort(L,1,9); for( q=1;q<=L->length;q++) cout<<L->r[q].key<<" "; cout<<endl; break; case 'E': cout<<"进行折半查找:"<<endl; cout<<"输入要查找的元素："<<endl;

《

数据结构

》实验报告

- 10 -

cin>>k; binsrch(L,k); break; case 'F': cout<<"建立二叉排序树,最后以 00 结束:"<<endl; creatbstree(B); break; case 'G': cout<<"二叉排序树查找特定元素："<<endl; cout<<"输入要查找元素："<<endl; cin>>k; searchbst(*B,k); break; case 'H': cout<<"创建哈希表："<<endl; CreatHashTable(h

,9); break; case 'I': cout<<"哈希表上的查找："<<endl; SearchHashTable(h); break; case 'J': cout<<"进行还原："<<endl; initrecord(L); for( e=1;e<=L->length;e++) cout<<L->r[e].key<<" "; cout<<endl; cout<<"简单选择排序："<<endl; selectsort(L); for( q=1;q<=L->length;q++) cout<<L->r[q].key<<" "; cout<<endl; break; case 'K': f=0; cout<<"退出！"<<endl; break; } } }

4 测试数据与实验结果(可以抓图粘贴)

《

数据结构

》实验报告

- 11 -

《

数据结构

》实验报告

- 12 -

《

数据结构

》实验报告

- 13 -

5 结果分析与实验体会这是最后一次试验了，也算是比较难的实验。我感觉这次试验花了自己很多的时间，首先要充分理解书本上的知识和算法，但是，仅仅这样还不足以完成这次试验，我又到图书馆查阅了很多本章的知识和算法，结合书本和实验内容才完成这次试验。这次试验，给了我很多的教训，使我为即将到来的课程设计做好了心理准备。

本文来源：https://www.bwwdw.com/article/atnm.html

相关文章：

正在阅读：

查找、排序综合实验07-24

计算机应用基础805-24

2017-2022年中国汽车等速万向节行业深度调研及发展策略研究报告03-17

2022年二级注册建筑师终极复习资料汇总04-06

代持股协议书(最新)07-09

猫作文600字06-12