《数据结构实验》课程教学大纲一、课程信息课程名称：数据结构实验Experiment of Data Structure课程代码：06E4115B课程类别：专业核心课程适用专业：计算机科学与技术专业课程学时：16学时课程学分：0.5学分修读学期：第四学期先修课程：程序设计基础，离散数学，概率论与数理统计二、课程自标《数据结构实验》是计算机科学与技术专业的一门综合性的专业核心课程，是对学生的一种综合训练，是与课堂听讲相辅相成必不可少的一个环节。它要求理解数据结构的基本算法，并能够用程序设计语言实现这些算法，灵活运用数据结构的基本算法解决实际问题，不仅可以培养学生的创新意识，而且培养学生独立分析问题、设计算法、实现复杂编程的能力，为后续课程的学习和科研工作的参与打下良好的基础。（一）具体目标通过本课程的学习，使学生加深对课程内容的理解，培养将原理应用于实际的能力，提高软件设计、算法应用、编程及调试的综合素质。1.掌握数据结构中线性表、栈、队列、树、图等基本结构的概念以及特点，针对具体问题，正确分析并建立不同模型求解问题。【支撑毕业要求指标点1.3】2.能够应用数据结构模型的基本原理，学会对问题进行分析，根据具体问题的实际要求选择并构建合适的数据存储结构。【支撑毕业要求指标点2.1】3.结合实际问题，对给定的非数值问题设计并求解算法，设计出一套可行的解决方案，得出有效结果，进一步提高学生的程序设计能力，培养良好的程序设计习惯，提高学生分析问题和解决问题的能力，为后续课程的学习以及软件设计
《数据结构实验》课程教学大纲 一、课程信息 课程名称：数据结构实验 Experiment of Data Structure 课程代码: 06E4115B 课程类别：专业核心课程 适用专业：计算机科学与技术专业 课程学时: 16 学时 课程学分: 0.5 学分 修读学期：第四学期 先修课程：程序设计基础，离散数学，概率论与数理统计 二、课程目标 《数据结构实验》是计算机科学与技术专业的一门综合性的专业核心课程， 是对学生的一种综合训练，是与课堂听讲相辅相成必不可少的一个环节。它要求 理解数据结构的基本算法，并能够用程序设计语言实现这些算法，灵活运用数据 结构的基本算法解决实际问题，不仅可以培养学生的创新意识，而且培养学生独 立分析问题、设计算法、实现复杂编程的能力，为后续课程的学习和科研工作的 参与打下良好的基础。 （一）具体目标 通过本课程的学习，使学生加深对课程内容的理解，培养将原理应用于实际 的能力，提高软件设计、算法应用、编程及调试的综合素质。 1.掌握数据结构中线性表、栈、队列、树、图等基本结构的概念以及特点， 针对具体问题，正确分析并建立不同模型求解问题。【支撑毕业要求指标点 1.3】 2.能够应用数据结构模型的基本原理，学会对问题进行分析，根据具体问题 的实际要求选择并构建合适的数据存储结构。【支撑毕业要求指标点 2.1】 3.结合实际问题，对给定的非数值问题设计并求解算法，设计出一套可行的 解决方案，得出有效结果，进一步提高学生的程序设计能力，培养良好的程序设 计习惯，提高学生分析问题和解决问题的能力，为后续课程的学习以及软件设计
水平的提高打下良好的基础。【支撑毕业要求指标点3.1】4.能够在VC++或其他环境，基于C语言对复杂计算机软件工程问题进行分析、设计、开发和测试，利用团队合作意识和一定的创新能力进行算法实现。【支撑毕业要求指标点4.2、4.3、4.4】（二）课程目标与毕业要求的对应关系表1课程目标与毕业要求指标点的对应关系课程目标支撑的毕业要求支撑的毕业要求指标点1.3掌捶计算机知识和数学建模的方法，应用于计算机工程间课程目标11.工程知识题的推演和分析：2.1能够应用计算机料学的基本原理，分析和识别计算机复杂课程目标22. 问题分析工程问题的关键点；3.1利用计算机科学技术的基本知识，针对计算机复杂工程问3.设计/开发课程目标3题，给出可行的解决方案，具有设计满足特定需求的中小型软解决方案件系统和大型系统的独立子系统的能力；4.3具有根据计算机实验方案构建实验系统，安全地开展实验，并正确的采集实验数据的能力：4. 科学研究课程目标44.4能对计算机实验结采进行分析和解释，并通过信息综合得到合理有效的结论；三、课程内容（一）课程内容与课程目标的关系表 2 课程内容与课程目标的关系课程内容教学方法学时安排支撑的课程目标第一部分 线性表的基4案例式教学、任务驱动教学课程目标1，2，3，4本操作及应用第二部分栈和队列2任务驱动教学，启发式教学课程目标1，2，3，4的应用第三部分二叉树两2任务驱动教学课程目标1，2，3，4种存储结构的应用第四部分图的存储2案例式教学、情景教学课程目标1,2，3,4 及应用
水平的提高打下良好的基础。【支撑毕业要求指标点 3.1】 4.能够在 VC++或其他环境，基于 C 语言对复杂计算机软件工程问题进行分析、 设计、开发和测试，利用团队合作意识和一定的创新能力进行算法实现。【支撑 毕业要求指标点 4.2、4.3、4.4】 （二）课程目标与毕业要求的对应关系 表 1 课程目标与毕业要求指标点的对应关系 课程目标 支撑的毕业要求 支撑的毕业要求指标点 课程目标 1 1.工程知识 1.3掌握计算机知识和数学建模的方法，应用于计算机工程问 题的推演和分析； 课程目标 2 2.问题分析 2.1能够应用计算机科学的基本原理，分析和识别计算机复杂 工程问题的关键点； 课程目标 3 3. 设计/开发 解决方案 3.1利用计算机科学技术的基本知识，针对计算机复杂工程问 题，给出可行的解决方案，具有设计满足特定需求的中小型软 件系统和大型系统的独立子系统的能力； 课程目标 4 4. 科学研究 4.3具有根据计算机实验方案构建实验系统，安全地开展实验， 并正确的采集实验数据的能力； 4.4能对计算机实验结果进行分析和解释，并通过信息综合得 到合理有效的结论； 三、课程内容 （一）课程内容与课程目标的关系 表 2 课程内容与课程目标的关系 课程内容 教学方法 支撑的课程目标 学时安排 第一部分 线性表的基 本操作及应用 案例式教学、任务驱动教学 课程目标 1，2，3，4 4 第二部分 栈和队列 的应用 任务驱动教学，启发式教学 课程目标 1，2，3，4 2 第三部分 二叉树两 种存储结构的应用 任务驱动教学 课程目标 1，2，3，4 2 第四部分 图的存储 及应用 案例式教学、情景教学 课程目标 1，2，3，4 2
第五部分数据结构课6案例式教学、任务驱动教学课程目标1，2,3，4程设计合计16 学时（二）具体内容第一部分线性表的基本操作及应用（4学时）【教学目标与要求】1、教学目标：通过本部分的学习，帮助学生复习C语言程序设计中的知识；熟悉线性表的逻辑结构；熟悉线性表的基本运算在顺序表和链表上的实现。2、教学要求：掌握顺序表的建立、求长度、取表中元素、修改元素、插入、删除等顺序表的操作：掌握链表的建立、求长度、取表中元素、修改元素、插入、删除等顺序表的操作；【教学重点与难点】1、教学重点：顺序表和链表的特点2、教学难点：顺序表和链表的的相关算法实现【教学内容】上机实验内容一：两种存储结构的基本运算1.问题描述使用二级菜单实现顺序表和链表的建立、插入和删除算法2.设计分析通过菜单项，调用子函数实现算法。二级菜单如下所示：*******************************1-—-——顺序表*2-------链表**0—--退出******************************请输入的选择：(0-2)：线性表的链式存储
第五部分 数据结构课 程设计 案例式教学、任务驱动教学 课程目标 1，2，3，4 6 合计 16 学时 （二）具体内容 第一部分 线性表的基本操作及应用（4 学时） 【教学目标与要求】 1、教学目标： 通过本部分的学习，帮助学生复习 C 语言程序设计中的知识；熟悉线性表的 逻辑结构；熟悉线性表的基本运算在顺序表和链表上的实现。 2、教学要求： 掌握顺序表的建立、求长度、取表中元素、修改元素、插入、删除等顺序表 的操作；掌握链表的建立、求长度、取表中元素、修改元素、插入、删除等顺序 表的操作； 【教学重点与难点】 1、教学重点：顺序表和链表的特点 2、教学难点：顺序表和链表的的相关算法实现 【教学内容】 上机实验内容一：两种存储结构的基本运算 1.问题描述 使用二级菜单实现顺序表和链表的建立、插入和删除算法 2．设计分析 通过菜单项，调用子函数实现算法。二级菜单如下所示： ***************************** * 1-顺序表 * * 2-链 表 * * 0-退 出 * ***************************** 请输入的选择：(0-2)： 线性表的链式存储
################################1----前插建立链表##2---后插建立链表##3----访问第i个元素##4----插入##5----删除##6----求线性表的表长##0---退出##############################请输入选择(0-6)：3.结点结构类型描述typedef struct (datatype data[MAXSIZE];int length,)sqlist;typedef struct node!datatype data,struct node *next:;jListNode,*LinkList上机实验内容二：超市密码存储箱系统的简单应用1.问题描述顾客到超市中需要存包时，首先检查是否有空箱子，如果有就“投一元硬币”一—一“找到一个空箱子，同时产生密码”————-“打印密码，打开箱子”一“取密码纸存包，并关闭箱子，入超市购物”一“购物结束”“输入密码”“找到对应箱子并打开”“取包”。2.设计分析①界面：编写菜单，可以循环进行存包、取包、退出。②顾客选择存包时，首先在空箱子链表中查找是否还有结点，如果“有”时就产生密码，将密码存入结点，从空箱子链表中删除该结点，加入到实箱子链表中，否则就显示箱子已满。③顾客选择取包时，首先输入密码与实箱子链表中结点的密码进行比对，如
############################## # 1-前插建立链表 # # 2-后插建立链表 # # 3-访问第 i 个元素 # # 4-插入 # # 5-删除 # # 6-求线性表的表长 # # 0-退出 # ############################## 请输入选择(0-6)： 3．结点结构类型描述 typedef struct { datatype data[MAXSIZE]; int length;}sqlist; typedef struct node{ datatype data; struct node *next;}ListNode,*LinkList 上机实验内容二：超市密码存储箱系统的简单应用 1．问题描述 顾客到超市中需要存包时，首先检查是否有空箱子，如果有就“投一元硬币” -“找到一个空箱子，同时产生密码”-“打印密码，打开箱子” -“取密码纸存包，并关闭箱子，入超市购物”-“购物结束” -“输入密码”-“找到对应箱子并打开”-“取包”。 2.设计分析 ①界面：编写菜单，可以循环进行存包、取包、退出。 ②顾客选择存包时，首先在空箱子链表中查找是否还有结点，如果“有”时 就产生密码，将密码存入结点，从空箱子链表中删除该结点，加入到实箱子链 表中，否则就显示箱子已满。 ③顾客选择取包时，首先输入密码与实箱子链表中结点的密码进行比对，如
果成功就从实箱子链表中删除该结点，加入到空箱子链表，否则显示密码不匹配。3.密码箱的存储结构类型定义typedef struct nodeintnum;/*箱子的号码*/intpassword;/*箱子的密码（满箱有，空箱无）*/structnode*next:/*指向下个结点的指针*/Node,*LinkList;上机实验内容三：员工通讯录管理1.问题描述为某个单位建立一个员工通讯录管理系统，可以方便地查询每一个员工的力公室电话号码、手机号码及电子邮箱。2.设计分析在本设计中，整个通讯录可以采用顺序表或链表方式存储。其功能包括通讯录链表的建立、员工通讯信息的查询、修改、插入与删除以及整个通讯录表的输出。3.员工通讯信息的结构类型定义和通讯录链表的结点类型typedef struct(charnum[5];/*员工编号*/charname[8];/*员工姓名*/charphone[9];/*办公室电话号码*/charcal[12];/*手机号码*/)DataType；/*员工通讯信息的结构类型*/typedefstruct node(DataTypedata;/*结点的数据域*structnode*next:/*结点的指针域*/ListNode,*LinkList；/*通讯录链表的结构类型*上机实验内容四：运动会记分子系统或学生成绩管理子系统1.问题描述参加运动会的N个学校编号为1N。比赛分成M个男子项目和W个女子项目，每个项目取前3名，得分分别为5，3，2。写一个程序产生各种成绩单和得分报表
果成功就从实箱子链表中删除该结点，加入到空箱子链表，否则显示密码不匹配。 3.密码箱的存储结构类型定义 typedef struct node { int num;/*箱子的号码*/ int password;/*箱子的密码（满箱有，空箱无）*/ struct node *next;/*指向下个结点的指针*/ }Node,*LinkList； 上机实验内容三：员工通讯录管理 1.问题描述 为某个单位建立一个员工通讯录管理系统，可以方便地查询每一个员工的办 公室电话号码、手机号码及电子邮箱。 2. 设计分析 在本设计中，整个通讯录可以采用顺序表或链表方式存储。 其功能包括通 讯录链表的建立、员工通讯信息的查询、修改、插入与删除以及整个通讯录表的 输出。 3. 员工通讯信息的结构类型定义和通讯录链表的结点类型 typedef struct { char num[5];/*员工编号*/ char name[8];/*员工姓名*/ char phone[9];/*办公室电话号码*/ char call[12];/*手机号码*/ }DataType；/*员工通讯信息的结构类型*/ typedef struct node { DataType data;/*结点的数据域*/ struct node *next;/*结点的指针域*/ }ListNode,*LinkList；/*通讯录链表的结构类型*/ 上机实验内容四：运动会记分子系统或学生成绩管理子系统 1.问题描述 参加运动会的 N 个学校编号为 1~N。比赛分成 M 个男子项目和 W 个女子项目， 每个项目取前 3 名，得分分别为 5，3，2。写一个程序产生各种成绩单和得分报 表
2.设计分析完成功能包括如下：①产生一总成绩表，包括：系名、男子团体总分、女子团体总分、团体总分存储结构要求用线性表的顺序存储。②实验报告中要写出测试数据、错误分析以及收获。③若选择学生成绩管理子系统，可仿照运动会记分子系统完成相关的插入、删除、查找及各种统计工作。3.运动会记分子系统结点的结构类型描述typedef struct Inode1intman[m];//男子项目intwoman[w];//女子项目intsuml[N];//男子团体总分intsum2[N];//女子团体总分intsum[N];//团体总分fInode;InodeschoolNl;//各学校【思政元素融入点】：通过顺序存储结构和链式存储结构的特点，类似于在“一带一路”，如果有新的国家加入，根据其地理位置，加入线性表中对应的位置，这与线性表中增加元素操作对应，相信在未来的不断发展中，将会有越来越多的国家加入“一带一路”。第二部分栈和队列的应用（2学时）【教学目标与要求】1、教学目标：通过本部分的学习，学生熟悉线性表的逻辑结构；熟悉栈和队列的基本运算在顺序表和链表上的实现；认真分析项目实例中的内容，将相关程序在计算机上运行实现。2、教学要求：掌握栈的特点、初始化、入栈、出栈、访问栈顶元素等相关操作；掌握队列的特点、初始化、入队、出队、求队列中元素长度等相关操作；
2.设计分析 完成功能包括如下： ①产生一总成绩表，包括：系名、男子团体总分、女子团体总分、团体总分 存储结构要求用线性表的顺序存储。 ②实验报告中要写出测试数据、错误分析以及收获。 ③若选择学生成绩管理子系统，可仿照运动会记分子系统完成相关的插入、 删除、查找及各种统计工作。 3．运动会记分子系统结点的结构类型描述 typedef struct lnode { int man[m]; // 男子项目 int woman[w];//女子项目 int sum1[N];//男子团体总分 int sum2[N];//女子团体总分 int sum[N];//团体总分 }lnode; lnode school[N];//各学校 【思政元素融入点】：通过顺序存储结构和链式存储结构的特点，类似于在“一 带一路”，如果有新的国家加入，根据其地理位置，加入线性表中对应的位置， 这与线性表中增加元素操作对应，相信在未来的不断发展中，将会有越来越多的 国家加入“一带一路”。 第二部分 栈和队列的应用（2 学时） 【教学目标与要求】 1、教学目标： 通过本部分的学习，学生熟悉线性表的逻辑结构；熟悉栈和队列的基本运算 在顺序表和链表上的实现；认真分析项目实例中的内容，将相关程序在计算机上 运行实现。 2、教学要求： 掌握栈的特点、初始化、入栈、出栈、访问栈顶元素等相关操作；掌握队列 的特点、初始化、入队、出队、求队列中元素长度等相关操作；
【教学重点与难点】1、教学重点：栈和队列的概念2、教学难点：栈和队列的算法实现【教学内容】上机实验内容一：表达式求值问题1.问题描述求一个数学表达式的值：用户输入一个包含正整数、括号和四则运算符（“+”“一”、“*”、“/”）的算术表达式，计算其结果。2.设计分析首先置操作数栈为空栈，表达式起始符“#”为运算符栈底元素：依次读入表达式中每个字符，若是操数则进操作数栈，若是操作符则和操作符栈顶的运算符进行比较优先权后作相应的操作，直到整个表达式求值完毕（即操作符栈顶元素和当前读入的字符均为“#”）3.结点结构类型描述如下typedef struct(char *base,*top;int stacksize,Isqstack,上机实验内容二：迷宫求解问题1.问题描述在一个m行n列的迷宫中，设入口为（1，1），出口为（mn），即从入口出发，顺某一方向向前探索，直到出口，如果迷宫中没有通路，就输出迷宫无解。2.设计分析本实验主要涉及的算法包括：随机生成一个m行n列的矩阵，为了操作方便可以在矩阵外围生成一圈障碍；设置东南西北四个方向，计算相邻节点的位置：对走过的节点进行标注；在迷宫中进行探索，找出通路。3.结点结构类型描述如下typedefstructnode( int row,int col,struct node *next;
【教学重点与难点】 1、教学重点：栈和队列的概念 2、教学难点：栈和队列的算法实现 【教学内容】 上机实验内容一：表达式求值问题 1．问题描述 求一个数学表达式的值：用户输入一个包含正整数、括号和四则运算符（“+”、 “—”、 “*”、 “/”）的算术表达式，计算其结果。 2．设计分析 首先置操作数栈为空栈，表达式起始符“#”为运算符栈底元素；依次读入 表达式中每个字符，若是操数则进操作数栈，若是操作符则和操作符栈顶的运算 符进行比较优先权后作相应的操作，直到整个表达式求值完毕（即操作符栈顶元 素和当前读入的字符均为“#”） 3．结点结构类型描述如下 typedef struct {char *base,*top; int stacksize; }sqstack; 上机实验内容二：迷宫求解问题 1.问题描述 在一个 m 行 n 列的迷宫中，设入口为（1，1），出口为（m,n），即从入口出 发，顺某一方向向前探索，直到出口，如果迷宫中没有通路，就输出迷宫无解。 2.设计分析 本实验主要涉及的算法包括：随机生成一个 m 行 n 列的矩阵，为了操作方便 可以在矩阵外围生成一圏障碍；设置东南西北四个方向，计算相邻节点的位置； 对走过的节点进行标注；在迷宫中进行探索，找出通路。 3．结点结构类型描述如下 typedef struct node { int row; int col; struct node *next;
3;【思政元素融入点】：栈的特点是先进后出，队列的特点是先进先出，引用在食堂排队打饭，强调遵守秩序，先到先服务，引导学生要懂规矩，守纪律，遵守社会公德。第三部分二叉树两种存储结构的应用（2学时）【教学目标与要求】1、教学目标：通过本部分的学习，使学生理解并掌握二叉树的相关概念以及问题的应用。2、教学要求：了解二又树的特点；掌握二叉树的建立、遍历思想、二又树的存储实现；算法设一种形式完成二叉树的显示；掌握二叉树的常见算法的程序实现【教学重点与难点】1、教学重点：二叉树的概念以及特点2、教学难点：二叉树存储结构的实现【教学内容】上机实验内容一：二叉树的建立及相关算法的实现1.问题描述使用菜单实现二叉树的相关算法2.设计分析选择相应的菜单调用相关算法子函数，完成二叉树的建立、显示、三种遍历、求树高、求叶子节点数等。菜单显示如下：****************************** 1-二叉树的建立***2-------显显示二叉树...........退出**n-*****************************请输入的选择：(0-n)：
}; 【思政元素融入点】：栈的特点是先进后出，队列的特点是先进先出，引用在食 堂排队打饭，强调遵守秩序，先到先服务，引导学生要懂规矩，守纪律，遵守社 会公德。 第三部分 二叉树两种存储结构的应用（2 学时） 【教学目标与要求】 1、教学目标： 通过本部分的学习，使学生理解并掌握二叉树的相关概念以及问题的应用。 2、教学要求： 了解二叉树的特点；掌握二叉树的建立、遍历思想、二叉树的存储实现；算 法设 一种形式完成二叉树的显示；掌握二叉树的常见算法的程序实现 【教学重点与难点】 1、教学重点：二叉树的概念以及特点 2、教学难点：二叉树存储结构的实现 【教学内容】 上机实验内容一：二叉树的建立及相关算法的实现 1.问题描述 使用菜单实现二叉树的相关算法 2.设计分析 选择相应的菜单调用相关算法子函数，完成二叉树的建立、显示、三种遍历、 求树高、求叶子节点数等。 菜单显示如下： ***************************** * 1-二叉树的建立 * * 2-显示二叉树 * . * n-退 出 * ***************************** 请输入的选择：(0-n)：
3.结点结构类型设计Typedef struct nodetDatatype data;Struct node *lchild,*rchild;}BiTnoe,*BiTree;上机实验内容二：哈夫曼编码/译码系统1.问题描述要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。2.设计分析在本例中的算法主要有：哈夫曼树的建立；哈夫曼编码的生成；对编码信息的翻译。要求设置发送者和接收者两个功能。发送者的功能包括：①输入待传送的字符信息；②统计字符信息中出现的字符类数和各字符出现的次数（频率）：③根据字符的种类数和各字符出现的次数建立哈夫曼树④利用以上哈夫曼树求出各字符的哈夫曼编码：③将字符信息转换成对应的编码信息进行传送。接收者的功能包括：①接收发送者传送来的编码信息；②利用上述哈夫曼树对编码进行翻译，即将编码信息还原成发送前的字符信息。3.结点的类型定义①哈夫曼树的存储结构类型定义为：typedef struct!char data,/*编码对应的字符*//*结点的权值*/int weight,intlchild,rchild,parent,/*左右孩子及双亲的下标*}HTNode;②哈夫曼编码的存储结构类型定义为：typedef struct(char bits[N];, /*存放哈夫曼编码的字符数组*
3．结点结构类型设计 Typedef struct node{ Datatype data; Struct node *lchild,*rchild;}BiTnoe,*BiTree; 上机实验内容二：哈夫曼编码/译码系统 1.问题描述 要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码， 然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信 息。 2.设计分析 在本例中的算法主要有：哈夫曼树的建立；哈夫曼编码的生成；对编码信 息的翻译。要求设置发送者和接收者两个功能。 发送者的功能包括： ①输入待传送的字符信息；②统计字符信息中出现的字符类数和各字符出 现的次数（频率）；③根据字符的种类数和各字符出现的次数建立哈夫曼树；④ 利用以上哈夫曼树求出各字符的哈夫曼编码；⑤将字符信息转换成对应的编码信 息进行传送。 接收者的功能包括： ①接收发送者传送来的编码信息；②利用上述哈夫曼树对编码进行翻译， 即将编码信息还原成发送前的字符信息。 3．结点的类型定义 ①哈夫曼树的存储结构类型定义为： typedef struct{ char data; /*编码对应的字符*/ int weight; /*结点的权值*/ int lchild,rchild,parent;/*左右孩子及双亲的下标*/ }HTNode; ②哈夫曼编码的存储结构类型定义为： typedef struct{ char bits[N]; /*存放哈夫曼编码的字符数组*/
int start,/*记录编码的起始位置，因为每种字符的编码长度不同*/}HCode;【思政元素融入点】：哈夫曼编码讲解可以引用图片压缩技术，这种压缩技术得到广泛应用，鼓励学生不懈努力，改革创新，思考计算机专业新的方法和理论；二叉树的遍历要用到递归算法思想，类似个人的所作所为抽象成递归最终的回溯结果，每个人的所作所为可能是渺小的，但是所有重大的变革或发展是众多个体努力的结果。第四部分图的存储及应用（2学时）【教学目标与要求】1、教学目标：通过本部分的学习，使学生理解并掌握图的概念、特点以及问题中的应用。2、教学要求：掌握图的深度、广度优先遍历算法思想及其程序实现；掌握图的常见应用算法的思想及其程序实现【教学重点与难点】1、教学重点：图的建立、遍历2、教学难点：图的两种遍历实现【教学内容】实验内容一：图的遍历问题1.问题描述使用菜单实现图的相关算法，如键盘输入以下结点数据：太原、成都、北京、上海、天津、大连、河北，建立一个有向图或无向图（自定）的邻接表并输出该邻接表；在图的邻接表的基础上计算各顶点的度，并输出；以有向图的邻接表为基础实现输出它的拓扑排序序列；采用邻接表存储实现无向图的深度优先遍历；采用邻接表存储实现无向图的广度优先遍历；采用邻接矩阵存储实现无向图的最小生成树的PRIM算法2.设计分析调用菜单项，分别调用相应的子函数。注意顶点存储地名，使用字符数组来实现
int start; /*记录编码的起始位置，因为每种字符的编码长度不同*/ }HCode; 【思政元素融入点】：哈夫曼编码讲解可以引用图片压缩技术，这种压缩技术得 到广泛应用，鼓励学生不懈努力，改革创新，思考计算机专业新的方法和理论； 二叉树的遍历要用到递归算法思想，类似个人的所作所为抽象成递归最终的回溯 结果，每个人的所作所为可能是渺小的，但是所有重大的变革或发展是众多个体 努力的结果。 第四部分 图的存储及应用（2 学时） 【教学目标与要求】 1、教学目标： 通过本部分的学习，使学生理解并掌握图的概念、特点以及问题中的应用。 2、教学要求： 掌握图的深度、广度优先遍历算法思想及其程序实现；掌握图的常见应用算 法的思想及其程序实现 【教学重点与难点】 1、教学重点：图的建立、遍历 2、教学难点：图的两种遍历实现 【教学内容】 实验内容一：图的遍历问题 1．问题描述 使用菜单实现图的相关算法,如键盘输入以下结点数据：太原、成都、北京、 上海、天津、大连、河北，建立一个有向图或无向图（自定）的邻接表并输出该 邻接表 ；在图的邻接表的基础上计算各顶点的度，并输出 ；以有向图的邻接表 为基础实现输出它的拓扑排序序列 ；采用邻接表存储实现无向图的深度优先遍 历；采用邻接表存储实现无向图的广度优先遍历；采用邻接矩阵存储实现无向图 的最小生成树的 PRIM 算法 2.设计分析 调用菜单项，分别调用相应的子函数。注意顶点存储地名，使用字符数组来 实现