数据结构实验五
if(key==ST.elem[mid])
return (mid);
else if(key<ST.elem[mid])
high=mid-1;
else
low=mid+1;
}
return (0);
}
/*在二叉排序树中查找某关键字等于 key 的数据元素*/
int SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p) //SearchBST() Sub-function
}
/*二叉排序树中插入算法*/
int SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p) //SearchBST()
{ if(!T)
{ p=f;
return (ERROR);
}
else if(key==T->data)
{ p=T;
return (OK);
n=H(key); //查HASH表得到指针数组的地址
q->next=T[n]; //原来的头指针后移
T[n]=q; //新元素插入头部
} //while
return OK;
}
/*输出用链地址法处理冲突的Hash表*/
int Print_Hash (CHashTable & T)
{
LNode* q;
实验五 查找与排序
实验课程名:数据结构(c语言版)
专业班级:学 号:姓 名:
实验时间:实验地点:指导教师:
一、实验目的
1、进一步掌握指针变量、动态变量的点和适用范围。
3、掌握用指针类型描述、访问和处理二叉树的运算
二、实验的内容和步骤
下面是查找与排序的部分基本操作实现的算法,请同学们自己设计主函数和部分算法,调用这些算法,完成下面的实验任务。
if(m<1) return ERROR;
for(int i=0; i<m; i++)
T[i]=NULL; //哈希表初始化
while( (key=Inputkey())!=0 ) //输入元素有效
{ q=(LNode*)malloc(sizeof(LNode));
q->data=key;
q->next=NULL;
{ if(!T)
{ p=f;
return (ERROR);
}
else if(key==T->data)
{ p=T;
return (OK);
}
else if(key<T->data)
SearchBST(T->lchild,key,T,p);
else
SearchBST(T->rchild,key,T,p);
}
/* 在有序查找表中折半查找其关键字等于 key 的数据元素*/
int Search_Seq(SSTable ST,KeyType key)//Search_Seq function
{ int mid,low=1,high=ST.length;
while(low<=high)
{ mid=(low+high)/2;
KeyType key ; //关键字
InfoType otherinfo; //其它数据项
}
else if(key<T->data)
SearchBST(T->lchild,key,T,p);
else
SearchBST(T->rchild,key,T,p);
} //SearchBST() end
/*二叉排序树中删除算法*/
int Delete(BiTree &p)//Delete() sub-function
{
ElemType x;
cout<<"请输入数据"<<endl;
cin>>x;
return x;
}
/*输入一组关键字,建立Hash表,表长为m,用链地址法处理冲突*/
int Build_Hash (CHashTable & T, int m)
{ ElemType key;
LNode* q;
int n;
{ BiTree q,s;
if(!p->data)
{ q=p;
p=p->lchild;
free(q);
}
else if(!p->lchild)
{ q=p;
p=p->rchild;
free(q);
}
else
{ q=p;
s=p->lchild;
while(s->rchild)
{ q=s;
s=s->rchild;
# define MAX_LENGTH 100
typedef int KeyType;
/* 顺序查找表的存储类型 */
typedef struct//define structure SSTable
{ KeyType *elem;
int length;
}SSTable;
/* 在查找表中顺序查找其关键字等于 key 的数据元素。 */
}
p->data=s->data;
if(q!=p)q->rchild=s->lchild;
elseq->lchild=s->rchild;
}
}
/*链地址Hash表类型*/
typedef int ElemType;
typedef struct LNode
{ElemType key;
struct LNode *next;
int n;
for(int i=0; i<11; i++)
{
q=T[i]; //哈希表初始化
while(q ) //输入元素有效
{
cout<<q->data<<" ";
q=q->next;
}
cout<<endl;
}
return OK;
}
/*定义每个记录(数据元素)的结构*/
Typedef struct { //定义每个记录(数据元素)的结构
int Search_Seq(SSTable ST,KeyType key)//Search_Seq function
{ int i;
ST.elem[0]=key;
for(i=ST.length;!(ST.elem[i]==key);--i)
;
return (i);//if not find,return i=0
}LNode,*LinkList;
typedef LNode * CHashTable [MAXSIZE] ; //链地址Hash表类型
/*求Hash函数*/
int H(int s)//
{
if(s)
return s%11; //求关键字
else
return 0;
}//H
/*输入数据的关键字函数*/
ElemType Inputkey()