计专数据结构实验指导书.pdf

《计专数据结构实验指导书.pdf》由会员分享，可在线阅读，更多相关《计专数据结构实验指导书.pdf（53页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、陕 西 理 工 学 院 重 点 课 程 数 据 结 构 实 验 指 导 书 曹 记 东 李 征 郭 天 印 编 著 计 算 机 科 学 与 技 术 系 2011年 9 月目 录 数 据 结 构 上 机 实 验 的 目 的 和 要 求.1实 验 一 线 性 表 的 插 入 和 删 除.2实 验 二 单 链 表 的 插 入 和 删 除.5实 验 三 栈.9实 验 四 栈 和 队 列.12实 验 五 二 叉 树 操 作.17实 验 六 哈 夫 曼 树 的 应 用.21实 验 七 图 的 遍 历 操 作.28实 验 八 排 序.35实 验 九 查 找.41实 验 十 哈 希 表 设 计.46 数 据

2、结 构 上 机 实 验 的 目 的 和 要 求 通 过 上 机 实 验 加 深 对 课 程 内 容 的 理 解，增 加 感 性 认 识，提 高 软 件 设 计、编 写 及 调 试 程 序 的 能 力。要 求 所 编 的 程 序 能 正 确 运 行，并 提 交 实 验 报 告。实 验 报 告 的 基 本 要 求 为：1、需 求 分 析：陈 述 程 序 设 计 的 任 务，强 调 程 序 要 做 什 么，明 确 规 定：（1）输 入 的 形 式 和 输 出 值 的 范 围；（2）输 出 的 形 式；（3）程 序 所 能 达 到 的 功 能；（4）测 试 数 据：包 括 正 确 的 输 入 输 出

3、结 果 和 错 误 的 输 入 及 输 出 结 果。2、概 要 设 计：说 明 用 到 的 数 据 结 构 定 义、主 程 序 的 流 程 及 各 程 序 模 块 之 间 的 调 用 关 系。3、详 细 设 计：提 交 带 注 释 的 源 程 序 或 者 用 伪 代 码 写 出 每 个 操 作 所 涉 及 的 算 法。4、调 试 分 析：（1）调 试 过 程 中 所 遇 到 的 问 题 及 解 决 方 法；（2）算 法 的 时 空 分 析；（3）经 验 与 体 会。5、用 户 使 用 说 明：说 明 如 何 使 用 你 的 程 序，详 细 列 出 每 一 步 操 作 步 骤。6、测 试 结 果

4、：列 出 对 于 给 定 的 输 入 所 产 生 的 输 出 结 果。若 有 可 能，测 试 随 输 入 规 模 的 增 长 所 用 算 法 的 实 际 运 行 时 间 的 变 化。实 验 一 顺 序 表 的 插 入 和 删 除 一、实 验 目 的 1、掌 握 用 Turbo C 上 机 调 试 线 性 表 的 基 本 方 法；2、掌 握 线 性 表 的 基 本 操 作，插 入、删 除、查 找，以 及 线 性 表 合 并 等 运 算 在 顺 序 存 储 结 构 和 链 接 存 储 结 构 上 的 运 算。二、实 验 内 容 线 性 表 基 本 操 作(插 入、删 除、查 找、合 并)的 实 现

5、 三、程 序 实 现：typedef Null 0；typedef int datatype；#define maxsize 1024；typedef struct datatype datamaxsize；int last；sequenlist；int insert(L,x,i)sequenlist*L；int i；int j;if(*L).last=maxsize-l)printfif“overflow)；return Null；else if(i(*L).last+l)printfferror)；return Null；)else for(j=(*L).last；j=i-l；j-)(*L

