上机实习题六查找 、实验目的 1.掌握查找的不同方法,并能用高级语言实现查找方法 2.熟练掌握顺序表和有序表的査找方法以及静态査找树的构造方法和査找算法,理解 静态查找树的折半查找方法。 3.熟练掌握二叉树的构造和査找方法。 实验内容 1.设计一个读入一串整数构成的二叉树的算法。 [实现提示]二叉排序树的构成,可以从空的二叉树开始,每输入一个接点数据,就建 立一个新结点、插入都当前已生成的二叉排序树中,所以,它的主要操作是二叉树的插 入运算。在儿叉排序数中插入新结点,只要保证插入后仍符合二叉树定义即可。插入是 这样进行的:若二叉树为空,则待插入结点*s作为根结点插入到空树;当二叉树非空 将待插结点的关键字s>key与树根的关键字t>key比较,若s>key=t->key,则说明树中 以有次结点,无需插入;若s->keykey,则将待插结点*s插入到根的左子树,否则将 *s插入到根的右子树。而子树的插入过程有和在树中的插入过程相同,如此进行下去, 直到把结点*s作为一个新的树叶插入到二插树中,或则直到发现树中已有*s结点为止 算法实现] typedef struct node { int key;∥关键字项 int other;∥其他数据项 void inorder(t)∥/中序遍历二叉树 bstnode *t: printf(t->key) inorder(t->rchild) bstnode insertbst(t,s)/将新结点*s插入到t所指的二叉树中 bstnode *s, *t while(pl=null) f=p; if(s->key==p->key )return t
上机实习题六 查找 一、实验目的 1． 掌握查找的不同方法，并能用高级语言实现查找方法。 2． 熟练掌握顺序表和有序表的查找方法以及静态查找树的构造方法和查找算法，理解 静态查找树的折半查找方法。 3． 熟练掌握二叉树的构造和查找方法。 而 二、实验内容 1． 设计一个读入一串整数构成的二叉树的算法。 [实现提示] 二叉排序树的构成，可以从空的二叉树开始，每输入一个接点数据，就建 立一个新结点、插入都当前已生成的二叉排序树中，所以，它的主要操作是二叉树的插 入运算。在儿叉排序数中插入新结点，只要保证插入后仍符合二叉树定义即可。插入是 这样进行的：若二叉树为空，则待插入结点*s 作为根结点插入到空树；当二叉树非空， 将待插结点的关键字 s->key 与树根的关键字 t->key 比较，若 s->key=t->key,则说明树中 以有次结点，无需插入；若 s->keykey, 则将待插结点*s 插入到根的左子树，否则将 *s 插入到根的右子树。而子树的插入过程有和在树中的插入过程相同，如此进行下去， 直到把结点*s 作为一个新的树叶插入到二插树中，或则直到发现树中已有*s 结点为止. [算法实现] typedef struct node {int key;//关键字项 int other;//其他数据项 struct node *lchild, *rchild; }bstnode; void inorder (t)//中序遍历二叉树 bstnode *t; { if(t!=null) {inorder(t->lchild); printf(t->key); inorder(t->rchild); } } bstnode insertbst(t,s)//将新结点*s 插入到 t 所指的二叉树中 bstnode *s, *t; { bstnode *f ,*p; p=t; while(p!=null) { f=p; if(s->key==p->key)return t;
f(s->keykey)p=p->lchild p-p->rchild return s f(s->keykey )f->lchild=s f->rchild=s return t bstnode* creator/返回二叉树 bstnode°t,*s, t=null while(key!=0) s=malloc( sizeof(bitree)) S->lchild=null S->rchild=null scanf( &key return t, maino root=creatordo
if(s->keykey)p=p->lchild; else p=p->rchild; } if(t==null) return s; if(s->keykey)f->lchild=s; else f->rchild=s; return t; } bstnode *creatord()//返回二叉树 { bstnode *t , *s; int key; t=null; scanf(&key); while(key!=0) { s=malloc(sizeof(bitree)); s->key=key; s->lchild=null; s->rchild=null; scanf(&data); s->other=data; t=insertbst(t,s); scanf(&key); } return t; } main() { bstnode *root; root=creatord(); inorder(root); }
2.试写出从二叉树中删除一个接点,使该二叉树仍未为叉树的算法。 实现提示]本题要注意的事,删除二叉树中的结点与删除一棵树中的结点不同,二叉树 的结点对应的是一条纪录,只要在删除它后仍使它为二叉排序即可:而要将一棵树中的 结点删除,是将该结点同他的左右子树一并删除 要将二叉树的结点删除,必须建立一棵二叉树,以二叉排序方式表示,然后 再进行二叉树结点删除,依据删除结点位置又可分为根和非跟结点两种,可将算法描述 为 (1)若被删除结点k为二叉树的根结点,则 a:若k有左子树l而无右子树,则将仅需I作为根结点即可 b:若k有右子树r而无左子树,则将仅需r作为根结点即可 c:若k有左子树I而又有右子树r,则将1作为根结点此时若l无右子树 需将的1右孩子指针指向r;若有右子树则需沿着1右分支一直往下检索 直到找到最右的且没有右子树的结点为止,即最右下的一个结点,然后把 该结点的右孩子指针指向r (2)若被删除的结点不是二叉树的根结点,此时可设*p为k的双亲结点,k是 *p的左子树活右子树,处理: a:若k有左子树1,而无右子树,则应将肀结点的左指针或右指针改指向 若k无左子树1,而有右子树,则应将◆p结点的左指针或右指针改指向 c:若k有左子树l,又有右子树,则应将◆p结点的左指针或右指针改指向 l,此时若1无右子树,需将的1右孩子指针指向r:若1有右子树则需沿着 l右分支一直往下检索,直到找到最右的且没有右子树的结点为止,即最右 下的一个结点,然后把该结点的右孩子指针指向r 设t为二叉排序树的根指针,而叉排序数一二叉链表储存,k为待删除结点 的关键字,则可的程序如下: 算法实现]首先建立一个二叉树,一二叉链表方式表示 typedef struct node ∥关键字项 struct node lchild. *rchild void inorder(t)∥/中序遍历二叉树 bitree *t norder(t->lchild)
2.试写出从二叉树中删除一个接点，使该二叉树仍未为叉树的算法。 [实现提示]本题要注意的事，删除二叉树中的结点与删除一棵树中的结点不同，二叉树 的结点对应的是一条纪录，只要在删除它后仍使它为二叉排序即可；而要将一棵树中的 结点删除，是将该结点同他的左右子树一并删除。 要将二叉树的结点删除，必须建立一棵二叉树，以二叉排序方式表示，然后 再进行二叉树结点删除，依据删除结点位置又可分为根和非跟结点两种，可将算法描述 为： （1） 若被删除结点 k 为二叉树的根结点，则: a:若 k 有左子树 l 而无右子树，则将仅需 l 作为根结点即可 b: 若 k 有右子树 r 而无左子树，则将仅需 r 作为根结点即可 c: 若 k 有左子树 l 而又有右子树 r ，则将 l 作为根结点,此时若 l 无右子树， 需将的 l 右孩子指针指向 r；若 l 有右子树则需沿着 l 右分支一直往下检索， 直到找到最右的且没有右子树的结点为止，即最右下的一个结点，然后把 该结点的右孩子指针指向 r。 （2） 若被删除的结点不是二叉树的根结点，此时可设*p 为 k 的双亲结点，k 是 *p 的左子树活右子树，处理： a：若 k 有左子树 l，而无右子树，则应将*p 结点的左指针或右指针改指向 l; b; 若 k 无左子树 l，而有右子树，则应将*p 结点的左指针或右指针改指向 r c: 若 k 有左子树 l，又有右子树，则应将*p 结点的左指针或右指针改指向 l，此时若 l 无右子树，需将的 l 右孩子指针指向 r；若 l 有右子树则需沿着 l 右分支一直往下检索，直到找到最右的且没有右子树的结点为止，即最右 下的一个结点，然后把该结点的右孩子指针指向 r。 设 t 为二叉排序树的根指针，而叉排序数一二叉链表储存，k 为待删除结点 的关键字，则可的程序如下： [算法实现]首先建立一个二叉树，一二叉链表方式表示 typedef struct node { int key; //关键字项 struct node * lchild, *rchild; }bitree; void inorder(t)//中序遍历二叉树 bitree *t; { if(t!=null) { inorder(t->lchild);
printf(t->key ); inorder(t->rchild) bitree *inserbst(ts)∥/将新结点*s插入到t所指的二叉树中 bitree* creator∥返回二叉树 再给出检索算法描述如下: 将pq作为全程量看待,则有 betsch(tk)/在一个儿叉树t中间所关键字为k的结点 bitree t;/t为二叉树的根指针,而叉树以二叉链表存储 k int flag: null/pq为全程量 flag=false while((ql=null)&&(flag=false) if(k==q->key )flag=true if(kkey) q=q->lchild qq->rchild 然后给出删除算法如下: bintree*p, *q bintreedele(t, k∥从二叉树中删除一个结点 betsch(tk);/检索过程,、设待删除结点在树中 if(ql=null∥/删除结点在树中
printf(t->key); inorder(t->rchild); } } bitree *inserbst(t,s)// 将新结点*s 插入到 t 所指的二叉树中 {} bitree *creatord()//返回二叉树 {} 再给出检索算法描述如下： 将 p,q 作为全程量看待，则有 bstsrch(t,k)//在一个儿叉树 t 中间所关键字为 k 的结点 bitree t;//*t 为二叉树的根指针，而叉树以二叉链表存储 int k; { int flag; p=null;//p,q 为全程量 q=t; flag=false; while((q!=null)&&(flag==false)) if(k==q->key)flag=true; else { p=q; if(kkey) q=q->lchild; else q=q->rchild; } } 然后给出删除算法如下： bittree *p, *q; bintreedele(t,k)//从二叉树中删除一个结点 bitree *t; int k; { bitree *r; bstsrch(t,k);//检索过程，、设待删除结点在树中 if(q!=null)// 删除结点在树中
iflp=null∥删除结点是根结点 ifq->lhld==null∥/删除结点无左子树 t=q->lchild else若被删除得结点无右子树 if(q->rchild==null while(r->lchild=null) r=r->rchd/检索中序前驱 r->rchild=q->rchild =q->lchild; else∥被删除结点不是根结点 ifq->lhid==null∥/若被删除得结点无左子树 p->lchild=q->rchild r=r->rchild whle(r->rchd!=nul!∥查找中序前驱 rr->rchild [->rchild=q->rchild p->lchild=q->lchild p->rchild=q->lchild maino i bitree "root, "p,*q bintreedele(root, k) 3.试设计菲薄那检索算法。 [实现提示]菲薄那检索是利用数列 fibonacci进行的一种检索的方法 首先给出数列如下 fl=1
if(p==null)// 删除结点是根结点 if(q->lchild==null)// 删除结点无左子树 t=q->lchild; else//若被删除得结点无右子树 if(q->rchild==null) t=q->lchild; while(r->lchild!=null) r=r->rchild;//检索中序前驱 r->rchild=q->rchild; t=q->lchild; } else//被删除结点不是根结点 if(q->lchild==null)// 若被删除得结点无左子树 if(q==p->lchild) p->lchild=q->rchild; else { r=r->rchild; while(r->rchild!=null)//查找中序前驱 r=r->rchild; r->rchild=q->rchild; if(q==p->lchild) p->lchild=q->lchild; else p->rchild=q->lchild; } free(q); } main() {bitree *root, *p , *q; int k; root=creatord(); inorder(root); scanf(&k); bintreedele(root,k); inorder(root); } 3.试设计菲薄那检索算法。 [实现提示]菲薄那检索是利用数列 fibonacci 进行的一种检索的方法 首先给出数列如下： f0=0 n=0 f1=1 n=1
fnfn-I+fn-2 从而可得菲薄那序列为:0,1,2,3,5,8,13,21,…假设利用一个数组r来存放 菲薄那数列,且r数组中的元素安关键字从大到小的顺序排列,并且假定元素个数n比某个 fibonacci数fm小1,即n=fm-1,第一次,用要检索的关键字key与r[fm-l]key进行比较, 其算法思想为: (1)若key=rfm-1]key,则检索成功,r[fm-1]为key所在纪录 (2)若keyr[fm-1]key,则下一次检索在从下标从m-1+1到fm-1的范围进行 此时该序列的长度为fm-1)-fm-1+1)+1=m-fm-1-1=fm2-1,从而可得 设r为顺序存储线性表,则 rI1].key =0fm+1>l1,n为记录元素个 数)。 算法实现]首先可定义一个递归函数,求 fibonacci数列的函数 if(n==O)return(O) else if(n==l)return(1) return (fibonacci(n-1)+fibonacci(n-2): 1 然后再给出数列检索的算法: #define keytype int; #define datatype int type struct g rectype
. . fn=fn-1+fn-2 n>=2; 从而可得菲薄那序列为：0，1，2，3，5，8，13，21，…..假设利用一个数组 r 来存放 菲薄那数列，且 r 数组中的元素安关键字从大到小的顺序排列，并且假定元素个数 n 比某个 fibonacci 数 fm 小 1，即 n=fm- 1,第一次，用要检索的关键字 key 与 r[fm-1].key 进行比较， 其算法思想为： (1) 若 key=r[fm-1].key，则检索成功，r[fm-1]为 key 所在纪录 (2)若 keyr[fm-1].key，则下一次检索在从下标从 fm-1 +1 到 fm -1 的范围进行， 此时该序列的长度为(fm –1)-(fm-1 +1)+1=fm-fm-1 –1=fm-2 -1，从而可得 到： 设 r 为顺序存储线性表，则： r[1].key=0,fm+1>I+1,n 为记录元素个 数)。 [算法实现] 首先可定义一个递归函数，求 fibonacci 数列的函数 int fibonacci(n) int n; { if(n==0)return(0); else if(n==1)return(1); else return (fibonacci(n-1)+fibonacci(n-2));} 然后再给出数列检索的算法： #define keytype int; #define datatype int; type struct { keytype key; datatype other; }rectype;
fibonacci(r, k, n) rectype rl keytype k int I I= fibonacci(m-1),∥设m为 fibonacci数列序号 P-fibonacci(m-2) S=n+1-(l+p) While((i))&&(!flag)) Switch { case k=rl].key: flag=ture break/检索成功 case k<r[key:ifq==0)I=0∥检索失败 1=l-q; P-q q=t-q break. case kr[ ke iflp=1)l=0,∥检索失败 P=p-q q-q-p, break default: i ruturn(i);
fibonacci(r,k,n) { rectype r[]; keytype k; int n; { int I,p,q,t,m,flag; I=fibonacci(m-1);//设 m 为 fibonacci 数列序号 P=fibonacci(m-2)； Q=fibonacci(m-3); S=n+1-(I+p); If(k>r[I].key I=I+s; Flag=false; While((i))&&(!flag)) Switch { case k==r[I].key: flag=ture; break;//检索成功 case kr[I].key: if(p==1)I=0; //检索失败 else { I=I+q; P=p-q; q=q-p; } break; default:} ruturn(i); }
