数据结构教案.docx

数据结构教案.docx

《数据结构教案.docx》由会员分享，可在线阅读，更多相关《数据结构教案.docx（25页珍藏版）》请在冰点文库上搜索。

数据结构教案

数据结构

教案

安徽财经大学信息工程学院

二00六年九月

教案专用页

内容

（标题）

第1章绪论

课时

3课时

教学目的及要求

教学目的:

介绍数据结构中常用的基本概念和术语以及学习数据结构的意义。

⑴基本概念和术语；

⑵学习数据结构的意义；

⑶算法的描述和分析。

教学要求：

了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。

重点难点及其处理

重点：

⑴数据结构的基本概念和术语，

⑵了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系，

⑶算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。

难点：

算法复杂度的分析方法。

算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。

算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。

处理：

通过对一些已学习过的数据类型进行分析，由此引申出数据结构的概念。

通过一些算法举例，来说明具体的算法如何分析时间复杂度。

教学方法

课堂讲授与课下作业相结合。

参考文献

1．朱若愚.数据结构（第二版）.北京：

电子工业出版社，2001

2．张绍民.数据结构教程（C语言版）.北京：

中国电力出版社，2002

课外作业及要求

估算冒泡排序法的时间复杂度

后记

教案专用页

内容

（标题）

第2章线性表

2.1线性表的逻辑结构

2.2线性表的顺序存储结构

课时

3课时

教学目的及要求

教学目的：

介绍线性表的逻辑结构和顺序存储表示方法，以及定义在逻辑结构上的各种基本运算及其在顺序存储结构上如何实现这些基本运算。

教学要求：

在熟悉顺序存储结构的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。

重点难点及其处理

重点：

⑴线性表的逻辑结构。

⑵线性表的逻辑结构特征。

⑶线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算。

⑷顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。

⑸顺序表上的插入、删除操作及其平均时间性能分析。

难点：

⑴顺序表上实现的各种基本算法及相关的时间性能分析

⑵利用顺序表设计算法解决筒单的应用问题。

处理：

通过和C程序设计课程中学过的数组相比较，来引入线性表。

使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。

教学方法

课堂讲授与课下作业相结合，鼓励学生自学上机实习。

参考文献

1．朱若愚.数据结构（第二版）.北京：

电子工业出版社，2001

2．张绍民.数据结构教程（C语言版）.北京：

中国电力出版社，2002

3．胡学钢.数据结构算法设计指导.北京：

清华大学出版社，2001

课外作业及要求

后记

教案专用页

内容

（标题）

第2章线性表

2.3线性表的链式存储结构

2.4顺序表和链表的比较

课时

3课时

教学目的及要求

教学目的：

介绍线性表的链式存储表示方法，以及定义在链式结构上的各种基本运算及其在各种链表上如何实现这些基本运算。

教学要求：

在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。

重点难点及其处理

重点：

⑴链表如何表示线性表中元素之间的逻辑关系。

⑵单链表、双链表、循环链表链接方式上的区别。

⑶单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。

⑷双链表的定义及其相关的算法

⑸顺序表和链表的比较

熟练掌握单链表上实现的各种基本算法及相关的时间性能分析，

难点：

⑴链表中头指针和头结点的使用。

⑵循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。

⑶针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。

处理：

能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。

利用链表设计算法解决简单的应用问题。

教学方法

课堂讲授与课下作业相结合，鼓励学生自学上机实习。

参考文献

1．朱若愚.数据结构（第二版）.北京：

电子工业出版社，2001

2．张绍民.数据结构教程（C语言版）.北京：

中国电力出版社，2002

3．胡学钢.数据结构算法设计指导.北京：

清华大学出版社，2001

课外作业及要求

1．试写出一个计算链表中数据元素结点个数的算法，其中指针p指向读链表的第一个结点．

2．试设计实现在单链表中删去值相同的多余结点的算法．

3．有一个线性表（a1，a2，…，an），它存储在有附加表头结点的单链表中，写一个算法，求出该线性表中值为x的元素的序号．如果x不存在，则输出序号为0．

4．写一个算法将一单链表逆置．要求操作在原链表上进行．

5．在一个非递减有序线性表中，插入一个值为x的元素，使插入后的线性表仍为非递减有序。

分别用向量和单链表编写算法．

后记

教案专用页

内容

（标题）

第3章栈和队列

3.1栈的逻辑结构、存储结构及其相关算法

课时

3课时