6、).data j4-l=(*L).dataj；(*L).datai-l=x；(*L).last=(*L).last+l；return(l)；int delete(L,i)sequenlist*L；int i；int j；if(i(*L).last+l)printf(error)；return Null；else forQ=i,j=(*L).last；j+)(*L).dataj-l=(*L).dataj;(*L).data-；fretum(l)；void c re atlist()sequenlist*L；int n,i,j；printf(“请 输 入 n 个 数 据 rT)；scanf(d”,

7、&n)；fbr(i=O；in；i+)printfCMata%d=,9 i)；scanf(*L).datai)；(*L).last=n-l；fprintout(L)sequenlist*L；int i；for(i=O；i(*L).last；i+)printfC4data%d=,i)；printfCt%d,(*L).datai)；m a in()sequenlist*L；char cmd；int i,t；c ls c r()；printf(i,I.插 入 n)；printffd,D 删 除 rT)；printff4q,Q退 出 n)；do docmd=getchar()；while(cmd!=6d

8、,)I I(cmd!=D)I I(cmd!=q,)I I(cm d!=Q)I I(cmd!=i)I I(cmd!=T)；switch(cmd)case 6i cr；scanf(&x)；scanfi(&i)；insert(L,x,i)；printout(L)；break；case d J D；scanfif&i)；delete(L,i)；printout L)；break；while(cmd!=q)&(cmd!=Q)；实 验 二 单 链 表 的 插 入 和 删 除 一、实 验 目 的：了 解 和 掌 握 线 性 表 的 逻 辑 结 构 和 链 式 存 储 结 构，掌 握 单 链 表 的 基 本

9、算 法 及 相 关 的 时 间 性 能 分 析。二、实 验 内 容：单 链 表 的 基 本 操 作 实 现 建 立 一 个 数 据 域 定 义 为 字 符 串 的 单 链 表，在 链 表 中 不 允 许 有 重 复 的 字 符 串；根 据 输 入 的 字 符 串，先 找 到 相 应 的 结 点，后 删 除 之。三、程 序 实 现：#include,stdio.hn#includenstring.hn#includenstdlib.hH#includenctype.hHtypedef struct nodef 定 义 结 点 char data10；结 点 的 数 据 域 为 字 符 串 str

10、uct node*next；ListNode；typedef ListNode*LinkList；LinkList CreatListRl()；ListNode*LocateNode()；结 点 的 指 针 域/自 定 义 LinkList单 链 表 类 型 函 数，用 尾 插 入 法 建 立 带 头 结 点 的 单 链 表 函 数，按 值 查 找 结 点 void DeleteList()；/函 数，删 除 指 定 值 的 结 点 void printlist()；void DeleteAll()；主 函 数/函 数，打 印 链 表 中 的 所 有 值 函 数，删 除 所 有 结 点，释 放

11、 内 存 void main()printf(H Delete node(y/n):n)；输 入“y”或 n”去 选 择 是 否 删 除 结 点 scanf(n%sn,num)；if(strcmp(num,nyn)=0|strcmp(num,Yn)=0)char*ch,*num；LinkList head；head=CreatListR 1()；用 尾 插 入 法 建 立 单 链 表，返 回 头 指 针 printlist(head)；/遍 历 链 表 输 出 其 值printf(uPlease input Delete_data:n)；scanf(%s”,ch)；输 入 要 删 除 的 字

