数据结构教案.docx

1、数据结构教案数 据 结 构教 案 安徽财经大学信息工程学院二00六年九月 教案专用页内容（标题）第1章 绪论课时3课时教学目的及要求教学目的:介绍数据结构中常用的基本概念和术语以及学习数据结构的意义。基本概念和术语；学习数据结构的意义；算法的描述和分析。教学要求：了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。重点难点及其处理重点：数据结构的基本概念和术语，了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系，算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。难点：算法复杂度的分析方法。算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。算法的

2、时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。处理：通过对一些已学习过的数据类型进行分析，由此引申出数据结构的概念。通过一些算法举例，来说明具体的算法如何分析时间复杂度。教学方法课堂讲授与课下作业相结合。参考文献1朱若愚.数据结构（第二版）.北京：电子工业出版社，20012张绍民.数据结构教程（C语言版）.北京：中国电力出版社，2002课外作业及要求估算冒泡排序法的时间复杂度后记 教案专用页内容（标题）第2章 线性表2.1 线性表的逻辑结构2.2 线性表的顺序存储结构课时3课时教学目的及要求教学目的：介绍线性表的逻辑结构和顺序存储表示方法，以及定义在逻辑结构上的各种基本运算及其

3、在顺序存储结构上如何实现这些基本运算。教学要求：在熟悉顺序存储结构的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。重点难点及其处理重点： 线性表的逻辑结构。 线性表的逻辑结构特征。 线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算。顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。顺序表上的插入、删除操作及其平均时间性能分析。难点：顺序表上实现的各种基本算法及相关的时间性能分析利用顺序表设计算法解决筒单的应用问题。 处理：通过和C程序设计课程中学过的数组相比较，来引入线性表。使用本章所学到的基本知识设计有效

4、算法解决与线性表相关的应用问题。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参考文献1朱若愚.数据结构（第二版）.北京：电子工业出版社，20012张绍民.数据结构教程（C语言版）.北京：中国电力出版社，20023胡学钢.数据结构算法设计指导.北京：清华大学出版社，2001课外作业及要求后记 教案专用页内容（标题）第2章 线性表2.3 线性表的链式存储结构2.4 顺序表和链表的比较课时3课时教学目的及要求教学目的：介绍线性表的链式存储表示方法，以及定义在链式结构上的各种基本运算及其在各种链表上如何实现这些基本运算。教学要求：在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选

5、择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。重点难点及其处理重点： 链表如何表示线性表中元素之间的逻辑关系。 单链表、双链表、循环链表链接方式上的区别。 单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。 双链表的定义及其相关的算法 顺序表和链表的比较熟练掌握单链表上实现的各种基本算法及相关的时间性能分析，难点： 链表中头指针和头结点的使用。 循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。 针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。处理：能够使用本章所学到的基本知识

6、设计有效算法解决与线性表相关的应用问题。利用链表设计算法解决简单的应用问题。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参考文献1朱若愚.数据结构（第二版）.北京：电子工业出版社，20012张绍民.数据结构教程（C语言版）.北京：中国电力出版社，20023胡学钢.数据结构算法设计指导.北京：清华大学出版社，2001课外作业及要求1试写出一个计算链表中数据元素结点个数的算法，其中指针p指向读链表的第一个结点2试设计实现在单链表中删去值相同的多余结点的算法3有一个线性表(a1，a2，an)，它存储在有附加表头结点的单链表中，写一个算法，求出该线性表中值为x的元素的序号如果x不存在，则输

7、出序号为04写一个算法将一单链表逆置要求操作在原链表上进行5在一个非递减有序线性表中，插入一个值为x的元素，使插入后的线性表仍为非递减有序。分别用向量和单链表编写算法后记 教案专用页内容（标题）第3章 栈和队列3.1 栈的逻辑结构、存储结构及其相关算法课时3课时教学目的及要求教学目的：介绍栈的逻辑结构定义及在两种存储结构上如柯实现栈的基本运算。教学要求：要求在掌握栈的特点的基础上，懂得在什么样的情况下能够使用栈。重点难点及其处理重点：栈的逻辑结构特点，栈与线性表的异同。顺序栈上实现的进栈、退栈等基本算法。栈的“上溢”和“下溢”的概念及其判别条件。掌握栈和队列在两种存储结构上实现的基本运算。难点

