数据结构教案.docx

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

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

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

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

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

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

6、才能取得较优的时空性能。处理：能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。利用链表设计算法解决简单的应用问题。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参献考文1 .朱若愚.数据结构(第二版).北京：电子工业出版社，20012 .张绍民.数据结构教程(C语言版).北京：中国电力出版社，20023 .胡学钢.数据结构算法设计指导.北京：清华大学出版社，2001课外作业及要求1 .试写出一个计算链表中数据元素结点个数的算法，其中指针P指向读链表的第一个结点.2 .试设计实现在单链表中删去值相同的多余结点的算法.3 .有一个线性表(al,a2,，an),它存储在

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

8、现的进栈、退栈等基本算法。栈的“上溢”和“下溢”的概念及其判别条件。（4）掌握栈和队列在两种存储结构上实现的基本运算。难点：是栈中对边界条件的处理。利用栈设计算法解决简单的应用问题。处理：加过现实生活中的例子来理解栈的特点，通过对栈的逻辑结构、存储结构的深入分析来理解栈的相关算法。通过栈的应用来掌握栈的特点，什么样的情况下能够使用栈。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参考文献1 .赵文静.数据结构一一C+语言描.西安：西安交通大学出版社，20012 .殷人昆.数据结构（用面向对象方法与C+描述）.北京：清华大学出版社，20023 .苏运霖.数据结构与算法.武汉：中南工业大

9、学出版社，1999课 外 作 业 及 要 后记1 .假定有编号为A、B、C、D的4辆列车，顺序开进一个栈式结构的站台，请写出开出车站站台的列车顺序（注：每一列车由站台开出时均可进栈，出栈开出站台，但不允许出栈后回退）。写出每一种可能的序列.2 .已知堆栈采用链式存储结构，初始时为空，试画出a,b、c、d4个元素依次进栈以后堆栈的状态，然后再画出此时的栈顶元素出栈后的状态.3 .写出链栈的取栈顶元素和置栈空的算法.4 .写出多个链表栈中取第j个链表栈顶元素值的算法。5 .写出计算表达式3+4/25*8-6时操作数栈和运算符栈的变化情况.凄做射表大聋教案专用页内容（标题）第3章栈和队列3.1队列的

10、逻辑结构、存储结构及其相关算法课时3课时教学目的及要教学目的：介绍队列的逻辑结构定义及在两种存储结构上如柯实现队列的基本运算。要求在掌握队列的特点的基础上，懂得在什么样的情况下能够使用队列。求重占八、难点及其处理重点：队列在两种存储结构上实现的基本运算，（2）队列的逻辑结构特点，队列与线性表的异同。顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法。（4）队列的“上溢”和“下溢”的概念及其判别条件。使用数组实现的循环队列取代普通的顺序队列的原因。难点：循环队列中对边界条件的处理。队列的逻辑结构、存储结构及其相关算法。处理：通过举例来说明队列这种数据结构的使用，利用队列设计算法解决筒

11、单的应用问题。最终能够掌握队列的应用，领会队列的特点，知道什么样的情况下能够使用队列。教学片课堂讲授与课下作业相结合，鼓励学生自学上机实习。参献考文1 .赵文静.数据结构C+语言描.西安：西安交通大学出版社，20012 .殷人昆.数据结构（用面向对象方法与C+描述）.北京：清华大学出版社，20023 .苏运霖.数据结构与算法.武汉：中南工业大学出版社，1999课外作业及要求1 .课文中规定：无论是循环队列还是链表队列，队头指针总是指向队头元素的前一位置，队尾指针指向队尾元素.试画出有两个元素A、B的不同存储结构的图示，及将这两个元素出队后循环队列和链表队列的状态不意图.2 .对于一个具有In个

12、单元的循环队列，写出求队列中元素个数的公式.3 .对于一个具有n个单元(n22)的循环队列，若从进入第一个元素开始，每隔11个时间单位进入下一个元素，同时从进入第一个元素开始，每隔t2(t2tl)个时间单位处理完一个元素并令其出队。试编写一个算法，求出在第几个元素进队时将发生溢出。4 .假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写出相应的置空队列，入队列和出队列的算法。后记建做财或大专教案专用页内容（标题）第4章串课时3课时教学目的及要求教学目的：介绍串的逻辑结构、存储结构及其中上的基本运算，由于C语言及其它高级语言均已具备了较强的串处理功能，主

13、要掌握串的模式匹配算法。教学要求：掌握3上实现的模式匹配算法。重点难占八、及其处理重点：1 .串及其运算1.1 串的有关概念及基本运算。1.2 串与线性表的关系。2 .中的存储结构2 .1串的两种存储表示。3 .2串上实现的模式匹配算法及其时间性能分析。难点：掌握串上实现的模式匹配算法。处理：通过多媒体演示来展现模式匹配的过程，详细演示了KMP算法。使用C语言提供的串操作函数构造与中相关的算法解决简单的应用问题。教学方法课堂讲授与课下作业相结合，鼓励学生自学上机实习。参献考文1 .赵文静.数据结构一一C+语言描.西安：西安交通大学出版社，20012 .殷人昆.数据结构（用面向对象方法与C+描述

14、）.北京：清华大学出版社，20023 .苏运霖.数据结构与算法.武汉：中南工业大学出版社，1999课外作业及要1 .假设所使用的字符串采用数组存储。试用C语言编写一个求字符串长度的函数定义.2 .假设所使用的字符串采用数组存储.试用C语言编写一个实现字符串复制的函数定义。3 .假设所使用的字符串采用链接存储结构，链表中每个结点存放m(m=4)个字符.试用C语言编写一个实现字符串删除的函数定义.4 .假设所使用的字符串采用数组存储。试用C语言编写一个函数，将字符中string2的头n个字符添加到字符串Stringl的尾部，并以求结束.后记建做财或大专教案专用页内容(标题)第5章数组和广义表5. 1多维数组5.2矩阵的压缩存储课时3课时教学目的及要求教学目的：介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法。教学要求：领会多维数组的概念掌握矩阵的压缩存储的方法熟练掌握稀疏矩阵的三元组表示法重点难占八、及其处理重点：(1)多维数组的逻辑结构特征。(2)多维数组的顺序存储结构及地址计算方式。矩阵的压缩存储方式、特殊矩阵和压缩存储时的下标变换方法。稀疏矩阵的三元