实验目的:

  • 熟悉常用查找算法;
  • 熟悉二叉排序树的定义和有关操作。

实验内容:

查找表结构定义如下

typedef struct {
int key; //主关键字
... //数据元素其他项的信息,可不定义;
}ElemType;
typedef struct {
ElemType *R; //表基址
int length; //表长
}SSTable;
  • 1.编写静态查找的三种算法:顺序查找、折半查找和分块查找
  • 2.编写二叉排序的建立、显示、插入、删除、查找元素

实验要求:

  • 程序要添加适当的注释,程序的书写要采用缩进格式。
  • 程序要具在一定的健壮性,即当输入数据非法时,程序也能适当地做出反应,如插入删除时指定的位置不对等等。
  • 程序要做到界面友好,在程序运行时用户可以根据相应的提示信息进行操作。
  • 在体会中描述如下内容:
    按照你的测试数据建立的二叉排序树示意图:
    开始录入数据示意图 开始录入数据示意图
    插入数据4示意图 插入数据4示意图
    删除数据8示意图 删除数据8示意图

实现代码


第一题:

SSTable.h:

//线性表的查找的定义
// Created by 17235 on 2020/5/9.
//

#ifndef SHIYAN7_SSTABLE_H
#define SHIYAN7_SSTABLE_H

#define MaxLength 5

typedef struct {
int key; //主关键字
//InfoType otherinfo; //数据元素其他项的信息,可不定义;
} ElemType;

typedef struct {
ElemType *R; //表基址
int length; //表长
}SSTable;

//索引表结构
typedef struct directionChart{
int key;
int start;
int end;
}DirectionChart[MaxLength];

/*
* 初始化顺序表
*/
extern SSTable initTable();

/*
* 顺序查找
*/
extern int Search_Seq(SSTable ST,int key);

/*
* 折半查找
*/
extern int Search_Bin(SSTable ST,int key);

/*
* 创建索引块
*/
extern int createIndex(SSTable ST,DirectionChart &Index);

/*
* 分块查找
*/
extern int blockIndex(SSTable ST,ElemType e);
#endif //SHIYAN7_SSTABLE_H

SSTable.cpp:

 
//
// Created by 17235 on 2020/5/9.
//

#include "SSTable.h"
#include <iostream>
/*
* 初始化顺序表
*/
SSTable initTable(){
SSTable t;
t.R = (ElemType *)malloc(MaxLength*sizeof(ElemType));
if (!t.R){
printf("初始化失败\n");
exit(0);
}
t.length=0;
return t;
}



/*
* 顺序查找
*/
int Search_Seq(SSTable ST,int key){
for (int i = ST.length; i >= 1; --i){
if (ST.R[i].key == key){
return i;
}
}
return 0;
}

