2015年数据结构总0820(上交)实验一线性表的链式存储结构.pdf

《2015年数据结构总0820(上交)实验一线性表的链式存储结构.pdf》由会员分享，可在线阅读，更多相关《2015年数据结构总0820(上交)实验一线性表的链式存储结构.pdf（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实 验 一 线 性 表 的 链 式 存 储 结 构 一、实 验 目 的：1.掌 握 线 性 表 的 链 式 存 储 结 构。2.熟 练 地 利 用 链 式 存 储 结 构 实 现 线 性 表 的 基 本 操 作。3.能 熟 练 地 掌 握 链 式 存 储 结 构 中 算 法 的 实 现。二、实 验 内 容：1.用 头 插 法 或 尾 插 法 建 立 带 头 结 点 的 单 链 表。2.实 现 单 链 表 上 的 插 入、删 除、查 找、修 改、计 数、输 出 等 基 本 操 作。三、实 验 要 求：I.根 据 实 验 内 容 编 写 程 序，上 机 调 试、得 出 正 确 的 运 行 程 序。

2、2.写 出 实 验 报 告（包 括 源 程 序 和 运 行 结 果）。四、实 验 学 时：2 学 时 五、实 验 步 骤：1.进 入 编 程 环 境，建 立 一 新 文 件；2.参 考 以 下 相 关 内 容，编 写 程 序，观 察 并 分 析 输 出 结 果。定 义 单 链 表 的 数 据 类 型，然 后 将 头 插 法 和 尾 插 法、插 入、删 除、查 找、修 改、计 数、输 出 等 基 本 操 作 都 定 义 成 子 函 数 的 形 式，最 后 在 主 函 数 中 调 用 它，并 将 每 一 种 操 作 前 后 的 结 果 输 出，以 查 看 每 一 种 操 作 的 效 果。部 分 参

3、 考 程 序 单 链 表 的 建 立（头 插 法），插 入，删 除，查 找、修 改、计 数、输 出#i n c 1 ude#define elemtype intstruct link elemtype data；元 素 类 型 link*next；指 针 类 型，存 放 下 一 个 元 素 地 址）；头 插 法 建 立 带 头 结 点 的 单 链 表 link*hcreat（）link s,p;elemtype i;coutnext=NULL；while（i）当 输 入 的 数 据 不 为 0 时;循 环 建 单 链 表 s=new link；s-data=i；s-next=p-next；p