12、符 串 DeleteList(head,ch)；printlist(head)；iDeleteAll(head)；删 除 所 有 结 点，释 放 内 存)用 尾 插 入 法 建 立 带 头 结 点 的 单 链 表 LinkList CreatListRl(void)(char*ch；LinkList head=(LinkList)malloc(sizeof(ListNode)；生 成 头 结 点 ListNode*s,*r,*pp；r=head；r-next=NULL；printf(Input#to end)；输 入#”代 表 输 入 结 束 printf(nPlease input Node

13、_data:n)；scanf(n%s,1,ch)；输 入 各 结 点 的 字 符 串 while(strcmp(ch,n#H)!=O)pp=LocateNode(head,ch)；按 值 查 找 结 点，返 回 结 点 指 针 if(pp=NULL)没 有 重 复 的 字 符 串，插 入 到 链 表 中 s=(ListNode*)malloc(sizeof(ListNode)；strcpy(s-data,ch)；r-next=s；r=s；r-next=NULL；)printf(nInput#to end”)；printf(nPlease input Node data:)；scanf(H%sn

14、,ch)；freturn head；返 回 头 指 针 f 按 值 查 找 结 点，找 到 则 返 回 该 结 点 的 位 置，否 则 返 回 NULL=ListNode*LocateNode(LinkList head,char*key)ListNode*p=head-next；从 开 始 结 点 比 较 while(strcmp(p-data,key)!=0&p)直 到 p 为 NULL 或 p-data 为 key 止 p=p-next；扫 描 下 一 个 结 点 return p；若 p=NULL则 查 找 失 败，否 则 p 指 向 找 到 的 值 为 key的 结 点)/删 除 带

15、 头 结 点 的 单 链 表 中 的 指 定 结 点 void DeleteList(LinkList head,char*key)(ListNode*p,*r,*q=head；p=LocateNode(head,key)；按 key 值 查 找 结 点 的 if(p=NULL)若 没 有 找 到 结 点，退 出 printf(nposition error1 1)；exit(0)；)while(q-next!=p)/p为 要 删 除 的 结 点，q 为 p 的 前 结 点 q=q-next；r=q-next；q-next=r-next；free(r)；释 放 结 点)打 印 链 表 void

16、 printlist(LinkList head)(ListNode*p=head-next；从 开 始 结 点 打 印 while(p)printf(n%s,H,p-data)；p=p-next；)printf(n)；)删 除 所 有 结 点，释 放 空 间 void DeleteAll(LinkList head)ListNode*p=head,*r；while(p-next)r=p-next；free(p)；p=r；)free(p)；实 验 三 栈 一、实 验 目 的：1.熟 练 掌 握 栈 的 结 构，以 及 这 种 数 据 结 构 的 特 点；2.能 够 在 两 种 存 储 结 构

17、上 实 现 栈 的 基 本 运 算，特 别 注 意 栈 满 和 栈 空 的 判 断 条 件 及 描 述 方 法；二、实 验 内 容：计 算 表 达 式 的 值 计 算 用 运 算 符 后 缀 法 表 示 的 表 达 式 的 值。后 缀 表 达 式 也 称 逆 波 兰 表 达 式，比 中 缀 表 达 式 计 算 起 来 更 方 便 简 单 些，中 缀 表 达 式 要 计 算 就 存 在 着 括 号 的 匹 配 问 题,所 以 在 计 算 表 达 式 值 时 一 般 都 是 先 转 换 成 后 缀 表 达 式，再 用 后 缀 法 计 算 表 达 式 的 值。如：表 达 式(a+b*c)/d-e用

18、后 缀 法 表 示 应 为 abc*+d/e-。只 考 虑 四 则 算 术 运 算，且 假 设 输 入 的 操 作 数 均 为 1位 十 进 制 数(0 9),并 且 输 入 的 后 缀 形 式 表 达 式 不 含 语 法 错 误。三、程 序 实 现：#include#define add 43#define subs 45#define mult 42#define div 47 运 算 符 加 号+的 A SC II码 运 算 符 减 号 的 A SC II码/运 算 符 乘 号*的 A SC II码 运 算 符 除 号/的 A SC II码#define MAXSIZE 100typed

19、ef struct int stkdataMAXSIZE；用 数 组 来 表 示 栈 空 间，定 义 长 度 为 M AXSIZE的 堆 栈 int top；/栈 顶 JSTKzone；typedef STKzone*STK；typedef enumtrue=l,false=O bool；typedef enum ok,error status；STKzone expSTKzone；STK expSTK；STK initSTK(STKzone*stack_zone)执 行 栈 初 始 化，建 栈 指 针 7S T K p；p=stack_zone；p-top=0；status push(int

20、*term,STK pstk)将 一 结 构 型 数 据 送 入 栈 中 if(pstk-top=M AX SIZE)return error；栈 满，进 栈 失 败 pstk-stkdatapstk-top=*term；(pstk-top)-H-；栈 顶 指 针 移 动 return ok；/pushbool emptySTK(STK pstk)判 断 栈 是 否 为 空 栈 retum(pstk-top=0)；)status pop(int*pdata,STK pstk)/从 栈 中 取 出 一 结 构 型 数 据 if(emptySTK(pstk)return error；(pstk-t

21、op)；退 栈*pdata=pstk-stkdatapstk-top；return ok；void synerror()printf(un表 达 式 语 法 错!”)；exit()；)int eval(char tag,int al,int a2)switch(tag)case add:return(al+a2)；case subs:retum(al-a2)；case mult:return(a 1*a2)；case div:return(al/a2)；f)main()char c；int opd 1,opd2,temp,c 1；expSTK=initSTK(&expSTKzone)；prin

