#define LIST_MAX_LENGTH 1000 //线形表的最大长度
typedef struct
{
int *elem; //指向存放线形表中数据元素的基地址
int length; //线形表的当前长度
} SEQLIST;
要求：
1、先存入10个随机数，并生成一颗查询二叉树，输出中序遍历的结构；
2、对10个数据按照快速排序算法对表中数据升序存储，输出排序结果；
3、按照直接插入算法插入88到该表，并保持有序性；
4、查找77是否在该表中，若存在则返回表的下标；
5、采用直接插入算法插入66到表中并保证表的有序性，需要显示结果；
6、把表看做一张散列表，依次插入34、97、120、345、551，设散列函数H(X)=X%37，用线形方式解决冲突；计算出每个数据插入的比较次数并输出。
程序运行后如下：
程序源码如下：
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define LIST_MAX_LENGTH 1000 //线形表的最大长度
typedef struct SEQLIST
{
int *elem; //指向存放线形表中数据元素的基地址
int length; //线形表的当前长度
} SEQLIST;
int cmp=0;
typedef struct tree
{
struct tree *left;
struct tree *right;
int value;
}tree;
int pation(int A[],int x,int y);
void quicksort(int A[], int x, int y)
{
if(x>=y) return;
int q=pation(A, x, y);
quicksort(A, x, q-1);
quicksort(A, q+1, y);
}
int charu(int A[],int number,int len)
{
int i,temp,ii;
int t[LIST_MAX_LENGTH];
for(i=0;i<len;i++)
{
if(number>=A)continue;
else
{
temp=A;
A=number;
ii=i+1;
break;
}
}
t[ii-1]=temp;
for(i=ii;i<len;i++)
{
t=A;
}
for(i=ii;i<len+1;i++)
{
A=t[i-1];
}
len=len+1;
return len;
}
最新回复
{
int i;
for(i=0;i<len;i++)
{
if(A==num)return i;
else continue;
}
return -1;
}
int hash(int num)
{
int h;
h=num%37;
//cout <<h <<endl;
return h;
}
int check(int A[],int checknum,int len)
{
int i;
for(i=0;i<len;i++)
{
if(checknum==A)
{
cmp=cmp+1;
return -1;
}
continue;
}
return 1;
}
int hashnum(int A[],int B[],int num,int len)
{
int h;
h=hash(num);
while(check(B,h,len)!=1)
{
h=hash(h+1);
}
B[len]=h;
A[h]=num;
return h;
}
int pation(int A[], int x, int y)
{
int n=A[x], i=x+1, j=y, temp;
while(1)
{
while(A<n)
{
++i;
}
while(A[j]>n)
{
--j;
}
if(i>=j) break;
temp=A; A=A[j]; A[j]=temp;
}
A[x]=A[j];
A[j]=n;
return j;
}
tree *Creat_Tree(int num[],int len)
{
int i,flag=1;
tree *tmp,*root,*front,*cur;
root=(tree *)malloc(sizeof(struct tree)*sizeof(char));
if(root==NULL)return NULL;
root->value=num[0];
root->left=root->right=NULL;
for(i=1;i<len;i++)
{
cur=root;
tmp=(tree *)malloc(sizeof(struct tree)*sizeof(char));
if(tmp==NULL)return NULL;
tmp->left=tmp->right=NULL;
tmp->value=num;
while(cur)
{
front=cur;
if(num>cur->value){flag=1;cur=cur->right;}
else {flag=-1;cur=cur->left;}
}
if(flag==1)front->right=tmp;
else front->left=tmp;
}
return root;
}
void Mid_Order(tree *root)
{
if(root==NULL)return;
else {
Mid_Order(root->left);
cout <<root->value <<" ";
//if(root->value==num)*ok=1;
Mid_Order(root->right);
}
}
void main()
{
char yes;
srand((unsigned)time(NULL));
yes='y';
while(yes!='n')
{
tree *root;
int i,findout,hashn[5];
int num[LIST_MAX_LENGTH];
int exitnum[LIST_MAX_LENGTH];
SEQLIST * list;
list=(SEQLIST *)malloc(sizeof(struct SEQLIST));
list->length=10;
list->elem=num;
for(i=0;i<list->length;i++)
{
list->elem=rand()%400;
}
cout <<"以下演示第一项:" <<endl <<endl;
cout <<"随机生成十个整数:" <<endl;
for(i=0;i<list->length;i++)
{
cout <<"第" <<i <<"个输入数为:" <<list->elem <<endl;
}
root=Creat_Tree(list->elem,list->length); /* 创建排序二叉树 */
cout <<endl <<"其中序遍历为:" <<endl;
Mid_Order(root);
cout <<endl;
quicksort(list->elem, 0, list->length-1);
cout <<"第一项演示结束!" <<endl;
cout <<"-------------------------------------------------" <<endl;
cout <<endl;
cout <<"以下演示第二项:" <<endl <<endl;
cout <<"进行快速排序后的结果为:" <<endl;
for(i=0; i<list->length; ++i)
cout <<list->elem <<endl;
cout <<"第二项演示结束:" <<endl;
cout <<"-------------------------------------------------" <<endl;
cout <<endl <<"以下演示第三项:" <<endl <<endl;
//cin >>cha;
list->length=charu(list->elem,88,list->length);
cout <<"插入88后的表为:" <<endl;
for(i=0;i<list->length;i++)
{
cout <<list->elem <<endl;
}
cout <<endl <<"第三项演示结束!" <<endl;
cout <<"-------------------------------------------------" <<endl;
cout <<endl;
cout <<"以下演示第四项:" <<endl <<endl;
cout <<"输入数列包含:" <<endl;
for(i=0;i<list->length;i++)
cout <<list->elem <<" ";
//cout <<"查找77是否在表中!!" <<endl;
//cout <<"请输入77:" <<endl;
//cin >>find;
cout <<endl;
findout=find77(list->elem,77,list->length);
if(findout!=-1)
cout <<"找到77,下标为:" <<findout <<endl;
else
cout <<"找不到77!" <<endl;
cout <<endl <<"第四项演示结束!" <<endl;
cout <<"-------------------------------------------------" <<endl;
list->length=charu(list->elem,66,list->length);
cout <<endl <<"以下演示第五项:" <<endl;
cout <<"插入66后的表为:" <<endl;
for(i=0;i<list->length;i++)
{
cout <<list->elem <<endl;
}
cout <<endl;
cout <<"第五项演示结束!" <<endl <<endl;
cout <<"-------------------------------------------------" <<endl;
cout <<"以下演示第六项:" <<endl;
for(i=0;i<list->length;i++)
{
exitnum=i;
}
hashn[0]=34;
hashn[1]=97;
hashn[2]=120;
hashn[3]=345;
hashn[4]=551;
for(i=0;i<5;i++)
{
int hhh;
hhh=hashnum(list->elem,exitnum,hashn,list->length);
list->length++;
cout <<hashn <<"(散列值为" <<hhh <<") 比较的次数为:" <<cmp <<"插入第" <<hhh <<"位" <<endl;
cmp=0;
}
quicksort(exitnum,0,list->length-1);
cout <<"插入完成后的散列按序如下:" <<endl;
for(i=0;i<list->length;i++)
cout <<exitnum <<" => " <<list->elem[exitnum] <<endl;
cout <<"第六项演示结束!" <<endl;
cout <<"你想继续演示吗?(y/n)" <<endl;
cin >>yes;
} }
以上程序在VC6.0的环境下编译通过！
转自: http://tb.blog.csdn.net/TrackBack.aspx?PostId=927923