4、-next=s；c in i；return p；输 出 单 链 表 void print(1 ink*head)(link*p；p=head-next；while(p-next!=NULL)(c o u t p-d ata-”；输 出 表 中 非 最 后 一 个 元 素 p=p-next；)coutp-data；输 出 表 中 最 后 一 个 元 素 coutendl；I 在 单 链 表 head中 查 找 值 为 x 的 结 点 Link*Locate(link*head,elemtype x)(Link*p；p=head-next；while(p!=NULL)&(p-data!=x)p=p

5、-next；return p；在 head为 头 指 针 的 单 链 表 中，删 除 值 为 x 的 结 点 void deletel(link*head,elemtype x)(link*p,*q；q=head；p=head-next；while(p!=NULL)&(p-data!=x)(q=p；p=p-next；If(p=NULL)c o u t 要 删 除 的 结 点 不 存 在”；elseq-next=p-next；delete(p)；)在 头 指 针 head所 指 的 单 链 表 中，在 值 为 x 的 结 点 之 后 插 入 值 为 y 的 结 点 void insert(lin

6、k*head,elemtype x,elemtype y)link*p,*s；s=new link；s-data=y；if(head，next=NULL)链 表 为 空(head-next=s；s-next=NULL：)p=Locate(head,x)；调 用 查 找 算 法 if(p=NULL)c o u tv插 入 位 置 非 法”：else(s-next=p-next；p-next=s；)将 单 链 表 p 中 所 有 值 为 x 的 元 素 修 改 成 yvoid change(link*p,elemtype x,elemtype y)(link*q；q=p-next；while(q!

7、=NULL)if(q-data=x)q-data=y；q=q-next；)void count(link*h)统 计 单 链 表 中 结 点 个 数(link*p；int n=0；p=h-next；while(p!=NULL)n+；p=p-next；return n;)void main()int n；elemtype x,y；link*p,*q；p=hcreat()；头 插 法 建 立 链 表 print(p)；输 出 刚 建 立 的 单 链 表c o u t 请 输 入 要 删 除 的 元 素”；c in y；deletel(p,y)；print(p)；输 出 删 除 后 的 结 果 co

8、utvv”请 输 入 插 入 位 置 的 元 素 值(将 待 插 元 素 插 入 到 它 的 后 面)”;c in x；coutvv”请 输 入 待 插 元 素 值&c in y；insert(p,x,y)；print(p)；输 出 插 入 后 的 结 果 coutcv”请 输 入 要 修 改 前、后 的 元 素 值”；c i n x y；change(p,x,y)；print(p)；c o u t 请 输 入 要 查 找 的 元 素 值”；c in x；q=Locate(p,x)；if(q=NULL)coutvvxv”不 在 表 中,找 不 到!”vendl：else coutvvxvv”在

9、 表 中,己 找 到!”vendl；n=count(p)；c o u t 链 表 中 结 点 个 数 为：n e n d l：)单 链 表 的 建 立(尾 插 法)、插 入、删 除、查 找、修 改、计 数、输 出#include#define elemtype intstruct link elemtype data；元 素 类 型 link*next；指 针 类 型，存 放 下-个 元 素 地 址)；尾 插 法 建 立 带 头 结 点 的 单 链 表 link*rcreat()link*s,*p,*r；elemtype i；coutnext=NULL；while(i)s=new link；s

10、-data=i；r-next=s；r=s；c in i；r-next=NULL；return p；输 出 单 链 表 void print(link*head)link*p；p=head-next；while(p-next!=NULL)(coutvvp-datavv”-”；输 出 表 中 非 最 后 一 个 元 素 p=p-next；)coutp-data；输 出 表 中 最 后 一 个 元 素 coutendl；)link*Locate(1 ink*head,int x)在 单 链 表 中 查 找 第 x 个 结 点 link*p；p=head：int j=0；while(p!=NULL)&

11、(jnext;j+；return p；void delete 1(link*head,elemtype x)在 head为 头 指 针 的 单 链 表 中，删 除 值 为 x 的 结 点(link*p,*q；q=head；p=head-next；while(p!=NULL)&(p-data!=x)(q=p；p=p-next；)if(p=NULL)coutnext=p-next；delete(p)；void insert(link*head,int x,elemtype y)在 头 指 针 head所 指 单 链 表 中，在 第 x 个 结 点 之 后 插 入 值 为 y 的 结 点 link*

12、p,*s；s=new link；s-data=y；if(head-next=NULL)链 表 为 空(head-next=s；s-next=NULL：p=Locate(head,x)；调 用 查 找 算 法 if(p=NULL)c o u t 插 入 位 置 非 法”；elses-next=p-next；p-next=s；)void change(link*p,elemtype x,elemtype y)将 单 链 表 P 中 所 有 值 为 X的 元 素 改 成 值 为 ylink*q；q=p-next；while(q!=NULL)if(q-data=x)q-data=y；q=q-next；

13、)void count(link*h)统 计 单 链 表 中 结 点 个 数(link*p；int n=0；p=h-next；while(p!=NULL)n+；p=p-next；return n;void main()int n;link p,q;p=rcreat()；尾 插 法 建 立 链 表 print(p)；输 出 刚 建 立 的 单 链 表 cout”请 输 入 要 删 除 的 元 素”；c in y；deletel(p,y)；print(p)；/输 出 删 除 后 的 结 果 c o u t”请 输 入 插 入 位 置”；c in x；coutvv”请 输 入 待 插 元 素 值”；

14、c in y；insert(p,x,y)；print(p)；输 出 插 入 后 的 结 果 c o u tv请 输 入 修 改 前、后 的 元 素 值”；c i n x y；change(p,x,y)；print(p)；c o u t 请 输 入 要 查 找 的 元 素 值”；c in x；q=Locate(p,x)；if(q=N U L L)coutxw 不 在 表 中，找 不 到!e n d l；else c o u t x v 在 表 中，已 找 到!”e n d l：n=count(p)；coutv”链 表 中 结 点 个 数 为：n endl;六、选 作 实 验 试 设 计 一 元

15、多 项 式 相 加(链 式 存 储)的 加 法 运 算。A(X)=7+3X+9X8+5X9B(X)=8X+22X7-9X81.建 立 一 元 多 项 式；2.输 出 相 应 的 一 元 多 项 式；3.相 加 操 作 的 实 现。实 验 二 循 环 链 表 的 操 作 一、实 验 目 的：通 过 本 实 验 中 循 环 链 表 和 双 向 链 表 的 使 用，使 学 生 进 一 步 熟 练 掌 握 链 表 的 操 作 方 式。二、实 验 内 容：本 次 实 验 可 以 从 以 下 两 个 实 验 中 任 选 一 个：1.建 立 一 个 单 循 环 链 表 并 实 现 单 循 环 链 表 上 的

16、 逆 置。所 谓 链 表 的 逆 置 运 算(或 称 为 逆 转 运 算)是 指 在 不 增 加 新 结 点 的 前 提 下，依 次 改 变 数 据 元 素 的 逻 辑 关 系，使 得 线 性 表，a2,a3，a j成 为，a?,a2,a)。2.构 建 一 个 双 向 链 表，实 现 插 入、查 找 和 删 除 操 作。三、实 验 要 求：1.根 据 实 验 内 容 编 写 程 序，上 机 调 试、得 出 正 确 的 运 行 程 序。2.写 出 实 验 报 告(包 括 源 程 序 和 运 行 结 果)。四、实 验 学 时：2 学 时 五、实 验 步 骤：1.进 入 编 程 环 境，建 立 一

17、新 文 件；2.参 考 以 下 相 关 内 容，编 写 程 序，观 察 并 分 析 输 出 结 果。建 立 一 个 带 头 结 点 的 单 循 环 链 表，从 头 到 尾 扫 描 单 链 表 L,把 p 作 为 活 动 指 针，沿 着 链 表 向 前 移 动，q 作 为 p 前 趋 结 点，r 作 为 q 的 前 趋 结 点。其 中，q 的 next值 为 r；r 的 初 值 置 为 heado 双 向 链 表 的 构 造 与 单 链 表 相 同，至 于 它 的 插 入 与 删 除 运 算 比 单 链 表 复 杂，插 入 运 算 需 要 4 步 操 作，删 除 运 算 需 要 2 步 操 作，

18、注 意 语 句 的 次 序，不 要 任 意 交 换 位 置，以 免 不 能 正 确 插 入 或 删 除 结 点。部 分 参 考 程 序 循 环 链 表 头 文 件 h l.h 的 内 容#define NULLO#include#includetypedef struct nodeint num；struct node*next；linklist；以 下 是 主 程 序 in clu d e”h l.h 输 出 循 环 链 表 的 信 息 void output(linklist*head)linklist*p；p=head-next；while(p!=head)printf(%d”,p-nu

19、m)；p=p-next；printf(“n”)；建 立 单 循 环 链 表 Linklist*creat(int n)(int k;linklist*head,*r,*p；p=(linklist*)malloc(sizeof(linklist)；head=p；r=p；p-next=p；for(k=l；knum=k；r-next=p；r=p；)p-next=head；retum(head)；)逆 置 函 数 linklist*invert(linklist*head)(Linklist*p,*q,*r；p=head-next；q=head；while(p!=head)r=q；q二 p；p=p-n

20、ext；q-next=r；)head-next=q；retum(head)；void main()int n；Linklist.head；printf(“输 入 所 建 立 的 循 环 链 表 的 结 点 个 数：n”)；scanf(d”，&n)；head=creat(n)；p rin tfC输 出 建 立 的 单 循 环 链 表：n)；output(head)；p rin tfC现 在 进 行 逆 置！n)；head=invert(head):printf(输 出 进 行 逆 置 运 算 后 的 单 循 环 链 表 的 结 点 信 息!n j；output(head)；)双 向 链 表 参

