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

scanf("%d",&m);

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()

{

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;

{

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] …… 此处隐藏：2678字，全部文档内容请下载后查看。喜欢就下载吧 ……