编程题实训-查找

第1关：基于递归的折半查找

任务描述

请编写一个递归的折半查找算法，查找给定有序数组中的某一元素。

编程要求

输入

多组数据，每组数据有三行。第一行为数组长度n，第二行为n个递增排列的数字，第三行为需要查找的数字k。当n=0时输入结束。

输出

每组数据输出一行，如果可以找到数字，则输出“YES”，否则输出“NO”。

#include<iostream>
using namespace std;
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[100],k;
        for(int i=0;i<n;i++)
            cin>>a[i];			//输入n个递增排列的数字
        cin>>k;				//输入需要查找的数字k
        if(BinSearch_Cur(a,k,0,n-1))
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

第2关：二叉排序树的判定?

任务描述

假设二叉树每个结点的元素均为一个单字符，根据给定的字符序列按照先序遍历的顺序递归创建该树的二叉链表，然后判断该二叉树是否为二叉排序树。

编程要求

输入

多组数据，每组数据有一行。每行为一个二叉树对应的前序序列（其中‘#’表示空树）。当序列为“#”时，输入结束。

输出

每组数据输出1行，若此二叉树为二叉排序树则输出“YES”，否则输出“NO”。

#include<iostream>
#include <string.h>
using namespace std;
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T,char S[],int &i)
{//先序建立二叉树
	if(S[i]=='#') T=NULL;
	else
	{
		T=new BiTNode;
		T->data=S[i];
		CreateBiTree(T->lchild,S,++i);
		CreateBiTree(T->rchild,S,++i);
	}
}
BiTree pre=NULL;   //前驱指针
void JudgeBST(BiTree T,int &flag)
{//判断二叉树T是否为二叉排序树，flag初值为1
    /**************begin************/
    if(T!=NULL&&flag)
    {
        JudgeBST(T->lchild,flag);//中序遍历左子树
        if(pre==NULL) pre=T;     //中序遍历的第一个结点不必判断
        else if(pre->data<T->data) pre=T;   //前驱指针指向当前结点
        else flag =0;                //不是二叉排序树
        JudgeBST(T->rchild,flag);   //中序遍历右子树
    }
    /**************end************/
}
int main()
{
	char S[100];
	while(cin>>S)
	{
		if(strcmp(S,"#")==0) break;
		int i=-1;
		int flag=1;
	  	BiTree T;
		CreateBiTree(T,S,++i);
		JudgeBST(T,flag);
		if(flag)
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
	return 0;
}

?第3关：二叉排序树的限定条件下的数据输出

任务描述

已知二叉排序树采用二叉链表存储结构，根结点的指针为T,链结点的结构为(lchild,data,rchild),其中lchild、rchild分别指向该结点左，右孩子的指针，data域存放结点数据。试编写算法，从小到大输出二叉排序树中所有数值大于等于x的结点的数据。要求先找到第一个满足条件的结点后，再依次输出其他满足条件的结点。

编程要求

输入

多组数据，每组三行。第一行为二叉排序树的结点数n。第二行为空格分隔的n个数字，对应二叉排序树中的n个结点。第三行为一个数字x。n=0时输入结束。

输出

每组数据输出一行。从小到大输出大于等于x的结点数据。每个数据用空格分隔。

#include<iostream>
using namespace std;
typedef struct BSTNode
{//二叉排序树的二叉链表存储表示
	int data;
	struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
int sum;设一个全局变量sum,为了判断该数据是否为输出的最后一个数
void InsertBST(BSTree &T,int e)
{//当二叉排序树T中不存在关键字等于e的数据元素时，则插入该元素
    /**************begin************/
	if(!T)
    {                            //找到插入位置，递归结束
        BSTree S=new BSTNode;    //生产新结点*S
        S->data=e;               //新结点*S的数据域置为e
        S->lchild=NULL;          //把新结点作为叶子结点
        S->rchild=NULL;
        T=S;                     //把新结点*S链接到已找到的插入位置
    }
    else
    {
        if(e<T->data)
            InsertBST(T->lchild,e);      //将*S插入左子树
        else
            InsertBST(T->rchild,e);      //将*S插入右子树
    }
    /**************end************/
}
BSTree CreateBSTree(int n)
{//构建二叉排序树
    BSTree T=NULL;
    int e;
    for(int i=0;i<n;i++)
    {
        cin>>e;
        InsertBST(T,e);
    }
    return T;
}
void InOrderTraverse(BSTree T,int x)
{//中序遍历二叉树T的递归算法
    if(T==NULL) return;   //空树
    else
    {
        InOrderTraverse(T->lchild,x);//递归遍历左子树
        sum--;         //每次遍历时sum减1
        if(T->data>=x)
        {                               //输出二叉排序树中所有数值大于等于x的结点的数据
            cout<<T->data;              //先输出数据
            if(sum==0) cout<<endl;    //如果是最后一个元素，换行
            else cout<<" ";           //非末位元素，输出空格
        }
        InOrderTraverse(T->rchild,x);//递归遍历右子树
    }
}
int main()
{
	int n,x;        //二叉排序树的结点数n，数字x
	while(cin>>n)
	{
		if(n==0) break;
		BSTree T=NULL;
		T=CreateBSTree(n);
		cin>>x;          //输入数字x
		sum=n;          //结点数n赋给sum
		InOrderTraverse(T,x);
	}
	return 0;
}

第4关：基于非递归的二叉排序树的结点的查找和插入

任务描述

已知二叉树T的结点形式为(llink,data,count,rlink)，在树中查找值为x的结点，若找到，则计数（count）加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树。请写出其非递归算法。

编程要求

输入

多组数据，每组数据3行。第一行为二叉排序树的结点数n，第二行为空格分隔的n个数字，对应二叉排序树中的n个结点，第三行为查找的值x。n=0时输入结束。

输出

每组数据输出两行。第一行为二叉排序树的中序序列（空格分隔），第二行为其对应的计数count。

#include<iostream>
using namespace std;
typedef struct BiTNode
{
	int data;
	int cnt;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int sum=0;        //全局变量sum表示排序树当前结点的个数,也为了判断数据是否为输出的最后一个数
void SearchBST(BiTree &T,int x)
{//基于非递归的二叉排序树的结点的查找和插入
    /**************begin************/
    BiTree s=new BiTNode;                    //生成一个数据域为x的新结点s
    s->data=x;
    s->cnt=0;
    s->lchild=NULL;
    s->rchild=NULL;
    if(!T)                                    //如果该树为空，则将待插入结点*s作为根结点插入到空树中
    {
        T=s;
        sum++;
        return;
    }
    BiTree q=T,f=NULL;
    while(q)                                //从根结点开始比较，直到结点为空
    {
        if(q->data==x)                        //如果找到该值则计数加1
        {
            q->cnt++;
            return;                            //函数结束
        }
        f=q;                                //如果没有找到，需要用f保存q结点
                                            //因为q指向的最后一个非空结点将会是x的父结点
        if(q->data>x)                        //x小于当前结点值，使指针指向左子树
            q=q->lchild;
        else                                 //x大于当前结点值，使指针指向右子树
            q=q->rchild;
    }
    if(f->data>x)                            //如果找不到，就将新结点插入树中
    {
        sum++;
        f->lchild=s;
    }
    else
    {
        sum++;
        f->rchild=s;
    }
    /**************end************/
}
void InOrderTraverse(BiTree T)
{//中序遍历输出二叉树T结点
    if(T==NULL) return;
    else
    {
        InOrderTraverse(T->lchild);
        sum--;
        cout<<T->data;
        if(sum==0)
            cout<<endl;
        else
            cout<<" ";
        InOrderTraverse(T->rchild);
    }
}
void Print_Count(BiTree T,int x)
{//中序遍历输出二叉树T计数
    if(T==NULL) return;
    else
    {
        Print_Count(T->lchild,x);
        sum--;
        cout<<T->cnt;
        if(sum==0)
            cout<<endl;
        else
            cout<<" ";
        Print_Count(T->rchild,x);
    }
}
int main()
{
	int n;
	while(cin>>n)
	{
		if(n==0) break;
		int e;        //变量e用于接收输入数据
	  	BiTree T=NULL;
		for(int i=0;i<n;i++)  //基于非递归的二叉排序树的结点的查找和插入
		{
			cin>>e;
			SearchBST(T,e);
		}
		int x;           //查找值为x
		cin>>x;
		SearchBST(T,x);
		if(sum==n+1) n++; //没找到时，x作为一个新结点插入树中，此时排序树的结点数加1
		sum=n;
		InOrderTraverse(T);//中序遍历输出二叉树T结点
		sum=n;
		Print_Count(T,x);   //中序遍历输出二叉树T计数
	}
	return 0;
}

第5关：平衡二叉树的高度的计算

任务描述

假设一棵平衡二叉树的每个结点都标明了平衡因子b，设计一个算法，求平衡二叉树的高度。

编程要求

输入

多组数据，每组数据一行，为平衡二叉树的先序序列。输入的数字为该节点的平衡因子。当序列为“#”时，输入结束。

输出

每组数据输出一行，为平衡二叉树的高度。

#include<iostream>
#include <string.h>
using namespace std;
typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree &T,char S[],int &i)
{//先序建立二叉树
	if(S[i]=='#')
		T=NULL;
	else
	{
		T=new BiTNode;
		T->data=S[i];
		CreateBiTree(T->lchild,S,++i);
		CreateBiTree(T->rchild,S,++i);
	}
}
int Height(BiTree T)
{//求平衡二叉树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 S[100];//如果平衡因子b=-1，会被字符数组割裂成'-'和'1'，故本题输入样例不包含b=-1
	while(cin>>S)
	{
		if(strcmp(S,"#")==0) break;
		int i=-1;
	  	BiTree T;
		CreateBiTree(T,S,++i);
		cout<<Height(T)<<endl;
	}
	return 0;
}

第6关：基于链地址法的散列表的插入

任务描述

请写出在散列表中插入关键字为k的一个记录的算法，设散列函数为H,H(key)=key%13，解决冲突的方法为链地址法。

编程要求

输入

多组数据，每组三行，第一行为待输入的关键字的个数n，第二行为对应的n个关键字，第三行为需要插入的关键字k。当n=0时输入结束。

输出

每组数据输出用链地址法处理冲突的散列表。

#include<iostream>
using namespace std;
typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode,*LinkList;
LinkList H[13];    //链地址法，13个单链表
void Hash(int e)
{//基于链地址法的散列表的插入
    /**************begin************/
	int index=e%13;       //计算散列地址
    LinkList p=H[index];   //工作指针p指向链表的头结点
    while(p->next)         //移至表尾
        p=p->next;
    LinkList q=new LNode;    //生成新结点*q
    q->data=e;               //将新结点*q的数据域置为e
    q->next=NULL;            //将新结点*q插入在尾结点*p之后
    p->next=q;
    /**************end************/
}
void Input(int n)
{//输入数据
	for(int i=0;i<13;i++)     //建立13个带有头结点的单链表
	{
		H[i]=new LNode;
		H[i]->next=NULL;
	}
	while(n--)          //输入n个关键字,构造散列表
	{
		int e;
		cin>>e;
		Hash(e);
	}
}
void Output()
{//输出数据
	for(int i=0;i<13;i++)
	{
		cout<<i;                 //输出散列地址
		LinkList p=H[i]->next;   //p初始化为链表的首元结点
		while(p)
		{
			cout<<" "<<p->data;
			p=p->next;
		}
		cout<<endl;
	}
}
int main()
{
	int n;
	while(cin>>n)
	{
		if(n==0) break;
		Input(n);     //输入数据
		int k;      //需要插入的关键字k
		cin>>k;
		Hash(k);
		Output();  //输出数据
	}
	return 0;
}

第7关：基于链地址法的散列表的删除?

任务描述

请写出在散列表中删除关键字为k的一个记录的算法，设散列函数为H，H(key)=key%13，解决冲突的方法为链地址法。

编程要求

输入

多组数据，每组三行，第一行为待输入的关键字的个数n，第二行为对应的n个关键字，第三行为需要删除的关键字k。当n=0时输入结束。

输出

每组数据输出用链地址法处理冲突的散列表。

#include<iostream>
using namespace std;
typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode,*LinkList;
LinkList H[13];   //链地址法，13个单链表
void Hash(int e)
{//基于链地址法的散列表的插入
	int index=e%13;       //计算散列地址
	LinkList p=H[index];   //工作指针p指向链表的头结点
	while(p->next)         //移至表尾
		p=p->next;
	LinkList q=new LNode;    //生成新结点*q
	q->data=e;               //将新结点*q的数据域置为e
	q->next=NULL;            //将新结点*q插入在尾结点*p之后
	p->next=q;
}
void Input(int n)
{//输入数据
	for(int i=0;i<13;i++)     //建立13个带有头结点的单链表
	{
		H[i]=new LNode;
		H[i]->next=NULL;
	}
	while(n--)          //输入n个关键字,构造散列表
	{
		int e;
		cin>>e;
		Hash(e);
	}
}
void Delete(int e)
{//基于链地址法的散列表的删除
    /**************begin************/
	int index=e%13;      //计算散列地址
    LinkList p=H[index];   //工作指针p指向链表的头结点
    while(p->next)         //p指向待删除结点的前一个结点，找不到待删除结点时，p最终指向表尾结点
    {
        if(p->next->data==e)
            break;
        p=p->next;
    }
    if(p->next!=NULL)    //p没指向表尾结点时
    {
        LinkList q=p->next;
        p->next=q->next;
        delete q;
    }
    /**************end************/
}
void Output()
{//输出数据
	for(int i=0;i<13;i++)
	{
		cout<<i;                 //输出散列地址
		LinkList p=H[i]->next;   //p初始化为链表的首元结点
		while(p)
		{
			cout<<" "<<p->data;
			p=p->next;
		}
		cout<<endl;
	}
}
int main()
{
	int n;
	while(cin>>n)
	{
		if(n==0) break;
		Input(n);     //输入数据
		int k;
		cin>>k;
		Delete(k);  //需要删除的关键字k
		Output();  //输出数据
	}
	return 0;
}

第8关：基于快排思想的查找

任务描述

借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..n]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。

编程要求

输入

多组数据，每组数据三行。第一行为序列的长度n，第二行为序列的n个元素（元素之间用空格分隔，元素都为正整数），第三行为要查找的key值。当n等于0时，输入结束。

输出

每组数据输出一行。如果查找成功，输出key在数组中的位置（1到n）和key的值，两个数字之间用空格隔开。如果查找失败，输出“not find”。

#include<iostream>
using namespace std;
int Search(int r[],int low,int high,int key)
{//基于快排思想的查找
    /**************begin************/
    while(low<high)
    {
        if(r[low]>key&&r[high]<key)      //如果关键字小于数组下界的值且大于数组上界的值，更新指针high和low
        {
            high--;
            low++;
        }
        while(low<=high&&r[high]>key) high--;   //从右侧开始找到第一个不大于关键字的记录，其位置为high
        if(r[high]==key) return high;           //查找成功返回其位置
        while(low<=high&&r[low]<key) low++;     //从左侧开始找到第一个不小于关键字的记录，其位置为low
        if(r[low]==key) return low;             //查找成功返回其位置
    }
    cout<<"not find"<<endl;     //查找失败
    return 0;
    /**************end************/
}
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        int r[n],key;
        for(int i=0;i<n;i++)   //输入数据
            cin>>r[i];
        cin>>key;       //输入要查找的key值
        if(Search(r,0,n-1,key))    //如果查找成功
			cout<<Search(r,0,n-1,key)+1<<" "<<key<<endl;  //输出key在数组中的位置（1到n）和key的值
    }
}