21、考 程 序 以 下 是 头 文 件 hh.h 的 内 容#include#includetypedef struct dupnodeint data；struct dupnode*next,prior；Jdulinklist；以 下 是 主 程 序 的 内 容#inckide”hh.h/create函 数 用 来 构 建 双 向 链 表 dulinklist create。dulinklist*head,*p,int i,n；head=(dulinklist*)malloc(sizeof(dulinklist)；head-next=NULL；head-prior=NULL；r=head；pri

22、ntf(“请 输 入 所 建 双 向 链 表 中 结 点 的 个 数：n”)；scanf(%d”,&n)；for(i=l；idata)；p-next=NULL；r-next=p；p-prior=r；r=r-next；return(head)；fin d函 数 用 来 实 现 在 双 向 链 表 中 按 序 号 查 找 某 个 结 点 的 功 能。void find(dulinklist*h)(int k,i；dulinklist*p；p=h；i=0：primf(输 入 要 查 找 结 点 的 序 号：n)；scanf(v%d”,&k)；while(p!=NULL)&(inext；i+：)if(

23、p)printfC所 查 到 的 结 点 的 值 为：n)；printf(w%dn”，p-data)；)elsep rin tf(没 找 到 该 结 点!n)；)/insdulist函 数 用 来 实 现 在 双 向 链 表 中 按 序 号 插 入 结 点 的 功 能 dulinklist*insdulist(dulinklist*head,int i,int x)dulinklist*p,*s；in tj；p=head；j=0；whi 1 e(p-next!=head)&(jnext；j+；)If(j=i-1)(s=(dulinklist*)malloc(sizeof(dulinklist)

24、；s-data=x；s-prior=p；s-next=p-next；p-next-prior=s；p-next=s；)elseprintf(v errorll)；return head；deledulist函 数 实 现 在 双 向 链 表 中 按 序 号 删 除 某 个 结 点 的 功 能 dulinklist*deledulist(dulinklist*head,int i)dulinklist*p；in tj；p=head；j=while(p-next!=head)&(jnext；j+;If(j=i)p-prior-next=p-next；p-next-prior=p-prior；fre

25、e(p)；)elseprintf(v error n)；return head；/output函 数 用 来 输 出 整 个 双 向 链 表 的 结 点 值 void output(dulinklist*h)(dulinklist*p；p=h-next；while(p!=NULL)printfC输 出 该 双 向 链 表 的 结 点，分 别 为：n)；printf(d n，p-data)；p=p-next；void main()dulinklist*head；int flag=l,i,k,x；while(flag)/flag作 为 判 断 循 环 的 标 志 位 printfC 1.建 立 双

26、 向 链 表 n)；printf(2.查 找 某 个 结 点 n)；printf(w 3.插 入 一 个 结 点 n)；prtntfC 4.删 除 一 个 结 点 n)；printf(w 5.退 出 n)；printf(”请 输 入 选 择：n)；scanf(d”，&i)；switch(i)case 1：head=createO：break；case 2：find(head)；break；case 3：printf(输 入 待 插 的 结 点 的 序 号 及 新 插 入 结 点 的 data值.n)；scanf(d%d，&k,&x)；head=insdulist(head,k,x)；outpu

