《数据结构》实验指导书（C语言版）

更新时间：2024-02-03 15:33:01 阅读量：教育文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

c语言实验指导书答案推荐度：
相关推荐

《数据结构》课程实验指导

《数据结构》实验教学大纲

课程代码：0806523006 开课学期：3 开课专业：信息管理与信息系统总学时/实验学时：64/16 总学分/实验学分：3.5/0.5

一、课程简介

数据结构是计算机各专业的重要技术基础课。在计算机科学中，数据结构不仅是一般程序设计的基础，而且是编译原理、操作系统、数据库系统及其它系统程序和大型应用程序开发的重要基础。数据结构课程主要讨论各种主要数据结构的特点、计算机内的表示方法、处理数据的算法以及对算法性能的分析。通过对本课程的系统学习使学生掌握各种数据结构的特点、存储表示、运算的原理和方法，学会从问题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。另一方面，本课程的学习过程也是进行复杂程序设计的训练过程，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。

二、实验的地位、作用和目的

数据结构是一门实践性较强的基础课程，本课程实验主要是着眼于原理和应用的结合，通过实验，一方面能使学生学会把书上学到的知识用于解决实际问题，加强培养学生如何根据计算机所处理对象的特点来组织数据存储和编写性能好的操作算法的能力，为以后相关课程的学习和大型软件的开发打下扎实的基础。另一方面使书上的知识变活，起到深化理解和灵活掌握教学内容的目的。

三、实验方式与基本要求

实验方式是上机编写完成实验项目指定功能的程序，并调试、运行，最终得出正确结果。具体实验要求如下：

1. 问题分析

充分地分析和理解问题本身，弄清要求，包括功能要求、性能要求、设计要求和约束，以及基本数据特性、数据间联系等等。

2. 数据结构设计

针对要解决的问题，考虑各种可能的数据结构，并且力求从中选出最佳方案（必须连同算法实现一起考虑），确定主要的数据结构和全程变量。对引入的每种数据结构和全程变量要详细说明其功用、初值和操作的特点。

3. 算法设计

算法设计分概要和详细设计。概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干程序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题。详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出。

4. 测试用例设计

准备典型测试数据和测试方案。测试数据要有代表性、敏感性。测试方案包括模块测试

和模块集成测试。

5. 上机调试

对程序进行编译，纠正程序中可能出现的语法错误。调试前，先运行一遍程序看看究竟将会发生什么。如果情况很糟，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。

6. 程序性能分析

在运行结果正确的前提下再分析程序中主要算法是否具有较好的时间复杂度和空间复杂度。如果没有，则通过改变数据结构或操作方法使编写的程序性能达到最佳。

7. 实验总结

每个实验完成后要认真书写实验报告，对程序运行的结构，要认真分析，总结每次实验项目的体会与收获。

四、报告与考核

每个实验都要求学生根据上机内容写出实验报告，报告要求包括以下七个方面的内容： 1．实验目的； 2．实验内容； 3．实验要求； 4．算法设计； 5．详细程序清单； 6．程序运行结果；

7．实验心得体会。考核方式：

每个实验项目根据以下两个方面进行考核：

1．指导教师随堂抽查学生的实验过程（包括实验预习、实验出勤、实验结果的测试），并根据抽查结果评定学生成绩，此成绩占此实验总成绩的70%；

2．学生编写课程设计实验报告，每位学生按照实验报告的内容和要求编写详细的实验报告并打印上交给指导老师，由指导老师根据每位学生的完成情况评定成绩，此成绩占实验总成绩的30%。

五、设备及器材材料配置

硬件：奔腾以上PC机软件：TURBO C、C++或Java

六、实验指导书及主要参考书

[1]朱蓉.数据结构实验指导书

[2]张铭.数据结构与算法. 高教出版社.2008.6

[3]张铭.数据结构与算法－－学习指导与习题解析. 高教出版社.2009 [4]耿国华等数据结构-C语言描述. 高教出版社.2005.7 [5]刘怀亮. 数据结构(C语言描述) .冶金出版社.2005.2

[6]刘怀亮. 数据结构(C语言描述)习题与实验指导导.冶金出版社.2005.2 [7]蔡子经，施伯乐.数据结构教程.上海:复旦大学出版社.1994 [8]严蔚敏,吴伟民.数据结构(C语言版).北京：清华大学出版社.1999；

[9]严蔚敏,吴伟民.数据结构题集(C语言版).北京：清华大学出版社.1999； [10]徐孝凯.数据结构课程实验.北京：清华大学出版社.2002；

[11]孟佳娜,胡潇琨.算法与数据结构实验与习题.北京：机械工业出版社.2004.

七、实验项目与内容提要序号 1 实验名称顺序表的基本操作 2 3 链表的基本操作栈的基本操作目的要求、内容提要（限20字）熟悉并完成顺序表上基本操作的算法及其应用问题的编程实现。熟悉并完成单链表和双向链表基本操作算法的编程实现。熟悉并完成顺序栈和链栈基本操作算法及其应用问题的编程实现 4 队列的基本操作 5 6 二叉树的操作静态查找表的查找操作 7 二叉排序树的查找操作 8 9 10 哈希表上的查找操作排序操作图的遍历熟悉并完成循环顺序队列和循环链队列基本操作算法及其应用问题的编程实现。熟悉并完成二叉树遍历算法及其应用问题的编程实现。。熟悉并完成静态查找表上的顺序查找、二分查找和索引查找算法的编程实现熟悉并完成在二叉排序树上进行查找、插入和删除操作的编程实现。熟悉并完成哈希表的建立、查找和插入操作的编程实现熟悉并完成几种主要排序操作的编程实现。熟悉并完成图的遍历、最小生成树及其应用问题的编程实现 1个班 1个班 1个班 2 设计选做 2 设计必做 2 设计选做 1个班 2 设计选做 1个班 1个班 2 设计必做 2 设计必做 1个班 2 设计必做 1个班 1个班 2 设计必做 2 设计必做每组人数 1个班实验学时 2 实验类型设计必做选做必做所在实验分室

实验B01: 顺序表的操作实验

一、实验名称和性质

所属课程实验名称实验学时实验性质必做/选做数据结构顺序表的操作 2 □验证 □综合 √设计 √必做 □选做二、实验目的

1．掌握线性表的顺序存储结构的表示和实现方法。 2．掌握顺序表基本操作的算法实现。 3．了解顺序表的应用。三、实验内容 1．建立顺序表。

2．在顺序表上实现插入、删除和查找操作（验证性内容）。 3．删除有序顺序表中的重复元素（设计性内容）。

4．完成一个简单学生成绩管理系统的设计（应用性设计内容）。四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

Windows环境下的TurboC2.0以上或VC++等。使用的软件名称、版本号以及模块：五、知识准备

前期要求熟练掌握了C语言的编程规则、方法和顺序表的基本操作算法。六、验证性实验 1．实验要求

编程实现如下功能：

（1）根据输入顺序表的长度n和各个数据元素值建立一个顺序表，并输出顺序表中各元素值，观察输入的内容与输出的内容是否一致。

（2）在顺序表的第i个元素之前插入一个值为x的元素，并输出插入后的顺序表中各元素值。

（3）删除顺序表中第i个元素，并输出删除后的顺序表中各元素值。

（4）在顺序表中查找第i个元素，如果查找成功，则显示“查找成功”和该元素在顺序表中的位置，否则显示“查找失败”。 2. 实验相关原理：

线性表的顺序存储结构称为顺序表，顺序表的存储结构描述为：

#define MAXLEN 30 /*线性表的最大长度*/ typedef struct

{ Elemtype elem[MAXLEN]; /*顺序表中存放元素的数组，其中elemtype为抽象数据类型，在程序具体实现时可以用任意类型代替*/

int length; /*顺序表的长度，即元素个数*/

}Sqlist; /*顺序表的类型*/

【核心算法提示】

1．顺序表插入操作的基本步骤：要在顺序表中的第i个数据元素之前插入一个数据元素x,首先要判断插入位置i是否合法，假设线性表的表长为n，则i的合法值范围：1≤i≤n+1，若是合法位置，就再判断顺序表是否满，如果满，则增加空间或结束操作，如果不满，则将第i个数据元素及其之后的所有数据元素都后移一个位置，此时第i个位置已经腾空，再将待插入的数据元素x插入到该位置上，最后将线性表的表长增加1。

