数据结构实验教案(76页全).ppt

数据结构实验教案 指导教师 李辉 数据结构实验教学课件 实验简介 本课程是结合理论课程 数据结构 安排的实践课程 目的是通过本课程的实践与操作 加深理论课程中数据结构与算法的理解 理论与实践密切结合 相辅相成 实验着眼于原理与应用的结合 使学生学会如何把书上学到的知识用于解决实际问题 培养软件工作所需要的动手能力 另一方面 能使书上的知识变 活 起到深化理解和灵活掌握教学内容的目的 数据结构实验教学课件 实验环境 硬件环境 微型计算机 软件环境 windows操作系统 VisualC 6 0或VisualStudio 数据结构实验教学课件 实验教材 数据结构实验与实训教程 刘勇等国防工业出版社 数据结构实验教学课件 实验一 线性结构基本算法的实现 实验目的 1 掌握线性表的顺序存储结构的定义及C语言实现 掌握顺序表中的各种基本操作 顺序表的建立 插入 删除等 2 掌握线性表的链式存储结构 单链表的定义及C语言实现 掌握单链表中的各种基本操作 单链表的建立 合并 删除重复值等 数据结构实验教学课件 实验内容 一 实验1主要实现创建一个顺序表 建立一个顺序表 输出一个顺序表 实验2主要实现顺序表的插入操作 实验3主要实现顺序表的删除操作自主编程实现顺序表的查找操作 数据结构实验教学课件 实验要求 认真看书 理解本节系列算法的思想 上机前写出各算法 语言的源代码 上机运行代码 保存和打印出程序的运行结果 并结合程序进行分析 按照你对线性表的操作需要 编写主程序并运行 打印出文件清单和运行结果写出实验报告 数据结构实验教学课件 顺序表的创建和输出 数据结构实验教学课件 主程序 include include SqList h 数据结构实验教学课件 顺序表的插入 顺序表的删除操作 数据结构实验教学课件 实验内容 二 1实现创建一个单链表 建立一个单链表 输出一个单链表2有序单链表的合并 3删除单链表的重复值 选作 4主要实现单循环链表的逆置 选作 数据结构实验教学课件 单链表的创建和输出 数据结构实验教学课件 单链表的合并 数据结构实验教学课件 单链表的合并 数据结构实验教学课件 数据结构实验教学课件 删除单链表的重复值 数据结构实验教学课件 数据结构实验教学课件 单循环链表的逆置 数据结构实验教学课件 实验二栈与队列的应用 实验目的 1 熟悉栈的特点 先进后出 及栈的基本操作 如入栈 出栈等 掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现 2 熟悉队列的特点 先进先出 及队列的基本操作 如入队 出队等 掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现 数据结构实验教学课件 实验内容 一 1 利用顺序栈各种基本运算的算法 实验1 2 实现链栈各种基本运算的算法 实验2选作 3 实现数值转换算法 写在预习本上 数据结构实验教学课件 数据结构实验教学课件 栈的基本操作 数据结构实验教学课件 栈的基本操作 数据结构实验教学课件 链栈的基本操作 数据结构实验教学课件 链栈的基本操作 实验内容 二 1 利用顺序队列实现各种基本运算的算法 实验3 2 利用链队列实现各种基本运算的算法 实验4 3 完成上次没完成的内容 数据结构实验教学课件 数据结构实验教学课件 顺序队列的基本操作 数据结构实验教学课件 顺序队列的基本操作 数据结构实验教学课件 链队列的基本操作 数据结构实验教学课件 链队列的基本操作 实验要求 认真看书 理解本节系列算法的思想 上机前写出各算法 语言的源代码 上机运行代码 保存和打印出程序的运行结果 并结合程序进行分析 编写主程序并运行 打印出文件清单和运行结果 写出实验报告 数据结构实验教学课件 实验三串 实验目的 1 掌握字符串的基本操作 2 熟悉串函数的实现方法 数据结构实验教学课件 实验三串 实验内容 1 完成实验指导书实验一内容 2 独立编程实现串的联接操作 写在预习本上 数据结构实验教学课件 实验四数组 实验内容 1 完成实验指导书P71基础实验中建立三元组顺序表 输出三元组顺序表和矩阵的转置的内容 2 自主编程实现快速转置的算法 数据结构实验教学课件 defineMAXSIZE12500typedefstruct inti j 该非零元的行下标和列下标ElemTypee 该非零元的值 Triple 三元组类型 一 三元组顺序表 typedefstruct Tripledata MAXSIZE 1 intmu nu tu TSMatrix 稀疏矩阵类型 有两种解决方法 1 按照矩阵M的列序来转置 1214 15 5 22 7 3136 3428 2114 51 5 22 7 1336 4328 StatusFastTransposeSMatrix TSMatrixM TSMatrix FastTransposeSMatrix 转置矩阵元素 Col M data p j q cpot col T data q i M data p j T data q j M data p i T data q e M data p e cpot col 实验五树与二叉树 实验目的 1 理解树这种数据结构 2 掌握二叉树二叉链表这种存储结构 3 完成二叉树各种基本运算的算法 数据结构实验教学课件 实验内容 1 实验1用递归算法实现创建一棵二叉树 必做 2 实验2实现二叉树各种遍历算法 3 实现中序遍历的非递归算法 写在预习本上 数据结构实验教学课件 ABCD A B C D 上页算法执行过程举例如下 A T B C D StatusCreateBiTree BiTree CreateBiTree 三 算法的递归描述 voidPreorder BiTreeT void visit TElemType 遍历右子树 voidInorder BiTreeT void visit TElemType 遍历右子树 voidPostorder BiTreeT void visit TElemType 访问结点 voidInorder I BiTreeT void visit TelemType 实验内容 1 实验3用递归算法实现统计二叉树叶子结点个数 必做 2 实验4实现二叉树深度的统计算法 必做 3 实现二叉树深度统计的非递归算法 选做 数据结构实验教学课件 voidCountLeaf BiTreeT int if CountLeaf intDepth BiTreeT 返回二叉树的深度if T depthval 0 else depthLeft Depth T lchild depthRight Depth T rchild depthval 1 depthLeft depthRight depthLeft depthRight returndepthval IntDepth BTree T 注意讲解时候的level队列 里面的值与qu队列一一对应 intm max rear front level MaxSize BTree qu MaxSize p 循环队列max 0 rear 0 front 0 rear qu rear T level rear 1 根结点入队while front rear front front 1 maxsize 出队列p qu front m level front if m max max m if p lchild NULL rear rear 1 Maxsize 左孩子入队qu rear p lchild level rear m 1 子女层次加1 if p rchild NULL rear rear 1 Maxsize 右孩子入队qu rear p rchild level rear m 1 子女层次加1 returnmax 实验要求 认真看书 理解本节系列算法的思想 上机前写出各算法 语言的源代码 上机运行代码 保存和打印出程序的运行结果 并结合程序进行分析 编写主程序并运行 打印出文件清单和运行结果 写出实验报告 数据结构实验教学课件 实验四图的基本实现与应用 实验目的 1 理解图这种数据结构 2 掌握邻接矩阵 邻接表这种存储结构的实现方法 3 完成图的遍历的算法 数据结构实验教学课件 实验内容 1 实现创建图的邻接矩阵结构的算法 2 实现邻接矩阵与邻接表的转换算法 3 实现创建图的邻接表的算法 数据结构实验教学课件 StatusCreateUDN Mgraph G 建立无向网scanf G vexnum G arcnum 置的对称弧 END 无向图的邻接表创建算法voidcreateadjgraph ALGraph g scanf d d 初始化一维数组 建立各单链表 for k 0 kArcnum k 循环e次建立边表 scanf d d 将新结点 s插入顶点vj的边表头部 实验内容 1 实现图遍历的算法 实验二 必做 写到预习作业本 2 求2点间边数最少的路径 选做 3 实现图的拓扑排序的算法 选做 数据结构实验教学课件 实验要求 认真看书 理解本节系列算法的思想 上机前写出各算法 语言的源代码 上机运行代码 保存和打印出程序的运行结果 并结合程序进行分析 编写主程序并运行 打印出文件清单和运行结果 写出实验报告 数据结构实验教学课件 实验四查找与排序 实验目的 1 理解动态查找表与静态查找表 2 掌握各种查找的算法 数据结构实验教学课件 实验内容 1 顺序查找的设计与实现 必做 2 折半查找的设计与实现 必做 3 直接插入排序算法的实现 必做 4 快速排序算法的实现 选作 5 生死者游戏 选作 6 迷宫的求解 选作 数据结构实验教学课件 ST elem i ST elem i 60 i key 64 key 60 i 64 intSearch Seq SSTableST KeyTypekey 在顺序表ST中顺序查找其关键字等于 key的数据元素 若找到 则函数值为 该元素在表中的位置 否则为0 ST elem 0 key key 哨兵 for i ST length ST elem i key key i 从后往前找returni 找不到时 i为0 Search Seq ST elem ST length 例如 key 64的查找过程如下 low high mid low mid high mid low指示查找区间的下界high指示查找区间的上界mid low high 2 intSearch Bin SSTableST KeyTypekey low 1 high ST length 置区间初值while low high mid low high 2 if EQ key ST elem mid key returnmid 找到待查元素elseif LT key ST elem mid key high mid 1 继续在前半区间进行查找elselow mid 1 继续在后半区间进行查找 return0 顺序表中不存在待查元素 Search Bin 实验要求 认真看书 理解本节系列算法的思想 上机前写出各算法 语言的源代码 上机运行代码 保存和打印出程序的运行结果 并结合程序进行分析 编写主程序并运行 打印出文件清单和运行结果 写出实验报告 数据结构实验教学课件 实验内容 实验1主要实现创建一个顺序表 建立一个顺序表 输出一个顺序表实验2主要实现顺序表的插入操作 实验3主要实现顺序表的删除操作自主编程实现顺序表的查找操作 数据结构实验教学课件 实验内容 1实现创建一个单链表表 建立一个单链表 输出一个单链表2有序单链表的合并 3删除单链表的重复值 选作 4主要实现单循环链表的逆置 选作 数据结构实验教学课件 实验内容 一 1 利用顺序栈各种基本运算的算法 实验1 2 实现链栈各种基本运算的算法 实验2 3 实现数值转换算法 写在预习本上 数据结构实验教学课件 实验内容 二 1 利用顺序队列实现各种基本运算的算法 实验3 做修改变成循环队列 2 利用链队列实现各种基本运算的算法 实验4 3 完成上次没完成的内容 数据结构实验教学课件 实验内容 1 实验1用递归算法实现创建一棵二叉树 必做 2 实验2实现二叉树各种遍历算法 选做 3 实现中序遍历的非递归算法 写在预习本上 数据结构实验教学课件 实验内容 1 实验3用递归算法实现统计二叉树