27、t(head)；break；case 4：printf(输 入 要 删 除 的 结 点 的 序 号.n)；scanf(d,&k)；head=deledulist(head,k)；output(head)；break；case 5:flag=0；)/while循 环 结 束 此 程 序 不 论 是 插 入、查 找 还 是 删 除 运 算 均 是 按 序 号 的 方 式 来 处 理，当 然 也 可 改 为 按 结 点 的 值 来 作 相 应 的 处 理，试 修 改 以 上 程 序 实 现 按 值 操 作 的 功 能。六、选 作 实 验 利 用 单 循 环 链 表 存 储 结 构，解 决 约 瑟 夫

28、(Josephus)环 问 题。即：将 编 号 是 1,2,n(n0)的 n 个 人 按 照 顺 时 针 方 向 围 坐 一 圈，每 人 持 有 一 个 正 整 数 密 码。开 始 时 任 选 一 个 正 整 数 作 为 报 数 上 限 值 m,从 某 个 人 开 始 顺 时 针 方 向 自 1开 始 顺 序 报 数，报 到 m 时 停 止 报 数，报 m 的 人 出 列，将 他 的 密 码 作 为 新 的 m 值，从 他 在 顺 时 针 方 向 的 下 一 个 人 开 始 重 新 从 1报 数，如 此 下 去，直 到 所 有 的 人 全 部 出 列 为 止。令 n 最 大 值 取 30。设

