数据结构实验习题(5)

int i; struct record temp;

for (i=n/2-1;i>=0;i--) createheap(r,i,n); /* 建初始堆 */ for (i=n-1;i>=1;i--)

{temp=r[0];r[0]=r[i];r[i]=temp; createheap(r,0,i);} }

main( ) {

struct record r[m]; int i;

for( i=0; i<=m-1; i++) r[i].key=random(100); simpleselectsort(r,m);

for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”); for( i=0; i<=m-1; i++) r[i].key=random(100); heapsort(r,m);

for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”);

}

4. 归并排序在顺序存储结构上的实现。其中函数merge的功能是实现将两个有序的子文件合并成一个有序的子文件，函数mergesort的功能是实现归并排序。 #include \#include “stdlib.h”

typedef int datatype; #define m 10

struct record {int key;datatype others;};

void merge(struct record r[], int low,int mid,int high) {

int i=low,j=mid+1,k=low; struct record temp[m]; while (i<=mid && j<=high) {

if (r[i].key<=r[j].key){temp[k]=r[i]; i=i+1;} else {temp[k]=r[j]; j=j+1;} k=k+1; }

while(i<=mid){temp[k]=r[i]; i=i+1;k=k+1;} while(j<=high){temp[k]=r[j];j=j+1;k=k+1;} for (i=low;i<=high;i++) r[i]=temp[i];

}

void mergesort(struct record r[ ], int s, int t) {

if(s!=t){mergesort(r,s,(s+t)/2); mergesort(r,(s+t)/2+1,t); merge(r,s,(s+t)/2,t);} }

main( ) {

int i; struct record r[m];

for( i=0; i<=m-1; i++) r[i].key=random(100); mergesort(r,0,m-1);

for( i=0; i<=m-1; i++) printf(“%d\\t”,r[i].key); printf(“\\n”); }

- 21 -

5. 基数排序在链式存储结构上的实现。其中函数radix的功能是实现对长度为3的整数序列进行排序，函数

createlklist是建立一个链式存储结构的待排序记录序列，库函数itoa的功能是将整型数据转化为字符型数据（第一个参数表示被转化的整型值，第二个参数存储经转化得到的字符串，第三个参数表示按何种进制进行转化，本算法中用10表示按十进制数进行转化）。 #include \#include \#define n 11

typedef struct node{int data; struct node *next;} lklist;

void createlklist(lklist *&head) {

int i,a[n]={312,290,180,653,358,432,865,264,451,526,239}; lklist *p,*q; for(i=0,head=0; i

p=(lklist *)malloc(sizeof(lklist)); p->data=a[i]; p->next=0; if(i==0) head=q=p; else {q->next=p; q=p;} } }

void radixsort(lklist *&head, int d) {

struct node *p,*q,*h[10],*t[10]; int i,j,x; char string[20]; for(i=d-1; i>=0; i--) {

for(j=0; j<=9; j++) h[j]=t[j]=0; for(p=head; p!=0; p=p->next) {

ltoa(p->data,string,10); x=string[i]-'0';

if(h[x]==0) h[x]=t[x]=p; else {t[x]->next=p; t[x]=p;}

}

for(j=0; h[j]==0; )j++; head=h[j]; q=t[j];

for(x=j+1; x<=9; x++) if(h[x]!=0) {q->next=h[x]; q=t[x];} q->next=0; }

}