22、tf(Hn后 置 表 达 式：”)；whi le(c=getchar()!=,n,)if(c=*)continue；if(c47)&(c58)判 断 是 否 是 09 的 字 符 putchar(c)；cl=c-48；把 输 入 的 字 符 型 数 字 转 换 成 数 字 if(push(&c 1,expSTK)=error)/运 算 分 量 进 栈 printsn表 达 式 太 长 n)；exit()；else if(c=add)1 1(c=subs)1 1(c=muIt)|(c=div)putchar(c)；if(pop(&opdl,expST2=eiror)将 运 算 量 1 出 栈 s

23、ynerror()；if(pop(&opd2,expSTK)=error)将 运 算 量 2 出 栈 synerror()；temp=eval(c,opd2,opd 1)；计 算 得 到 结 果 push(&temp,expSTK)；将 运 算 结 果 进 栈)else synerror()；出 现 非 法 字 符/whileif(pop(&opd 1,expSTK)=error)synerror()；if(!(emptySTK(expSTK)synerror()；printf(c-%-3dn,opd 1)；/main_end实 验 四 栈 和 队 列 一、实 验 目 的：1.掌 握 队 列

24、和 栈 的 顺 序 存 储 结 构 和 链 式 结 构，以 便 在 实 际 背 景 下 灵 活 运 用。2.掌 握 栈 和 队 列 的 特 点，即 先 进 后 出 与 先 进 先 出 的 原 则。二、实 验 内 容：停 车 场 管 理 根 据 题 目 要 求，停 车 场 只 有 一 个 大 门，因 此 可 用 一 个 栈 来 模 拟；而 当 栈 满 后,继 续 来 的 车 辆 只 能 停 在 便 道 上，根 据 便 道 停 车 的 特 点，可 知 这 可 以 用 一 个 队 列 来 模 拟，安 排 队 的 车 辆 先 离 开 便 道，进 入 停 车 场。由 于 在 停 车 场 中 间 的 车

25、辆 可 以 提 出 离 开 停 车 场，而 且 要 求 在 离 开 车 辆 到 停 车 场 大 门 之 间 的 车 辆 都 必 须 先 离 开 停 车 场，让 此 车 离 去，然 后 再 让 这 些 车 辆 依 原 来 的 次 序 进 入 停 车 场，因 此 在 一 个 栈 和 一 个 队 列 的 基 础 上，还 需 要 有 一 个 地 方 保 存 为 了 让 路 离 开 停 车 场 的 车 辆，很 显 然 这 也 应 该 用 一 个 栈 来 模 拟。因 此 本 题 中 用 到 两 个 栈 和 一 个 队 列。对 于 停 车 场 和 车 辆 规 避 所，有 车 辆 进 入 和 车 辆 离 去

26、两 个 动 作，这 就 是 栈 的 进 栈 和 出 栈 操 作，只 是 还 允 许 排 在 中 间 的 车 辆 先 离 开 停 车 场，因 此 在 栈 中 需 要 进 行 查 找。而 对 于 便 道，也 有 入 队 列 和 出 队 列 的 操 作，同 样 允 许 排 在 中 间 的 车 辆 先 离 去 队 列。这 样 基 本 动 作 只 需 利 用 栈 和 队 列 的 基 本 操 作 就 可 实 现。三、程 序 实 现：#include stdio.h#define N 5#define M 10typedef structint num；int arrtime；elemtype；typede

27、f structelemtype stackN；int top；stack；typedef struct nodeint num；struct node*next；定 义 停 车 场 长 度 定 义 栈 元 素 的 类 型 定 义 栈/定 义 队 列 节 点 类 型queneptr；typedef struct 定 义 队 列 queneptr*front,*rear；quene；void initstack(stack*s)初 始 化 栈 s-top=l；int push(stack*s,elemtype x)/数 据 元 素 X 进 入 指 针 S所 指 的 栈 if(s-top=N-l)

28、retum(O)；else s-stack-H-s-top=x；return(l)；)elemtype pop(stack*s)elemtype x；if(s-topstacks-top；s-top；return x；void initquene(quene*s)初 始 化 队 列 s-front=(queneptr*)malloc(sizeof(queneptr)；产 生 一 个 新 结 点，作 为 头 结 点 s-rear=s-front；s-front-next=NULL；s-front-num=0；头 结 点 的 NUM保 存 队 列 元 素 的 个 数 void enquene(qu

29、ene*s,int num)数 据 入 队 歹 l lqueneptr*p；p=(queneptr*)malloc(sizeof(queneptr)；p-num=num；p-next=NULL；s-rear-next=p；s-rear=p；s-front-num+；int delquene(quene*s)queneptr*p；int n；if(s-front=s-rear)return(O)；如 果 队 列 空 elsep=s-front-next；s-front-next=p-next；if(p-next=NULL)s-rear=s-front；n=p-num；free(p)；s-fron

30、t-num；return(n)；void arrive(stack*sl,quene*p,elemtype x)int f；f=push(s 1,x)；新 到 达 的 车 辆 入 停 车 栈 if(f=O)enquene(p,x.num)；如 果 停 车 场 满，就 进 入 队 列 printffthe%d car stops the%d seat of the quenenn,x.num,p-front-num)；)else printsnthe%d car stops the%d seat of the stacknH,x.num,s 1-top+1)；void leave(stack*s

31、l,stack*s2,quene*p,elemtype x)处 理 车 辆 离 去 函 数int n,f=O；elemtype y；queneptr*q；while(s 1-top-l)&(!f)y=pop(sl)；if(y.num!=x.num)n=push(s2,y)；else f=l；)if(y.num=x.num)如 果 栈 顶 元 素 不 是 要 离 开 的 车 辆，就 将 其 放 入 车 辆 规 避 所 printf(nthe money of the%d is%d yuann,y.num,(x.arrtime-y.arrtime)*M)；while(s2-top-1)y=pop(

32、s2)；f=push(sl,y)；)n=delquene(p)；if(n)在 停 车 场 中 找 到 要 离 开 的 车 辆 y.num=n；y.arrtime=x.arrtime；f=push(sl,y)；printffthe%d car stops the%d seat o f the staknH,y.num,s 1-top+1)；)else while(s2-top-l)车 辆 规 避 所 不 空，将 其 全 放 回 停 车 场 y=pop(s2)；f=push(sl,y)；q=p-front；f=0；while(f=O&q-next!=NULL)if(q-next-num!=x.nu

33、m)/如 果 便 道 上 有 车 辆，将 第 一 辆 车 放 入 停 车 场 q=q-next；else q-next=q-next-next；p-front-num-；if(q-next=NULL)p-rear=p-front；printfVthe%d car leave the quenenn,x.num)；fM;)if(a=o)在 便 道 上 没 有 找 到 要 离 开 的 车 辆，输 出 数 据 错 误 printf(nerror!the stack and the quene have no the%d carnn,x.num)；)void main()停 车 场 模 拟 管 理 程