29、计 一 个 程 序，求 出 出 列 顺 序，并 输 出 结 果。实 验 三 树 形 结 构 一、实 验 目 的：1.掌 握 二 叉 树 的 数 据 类 型 描 述 及 二 叉 树 的 特 性。2.掌 握 二 叉 树 的 链 式 存 储 结 构（二 叉 链 表）的 建 立 算 法。3.掌 握 二 叉 链 表 上 二 叉 树 的 基 本 运 算 的 实 现。二、实 验 内 容：从 以 下 1、2 和 3、4 中 各 选 择 一 项 内 容 1.用 递 归 实 现 二 叉 树 的 先 序、中 序、后 序 3 种 遍 历。2.用 非 递 归 实 现 二 叉 树 的 先 序、中 序、后 序 3 种 遍

30、历。3.实 现 二 叉 树 的 层 次 遍 历。4.将 一 棵 二 叉 树 的 所 有 左 右 子 树 进 行 交 换。三、实 验 要 求：1.根 据 实 验 内 容 编 程，上 机 调 试、得 出 正 确 的 运 行 程 序。2.写 出 实 验 报 告（包 括 源 程 序 和 运 行 结 果）。四、实 验 学 时：4 学 时 五、实 验 步 骤：1.进 入 编 程 环 境，建 立 一 新 文 件；2.参 考 以 下 相 关 内 容，编 写 程 序，观 察 并 分 析 输 出 结 果。将 建 立 二 叉 树 及 先 序、中 序、后 序 3 种 遍 历 算 法 都 写 成 子 函 数，然 后 分

31、 别 在 主 函 数 中 调 用 它，但 在 建 立 二 又 树 中，必 须 把 二 叉 树 看 成 完 全 二 叉 树 的 形 式。若 不 是 完 全 二 叉 树，则 在 输 入 数 据 时，用 虚 结 点（不 存 在）表 示（本 算 法 中，用“，”号 代 替）。用 非 递 归 法 实 现 二 叉 树 的 遍 历 非 递 归 算 法 中，必 须 设 置 堆 栈，可 以 直 接 用 一 维 数 组 来 代 替 栈，但 必 须 另 外 设 置 栈 顶 指 针。实 现 二 叉 树 的 层 次 遍 历 用 一 个 一 维 数 组 代 替 队 列，实 现 二 叉 树 的 层 次 遍 历。将 棵 二

