数据结构实验报告

院 系 计算机科学学院 专 业 网络工程 年 级 2012 课程名称 数据结构 学 号 姓 名 黄勇 指导教师 吴立锋 2014 年 6 月日 年级 2012 学号 专业网络工程 班号 1201组号 姓名黄勇黄勇 实验 名称 第二章 线性表实验室 实 验 目 的 或 要 求 了解线性表的逻辑结构和各种存储表示方法 以及定义在逻辑结构上的各种基本 运算及其在某种存储结构上如何实现这些基本运算 在熟悉上述内容的基础上 能够 针对具体应用问题的要求和性质 选择合适的存储结构设计出相应的有效算法 解决 与线性表相关的实际问题 实 验 原 理 算 法 流 程 1 实验内容 单链表的各种基本操作 包括创建 查找 插入 删除 输出 合并等 2 存储结构描述及说明 链式存储结构 typedef struct node char data struct node next linklist 3 函数说明 linklist rcrect linklist head 尾插法建立单链表 void print linklist head 输出函数 输出单链表 linklist location linklist head 按序号查找函数 按序号查找单链表中数据 linklist inset linklist head 插入函数 在单链表中插入数据 linklist delet linklist head 删除函数 删除单链表中的数据 int main 主函数 程序运行调用各子函数 4 模块之间的调用关系 开 始 主函数 创建单链表 查找单链表数据删除数据 输出函数 插入函数 程序清单 include include include typedef struct node 定义节点类型 char data struct node next 因为上面结构体的类型名是 struct node linklist 是别名 linklist 一般 List 顺序表 linklist 链表 int main int a linklist head head linklist malloc sizeof linklist printf 请先建立单链表 n linklist rcrect linklist head 调用尾插法 rcrect head linklist hcrect 或者调用 头插法 hcrect for printf n 您想要对此单链表表做何种操作 n0 退出 t1 查找 t2 插入 t3 删除 n scanf d if a3 printf 您输入的数字有误 请重新输入 n if a 0 退出 exit 0 if a 1 linklist location linklist head 调用按序号查找函数 location head if a 2 linklist inset linklist head 调用插入函数 inset head if a 3 调用删除函数 linklist delet linklist head 调用删除函数 delet head return 0 1 尾插法建立单链表 linklist rcrect linklist head 尾插法 链接到已经建立好的单链表的末尾 linklist p last char ch 用于输入字符 last head printf 请输入你要存储的字符 以 号结束 n while ch p linklist malloc sizeof linklist scanf c p data ch 每次都申请一个节点 数据域存放数据 指针域为空 printf c t p data 可以用来测试存储是否正确 last next p last p 上一次的最后一个元素的地址赋给 last p next NULL void print linklist head 调用输出函数 print head return head 2 输出函数函数 void print linklist head linklist p p head next printf n 你存储的数据为 n while p NULL printf c t p data p p next 3 按序号查找函数 linklist location linklist head linklist p int i k 0 p head printf n 请输入你要查找链表中第几个元素 n scanf d while p k if k i p printf 输入的序号有误 查找失败 n exit 0 else printf 第 d 个元素的值为 c n i p data return head 4 插入函数 linklist inset linklist head linklist p p1 int i k 0 char ch p head 不能为 head next printf 请输入你要在链表的第几个位置 t 插入什么元素 n scanf d c p1 linklist malloc sizeof linklist 新建一个节点 p1 data ch p1 next NULL while p k if k i 1 p printf 输入的序号有误 插入失败 n exit 0 else p1 next p next p next p1 printf 插入后的新数据为 n 输出插入后的新数据 p head next while p NULL printf c t p data p p next printf n return head 5 删除函数 linklist delet linklist head linklist p p1 p2 p head int i k 0 printf 请输入你要删除第几个元素 n scanf d while p k if k i 1 p printf 输入的序号有误 删除失败 n exit 0 else p2 p next p next p2 next free p2 printf 删除后的新数据为 n 输出插入后的新数据 p head next while p NULL printf c t p data p p next printf n return head 组 内 分 工 可 选 无 实 验 结 果 分 析 及 心 得 体 会 实验结果截图 心得体会 通过本次实验对于线性表的运用更熟练了 对于单链表的建立 删除 插入 输出更加熟悉 成 绩 评 定 教师签名 年 月 日 年级 2012 学号 专业网络工程 班号1201组号 姓名 黄勇黄勇 实验 名称 第三章 栈和队列实验室 实 验 目 的 或 要 求 在掌握栈 队列 特点的基础上 懂得在什么样的情况下能够使用栈 队列 能 熟练使用栈 队列 的一种存储表示 以及在该存储结构上如何实现栈 队列 的基 本操作 在熟悉上述内容的基础上 能够针对具体应用问题的特点 选择栈 队列 设计出相应的有效算法 解决与栈 队列 相关的实际问题 实 验 原 理 算 法 流 程 1 实验内容 括号匹配的检验 合法的括号包括 和 两类 利用栈判断任意输入的一个括号 序列是否匹配对出现 若是输出 right 否则输出 error 且提示错误原因 2 存储结构描述及说明 typedef struct int base int top int stacksize SqStack 顺序存储结构 3 函数说明 int InitStack SqStack S 构造函数 构造一个空栈 S 该栈预定义大小为 STACK INIT SIZE int push SqStack S int e 插入函数 在栈 S 中插入元素 e 为新的栈顶元素 int pop SqStack S int e 删除函数 若栈不空 则删除 S 的栈顶元素 用 e 返回 其值 并返回 1 否则返回 ERROR void match char str 检测函数 对输入的表达式进行检测 括号是否匹配 匹 配则返回配对 否则返回不配对 int main 主函数 4 模块之间的调用关系 主函数 构造函数 插入函数 删除函数 检测函数 程序清单 include stdio h include conio h include stdlib h define ERROR 1 define STACK INIT SIZE 100 define STACKINCREMENT 10 typedef struct int base int top int stacksize SqStack int InitStack SqStack S S base int malloc STACK INIT SIZE sizeof int if S base printf n 磁盘不足 n getch exit ERROR S top S base S stacksize STACK INIT SIZE return 1 int push SqStack S int e if S top S base S stacksize S base int realloc S base S stacksize STACKINCREMENT sizeof int if S base printf n 磁盘不足 n getch exit ERROR S top S base S stacksize S stacksize STACKINCREMENT S top e return 1 int pop SqStack S int e if S top S base printf n 栈已满 n return ERROR e S top return 1 void match char str SqStack S char p int e InitStack p str while p if p p p push else if p p p if S top 1 1 p S top 1 2 p pop else printf n 不配对 n return p if S top S base printf n 配对 n else printf n 不配对 n int main char str 100 printf n 输入表达式 n gets str match str getch return 0 组 内 分 工 可 选 无 实 验 结 果 分 析 及 心 得 体 会 实验结果截图 心得体会 通过本次实验 对于栈的运用更加熟练 对于栈的应用有了初步认识 在以后 的学习中加深对于栈的认识 对于数据结构有了更深刻的印象 成 绩 评 定 教师签名 年 月 日 年级 2012 学号 专业网络工程 班号 1201组号 姓名 黄勇黄勇 实验 名称 第六章 树和二叉树实验室 实 验 目 的 或 要 求 了解二叉树的定义 性质 存储结构等相关知识 在熟悉这些内容的基础上掌握 二叉树在某种存储结构下遍历以及相关算法的实现及应用 能根据本章所学到的有关 知识设计出有效的算法 实 验 原 理 算 法 流 程 1 实验内容 二叉树的相关演示操作 自定义结点结构 以二叉链表为存储结构 完成以下功能 1 以先序递归放松创建一棵二叉树 2 输出二叉树的先序 中序和后序递归或非递归遍历下的结点访问次序 3 输出二叉树所有的叶子节点和叶子节点个数 4 输出二叉树的高度 5 输出二叉树的按层次遍历序列 选作 6 输出二叉树的形状 选作 2 存储结构描述及说明 二叉链表存储结构 3 函数说明 BinTree CreatBinTree void 输入先序序列 其中加入虚结点 以示空指针的位置 构造二叉树 void Preorder BinTree T 先序遍历二叉树函数 以先序递归遍历二叉树 输出先 序遍历 void Inorder BinTree T 中序遍历二叉树函数 以中序递归遍历二叉树 输出中序 遍历 void Postorder BinTree T 后序遍历二叉树函数 以后序递归遍历二叉树 输出后 序遍历 int TreeDepth BinTree T 求二叉树深度及叶子节点数函数 采用后序遍历求二叉 树的深度 结点数及叶子数并输出 void main 主函数 4 模块之间的调用关系 主函数 先序创建二 叉树函数 先序遍历函数中序遍历 函数 后序遍历二 叉树 求叶子节点 及深度函数 程序清单 include stdio h include string h include stdlib h define Max 20 结点的最大个数 typedef struct node char data struct node lchild rchild BinTNode 自定义二叉树的结点类型 typedef BinTNode BinTree 定义二叉树的指针 int NodeNum leaf NodeNum 为结点数 leaf 为叶子数 基于先序遍历算法创建二叉树 要求输入先序序列 其中加入虚结点 以示空指针的位置 BinTree CreatBinTree void BinTree T char ch if ch getchar return NULL 读入 返回空指针 else T BinTNode malloc sizeof BinTNode 生成结点 T data ch T lchild CreatBinTree 构造左子树 T rchild CreatBinTree 构造右子树 return T NLR 先序遍历 void Preorder BinTree T if T printf c T data 访问结点 Preorder T lchild 先序遍历左子树 Preorder T rchild 先序遍历右子树 LNR 中序遍历 void Inorder BinTree T if T Inorder T lchild 中序遍历左子树 printf c T data 访问结点 Inorder T rchild 中序遍历右子树 LRN 后序遍历 void Postorder BinTree T if T Postorder T lchild 后序遍历左子树 Postorder T rchild 后序遍历右子树 printf c T data 访问结点 采用后序遍历求二叉树的深度 结点数及叶子数的递归算法 int TreeDepth BinTree T int hl hr max if T hl TreeDepth T lchild 求左深度 hr TreeDepth T rchild 求右深度 max hl hr hl hr 取左右深度的最大值 NodeNum NodeNum 1 求结点数 if hl 0 若左右深度为 0 即为叶子 return max 1 else return 0 主函数 void main BinTree root int i depth printf n printf 输入二叉树的先序序列创建二叉树 用 代表空结点 输入完全二叉树的先序序列 用 代表虚结点 如 ABD CE F root CreatBinTree 创建二叉树 返回根结点 do 从菜单中选择遍历方式 输入序号 printf t 菜单 n printf t1 先序遍历 n printf t2 中序遍历 n printf t3 后序遍历 n printf t4 求树的深度及叶子节点数 n printf t0 退出 n printf t n do 从菜单中选择遍历方式 输入序号 scanf d 输入菜单序号 0 5 switch i case 1 printf 先序遍历为 Preorder root 先序遍历 break case 2 printf 中序遍历为 Inorder root 中序遍历 break case 3 printf 后序遍历为 Postorder root 后序遍历 break case 4 depth TreeDepth root 求树的深度及叶子节点数 printf 树的深度 d 树的叶子节点 d depth NodeNum break default exit 1 printf n while i 0 写不完时 可另加附页 组 内 分 工 可 选 无 实 验 结 果 分 析 及 心 得 体 会 实验结果截图 心得体会 通过本次实验对于二叉树的运用更熟练 对于二叉树的先序 中序和后序遍历 更加熟悉 成 绩 评 定 教师签名 年 月 日 年级 2012 学号 专业网络工程 班号 1201组号 姓名黄勇黄勇 实验 名称 第七章 图实验室 实 验 目 的 或 要 求 了解图的基本概念 理解几种常用的存储结构 两种遍历算法以及图的应用算法 在熟悉这些内容的基础上 重点掌握图在邻接表这种存储结构下遍历算法的实现 实 验 原 理 算 法 流 程 1 实验内容 图在采用邻接表的存储结构下的基本操作 包括图的创建 图的深度优先搜索和广 度优先搜索 2 存储结构描述及说明 邻接表存储结构 typedef struct st arc int adjvex int weight struct st arc nextarc arcnode typedef struct int vertex struct st arc firstarc vernode typedef vernode adjlist maxnode int queue maxnode 3 函数说明 void dfs adjlist g int k int visited 深度优先搜索函数 从顶点 k 出发 深 度优先搜索 void bfs adjlist g int k int visited 广度优先搜索函数 从顶点 k 出发 广 度优先搜索 void trave bfs adjlist g int n 广度优先搜索函数 void trave dfs adjlist g int n 深度优先搜索函数 4 模块之间的调用关系 主函数 创建图 广度优先 搜索 深度优先搜 索 程序清单 include iostream include stdlib h include stdio h include malloc h define maxnode 40 define null 0 define m 20 typedef struct st arc int adjvex int weight struct st arc nextarc arcnode typedef struct int vertex struct st arc firstarc vernode typedef vernode adjlist maxnode int queue maxnode void dfs adjlist g int k int visited 从顶点 k 出发 深度优先搜索 arcnode p int w visited k 1 printf d g k vertex p g k firstarc while p null w p adjvex if visited w 0 dfs g w visited p p nextarc void bfs adjlist g int k int visited 从顶点 k 出发 广度优先搜索 int front 0 rear 1 w arcnode p visited k 1 访问初始顶点 printf d k queue rear k 初始顶点入队列 while front rear 队列不为空 front front 1 m w queue front 按访问次序依次出队列 p g w firstarc while p null if visited p adjvex 0 visited p adjvex 1 printf d p adjvex rear rear 1 m queue rear p adjvex p p nextarc void trave bfs adjlist g int n int i visited maxnode 数组 visited 标志图中的顶点是否已被访问 for i 1 i n i v