淮海工学院计算机科学系
实验报告书
课程名：《数据结构》
题 目： 查找、排序的应用实验
班 级： ^ ^
学 号： ^ ^
姓 名： ^ ^
排序、查找的应用实验报告要求
1目的与要求:
1）查找、排序是日常数据处理过程中经常要进行的操作和运算，掌握其算法与应用对于提高学生数据处理能力和综合应用能力显得十分重要。
2）本次实验前，要求同学完整理解有关排序和查找的相关算法和基本思想以及种算法使用的数据存储结构；
3）利用C或C++语言独立完成本次实验内容或题目，程序具有良好的交互性（以菜单机制实现实验程序的交互运行）和实用性；
4）本次与第七次实验已合二为一，实验结果在机房现场验收和评分，希望同学们认真对待，并于20##年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
#define LIST_SIZE 20
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;
if(k!=i)
{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);
Qsort(L,pivotloc+1,high);
}
}
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=key;
s->lchild=NULL;
s->rchild=NULL;
*bst=s;
}
else
if (key < (*bst)->key)
InsertBST(&((*bst)->lchild), key);/*将s插入左子树*/
else
if (key > (*bst)->key)
InsertBST(&((*bst)->rchild), key); /*将s插入右子树*/
}
void CreateBST(BSTree *bst)
{
KeyType key;
*bst=NULL;
scanf("%d", &key);
while (key!=ENDKEY) /*ENDKEY为自定义常量*/
{
InsertBST(bst, key);
scanf("%d", &key);
}
}
void PreOrder(BSTree root)
{
if (root!=NULL)
{
printf("%d ",root->key); /*输出结点*/
PreOrder(root->lchild); /*先序遍历左子树*/
PreOrder(root->rchild); /*先序遍历右子树*/
}
}
BSTree SearchBST(BSTree bst, KeyType key)
{
if (!bst)
return NULL;
else
if (bst->key == key)
return bst;/*查找成功*/
else
if (bst->key > key)
return SearchBST(bst->lchild, key);/*在左子树继续查找*/
else
return SearchBST(bst->rchild, key);/*在右子树继续查找*/
}
BSTNode * DelBST(BSTree t, KeyType k)
{
BSTNode *p, *f,*s ,*q;
p=t;
f=NULL;
while(p)
{
if(p->key==k ) break;
f=p;
if(p->key>k)
p=p->lchild;
else
p=p->rchild;
}
if(p==NULL) return t;
if(p->lchild==NULL)
{
if(f==NULL)
t=p->rchild;
else
if(f->lchild==p)
f->lchild=p->rchild ;
else
f->rchild=p->rchild ;
free(p);
}
else
{
q=p;
s=p->lchild;
while(s->rchild)
{q=s;
s=s->rchild;
}
if(q==p)
q->lchild=s->lchild ;
else
q->rchild=s->lchild;
p->key=s->key;
free(s);
}return t;
} /*DelBST*/
//建立哈希表
int CreatHashTable(HashTable &H,int m)
{
int i,keys,p,len;
H.elem = (Elemtype *)malloc(MAX * sizeof(Elemtype));
H.sizeindex = MAX;//初始存储容量
H.count=0;
printf("请输入该组关键字的个数:");
scanf("%d",&m);
printf("请输入表长len:");
scanf("%d",&len);
H.sizeindex = len;
for(i = 0;i < m;++i)
{
H.elem[i].flag = 0;
}
printf("请输入该组关键字：");
for(i = 0;i < m;++i)
{
scanf("%d",&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;
printf("哈希表创建完毕！\n");
printf("下标 关键字\n");
for(i = 0;i<len;i++)
{
printf("%d ",i);
printf("%d",H.elem[i].key);
printf("\n");
}
return SUCCESS;
}
void SearchHashTable(HashTable H)
{int keys,p;
printf("请输入您要查找的关键字：\n");
scanf("%d",&keys);
for(int i=0;i<H.count;i++)
{
if( keys == H.elem[i].key)//p是找到的关键字的下标
{
p=i;
}
}
if(p>-1&&p<H.count)
{
printf("查找成功！\n");
printf("该关键字在哈希表中的下标为：%d \n",p);
}
else
printf("查找失败，表中无此关键字！\n");
}
//堆排序
//筛选
void sift(RecordType r[],int k,int m)
{
int t;
t=r[k].key;
int x=r[k].key;
int i=k;
int j=2*i;
int finished=FALSE;
while(j<=m&&!finished)
{
if(j<m&&r[j].key<r[j+1].key)j=j+1;
if(x>=r[j].key)finished=TRUE;
else{
r[i]=r[j];
i=j;
j=2*i;
}/* 继续筛选*/
}
r[i].key=t;
}/* sift */
//建堆
void crt_heap(RecordType r[],int length)
{
int n=length;
for(int i=n/2;i>=1;--i)
sift(r,i,n);
}
//堆排序
void HeapSort(RecordType r[],int length)
{
crt_heap(r,length);
int n=length;
int b;
for(int i=n;i>=2;--i)
{
b=r[1].key;
r[1].key=r[i].key;
r[i].key=b;
sift(r,1,i-1);
}
}
//链式基数排序
void Distribute (SLinkList *L,int i,PVector head,PVector tail)
{
int j,p;
for(j=0;j<=RADIX-1;++j)
head[j]=0;
p=L->R[0].next;
while(p)
{
j=L->R[p].key[i];
if(head[j]==0) head[j]=p;
else L->R[tail[j]].next=p;
tail[j]=p;
p=L->R[p].next;
}
}
void Collect(SLinkList *L,PVector head,PVector tail)
{
int j=0,t;
while(head[j]==0)
++j;
L->R[0].next=head[j];t=tail[j];
while(j<RADIX-1)
{
++j;
while((j<RADIX-1)&&(head[j]==0))
++j;
if(head[j]!=0)
{
L->R[t].next=head[j];t=tail[j];
}
}
L->R[t].next=0;
}
void RadixSort(SLinkList *L )
{
int n,i,d,j,x,k;
printf("输入链表长度 :");
scanf("%d",&(L->length));
printf("输入最大位数 :");
scanf("%d",&(L->keynum));
PVector head,tail;
n=L->length;
for(i=0;i<=n-1;++i) L->R[i].next=i+1;
L->R[n].next=0;
printf("输入各记录 :");
for(j=1;j<=L->length;j++)
{
scanf("%d",&(L->R[j].type));
}
for(i=1;i<=L->length;i++)
{
x=L->R[i].type;
for(j=0;j<L->keynum;j++)
{
L->R[i].key[j]=x%10;
x=x/10;
}
}
d=L->keynum;
for(i=0;i<L->keynum;++i)
{
Distribute(L,i,head,tail);
Collect(L,head,tail);
}
k=0;
printf("排序后为 :");
while(L->R[k].next)
{
printf("%d ",L->R[L->R[k].next].type);
k=L->R[k].next;
}
}
void main()
{
SLinkList M;
int i,j,select,a,flag=1,m=0;
RecordType r[20];
BSTree bst,result,T;
RecordList L,Q;
int length,k,low;
printf("1 进行顺序查找 \t2 进行直接排序 \t3 进行冒泡排序 \n4 进行快速排序 \t5 对排好序的纪录序列表进行折半查找 \n6 利用原纪录序列建立一颗二叉排序树，并在其上实现特定关键字值结点的查找 \n7 建立哈希表，并对其进行查找\n");
printf("8 简单选择排序 9堆排序 10链式基数排序\n");
printf("0退出");
int symbol(1);
while(flag)
{
printf("\n请选择：");
scanf("%d",&a);
if(a==10)symbol=0;
while(symbol)
{
printf("请输入待排序记录的长度:"); //交互创建纪录表
scanf("%d",&length);
printf("请输入各元素：");
for(i=1;i<=length;i++)
{
fflush(stdin);
scanf("%d",&j);
r[i].key = j;
}
printf("你输入的各元素为：");
for(i=1;i<=length;i++)
printf("%d ",r[i].key);
printf("\n");
symbol=0;
}
switch(a)
{
case 1:
printf("请输入你要查找的元素k：");
fflush(stdin);
scanf("%d",&k);
L.length=length;
for(i=1;i<=L.length;i++)
{
L.r[i]=r[i];
}
SeqSearch(L,k);
printf("\n");
break;
case 2:
InsSort(r,length);
printf("按直接排序后各元素为：");
for(i=1;i<=length;i++)
printf("%d ",r[i].key);
printf("\n");break;
case 3:
BubbleSort(r,length);
printf("按冒泡排序后各元素为：");
for(i=1;i<=length;i++)
printf("%d ",r[i].key);
printf("\n");
break;
case 4:
L.length=length;
for(i=1;i<=L.length;i++)
{
L.r[i]=r[i];
}
QuickSort(L);
printf("进行快速排序后各元素为: ");
for(i=1;i<=L.length;i++)
printf("%d ",L.r[i].key);
printf("\n");
break;
case 5:
InsSort(r,length);
L.length=length;
for(i=1;i<=L.length;i++)
{
L.r[i]=r[i];
}
printf("请输入要查找的元素:");
scanf("%d",&k);
BinSrch(L,k);
printf("\n");
break;
case 6: int k;
printf("建立二叉排序树，请输入序列（以0结束）:\n");
CreateBST(&T);
printf("先序遍历输出序列为:");
PreOrder(T);
printf("\n请输入要查找的元素:");
fflush(stdin);
scanf("%d",&k);
result = SearchBST(T,k);
if (result != NULL)
printf("存在要查找的元素为%d\n",result->key);
else
printf("未找到!\n");
result = DelBST(T,k);
//getch();
break;
case 7:
HashTable H;
CreatHashTable(H,m);
SearchHashTable(H);
break;
case 0:
flag=0;
case 8:
SelectSort(r,length);
printf("按简单选择排序后各元素为：");
for(i=1;i<=length;i++)
printf("%d ",r[i].key);
printf("\n");
break;
case 9:
crt_heap(r,length);
HeapSort(r,length);
printf("按简单选择排序后各元素为：");
for(i=1;i<=length;i++)
printf("%d ",r[i].key);
printf("\n");
break;
case 10:
RadixSort(&M);
symbol=1;
break;
default:
printf("输入错误");
break;
}
}
}
4 测试数据与实验结果（可以抓图粘贴）
5 结果分析与实验体会
通过本次的数据结构实验，我掌握了多种基本查找、和排序的思想，以及实现他们的算法，对他们有了一个更加具体、深刻的认识，尤其当使用哈希排序时，很多时候会遇到冲突的情况，掌握了解决处理冲突的方法，例如线性探测再散列的冲突处理方法来创建哈希表解决实际问题。掌握了这一系列的方法，会为我们今后的继续学习带来很大的帮助。