8、：是栈中对边界条件的处理。利用栈设计算法解决筒单的应用问题。处理：通过现实生活中的例子来理解栈的特点，通过对栈的逻辑结构、存储结构的深入分析来理解栈的相关算法。通过栈的应用来掌握栈的特点，什么样的情况下能够使用栈。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参考文献1赵文静.数据结构C+语言描.西安：西安交通大学出版社，20012. 殷人昆.数据结构（用面向对象方法与C+描述）.北京： 清华大学出版社，20023苏运霖.数据结构与算法.武汉：中南工业大学出版社，1999课外作业及要求1假定有编号为A、B、C、D的4辆列车，顺序开进一个栈式结构的站台，请写出开出车站站台的列车顺序(注

9、：每一列车由站台开出时均可进栈，出栈开出站台，但不允许出栈后回退)。写出每一种可能的序列2已知堆栈采用链式存储结构，初始时为空，试画出a，b、c、d 4个元素依次进栈以后堆栈的状态，然后再画出此时的栈顶元素出栈后的状态3写出链栈的取栈顶元素和置栈空的算法4写出多个链表栈中取第j个链表栈顶元素值的算法。5写出计算表达式3+4/25*8-6时操作数栈和运算符栈的变化情况后记 教案专用页内容（标题）第3章 栈和队列3.1队列的逻辑结构、存储结构及其相关算法课时3课时教学目的及要求教学目的：介绍队列的逻辑结构定义及在两种存储结构上如柯实现队列的基本运算。要求在掌握队列的特点的基础上，懂得在什么样的情况

10、下能够使用队列。重点难点及其处理重点：队列在两种存储结构上实现的基本运算，队列的逻辑结构特点，队列与线性表的异同。顺序队列(主要是循环队列)和链队列上实现的入队、出队等基本算法。队列的“上溢”和“下溢”的概念及其判别条件。使用数组实现的循环队列取代普通的顺序队列的原因。难点：循环队列中对边界条件的处理。队列的逻辑结构、存储结构及其相关算法。处理：通过举例来说明队列这种数据结构的使用，利用队列设计算法解决筒单的应用问题。最终能够掌握队列的应用，领会队列的特点，知道什么样的情况下能够使用队列。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参考文献1赵文静.数据结构C+语言描.西安：西安交

11、通大学出版社，20012. 殷人昆.数据结构（用面向对象方法与C+描述）.北京： 清华大学出版社，20023苏运霖.数据结构与算法.武汉：中南工业大学出版社，1999课外作业及要求1课文中规定：无论是循环队列还是链表队列，队头指针总是指向队头元素的前一位置，队尾指针指向队尾元素试画出有两个元素A、B的不同存储结构的图示，及将这两个元素出队后循环队列和链表队列的状态示意图2对于一个具有m个单元的循环队列，写出求队列中元素个数的公式3对于一个具有n个单元(n2)的循环队列，若从进入第一个元素开始，每隔11个时间单位进入下一个元素，同时从进入第一个元素开始，每隔t2(t2t1)个时间单位处理完一个元

12、素并令其出队。试编写一个算法，求出在第几个元素进队时将发生溢出。4假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写出相应的置空队列，入队列和出队列的算法。后记 教案专用页内容（标题）第4章 串课时3课时教学目的及要求教学目的：介绍串的逻辑结构、存储结构及其中上的基本运算，由于C语言及其它高级语言均已具备了较强的串处理功能，主要掌握串的模式匹配算法。教学要求：掌握串上实现的模式匹配算法。重点难点及其处理重点：1.串及其运算 1.1 串的有关概念及基本运算。 1.2 串与线性表的关系。2.中的存储结构 2.1 串的两种存储表示。 2.2 串上实现的模式匹

