数据结构 - 大连职业技术学院 - 信息工程学院.doc

1、- 1 -第 1 次课 教案2008 年 3 月 3 日 星期一章 节： 第 1 章 绪 论1.1 引言1.2 基本概念和术语1.3 算法描述1.4 算法分析教学任务：了解：数据结构的基本概念掌握：数据的逻辑结构和存储结构算法描述和分析的方法。重点、难点：重点：数据结构的基本概念难点：算法分析的方法教学内容提要：1.1 引言1.2 基本概念和术语1.3 算法描述1.3.1 算法的 5 个重要特性1.3.2 数据结构上的基本操作- 2 -1.3.3 算法的描述方法1.4 算法分析1.4.1 算法设计的要求：易读性、健壮性、高效率。1.4.2 算法时间效率的度量分析1.4.2 算法空间效率的度量分

2、析复习 1：结构体类型变量的输入与输出。复习 2：编程实现对一给定实型数组的下列操作小结本课内容思考题：1.1 简述下列术语： 数据、数据元素、数据逻辑的结构、数据的存储结构、算法。1.2 分析下面语句段执行的时间复杂度。(1) for (i = 1; i = n ; i +)for (j = 1; j = n ; j +) s +;(2) for (i = 1; i = n ; i +)for (j = i; j = n ; j +) s +;(3) for (i = 1; i = n ; i +)for (j = 1; j = i; j +) s +;(4) i = 1; k = 0;wh

3、ile (i = n - 1) k += 10 * i; i +; 课后小结： - 3 -第 2 次课 教案2008 年 3 月 7 日 星期五章 节： 第 2 章 线性表2.1 线性表的基本概念教学任务：了解：线性表的定义、逻辑结构、基本操作掌握：线性表的运算重点、难点：重点：线性表的定义难点：线性表中的元素地址的计算方法教学内容提要：复习上一节内容2.1 线性表的基本概念2.1.1 线性表的逻辑结构1、线性表的定义2、线性表的特征2.1.2 线性表的基本操作(1) INITIATE（L）初始化操作函数(2) LENGTH（L）求表长度的函数。(3) GET（L, i) 取表中元素的函数。(

4、4) LOCATE（L , x）定位函数。- 4 -(5) INSERT(L, b, i)插入操作。(6) DELETE(L, i)删除操作。(7) EMPTY(L) 判空表函数。(8) CLEAR(L)表置空操作。2.1.3 线性表的顺序存储结构1. 顺序表的定义2. 顺序表的特点3. 表中任意元素的地址计算公式4. 顺序表的数据类型5. 线性表的存储特点小结本课内容思考题：如果线性表以顺序方式存储，每个元素的类型为long，首元素 a1 的存储地址为 0x3000,那么 a7 的存储地址是_?课后小结： - 5 -第 3 次课 教案2008 年 3 月 10 日 星期一章 节： 第 2 章

5、 线性表2.2 顺序存储的线性表教学任务：了解：顺序表的初始化及算法时间复杂度分析掌握：顺序表的数据类型及插入算法的实现重点、难点：重点：基本操作在顺序表上的实现难点：顺序表插入新元素的算法实现教学内容提要：复习上一节内容2.2.1 顺序表的插入算法1. 数据类型描述2. 算法思路3. 移动次序4. 数组的下标5. 顺序表初始化函数6. 顺序表中插入一个元素的算法- 6 -7. 算法的平均时间复杂度2.2.2 顺序表上元素的删除算法：1. 算法思路2. 移动次序3. 顺序表中删除 i 号元素的算法4. 算法的平均时间复杂度2.2.3 顺序表上元素的定位1. 算法思路2. 顺序表中定位元素的算法

6、实现3. 该算法的平均时间复杂度小结本课内容思考题：设有两个按元素值递增有序的顺序表 A 和 B，编一程序将 A 表和 B 表归并成一个新的递增有序的顺序表 C（值相同的元素均保留在 C 表中） 。课后小结： - 7 -第 4 次课 教案2008 年 3 月 14 日 星期五章 节： 第 2 章 线性表顺序表综合实训教学任务：了解：顺序表各基本算法的实际应用掌握：顺序表各基本算法的实现重点、难点：重点：加深理解顺序表各基本算法的实现方法难点：顺序表变量的作用域。教学内容提要：复习上一节内容顺序表综合实训例 2.1 将所有在顺序表 lb 中存在而在顺序表 la中不存在的数据元素插入到 la 表中

7、。1、算法的设计思路2、算法的实现3、该算法的平均时间复杂度例 2.2 写一算法输出已知顺序表 A 中元素的最大值和次最大值，编写 C 语言程序进行测试。- 8 -1、算法的设计思路2、算法的实现3、该算法的平均时间复杂度例 2.3 设一顺序表 a 中元素值递增有序。写一算法，将元素 x 插到表中适当的位置，并保持顺序表a 的有序性。1、算法的设计思路2、算法的实现3、该算法的平均时间复杂度例 2.4 设一顺序表 L 中元素值递增有序。写一算法，删除表中值相同的元素，使之只保留一个（去偶） 。1、算法的设计思路2、算法的实现3、该算法的平均时间复杂度小结本课内容作业题：定义线性表的顺序存储结构

8、，编写算法：第 i个结点前插入新元素，编写算法：删除第 i 个结点，编写算法：删除值为 x 的结点（书面作业）课后小结： - 9 -第 5 次课 教案2008 年 3 月 17 日 星期一章 节： 第 2 章 线性表2.3 线性表的链式存储结构教学任务：掌握：1、概念链表、头指针、头结点、元素结点、首元素结点2、单链表上的基本算法重点、难点：重点：建立链表的思路难点：指向结点的指针变量的使用要领。教学内容提要：复习上一节内容顺序表的优点和缺点2.3 线性表的链式存储结构1. 链表的定义2. 头指针的定义3. 首元素结点4. 用 C 语言描述单链表的结点结构2.3.1 单链表结构类型定义：- 10 -typedef struct node DataType data;Struct node *next;LinkList;单链表示意图2.3.2 单链表上的基本运算1建立单链表：(1) 头插入法建表(2) 尾插入法建表2 查找运算：(1) 按序号查找(2) 按值查找小结本课内容思考题：设有两个线性表 A 和 B 皆是单链表存储结构。同一个表中的元素各不相同，且递增有序。写一算法，构成一个新的线性表 C，使 C 为 A 和 B 的交集，且 C 中元素也递增有序。课后小结：