32、叉 树 的 所 有 左 右 子 树 进 行 交 换。本 算 法 只 要 增 加 一 个 实 现 二 叉 树 左 右 子 树 交 换 的 子 函 数 即 可。为 了 便 于 查 看，在 主 函 数 将 交 换 前 后 的 三 种 遍 历 效 果，分 别 输 出。以 下 为 部 分 参 考 程 序：递 归 实 现 二 叉 树 的 3 种 遍 历#includetypedef char elemtype；struct bitree定 义 二 叉 树 数 据 类 型 elemtype data；结 点 信 息 bitree*lchild,*rchild；左 右 孩 子）；bitree*create（）

33、建 立 二 叉 链 表 bitree*root,*s,*q100；/q 为 队 列，最 大 空 间 为 100int front=l,rear=0；队 列 头、尾 指 针 char ch；root=NULL；cout”请 输 入 结 点 值(，为 虚 结 点，#结 束)：v data=ch；s-lchild=NULL；s-rchild=NULL；)rear+；qrearj=s；进 队 if(rear=l)root=s；elseif(s!=NULL)&(qfront!=NULL)if(rear%2=0)qlfront-lchild=s；else qfront-rchid=s；if(rear%2=

34、1)front+；出 队)c in c h；)return root：)void preorder(bitree*root)先 序 遍 历 bitree*p；p=root；if(p!=NULL)coutp-datapreorder(p-lchild)；preorder(p-rchild)；)void inorderl(bitree*root)中 序 遍 历 bitree*p；p=root；if(p!=NULL)(inorder(p-lchild)；co u t p-d a ta”;inorder(p-rchild)；)void postorder(bitree*root)后 序 遍 历 bit

35、ree*p；p=root；if(p!=NULL)(postorder(p-lchild)；postorder(p-rchild)；co u t p-d a ta“；)void main()bitree*root；root=create()；建 立 二 叉 链 表 coutvv”先 序 遍 历 的 结 果 0)while(p!=NULL)co u t p-d atas+top=p；进 栈 p=p-lchild；)p=stop-；/退 栈 p=p-rchild；)void inorderl(bitree*root)中 序 遍 历 bitree*p,*s100；int top=0；p=root；wh

36、ile(p!=NULL)Il(topO)while(p!=NULL)s+top=p；p=p-lchild；p=stop-；c o u t p-d ata”p=prchild；void postorderl(bi tree*root)后 序 遍 历(bitree*p*sl100；int s2100J,top=0,b；p=root；dowhile(p!=NULL)s I topj=p；s2top+=0；p=p-lchild；)if(top0)(b=s2-top；p=sltopj；if(b=O)sltop=p；s2ltop+=l；p=p-rchild；elseco u t p-d a ta;p=NU

37、LL；)while(top0)；建 立 二 叉 链 表 参 考 前 述 程 序 按 照 层 次 遍 历 二 叉 链 表#includetypedef char elemtype；struct bitree（elemtype data；结 点 信 息 bitree*lchild,*rchild；左 右 孩 子）；/按 层 次 遍 历 二 叉 树（建 立 二 叉 链 表 同 前）void lorder（bitree*t）bitree q100,*p；q 代 表 队 列 intf,r;/f,r 类 似 于 队 列 头、尾 指 针 ql=t；f=r=l；coutv”按 层 次 遍 历 二 叉 树 的

38、结 果 为：”；while if d a t a;if(P-lchild!=NULL)r+；qr=p-lchild；入 队 if p-rchild!=NULLl.r+；qr=prchild;入 队)coutendl；)void main()bitree*t；t=createO；建 立 二 叉 链 表 lorder(t)；/：按 层 次 遍 历 二 叉 树 将 二 叉 树 的 左 右 子 树 进 行 交 换 void leftOright(bitree*r)bitree*root=r;if(root!=NULL)leftOright(root-lchild);leftOright(root-rc

39、hild);bi tree*t=root-lchild;root-lchild=root-rchild;root-rchild=t;)主 函 数 void main()bitree root；root=create()；建 立 二 叉 链 表 c o u t en d l en d l 左 右 子 树 交 换 前 的 遍 历 结 果 e n d l；c o u tn先 序 遍 历 的 结 果 vvendl；preorder(root)；coutendl；coutvv”中 序 遍 历 的 结 果 e n d l；inorder(root)；coutendl：c o u t 后 序 遍 历 的 结

