查找、排序综合实验

淮海工学院计算机科学系

实验报告书

课程名： 《数据结构》

题 目： 查找、排序综合实验

班 级： 学 号： 姓 名：

评语： 成绩： 指导教师： 批阅时间： 年 月 日

《 数据结构 》实验报告 - 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 #include #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<<\请输入该组关键字的个数:\ cin>>m;

cout<<\请输入表长len:\cin>>len;

H->sizeindex = len; for(i = 0;i < m;++i) {

H->elem[i].flag = 0; }

cout<<\请输入该组关键字：\ 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;jelem[j].key=0;

cout<<\哈希表创建完毕!\

cout<<\下标 关键字\ for(i = 0;i

cout<

cout<elem[i].key<

return 1; }

void SearchHashTable(HashTable* H) {

int keys,p;

cout<<\请输入您要查找的关键字：\ cin>>keys;

for(int i=0;icount;i++) {

if( keys == H->elem[i].key) p=i; }

《 数据结构 》实验报告 - 4 -

if(p>-1&&pcount) {

cout<<\查找成功!\

cout<<\该关键字在哈希表中的下标为：\} else

cout<<\查找失败，表中无此关键字!\}

//初始化

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<<\存在该元素：\ cout<<\该元素所在位置：\ return(i); } else {

cout<<\不存在该元素！\ return(0); } }

//直接插入排序

void inssort(recordlist * l) {

int j;

for(int i=2;i<=l->length;i++) {

l->r[0].key=l->r[i].key;