34、 序 char ch；stack*sl,*s2；quene*p；elemtype x；int i=l；clrscr()；s 1=(stack*)malloc(sizeof(stack)；s2=(stack*)malloc(sizeof(stack)；p=(quene*)malloc(sizeof(quene)；initstack(s 1)；initstack(s2)；初 始 化 停 车 规 避 所 栈 initquene(p)；初 始 化 便 道 队 列 while(i)printffwhat do you want to do?nn)；printf(ninput(Add/Del/Exit):

35、n)；scanf(n%c,&ch)；switch(ch)casea:printfVinput the number:nH)；scanf(n%dH,&x.num)；printfl(ninput the time:n,!)；scanf(n%d,&x.arrtime)；arrive(s l,p,x)；车 辆 到 达 break；case,d,:printf(ninput the number:nH)；scanf(,!%dn,&x,num)；printffinput the time:n,!)；scanf(H%dn,&x.arrtime)；leave(s l,s2,p,x)；车 辆 离 开 break

36、；case,e,:printf(Hthe end!”)；i=0；break；default:printffinput error!-please input again:nH)；break；ch=getchar()；)实 验 五 二 叉 树 操 作 一、实 验 目 的：掌 握 二 义 树 的 定 义、性 质 及 存 储 方 式，各 种 遍 历 算 法。二、实 验 内 容：采 用 二 叉 树 链 表 作 为 存 储 结 构，完 成 二 叉 树 的 建 立，先 序、中 序 和 后 序 以 及 按 层 次 遍 历 的 操 作，求 所 有 叶 子 及 结 点 总 数 的 操 作。三、程 序 实 现：#