40、 果 e n d l；postorder(root)；coutendl；)leftTOright(root)；coutendlendl v左 右 子 树 交 换 后 的 遍 历 结 果 vvendl；c o u tv先 序 遍 历 的 结 果 e n d l；preorder(root)；coutendl；c o u t,中 序 遍 历 的 结 果 e n d l；inorder(root)；coutendl；coutcv”后 序 遍 历 的 结 果”vvendl；postorder(root)；coutendl；六、选 作 实 验 1.给 定 权 值 5,29,7,8,14,23,3,11,

41、建 立 哈 夫 曼 树，输 出 哈 夫 曼 编 码。2.对 上 述 给 定 的 哈 夫 曼 树 及 得 到 的 哈 夫 曼 编 码，试 输 入 一 串 二 进 制 编 码，输 出 它 的 哈 夫 曼 译 码。算 法 提 示：将 建 立 哈 夫 曼 树、实 现 哈 夫 曼 编、哈 夫 曼 译 码 都 定 义 成 子 函 数 的 形 式，然 后 在 主 函 数 调 用 它 们。建 立 哈 夫 曼 树 时，将 哈 夫 曼 树 的 结 构 定 义 为 一 个 结 构 型 的 维 数 组，每 个 元 素 含 有 四 项：双 亲、左 孩 子、右 孩 子。给 定 的 权 值 可 以 从 键 盘 输 入，要

42、输 出 所 建 立 的 哈 夫 曼 树，只 要 输 出 哈 夫 曼 树 的 维 数 组 中 全 部 元 素 即 可。要 实 现 哈 夫 曼 编 码，只 要 在 所 建 立 的 哈 夫 曼 树 上 进 行 二 进 制 编 码：往 左 走，编 码 为 0,往 右 走，编 码 为 1，然 后 将 从 根 结 点 到 树 叶 中 所 有 0、1排 列 起 来，则 得 到 该 树 叶 的 哈 夫 曼 编 码。哈 夫 曼 编 码 可 以 用 一 个 结 构 型 的 一 维 数 组 保 存，每 个 元 素 包 含：编 码、编 码 的 开 始 位 置、编 码 所 对 应 的 字 符 等 3 项。哈 夫 曼 译

43、 码，就 是 将 输 入 的 编 码 还 原 成 对 应 的 字 符。实 验 四 图 的 遍 历 操 作 一、实 验 目 的：1.掌 握 图 的 含 义。2.掌 握 用 邻 接 矩 阵 和 邻 接 表 的 方 法 描 述 图 的 存 储 结 构。3.理 解 并 掌 握 深 度 优 先 遍 历 和 广 度 优 先 遍 历 的 存 储 结 构。二、实 验 内 容：从 以 下 1、2 和 3、4 中 各 选 择 一 项 内 容 1.建 立 无 向 图 的 邻 接 矩 阵，并 实 现 插 入、删 除 边 的 功 能。2.建 立 有 向 图 的 邻 接 表，并 实 现 插 入、删 除 边 的 功 能。3

44、.建 立 一 个 包 含 6 个 结 点 的 图，并 实 现 该 图 的 深 度 优 先 搜 索 遍 历。4.建 立 一 个 包 含 6 个 结 点 的 图，并 实 现 该 图 的 广 度 优 先 搜 索 遍 历。三、实 验 要 求：1.根 据 实 验 内 容 编 程，上 机 调 试、得 出 正 确 的 运 行 程 序。2.写 出 实 验 报 告(包 括 源 程 序 和 运 行 结 果)。四、实 验 学 时：4 学 时 五、实 验 步 骤：1.进 入 编 程 环 境，建 立 一 新 文 件；2.参 考 以 下 相 关 内 容，编 写 程 序，观 察 并 分 析 输 出 结 果。内 容 1 的