13、配算法及其时间性能分析。 难点：掌握串上实现的模式匹配算法。 处理： 通过多媒体演示来展现模式匹配的过程，详细演示了KMP算法。使用C语言提供的串操作函数构造与中相关的算法解决简单的应用问题。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参考文献1赵文静.数据结构C+语言描.西安：西安交通大学出版社，20012. 殷人昆.数据结构（用面向对象方法与C+描述）.北京： 清华大学出版社，20023苏运霖.数据结构与算法.武汉：中南工业大学出版社，1999课外作业及要求1假设所使用的字符串采用数组存储。试用C语言编写一个求字符串长度的函数定义2假设所使用的字符串采用数组存储试用C语言编写一

14、个实现字符串复制的函数定义。3假设所使用的字符串采用链接存储结构，链表中每个结点存放m(m4)个字符试用C语言编写一个实现字符串删除的函数定义4假设所使用的字符串采用数组存储。试用C语言编写一个函数，将字符中string2的头n个字符添加到字符串string1的尾部，并以结束后记 教案专用页内容（标题）第5章 数组和广义表5.1 多维数组5.2 矩阵的压缩存储课时3课时教学目的及要求教学目的：介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法。 教学要求： 领会多维数组的概念 掌握矩阵的压缩存储的方法 熟练掌握稀疏矩阵的三元组表示法重点难点及其处理重点：多维数组的逻辑结构

15、特征。多维数组的顺序存储结构及地址计算方式。矩阵的压缩存储方式、特殊矩阵和压缩存储时的下标变换方法。稀疏矩阵的三元组表表示方法及有关算法。难点：数组是一种随机存取结构的原因。稀疏矩阵的压缩存储表示下实现的算法。处理： 通过对线性代数中矩阵的引入来理解多维数组，并结合矩阵运算来理解稀疏矩阵。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参考文献1赵文静.数据结构C+语言描.西安：西安交通大学出版社，20012. 殷人昆.数据结构（用面向对象方法与C+描述）.北京： 清华大学出版社，20023苏运霖.数据结构与算法.武汉：中南工业大学出版社，1999课外作业及要求1. 设有一个n维数组A

16、d1d2.dn，求loc(Ai1,i2,.,in)。2已知二维数组A46其每个元素占三个存储单元，且A00的存储地址为1200，试求元素A24的存储地址(分别讨论以行序和列序为主序方式进行分配时的结论)该数组共占用多少单元?3设A和B分别为上、下三角形矩阵，每一个都有n行试设计一个方案，将A和B放到数组Cnn+1中，井写出确定C数组元素值的算法。4已知An为整型数组，试写出实现下列运算的算法： (1)求数A中的最大整数。 (2)求n个整数之和。 (3)求n个整数的平均值5已知稀疏矩阵A65如下所示，试写出它的三元组表与十字链表6若稀疏矩阵采用三元组表示，请写出求两个具有相同行列数的稀疏矩阵的相

17、加的算法后记 教案专用页内容（标题）第5章 数组和广义表5.3 广义表课时3课时教学目的及要求教学目的：领会广义表的概念，掌握广义表的表示方法，学会广义表的基本算法。教学要求： 掌握广义的两种表示方法。 掌握广义表的表头表尾运算。 掌握广义表的访问方法。重点难点及其处理重点：广义表的定义求表头和表尾的运算.广义表与线性表的区别难点：广义表的有关概念及其与线性表的关系。广义表的括号表示和图形表示之间的转换。求给定的非空广义表的表头和表尾运算。处理：广义表是一种递归的结构，通过一些实例来理解广义表的构成。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参考文献1赵文静.数据结构C+语言描.

18、西安：西安交通大学出版社，20012. 殷人昆.数据结构（用面向对象方法与C+描述）.北京： 清华大学出版社，20023苏运霖.数据结构与算法.武汉：中南工业大学出版社，1999课外作业及要求1已知下列广义表，画出其存储结构： (1)A(a，(b，c，d)，c，(f，g) (2)B(a) (3)C(y， (z，w)， (x，z，w)，a) (4)D(x，(y)，B)，D)2. 写出上题中各广义表的长度及深度3对上题中各广义表，写出： HEAD(A)? TAI1(A)?后记 教案专用页内容（标题）第6章 树6.1 树的概念6.2 二叉树课时3课时教学目的及要求教学目的：介绍树的定义，树的各种存储

