T->data=Pre[Pre_start]; /*取先序序列中的第一个字符作为根结点的数据域值*/ for(i=Mid_start;Mid[i]!=T->data;i++); /*在中序序列中查找根结点*/ ltreelen=i-Mid_start; /*计算左子树中结点个数*/ rtreelen=Mid_end-i; /*计算右子树中结点个数*/ if(ltreelen)
T->lchild=creat_sub(T,Pre_start+1,Pre_start+ltreelen,Mid_start,Mid_start+ltreelen-1) ; else
T->lchild=NULL;
if(rtreelen)
T->rchild=creat_sub(T,Pre_end-rtreelen+1,Pre_end,Mid_end-rtreelen+1,Mid_end); else
T->rchild=NULL;
return T; }
int precmp(Bitree T1,Bitree T2)
/*用先序遍历方法判断两棵二叉树是否相等*/ { if (!T1&&!T2) return 1; if (T1&&T2)
if (T1->data==T2->data)
if (precmp(T1->lchild,T2->lchild)) if(precmp(T1->rchild,T2->rchild))
return 1; return 0; }
int midcmp(Bitree T1,Bitree T2)
/*用中序遍历方法判断两棵二叉树是否相等*/ { if (!T1&&!T2) return 1; if (T1&&T2)
if (precmp(T1->lchild,T2->lchild)) if (T1->data==T2->data)
if(precmp(T1->rchild,T2->rchild)) return 1; return 0; }
int backcmp(Bitree T1,Bitree T2)
/*用后序遍历方法判断两棵二叉树是否相等*/ { if (!T1&&!T2) return 1; if (T1&&T2)
if (precmp(T1->lchild,T2->lchild))
if(precmp(T1->rchild,T2->rchild))
if (T1->data==T2->data) return 1;
return 0; }
36
2． 编程求从二叉树根结点到到指定结点p之间的路径。
⑴ 实验要求
① 假设二叉树的结点值是字符，请根据输入的二叉树后序遍历序列和中序遍历序列来建立二叉链表表示的二叉树,并对其进行某种遍历,输出遍历序列以验证建立的二叉树是否正确。
② 任意给定一结点p,输出从二叉树的根结点到该结点p的路径。 ⑵ 核心算法提示
要求出从根结点到指定结点p之间的路径，可利用后序遍历的非递归算法来实现。由于
后序遍历当访问到p所指结点时，栈中所有结点均为p所指结点的祖先，由这些祖先便构成了一条从根结点到p结点之间的路径。
37
实验B06: 静态表的查找操作实验
一、实验名称和性质
所属课程 实验名称 实验学时 实验性质 必做/选做 数据结构 静态表的查找操作 2 □验证 □综合 √设计 √必做 □选做 二、实验目的
1．掌握顺序查找操作的算法实现。
2．掌握二分查找操作的算法实现及实现该查找的前提。 3．掌握索引查找操作的算法实现。 三、实验内容
1．建立顺序查找表，并在此查找表上实现顺序查找操作（验证性内容）。 2．建立有序顺序查找表，并在此查找表上实现二分查找操作（验证性内容）。 3．建立索引查找表，并在此查找表上实现索引查找操作（设计性内容）。 四、实验的软硬件环境要求
硬件环境要求：
PC机（单机）
Windows环境下的TurboC2.0以上或VC++ 使用的软件名称、版本号以及模块： 五、知识准备
前期要求掌握查找的含义和顺序查找、二分查找及索引查找操作的方法。 六、验证性实验 1．实验要求
编程实现如下功能：
（1）根据输入的查找表的表长n和n个关键字值，建立顺序查找表，并在此查找表中用顺序查找方法查找给定关键值的记录，最后输出查找结果。
（2）根据输入的查找表的表长n和n个按升排列的关键字值，建立有序顺序查找表，并在此查找表中用二分查找方法查找给定关键值的记录，最后输出查找结果。
（3）主程序中要求设计一个菜单，允许用户通过菜单来多次选择执行哪一种查找操作。 2. 实验相关原理：
查找表分别静态查找表和动态查找表两种，其中只能做引用操作的查找表称为静态查找表。
静态查找表采用顺序存储结构的数据描述为：
#define MAXSIZE 100 /*顺序查找表的最大长度*/ typedef int keytype; typedef struct {keytype key;
38
}redtype; typedef struct
{redtype elem[MAXSIZE]; int length; }Sstable;
【核心算法提示】
查找操作是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素 或记录的过程。若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；若在查找表中不存在这样的记录，则称“查找不成功”。查找结果给出“空记录”或“空指针”。
（1）顺序查找操作的基本步骤：从表中最后一个记录开始，逆序扫描查找表，依次将扫描到的结点关键字值与给定值key进行比较，若当前扫描到的结点关键字值与key相等，则查找成功；若扫描到第一个记录，仍未找到关键字值等于key的记录，则查找失败。在程序设计中为了减少执行的循环次数使用了监视哨。监视哨可设置在表头，也可设置在表尾。在此设置在表头。
（2）二分查找也叫折半查找，这种查找要求查找表必须是有序顺序表。其查找操作的基本步骤：首先取出表中的中间元素，若其关键字值等于给定值key，则查找成功，操作结束；否则以中间元素为分界点，将查找表分成两个子表，并判断所查的key值所在的子表是前部分，还是后部分，再重复上述步骤直到找到关键字值为key的元素或子表长度为0。 【核心算法描述】
int sxsearch(Sstable ST, keytype key)
/*在顺序查找表ST中，用顺序查找的方法查找其关键字等于key的数据元素。若找到，则函数返回该元素在表中的位置，否则返回0 */
{ ST.elem[0].key=key; /*在表头设置监视哨*/
for(i=ST.length;ST.elem[i].key!=key;--i); /*从后往前顺序查找*/ return i; }
int binsearch(Sstable ST,keytype key)
/*在按关键字从小到大的有序顺序表ST中，用二分查找的方法查找其关键字等于key的数据元素。若找到，则函数返回该元素在表中的位置，否则返回0 */ { low=1;high=ST.length; /*置查找区间的初值*/ while(low<=high) { mid=(low+high)/2;
if (key==ST.elem[mid].key)
return mid;/*找到匹配记录*/ else if (key high=mid-1;/*继续对左半部分进行二分查找*/ else low=mid+1；/*继续对右半部分进行二分查找*/ } return 0; /*找不到匹配记录*/ } 39 3．源程序代码参考 #define MAXSIZE 100 typedef int keytype; typedef struct { keytype key; }redtype; typedef struct { redtype elem[MAXSIZE]; int length; }Sstable; int sxsearch(Sstable ST,keytype Key)/*顺序查找函数*/ { int i; ST.elem[0].key=Key; for(i=ST.length;ST.elem[i].key!=Key;--i); return i; } int binsearch(Sstable ST,keytype Key)/*二分法查找函数*/ { int low,mid,high; low=1;high=ST.length; while(low<=high) { mid=(low+high)/2; if (Key==ST.elem[mid].key) return mid; else if (Key main()/*主函数*/ {Sstable ST; int i,pos,x,key; pos=0; while(1) { printf(\ 1---Sxserach\\n\ printf(\ 2---Binserach\\n\ printf(\ 3---Exit\\n\ 40