教学目的及要求

教学目的：

介绍栈的逻辑结构定义及在两种存储结构上如柯实现栈的基本运算。

教学要求：

要求在掌握栈的特点的基础上，懂得在什么样的情况下能够使用栈。

重点难点及其处理

重点：

⑴栈的逻辑结构特点，栈与线性表的异同。

⑵顺序栈上实现的进栈、退栈等基本算法。

⑶栈的“上溢”和“下溢”的概念及其判别条件。

⑷掌握栈和队列在两种存储结构上实现的基本运算。

难点：

⑴是栈中对边界条件的处理。

⑵利用栈设计算法解决筒单的应用问题。

处理：

通过现实生活中的例子来理解栈的特点，通过对栈的逻辑结构、存储结构的深入分析来理解栈的相关算法。

通过栈的应用来掌握栈的特点，什么样的情况下能够使用栈。

教学方法

课堂讲授与课下作业相结合，鼓励学生自学上机实习。

参考文献

1．赵文静.数据结构——C++语言描.西安：

西安交通大学出版社，2001

2.殷人昆.数据结构（用面向对象方法与C++描述）.北京：

清华大学出版社，2002

3．苏运霖.数据结构与算法.武汉：

中南工业大学出版社，1999

课外作业及要求

1．假定有编号为A、B、C、D的4辆列车，顺序开进一个栈式结构的站台，请写出开出车站站台的列车顺序（注：

每一列车由站台开出时均可进栈，出栈开出站台，但不允许出栈后回退）。

写出每一种可能的序列．

2．已知堆栈采用链式存储结构，初始时为空，试画出a，b、c、d4个元素依次进栈以后堆栈的状态，然后再画出此时的栈顶元素出栈后的状态．

3．写出链栈的取栈顶元素和置栈空的算法．

4．写出多个链表栈中取第j个链表栈顶元素值的算法。

5．写出计算表达式3+4/25*8-6时操作数栈和运算符栈的变化情况．

后记

教案专用页

内容

（标题）

第3章栈和队列

3.1队列的逻辑结构、存储结构及其相关算法

课时

3课时

教学目的及要求

教学目的：

介绍队列的逻辑结构定义及在两种存储结构上如柯实现队列的基本运算。

要求在掌握队列的特点的基础上，懂得在什么样的情况下能够使用队列。

重点难点及其处理

重点：

⑴队列在两种存储结构上实现的基本运算，

⑵队列的逻辑结构特点，队列与线性表的异同。

⑶顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法。

⑷队列的“上溢”和“下溢”的概念及其判别条件。

⑸使用数组实现的循环队列取代普通的顺序队列的原因。

难点：

⑴循环队列中对边界条件的处理。

⑵队列的逻辑结构、存储结构及其相关算法。

处理：

通过举例来说明队列这种数据结构的使用，利用队列设计算法解决筒单的应用问题。

最终能够掌握队列的应用，领会队列的特点，知道什么样的情况下能够使用队列。

教学方法

课堂讲授与课下作业相结合，鼓励学生自学上机实习。

参考文献

1．赵文静.数据结构——C++语言描.西安：

西安交通大学出版社，2001

2.殷人昆.数据结构（用面向对象方法与C++描述）.北京：

清华大学出版社，2002

3．苏运霖.数据结构与算法.武汉：

中南工业大学出版社，1999

课外作业及要求

1．课文中规定：

无论是循环队列还是链表队列，队头指针总是指向队头元素的前一位置，队尾指针指向队尾元素．试画出有两个元素A、B的不同存储结构的图示，及将这两个元素出队后循环队列和链表队列的状态示意图．

2．对于一个具有m个单元的循环队列，写出求队列中元素个数的公式．

3．对于一个具有n个单元（n≥2）的循环队列，若从进入第一个元素开始，每隔11个时间单位进入下一个元素，同时从进入第一个元素开始，每隔t2（t2>t1）个时间单位处理完一个元素并令其出队。

试编写一个算法，求出在第几个元素进队时将发生溢出。

4．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写出相应的置空队列，入队列和出队列的算法。

后记

教案专用页

内容

（标题）

第4章串

课时

3课时

教学目的及要求

教学目的：

介绍串的逻辑结构、存储结构及其中上的基本运算，由于C语言及其它高级语言均已具备了较强的串处理功能，主要掌握串的模式匹配算法。

教学要求：

掌握串上实现的模式匹配算法。

重点难点及其处理