19、结构，二叉树的定义、性质、存储结构、教学要求：在熟悉树和二叉树的基础上， 掌握二叉树的基本概念及其有关应用。重点难点及其处理重点：树的概念树和二叉树的常用术语及含义二叉树的递归定义及树与二叉树的差别。二叉树的性质，了解相应的证明方法。 难点：二叉树的两种存储方法、特点及适用范围二叉树的性质使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。 处理： 对于树的概念，通过现实中组织结构图来引入，增强对树这种结构的理解，对于二叉树要强调它本身的特点，整理归纳二叉树的术语，强调二叉树的性质。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参考文献1黄定.数据结构与算法.广州

20、：广东科技出版社，20002徐士良.实用数据结构.北京：清华大学出版社，19983美Bruno R.Preiss.数据结构与算法面向对象的C+设计模式.北京：电子工业出版社，2001课外作业及要求1对于3个结点A，B，C，可组成多少种不同的二叉树?请画出。2如果一棵树有n1个度为1的结点，n2个度为2的结点，nm个度为m的结点，则该树共有多少个叶子结点(n0=?)?可参考二叉树性质3的证明方法来思考m叉树问题。3写出图625中所示的树的叶子结点，非终端结点，各结点的度和树深4将图626中的树转换为二叉树对转换后的二叉树按先根、中根、后根次序遍历的结点序列后记 教案专用页内容（标题）第6章 树6

21、.3 二叉树的遍历6.4 线索二叉树课时3课时教学目的及要求教学目的：了解二叉树遍历的基本方法，遍历时访问节点的先后次序。能够掌握遍历二叉树来解决复杂的问题。教学要求：掌握二叉树的遍历算法及其有关应用。重点难点及其处理重点：二叉树的三种遍历算法，理解其执行过程。确定三种遍历所得到的相应的结点访问序列。以遍历算法为基础，设计有关算法解决简单的应用问题。二叉树线索化的目的及实质。难点：确定三种遍历所得到的相应的结点访问序列。二叉树线索化的目的及实质。在中序线索树中查找给定结点的中序前趋和中序后继的方法。查找给定结点的前序前趋和后序后继井非有效的原因。处理： 通过演示二叉树的遍历过程来增强对访问节点

22、序列的理解。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参考文献1黄定.数据结构与算法.广州：广东科技出版社，20002徐士良.实用数据结构.北京：清华大学出版社，19983美Bruno R.Preiss.数据结构与算法面向对象的C+设计模式.北京：电子工业出版社，2001课外作业及要求1写出先根遍历的非递归算法2写出按层遍历二叉树的算法3写一个算法求二叉树中结点总数你能写出多少种方法?4现有按后根遍历二叉树的结果为C，B，A，有几种不同的二叉树可以得到这一结果?5现有按先根和中根遍历某二叉树的结果，试画出这棵二叉树，形状唯一吗?为什么?先根遍历：ABCDEFGHI，中根遍历；BC

23、AEDGHFI后记 教案专用页内容（标题）第6章 树6.5 树和森林6.6 哈夫曼树及其应用课时3课时教学目的及要求教学目的：树和森林与二又树之间的转换方法。树的各种存储结构及其特点。树的两种遍历方法。哈夫曼算法的思想根据给定的叶结点及其权值构造出相应的最优二叉树教学要求：掌握树的存储方法和树和森林的转化方法。掌握哈夫曼树的构造方法，根据最优二叉树构造对应的哈夫曼编码。重点难点及其处理重点： 树和森林与二又树之间的转换方法。最优二叉树和最优前缀码的概念及特点。哈夫曼算法的思想。根据给定的叶结点及其权值构造出相应的最优二叉树。根据最优二叉树构造对应的哈夫曼编码。难点：哈夫曼算法的思想哈夫曼树及其