main( ) {

lklist *head=0,*p; createlklist(head); radixsort(head,3);

for(p=head; p!=0; p=p->next) printf(\}

- 22 -

实验七 查找

一、 实验目标

1． 掌握顺序表的查找算法在顺序存储结构上的实现。

2． 掌握建立二叉排序树和在二叉排序树上查找指定结点的算法在链式存储结构上的实现。 3． 掌握散列表的建立和查找算法在顺序存储结构上的实现。 4． 掌握散列表的建立和查找算法在链式存储结构上的实现。

二、 实验内容

1． 顺序表查找在顺序存储结构上的实现。其中函数sqsearch的功能是实现在顺序线性表中顺序查找关键字，函数bisearch的功能是实现在顺序线性表中折半查找关键字。 #include \#include “stdlib.h”

typedef int datatype; #define n 10

struct record {int key;datatype others;};

int sqsearch(struct record r[ ], int k) {

int i;

for(i=0; i<=n-1; i++) if (r[i].key==k) return(i+1); return(0); }

int bisearch(struct record r[ ], int k) {

int low=0,mid,high=n-1; while(low<=high) {

mid=(low+high)/2;

if(r[mid].key==k) return(mid+1);

else if(r[mid].key>k) high=mid-1; else low=mid+1; } return(0);

}

main( ) {

int i; struct record r[n];

for (i=0;i

if (sqsearch(r,44)>0) printf(“44 found\\n”); else printf(“44 not found\\n”); if(bisearch(r,44)>0) printf(“44 found\\n”); else printf(“44 not found\\n”);

}

2． 建立二叉排序树和在二叉排序树上查找指定结点的算法在链式存储结构上的实现。其中函数bstsearch的功能是实现利用递归方法在二叉排序树上查找指定结点，函数bstsearch1的功能是实现利用非递归方法在二叉排序树上查找指定结点，函数bstinsert的功能是实现在二叉排序树上插入结点，函数createbsttree的功能是实现建立一棵二叉排序树，函数inorder的功能是实现中序遍历二叉树。 #include \

- 23 -

#include \typedef int datatype;

#define n 10

typedef struct node{int key; struct node *lchild,*rchild;}bitree;

void inorder(bitree *bt) {

if (bt!=0) {inorder(bt->lchild); printf(“%d\\t”,bt->key); inorder(bt->rchild);} }

bitree *bstsearch(bitree *t, int key) {

if (t==0 || t->key==key) return(t);

else if (t->keyrchild,key)); else return(bstsearch(t->rchild,key)); }

bitree *bstsearch1(bitree *t, int key) {

bitree *p=t;

while(p!=0) if (p->key==key) return(p);else if (p->key>key)p=p->lchild; else p=p->rchild; return(0); }

void bstinsert(bitree *&bt,int key)

{

if (bt==0){bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0;} else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key); }

void createbsttree(bitree *&bt)

{

int i;

for(i=1;i<=n;i++) bstinsert(bt,random(100)); }

main( ) {

bitree *bt=0;

createbsttree(bt);

inorder(bt); printf(“\\n”);

if(bstsearch(bt,44)!=0) printf(“found\\n”); else printf(“not found\\n”);

}

3． 建立散列表和在散列表中查找指定结点的算法在顺序存储结构的实现。其中函数createsqhash的功能是实现建立顺序存储结构的散列表，函数hashsqsearch的功能是实现在顺序存储结构上实现散列表查找。 #include \#define m 8 #define n 7 #define p 7

struct record {int key; int flag;}; int a[n]={7,9,16,23,30,32,34};

void createsqhash(struct record hashtable[]) {

- 24 -

int i,j,k;

for(k=0;k

for(k=0;k

j=i=a[k] % p; while(1)

if(hashtable[j].flag==0){hashtable[j].key=a[k];hashtable[j].flag=1;break;} else {j=(j+1)%m; if(j==i){printf(\ }

}

int hashsqsearch(struct record hashtable[ ],int k)

{

int i,j; j=i=k % p;

while (hashtable[j].key!=k && hashtable[j].flag!=0 ) {j=(j+1)%m; if (i==j) return(-1);} if (hashtable[j].key==k) return(j); else return(-1); }

main( ) {

struct record hashtable[m]; int i;

createsqhash(hashtable);

for(i=0;i

4． 建立散列表和在散列表中查找指定结点的算法在链式存储结构的实现。其中函数createlkhash的功能是实现建立链式存储结构的散列表，函数hashlksearch的功能是实现在链式存储结构上实现散列表查找。 #include \#include \#define m 8 #define n 7 #define p 7

typedef struct node {int key; struct node *next;} lklist; int a[n]={7,9,16,23,30,32,34};

void createlkhash(lklist *hashtable[ ]) {

int i,k; lklist *s;

for(i=0;i

for(i=0;ikey=a[i];k=a[i] % p; s->next=hashtable[k]; hashtable[k]=s;} }

lklist *hashlksearch(lklist *hashtable[ ],int k) {

int i=k % p; lklist *s;

for(s=hashtable[i]->next; s!=0; s=s->next) if (s->key==k) return(s); return(0); } main( ) {

- 25 -

lklist *hashtable[m],*s; int i; createlkhash(hashtable);

for(i=0;inext) printf(“%d\\t”,s->key); printf(“\\n”);} if (hashlksearch(hashtable,16)!=0) printf(\}

- 26 -