授课计划
广 西 中 医 药 大 学
教 师 授 课 计 划
| 专 业： | 信息管理与信息系统 |
| 班 级： | 2016级信管 |
| 课 程： | 数据结构 |
| 主讲教师签名： | 唐晓年 |
| 教研室主任签名： | 甘昕艳 |
| 制 定 日 期： | 2017-9-2 |
学时分配：
| 总学时 | 理论 | 实验 | 见习 | 电化教学 | 课堂讨论 | 读书活动 | 作业 | 复习 | 考核 | 机动 | ||
| 64 | 32 | 32 | ||||||||||
| 理论课时分配 | 教授、副教授 | 讲 师 | 助 教 | 教 员 | ||||||||
| 课时 | ％ | 课时 | ％ | 课时 | ％ | 课时 | ％ | |||||
| 64 | 100 | |||||||||||
备注：各门课程的授课计划请于开学前交学院教务科。
教 师 授 课 计 划
| 周 次 | 课 次 | 授 课 内 容 （标明重点、难点） | 课时 | 主讲教师 | 职 称 | |
| 理论课 | 实验见习讨论 | |||||
| 1 | 2 | C语言补充知识：结构体数据类型 教学内容： 1) 结构体类型和基本类型有什么联系和区别？ 2) 结构体的基本概念 3) 结构体的定义和初始化 4) 结构体的嵌套定义 5) 结构体变量和结构体数组 6) 结构体成员的引用 教学重点 1) 结构体的定义和初始化 2) 结构体成员的引用 教学难点： 1) 结构体的嵌套定义 2) 结构体数组成员应用 | 2 | 唐晓年 | 讲师 | |
| 111周 次 1 1 2 2 教学内容： 3) 什么是数据结构 4) 基本概念和术语 5) 数据类型和抽象数据类型 6) 算法描述与算法评价 7) 算法描述 8) 算法设计要求 9) 算法的评价 教学重点 1) 了解数据结构 2) 掌握数据结构的概念。 3) 掌握数据的类型 4) 了解算法的设计要求 教学难点： 3) 数据类型的掌握 4) 算法的设计 第九章 结构体数据类型与链表 9.1 结构体类型的定义 9.2 结构体类型变量 9.3 结构体类型数组 9.4 结构体类型指针 2 2 唐晓年 讲师 周 次 课 次 授 课 内 容 （标明重点、难点） 课时 主讲教师 职 称 理论课 实验见习讨论 1 1 2 2 教学内容： 10) 什么是数据结构 11) 基本概念和术语 12) 数据类型和抽象数据类型 13) 算法描述与算法评价 14) 算法描述 15) 算法设计要求 16) 算法的评价 教学重点 5) 了解数据结构 6) 掌握数据结构的概念。 7) 掌握数据的类型 8) 了解算法的设计要求 教学难点： 5) 数据类型的掌握 6) 算法的设计 第九章 结构体数据类型与链表 9.1 结构体类型的定义 9.2 结构体类型变量 9.3 结构体类型数组 9.4 结构体类型指针 2 2 唐晓年 讲师 周 次 | 课 次 | 授 课 内 容 （标明重点、难点） | 课时 | 主讲教师 | 职 称 | |
| 理论课 | 实验见习讨论 | |||||
| 2 3 | 2 3 | C语言补充知识：指针 教学内容： 1) 地址和指针的概念 2) 变量的指针和指向变量的指针变量 3) 数组与指针 4) 字符串与指针 5) 指向函数的指针 教学重点 1) 理解指针包括地址和类型两种属性。 2) 掌握指针运算符&和*。 3) 能够通过地址引用调用在被调函数与主调函数之间共享数据。 4) 理解指针和数组的关系。 5) 理解指向函数的指针的用法 教学难点： 1) 数组与指针 2) 字符串与指针 | 2 2 2 | 唐晓年 | 讲师 | |
| 周 次 | 课 次 | 授 课 内 容 （标明重点、难点） | 课时 | 主讲教师 | 职 称 | |
| 理论课 | 实验见习讨论 | |||||
| 5 | 4 | C语言补充知识：预定义和结构体指针 教学内容： 1) 预定义命令的使用 2) typedef定义数据类型 3) 指向结构体类型数据的指针 4) “ . ”和“->”分量运算符操作结构体变量和指向结构体的指针变量 教学重点 1) 结构体指针 2) 成员运算和引用运算的联系与区别 教学难点： 1) 成员运算和引用运算 | 2 2 | 唐晓年 | 讲师 | |
第 1 页
| 周 次 | 课 次 | 授 课 内 容 （标明重点、难点） | 课时 | 主讲教师 | 职 称 | |
| 理论课 | 实验见习讨论 | |||||
| 6 1 | 5 2 | 教学内容： 7) 什么是数据结构 8) 基本概念和术语 9) 数据类型和抽象数据类型 10) 算法描述与算法评价 11) 算法描述 12) 算法设计要求 13) 算法的评价 教学重点 9) 了解数据结构 10) 掌握数据结构的概念。 11) 掌握数据的类型 12) 了解算法的设计要求 教学难点： 7) 数据类型的掌握 8) 算法的设计 | 2 2 | 唐晓年 | 讲师 | |
| 周 次 | 课 次 | 授 课 内 容 （标明重点、难点） | 课时 | 主讲教师 | 职 称 | |
| 理论课 | 实验见习讨论 | |||||
| 7 7 | 6 6 | 第二章 线性表 教学内容： 1) 什么是线性表 2) 线性表的逻辑结构 3) 线性表的运算 4) 线性表的顺序存储结构 5) 线性表的链式存储结构 2．教学重点： 1) 掌握算线性表的基本概念 2) 掌握单链表上的基本算法 3. 教学难点： 线性表的逻辑结构 实验一：顺序表的建立与查找 一、实验目的 1、掌握建立顺序表的基本方法。 2、理解和掌握顺序表元素查找算法。 3、掌握顺序表的插入、删除算法的思想和实现。 二、实验内容 1、 建立一个顺序表，要求从键盘输入10个整数，并将该顺序表的元素从屏幕显示出来 2、编写查找函数，在上面的顺序表中查找其中一个元素，如果找到，返回该元素在顺序表中的位置和该元素的值，否则提示无此元素。要求被查找元素从键盘输入。 3、编写插入和删除函数，由用户输入待插入元素及插入位置，将完成插入后的顺序表输出；由用户输入删除第几个元素，将完成删除后的顺序表输出。 | 2 | 2 | 唐晓年 | 讲师 |
| 周 次 | 课 次 | 授 课 内 容 （标明重点、难点） | 课时 | 主讲教师 | 职 称 | |
| 理论课 | 实验见习讨论 | |||||
| 8 3 | 7 2 | 第三章 线性表 1. 教学内容： 3.1 线性表存储结构的选择 3.2 线性表的应用举例 2．教学重点 1) 掌握线性表存储结构的方法 3. 教学难点： 1) 线性表存储结构的选择 实验三：单链表的基本操作 一、实验目的 1、理解和掌握单链表的类型定义方法和结点生成方法。 2、掌握建立单链表和显示单链表元素的算法。 3、掌握单链表的插入和删除算法。 二、实验内容 1、建立一个单链表，并从屏幕显示单链表元素列表。 2、删除链表某位置上的元素，并保持链表原有的顺序不变，请在给出的程序中加入一个删除函数，实现上述功能要求。ElemType delete_L(LNode *L,int i)为删除函数的原型，L表示链表，i表示插入位置。注意菜单中给出了菜单项，请在switch语句给出调用语句，在主函数中加入删除函数，并注意判断表为空的情况。 | 2 2 | 唐晓年 | 讲师 | |
| 周 次 | 课 次 | 授 课 内 容 （标明重点、难点） | 课时 | 主讲教师 | 职 称 | |
| 理论课 | 实验见习讨论 | |||||
| 9 9 | 8 8 | 第三章 栈和队列 1. 教学内容： 4.1 栈的定义及其运算 4.2 栈的顺序存储结构 4.3栈的链式存储结构 2．教学重点 1) 掌握栈的定义及其运算方法 2) 了解栈的顺序存储结构和链式存储结构 3. 教学难点： 栈的顺序存储结构和链式存储结构 实验三：栈的应用—括号匹配 一、实验目的 1．掌握堆栈特殊线性表的存储方式的基本操作方法。 2．掌握堆栈后进先出运算原则在解决实际问题中的应用。 3．掌握使用栈的原理来解决表达式中的括号配对问题。 二、实验内容 假设一个算术表达式中包含圆括弧、方括弧三种类型的括弧，编写一个程序用于判别表达式中括弧是否正确配对。 说明：检验表达式中的括号匹配情况：假设在一个算术表达式中，可以包含三种括号：圆括号"（"和"）"，方括号"["和"]"，并且这两种括号可以按任意的次序嵌套使用。比如，...[......[...]...]...(...)..。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。 提示： 算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。 （1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号； （2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况； （3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。 算法步骤：扫描表达式， 1）凡出现左括弧，则进栈； 2）凡出现右括弧，首先检查栈是否空。 若栈空，则表明该“右括弧”多余 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” 否则表明不匹配 3）表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余 栈的类型定义及基本操作代码可参考教材相关定义和程序。 | 2 | 2 | 唐晓年 | 讲师 |
| 周 次 | 课 次 | 授 课 内 容 （标明重点、难点） | 课时 | 主讲教师 | 职 称 | |
| 理论课 | 实验见习讨论 | |||||
| 10 | 9 | 第三章 栈和队列 1. 教学内容： 5.4 队列的定义及其运算 5.5 队列的顺序存储结构 5.6 队列的链式存储结构 5.7 队列的举例应用 5.8 优先队列 5.9 双端队列 2．教学重点 1) 熟练掌握队列的顺序存储结构 熟练掌握队列的链式存储结构 3. 教学难点： 1）优先队列的应用 实验五：队列的基本操作 一、实验目的 1．掌握队列的顺序存储结构。 2．掌握队列先进先出运算原则在解决实际问题中的应用。 3. 掌握自定义数据类型的用法。 二、实验内容 仿照资料中顺序循环队列的例子，设计一个只使用队头指针和计数器的顺序循环队列抽象数据类型。其中操作包括：初始化、入队列、出队列、判断队列是否非空。编写主函数，验证所设计的顺序循环队列的正确性。 以下是队列操作函数的定义： (1)QueueInitiate(Q) 初始化队列Q (2)QueueNotEmpty(Q) 队列Q非空否 (3)QueueAppend(Q,x) 入队列，在队列Q的队尾插入数据元素x。 (4)QueueDelete(Q,d) 出队列，把队列Q的队头元素删除并由参数d带回。 提示：队尾的位置可由队头指针与计数器进行求解，请思考它们之间的关系，同时还要考虑如何实现循环队列（可借助求模运算）。 | 2 | 2 | 唐晓年 | 讲师 |
| 周 次 | 课 次 | 授 课 内 容 （标明重点、难点） | 课时 | 主讲教师 | 职 称 | |
| 理论课 | 实验见习讨论 | |||||
| 11 | 10 | 第六章 树 1．教学内容： 6.1什么是树？ 6.2二叉树的概念 6.3二叉树的性质 6.4遍历二叉树的递归算法 6.5遍历二叉树的非递归算法 2．教学重点： 1) 二叉树的运算 2) 二叉树遍历的特点 3. 教学难点： 二叉树算法实现 实验五：二叉树的遍历应用 一、实验目的 1、掌握二叉树的建立方法 2、掌握二叉树遍历的基本方法（前序、中序、后序） 3、掌握递归二叉树遍历算法的应用 二、实验内容 1.构造一棵二叉树,树的形态如下图所示，打印出前序遍历、中序遍历、后序遍历的遍历序列。 | 2 | 2 | 唐晓年 | 讲师 |
| 周 次 | 课 次 | 授 课 内 容 （标明重点、难点） | 课时 | 主讲教师 | 职 称 | |
| 理论课 | 实验见习讨论 | |||||
| 12 | 11 | 第六章 树 1．教学内容： 6.1线索二叉树的概念 6.2树和森林的遍历 6.3哈夫曼算法 2．教学重点： 1) 线索二叉树的运算 2) 树的存储结构的特点 3. 教学难点： 哈夫曼树算法实现 实验六：二叉树层序遍历的实现 一、实验目的 1、掌握二叉树层序遍历的过程 2、熟悉二叉树层序遍历的实现 二、实验内容 二叉树的层序遍历是按二叉树的层次顺序（即从根结点层至叶结点层），同一层按先左子树再右子树的次序遍历。给定如下图所示的二叉树，请输出对应的层序遍历的序列。 设计参考：可以采用队列结构来实现。 A B F C E G D | 2 | 2 | 唐晓年 | 讲师 |
| 周 次 | 课 次 | 授 课 内 容 （标明重点、难点） | 课时 | 主讲教师 | 职 称 | |
| 理论课 | 实验见习讨论 | |||||
| 13 | 12 | 第七章 图 1．教学内容： 7.1图的基本概念 7.2图的存储结构 7.3图的遍历 7.4深度优先搜索遍历 2．教学重点： 1) 图的存储结构特点 2) 优先搜索遍历 3. 教学难点： 优先搜索遍历算法的实现 实验七：图的广度优先遍历的实现 一、实验目的 1、 掌握图的遍历过程； 2、 理解图的存储结构与基本操作； 2、熟悉图的广度优先遍历的实现 二、实验内容 1 采用邻接矩阵的存储结构保存下图； 2 编程实现该图的创建与广度优先遍历。 提示：连通图的广度优先遍历算法为： （1）访问初始顶点v并标记顶点v为已访问； （2）顶点v入队列； （3）当队列非空时则继续执行，否则算法结束； （4）出队列取得队头顶点u； （5）查找顶点u的第一个邻接顶点w； （6）若顶点u的邻接顶点w不存在，则转到步骤（3），否则循环执行， （6.1）若顶点w尚未被访问则访问顶点w并标记顶点w为已访问； （6.2）顶点w入队列； （6.3）查找顶点u的w邻接顶点后的下一个邻接顶点w，转到步骤（6）。 | 2 | 2 | 唐晓年 | 讲师 |
| 周 次 | 课 次 | 授 课 内 容 （标明重点、难点） | 课时 | 主讲教师 | 职 称 | |
| 理论课 | 实验见习讨论 | |||||
| 14 | 13 | 第七章 图 1．教学内容： 7.1最小生成树的基本概念 7.2普里姆算法 7.3克鲁斯卡尔算法 7.4最短路径 2．教学重点： 1) 生成树和最小生成树 2) 最短路径 3. 教学难点： 优最短路径的算法 实验八：哈夫曼编码的程序设计 一、实验目的 1、掌握哈夫曼树的建立过程 2、熟悉哈夫曼编码的实现 二、实验内容 设有字符集{A,B,C,D},各字符在电文中出现的次数集为{1,3,4,7};要求编程实现哈夫曼树的构造,并在此基础上编程实现哈夫曼编码。 | 2 | 2 | 唐晓年 | 讲师 |
| 周 次 | 课 次 | 授 课 内 容 （标明重点、难点） | 课时 | 主讲教师 | 职 称 | |
| 理论课 | 实验见习讨论 | |||||
| 15 | 14 | 第九章 排序 9.1排序的基本概念 9.2交换排序 9.3选择排序 2．教学重点： 1) 排序的概念 2) 冒泡排序 3. 教学难点： 冒泡排序的实现 实验九：插入排序算法的实现 一、实验目的 1、理解插入排序思想 2、掌握直接插入排序的实现方法 3、掌握希尔排序的实现方法 二、实验内容 编写直接插入排序和希尔排序的实现程序，并编写测试函数，测试数据为（43，5，47，1，19，43，11，59，15，48，41），其中希尔排序增量d=5,3,1。 提示： 1.直接插入排序算法思想：顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。 2.希尔排序算法思想：将相隔某个增量d的记录组成一个小组, 对同一小组内的数据元素用直接插入法排序；让增量dk逐趟缩短（例如依次取5,3,1），直到dk＝1为止。 | 2 2 | 唐晓年 | 讲师 | |
| 周 次 | 课 次 | 授 课 内 容 （标明重点、难点） | 课时 | 主讲教师 | 职 称 | |
| 理论课 | 实验见习讨论 | |||||
| 16 17 | 15 16 | 第九章 排序 9.1归并排序的基本概念 9.2基数排序 9.3外排序排序 2．教学重点： 1) 归并排序的概念 2) 内部排序 3. 教学难点： 外排序的实现 实验十：折半查找递归算法 一、实验目的 1．理解递归调用的实现过程 2．学会递归程序的设计方法 二、实验内容 1.编写折半查找的递归程序。 2.在VC++的调试环境下观察折半查找递归程序的调用与返回过程,并记录其过程和返回值。 3.设计一个折半查找的循环结构的算法,并与递归算法进行对比分析。 提示：将要查找的元素key与查找区间正中元素相比，若key小，则查找区间缩小至前半部份查找，若key大，则查找区间缩小至后半部份查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。如递归实现，考虑函数的参数应有哪些。在用循环结构实现时，函数的参数有什么变化？ 复习和答疑 | 2 | 2 | 唐晓年 | 讲师 |
