算法 c++ 查找：折半查找、平衡二叉树、散列表（习题-1、5、6）

第1关：折半查找的递归算法（算法设计题1）

#include

using namespace std;

//在有序表ST中折半查找其关键字等于key的数据元素，若查找成功，返回k所在位置，查找失败返回0

int BinSearch_Cur(int a[],int key,int low,int high)

{

/***********************Begin**********************/

if(low <= high)

{

int mid = low + high >> 1;

if(a[mid] == key) return mid + 1;

else if(a[mid] > key) return BinSearch_Cur(a,key,low,mid - 1);

else return BinSearch_Cur(a,key,mid + 1,high);

}

return 0;

/*********************** End **********************/

}

int main()

{

int n; //输入数组长度n

while(cin>>n)

{

if(n==0) break;

int a[99],key;

for(int i=0;i

cin>>a[i]; //输入n个递增排列的数字

cin>>key; //输入需要查找的数字key

cout<

}

return 0;

}

第2关：平衡二叉树的高度（算法设计题5）

//平衡二叉树高度的计算

#include

using namespace std;

typedef struct BiTNode

{

char data;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

void CreatBiTree(BiTree &T){

//按先序次序输入二叉树中结点的值 创建二叉链表表示的二叉树

char ch;

cin>>ch;

if(ch=='#') T = NULL; //递归结束 空树

else{ //递归创建二叉树

T = new BiTNode; //生成根节点

T->data = ch; //根结点数据域置ch

CreatBiTree(T->lchild); //递归创建左子树

CreatBiTree(T->rchild); //递归创建右子树

}

}

int Depth(BiTree T)

{

/***********************Begin**********************/

int level = 0;

BiTree p = T;

while(p)

{

level++ ;

if(p -> data < 0) p = p -> rchild;

else p = p -> lchild;

}

return level;

/*********************** End **********************/

}

int main()

{

char ch;

BiTree T;

CreatBiTree(T);

cout<

return 0;

}

第3关：散列表关键字的插入和删除（算法设计题6）

#include

#define LENGTH 7

using namespace std;

typedef struct LNode

{

int data;

struct LNode *next;

}LNode,*LinkList;

LinkList HT[LENGTH];

int H(int data)

{

return data%LENGTH;

}

bool Insert_K( )

{

/***********************Begin**********************/

int x;

cin>>x;

int ant = H(x);

LinkList p = HT[ant];

while (p->next){

if(p->next->data==x)

return false;

p=p->next;

}

LinkList s;

s=new LNode;

s->data=x;

s->next=p->next;

p->next=s;

return true;

/*********************** End **********************/

}

bool Delete_K(int data)

{

/***********************Begin**********************/

int ant=H(data);

LinkList p=HT[ant];

while (p->next){

if(p->next->data==data){

LinkList s=p->next;

p->next=s->next;

delete s;

return true;

}

p=p->next;

}

return false;

/*********************** End **********************/

}

void Output()

{//输出数据

for(int i=0;i

{

cout<

LinkList p=HT[i]->next; //p初始化为链表的首元结点

while(p)

{

cout<data;

p=p->next;

if(p) cout<<" ";

}

cout<

}

}

void initHash()

{

for(int i=0;i

{

HT[i]=new LNode;

HT[i]->next=NULL;

}

}

int main()

{

initHash();

int n,ndel;

cin>>n;

for(int i=0;i

Insert_K();

Output();

cin>>ndel;

Delete_K(ndel);

Output();

return 0;

}

参考文章