验证性实验五

验证性实验五 查找与排序

实验课程名：数据结构

专业班级： 学号： 姓名：

实验时间： 实验地点： K4－207 指导教师： 一、实验目的

1、掌握查找的不同方法，并能用高级语言实现查找算法。

2、熟练掌握顺序表的查找方法和有序顺序表的折半查找算法以及静态查找树的构造方法和查找算法。 3、掌握二叉排序树的生成、插入、删除、输出运算。 4、掌握常用的排序方法，并能用高级语言实现排序算法。

5、深刻理解排序的定义和各种排序方法的特点，并能加以灵活运用。

6、了解各种方法的排序过程及依据的原则，并掌握各种排序方法的时间复杂度的分析方法。

二、实验内容

下面是查找与排序的部分基本操作实现的算法，请同学们自己设计主函数和部分算法，调用这些算法，完成下面的实验任务。

1、顺序表的顺序查找

#include

#define KEYTYPE int #define MAXSIZE 100 typedef struct

{ KEYTYPE key; }SSELEMENT;

typedef struct

{ SSELEMENT r[MAXSIZE]; int len; }SSTABLE;

int seq_search(KEYTYPE k, SSTABLE st) {/*顺序表上查找元素*/ int j;

j = st.len; /*顺序表元素个数*/

st.r[0].key = k; /*st->r[0]单元作为监视哨*/ while(st.r[j].key != k) j--; /*顺序表从后向前查找*/

return j; /*j=0, 找不到；j0 找到*/ }

void main( )

