网站可以多个域名吗,cms系统教程,可以做驾校推广的网站,百度下载并安装到桌面第1关#xff1a;基于递归的折半查找
任务描述
请编写一个递归的折半查找算法#xff0c;查找给定有序数组中的某一元素。
编程要求
输入
多组数据#xff0c;每组数据有三行。第一行为数组长度n#xff0c;第二行为n个递增排列的数字#xff0c;第三行为需要查找的数…第1关基于递归的折半查找
任务描述
请编写一个递归的折半查找算法查找给定有序数组中的某一元素。
编程要求
输入
多组数据每组数据有三行。第一行为数组长度n第二行为n个递增排列的数字第三行为需要查找的数字k。当n0时输入结束。
输出
每组数据输出一行如果可以找到数字则输出“YES”否则输出“NO”。
#includeiostream
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;//数组长度nwhile(cinn){if(n0) break;int a[100],k;for(int i0;in;i)cina[i]; //输入n个递增排列的数字cink; //输入需要查找的数字kif(BinSearch_Cur(a,k,0,n-1))coutYESendl;elsecoutNOendl;}return 0;
}
第2关二叉排序树的判定
任务描述
假设二叉树每个结点的元素均为一个单字符根据给定的字符序列按照先序遍历的顺序递归创建该树的二叉链表然后判断该二叉树是否为二叉排序树。
编程要求
输入
多组数据每组数据有一行。每行为一个二叉树对应的前序序列其中‘#’表示空树。当序列为“#”时输入结束。
输出
每组数据输出1行若此二叉树为二叉排序树则输出“YES”否则输出“NO”。
#includeiostream
#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]#) TNULL;else{Tnew BiTNode;T-dataS[i];CreateBiTree(T-lchild,S,i);CreateBiTree(T-rchild,S,i);}
}
BiTree preNULL; //前驱指针
void JudgeBST(BiTree T,int flag)
{//判断二叉树T是否为二叉排序树flag初值为1/**************begin************/if(T!NULLflag){JudgeBST(T-lchild,flag);//中序遍历左子树if(preNULL) preT; //中序遍历的第一个结点不必判断else if(pre-dataT-data) preT; //前驱指针指向当前结点else flag 0; //不是二叉排序树JudgeBST(T-rchild,flag); //中序遍历右子树}/**************end************/
}
int main()
{char S[100];while(cinS){if(strcmp(S,#)0) break;int i-1;int flag1;BiTree T;CreateBiTree(T,S,i);JudgeBST(T,flag);if(flag)coutYESendl;elsecoutNOendl;}return 0;
} 第3关二叉排序树的限定条件下的数据输出
任务描述
已知二叉排序树采用二叉链表存储结构根结点的指针为T,链结点的结构为(lchild,data,rchild),其中lchild、rchild分别指向该结点左右孩子的指针data域存放结点数据。试编写算法从小到大输出二叉排序树中所有数值大于等于x的结点的数据。要求先找到第一个满足条件的结点后再依次输出其他满足条件的结点。
编程要求
输入
多组数据每组三行。第一行为二叉排序树的结点数n。第二行为空格分隔的n个数字对应二叉排序树中的n个结点。第三行为一个数字x。n0时输入结束。
输出
每组数据输出一行。从小到大输出大于等于x的结点数据。每个数据用空格分隔。
#includeiostream
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 Snew BSTNode; //生产新结点*SS-datae; //新结点*S的数据域置为eS-lchildNULL; //把新结点作为叶子结点S-rchildNULL;TS; //把新结点*S链接到已找到的插入位置}else{if(eT-data)InsertBST(T-lchild,e); //将*S插入左子树elseInsertBST(T-rchild,e); //将*S插入右子树}/**************end************/
}
BSTree CreateBSTree(int n)
{//构建二叉排序树BSTree TNULL;int e;for(int i0;in;i){cine;InsertBST(T,e);}return T;
}
void InOrderTraverse(BSTree T,int x)
{//中序遍历二叉树T的递归算法if(TNULL) return; //空树else{InOrderTraverse(T-lchild,x);//递归遍历左子树sum--; //每次遍历时sum减1if(T-datax){ //输出二叉排序树中所有数值大于等于x的结点的数据coutT-data; //先输出数据if(sum0) coutendl; //如果是最后一个元素换行else cout ; //非末位元素输出空格}InOrderTraverse(T-rchild,x);//递归遍历右子树}
}
int main()
{int n,x; //二叉排序树的结点数n数字xwhile(cinn){if(n0) break;BSTree TNULL;TCreateBSTree(n);cinx; //输入数字xsumn; //结点数n赋给sumInOrderTraverse(T,x);}return 0;
}
第4关基于非递归的二叉排序树的结点的查找和插入
任务描述
已知二叉树T的结点形式为(llink,data,count,rlink)在树中查找值为x的结点若找到则计数count加1否则作为一个新结点插入树中插入后仍为二叉排序树。请写出其非递归算法。
编程要求
输入
多组数据每组数据3行。第一行为二叉排序树的结点数n第二行为空格分隔的n个数字对应二叉排序树中的n个结点第三行为查找的值x。n0时输入结束。
输出
每组数据输出两行。第一行为二叉排序树的中序序列空格分隔第二行为其对应的计数count。
#includeiostream
using namespace std;
typedef struct BiTNode
{int data;int cnt;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int sum0; //全局变量sum表示排序树当前结点的个数,也为了判断数据是否为输出的最后一个数
void SearchBST(BiTree T,int x)
{//基于非递归的二叉排序树的结点的查找和插入/**************begin************/BiTree snew BiTNode; //生成一个数据域为x的新结点ss-datax;s-cnt0;s-lchildNULL;s-rchildNULL;if(!T) //如果该树为空则将待插入结点*s作为根结点插入到空树中{Ts;sum;return;}BiTree qT,fNULL;while(q) //从根结点开始比较直到结点为空{if(q-datax) //如果找到该值则计数加1{q-cnt;return; //函数结束}fq; //如果没有找到需要用f保存q结点//因为q指向的最后一个非空结点将会是x的父结点if(q-datax) //x小于当前结点值使指针指向左子树qq-lchild;else //x大于当前结点值使指针指向右子树qq-rchild;}if(f-datax) //如果找不到就将新结点插入树中{sum;f-lchilds;}else{sum;f-rchilds;}/**************end************/
}
void InOrderTraverse(BiTree T)
{//中序遍历输出二叉树T结点if(TNULL) return;else{InOrderTraverse(T-lchild);sum--;coutT-data;if(sum0)coutendl;elsecout ;InOrderTraverse(T-rchild);}
}
void Print_Count(BiTree T,int x)
{//中序遍历输出二叉树T计数if(TNULL) return;else{Print_Count(T-lchild,x);sum--;coutT-cnt;if(sum0)coutendl;elsecout ;Print_Count(T-rchild,x);}
}
int main()
{int n;while(cinn){if(n0) break;int e; //变量e用于接收输入数据BiTree TNULL;for(int i0;in;i) //基于非递归的二叉排序树的结点的查找和插入{cine;SearchBST(T,e);}int x; //查找值为xcinx;SearchBST(T,x);if(sumn1) n; //没找到时x作为一个新结点插入树中此时排序树的结点数加1sumn;InOrderTraverse(T);//中序遍历输出二叉树T结点sumn;Print_Count(T,x); //中序遍历输出二叉树T计数}return 0;
}
第5关平衡二叉树的高度的计算
任务描述
假设一棵平衡二叉树的每个结点都标明了平衡因子b设计一个算法求平衡二叉树的高度。
编程要求
输入
多组数据每组数据一行为平衡二叉树的先序序列。输入的数字为该节点的平衡因子。当序列为“#”时输入结束。
输出
每组数据输出一行为平衡二叉树的高度。
#includeiostream
#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]#)TNULL;else{Tnew BiTNode;T-dataS[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-1while(cinS){if(strcmp(S,#)0) break;int i-1;BiTree T;CreateBiTree(T,S,i);coutHeight(T)endl;}return 0;
}
第6关基于链地址法的散列表的插入
任务描述
请写出在散列表中插入关键字为k的一个记录的算法设散列函数为H,H(key)key%13解决冲突的方法为链地址法。
编程要求
输入
多组数据每组三行第一行为待输入的关键字的个数n第二行为对应的n个关键字第三行为需要插入的关键字k。当n0时输入结束。
输出
每组数据输出用链地址法处理冲突的散列表。
#includeiostream
using namespace std;
typedef struct LNode
{int data;struct LNode *next;
}LNode,*LinkList;
LinkList H[13]; //链地址法13个单链表
void Hash(int e)
{//基于链地址法的散列表的插入/**************begin************/int indexe%13; //计算散列地址LinkList pH[index]; //工作指针p指向链表的头结点while(p-next) //移至表尾pp-next;LinkList qnew LNode; //生成新结点*qq-datae; //将新结点*q的数据域置为eq-nextNULL; //将新结点*q插入在尾结点*p之后p-nextq;/**************end************/
}
void Input(int n)
{//输入数据for(int i0;i13;i) //建立13个带有头结点的单链表{H[i]new LNode;H[i]-nextNULL;}while(n--) //输入n个关键字,构造散列表{int e;cine;Hash(e);}
}
void Output()
{//输出数据for(int i0;i13;i){couti; //输出散列地址LinkList pH[i]-next; //p初始化为链表的首元结点while(p){cout p-data;pp-next;}coutendl;}
}
int main()
{int n;while(cinn){if(n0) break;Input(n); //输入数据int k; //需要插入的关键字kcink;Hash(k);Output(); //输出数据}return 0;
}
第7关基于链地址法的散列表的删除
任务描述
请写出在散列表中删除关键字为k的一个记录的算法设散列函数为HH(key)key%13解决冲突的方法为链地址法。
编程要求
输入
多组数据每组三行第一行为待输入的关键字的个数n第二行为对应的n个关键字第三行为需要删除的关键字k。当n0时输入结束。
输出
每组数据输出用链地址法处理冲突的散列表。
#includeiostream
using namespace std;
typedef struct LNode
{int data;struct LNode *next;
}LNode,*LinkList;
LinkList H[13]; //链地址法13个单链表
void Hash(int e)
{//基于链地址法的散列表的插入int indexe%13; //计算散列地址LinkList pH[index]; //工作指针p指向链表的头结点while(p-next) //移至表尾pp-next;LinkList qnew LNode; //生成新结点*qq-datae; //将新结点*q的数据域置为eq-nextNULL; //将新结点*q插入在尾结点*p之后p-nextq;
}
void Input(int n)
{//输入数据for(int i0;i13;i) //建立13个带有头结点的单链表{H[i]new LNode;H[i]-nextNULL;}while(n--) //输入n个关键字,构造散列表{int e;cine;Hash(e);}
}
void Delete(int e)
{//基于链地址法的散列表的删除/**************begin************/int indexe%13; //计算散列地址LinkList pH[index]; //工作指针p指向链表的头结点while(p-next) //p指向待删除结点的前一个结点找不到待删除结点时p最终指向表尾结点{if(p-next-datae)break;pp-next;}if(p-next!NULL) //p没指向表尾结点时{LinkList qp-next;p-nextq-next;delete q;}/**************end************/
}
void Output()
{//输出数据for(int i0;i13;i){couti; //输出散列地址LinkList pH[i]-next; //p初始化为链表的首元结点while(p){cout p-data;pp-next;}coutendl;}
}
int main()
{int n;while(cinn){if(n0) break;Input(n); //输入数据int k;cink;Delete(k); //需要删除的关键字kOutput(); //输出数据}return 0;
}
第8关基于快排思想的查找
任务描述
借助于快速排序的算法思想在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l..n]中。若查找成功则输出该记录在r数组中的位置及其值否则显示“not find”信息。
编程要求
输入
多组数据每组数据三行。第一行为序列的长度n第二行为序列的n个元素元素之间用空格分隔元素都为正整数第三行为要查找的key值。当n等于0时输入结束。
输出
每组数据输出一行。如果查找成功输出key在数组中的位置1到n和key的值两个数字之间用空格隔开。如果查找失败输出“not find”。
#includeiostream
using namespace std;
int Search(int r[],int low,int high,int key)
{//基于快排思想的查找/**************begin************/while(lowhigh){if(r[low]keyr[high]key) //如果关键字小于数组下界的值且大于数组上界的值更新指针high和low{high--;low;}while(lowhighr[high]key) high--; //从右侧开始找到第一个不大于关键字的记录其位置为highif(r[high]key) return high; //查找成功返回其位置while(lowhighr[low]key) low; //从左侧开始找到第一个不小于关键字的记录其位置为lowif(r[low]key) return low; //查找成功返回其位置}coutnot findendl; //查找失败return 0;/**************end************/
}
int main()
{int n;while(cinn){if(n0) break;int r[n],key;for(int i0;in;i) //输入数据cinr[i];cinkey; //输入要查找的key值if(Search(r,0,n-1,key)) //如果查找成功coutSearch(r,0,n-1,key)1 keyendl; //输出key在数组中的位置1到n和key的值}
}
第9关查找链表倒数第k个结点
任务描述
已知一个带有表头结点的单链表结点结构为datalink假设该链表只给出了头指针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)
{//后插法创建单链表Lnew LNode;L-nextNULL;LinkList rL;for(int i0;in;i){LinkList pnew LNode;cinp-data;p-nextNULL;r-nextp;rp;}
}
int Search_k(LinkList L,int a[],int k)
{//查找链表倒数第k个结点
//通过一趟遍历把该链表的结点都存入到一个辅助数组中再通过数组下标可直接获取倒数第k个结点但这样会需要额外的存储空间因此空间复杂度为O(n)/**************begin************/LinkList pL-next; //初始化指针p指向首元结点int length0; //length记录链表长度也是数组元素的个数while(p!NULL){a[length]p-data;pp-next;}if(klength) return ERROR;else couta[length-k]endl;return OK;/**************end************/
}
int main()
{int n;while(cinn){if(n0) break;LinkList L;CreateList_R(L,n);int k,a[MAXSIZE];cink;Search_k(L,a,k);}return 0;
}
