数据结构实验C语言版(1).doc

南阳理工学院南阳理工学院 数据结构数据结构 C 语言版语言版 上机实验指导书上机实验指导书 软件学院 软件工程 目目 录录 实验 1 线性表应用 实验 2 栈和队列的应用 14 实验 3 线性表应用 27 实验 4 图论及其应用 46 实验 5 查找 实验 6 排序 64 实验实验 1 线性表应用线性表应用 1 1 实验目的实验目的 3 了解和掌握线性表顺序存储和链式存储在计算机中的表示 基本操做在计算机中的实 2 能够利用线性表结构对实际问题进行分析建模 利用计算机求解 1 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合 二 实验内容及步骤二 实验内容及步骤 1 利用程序设计语言分别实现顺序表和链表的抽象数据类型 2 掌握程序分文件 头文件和实现文件 书写的方式 3 分别用顺序表和链表实现课本算法 2 2 合并两个非递减有序序列 并对其时间性能做 出分析 三 实验步骤与调试过程三 实验步骤与调试过程 以线性表来描述一元多项式 储存结构采用单链表 每个结点储存的多项式中某一项 的系数和指数 建立单链表时指数高的结点列于指数低的结点之后 即线性表的元素按指 数递增有序排列 四 实验结果四 实验结果 五 疑难小结五 疑难小结 当线性表的长度变化较大 难以估计其存储规模 另外对线性表频繁进行插入和删除 操作时 则采用链表作为存储结构可能会更好一些 在实际应用中应该考虑以下因素 1 应有利于运算的实现 2 应有利于数据的特性 3 应有利于软件环境 六 主要算法和程序清单六 主要算法和程序清单 顺序表的非递减数列合并 include 包含输入输出头文件 define ListSize 100 typedef int DataType typedef struct DataType list ListSize int length SeqList void InitList SeqList L 将线性表初始化为空的线性表只需要把线性表的长度 length 置为 0 L length 0 把线性表的长度置为 0 int ListEmpty SeqList L 判断线性表是否为空 线性表为空返回 1 否则返回 0 if L length 0 判断线性表的长度是否为 9 return 1 当线性表为空时 返回 1 否则返回 0 else return 0 int GetElem SeqList L int i DataType e 查找线性表中第 i 个元素 查找成功将该值返回给 e 并返回 1 表示成功 否则返回 1 表 示失败 if iL length 在查找第 i 个元素之前 判断该序号是否合法 return 1 e L list i 1 将第 i 个元素的值赋值给 e return 1 int LocateElem SeqList L DataType e 查找线性表中元素值为 e 的元素 查找成功将对应元素的序号返回 否则返回 0 表示失 败 int i for i 0 i L length i 从第一个元素开始比较 if L list i e return i 1 return 0 int InsertList SeqList L int i DataType e 在顺序表的第 i 个位置插入元素 e 插入成功返回 1 如果插入位置不合法返回 1 顺序 表满返回 0 int j if iL length 1 在插入元素前 判断插入位置是否合法 printf 插入位置 i 不合法 n return 1 else if L length ListSize 在插入元素前 判断顺序表是否已经满 不能插入 元素 printf 顺序表已满 不能插入元素 n return 0 else for j L length j i j 将第 i 个位置以后的元素依次后移 L list j L list j 1 L list i 1 e 插入元素到第 i 个位置 L length L length 1 将顺序表长增 1 return 1 int DeleteList SeqList L int i DataType e int j if L length 0 printf 顺序表已空不能进行删除 n return 0 else if iL length printf 删除位置不合适 n return 1 else e L list i 1 for j i jlength 1 j L list j 1 L list j L length L length 1 return 1 int ListLength SeqList L return L length void ClearList SeqList L L length 0 void MergeList SeqList A SeqList B SeqList C 合并顺序表 A 和 B 中元素的函数声明 void main int i flag DataType a 6 11 11 23 DataType b 2 10 12 12 21 DataType e SeqList A B C 声明顺序表 A B 和 C InitList 初始化顺序表 A InitList 初始化顺序表 B InitList 初始化顺序表 C for i 1 i sizeof a sizeof a 0 i 将数组 a 中的元素插入到顺序表 A 中 if InsertList return for i 1 i sizeof b sizeof b 0 i 将数组 b 中元素插入到顺序表 B 中 if InsertList return printf 顺序表 A 中的元素 n for i 1 i A length i 输出顺序表 A 中的每个元素 flag GetElem A i 返回顺序表 A 中的每个元素到 e 中 if flag 1 printf 4d e printf n printf 顺序表 B 中的元素 n for i 1 i B length i 输出顺序表 B 中的每个元素 flag GetElem B i 返回顺序表 B 中的每个元素到 e 中 if flag 1 printf 4d e printf n printf 将在 A 中出现 B 的元素合并后 C 中的元素 n MergeList A B 将在顺序表 A 和 B 中的元素合并 for i 1 i C length i 显示输出合并后 C 中所有元素 flag GetElem C i if flag 1 printf 4d e printf n getch void MergeList SeqList A SeqList B SeqList C 合并顺序表 A 和 B 的元素到 C 中 并保持元素非递减排序 int i j k DataType e1 e2 i 1 j 1 k 1 while i A length 取出顺序表 A 中的元素 GetElem B j 取出顺序表 B 中的元素 if e1 e2 比较顺序表 A 和顺序表 B 中的元素 InsertList C k e1 将较小的一个插入到 C 中 i 往后移动一个位置 准备比较下一个元素 k else InsertList C k e2 将较小的一个插入到 C 中 j 往后移动一个位置 准备比较下一个元素 k while i A length 如果 A 中元素还有剩余 这时 B 中已经没有元 素 GetElem A i InsertList C k e1 将 A 中剩余元素插入到 C 中 i k while jlength A length B length C 的表长等于 A 和 B 的表长的和 链式表的非递减数列合并链式表的非递减数列合并 包含头文件 include include include 宏定义和单链表类型定义 define ListSize 100 typedef int DataType typedef struct Node DataType data struct Node next ListNode LinkList void MergeList LinkList A LinkList B LinkList C 将单链表 A 和 B 的元素合并到 C 中的 函数声明 void InitList LinkList head 将单链表初始化为空 动态生成一个头结点 并将头结点的指 针域置为空 if head LinkList malloc sizeof ListNode NULL 为头结点分配一个存储空间 exit 1 head next NULL 将单链表的头结点指针域置为空 int ListEmpty LinkList head 判断单链表是否为空 就是通过判断头结点的指针域是否为空 if head next NULL 判断 单链表头结点的指针域是否为空 return 1 当单链表为空时 返回 1 否则返回 0 else return 0 ListNode Get LinkList head int i 查找单链表中第 i 个结点 查找成功返回该结点的指针表示成 功 否则返回 NULL 表示失败 ListNode p int j if ListEmpty head 在查找第 i 个元素之前 判断链表是否为空 return NULL if inext NULL j if j i return p 找到第 i 个结点 返回指针 p else return NULL 如果没有找到第 i 个元 素 返回 NULL ListNode LocateElem LinkList head DataType e 查找线性表中元素值为 e 的元素 查找成功将对应元素的结点 指针返回 否则返回 NULL 表示失败 ListNode p p head next 指针 p 指向第一个结点 while p if p data e 找到与 e 相等的元素 返 回该序号 p p next else break return p int LocatePos LinkList head DataType e 查找线性表中元素值为 e 的元素 查找成功将对应元素的序号 返回 否则返回 0 表示失败 ListNode p int i if ListEmpty head 在查找第 i 个元 素之前 判断链表是否为空 return 0 p head next 指针 p 指向第一 个结点 i 1 while p if p data e 找到与 e 相等的 元素 返回该序号 return i else p p next i if p 如果 没有找到与 e 相等的元素 返回 0 表示失败 return 0 int InsertList LinkList head int i DataType e 在单链表中第 i 个位置插入一个结点 结点的元素值为 e 插入 成功返回 1 失败返回 0 ListNode p pre 定义指向第 i 个元素的前 驱结点指针 pre 指针 p 指向新生成的结点 int j pre head 指针 p 指向头结 点 j 0 while pre next NULL j if pre 如果没找到 说明插入位置错误 printf 插入位置错 return 0 新生成一个结点 并将 e 赋值给该结点的数据域 if p ListNode malloc sizeof ListNode NULL exit 1 p data e 插入结点操作 p next pre next pre next p return 1 int DeleteList LinkList head int i DataType e 删除单链表中的第 i 个位置的结点 删除成功返回 1 失败返回 0 ListNode pre p int j pre head j 0 while pre next NULL j if j i 1 如果没找到要 删除的结点位置 说明删除位置错误 printf 删除位置错误 return 0 指针 p 指向单链表中的第 i 个结点 并将该结点的数据 域值赋值给 e p pre next e p data 将前驱结点的指针域指向要删除结点的下一个结点 也就是将 p 指向的结点与单链表断开 pre next p next free p 释放 p 指向的结 点 return 1 int ListLength LinkList head ListNode p int count 0 p head while p next NULL p p next count return count void DestroyList LinkList head ListNode p q p head while p NULL q p p p next free q void main int i DataType a 6 7 9 14 37 45 65 67 DataType b 3 7 11 34 45 89 LinkList A B C 声明单链表 A 和 B ListNode p InitList 初始化单链表 A InitList 初始化单链表 B for i 1 i sizeof a sizeof a 0 i 将数组 a 中元素插入到单链表 A 中 if InsertList A i a i 1 0 printf 位置不合法 return for i 1 i sizeof b sizeof b 0 i 将数组 b 中元素插入单链表 B 中 if InsertList B i b i 1 0 printf 位置不合法 return printf 单链表 A 中的元素有 d 个 n ListLength A for i 1 idata 输出单链表 A 中的每个元素 printf n printf 单链表 B 中的元素有 d 个 n ListLength B for i 1 idata 输出单链表 B 中的每个元素 printf n MergeList A B 将单链表 A 和 B 中的元素合并到 C 中 printf 将单链表 A 和 B 的元素合并到 C 中后 C 中的元素有 d 个 n ListLength C for i 1 idata 显示输出 C 中所有元素 printf n getch void MergeList LinkList A LinkList B LinkList C 单链表 A 和 B 中的元素非递减排列 将单链表 A 和 B 中的元素合并到 C 中 C 中的元 素仍按照非递减排列 ListNode pa pb pc 定义指向单链表 A B C 的指针 pa A next pb B next C A 将单链表 A 的头结点作为 C 的头结点 C next NULL pc C 依次将链表 A 和 B 中较小的元素存入链表 C 中 while pa 如果 A 中的元素小于或等于 B 中的元素 将 A 中的元素的结 点作为 C 的结点 pc pa pa pa next else pc next pb 如果 A 中的元素大于 B 中的元素 将 B 中的元素的结点作为 C 的结点 pc pb pb pb next pc next pa pa pb 将剩余的结点插入 C 中 free B 释放 B 的头结点 实验实验 2 栈和队列的应用栈和队列的应用 一 实验目的一 实验目的 1 掌握栈和队列这两种抽象数据类型的特点 并能在相应的应用问题中正确选用它们 2 熟练掌握栈类型的两种实现方法 3 熟练掌握循环队列和链队列的基本操作实现算法 二 实验内容及步骤二 实验内容及步骤 1 用程序设计语言实现栈和队列的抽象数据类型 2 在第一题的基础上完成以下选择 选择一 1 设计并实现括号匹配算法 2 用队列实现在屏幕上打印杨辉三角 选择二 分别用栈和队列实现迷宫问题求解 选择三 分别用栈和队列实现一个列车调度系统 三 实验步骤与调试过程三 实验步骤与调试过程 首先只只置操作数栈为空 表达式起始符 为运算符栈的栈底元素 依次读入表达 式中每个字符 直至整个表达式求值完毕 四 实验结果四 实验结果 五 疑难小结五 疑难小结 对栈的顺序存储结构用了更深刻的了解 同时也对程序设计能力有了提高 加深了对 栈先进后出性质的理解 对数组的应用也十分熟练 六 主要算法 六 主要算法 括号匹配算法括号匹配算法 include include include include string h 宏定义和链栈类型定义 typedef char DataType int Match DataType e DataType ch typedef struct node DataType data struct node next LStackNode LinkStack void InitStack LinkStack top 将链栈初始化为空 动态生成头结点 并将头结点的指针域置为空 if top LinkStack malloc sizeof LStackNode NULL 为头结点分配一个存储 空间 exit 1 top next NULL 将链栈的头结点指针域置为空 int StackEmpty LinkStack top 判断链栈是否为空 就是通过判断头结点的指针域是否为空 if top next NULL 判断链栈头结点的指针域是否为空 return 1 当链栈为空时 返回 1 否则返回 0 else return 0 int PushStack LinkStack top DataType e 进栈操作就是要在链表的第一个结点前插入一个新结点 进栈成功返回 1 LStackNode p 定义指向第 i 个元素的前驱结点指针 pre 指针 p 指向新生成 的结点 if p LStackNode malloc sizeof LStackNode NULL printf 内存分配失败 exit 1 p data e 指针 p 指向头结点 p next top next top next p return 1 int PopStack LinkStack top DataType e 删除单链表中的第 i 个位置的结点 删除成功返回 1 失败返回 0 LStackNode p p top next if p 判断链栈是否为空 printf 栈已空 return 0 top next p next 将栈顶结点与链表断开 即出栈 e p data 将出栈元素赋值给 e free p 释放 p 指向的结点 return 1 int StackLength LinkStack top LStackNode p int count 0 p top while p next NULL p p next count return count void DestroyStack LinkStack top LStackNode p q p top while p q p p p next free q int GetTop LinkStack top DataType e LStackNode p p top next if p 判断链栈是否为空 printf 栈已空 return 0 e p data 将出栈元素赋值给 e return 1 void main LinkStack S char p DataType e DataType ch 60 InitStack 初始化链栈 printf 请输入带括号的表达式 n gets ch p ch while p switch p case case case PushStack S p break case case case if StackEmpty S printf 缺少左括号 n return else GetTop S if Match e p PopStack S else printf 左右括号不配对 n return default p if StackEmpty S printf 括号匹配 n else printf 缺少右括号 n int Match DataType e DataType ch if e else if e else if e else return 0 用队列实现在屏幕上打印杨辉三角用队列实现在屏幕上打印杨辉三角 包含头文件 include include typedef int DataType 定义链式队列元素的类型为整数类型 define MaxSize 100 void PrintArray int a int n void YangHuiTriangle int N typedef struct QNode DataType data struct QNode next LQNode QueuePtr typedef struct QueuePtr front QueuePtr rear LinkQueue void InitQueue LinkQueue LQ 将带头结点的链式队列初始化为空队列需要把头结点的指针域置为 0 LQ front LQNode malloc sizeof LQNode if LQ front NULL exit 1 LQ front next NULL 把头结点的指针域置为为 0 LQ rear LQ front int QueueEmpty LinkQueue LQ 判断链式队列是否为空 队列为空返回 1 否则返回 0 if LQ front next NULL 当链式队列为空时 返回 1 否则返回 0 return 1 else return 0 int EnterQueue LinkQueue LQ DataType e 将元素 e 插入到链式队列 LQ 中 插入成功返回 1 LQNode s s LQNode malloc sizeof LQNode 为将要入队的元素申请一个结点的空间 if s exit 1 如果申请空间失败 则退出并返回参数 1 s data e 将元素值赋值给结点的数据域 s next NULL 将结点的指针域置为空 LQ rear next s 将原来队列的队尾指针指向 p LQ rear s 将队尾指针指向 p return 1 int DeleteQueue LinkQueue LQ DataType e 删除链式队列中的队头元素 并将该元素赋值给 e 删除成功返回 1 否则返回 0 LQNode s if LQ front LQ rear 在删除元素之前 判断链式队列是否为空 return 0 else s LQ front next 使指针 p 指向队头元素的指针 e s data 将要删除的队头元素赋值给 e LQ front next s next 使头结点的指针指向指针 p 的下一个结点 if LQ rear s LQ rear LQ front 如果要删除的结点是队尾 则使队尾指针 指向队头指针 free s 释放指针 p 指向的结点 return 1 int GetHead LinkQueue LQ DataType e 取链式队列中的队头元素 并将该元素赋值给 e 取元素成功返回 1 否则返回 0 LQNode s if LQ front LQ rear 在取队头元素之前 判断链式队列是否为空 return 0 else s LQ front next 将指针 p 指向队列的第一个元素即队头元素 e s data 将队头元素赋值给 e 取出队头元素 return 1 出队操作 int DeleteQueue LinkQueue Q DataType x 将队列 Q 的队头元素出队 并存放到 x 所指的存储空间中 LQNode p if Q front Q rear return 0 p Q front next Q front next p next 队头元素 p 出队 if Q front NULL 如果队中只有一个元素 p 则 p 出队后成为空队 Q rear Q front x p data free p 释放存储空间 return 1 void YangHuiTriangle int N 链式队列实现打印杨辉三角 int i j k n DataType e t int temp MaxSize 定义一个临时数组 用于存放每一行的元素 LinkQueue Q k 0 InitQueue 初始化链队列 EnterQueue 第一行元素入队 产生第中间 n 2 行的元素 for n 2 n N n 产生第 i 行元素并入队 同时将第 i 1 行的元素保存 在临时数组中 k 0 EnterQueue 第 i 行的第一个元素入队 for i 1 i n 2 i 利用队列中第 i 1 行元素产生第 i 行的中间 i 2 个元 素并入队列 DeleteQueue temp k t 将第 i 1 行的元素存入临时数组 GetHead Q 取队头元素 t t e 利用队中第 i 1 行元素产生第 i 行元素 EnterQueue DeleteQueue temp k t 将第 i 1 行的最后一个元素存入临时数组 PrintArray temp k N EnterQueue 第 i 行的最后一个元素入队 k 0 将最后一行元素存入数组之前 要将下标 k 置为 0 while QueueEmpty Q 将最后一行元素存入临时数组 DeleteQueue temp k t if QueueEmpty Q PrintArray temp k N void main int n printf 请输入要打印的行数 n scanf d YangHuiTriangle n void PrintArray int a int n int N 打印数组中的元素 使能够呈正确的形式输出 int i static count 0 记录输出的行 for i 0 i N count i 打印空格 printf count for i 0 i n i 打印数组中的元素 printf 6d a i printf n 用栈实现迷宫问题求解用栈实现迷宫问题求解 include include define OVERFLOW 1 define MAX 100 typedef struct int x int y int d Data typedef struct int pos Data data MAX SNode Stack Stack InitStack Stack pStack pStack Stack malloc sizeof SNode if pStack exit OVERFLOW pStack pos 1 return pStack int IsEmpty Stack pstack return pstack pos 1 void Push Stack pStack Data x if pStack pos MAX 1 exit OVERFLOW else pStack pos pStack data pStack pos x void Pop Stack pStack if pStack pos 1 exit OVERFLOW else pStack pos Data GetTop Stack pStack return pStack data pStack pos Data SetStackElem int x int y int d Data element element x x element y y element d 0 return element void DisplayPath Stack pStack Data element printf The path is n while IsEmpty pStack element GetTop pStack Pop pStack printf The node is d d n element x element y void MazePath int maze 8 11 int direction 4 2 int x1 int y1 int x2 int y2 int i j k g h Stack pStack Data element pStack InitStack maze x1 y1 2 Push pStack SetStackElem x1 y1 0 while IsEmpty pStack element GetTop pStack Pop pStack i element x j element y k element d while k 3 g i direction k 0 h j direction k 1 if g x2 Push pStack SetStackElem x2 y2 k DisplayPath pStack return if maze g h 0 maze g h 2 Push pStack SetStackElem i j k 1 i g j h k 0 else k printf The path has not been found n void main int direction 4 2 0 1 1 0 0 1 1 0 int maze 8 11 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 1 0 0 1 1 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 1 1 1 0 0 1 0 1 1 0 0 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 int i j printf The maze is n for i 0 i 8 i for j 0 j 11 j printf 2d maze i j printf n MazePath maze direction 1 1 6 9 用队列实现迷宫问题求解用队列实现迷宫问题求解 include define r 64 define m2 8 define n2 10 int m m2 2 n n2 2 typedef struct int x y 行列坐标 int pre sqtype sqtype sq r struct moved int x y 坐标增量 取值 1 0 1 move 8 int maze m2 n2 int PATH int maze n2 找迷宫 maze 的路径 int i j k v front rear x y int mark m2 n2 for i 0 i m2 i for j 0 j n2 j mark i j 0 printf Please Input move array n for i 0 i 8 i scanf d d sq 1 x 1 sq 1 y 1 sq 1 pre 0 front 1 rear 1 mark 1 1 1 标记入口以到达过 while front rear x sq front x y sq front y x y 为出发点 for v 0 v 8 v 搜索 x y 的 8 个相邻 i j 是否可以到达 i x move v x j y move v y if maze i j 0 sq rear pre front mark i j 1 标记 i j 已经到达过 if i m k rear do printf d d sq k x sq k y k sq k pre 找前一点 while k 0 k 0 是已经到达 for i 1 i 19 i printf 3d i printf n for i 1 i 19 i printf 3d sq i x printf n for i 1 i 19 i printf 3d sq i y printf n for i 1 i 19 i printf 3d sq i pre printf n return 1 成功返回 front 出队 front 指向新的出发点 队空 循环结束 printf There is no path n return 0 迷宫没有路径返回 main int i j for i 0 i 10 i maze 0 i 1 maze 7 i 1 for i 0 i 8 i maze i 0 1 maze i 9 1 for i 1 i 7 i for j 1 j 9 j printf d d i j scanf d maze 1 1 0 maze 1 2 1 maze 1 3 0 maze 1 4 1 maze 1 5 1 maze 1 6 0 maze 1 7 1 maze 1 8 1 maze 2 1 1 maze 2 2 0 maze 2 3 0 maze 2 4 1 maze 2 5 1 maze 2 6 0 maze 2 7 1 maze 2 8 0 maze 3 1 0 maze 3 2 1 maze 3 3 1 maze 3 4 0 maze 3 5 0 maze 3 6 1 maze 3 7 1 maze 3 8 1 maze 4 1 1 maze 4 2 0 maze 4 3 0 maze 4 4 1 maze 4 5 1 maze 4 6 0 maze 3 7 0 maze 4 8 1 maze 5 1 1 maze 5 2 1 maze 5 3 0 maze 5 4 0 maze 5 5 1 maze 5 6 1 maze 5 7 0 maze 5 8 1 maze 6 1 0 maze 6 2 1 maze 6 3 1 maze 6 4 1 maze 6 5 0 maze 6 6 0 maze 6 7 0 maze 6 8 0 printf n for i 0 i 8 i for j 0 j 10 j printf d maze i j printf n PATH maze 分别用队列实现一个列车调度系统 分别用队列实现一个列车调度系统 实验实验 3 树的应用树的应用 一 实验目的一 实验目的 1 领会并理解二叉树的类型定义 2 熟练掌握二叉树的主要特性 3 熟练掌握二叉树的各种遍历算法 并能灵活运用遍历算法实现二叉树的其它操作 4 熟练掌握二叉树和树的各种存储结构及其建立的算法 5 了递归算法的实现过程 二 实验内容及步骤二 实验内容及步骤 1 实现二叉树的抽象数据类型 2 构造一棵二叉树并用递归实现其先序 中序 后序遍历算法并验证 3 用非递归算法实现二叉树的中序遍历 4 给出一段报文和每个字符出现的概率 对其进行哈夫曼编码和解码 三 实验步骤与调试过程三 实验步骤与调试过程 利用栈来实现 根结点进栈 之后栈非空 弹出 接着根节点的右结点进栈 之后 左节点进栈 接着 弹出栈顶元素 此结点的右结点进栈 之后左节点进栈 弹出栈顶元素 直到栈为空 从根节点开始 循环 只要有左子节点则进栈 直到左子节点为空 接着弹出栈顶输 出 判断该结点是否有右子节点 若有则进栈 若没有继续弹栈 有右子节点的情况 判 断该节点是否有左子节点 有则进栈 直到左子节点为空 若该右子节点没有左子节点 则弹栈 判断弹出的节点 是否有右子节点 若有则进栈 没有继续弹栈 接着又要判断 刚进栈的这个节点 是否有左子节点 有则进栈 没有则继续弹栈 从根结点开始 只要左子节点非空 则进栈 直到左子节点为空为止 取出栈顶元素 判断取出的栈顶元素是否有右子节点 或者右子节点是否被访问过 若满足条件 则输出 该结点 同时弹栈 并且记录下该访问的节点 取出的栈顶元素 若有右子节点 且未被 访问过 则指针继续移动到右子节点 四 实验结果四 实验结果 五 疑难小结五 疑难小结 用图形显示遍历能够是人更好的明白二叉树的遍历 更好的理解二叉树的链式结构的 存储 理解二叉树遍历的过程 能够针对递归结构的二叉树进行查询 修改 删除的操作 6 主要算法和程序清单主要算法和程序清单 二叉树递归实现其先序 中序 后序遍历算法并验证 二叉树递归实现其先序 中序 后序遍历算法并验证 包含头文件及宏定义 include include include typedef char DataType define MaxSize 100 定义栈的最大容量 函数的声明 void CreateBitTree2 BiTree T char str 利用括号嵌套的字符串建立二叉树的函数声明 void LevelPrint BiTree T 按层次输出二叉树的结点 void TreePrint BiTree T int nLayer 按树状打印二叉树 typedef struct Node 二叉链表存储结构类型定义 DataType data 数据域 struct Node lchild 指向左孩子结点 struct Node rchild 指向右孩子结点 BiTree BitNode void InitBitTree BiTree T 二叉树的初始化操作 T NULL void DestroyBitTree BiTree T 销毁二叉树操作 if T 如果是非空二叉树 if T lchild DestroyBitTree if T rchild DestroyBitTree free T T NULL void CreateBitTree BiTree T 递归创建二叉树 DataType ch scanf c if ch T NULL else T BiTree malloc sizeof BitNode 生成根结点 if T exit 1 T data ch CreateBitTree 构造左子树 CreateBitTree 构造右子树 int InsertLeftChild BiTree p BiTree c 二叉树的左插入操作 if p 如果指针 p 不空 c rchild p lchild p 的原来的左子树成为 c 的右子树 p lchild c 子树 c 作为 p 的左子树 return 1 return 0 int InsertRightChild BiTree p BiTree c 二叉树的右插入操作 if p 如果指针 p 不空 c rchild p rchild p 的原来的右子树作为 c 的右子树 p rchild c 子树 c 作为 p 的右子树 return 1 return 0 BiTree Point BiTree T DataType e 查找元素值为 e 的结点的指针 BiTree Q MaxSize 定义一个队列 用于存放二叉树中结点的指针 int front 0 rear 0 初始化队列 BitNode p if T 如果二叉树非空 Q rear T rear while front rear 如果队列非空 p Q front 取出队头指针 front 将队头指针出队 if p data e return p if p lchild 如果左孩子结点存在 将左孩子指针入队 Q rear p lchild 左孩子结点的指针入队 rear if p rchild 如果右孩子结点存在 将右孩子指针入队 Q rear p rchild 右孩子结点的指针入队 rear return NULL DataType LeftChild BiTree T DataType e 返回二叉树的左孩子结点元素值操作 BiTree p if T 如果二叉树不空 p Point T e p 是元素值 e 的结点的指针 if p 返回 p 的左孩子结点的元素值 return DataType RightChild BiTree T DataType e 返回二叉树的右孩子结点元素值操作 BiTree p if T 如果二叉树不空 p Point T e p 是元素值 e 的结点的指针 if p 返回 p 的右孩子结点的元素值 return int DeleteLeftChild BiTree p 二叉树的左删除操作 if p 如果 p 不空 DestroyBitTree 删除左子树 return 1 return 0 int DeleteRightChild BiTree p 二叉树的左删除操作 if p 如果 p 不空 DestroyBitTree 删除右子树 return 1 return 0 void main BiTree T root printf 根据括号嵌套 a b c d e f g h i 建立二叉树 n CreateBitTree2 printf 按层次输出二叉树的序列 n LevelPrint T printf n printf 按树状打印二叉树 n TreePrint T 1 printf 根据括号嵌套 A B D H E I C F G 建立二叉树 n CreateBitTree2 printf 按层次输出二叉树的序列 n LevelPrint root printf n printf 按树状打印二叉树 n TreePrint root 1 DestroyBitTree DestroyBitTree void LevelPrint BiTree T 按层次打印二叉树中的结点 BiTree queue MaxSize 定义一个队列 用于存放结点的指针 BitNode p int front rear 定义队列的队头指针和队尾指针 front rear 1 队列初始化为空 rear 队尾指针加 1 queue rear T 将根结点指针入队 while front rear 如果队列不为空 front front 1 MaxSize p queue front 取出队头元素 printf c p data 输出根结点 if p lchild NULL 如果左孩子不为空 将左孩子结 点指针入队 rear rear 1 MaxSize queue rear p lchild if p rchild NULL 如果右孩子不为空 将右孩子结 点指针入队 rear rear 1 MaxSize queue rear p rchild void TreePrint BiTree T int level 按树状打印的二叉树 int i if T NULL 如果指针为空 返回上一层 return TreePrint T rchild level 1 打印右子树 并将层次加 1 for i 0 idata 输出根结点 TreePrint T lchild level 1 打印左子树 并将层次加 1 void CreateBitTree2 BiTree T char str 利用括号嵌套的字符串建立二叉链表 char ch BiTree stack MaxSize