重点：

1.串及其运算

1.1串的有关概念及基本运算。

1.2串与线性表的关系。

2.中的存储结构

2.1串的两种存储表示。

2.2串上实现的模式匹配算法及其时间性能分析。

难点：

掌握串上实现的模式匹配算法。

处理：

通过多媒体演示来展现模式匹配的过程，详细演示了KMP算法。

使用C语言提供的串操作函数构造与中相关的算法解决简单的应用问题。

教学方法

课堂讲授与课下作业相结合，鼓励学生自学上机实习。

参考文献

1．赵文静.数据结构——C++语言描.西安：

西安交通大学出版社，2001

2.殷人昆.数据结构（用面向对象方法与C++描述）.北京：

清华大学出版社，2002

3．苏运霖.数据结构与算法.武汉：

中南工业大学出版社，1999

课外作业及要求

1．假设所使用的字符串采用数组存储。

试用C语言编写一个求字符串长度的函数定义．

2．假设所使用的字符串采用数组存储．试用C语言编写一个实现字符串复制的函数定义。

3．假设所使用的字符串采用链接存储结构，链表中每个结点存放m（m＝4）个字符．试用C语言编写一个实现字符串删除的函数定义．

4．假设所使用的字符串采用数组存储。

试用C语言编写一个函数，将字符中string2的头n个字符添加到字符串string1的尾部，并以''结束．

后记

教案专用页

内容

（标题）

第5章数组和广义表

5.1多维数组

5.2矩阵的压缩存储

课时

3课时

教学目的及要求

教学目的：

介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法。

教学要求：

⑴领会多维数组的概念

⑵掌握矩阵的压缩存储的方法

⑶熟练掌握稀疏矩阵的三元组表示法

重点难点及其处理

重点：

⑴多维数组的逻辑结构特征。

⑵多维数组的顺序存储结构及地址计算方式。

⑶矩阵的压缩存储方式、

⑷特殊矩阵和压缩存储时的下标变换方法。

⑸稀疏矩阵的三元组表表示方法及有关算法。

难点：

数组是一种随机存取结构的原因。

稀疏矩阵的压缩存储表示下实现的算法。

处理：

通过对线性代数中矩阵的引入来理解多维数组，并结合矩阵运算来理解稀疏矩阵。

教学方法

课堂讲授与课下作业相结合，鼓励学生自学上机实习。

参考文献

1．赵文静.数据结构——C++语言描.西安：

西安交通大学出版社，2001

2.殷人昆.数据结构（用面向对象方法与C++描述）.北京：

清华大学出版社，2002

3．苏运霖.数据结构与算法.武汉：

中南工业大学出版社，1999

课外作业及要求

1.设有一个n维数组A[d1][d2]...[dn]，求loc（Ai1,i2,..,in）。

2．已知二维数组A[4][6]．其每个元素占三个存储单元，且A[0][0]的存储地址为1200，试求元素A[2][4]的存储地址（分别讨论以行序和列序为主序方式进行分配时的结论）．该数组共占用多少单元?

3．设A和B分别为上、下三角形矩阵，每一个都有n行．试设计一个方案，将A和B放到数组C[n][n+1]中，井写出确定C数组元素值的算法。

4．已知A[n]为整型数组，试写出实现下列运算的算法：

（1）求数A中的最大整数。

（2）求n个整数之和。

（3）求n个整数的平均值．

5．已知稀疏矩阵A[6][5]如下所示，试写出它的三元组表与十字链表．

6．若稀疏矩阵采用三元组表示，请写出求两个具有相同行列数的稀疏矩阵的相加的算法．

后记

教案专用页

内容

（标题）

第5章数组和广义表

5.3广义表

课时

3课时

教学目的及要求

教学目的：

领会广义表的概念，掌握广义表的表示方法，学会广义表的基本算法。

教学要求：

掌握广义的两种表示方法。

掌握广义表的表头表尾运算。

掌握广义表的访问方法。

重点难点及其处理

重点：

广义表的定义

求表头和表尾的运算.

广义表与线性表的区别

难点：

广义表的有关概念及其与线性表的关系。

广义表的括号表示和图形表示之间的转换。

求给定的非空广义表的表头和表尾运算。

处理：

广义表是一种递归的结构，通过一些实例来理解广义表的构成。

教学方法

课堂讲授与课下作业相结合，鼓励学生自学上机实习。

参考文献

1．赵文静.数据结构——C++语言描.西安：

