数据结构_查找、排序的应用实验

淮海工学院计算机科学系

实验报告书

课程名： 《数据结构》

题 目： 查找、排序的应用实验

班 级：

学 号： ^ ^

姓 名：

排序、查找的应用实验报告要求

1目的与要求:

1）查找、排序是日常数据处理过程中经常要进行的操作和运算，掌握其算法与应用对于提

高学生数据处理能力和综合应用能力显得十分重要。

2）本次实验前，要求同学完整理解有关排序和查找的相关算法和基本思想以及种算法使用

的数据存储结构；

3）利用C或C++语言独立完成本次实验内容或题目，程序具有良好的交互性（以菜单机制

实现实验程序的交互运行）和实用性；

4）本次与第七次实验已合二为一，实验结果在机房现场验收和评分，希望同学们认真对待，并于2009年12月20日按时提交本次实验报告（含电子和纸质报告），任何同学不得拖延。

5）如果验收时间紧张，不能再正课时间完成者，由老师择机决定另行通知专门验收时间。凡无故不主动或拖延验收者，均按照不及格处理。

5）认真书写实验报告（包括程序清单及相关实验数据与完整运行结果），并于按时提交。 2 实验内容或题目

题目：对数据序列（查找表）：{55，13，23，72，109，67，2，78,13}分别实现如下操作：

1) 顺序查找；

2) 分别使用直接插入排序、冒泡排序、快速排序对原纪录序列进行排序；

3) 对排好序的纪录序列表进行折半查找；

4) 利用原纪录序列建立一颗二叉排序树，并在其上实现特定关键字值结点的查找；

5) 按照“除留余数法”哈希构造函数和线性探测再散列的冲突处理方法创建表长为m=11的哈希表；

6) 实现5）创建哈希表上的查找。

7） 分别简单选择排序、堆排序、链式基数排序算法对数据序列进行排序，并显示排序结果。

3 实验步骤与源程序

#include <stdio.h>

#include<malloc.h>

#include <stdlib.h>

#define LIST_SIZE 20

#define TRUE 1

#define FALSE 0

#define SUCCESS 1

#define UNSUCCESS -1

#define MAX 100

#define RADIX 10

#define KEY_SIZE 6

typedef char KeyType;

typedef int OtherType;

typedef int PVector[RADIX];

typedef struct

{ KeyType key[KEY_SIZE];

int type;

int next;

}RecordType1;

typedef struct

{RecordType1 R[LIST_SIZE+1];

int length;

int keynum;

}SLinkList;

typedef struct

{KeyType key;

OtherType other_data;

}RecordType;

typedef struct

{RecordType r[LIST_SIZE+1];

int length;

}RecordList;

//二叉排序树的创建与查找

#define ENDKEY 0

typedef struct node

{

KeyType key ; /*关键字的值*/

struct node *lchild,*rchild;/*左右指针*/

}BSTNode, *BSTree;

/*哈希表的创建*/

typedef struct

{

int key;

int flag;//falg=1时表示有关键字，=0时表示没有关键字

}Elemtype;

typedef struct

{

Elemtype *elem;//动态分配的哈希表的首地址

int sizeindex;//hashsize[sizeindex]为当前容量

int count;//当前数据元素个数

}HashTable;

//顺序查找

void SeqSearch(RecordList l, KeyType k)

/*在顺序表l中顺序查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置，否则为0*/

{

int i;

l.r[0].key=k;

i=l.length;

while (l.r[i].key!=k) i--;

if (i>=1)

{

printf("该元素k所在的位置是:");

printf("%d",i);

}

else

printf("该元素不存在");

}

//直接插入排序

void InsSort(RecordType r[], int length)

{

int i,j;

for (i=2; i<=length; i++)

{

r[0]=r[i]; /*将待插入记录存放到监视哨r[0]中*/

j=i-1;

while (r[0].key< r[j].key ) /* 寻找插入位置 */

{

r[j+1]= r[j];

j=j-1;

}

r[j+1]=r[0]; /*将待插入记录插入到已排序的序列中*/

}

} /* InsSort */

//简单选择排序

void SelectSort(RecordType r[],int length)

{

int n,k;int x;

n=length;

for(int i=1;i<=n-1;++i)

{

k=i;

for(int j=i+1;j<=n;++j)

if(r[j].key<r[k].key)k=j;

{x=r[i].key ;r[i].key =r[k].key ;r[k].key =x;}

}

}/* SelectSort */

//冒泡排序

void BubbleSort(RecordType r[],int length)

{

int x,i,n,change,j;

n=length;change=TRUE;

for(i=1;i<=n-1&&change;++i)

{

change=FALSE;

for(j=1;j<=n-i;++j)

if(r[j].key>r[j+1].key)

{

x=r[j].key;

r[j]=r[j+1];

r[j+1].key=x;

change=TRUE;

}

}

}

//快速排序

int Partition(RecordList &L,int low,int high) //Partition() sub-function

{ int pivotkey;

L.r[0]=L.r[low];

pivotkey=L.r[low].key;

while(low<high)

{ while(low<high&&L.r[high].key>=pivotkey)

--high;

L.r[low]=L.r[high];

while(low<high&&L.r[low].key<=pivotkey)

++low;

L.r[high]=L.r[low];

}

L.r[low]=L.r[0];

return(low);

}

void Qsort(RecordList &L,int low,int high)

{ int pivotloc;

if(low<high)

{ pivotloc=Partition(L,low,high);

Qsort(L,low,pivotloc-1);

}

}

void QuickSort(RecordList &L)

{ Qsort(L,1,L.length);

}

//对排好的序进行折半查找算法

void BinSrch(RecordList l,KeyType k)

{

int low,high,mid;

low=1;

high=l.length;

while(low<=high)

{

mid=(low+high)/2;

if (k==l.r[mid].key)

{

printf("找到该元素，其位置为%d",mid);

break;

}/*找到待查元素*/

else

if (k<l.r[mid]. key)

high=mid-1;/*未找到，则继续在前半区间进行查找*/

else

low=mid+1;/*继续在后半区间进行查找*/

}

if(low>high) printf("没有找到该元素");

}

void InsertBST(BSTree *bst, KeyType key)

{

BSTree s;

if (*bst == NULL)/*递归结束条件*/

{

s=(BSTree)malloc(sizeof(BSTNode));/*申请新的结点s*/

s-> key …… 此处隐藏：3145字，全部文档内容请下载后查看。喜欢就下载吧 ……