37、includenstdio.hH#includeustring.hn#define Max 20 结 点 的 最 大 个 数 typedef struct nodechar data；struct node*lchild,*rchild；BinTNode；自 定 义 二 叉 树 的 结 点 类 型 typedef BinTNode*BinTree；定 义 二 叉 树 的 指 针 int NodeNum,leaf；/NodeNum 为 结 点 数，leaf 为 叶 子 数 基 于 先 序 遍 历 算 法 创 建 二 叉 树 要 求 输 入 先 序 序 列，其 中 加 入 虚 结 点“#”以 示

38、空 指 针 的 位 置 BinTree CreatBinTree(void)(BinTree T；char ch；if(ch=getchar()=#)retum(NULL)；读 入#,返 回 空 指 针 elseT=(BinTNode*)malloc(sizeof(BinTNode)；生 成 结 点 T-data=ch；T-lchild=CreatBinTree()；构 造 左 子 树 T-rchild=CreatBinTree()；构 造 右 子 树 return(T)；)/D LR先 序 遍 历 void Preorder(BinTree T)if(T)printf(n%cT-data)；

39、Preorder(T-lchild)；Preorder(T-rchild)；)/L D R中 序 遍 历 void Inorder(BinTree T)(if(T)Inorder(T-lchild)；printf(n%cn,T-data)；Inorder(T-rchild)；)/L R D后 序 遍 历 void Postorder(BinTree T)(Postorder(T-lchild)；Postorder(T-rchild)；printf(n%cu,T-data)；访 问 结 点 先 序 遍 历 左 子 树 先 序 遍 历 右 子 树 中 序 遍 历 左 子 树 访 问 结 点 中 序

40、 遍 历 右 子 树/后 序 遍 历 左 子 树 后 序 遍 历 右 子 树 访 问 结 点/采 用 后 序 遍 历 求 二 叉 树 的 深 度、int TreeDepth(BinTree T)(int hl,hr,max；if(T)hl=TreeDepth(T-lchild)；hr=T reeDepth(T-rch ild)；max=hlhr?hl:hr；NodeNum=NodeNum+l；if(hl=O&hr=O)leaf=leaf4-1；结 点 数 及 叶 子 数 的 递 归 算 法 求 左 深 度 求 右 深 度 取 左 右 深 度 的 最 大 值 求 结 点 数 若 左 右 深 度

41、为 0,即 为 叶 子return(max-i-l)；else retum(O)；)/利 用“先 进 先 出”(F I F O)队 列，按 层 次 遍 历 二 叉 树 void Levelorder(BinTree T)int front=0,rear=1；BinTNode*cqMax,*p；定 义 结 点 的 指 针 数 组 cqcql=T；根 入 队 while(front!=rear)front=(front+1)%N odeN um；p=cqfront；出 队 printf(n%cn,p-data)；出 队，输 出 结 点 的 值 if(p-lchild!=NULL)rear=(rea

42、r+l)%NodeNum；cqrear=p-lchild；左 子 树 入 队)if(p-rchild!=NULL)rear=(rear+l)%NodeNum；cqrear=p-rchild；右 子 树 入 队 主 函 数 void main()BinTree root；int i,depth；printf(,!nH)；printf(nCreat Bin Tree；Input preorder:H)；输 入 完 全 二 叉 树 的 先 序 序 列，root=CreatBinTree()；do 用#代 表 虚 结 点，如 ABD#CE#F#创 建 二 叉 树，返 回 根 结 点 从 菜 单 中 选

43、 择 遍 历 方 式，输 入 序 号。printf(”t*select*W).printf(ntl:Preorder Traversalnn)；printf(%2:lorder Traversalnn)；printf(nt3:Postorder traversalnH)；printf(nt4:PostTreeDepth,Node number,Leaf numbernu)；printf(nt5:Level Depthnu)；按 层 次 遍 历 之 前，先 选 择 4,求 出 该 树 的 结 点 数。printfftO:Exitnn)；printf(t*n).scanf(%d,&i)；switc

