信息管理与信息系统教研室、医学信息工程教研室（合署）

理论课

实验见习讨论

1

1

C语言补充知识：结构体数据类型

教学内容：

教学重点

教学难点：

2

唐晓年

讲师

周

次

课

次

授         课         内         容

（标明重点、难点）

课时

主讲教师

职

称

理论课

实验见习讨论

2

3

2

3

C语言补充知识：指针

教学内容：

教学重点

教学难点：

2

2

2

唐晓年

讲师

周

次

课

次

授         课         内         容

（标明重点、难点）

课时

主讲教师

职

称

理论课

实验见习讨论

4

4

C语言补充知识：预定义和结构体指针

教学内容：

教学重点

教学难点：

2

2

唐晓年

讲师

理论课

实验见习讨论

5

5

教学内容：

教学重点

教学难点：

2

2

唐晓年

讲师

周

次

课

次

授         课         内         容

（标明重点、难点）

课时

主讲教师

职

称

理论课

实验见习讨论

6

6

第二章  线性表

教学内容：

2．教学重点：

1) 掌握算线性表的基本概念

2) 掌握单链表上的基本算法

3. 教学难点：

线性表的逻辑结构     

实验一：顺序表的建立与查找

一、实验目的

1、掌握建立顺序表的基本方法。

2、理解和掌握顺序表元素查找算法。

3、掌握顺序表的插入、删除算法的思想和实现。

二、实验内容

1、 建立一个顺序表，要求从键盘输入10个整数，并将该顺序表的元素从屏幕显示出来

2、编写查找函数，在上面的顺序表中查找其中一个元素，如果找到，返回该元素在顺序表中的位置和该元素的值，否则提示无此元素。要求被查找元素从键盘输入。

3、编写插入和删除函数，由用户输入待插入元素及插入位置，将完成插入后的顺序表输出；由用户输入删除第几个元素，将完成删除后的顺序表输出。

2

2

唐晓年

讲师

理论课

实验见习讨论

7

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

唐晓年

讲师

理论课

实验见习讨论

8

8

第三章  栈和队列

1. 教学内容：                                            

4.1 栈的定义及其运算

4.2 栈的顺序存储结构

4.3栈的链式存储结构

2．教学重点

1) 掌握栈的定义及其运算方法

2) 了解栈的顺序存储结构和链式存储结构

3. 教学难点：

栈的顺序存储结构和链式存储结构

实验三：栈的应用—括号匹配

一、实验目的

    1．掌握堆栈特殊线性表的存储方式的基本操作方法。

2．掌握堆栈后进先出运算原则在解决实际问题中的应用。

3．掌握使用栈的原理来解决表达式中的括号配对问题。

二、实验内容

 假设一个算术表达式中包含圆括弧、方括弧三种类型的括弧，编写一个程序用于判别表达式中括弧是否正确配对。

说明：检验表达式中的括号匹配情况：假设在一个算术表达式中，可以包含三种括号：圆括号"（"和"）"，方括号"["和"]"，并且这两种括号可以按任意的次序嵌套使用。比如，...[......[...]...]...(...)..。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。

提示：

算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。

（1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；

（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；

（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。

算法步骤：扫描表达式，

1）凡出现左括弧，则进栈；

2）凡出现右括弧，首先检查栈是否空。

   若栈空，则表明该“右括弧”多余

   否则和栈顶元素比较，

       若相匹配，则“左括弧出栈”

       否则表明不匹配

3）表达式检验结束时，

   若栈空，则表明表达式中匹配正确

   否则表明“左括弧”有余

栈的类型定义及基本操作代码可参考教材相关定义和程序。

2

2

唐晓年

讲师

理论课

实验见习讨论

9

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

唐晓年

讲师

理论课

实验见习讨论

10

11

10

11

   第六章  树

1．教学内容：

6.1什么是树？        

6.2二叉树的概念

6.3二叉树的性质

实验五：树的5种性质地应用，二叉树的遍历方法，二叉树的结构体定义

6.4遍历二叉树的递归算法

2．教学重点：

1) 二叉树三种遍历运算

2) 二叉树遍历的特点

3. 教学难点：

二叉树算法实现

2

2

唐晓年

讲师

理论课

实验见习讨论

12

12

6.5遍历二叉树的非递归算法     

2．教学重点：

1) 非递归算法的实现

2) 递归和非递归算法的区别

3. 教学难点：

非递归算法的实现

实验六：二叉树递归和非递归遍历算法的实现

一、实验目的

1、掌握二叉树的建立方法

2、掌握二叉树遍历的基本方法（前序、中序、后序）

3、掌握递归二叉树遍历算法的应用

二、实验内容

1.构造一棵二叉树,树的形态如下图所示，打印出前序遍历、中序遍历、后序遍历的遍历序列。

2

2

唐晓年

讲师

周

次

课

次

授         课         内         容

（标明重点、难点）

课时

主讲教师

职

称

理论课

实验见习讨论

13

13

   第六章 树

1．教学内容：

6.1线索二叉树的概念        

6.2树和森林的遍历

6.3哈夫曼算法

2．教学重点：

1) 线索二叉树的运算

2) 树的存储结构的特点

3. 教学难点：

哈夫曼树算法实现

实验六：二叉树层序遍历的实现

一、实验目的

1、掌握二叉树层序遍历的过程

2、熟悉二叉树层序遍历的实现

二、实验内容

 二叉树的层序遍历是按二叉树的层次顺序（即从根结点层至叶结点层），同一层按先左子树再右子树的次序遍历。给定如下图所示的二叉树，请输出对应的层序遍历的序列。

设计参考：可以采用队列结构来实现。

                 A

          B               F

    C                  E      G

        D

2

2

唐晓年

讲师

理论课

实验见习讨论

14

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

唐晓年

讲师