第9关：查找链表倒数第k个结点

任务描述

已知一个带有表头结点的单链表，结点结构为（data，link），假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。

编程要求

输入

多组数据，每组数据两行。第一行为链表的长度n，第二行为链表的n个元素（元素之间用空格分隔，元素都为正整数）。当n等于0时，输入结束。第三行为要查询链表的倒数索引k。

输出

输出数据一行。若查询到值则输出值，否则不输出。

#include <iostream>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*LinkList;
void CreateList_R(LinkList &L,int n)
{//后插法创建单链表
    L=new LNode;
    L->next=NULL;
    LinkList r=L;
    for(int i=0;i<n;i++)
    {
        LinkList p=new LNode;
        cin>>p->data;
        p->next=NULL;
        r->next=p;
        r=p;
    }
}
int Search_k(LinkList L,int a[],int k)
{//查找链表倒数第k个结点
//通过一趟遍历把该链表的结点都存入到一个辅助数组中，再通过数组下标可直接获取倒数第k个结点，但这样会需要额外的存储空间，因此空间复杂度为O(n)
    /**************begin************/
    LinkList p=L->next;          //初始化指针p指向首元结点
    int length=0;               //length记录链表长度，也是数组元素的个数
    while(p!=NULL)
    {
        a[length++]=p->data;
        p=p->next;
    }
    if(k>length) return ERROR;
    else cout<<a[length-k]<<endl;
    return OK;
    /**************end************/
}
int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        LinkList L;
        CreateList_R(L,n);
        int k,a[MAXSIZE];
        cin>>k;
        Search_k(L,a,k);
    }
    return 0;
}

?

?