/*
* 折半查找
*/
int Search_Bin(SSTable ST,int key){
int low = 1;
int high = ST.length;
while (low <= high){
int 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;
}

/*
*创建块用于分块查找
*/
int createIndex(SSTable ST,DirectionChart &Index){
int j=1;
for(int i=0;i<MaxLength;i++){
Index[i].start=j;
Index[i].key=ST.R[j].key;
j+=6;
Index[i].end=j-1;
for(int k=Index[i].start+1;k<=Index[i].end;k++){
if(Index[i].key<ST.R[k].key){
Index[i].key=ST.R[k].key;
}
}
}
return 0;
}

/*
* 分块查找
*/
int blockIndex(SSTable ST,ElemType e){
DirectionChart Index;
createIndex(ST,Index);
int i,j;
i=0;
while(i<MaxLength && e.key>Index[i].key){
i++;
}
if(i>MaxLength){
return 0;
}
j=Index[i].start;
while(j<=Index[i].end && ST.R[j].key!=e.key){
j++;
}
if(j>Index[i].end) {
j = 0;
}
return j;
}

main.cpp:

#include <iostream>
#include "SSTable.h"

int main() {
int tempKey,result;
SSTable S;
S = initTable();
S.R[0].key = 5;
S.R[1].key = 3;
S.R[2].key = 8;
S.R[3].key = 6;
S.R[4].key = 9;
S.length = MaxLength;
printf("请输入要查找的数据值:\n");
scanf("%d",&tempKey);
result = Search_Seq(S,tempKey);
if (result == 0){
printf("顺序查找结果:没找到\n");
}else{
printf("顺序查找结果:元素所在位置:%d\n",result);
}
result = -1;
result = Search_Bin(S,tempKey);
if (result == 0){
printf("顺序查找结果:没找到\n");
}else{
printf("折半查找结果:元素所在位置:%d\n",result);
}
result = -1;
ElemType e;
e.key = tempKey;
result = blockIndex(S,e);
if (result == 0){
printf("分块查找结果:没找到\n");
}else{
printf("分块查找结果:元素所在位置:%d\n",result);
}
return 0;
}

实验截图:

image-20200515120429930


第二题:

BST.h:

//二叉排序树
// Created by 17235 on 2020/5/14.
//

#ifndef SHIYAN7_2_BST_H
#define SHIYAN7_2_BST_H

typedef int KeyType ;
typedef int Status;

typedef struct{
KeyType key;//关键字项
}ElemType;

typedef struct BSTNode{
ElemType data;//每个结点的数据域
struct BSTNode *lchild;//左结点
struct BSTNode *rchild;//右结点
}BSTNode,*BSTree;

/**
* 二叉排序树的插入
* @param T
* @param e
*/
extern void insertBST(BSTree &T, ElemType e);

/**
* 二叉排序树的建立
* @param T
*/
extern void CreateBST(BSTree &T);

/**
* 以中序遍历的方式显示二叉树
* @param T
*/
extern void InOrderTraverse(BSTree T);

/**
* 在二叉排序树里查找元素
* @param T
* @param key
* @return 当前二叉排序树的指针
*/
extern BSTree searchBST(BSTree T,KeyType key);

/**
* 二叉排序树的元素的删除
* @param T
* @param key
*/
extern void DeleteBST(BSTree &T,KeyType key);
#endif //SHIYAN7_2_BST_H

BST.cpp:

//
// Created by 17235 on 2020/5/14.
//

#include "BST.h"
#include <iostream>

#define ENDFLAG -1

/**
* 二叉排序树的插入
* @param T
* @param e
*/
void insertBST(BSTree &T, ElemType e){
if(!T){
BSTree S = new BSTNode;
S->data = e;
S->lchild = NULL;
S->rchild = NULL;
T = S;
}
else if(e.key<T->data.key)
insertBST(T->lchild,e);
else if(e.key>T->data.key)
insertBST(T->rchild,e);
}

/**
* 二叉排序树的建立
* @param T
*/
void CreateBST(BSTree &T){
T = NULL;
ElemType *e = new ElemType;
printf("请输入元素:");
int a;
scanf("%d",&a);
e->key = a;
while(e->key != ENDFLAG){
insertBST(T,*e);
printf("请输入元素:");
int a;
scanf("%d",&a);
e->key = a;
}
}

/**
* 以中序遍历的方式显示二叉树
* @param T
*/
void InOrderTraverse(BSTree T){
if (T == NULL){
return;
}
//遍历左子树
InOrderTraverse(T->lchild);
//输出结点数据
printf("%d ",T->data.key);
//遍历右子树
InOrderTraverse(T->rchild);
}

/**
* 在二叉排序树里查找元素
* @param T
* @param key
* @return 当前二叉排序树的指针
*/
BSTree searchBST(BSTree T,KeyType key){
if(!T || key == T->data.key){
return T;
}
else if(key<T->data.key)
return searchBST(T->lchild,key);
else
return searchBST(T->rchild,key);
}


/**
* 二叉排序树的元素的删除
* @param T
* @param key
*/
void DeleteBST(BSTree &T,KeyType key){
BSTree p = new BSTNode;
p=T;
BSTree f = new BSTNode;
f=NULL;

while(p){
if(p->data.key==key)
break;
f=p;
if(p->data.key>key) {
p = p->lchild;
}
else {
p=p->rchild;
}
}
if(!p) return;
BSTree q = new BSTNode;
q = p;

if((p->lchild) && (p->rchild)){
BSTree s = new BSTNode;
s = p->lchild;
while(s->rchild){
q = s;
s = s->rchild;
}
p->data.key = s->data.key;
if(q != p){
q->rchild = s->lchild;
}
else{
q->lchild = s->lchild;
}
delete s;
return;
}
else if(!p->rchild){
p = p->lchild;
}
else if(!p->lchild){
p = p->rchild;
}

if(!f){
T=p;
}
else if(q==f->lchild)
f->lchild=p;
else
f->rchild=p;
delete q;
}

main.cpp:

#include <iostream>
#include "BST.h"

using namespace std;

int main(){
BSTree bsTree;
int findNumber;
printf("开始建立二叉排序树,以-1结束\n");
CreateBST(bsTree);
printf("二叉排序树的显示,以中序遍历来显示\n");
InOrderTraverse(bsTree);
printf("\n");

printf("二叉排序树的查找,请输入关键值key\n");
cin>>findNumber;
if(searchBST(bsTree,findNumber)!=NULL){
printf("%d在二叉排序树中\n",findNumber);
} else{
printf("%d不在二叉排序树中\n",findNumber);
}

printf("二叉排序树的插入,请输入关键值key\n");
ElemType elemType;
cin>>findNumber;
elemType.key=findNumber;
insertBST(bsTree,elemType);
printf("插入后的二叉排序树的显示,以中序遍历来显示\n");
InOrderTraverse(bsTree);
printf("\n");

printf("二叉排序树的删除,请输入关键值key\n");
cin>>findNumber;
DeleteBST(bsTree,findNumber);
printf("删除后的二叉排序树的显示,以中序遍历来显示\n");
InOrderTraverse(bsTree);
printf("\n");
return 0;
}

实验截图:

image-20200515120542928

image-20200515120602596