2．顺序表删除操作的基本步骤：要删除顺序表中的第i个数据元素，首先仍然要判断i的合法性，i 的合法范围是1≤i≤n，若是合法位置，则将第i个数据元素之后的所有数据元素都前移一个位置，最后将线性表的表长减1。

3．顺序表查找操作的基本步骤：要在顺序表中查找一个给定值的数据元素，则可以采用顺序查找的方法，从顺序表中第1个数据元素开始依次将数据元素值与给定值进行比较，若相等则返回该数据元素在顺序表中的位置，否则返回0值。【核心算法描述】

status Sqlist_insert(Sqlist &L,int i,Elemtype x)

/*在顺序表L中第i个元素前插入新元素x*/

{ if (i<1||i>L.length+1) return ERROR; /*插入位置不正确则出错*/ if (L.length>=MAXLEN) return OVERFLOW;

/*顺序表L中已放满元素，再做插入操作则溢出*/

for(j=L.length-1;j>=i-1;j--)

L.elem[j+1]=L.elem[j];/*将第i个元素及后续元素位置向后移一位*/ L.elem[i-1]=x; /*在第i个元素位置处插入新元素x*/ L.length++; /*顺序表L的长度加1*/ return OK; }

status Sqlist_delete(Sqlist &L,int i,Elemtype &e)

/*在顺序表L中删除第i个元素*/

{ if (i<1||i>L.length) return ERROR; /*删除位置不正确则出错*/ for(j=i;j<=L.length-1;j++)

L.elem[j-1]=L.elem[j]; /*将第i+1个元素及后继元素位置向前移一位*/ L.length--; /*顺序表L的长度减1*/ return OK；

}

int Sqlist_search(Sqlist L,Elemtype x)

/* 在顺序表中查找值为x的元素，如果找到，则函数返回该元素在顺序表中的位置，否则返回0*/

