实验五 查找

实验五 查找

实验目的
1.掌握各种不同查找算法的思想及其程序实现
2.掌握二叉排序树的查找、插入、删除算法的思想及程序实现

实验内容

1.编写函数，建立有序表，采用折半查找实现某一已知的关键字的查找。（采用顺序表存储结构）
2.编写函数，输入一组关键字，利用二叉排序树的插入算法建立二叉排序树。
3.编写函数，在以上二叉排序树中删除某一指定关键字元素。
4.编写一个主函数，在主函数中设计一个简单的菜单，分别调用上述函数。

#include <stdio.h>
#include <stdlib.h>
#include<iostream>
using namespace std;
#define MAXSIZE 50
typedef int KeyType;//
#define TElemType char
//数据元素类型定义
typedef struct{
KeyType key;
}ElemType;
//顺序表的定义
typedef struct{
ElemType *R;//存储空间基地址
int length;
}SSTable;
//链式二叉查找树数据结构
typedef struct BSTNode
{
TElemType data;//数据域
struct BSTNode *lchild, *rchild;//左右孩子
}BSTNode, *BSTree;
//创建有序表
bool CreateList(SSTable &L)
{ int i;
L.R=new ElemType[MAXSIZE+1]; //分配空间
if (!L.R)
return false;
cout<<"请输入线性表的长度,不能大于"<<MAXSIZE<<':'; cin>>L.length;
cout<<"请输入表中元素：";
for(i=1;i<=L.length;i++)
cin>>L.R[i].key;
}
//输出有序表
void print(SSTable L)
{ int i;
for(i=1;i<=L.length;i++)
if (i==1)
cout<<'('<<L.R[i].key;
else cout<<','<<L.R[i].key;
cout<<')'<<endl;
}
int Search_Bin(SSTable ST,KeyType key)
{
int low,high,mid;//课本总是没有定义
low=1;high=ST.length;
while(low<=high)
{
mid=(low+high)/2;
if(key==ST.R[mid].key)
return mid;
else if(key<ST.R[mid].key) high=mid-1;
else low=mid+1;
}
return 0;
}
//二叉查找树插入 参数T，二叉查找树根节点 作用：插入数据data,保证中序非严格递增（即可重复）
int BST_Insert(BSTree &T, TElemType e)
{
if (T == NULL)//树为空
{
T = (BSTree)malloc(sizeof(BSTNode));//申请结点空间
T->data = e;
//赋值
T->lchild = NULL;
//左右孩子为空
T->rchild = NULL;
return 1;
}
else if (e < T->data)
//比当前节点数据小，插入左子树
{
return BST_Insert(T->lchild,e);
}
else
//这里规定二叉查找树可以重复，等于及大于当前结点时，插入右子树
{
return BST_Insert(T->rchild,e);
}
}
//中序遍历-递归
void InOrder(BSTree T)
{
if (T != NULL)
{
InOrder(T->lchild);//递归中序遍历左右子树
cout << T->data << " ";
InOrder(T->rchild);
}
}
//二叉查找树删除 参数 BSTree T, TElemType key，作用查找key是否存在于二叉查找树中，若存在，删除，返回true,否则，返回false
bool BST_Delete(BSTree &T, TElemType key)
{
BSTNode*
p = T;
BSTNode*
f = NULL;//当前结点的双亲结点
while (p&&key != p->data)
{
if (key<p->data)
//比当前结点数据小
{
f = p;
//记录双亲结点
p = p->lchild;
}
else
//比当前结点数据大
{
f = p;
//记录双亲结点
p = p->rchild;
}
}
if (p)//找到啦，分情况删除：叶子结点（度为0） 单支结点（度为1） 双支结点（度为2）
{
if (p->lchild==NULL&&p->rchild==NULL)//叶子结点
{
if (p == T)//根节点
{
T = NULL;
}
else if (f->lchild == p)//要删除的是cur_par的左孩子
{
f->lchild = NULL;
}
else
{
f->rchild = NULL;
}
}
else if (p->lchild == NULL || p->rchild == NULL)//单支结点
{
if (p == T)//根节点
{
if (p->lchild)//有左孩子
{
T = p->lchild;
}
else
{
T = p->rchild;
}
}
else //非根结点，双亲结点指向要删除结点的子结点即可
{
if (f->lchild == p&&p->lchild)//cur为cur的双亲结点的左孩子，且有左孩子
{
f->lchild = p->lchild;
}
else if (f->lchild == p&&p->rchild)
{
f->lchild = p->rchild;
}
else if (f->rchild == p&&p->lchild)
{
f->rchild = p->lchild;
}
else{
f->rchild = p->rchild;
}
}
}
else //双支结点
可以选择与直接前驱交换数据域，然后删除直接前驱。
//或者，与直接后继交换数据域，删除直接后继。这里选择后者。
{
BSTNode* temp = p;//记录需要删除的结点，接下来要与直接后继交换数据域
f = p;
//用cur找到temp的直接后继 则cur为temp右子树的最左孩子
p = p->rchild;
//右子树
while (p->lchild)//找到直接后继，即右子树的最左孩子（最小值）
{
f = p;
p=p->lchild;
}
temp->data = p->data;//交换数据域
if (f == temp)//待删除结点的右子树没有左子树，即右子树根节点即为待删除结点后继
{
f->rchild = p->rchild;
}
else
//待删除结点的右子树有左子树
{
f->lchild = p->rchild;//将cur的右子树给双亲结点
}
}
free(p);
return true;
}//if
return false;
}
//**********************************功能实现函数*****************************//
//调用BST_Insert进行二叉查找树的创建
void CreateBSTree(BSTree &T)
{
string s;
printf("请输入二叉树结点数据创建二叉查找树(结点字符串):");
cin >> s;
for (int i=0;i<s.length();i++)
{
BST_Insert(T,s[i]);
}
printf("二叉查找树中序遍历序列:");
InOrder(T);
printf("n");
}
//删除 调用BST_Delete
void DeleteBSTree(BSTree &T)
{
TElemType key;
printf("请输入要删除的数据：n");
cin >> key;
if (BST_Delete(T, key))
{
printf("删除成功！n");
}
else
{
printf("未找到！n");
}
}
int main()
{
int choice;
BSTree T = NULL;
while(1){
printf("tt1.建立有序表，采用折半查找关键字nn");
printf("tt2.建立二叉排序树nn");
printf("tt3.删除关键字元素nn");
printf("tt4.退出nn");
printf("nnnt请输入菜单序号：");
scanf("%d",&choice);
if(choice==4)break;
switch(choice)
{
case 1:
int e,c;
SSTable S;
CreateList(S);
cout<<"建立有序表";
print(S);
cout<<"输入要查找的关键字";
cin>>e;
cout<<"元素的位置为";
c=Search_Bin(S,e);
cout<<c;
printf("n");
break;
case 2:CreateBSTree(T);break;
case 3:DeleteBSTree(T);break;
}
}
return 0;
}

最后

以上就是昏睡飞鸟为你收集整理的实验五 查找的全部内容，希望文章能够帮你解决实验五 查找所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。