程序设计《任选一题》

/查找算法

问题描述：

设计一个实现顺序查找、二分查找（折半查找）、二叉排序树、哈希查找算法的程序，并具有人机交互界面。

基本要求：

（1）设计一个菜单将实现的查找算法的名字显示出来，并提示用户对查找算法进行选择；

（2）分别实现顺序查找、二分查找（折半查找）、二叉排序树、哈希查找；

（3）哈希函数采用除留余数发，解决冲突的方法大家任选择一种；

（4）二叉排序树必须实现构建、查找、插入、删除四个基本 *** 作；

（5）输出各种排序的结果并进行比较。/

#include<stdioh>

#include<conioh>

#include<stdlibh>

#define MAX 20

typedef struct /顺序结构数据类型/

{

int key;

}RecordType;

typedef struct

{

RecordType r[MAX+1];

int length;

}RecordList;

typedef struct

{

RecordType HashTable[MAX];

}RecordHash;

typedef struct node /二叉排序树的结点结构/

{

int key;

struct node lchild,rchild;

}BSTNode,BSTree;

void page_title(char menu_item) /返回界面函数/

{

clrscr();

printf(" 查找算法 \n\n\n\n\n%s\n\n",menu_item);

}

void return_confirm()

{

printf("按任意键返回\n");

getch(); /从键盘终端接受一个字符/

}

RecordList creat1() /建立线性表/

{

RecordList h;

int i,n=1;

hlength=0;

printf("请输入第1个数:");

scanf("%d",&i);

while(i!=0)

{

hlength++;

hr[hlength]key=i;

printf("请输入第%d个数:",++n);

scanf("%d",&i);

}

return h;

}

void InsertBST(BSTree &p,int k)

{

BSTNode s;

if(p==NULL)

{

s=(BSTNode)malloc(sizeof(BSTNode));

s->key=k;

s->lchild=NULL;

s->rchild=NULL;

p=s;

}

else if(k<p->key)

InsertBST(p->lchild,k);

else if(k>p->key)

InsertBST(p->rchild,k);

}

BSTNode creat2() /创建二叉排序树/

{

BSTNode h;

int k,i=1;

h=NULL;

printf("请输入第1个关键字:");

scanf("%d",&k);

while(k!=0)

{

InsertBST(h,k);

printf("请输入第%d个关键字:",++i);

scanf("%d",&k);

}

return h;

}

void SeqSearch(RecordList l) /顺序查找/

{

int i;

int k;

page_title("顺序查找");

printf("请输入要查找的关键字:");

scanf("%d",&k);

lr[0]key=k;

i=llength;

while(lr[i]key!=k) i--;

if(i==0) printf("查找失败\n");

else

{

printf("lr[%d]key=%d\n",i,k);

printf("查找成功\n");

}

return_confirm();

}

void Binsrch(RecordList l) /二分查找/

{

int k,j,i=0;

int low=1,high=llength,mid;

page_title("二分查找");

printf("请输入要查找的关键字:");

scanf("%d",&k);

while(low<=high)

{

mid=(low+high)/2;

if(lr[mid]key==k)

{

i=mid;

break;

}

else

if(k<lr[mid]key) high=mid-1;

else low=mid +1;

}

if(i!=0)

{

printf("lr[%d]key=%d\n",i,k);

printf("查找成功\n");

}

else printf("查找失败\n");

return_confirm();

}

void SearchBST(BSTNode h,int k) /二叉排序树的查找/

{

if(!h)

{

printf("查找失败\n");

return_confirm();

}

else if(h->key==k)

{

printf("查找成功\n");

return_confirm();

}

else if(h->key>k)

SearchBST(h->lchild,k);

else

SearchBST(h->rchild,k);

}

RecordHash creat3() /创建哈希表/

{

RecordHash ht;

int i,j=1,k;

for(i=0;i<MAX;i++)

htHashTable[i]key=0;

printf("请输入第1个关键字:");

scanf("%d",&k);

while(k!=0&&j<MAX)

{

i=k%13;

while(htHashTable[i]key!=0) i++;

htHashTable[i]key=k;

printf("请输入第%d个关键字:",++j);

scanf("%d",&k);

}

return ht;

}

void HashSearch(RecordHash ht) /哈希查找/

{

int k,i;

page_title("哈希查找");

printf("请输入要查找的关键字:");

scanf("%d",&k);

i=k%13;

if(htHashTable[i]key==k)

{

printf("htHashTable[%d]key=%d\n",i,k);

printf("查找成功\n");

}

else

{

i=i+1;

for(;i<MAX;i++)

if(htHashTable[i]key==k)

{

printf("htHashTable[%d]key=%d\n",i,k);

printf("查找成功\n");

break;

}

if(i==MAX) printf("查找失败\n");

}

return_confirm();

}

void main()

{

RecordList L1,L2;

BSTNode pt;

RecordHash ht;

int k,i;

printf("\n创建顺序查找线性表,输入0则结束输入(可不按顺序输入)\n");

L1=creat1();

printf("\n创建二分查找线性表，输入0则结束输入(按递增顺序输入)\n");

L2=creat1();

printf("\n创建二叉排序树，输入0则结束输入\n");

pt=creat2();

printf("\n创建哈希表\n");

ht=creat3();

menu:page_title("请选择查找方式，输入0则结束输入");

printf("顺序查找请按1\n二分查找请按2\n二叉排序树查找请按3\n哈希查找请按4\n推出请按0\n");

switch(getch())

{

case '1':

SeqSearch(L1);

break;

case '2':

Binsrch(L2);

break;

case '3':

page_title("二叉排序树查找");

printf("请输入要查找的关键字:");

scanf("%d",&k);

SearchBST(pt,k);

break;

case '4':

HashSearch(ht);

break;

case '0':

exit(0);

default :

printf("输入错误，按任意键返回");

getch();

}

goto menu;

}

1B 2B 3C 4A 5C 6D 7B 8B 9A 10C

1、编写程序。从键盘输入100个数，将正数升序排列到数组的前端，把0放在中间，负数按降序排列在0的后面。

#include"stdioh"

void main()

{

int i,j,k,s,a[100],b[100]={0},m=0,n=0;

printf("input:");

for(i=0;i<100;i++)

scanf("%d",a[i]);

for(i=0,j=0;i<100;i++)

if(a[i]>0){b[j++]=a[i];m++;}//m正数个数

for(i=0,j=99;i<100;i++)

if(a[i]<0){b[j--]=a[i]; n++;}//n负数个数

for(i=0;i<m-1;i++)//正数排序

{ k=i

for(j=i+1;j<m;j++)

if(b[i]>b[j])k=j;

if(i!=k)

{s=b[i];b[i]=b[k];b[k]=s;}

}

for(i=100-n;i<99;i++)//负数排序

{ k=i

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

if(b[i]<b[j])k=j;

if(i!=k)

{s=b[i];b[i]=b[k];b[k]=s;}

}

for(i=0;i<100;i++)

printf("%d ",b[i]);

printf("\n")

}

以上就是关于程序设计《任选一题》全部的内容，包括:程序设计《任选一题》、C语言程序设计、等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！