45、知 识 要 点：图 由 一 个 非 空 的 顶 点 的 集 合 和 个 描 述 顶 点 之 间 关 系(边)的 集 合 组 成。它 可 以 定 义 为 G=(V,E)。其 中，G 表 示 一 个 图，V 是 图 G 中 顶 点 的 集 合，E 是 图 G 中 边 的 集 合。图 是 种 复 杂 的 数 据 结 构。对 于 实 际 问 题，需 要 根 据 具 体 图 的 结 构 特 点 以 及 所 要 实 施 的 操 作，选 择 建 立 合 适 的 存 储 结 构。图 的 存 储 结 构 包 括 邻 接 矩 阵 和 邻 接 表。邻 接 矩 阵:用 一 维 数 据 组 存 储 图 中 顶 点 的

46、信 息,用 矩 阵 表 示 图 中 各 顶 点 之 间 的 相 邻 关 系。它 属 于 静 态 存 储 方 法。邻 接 表：邻 接 表 存 储 方 法 是 一 种 顺 序 存 储 与 链 式 存 储 相 结 合 的 存 储 方 法。顺 序 存 储 部 分 用 来 保 存 图 中 顶 点 的 信 息，链 式 存 储 部 分 用 来 保 存 图 中 边 的 信 息。邻 接 矩 阵 的 存 储 结 构 typedef structint vertex；node；typedef structint adj；arc；typedef structnode nodemaxnode；arc arcsmaxno

47、demaxnode；graph；实 现 插 入、删 除 边 的 操 作 void ins_arc(graph int v,int w)g-arcsv w.adj=l；return；void del_arc(graph*g,int v,int w)g-arcfvw.adj=O；return;)内 容 1参 考 程 序#define maxnode 40#define null 0#includetypedef struct st_arcint adj vex；int weight；struct st_arc*nextrac；arcnode；typedef structint vertex；str

48、uct st_arc*firstarc；vemode；typedef vemode adjlistmaxnode；void del_arc(vernode g,int v,int w)删 除 从 顶 点 v 到 顶 点 w 的 边 arcnode*rl,*r2；rl=gv.frrstarc；r2=rl；while(rl!=null&r 1-adj vex!=w)r2=rl;rl=rl-nextarc；)if(rl=null)printf(no edge v-w.n)；return；)elseif(rl=r2)当 只 有 一 个 边 结 点 时 gf v.firstarc=r 1-nextarc

49、；elser2-nextarc=r 1-nextarc；有 多 个 边 结 点 时 rl=gw.firstarc；r2=rl；while(rl!=null&rl-adjvex!=v)/在 以 v 为 头 结 点 的 链 表 中，删 除 相 应 的 边 结 点r2=rl；rl=rl-nextarc；)if(rl=null)printf(n noedgev-w.)；return；)elseif(rl=r2)gw,firstarc=rl-nextarc；elser2-nextarc=r 1-nextarc；)void print(vernode g,int n)打 印 图 中 各 结 点 的 结 构

50、 arc node*q；int i；printf(adjacency list of the graph：n)；for(i=0；iadjvex)；printf(%dt”,q-weight)；q=q-nextarc；)printf(“W”)；)main()int i,j,n,k,w,v；arcnode*p,*q；adjlist g；printf(v Input node：)；输 入 图 中 顶 点 个 数 scanf(%d”,&n)；for(k=0；kn；k+)输 入 边 值 和 权 值 printf(v node%d=,k)；scanf(%d”,&gk.vertex)；gk.firstarc=