{ for (i=0;i

/*从第一个元素开始依次将每个元素值与给定值x比较*/

if (i

3．源程序代码参考 #define MAXLEN 50

typedef struct{int elem[MAXLEN]; int length;}Sqlist;

Sqlist Sqlist_insert(Sqlist L,int i,int x) /*顺序表插入函数*/ {int j;

if(i<1||i>L.length+1) printf(\ else if(L.length>=MAXLEN) printf(\

else { for(j=L.length-1;j>=i-1;j--)

L.elem[j+1]=L.elem[j];

L.elem[i-1]=x; L.length++;

} return L; }

Sqlist Sqlist_delete(Sqlist L,int i) /*顺序表删除函数*/ {int j;

if(i<1||i>L.length) printf(\ else { for(j=i;j<=L.length-1;j++) L.elem[j-1]=L.elem[j];

L.length--;

} return L; }

int Sqlist_search(Sqlist L,int x)/* 顺序表查找函数*/ { int i;

for (i=0;i

else

return 0; }

void Sqlist_display(Sqlist L) /*顺序表元素输出函数*/ { int j;

for(j=0;j<=L.length-1;j++) printf(\ printf(\}

main() /*主函数 */ { Sqlist L; int i,x,j;

printf(\请求输入顺序表中元素个数*/ scanf(\

printf(\请求输入顺序表中各个元素*/ for(j=0;j<=L.length-1;j++)

scanf(\

printf(\请求输入插入操作位置*/ scanf(\

printf(\请求输入需要插入的新元素*/ scanf(\

L=Sqlist_insert(L,i,x);/*调用顺序表插入函数*/ Sqlist_display(L);/*调用顺序表元素输出函数*/

printf(\请求输入删除操作位置*/ scanf(\

L=Sqlist_delete(L,i);/*调用顺序表删除函数*/ Sqlist_display(L);/*调用顺序表元素输出函数*/ printf(\ scanf(\

if (Sqlist_search(L,x)) /*如果查找成功，则显示查找成功和找到的元素位置，否则显示查

找不成功*/

printf(\ else

printf(\ }

4．运行结果参考如图1-1所示：

图1-1: 验证性实验运行结果

七、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成) 1．编程实现删除有序顺序表中的所有重复元素，即使有序顺序表中相同的元素只保留一个。 ⑴ 实验要求

① 根据输入的n个非递减的有序数据建立一个有序顺序表，并输出有序顺序表中各元素值。

② 删除有序顺序表中所有的重复元素，并显示删除后的有序顺序表中各元素值。 ⑵ 核心算法提示

要在有序顺序表中删除重复的元素，首先就要抓住有序顺序表的特性：重复的元素总是在相邻的位置上，如：12，15，15，15，35，56，56，78。则删除重复元素后所得的有序表为：12，15，35，56，78。下面给出大致的操作步骤：从第1 个元素开始，依次将它与后面相邻的元素进行比较，如果相等则将前面那个相等的元素从顺序表中删除；如果不相等，则继续往下比较，如此重复，直到最后一个元素为止。

⑶ 核心算法描述 Sqlist delSqlist(Sqlist L)

{int i=0,j;

while(i

if (L.elem[i]==L.elem[i+1]) /*如果第i个及第i+1个相邻元素值相等*/

{ for (j=i+1;j

除第i个元素的目的*/

L.elem[j-1]=L.elem[j];

L.length--; /*有序顺序表的表长减1*/ } else i++; return L; }

2．编程实现一个简单学生成绩表的操作。

实验要求

此系统的功能包括：

① 查询：按特定的条件查找学生

② 修改：按学号对某个学生的某门课程成绩进行修改 ③ 插入：增加新学生的信息

④ 删除：按学号删除已退学的学生的信息。学生成绩表的数据如下：

学号 2008001 2008002 2008003 2008004 2008006 2008006 姓名 Alan Danie Helen Bill Peter Amy 性别 F M M F M F 大学英语高等数学 93 75 56 87 79 68 88 69 77 90 86 75 要求采用顺序存储结构来实现对上述成绩表的相关操作。

实验B02: 链表的操作实验

一、实验名称和性质

所属课程实验名称实验学时实验性质必做/选做数据结构链表的操作 2 □验证 □综合 √设计 √必做 □选做二、实验目的

1．掌握线性表的链式存储结构的表示和实现方法。 2．掌握链表基本操作的算法实现。三、实验内容

1．建立单链表，并在单链表上实现插入、删除和查找操作（验证性内容）。 2．建立双向链表，并在双向链表上实现插入、删除和查找操作（设计性内容）。 3．计算已知一个单链表中数据域值为一个指定值x的结点个数（应用性设计内容）。四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

Windows环境下的TurboC2.0以上或VC++ 等。使用的软件名称、版本号以及模块：五、知识准备

前期要求熟练掌握了C语言的编程规则、方法和单链表和双向链表的基本操作算法。六、验证性实验 1．实验要求

编程实现如下功能：

（1）根据输入的一系列整数，以0标志结束，用头插法建立单链表，并输出单链表中各元素值，观察输入的内容与输出的内容是否一致。

（2）在单链表的第i个元素之前插入一个值为x的元素，并输出插入后的单链表中各元素值。

（3）删除单链表中第i个元素，并输出删除后的单链表中各元素值。

（4）在单链表中查找第i个元素，如果查找成功，则显示该元素的值，否则显示该元素不存在。 2. 实验相关原理：

线性表的链式储结构是用一组任意的存储单元依次存放线性表中的元素，这组存储单元可以是连续的，也可以是不连续的。为反映出各元素在线性表中的前后逻辑关系，对每个数据元素来说，除了存储其本身数据值之外，还需增加一个或多个指针域，每个指针域的值称为指针，又称作链，它用来指示它在线性表中的前驱或后继的存储地址。这两个部分的的一起组成一个数据元素的存储映像，称为结点，若干个结点链接成链表。如果一个结点中只含

一个指针的链表，则称单链表。单链表的存储结构描述如下：

typedef struct Lnode {

Elemtype data;/*数据域*/ struct Lnode *next;/*指针域*/

}LNODE,*Linklist; /*其中LNODE为结点类型名，Linklist为指向结点的指针类型名*/

【核心算法提示】

1．链表建立操作的基本步骤：链表是一个动态的结构，它不需要予分配空间，因此建立链表的过程是一个结点“逐个插入” 的过程。先建立一个只含头结点的空单链表，然后依次生成新结点，再不断地将其插入到链表的头部或尾部，分别称其为“头插法”和“尾插法”。

2．链表查找操作的基本步骤：因链表是一种\顺序存取\的结构，则要在带头结点的链表中查找到第 i个元素，必须从头结点开始沿着后继指针依次\点数\，直到点到第 i 个结点为止,如果查找成功，则用e返回第i个元素值。头结点可看成是第0个结点。

3．链表插入操作的基本步骤：先确定要插入的位置，如果插入位置合法，则再生成新的结点，最后通过修改链将新结点插入到指定的位置上。

4．链表删除操作的基本步骤：先确定要删除的结点位置，如果位置合法，则再通过修改链使被删结点从链表中“卸下”，最后释放被删结点的空间。【核心算法描述】

void creat1(Linklist &L) /*输入一系列整数，以0标志结束，将这些整数作为data域并用头

插法建立一个带头结点的单链表的函数*/

{ L=(Linklist)malloc(sizeof(LNODE));/*生成头结点*/ L->next=NULL;/*头结点的指针域初始为空*/ scanf(\

while(node!=0)

{ p=(Linklist)malloc(sizeof(LNODE));/*为一个新结点的分配空间*/ p->data=node; /*为新结点数据域赋值*/ p->next=L->next;/*新结点指针域指向开始结点*/

L->next=p; /*头结点指针域指向新结点，即新结点成为开始结点*/

scanf(\} }

void creat2(Linklist &L) /*输入一系列整数，以0标志结束，将这些整数作为data域并用尾插

法建立一个带头结点的单链表的函数*/

{ L=(Linklist)malloc(sizeof(LNODE));/*为头结点分配空间*/ L->next=NULL; /*头结点的指针域初始为空*/ r=L; /*尾指针初始指向头结点*/

scanf(\while(node!=0)

{ p=(Linklist)malloc(sizeof(LNODE));/*为一个新结点分配空间*/ p->data=node; /*新结点数据域赋值*/ p->next=NULL; /*新结点指针域为空*/ r->next=p;/*尾结点指针域指向新结点*/

r=p; /*尾指针指向新结点，即新结点成为尾结点*/

scanf(\ } }

status list_search(Linklist L, int i;Elemtype &e)

/*在带头结点的单链表L中查找第i个元素，如果查找成功则用e返回其值*/

{ p=L->next; /*使指针p指向第1个元素结点*/

j=1; /*计数器赋初值为1*/

while (p&& jnext; j++; }

if (!p&& j>i)

return ERROR; /*如果i值不合法，即i值小于1或大于表长，则出错*/ e=p->data; /*如果第i个元素存在，则将该元素值赋给e*/ return OK;

}

status list_insert(Linklist &L,int i;Elemtype x)

/*在带头结点的单链表L中第i个位置之前插入新元素x*/

{ p=L; j=0;

while(p!=NULL&&j

个位置*/

{ p=p->next;

++j;

}

if(p==NULL||j>i-1)

return ERROR; /*若位置不正确,即i小于1或大于表的长度加1，则出错*/ s=(Linklist)malloc(sizeof(LNODE)); /*分配一个新结点的空间*/ s->data=x; /*为新结点数据域赋值*/

/*下面两条语句就是完成修改链，将新结点s插入到p结点之后*/

s->next=p->next; /*新结点指针域指向p的后继结点*/

p->next=s; /*新结点成为p的后继结点*/ return OK;

}

status list_delete(Linklist &L,int i,Elemtype &x)

/*在带头结点的单链表L中，删除第i个元素结点,并用x返回其值*/

{ p=L;j=0;

while(p->next!=NULL&&jnext;

++j; }

if (p->next==NULL||j>i-1)

return ERROR; /*若位置不正确，即i小于1或大于表长，则出错*/ q=p->next; /* q指向p的后继结点*/

p->next=q->next; /*q的后继结点成为p的后继结点*/ x=q->data; /*用x返回第i个位置的元素*/

free(q); /*释放q所指的被删结点的空间*/ return OK; }

3．源程序代码参考

#include #include typedef struct Lnode { int data;

struct Lnode *next; } LNODE,*Linklist;

Linklist creat(Linklist L) /*单链表建立函数 */ {int node; Linklist p;

L=(Linklist)malloc(sizeof(LNODE)); L->next=NULL;

printf(\ \ /*请求输入线性表中各个元素，以0结束*/ scanf(\ while(node!=0)

{p=(Linklist)malloc(sizeof(LNODE)); if (!p) exit(); p->data=node; p->next=L->next; L->next=p; scanf(\ } return L; }

Linklist insert(Linklist L,int i,int x) /*单链表插入函数*/ { int j;Linklist p,s; p=L; j=0;

while (p!=NULL&&jnext; ++j; }

if (p==NULL||j>i-1)

printf(\ else

{ s=(Linklist)malloc(sizeof(LNODE)); s->data=x; s->next=p->next; p->next=s; } return L; }

Linklist delete(Linklist L,int i) /*单链表删除函数*/ { int j,x; Linklist p,q; p=L; j=0;

while(p->next!=NULL&&jnext; ++j; }

if(p->next==NULL||j>i-1) printf(\ else

{ q=p->next; p->next=q->next; x=q->data;

printf(\ free(q); } return L; }

int search(Linklist L, int i) /*单链上的查找函数*/ { Linklist p; int j; p=L->next; j=1;

while (p&& jnext; j++; }

if (!p&& j>i)

return 0; /*如果i值不合法，即i值小于1或大于表长，则函数返回0值*/ else

return(p->data); /*否则函数返回第i个元素的值*/ }

void display(Linklist L) /*单链表元素输出函数*/ { Linklist p; p=L->next; while(p!=NULL) { printf(\ p=p->next; } printf(\}

main()/*主函数*/

{Linklist L=NULL; int i,x;

L=creat(L);/*调用单链表建立函数*/ printf(\

display(L); /*调用单链表元素输出(遍历)函数*/

printf(\ you want to insert:\请求输入插入操作位置*/ scanf(\

printf(\请求输入需要插入的元素*/ scanf(\

L=insert(L,i,x);/*调用单链表插入函数*/ printf(\ display(L);/*调用单链表元素输出(遍历)函数*/

printf(\请求输入删除操作位置*/ scanf(\

L=delete(L,i); /*调用单链表删除函数*/ printf(\

display(L); /*调用单链表元素输出(遍历)函数*/

printf(\请求输入待查找元素的位置*/ scanf(\

x=search(L,i); /*调用单链表查找函数*/

if (x) /*如果查找成功，则显示第i个元素的值，否则显示第i个元素不存在*/ printf(\ the %dth elem is %d\\n\ else

printf(\ the %dth elem is not exsit\\n\}

4．运行结果参考如图2-1所示：

图2-1: 验证性实验运行结果

七、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成) 1. 编程实现在双向循环链表上的插入、删除和查找操作

⑴ 实验要求

（1）输入链表的长度和各元素的值，用尾插法建立双向循环链表，并输出链表中各元素值，观察输入的内容与输出的内容是否一致。

（2）在双向循环链表的第i个元素之前插入一个值为x的元素，并输出插入后的链表中各元素值。

（3）删除双向循环链表中第i个元素，并输出删除后的链表中各元素值。

（4）在双向循环链表中查找值为x元素，如果查找成功，则显示该元素在链表中的位置，否则显示该元素不存在。

⑵ 核心算法提示

双向循环链表采用的存储结构描述如下：

typedef struct DULNODE

{ Elemtype data; /*数据域*/

struct DULNODE *prior; /*指向前驱结点的指针域*/ struct DULNODE *next;/*指向后继结点的指针域*/

}DULNODE,*DuLinklist; typedef int Elemtype;

不论是建立双向循环链表还是在双向循环链表中进行插入、删除和查找操作，其操作方法和步骤都跟单链表类似。只不过要注意两点：

（1）凡是在操作中遇到有修改链的地方，都要进行前驱和后继两个指针的修改。（2）单链表操作算法中的判断条件：p= =NULL 或p!=NULL ,在循环链表的操作算法中则需改为：p!= L,其中L为链表的头指针。

⑶ 核心算法描述

void DuList_creat (DuLinklist &L,int n) /*输入n个整数（其中n为表长），将这些整数作为data

域并用尾插法建立一个带头结点的双向循环链表的函数*/

{ L=( DuLinklist)malloc(sizeof(DULNODE));/*为头结点分配空间*/

L->next=L->prior=L;

/*使头结点的后继指针和前驱指针都指向自身，形成空的双向循环链表*/

r=L; /*尾指针初始指向头结点*/

for (i=0;i

{ p=(DuLinklist)malloc(sizeof(DULNODE));/*为一个新结点分配空间*/ scanf(\从键盘输入值，并保存在新结点数据域中*/ p->next=r->next; /*新结点后继指针指向尾结点r的后继结点*/ p->prior=r; /*新结点的前驱指针指向尾结点r*/

r->next=p; /*尾结点的后继指针指向新结点*/

r=p; /*尾指针指向新结点，即新结点成为尾结点*/

}

L->prior=r; /*使尾结点成为头结点的前驱结点*/ }

status DuList_search(DuLinklist L, int i;Elemtype &e)

/*在带头结点的双向循环链表L中查找第i个元素，如果查找成功则用e返回其值*/

{ p=L->next; /*使指针p指向第1个元素结点*/ j=1; /*计数器赋初值为1*/

while (p!=L && jnext; j++;

} if (j!=i)

return ERROR; /*如果i值不合法，即i值小于1或大于表长，则出错*/ e=p->data; /*如果第i个元素存在，则将该元素值赋给e*/ return OK; }

status DuList_insert(DuLinklist &L,int i;Elemtype x)

/*在带头结点的双向循环链表L中第i个位置之前插入新元素x*/

{ p=L->next; j=1;

while(p!=L &&j

{ p=p->next;

++j; }

if(j!=i)

return ERROR; /*若位置不正确,即i小于1或大于表的长度加1，则出错*/ s=(DuLinklist)malloc(sizeof(DULNODE)); /*为一个新结点s分配空间*/ s->data=x; /*为新结点数据域赋值*/

/*下面四条语句就是完成修改链，将新结点s插入到p结点之前*/ s->next=p;

p->prior->next=s;

s->prior=p->prior;

p->prior=s;

return OK;

}

status DuList_delete(DuLinklist &L,int i,Elemtype &x)

/*在带头结点的双向循环链表L中，删除第i个元素结点，并用x返回其值*/ { p=L->next;j=1;

while(p!=L&&jnext;

++j; }

if (j!=i)

return ERROR; /*若位置不正确，即i小于1或大于表长，则出错*/

q=p; /*记下被删结点*/

p->prior->next=p->next; /*修改链使得p结点从链中脱离*/ p->next->prior=p->prior; x=q->data;

printf(\ free(q); //释放被删结点空间 return OK; }

提醒: 请将上述算法与单链表上相应操作的算法对照学习，特别注意它们不相同的地方。

2．编写一个程序，计算出一个单链表中数据域值为一个指定值x的结点个数。

实验要求：

⑴ 从键盘输入若干个整数，以此序列为顺序建立一个不带头结点的单链表； ⑵ 输出此单链表中的各个数据元素值；

⑶ 给定一个x的具体整数值，计算并返回此单链表中数据域值为x的结点个数值。

实验B03: 栈的操作实验

一、实验名称和性质

所属课程实验名称实验学时实验性质必做/选做数据结构栈的操作 2 □验证 □综合 √设计 √必做 □选做二、实验目的

1．掌握栈的存储结构的表示和实现方法。 2．掌握栈的入栈和出栈等基本操作算法实现。 3．了解栈在解决实际问题中的简单应用。三、实验内容

1．建立顺序栈，并在顺序栈上实现入栈和出栈操作（验证性内容）。 2．建立链栈，并在链栈上实现入栈和出栈操作（设计性内容）。 3．实现汉诺（Hanoi）塔求解问题（应用性设计内容）。四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

Windows环境下的TurboC2.0以上或VC++等。使用的软件名称、版本号以及模块：五、知识准备

前期要求熟练掌握了C语言的编程规则、方法和顺序栈、链栈的基本操作算法。六、验证性实验 1．实验要求

编程实现如下功能：

（1）根据输入的栈中元素个数n和各元素值建立一个顺序栈，并输出栈中各元素值。（2）将数据元素e入栈，并输出入栈后的顺序栈中各元素值。

（3）将顺序栈中的栈顶元素出栈，并输出出栈元素的值和出栈后顺序栈中各元素值。 2. 实验相关原理：

栈是一种插入和删除操作都限制在表的一端进行的特殊线性表，它的操作具有“先进后出”的特性。采用顺序存储结构的栈称为顺序栈。栈的存储结构描述如下：

#define MAXSIZE 100; /*顺序栈的最大长度*/ typedef struct

{ Selemtype base[MAXSIZE]; /*存储栈中数据元素的数组*/

int top; /*top为栈顶指针，它指示栈顶元素的存储空间的下一个存储单元*/ }Sqstack;

【核心算法提示】

1．顺序栈入栈操作的基本步骤：首先判断顺序栈是否为满，如果满，则函数返回ERROR，否则将待入栈的数据元素存放在top所指示的存储单元中，再使top后移一个存储单元位置，即将top值加1，最后函数返回OK。

2．顺序栈出栈操作的基本步骤：首先判断顺序栈是否为空，如果空，则函数返回ERROR，否则将栈顶指针前移一个存储单元位置，即将top值减1,再将top所指示的栈顶元素用e返回其值，并使函数返回OK。【核心算法描述】

status Push(Sqstack &S,Selemtype e)

/*将数据元素e压入到顺序栈S中，使其成为新的栈项元素*/ { if (S.top >=MAXSIZE) /*如果栈满，则函数返回ERROR*/ return ERROR;

S.base[S.top++]=e;/*将新元素e存放在top所指示的存储单元中,并使top值加1*/ return OK; }

status Pop(Sqstack &S,Selemtype &e)

/*将顺序栈S中的栈顶元素从栈中删除，并用e返回其值*/ { if (S.top==0) /*如果栈空，则函数返回ERROR*/ Return ERROR;

e=S.base[--S.top];/*将top值减1,并用e保存top所指示的栈顶元素值*/ return OK; }

3．源程序代码参考

#define MAXSIZE 100 typedef struct

{ int base[MAXSIZE];

int top; /*top指示存储栈顶元素的下一存储单元*/ }Sqstack; /*顺序栈的类型定义*/

Sqstack Push(Sqstack S,int e) /*顺序栈的入栈操作函数*/ { if (S.top>=MAXSIZE)

printf(\

else

S.base[S.top++]=e;

return S; }

Sqstack Pop(Sqstack S,int *e) /*顺序栈的出栈操作函数*/ { if (S.top==0)

printf(\

else

*e=S.base[--S.top];

return S; }

void Stack_display(Sqstack S) /*顺序栈的输出函数*/ { int i;

for(i=0; i

{ Sqstack S; int i,j,n,x,e;

printf(\请求输入顺序栈中元素个数*/ scanf(\

printf(\请求输入顺序栈中各个元素值*/ for(i=0;i

scanf(\ S.top=n;

printf(\ Stack_display(S);

printf(\请求输入需要入栈的新元素*/ scanf(\ S=Push(S,x);

printf(\提示输出入栈后栈中各个元素值*/ Stack_display(S); /*调用顺序栈的输出函数*/ S=Pop(S,&e);

printf(\输出出栈元素的值*/

printf(\提示输出出栈后栈中各个元素值*/ Stack_display(S); /*调用顺序栈的输出函数*/ }

4．运行结果参考如图3-1所示：

图3-1：验证性实验运行结果

七、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成) 1．编程实现链栈的入栈和出栈操作。

⑴ 实验要求

（1）根据输入的栈中元素个数和各元素值建立一个链栈，并输出链栈中各元素值, 观察输入的内容与输出的内容是否一致,特别注意栈顶元素的位置。

（2）将数据元素x入栈，并输出入栈后的链栈中各元素值。

（3）将链栈中的栈顶元素出栈，并输入出栈元素的值和出栈后链栈中各元素值。 ⑵ 核心算法提示

采用链式存储结构的栈称为链栈，链栈的存储结构描述如下：

typedef struct Snode { Selemtype data;/*数据域*/ struct Snode *next;/*指针域*/

}SNODE,* LinkStack;/*其中SNODE为链栈中的结点类型名, LinkStack为指向结点的指针类型名*/

如果栈中元素序列为{a1,a2，?,an}，则链栈的存储结构如下图3-1所示：

图3-2：链栈的存储结构示意图

top an an-1 an-2 … a1 ^

从图3-1可看出，栈的链式存储结构与单链表的存储结构相同，所有在链栈上进行入栈和出栈操作与单链表上的插入和删除操作的主要步骤相同。只不过要特别注意以下几点：

（1）链栈中无需加头结点。

（2）链栈中的指针是指向栈中元素序列的前驱结点。（3）链栈中的入栈和出栈操作都是在链表的表头进行。 ⑶ 核心算法描述

status Push(LinkStack &top,int e)

/*将数据元素e压入到链栈top中，使其成为新的栈项元素*/ { LinkStack p;

p=(LinkStack)malloc(sizeof(SNODE)); /*生成一个新的结点*/ if (!p) /*如果分配空间失败，则函数返回\ return OVERFLOW;

p->data=e; /*新结点的数据域赋值*/

p->next=top; /*修改链使新结点插入到链表的头部,并成为新的栈顶元素*/ top=p; return OK; }

status Pop(LinkStack &top,int &e)

/*将链栈top中的栈顶元素从栈中删除，并用e返回其值*/

{ LinkStack q;

if (!top) /*如果栈空，则函数返回ERROR*/ return ERROR;

e=top->data; /*将被删的栈顶元素的值保存在e中*/ q=top; /*用q记下待删的栈顶元素*/

top=q->next;

/*修改链使待删结点从链中“卸下”，此时被删结点的后继成为新的栈顶元素结点*/

free(q); /*释放被删结点的存储空间*/ return OK; }

2．编程实现汉诺（Hanoi）塔求解问题。

⑴ 实验要求

假设有三个命名为X、Y和Z的塔座，在塔座X上插有n个直径大小各不相同且从小到大编号为1,2,??,n的圆盘。现要求将塔座X上的n个圆盘借助于塔座Y移至塔座Z上，并仍按同样顺序叠排。圆盘移动时必须遵循下列规则：

① 每次只能移动一个圆盘；

② 圆盘可以插在X、Y和Z中的任何一个塔座上；

③ 任何时刻都不能将一个较大的圆盘压在较小的圆盘上。 ⑵ 核心算法提示

当n=1时，问题比较简单，只要将编号为1圆盘从塔座X直接移动到塔座Z上即可；当n>1时，若能将压在编号为n的圆盘上的n-1个圆盘从塔座X借助于塔座Z移至塔座Y上，则可先将编号为n的圆盘从塔座X移至塔座Z上，再将塔座Y上的n-1个圆盘借助于塔座X移至塔座Z上。而将n-1个圆盘从一个塔座借助于另一个塔座而移至到第三个塔座上是一个与原问题具有相同特征属性的问题，只是问题规模小1,因此可以用解决原问题的方法来解决。

实验B04: 队列的操作实验

一、实验名称和性质

所属课程实验名称实验学时实验性质必做/选做数据结构队列的操作 2 □验证 □综合 √设计 √必做 □选做二、实验目的

1．掌握队列存储结构的表示和实现方法。 2．掌握队列的入队和出队等基本操作的算法实现。 3．了解队列在解决实际问题中的简单应用。三、实验内容

1．建立顺序循环队列，并在顺序循环队列上实现入队、出队基本操作（验证性内容）。 2．建立循环链队列，并在循环链队列上实现入队、出队基本操作（设计性内容）。 3．实现键盘输入循环缓冲区问题（应用性设计内容）。四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

Windows环境下的TurboC2.0以上或VC++ 使用的软件名称、版本号以及模块：五、知识准备

前期要求熟练掌握了C语言的编程规则、方法和顺序循环队列、循环链队列的基本操作算法。

六、验证性实验 1．实验要求

编程实现如下功能：

（1）根据输入的队列长度n和各元素值建立一个循环顺序表表示的队列（循环队列），并输出队列中各元素值。

（2）将数据元素e入队，并输出入队后的队列中各元素值。

（3）将循环队列的队首元素出队，并输出出队元素的值和出队后队列中各元素值。 2. 实验相关原理：

队列是一种插入操作限制在表尾，而删除操作限制在表头进行的特殊线性表，它的操作具有“先进先出”的特性。采用顺序存储结构的队列称为顺序队列，顺序队列的存储结构描述如下：

#define MAXQSIZE 100/*顺序循环队列的最大长度*/ typedef struct

{ Qelemtype base[MAXQSIZE]; /*存放队列元素的数组空间*/ int front; /*头指针，若队列不空，则指向队列头元素*/

int rear; /*尾指针，若队列不空，则指向队列尾元素的下一个存储单元*/ }Sqqueue;

【核心算法提示】

1．顺序循环队列入队操作的基本步骤：首先判断队列是否为满，如果队列满，则函数返回ERROR，否则将待入队的数据元素e存放在尾指针rear所指示的存储单元中，再使尾指针沿着顺序循环存储空间后移一个位置，最后函数返回OK。

2．顺序循环队列出队操作的基本步骤：首先判断队列是否为空，如果队列空，则函数返回ERROR，否则将头指针所指示的队首元素用e返回其值，再使头指针沿着顺序循环存储空间后移一个位置，最后函数返回OK。【核心算法描述】

status enqueue(Sqqueue &Q,Qelemtype e)

/*在循环队列Q中，插入新元素使其成为队尾元素*/ { if ((Q.rear+1)%MAXQSIZE==Q.front)

return ERROR; /*若队列满，插入操作不能进行，函数返回ERROR*/

Q.base[Q.rear]=e; /*新元素成为队尾元素*/

Q.rear=(Q.rear+1)%MAXQSIZE;/*利用模运算,“尾指针”加1,使尾指针后移一个位置*/ return OK; }

status dequeue(Sqqueue &Q，Qelemtype &e)

/*在循环队列Q中，删除Q的队首元素*/ { if (Q.front==Q.rear)

return ERROR;/*若队列空，删除操作不能进行，函数返回ERROR*/

e=Q.base[Q.front];/*将队首元素用e保存其值*/

Q.front=(Q.front+1)%MAXQSIZE;/*利用模运算,“头指针”加1,使头指针后移一个位置*/ return OK;

}

3．源程序代码参考

#define MAXQSIZE 100 typedef struct { int base[MAXQSIZE]; int front; int rear; } Sqqueue;

Sqqueue enqueue(Sqqueue Q,int e)/*队列的入队函数*/ { if ((Q.rear+1)%MAXQSIZE==Q.front) printf(\ else

{Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAXQSIZE; }

return Q; }

Sqqueue dequeue(Sqqueue Q,int *e)/*队列的出队函数*/ { int x;

if (Q.front==Q.rear) printf(\ else

{ *e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; } return Q; }

void display(Sqqueue Q)/*队列元素输出函数*/ { int k,m;

k=Q.front;m=Q.rear; while(k!=m)

{ printf(\ k=(k+1)%MAXQSIZE;} printf(\ }

main()/*主函数*/ { Sqqueue Q; int i,n,x,y,e;

Q.rear=Q.front=0; /*初始化顺序队列，使其成为空队列*/ printf(\请求输入队列的长度*/ scanf(\

printf(\请求输入队列中各个元素*/ for(i=1;i<=n;i++) {scanf(\

Q=enqueue(Q,x);}/*调用队列插入函数*/ printf(\

display(Q);/*调用队列元素输出函数*/

printf(\请求输入需要插入的元素*/ scanf(\

Q=enqueue(Q,y);/*调用队列插入函数*/

printf(\提示显示执行入队操作后的队列*/ display(Q);/*调用队列元素输出函数*/ Q=dequeue(Q,&e);/*调用队列删除函数*/

printf(\显示被删的队首元素值*/

printf(\提示显示执行出队操作后的队列*/ display(Q);/*调用队列元素输出函数*/ }

4．运行结果参考如图4-1所示：

图4-1: 验证性实验运行结果

七、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成) 1．编程实现对循环链队列的入队和出队操作。

⑴ 实验要求

①根据输入的队列长度n和各元素值建立一个带头结点的循环链表表示的队列（循环链队列），并且只设一个尾指针来指向尾结点，然后输出队列中各元素值。

②将数据元素e入队，并输出入队后的队列中各元素值。

③将循环链队列的队首元素出队，并输出出队元素的值和出队后队列中各元素值。 ⑵ 核心算法分析

采用链式存储结构的队列称为链队列，链队列的存储结构描述如下：

typedef struct CQnode {

Qelemtype data;/*数据域*/ struct CQnode *next;/*指针域*/ }CQNODE,*CQLink;

如果队列中元素序列为{a1,a2，?,an}，则带头结点的循环链队列的存储结构如下图4-1所示：

图4-2：循环链队列的存储结构示意

rear a1 a2 … an

从图4-1可看出，队列的循环链式存储结构与循环单链表的存储结构相同，所有在循环链队列上进行入队和出队操作与单链表上的插入和删除操作的主要步骤相同。只不过要特别注意以下几点：

①此循环链队列是通过一个指向队尾结点的指针rear来标识的,则rear指向队尾元素结点，rear->next指向队头结点，而rear->nexnt->next指向队首元素结点。

②队列的入队操作是在链表的表尾（队尾）进行，而出队操作则在链表的表头（队首）进行。

③在出队操作时要注意：如果当链表中只有一个结点，即被删结点既是队首结点，又是队尾结点时，要进行尾指针的修改。

⑶ 核心算法描述

void InitCiQueue(CQLink &rear)

/*初始化循环链表表示的队列rear,其中rear指向队尾元素*/

{ rear=(CQNODE*)malloc(sizeof(CQNODE)); /*产生一个头结点，并使队尾指针指向它*/ rear->next=rear; /*形成循环*/ }

入队操作：

status EnCiQueue(CQLink &rear, int x) /*把元素x插入到循环链表表示的队列rear中*/ { p=(CQNODE*)malloc(sizeof(CQNODE)); If

p->data=x; /*产生一个新结点p*/

p->next=rear->next; /*直接把p插入到rear的后面*/ rear->next=p;

rear=p; /*修改尾指针,使p成为新的队尾结点*/ }

status DeCiQueue(CQLink &rear, int &x)

/*从用队尾指针rear表示的循环链表删除一个队首元素，并用x返回其数据域的值。*/ { if(rear==rear->next) return ERROR; /*如果队列为空，则函数返回ERROR*/ p=rear->next->next;/*用p指针指向队首结点,也是待删结点*/ x=p->data; /* 用x保存待删队首结点的数据域的值*/

rear->next->next=p->next;/*修改链，使p的后继成为新的队首结点*/

if (rear==p) /*如果待删的结点p是队尾结点,则要使队尾指针指向原来队尾结点的后继(头结

点)*/

rear=rear->next;

free(p); /*释放待删结点的空间*/ return OK; }

2．编程实现键盘输入循环缓冲区问题。 ⑴ 实验要求

有两个进程同时存在于一个应用程序中。其中一个进程在屏幕上连续显示字符“A”，与此同时，程序不断检测键盘是否有输入，如果有的话，就读入用户链入的字符并保存到缓冲区中。在用户输入时，键入的字符并不立即回显在屏幕上。当用户键入一个逗号“，”时表示第一个进程结束，第二个进程从缓冲区中读取那些已键入的字符并显示在屏幕上。第二个进程结束后，程序又进入第一个进程，重新显示字符“A”，同时用户又可以继续键

入字符，直到用户输入一个分号“；”键，才结束第一个进程，同时也结束整个进程。

⑵ 核心算法提示

在操作系统中，循环队列经常用于实时应用程序。例如，当程序正在执行其他任务时，用户可以从键盘上不断键入所要输入的内容。很多字处理软件就是这样工作的。系统在利用这种分时处理方法时，用户键入的内容不能在屏幕上立刻显示出来，直到当前正在工作的那个进程结束为止。但在这个进程执行时，系统是在不断地检查键盘状态，如果检测到用户键入了一个新的字符，就立刻把它存到系统缓冲区中，然后继续运行原来的进程。在当前工作的进程结束后，系统就从缓冲区中取出键入的字符，并按要求进行处理。所以，这里的键盘输入缓冲区可采用循环队列。队列保证了输入字符先输入、先保存、先处理的要求，循环结构又有效地限制了缓冲区的大小，并避免了假溢出问题。

实验B05: 二叉树的操作实验

一、实验名称和性质

所属课程实验名称实验学时实验性质必做/选做数据结构二叉树的操作 2 □验证 □综合 √设计 √必做 □选做二、实验目的

1．理解二叉树的类型定义与性质。

2．掌握二叉树的二叉链表存储结构的表示和实现方法。 3．掌握二叉树遍历操作的算法实现。 4．熟悉二叉树遍历操作的应用。三、实验内容

1．建立二叉树的二叉链表存储结构。

2．实现二叉树的先序、中序和后序三种遍历操作（验证性内容）。

3．应用二叉树的遍历操作来实现判断两棵二叉树是否相等的操作（设计性内容）。 4．求从二叉树根结点到指定结点p之间的路径（应用性设计内容）。四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

Windows环境下的TurboC2.0以上或VC++ 使用的软件名称、版本号以及模块：五、知识准备

前期要求掌握二叉树的二叉链表的存储结构表示和三种遍历操作算法。六、验证性实验 1．实验要求

编程实现如下功能：

（1）假设二叉树的结点值是字符，根据输入的一棵二叉树的完整先序遍历序列建立一棵以二叉链表表示的二叉树。

（2）对二叉树进行先序、中序和后序遍历操作，并输出遍历序列，观察输出的序列是否与逻辑上的序列一致。

（3）主程序中要求设计一个菜单，允许用户通过菜单来多次选择执行哪一种遍历操作。 2. 实验相关原理：

二叉树的形式定义：二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。

二叉树的二叉链表存储结构描述为：

typedef char Telemtype; typedef struct Bitnode

{ Telemtype data;/*数据域*/

struct Bitnode *lchild, *rchild;

/*指针域,分别指向该结点的左、右孩子*/

}Bitnode,*Bitree;

【核心算法提示】

二叉树的遍历是指按某条搜索路径周游二叉树，对树中每个结点访问一次且仅访问一次。其中先序、中序和后序遍历操作步骤分别为：

（1）先序遍历：若二叉树为空树，则空操作；否则先访问根结点，再先序遍历左子树，最后先序遍历右子树。

（2）先序遍历：若二叉树为空树，则空操作；否则先中序遍历左子树，再访问根结点，最后中序遍历右子树。

（3）先序遍历：若二叉树为空树，则空操作；否则先后序遍历左子树，再后序遍历右子树，最后访问根结点。

注意：这里的“访问”的含义可以很广，几乎可以含盖对结点的任何一种操作。如：输出结点的信息、判断结点是否为叶子结点等等。

由于二叉树是一种递归定义，所以，要根据二叉树的某种遍历序列来实现建立一棵二叉树的二叉链表存储结构，则可以模仿对二叉树遍历的方法来加以实现。如：如果输入的是一棵二叉树的完整先序遍历序列，则可利用先序遍历方法先生成根结点，再用递归函数调用来实现左子树和右子树的建立。所谓完整的先序遍历序列就是在先序遍历序列中加入空树信息。

【核心算法描述】

void createbitree(Bitree &T)

/*根据输入的完整先序遍历序列建立一棵二叉树*/

{ scanf(\读取完整先序序列中的一个字符*/ if(x==‘#’) T=NULL; else

{ T=(Bitree)malloc(sizeof(Bitnode));/*生成根结点*/ T->data=x;

createbitree(T->lchild);/*递归建立左子树*/ createbitree(T->rchild); /*递归建立右子树*/ } }

void preorder(Bitree T) /*先序遍历二叉树*/ { if(T!=NULL)/*若二叉树非空*/

{ visit(T->data); /*访问根结点*/

preorder(T->lchild); /*递归先序遍历左子树*/ preorder(T->rchild); /*递归先序遍历右子树*/ }

}

void inorder(Bitree T) /*中序遍历二叉树*/ { if(T!=NULL) /*若二叉树非空*/

{ inorder(T->lchild); /*递归中序遍历左子树*/

visit(T->data); /*访问根结点*/

inorder(T->rchild); /*递归中序遍历右子树*/

}

void postorder(Bitree T) /*后序遍历二叉树*/ { if(T!=NULL) /*若二叉树非空*/

{ postorder(T->lchild); /*递归后序遍历左子树*/ postorder(T->rchild); /*递归后序遍历右子树*/ visit(T->data); /*访问根结点*/ } }

3．源程序代码参考

#include typedef struct Bitnode {char data;

struct Bitnode *lchild,*rchild; }Bitnode,*Bitree;

Bitree creat(Bitree T)/*建立二叉树函数*/ { char x;

scanf(\ if (x=='#') T=NULL; else

{T=(Bitree)malloc(sizeof(Bitnode)); if (!T)

{printf(\ exit(-1); } else

{T->data=x;

T->lchild=creat(T->lchild); T->rchild=creat(T->rchild); } } return T; }

Bitree preorder(Bitree T)/*先序遍历二叉树函数*/ { if (T!=NULL)

{ printf(\ preorder(T->lchild); preorder(T->rchild);

} }

void midorder(Bitree T) /*中序遍历二叉树函数*/ { if (T!=NULL)

{ midorder(T->lchild); printf(\ midorder(T->rchild); } }

void backorder(Bitree T) /*后序遍历二叉树函数*/ { if (T!=NULL)

{ backorder(T->lchild); backorder(T->rchild); printf(\ } }

main()/*主函数*/

{ Bitree T=NULL; char x;

printf(\请求输入二叉树中各个元素*/ T=creat(T);/*调用建立二叉树函数*/ while(1)

{ printf(\ printf(\ printf(\ printf(\

printf(\请求选择遍历方式*/ scanf(\ switch(x)

{case 1: printf(\

preorder(T); /*调用先序遍历二叉树函数*/ break;

case 2: printf(\

midorder(T); /*调用中序遍历二叉树函数*/ break;

case 3: printf(\

backorder(T); /*调用后序遍历二叉树函数*/ break; case 4: return;

default:printf(\ }

printf(\ } }

4．运行结果参考如图5-1所示：

图5-1：验证性实验运行结果

说明：上述对应的二叉树如图5-2所示。

七、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成) 1．编程实现根据二叉树的先序遍历序列和中序遍历序列来建立两棵二叉树，并判断这两棵二叉树是否相等。

⑴ 实验要求

① 假设二叉树的结点值是字符，请分别根据输入的两棵二叉树的先序遍历序列和中序遍历序列来建立二叉链表表示的两棵二叉树。

图5-2：建立的二叉树

a b c e df 34

② 分别利用先序、中序和后序遍历方法来实现判断两棵二叉树是否相等的操作。 ③ 主程序中要求设计一个菜单，允许用户通过菜单来多次选择执行利用哪一种遍历方法来判断两棵二叉树是否相等。

⑵ 核心算法提示 1）二叉树的建立

二叉树的先序遍历序列：

根左子树先序序列右子树先序序列二叉树的中序遍历序列：

左子树先序序列根右子树先序序列图5-3：二叉树的先序、中序遍历序列特征图

假设二叉树的先序遍历序列和中序遍历序列已经存储在数组Pre和Mid中，其序列分列具有如图5-3所示的特征。

根据此特征，建立二叉树的基本步骤可归纳为：

① 建立根结点，取先序先序遍历序列中的第一个字符作为根结点的数据域值； ② 在中序遍历序列中查找确定这个根结点在中序遍历序列中的位置，由此得到在根结点左边的序列即为此根结点左子树的中序遍历序列，而右边的序列即为此根结点右子树的中序遍历序列。

③ 根据左、右子树中序遍历序列中的字符个数再在先序遍历序列中确定左、右子树的先序遍历序列。

④ 根据（2）、（3）确定的左、右子树的先序和中序遍历序列采用递归调用的方法建立根结点的左、右子树。

2）判断两棵二叉树是否相等

假设T1和T2是两棵二叉树，如果两棵二叉树都是空树；或者两棵树的根结点的值相等，并且根结点的左、右子树分别也相等，则称二叉树T1与T2是相等的。所以，也可以利用先序、中序和后序遍历方法，采用递归函数来判断两棵树是否相等。假设两棵树相等，函数返回1，否则返回0。下面以用先序遍历方法为例，说明其基本操作步骤为：

① 如果两棵二叉树都为空，则函数返回1；

② 如果两棵二叉树都不为空，则先判断两棵树的根结点值是否相等，如果相等，则再采用递归调用的方法判断它的左、右子树是否相等，如果都相等则函数返回1；

③ 其它情况都返回0。 ⑶ 核心算法描述

char Pre[100],Mid[100]; /*存储先序和中序序列的字符数组，定义为全局变量*/ Bitree creat_sub(Bitree T,int Pre_start,int Pre_end,int Mid_start,int Mid_end) /*已知二叉树的先序序列和中序序列，建立此二叉树*/ { int i,ltreelen,rtreelen;

T=(Bitree)malloc(sizeof(Bitnode)); /*建立根结点*/

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; }

2．编程求从二叉树根结点到到指定结点p之间的路径。

⑴ 实验要求

① 假设二叉树的结点值是字符，请根据输入的二叉树后序遍历序列和中序遍历序列来建立二叉链表表示的二叉树,并对其进行某种遍历,输出遍历序列以验证建立的二叉树是否正确。

② 任意给定一结点p,输出从二叉树的根结点到该结点p的路径。 ⑵ 核心算法提示

要求出从根结点到指定结点p之间的路径，可利用后序遍历的非递归算法来实现。由于

后序遍历当访问到p所指结点时，栈中所有结点均为p所指结点的祖先，由这些祖先便构成了一条从根结点到p结点之间的路径。

实验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;

}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; /*找不到匹配记录*/ }

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\

printf(\ scanf(\ switch(x) { case 1:

printf(\请求输入顺序表表长*/ scanf(\

printf(\请求输入n个关键字值*/ for(i=1;i<=ST.length;i++) scanf(\

printf(\请求输入待查找的记录关键字值*/ scanf(\

pos=sxsearch(ST,key); /*调用顺序查找函数*/ break; case 2:

printf(\请求输入顺序表表长*/ scanf(\

printf(\请求输入n个关键字值（必须升序排列）*/ for(i=1;i<=ST.length;i++) scanf(\

printf(\请求输入待查找的记录关键字值*/ scanf(\

pos=binsearch(ST,key);/*调用二分法查找函数*/ break; case 3: return;

default: printf(\ } if(pos==0)

printf(\若找不到，提示信息*/ else

printf(\ at position %d\\n\若找到，输出位置*/ }

4．运行结果参考如图6-1所示

图6-1 验证性实验运行结果七、设计性实验 1．实验要求

编程实现如下功能：（1）建立索引查找表

（2）利用索引查找确定给定记录在索引查找表中的块号和在块中的位置。 2．核心算法分析

索引查找表有索引表和块表两部分所构成，其中索引表存储的是各块记录中的最大关键字值和各块的起始存储地址，用顺序存储结构，各块的起始存储地址的初始值置为空指针；而块表中存储的是查找表中的所有记录并且按块有序，用链式存储或顺序存储结构，在此用链式存储结构。则索引查找表的存储结构图如6-2所示：

ST ST. Length 3 ST. r

r[0] r[1] r[2] r[3]

12 23 47 …… 最大关键字块链头指针

3 15 31 6 23 45 12 14 37 9 21 47 ^ 4 ^ 13 ^ 图6-2 索引查找表的存储结构示意图

将如图6-2所示的存储结构描述为： #define MAXSIZE 100

typedef int keytype;

typedef struct bnode /*块链中的结点类型*/ { keytype key; /*存储块中记录的关键字值*/

struct bnode *next; /*指向块链中下一记录结点的指针*/ } Bnode;

typedef struct snode /*索引表中元素的类型*/

{ keytype Maxkey; /*存储各块记录中的最大关键字值*/ Bnode *head; /*块链的头指针*/ }Snode;

typedef struct /*索引查找表的结构类型*/ { Snode r[MAXSIZE]; /*索引顺序表*/

int length; /*索引顺序表中存储数据的个数*/ }Stable;

由于在索引查找表中，索引表是按关键字从小到大排列的有序顺序表，块链是一个无序链表，所有索引表的查找过程可归纳为：

（1）在索引表中用二分查找确定待查找的记录所在的块号；

（2）沿着块链指针用顺序查找的方法确定待查找的记录在块链中的存储位置。

如果查找成功，则输出待查找记录在索引表中的块号和在块链中的存储地址；如果查找失败，则输出“没有找到”的信息。 3．核心算法描述

int findblock(Stable ST, keytype key)

/*用二分查找法在索引查找表ST的索引表中确定关键字值为key的待查找记录所在的块号,函数并返回值其块号值*/ { int low,high,mid; low=1;high=ST.length; while(low<=high) { mid=(low+high)/2; if (key

low=mid+1; }

return high+1; }

Blink findrec(Stable ST,keytype key)

/*用顺序查找法在索引查找表的块链中确定关键字值为key的待查找记录的存储位置，如查找成功则函数返回其地址值，否则返回空指针*/ { Blink p; int Bno;

Bno=findblock(ST,key); /*调用函数，确定待查记录所在块号*/ p=ST.r[Bno].head; /*取到待查记录所在块链的头指针*/ while (p&&p->key!=key) /*顺着链指针依次查找*/ p=p->next;

return p; /*返回查找结果*/ }

实验B07: 二叉排序树的操作实验

一、实验名称和性质

所属课程实验名称实验学时实验性质必做/选做数据结构二叉排序树的操作 2 □验证 □综合 √设计 □必做 √选做二、实验目的

1．掌握二叉排序树的含义及其在计算机中的存储实现。 2．掌握在二叉排序树上查找操作的算法实现。 3．掌握二叉排序树的插入、删除操作的算法实现。三、实验内容 1．建立二叉排序树。

2．在二叉排序树上实现对给定值进行查找操作（验证性内容）。 3．在二叉排序树上实现插入、删除一个指定结点（设计性内容）。 4．判断一棵二叉树是否为二叉排序树（设计性内容）。四、实验的软硬件环境要求

硬件环境要求：

PC机（单机）

Windows环境下的TurboC2.0以上或VC++等。使用的软件名称、版本号以及模块：五、知识准备

前期要求掌握二叉排序树的含义、二叉排序树上的查找算法和二叉排序上的插入、删除操作的算法。六、验证性实验 1．实验要求

编程实现如下功能：

（1）按照输入的n个关键字序列顺序建立二叉排序树，二叉排序树采用二叉链表的存储结构。

（2）先输入待查找记录的关键字值key,然后在二叉排序树上查找该记录，如果在二叉排序树中存在该记录，则显示“找到”的信息，否则显示“找不到”的信息。 2. 实验相关原理：

二叉排序树的性质如下：

（1）若左子树不空，则左子树上所有结点的值均小于根结点的值。（2）若右子结不空，则右子树上所有结点的值均大于根结点的值。（3）左右子树又分别是二叉排序树。

二叉排序树的二叉链表存储结构描述为：

typedef struct Bitnode /*定义二叉排序树的结点类型*/

{ keytype key;/*存放记录关键值的数据域key*/ elemtype other; /*存储记录中的其它数据项的域*/

struct Bitnode *lchild, *rchild; /*左、右孩子指针域*/ }Bitnode,*Bitree;

【核心算法提示】

（1）二叉排序树查找操作的基本步骤：对于给定的待查找记录的关键字值key，在二叉排序树非空的情况下，先将给定的值key与二叉排序树的根结点的关键字值进行比较，如果相等，则查找成功，函数返回指向根结点的指针，否则，如果给定的值key小于根结点的关键字值，则在二叉排序树的左子树上继续查找；如果给定的值key大于根结点的关键字值，则在二叉排序树的右子树上继续查找，直到查找成功，或子树为空即查找失败函数返回空指针为止。

（2）二叉排序树的插入操作的基本步骤（用递归的方法）：如果已知二叉排序树是空树，则插入的结点成为二叉排序树的根结点；如果待插入结点的关键字值小于根结点的关键字值，则插入到左子树中；如果待插入结点的关键字值大于根结点的关键字值，则插入到右子树中。

【核心算法描述】

Bitree Bstsearch1(Bitree T,keytype key) /*二叉排序树查找的递归算法*/

{ if (T==NULL||key==T->key)

return T; /*当T为非空时，查找成功，否则表示查找失败*/ else if (key< T->key)

return(searchbst(T->key, key)); /*递归查找二叉排序树的左子树*/ else return(searchbst(T->key, key)); /*递归查找二叉排序树的右子树*/ }

Bitree Bstsearch2(Bitree T,keytype key) /*二叉排序树查找的非递归算法*/ { Bitree p; p=T;

while (p&& key!= p->key) { if (keykey)

p=p->lchild; /*沿左子树继续查找*/ else

p=p->rchild; /*沿右子树继续查找*/ }

return p; }

Bitree Bstinsert(Bitree T,Bitree s)

/*将结点s插入到二叉排序树T中，使其仍然构成一棵二叉排序树*/

{ if(T==NULL) T=s; /*如果已知二叉排序树是空树，则新插入的结点成为根结点*/ else if(s->key>T->key)

T->rchild=Bstinsert(T->rchild,s); /*递归调用*/ else if(s->keykey)

T->lchild=Bstinsert(T->lchild,s);/*递归调用*/ return T;}

3．源程序代码参考

#include #include typedef int elemtype; typedef int keytype;

typedef struct Bitnode /*定义二叉排序树的结点类型*/ { keytype key; elemtype other;

struct Bitnode *lchild, *rchild; }Bitnode,*Bitree;

Bitree Bstinsert(Bitree T,Bitree s)

/*将结点s插入到二叉排序树T中，使其仍然构成一棵二叉排序树*/ { if(T==NULL) T=s; else if(s->key>T->key)

T->rchild=Bstinsert(T->rchild,s); /*递归调用*/ else if(s->keykey)

T->lchild=Bstinsert(T->lchild,s);/*递归调用*/ return T;}

Bitree creat(Bitree T)

/*根据输入的n个关键字序列，建立一棵二叉排序树*/ { Bitree s; keytype key; int i,n;

printf(\ scanf(\

printf(\ for (i=0; i

s=(Bitree)malloc(sizeof(Bitnode)); /*生成一个待插入的新结点*/ s->key=key; s->lchild=NULL; s->rchild=NULL;

T=Bstinsert(T,s);/*调用二叉排序树插入函数*/ }

return T;

}

Bitree Bstsearch(Bitree T,keytype key) /*二叉排序树查找的非递归算法*/ { Bitree p; p=T;

while (p&& key!= p->key) { if (keykey)

p=p->lchild; /*沿左子树继续查找*/ else

p=p->rchild; /*沿右子树继续查找*/ } return p; }

main()/*主函数*/ { Bitree T=NULL,p; keytype key;

T=creat(T); /*调用二叉排序树建立函数*/

printf(\请求输入需要查找的记录的关键字值*/ scanf(\

p=Bstsearch(T,key);/*调用二叉排序树查找函数*/ if(p==NULL)

printf(\输出“找不到”信息*/ else

printf(\输出“找到”信息*/ }

5．运行结果参考如图7-1所示：

图7-1 验证性实验运行结果

七、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成) 1．在二叉排序树上实现插入、删除一个指定结点。

⑴ 实验要求

（1）按照输入的n个关键字序列顺序建立二叉排序树，二叉排序树采用二叉链表的存储结构。

（2）输入待插入记录的关键字值key,然后在二叉排序树上查找该记录，如果查找失败，则在二叉排序树中插入该记录对应的结点，并输出插入操作后的二叉排序树（以某种遍历序列表示）。

（3）输入待删除记录的关键字值key,然后在二叉排序树上查找该记录，如果查找成功，则在二叉排序树中删除该记录对应的结点，并输出删除操作后的二叉排序树（以某种遍历序列表示）。

⑵ 核心算法分析

要实现以上功能，主要要完成查找、插入和删除操作算法的编写。插入操作是在查找失败时才进行，其算法内容验证性实验中的内容相同。为了删除操作的需要，查找算法只要在验证性实验的查找算法内容中，当搜索指针p移动之前，增加一个记载其双亲结点的指针f的操作语句。与插入相反，删除操作是在查找成功时才进行，下面对删除操作的算法详细分析如下：由二叉排序树的性质决定，中序遍历二叉排序树可得到一个关键字的有序序列，则在二叉排序树中删除一个结点就相当于删除有序序列中的一个记录，只要保证删除某个结点后仍然保持二叉排序树的特性即可。假设用p指针指向被待删除的结点，f指针指向二叉排序树中p的双亲结点，删除操作的关键是找到p结点在中序遍历序列中的前驱结点s，再用s替代掉p，如图7-2所示：

图7-2

前驱结点被删结点

则删除操作需要分三种情况分别处理：

（1）若待删除的结点是叶子结点，则只要将其双亲结点中相应指针域的值改为“空”；（2）若待删除的结点只有左子树或者只有右子树，则只要将其双亲结点的相应指针域的值改为 “指向待删除结点的左子树或右子树”；

（3）若待删除的结点既有左子树又有右子树，则以其中序遍历序列下的前驱结点替代掉待删结点p，然后再删除该前驱结点s。 ⑶ 核心算法描述

Bitree f=NULL; /*全局变量*/ Bitree Bstsearch(Bitree T, keytype key)

/*在二叉排序树中查找关键字为key的记录，如果找到则返回该记录结点的地址,全局变量f指向该结点的双亲结点，否则返回空指针,全局变量f指向搜索路径上最后一个访问的结点*/ { Bitree p;

p=T;

while (p&& key!= p->key) { if (keykey)

{ f=p; /* 在p移动之前，用f 记下p, 使f永远指向p的双亲结点*/ p=p->lchild; /*沿左子树继续查找*/ } else { f=p;

p=p->rchild; /*沿右子树继续查找*/ } } return p; }

Bitree Bstinsert(Bitree T,Bitree s)