24、应用，根据最优二叉树构造对应的哈夫曼编码 处理： 通过幻灯演示哈夫曼编码的过程来加强对哈夫曼编码的理解。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参考文献1黄定.数据结构与算法.广州：广东科技出版社，20002徐士良.实用数据结构.北京：清华大学出版社，19983美Bruno R.Preiss.数据结构与算法面向对象的C+设计模式.北京：电子工业出版社，2001课外作业及要求1有一组数值14，21，32，15，28，画出哈夫曼树的生成过程及最后结果2凡二叉树都只能用二叉链表来存储，这种说法是否正确?满二叉树和完全二叉树用什么存储结构更适合?书中哈夫曼算法的实现，用的是什么存储结构

25、?后记 教案专用页内容（标题）第8章 查找8.1 查找表的基本概念8.2 线性表的查找课时3课时教学目的及要求教学目的：介招顺序查找、二分查找、分块查找的基本思想、算法实现和查找效率分析。教学要求：掌握顺序查找、二分查找，查找的基本思想和算法实现。通过比较线性表上三种查找方法的优缺点，能根据实际问题的要求和特点，选择出合适的查找方法。重点难点及其处理重点： 静态查找表和动态查找表的基本概念 顺序查找的基本思想和算法实现。 二分查找的基本思想和算法实现难点： 顺序查找中哨兵的使用方法。 二分查找的算法实现。 处理： 通过分析线性表的查找方法，对比顺序查找的算法思想，来引入顺序查找。通过对有序表的

26、分析，引入折半查找的思想。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参考文献1黄定.数据结构与算法.广州：广东科技出版社，20002徐士良.实用数据结构.北京：清华大学出版社，19983美Bruno R.Preiss.数据结构与算法面向对象的C+设计模式.北京：电子工业出版社，2001课外作业及要求1设有一个有序文件，其中各记录的关键字为：1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，当用折半查找算法查找关键字为2，10、17时，其比较次数分别为多少?2用C语言改写折半查找程序，使其成为递归过程并上机验证3设单链表的结点是按关键字从小到大排列的，试写出对

27、此链表的查找算法，并说明是否可以采用折半查找4若对大小均为n的有序顺序表和无序顺序表分别进行查找，试就下列三种情况分别讨论两者在等查找概率时，平均查找长度是否相同： (1)查找失败； (2)查找成功； (3)查找成功，表中有多个关健字等于给定值的记录，一次查找要求找出所有记录后记 教案专用页内容（标题）第8章 查找8.4 树的查找8.5 散列技术课时3课时教学目的及要求教学目的：介招二叉查找树和B-树的定义和特点以及用途介绍二叉查找树的插入、删除、建树和查找算法及时间性能。了解B-树的插入、删除及查找方法的基本思想。掌握散列表、散列函数的概念和几种常用的散列函数构造方法。教学要求：掌握二叉查找

28、树上查找以及散列表上查找的基本思想和算法实现。重点难点及其处理重点： 二叉查找树和B树的定义和特点以及用途 二叉查找树的插入、删除、建树和查找算法及时间性能 B树的插入、删除及查找方法 散列表、散列函数、散列地址和装填因子等有关概念 几种常用的散列函数构造方法难点： 二叉查找树的删除算法 B树上的插入和删除算法。 两类解决冲突的方法及其优缺点处理：举例了解散列函数的选取原则及产生冲突的原因。深入分析采用线性探测法和拉链法解决冲突时，散列表的建表方法、查找过程以及算法实现和时间分析。比较散列表和其它表的本质区别。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参考文献1黄定.数据结构与算法.广州：广东科技出版社，20002徐士良.实用数据结构.北京：清华大学出版社，19983美Bruno R.Preiss.数据结构与算法面向对象的C+设计模式.北京：电子工业出版社，2001课外作业及要求1什么叫二叉平衡树?试按下列次序将各关键字插入到二叉平衡树中，画出重新平衡的情况关键字依次为；8，9，10，2，1，5，3，6，7，