西安交通大学出版社，2001

2.殷人昆.数据结构（用面向对象方法与C++描述）.北京：

清华大学出版社，2002

3．苏运霖.数据结构与算法.武汉：

中南工业大学出版社，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课时

教学目的及要求

教学目的：

介绍树的定义，树的各种存储结构，二叉树的定义、性质、存储结构、

教学要求：

在熟悉树和二叉树的基础上，掌握二叉树的基本概念及其有关应用。

重点难点及其处理

重点：

树的概念

树和二叉树的常用术语及含义

二叉树的递归定义及树与二叉树的差别。

二叉树的性质，了解相应的证明方法。

难点：

二叉树的两种存储方法、特点及适用范围

二叉树的性质

使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。

处理：

对于树的概念，通过现实中组织结构图来引入，增强对树这种结构的理解，对于二叉树要强调它本身的特点，整理归纳二叉树的术语，强调二叉树的性质。

教学方法

课堂讲授与课下作业相结合，鼓励学生自学上机实习。

参考文献

1．黄定.数据结构与算法.广州：

广东科技出版社，2000

2．徐士良.实用数据结构.北京：

清华大学出版社，1998

3．[美]BrunoR.Preiss.数据结构与算法——面向对象的C++设计模式.北京：

电子工业出版社，2001

课外作业及要求

1．对于3个结点A，B，C，可组成多少种不同的二叉树?

请画出。

2．如果一棵树有n1个度为1的结点，n2个度为2的结点，…，nm个度为m的结点，则该树共有多少个叶子结点（n0=?

）?

可参考二叉树性质3．的证明方法来思考m叉树问题。

3．写出图6．25中所示的树的叶子结点，非终端结点，各结点的度和树深．

4．将图6．26中的树转换为二叉树．对转换后的二叉树按先根、中根、后根次序遍历的结点序列．

后记

教案专用页

内容

（标题）

第6章树

6.3二叉树的遍历

6.4线索二叉树

课时

3课时

教学目的及要求

教学目的：

了解二叉树遍历的基本方法，遍历时访问节点的先后次序。

能够掌握遍历二叉树来解决复杂的问题。

教学要求：

掌握二叉树的遍历算法及其有关应用。

重点难点及其处理

重点：

⑴二叉树的三种遍历算法，理解其执行过程。

⑵确定三种遍历所得到的相应的结点访问序列。

⑶以遍历算法为基础，设计有关算法解决简单的应用问题。

⑷二叉树线索化的目的及实质。

难点：

⑴确定三种遍历所得到的相应的结点访问序列。

⑵二叉树线索化的目的及实质。

⑶在中序线索树中查找给定结点的中序前趋和中序后继的方法。

⑷查找给定结点的前序前趋和后序后继井非有效的原因。

处理：

通过演示二叉树的遍历过程来增强对访问节点序列的理解。

教学方法

课堂讲授与课下作业相结合，鼓励学生自学上机实习。

参考文献

1．黄定.数据结构与算法.广州：

广东科技出版社，2000

2．徐士良.实用数据结构.北京：

清华大学出版社，1998

3．[美]BrunoR.Preiss.数据结构与算法——面向对象的C++设计模式.北京：

电子工业出版社，2001

课外作业及要求

1．写出先根遍历的非递归算法．

2．写出按层遍历二叉树的算法．

3．写一个算法求二叉树中结点总数．你能写出多少种方法?

4．现有按后根遍历二叉树的结果为C，B，A，有几种不同的二叉树可以得到这一结果?

5．现有按先根和中根遍历某二叉树的结果，试画出这棵二叉树，形状唯一吗?

为什么?

先根遍历：

ABCDEFGHI，中根遍历；BCAEDGHFI．

后记

教案专用页

内容

（标题）

第6章树

6.5树和森林

6.6哈夫曼树及其应用

课时

3课时

教学目的及要求

教学目的：

树和森林与二又树之间的转换方法。

树的各种存储结构及其特点。

树的两种遍历方法。

哈夫曼算法的思想

根据给定的叶结点及其权值构造出相应的最优二叉树

教学要求：

掌握树的存储方法和树和森林的转化方法。

掌握哈夫曼树的构造方法，根据最优二叉树构造对应的哈夫曼编码。

重点难点及其处理

重点：

树和森林与二又树之间的转换方法。

最优二叉树和最优前缀码的概念及特点。

哈夫曼算法的思想。