{ SSTABLE a; int i, j, k;

printf("请输入顺序表元素(整型量) ，用空格分开，0为结束标志 ："); j = 0; k = 1; i = 0; scanf("%d",&i);

while (i!=0) { j++; a.r[k].key = i; k++; scanf("%d",&i); }/*输入顺序表元素*/ a.len = j;

printf("\n顺序表元素列表显示 ："); for (i = 1; i

printf("\n输入待查元素关键字 : "); scanf("%d",&i); k=seq_search(i,a);

if(k==0) printf("表中待查元素不存在\n");

else printf("表中待查元素存在, 为第%d个元素\n",k); }

实验结果：

2、有序顺序表的二分查找的算法

#include

#define KEYTYPE int #define MAXSIZE 100 typedef struct

{ KEYTYPE key; }SSELEMENT;

typedef struct

{ SSELEMENT r[MAXSIZE]; int len; }SSTABLE;

int search_bin(KEYTYPE k, int low, int high,SSTABLE a) { /*有序表上二分法查找, 递归算法*/ int mid;

mid = -1;

if(low

/*high表示当前表中最后一个元素所在下标*/ {

mid = (low +high)/2; /*mid表示当前表中中间一个元素所在下标*/ if(a.r[mid].key

mid = search_bin(k, mid + 1,high,a); /*二分法递归查找*/ else if(a.r[mid].key > k)

mid = search_bin(k,low,high - 1,a); }

return mid; /*mid = -1 查找不成功；mid!=-1 查找成功*/ }

void main( )

{ SSTABLE a; int i, j, k;

printf("请输入有序表元素，元素为整型量（从小到大输入），用空格分开，-100为结束标志 ：\n"); j=0; k = 1; i = 0; scanf("%d",&i); while (i != -100) { j++; a.r[k].key = i; k++; scanf("%d",&i); }/*输入有序表元素*/ a.len = j;

printf("\n有序表元素列表显示 ："); for (i = 1; i

printf("\n输入待查元素关键字 : "); scanf("%d",&i);

k=search_bin(i,1,a.len,a);

if (k == -1) printf("表中待查元素不存在\n\n");

else printf("表中待查元素存在, 为第%d个元素\n",k); }

实验结果：

3、二叉排序树的查找、插入、删除等基本操作的实现

#include #include #include

/******二叉排序树的数据结构********/ typedef struct Bstnode { int key; struct Bstnode *lchild,*rchild; }Bstnode,* Bstree;

Bstree Create(); //创建二叉排序树 Bstree Insert(Bstree tree,int key); //插入 Bstree Search(Bstree tree,int key); //查找

void Traverse(Bstree tree); //遍历 Bstree Delete(Bstree tree,int key); //删除

/*********************创建二叉排序树**************/ Bstree Create() {

int key; Bstree tree=NULL; //初始化空树 scanf("%d",&key); while(key!=0) { tree=Insert(tree,key); //逐个插入节点 scanf("%d",&key); } return tree; }

/*******************插入*********************/ Bstree Insert(Bstree tree,int key) { Bstree p=tree; Bstree s,f; while (p!=NULL) { f=p; if(key==p->key) return tree; if(key

key) p=p->lchild; else p=p->rchild; } s=(Bstree)malloc(sizeof(Bstnode)); s->key=key; s->lchild=NULL;

s->rchild=NULL; if(tree==NULL) return s; //新节点为二叉排序树的根 if(keykey) f->lchild=s; else f->rchild=s; return tree; }

/**************查找**************/ Bstree Search(Bstree tree,int key) { Bstree p=tree; int flag=0;

while(p!=NULL) { if(p->key==key) { printf("查询到该节点！"); flag=1; return(p); break; } if (key

key) p=p->lchild; else p=p->rchild; } if(flag==0) { printf("查询不到关键字为%d的节点！",key); return NULL; } }

/***************遍历*********************/ void Traverse(Bstree tree) { if(tree) { Traverse(tree->lchild); printf("%4d",tree->key); Traverse(tree->rchild); } }

/***************删除*******************/ Bstree Delete(Bstree tree,int key) { Bstree p=tree;

Bstree f,s,q; f=NULL; while(p) { //查找关键字为key 的节点 if(p->key==key) break; f=p; if(p->key>key) p=p->lchild; else p=p->rchild; } if (p==NULL) return tree; if ((p->lchild==NULL)||(p->rchild==NULL)) { if(f==NULL) if(p->lchild==NULL) tree=p->rchild; else tree=p->lchild; else if (p->lchild==NULL) if(f->lchild==p) f->lchild=p->rchild; else f->rchild=p->rchild; else if(f->lchild==p) f->lchild=p->lchild; else f->lchild=p->lchild; free(p); } else { q=p;s=p->lchild; while(s->rchild) { q=s;s=s->rchild; } if(q==p) q->lchild=s->lchild; p->key=s->key; free(s); } return tree; }

/*******************************************/ void main() {

system("color 1E"); Bstree tree,p; int key1,key2,key3; int select,flag; printf("############################################\n"); printf("|* 欢迎您使用本系统 *|\n"); printf("|******************************************|\n");

printf("|* 1. 创建二叉排序树 *|\n"); printf("|* 2. 插入 *|\n"); printf("|* 3. 查找 *|\n"); printf("|* 4. 遍历 *|\n"); printf("|* 5. 删除 *|\n"); printf("|* 6. 退出 *|\n"); printf("********************************************\n"); while(select!=6) { printf("选择的功能："); scanf("%d",&select); switch(select) { case 1: printf("请输入节点信息(0为结束符):\n"); tree=Create(); printf("\n"); break; case 2: printf("插入一个新的节点:"); scanf("%d",&key1);Insert(tree,key1); printf("插入后得序列为:\n"); Traverse(tree); printf("\n"); break; case 3: printf("输入查找的数据:"); scanf("%d",&key2); p=Search(tree,key2); printf("\n"); break; case 4: printf("遍历所得序列为:\n"); Traverse(tree); printf("\n"); break; case 5: printf("输入删除的数据:"); scanf("%d",&key3); tree=Delete(tree,key3); printf("删除后遍历所得序列:\n"); Traverse(tree); printf("\n"); break;

case 6: printf("谢谢您的使用，再见！\n");flag=0;break; default:printf("输入错误, 请重新输入\n");break; } } }

实验结果：

4、在用拉链法解决冲突的散列表上插入元素

#include #include #include #include #include #include #include

#define slot_size 10 //散列槽的大小 #define arr_size 20 //动态关键字集合

using namespace std; struct node {

string key; node* next; };

string* arr_set;

node link_hash[slot_size]; long str2num(string s) {

long num=0;

const char *temp=s.c_str(); int i=0;

while(temp[i]!='\0') {

num=num+int(temp[i]); i++; }

return num; } /*

* 散列函数，为方便起见，实验是使用了除法散列函数 */

long hash_function(string key) {

return str2num(key)%slot_size; } /*

* 打印数组函数 */

void print_arr(long* set,long size) {

for(long i=0;i

cout

* 链接法插入操作，在散列表指向的链表头前添加一个元素（节点） */

void hash_insert(string k) {

long temp_index=hash_function(k); node *new_node=new node; new_node->key=k;

new_node->next=link_hash[temp_index].next; link_hash[temp_index].next=new_node; } /*

* 查找函数, 计算散列值后，沿着链表一起搜索，知道找到该关键字 * 为止，如果找不到，则返回false */

bool hash_find(string k)

{

long temp_index=hash_function(k); node *temp_node =new node;

if(link_hash[temp_index].next==NULL) {

return false; } else {

temp_node=link_hash[temp_index].next; while(temp_node->key!=k) {

if(temp_node->next!=NULL) {

temp_node=temp_node->next; } else {

return false; } } }

return true; } /*

* 删除函数，如果没有找到就返回false ,如果找到了该关键字，就将前一节点的next 指针指向该关键字的 * next指针所指的节点 */

bool hash_delete(string k) {

long temp_index=hash_function(k); if(link_hash[temp_index].next==NULL) {

return false; } else {

node *temp_node =new node;

temp_node=link_hash[temp_index].next; node *pre_node=new node;

pre_node=&link_hash[temp_index]; while(temp_node->key!=k)

{

if(temp_node->next!=NULL)

{

pre_node=temp_node;

temp_node=temp_node->next;

}

else

{

return false;

}

}

pre_node->next=temp_node->next;

}

return true;

}

/*

* 打印散列表的函数，可以设置打印的开始索引到结束索引

*/

void print_hash(long start,long end)

{

node *temp;

long count=0;

for(long j=start;j

{

cout

if(link_hash[j].next==NULL)

{

cout

}

else

{

temp=&link_hash[j];

//temp=temp->next;

while(temp->next!=NULL)

{

cout"next->key;

temp=temp->next;

count++;

}

cout

}

}

cout

return;

}

//主函数，程序流程如实验设计的流程图

int main(int argc, char* argv[])

{

//cout

//cin>>arr_size;

string

name_set[20]={"terry","dos","garry","gerry","lily","poly","lernerd","vincent","biandu,adli","afand","lonsc","cecial","jimmy","cardly","supper","loser","kedny","nody","sen dcy"};//to generate arr_size from 1 to 1000 random number

arr_set=name_set;

//print_arr(arr_set,arr_size);

//初始化散列表的槽

for(long n=0;n

{

link_hash[n].next=NULL;

link_hash[n].key="";

}

//插入操作

DWORD insert_start = GetTickCount();

for(long m=0; m

{

hash_insert(arr_set[m]);

}

DWORD insert_time=GetTickCount() - insert_start;

coutcout

cout

cout

cout

cout

cout

print_hash(0,10);

//查找操作

DWORD find_start=GetTickCount();

for(n=0;n

{

hash_find(arr_set[n]);

}

DWORD find_time=GetTickCount()-find_start;

cout

cout

int a;

cin>>a;

return 0;

}

实验结果：

5、排序综合练习

#include

#include

# include

#define MAX 7// 元素个数

#define NUM_MAX 100 // 随机数的最大值

//冒泡排序

void BubbleSort(int a[],int n)

{ int i,j,temp;

for(i=0;i

for(j=0;j

if(a[j+1]

{ temp=a[j+1];

a[j+1]=a[j];

a[j]=temp;

}

for(i=0;i

//快速排序

int Partition(int a[],int low,int high)

{ int pivotkey;

pivotkey=a[low];

while(low

{ while(low=pivotkey)

--high;

a[low]=a[high];

while(low

++low;

a[high]=a[low];

}

a[low]=pivotkey;

return (low);

} //Partition() end

void Qsort(int a[],int low,int high) //Qsort() sub-function { int pivotloc;

if(low

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

Qsort(a,low,pivotloc-1);

Qsort(a,pivotloc+1,high);

}

}

void QuickSort(int a[]) //QuickSort() sub-function {int i;

Qsort(a,0,MAX-1); //call Qsort()

for(i=0;i

//希尔排序

void swap(int a[], int i, int j)

{

int t = a[i];

a[i] = a[j];

a[j] = t;

}

void selsort(int a[], int n, int dk)

{

int i, j;

for (i = dk; i

for (j = i; (j >= dk)

&& (a[j]

swap(a, j, j-dk);

}

void shellsort(int a[], int n) //希尔排序

{

int i, j;

for (i = n / 2; i > 2; i /= 2)

for (j = 0; j

selsort(&a[j], n - j, i);

selsort(a, n, 1);

for(i=0;i}

//堆排序

void HeapAdjust(int a[],int s,int m)

{

int rc = a[s];

int j=0;

for(j=2*s+1;j

{

if(j

++j;

if(rc > a[j])break;

a[s] = a[j];

s = j;

}

";

a[s] = rc;

}

void HeapSort(int a[],int n) //堆排

{

int t,i;

for(i=n/2; i>=0; --i)

{

HeapAdjust(a,i,n-1);

}

for(i=n-1;i>0;i--)

{

t = a[0];

a[0] = a[i];

a[i] = t;

HeapAdjust(a,0,i-1);

}

for(i=0;i}

void main()

{

int i,a[MAX],b[MAX],c[MAX],d[MAX];

clock_t begin, end;

long double cost;

srand((unsigned)time(NULL)); //随机产生整数 for (i=0; i

{a[i]=rand()%NUM_MAX;b[i]=a[i];c[i]=a[i];d[i]=a[i];} cout

for(i=0;i/*for(i=0;i

begin = clock();

BubbleSort(a,MAX);//冒泡

end = clock();

cost = (long double)(end - begin) / CLOCKS_PER_SEC; cout

cout

begin = clock();

QuickSort(b);//快速

end = clock();

cost = (long double)(end - begin) / CLOCKS_PER_SEC; cout

cout

begin = clock();

shellsort( c, MAX);//希尔

end = clock();

cost = (long double)(end - begin) / CLOCKS_PER_SEC; cout

cout

begin = clock();

HeapSort( d, MAX);//堆

end = clock();

cost = (long double)(end - begin) / CLOCKS_PER_SEC; cout

}

实验结果：