44、h(i)输 入 菜 单 序 号（0-5）case 1:printf(nPrint Bin tree Preorder:)；Preorder(root)；先 序 遍 历 break；case 2:printffPrint Bin Tree Inorder:)；Inorder(root)；中 序 遍 历 break；case 3:printf(HPrint Bin Tree Postorder:)；Postorder(root)；后 序 遍 历 break；case 4:depth=TreeDepth(root)；求 树 的 深 度 及 叶 子 数 printf(uBinTree Depth=%d

45、 BinTree Node number=%dM,depth,NodeNum)；printf(n BinTree Leaf number=%dn,leaf)；break；case 5:printfl(nLevePrint Bin Tree:)；Levelorder(root)；按 层 次 遍 历 break；default:exit(l)；printf(nnn)；while(i!=0)；实 验 六 哈 夫 曼 树 的 应 用 一、实 验 目 的：掌 握 哈 夫 曼 树 的 定 义、性 质 及 存 储 方 式，以 及 哈 夫 曼 树 的 编 码 方 法。二、实 验 内 容：构 造 一 颗 哈 夫

46、 曼 树，并 对 其 进 行 编 码，测 试，演 示 输 出。三、程 序 实 现#include#include#include#includea#include#define MAXVALUE 200#define MAXBIT 30#define MAXNODE 30struct haffhodechar data；int weight；int flag；int parent；int leftchild；int rightchild；/权 值 的 最 大 值 最 大 的 编 码 位 数/初 始 的 最 大 的 结 点 数 双 亲 结 点 的 下 标 左 孩 子 下 标 右 孩 子 下 标)

47、;struct haffcodeint bitMAXNODE；int start；编 码 的 起 始 下 标 char data；int weight；字 符 权 值；函 数 说 明 void pprintf(struct haffcode haffcode,int n)；/输 出 函 数 void haffrnantree(int weight,int n,struct haffhode hafftree口,char data)；建 立 哈 夫 曼 树void haffmancode(struct haffhode hafftree,int n,struct haffcode haffcod

48、e)；求 哈 夫 曼 编 码 void test(struct haffcode haffcode,int n)；测 试 函 数 void end()；结 束 界 面 函 数 void haffmantree(int weight,int n,struct haflfhode hafftree,char data)建 立 叶 结 点 个 数 为 n,权 值 数 组 为 weight口 的 哈 夫 曼 树 int i,j,ml,m2,xl,x2；哈 夫 曼 树 hafftree初 始 化，n 个 叶 结 点 共 有 2 n-l个 结 点 fdr(i=0；i2*n-l；i+)if(in)hafft

49、reei.data=datai；hafftreei.weight=weighti；叶 结 点 else hafftree i.weight=0；非 叶 结 点 hafftreei.data-0*；hafftreei.parent=O；初 始 化 没 有 双 亲 结 点 hafftreei.flag=O；hafftreei.leftchild=-l；hafftreei.rightchild=l；for(i=0；in-l；i+)构 造 哈 夫 曼 树 n-1个 非 叶 结 点 ml=m2=M AX VALUE；xl=x2=0；for(j=0；j n+i；j+)if(hafftreej.weight

50、ml&hafftreej.flag=O)m2=ml；x2=xl；m 1=haffiree j.weight；x l f)else if(hafftreej.weightm2&hafftreej.flag=0)m2=hafftreej.weight；x2=j；hafftreefx l.parent=n+i；hafftreex2.parent=n+i；hafftree xl.flag=1；hafftreex2.flag=l；hafftreen+i.weight=hafftreexl.weight+hafftreex2.weight；hafftreen+i.leftchild=xl；hafftree