根据给定的叶结点及其权值构造出相应的最优二叉树。

根据最优二叉树构造对应的哈夫曼编码。

难点：

哈夫曼算法的思想

哈夫曼树及其应用，根据最优二叉树构造对应的哈夫曼编码

处理：

通过幻灯演示哈夫曼编码的过程来加强对哈夫曼编码的理解。

教学方法

课堂讲授与课下作业相结合，鼓励学生自学上机实习。

参考文献

1．黄定.数据结构与算法.广州：

广东科技出版社，2000

2．徐士良.实用数据结构.北京：

清华大学出版社，1998

3．[美]BrunoR.Preiss.数据结构与算法——面向对象的C++设计模式.北京：

电子工业出版社，2001

课外作业及要求

1．有一组数值14，21，32，15，28，画出哈夫曼树的生成过程及最后结果．

2．凡二叉树都只能用二叉链表来存储，这种说法是否正确?

满二叉树和完全二叉树用什么存储结构更适合?

书中哈夫曼算法的实现，用的是什么存储结构?

后记

教案专用页

内容

（标题）

第8章查找

8.1查找表的基本概念

8.2线性表的查找

课时

3课时

教学目的及要求

教学目的：

介招顺序查找、二分查找、分块查找的基本思想、算法实现和查找效率分析。

教学要求：

掌握顺序查找、二分查找，查找的基本思想和算法实现。

通过比较线性表上三种查找方法的优缺点，能根据实际问题的要求和特点，选择出合适的查找方法。

重点难点及其处理

重点：

⑴静态查找表和动态查找表的基本概念

⑵顺序查找的基本思想和算法实现。

⑶二分查找的基本思想和算法实现

难点：

⑴顺序查找中哨兵的使用方法。

⑵二分查找的算法实现。

处理：

通过分析线性表的查找方法，对比顺序查找的算法思想，来引入顺序查找。

通过对有序表的分析，引入折半查找的思想。

教学方法

课堂讲授与课下作业相结合，鼓励学生自学上机实习。

参考文献

1．黄定.数据结构与算法.广州：

广东科技出版社，2000

2．徐士良.实用数据结构.北京：

清华大学出版社，1998

3．[美]BrunoR.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．设单链表的结点是按关键字从小到大排列的，试写出对此链表的查找算法，并说明是否可以采用折半查找．

4．若对大小均为n的有序顺序表和无序顺序表分别进行查找，试就下列三种情况分别讨论两者在等查找概率时，平均查找长度是否相同：

（1）查找失败；

（2）查找成功；（3）查找成功，

表中有多个关健字等于给定值的记录，一次查找要求找出所有记录．

后记

教案专用页

内容

（标题）

第8章查找

8.4树的查找

8.5散列技术

课时

3课时

教学目的及要求

教学目的：

介招二叉查找树和B-树的定义和特点以及用途

介绍二叉查找树的插入、删除、建树和查找算法及时间性能。

了解B-树的插入、删除及查找方法的基本思想。

掌握散列表、散列函数的概念和几种常用的散列函数构造方法。

教学要求：

掌握二叉查找树上查找以及散列表上查找的基本思想和算法实现。

重点难点及其处理

重点：

⑴二叉查找树和B—树的定义和特点以及用途

⑵二叉查找树的插入、删除、建树和查找算法及时间性能

⑶B—树的插入、删除及查找方法

⑷散列表、散列函数、散列地址和装填因子等有关概念

⑸几种常用的散列函数构造方法

难点：

⑴二叉查找树的删除算法

⑵B—树上的插入和删除算法。

⑶两类解决冲突的方法及其优缺点

处理：

举例了解散列函数的选取原则及产生冲突的原因。

深入分析采用线性探测法和拉链法解决冲突时，散列表的建表方法、查找过程以及算法实现和时间分析。

比较散列表和其它表的本质区别。

教学方法

课堂讲授与课下作业相结合，鼓励学生自学上机实习。

参考文献

1．黄定.数据结构与算法.广州：

广东科技出版社，2000

2．徐士良.实用数据结构.北京：

清华大学出版社，1998

3．[美]BrunoR.Preiss.数据结构与算法——面向对象的C++设计模式.北京：

电子工业出版社，2001

课外作业及要求

1．什么叫二叉平衡树?

试按下列次序将各关键字插入到二叉平衡树中，画出重新平衡的情况．关键字依次为；8，9，10，2，1，5，3，6，7，