《数据结构》教案.docx

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

1、课程简介人们在运用程序设计语言编写程序的过程中发觉全部的数据都可以抽象为三种结构，而对这些数据的全部操作都可以转化为对这三种数据的几种基本操作，而大多数的程序设计技巧都可以抽象为一些最基本的兑法。于是人们逐步发展了一门称为数据结构（或数据结构与算法）的计兑机科学，它广泛应用于计兑机领域。数据结构是信息与计算专业的核心基础课程之一。数据是计兑机处理的对象，本课程探讨的数据是非数值性、结构性的数据。学习本课程要求驾驭各种主要数据结构的特点、计算机内的表示方法，以及处理数据的算法，对于算法所花费的时间和空间代价的分析也要求有肯定程度的了解和驾驭。通过本课程的学习，使学生透彻地理解各种数据对彖的特点，

2、学会数据的组织方法和实现方法，并进一步培育基本的良好的程序设计实力。本课程主要包括如下三个方面的内容：1 .基本数据结构：线性表、栈、队列、串、数组和广义表，驾驭它们的特点、表示和实现，对静态结构要求特别娴熟的编程上机实现，对动态结构要求逐步熟识链表的表示，通过仿照试验教程中的例子，冏驭编程技巧。强谢类C语言的书写规范，特殊留意参数的区分,输入输出的方式和错误处理方式，以及抽象数据类型的表示和实现。能娴熟完成以下的应用：多项式的计算、语法检查、回朔算法、递归算法、表达式求值、离散事务模拟、文字的编辑和稀疏矩阵进行矩阵运算采纳的处理方法。2 .困难数据结构：树、二叉树、图。驾驭它们的定义和特点、

3、表示和实现，特殊留意与基本数据结构的区分，驾驭各种遍历的递归和非递归算法，能娴熟完成以下的应用：最优树、HUffman编码、拓扑排序、关键路径和最短路径问题。3 .数据结构的应用：查找和内部排序.娴熟驾驭静态查找表的查找方法和实现，J解哈希表的构造和查找方法.驾驭各种内部排序方法的基本思想、算法特点、排序过程以及它们的时间困难度分析。3.2 栈的应有和举例数制转换迷宫求解3.3 校与递归的实现3.4 队列教学要求：理蟀栈和队列的定义、特点，学习它们的各种组织方式及算法：驾驭它们的空和满的推断条件:并学会它们的简洁应用。第四章，串4.14 类型的定义4.15 的表示和实现定长依次存储表示串的块依

4、存储表示4.16 的模式匹配算法求字申位置的定位函数教学要求：了解串的慨念,驾驭小的基本运算，学习串运算在不同存储结构下的实现过程。第五章：多修数坦和广义表5数组的定义5.2 数处的依次表现和实现5.3 矩阵的压缩存谛教学要求：领悟数组的定义，数组的两种依次存储结构,并领悟几种特殊矩阵和稀畸矩阵的压缩存储方法.第六章，W6.1 国的定义和基本术谱6.2 二叉树二叉树的定义二叉树的性质二叉树的存储结构6.3 遍历二叉树和线索二叉树遍历二叉树6.4 树和森林树的存储结构杳林与二叉树的转换树和森林的诩历6.6 赫夫蚣树及其应用最优二叉树（林夫受树）赫夫蚣编码教学要求：理解树型结构的概念:和术语，领悟

5、：叉树的定义、形态、性质和存储结构，驾驭：叉树的各种遍历算法极其实现过程，了斛树和森林及其相可转换：驾驭哈夫蚣树极其应用。第七章：图7.1 图的定义和术语7.2 图的存储结构数组表示法邻接表十字链表邻接多曳衣7.3 图的遍历深度优先搜寻7.3.2广度优先搜寻7.4 图的连通性网SS无向图的连通HHit和生成树最小生成树7.5 有向无环图及其应用拓扑排序美镀路径7.6 鼓短路径从某个源点到其氽各顶点的最短路径教学要求：理解图型结构的概念和术语,驾驭图的邻接矩阵利邻接衣两种存储形式，理解图的遍历的基木思想，驾驭图的两种迪历的方法和其实现的过程，学会图在收小生成树、拓扑拷序、最短跖径、关键路径中的应

6、用。第九章：查找9.1 静态杳找去依次表的查找有序表的查找索引依次友的查找9.3 哈希表什么是哈希表哈布函数的构造方法处埋冲突的方法.教学要求：驾驭,找表的定义和分类，娴热驾驭依次杳找和：分杳我的思想，了斛：叉排序树及其杳找,了解散列克找的思想和有关方法.第十章；内部排序10.1 概述10.2 插入排序干脆插入排序其他插入排序（表的插入排序不讲希尔排序103快速排序10.4 选择排序简洁选择排序10.5 归并排序教学要求：嫡熟驾驭各种排序方法的思想和特点，如：插入持序、交换排序、选择持序、安排排序等，学会分析它们的优点和缺点以刚好空性能.并学会选择和应用各种排序方法耨决实际问遨.四、学时安排章

7、节内容讲授学时上机学时习题学时概论400线性表6I1三枝、队列6I1四事211五数组和广义表4I1树和二叉树8II七图8I1九查找2I1十内部持序411总学时数：60课时4488五、举粗*材及教学参考书1 .教材数据结构：严刘敏娟著：清华高校出版社2 .教学参考书算法与数据结构（C语言版）,范策等端洋，机械工业出版社,2004E数据结构（C语言版）？，严的收等编著，清华高校出俄社2004。数据结构与究法，许卓用,杨冬青,唐世湘，张铭，高等教化出版社，2004彳数据结构好用教程（其次版）3.徐孝凯编著.清华将校出版社20064数据结构辅导与提商好用教理（其次版）J,徐孝凯，清华高校出版社2003

8、E数据结构,谢楚屏等，人民邮电出版社，2001算法与数据结构一Ci杵吉描述？.张乃孝等.高等教化出版社，2002E数据结构令.殷人昆.清华高校出版社.2001计算机算法设计与分析,苏霭富，电子工业出版社,2001E算法与数据结构8,卿清祥，王哓筌，电子工业Hl版社，1998，:数据结构-C+与面对对象的途径:。，张乃孝，炎宗燕，高等教化出版社，2001E数据结构一用面对对象方法与C+描述,殷人昆等清华高校出版社算法设计与分析？，梁田货,张弼编著，冶金工业出版社，2004六、考核方法和成果评定标准依据教学要求进行期末考试,由任课老师依据完成状况进行评定并的终结合平常成果的考核给出综合成果。制定：

9、制定日期:授课时间效案编写时间课程名称数据结构i果程代码总学时讲课；学时上机：学时实习：周学分课程性质必蟋课（）选修深（）埋论课（J）试验深）任课老师职称授课时象专业；年级：班级；教材和主要参学资料选刖教材：E数据结构:,严西敏编著清华高校出版社主18书，算法与数据结构（C语言版）B,范策,周世平，胡晓琨等编著，机械工业出版社.2004数据结构（C语言版）.严的收等编著，清华高校出版社2004g数抠结构与算法.许卓群，杨冬青，唐世湖,张侨，岛等教化出版社，2004数据结构好用教程（其次版）.徐孝凯编著.清华高校出版社2006数据结构辅导与与提高用用程（其次版）B.徐孝凯，清华高校出版社2003

10、数据结构，谢谊屏等，人民邮电出版社,2001彳算法与数据结构一C语言描述3.张乃孝等，高等教化出版社，2002数据结构3.殷人昆，清华高校出版社，2001计算机算法设计与分分，苏镌富，电子工业出版社，2001算法与数据结构3,傅清徉,王晓冬，电子工业出版社，1998数据结构-C+与面对对象的途径,张乃孝,裳宗燕.高等教化出版社.2（X）1数据结构一用面时对象方法与C+描述3.殷人昆等清华高校出版社律法设计与分析.梁田贵,张则编著.冶金工业出版社,2004教学目的和教学要求通过本门课程的学习，成使学生驾以以下几个方面的学（：1 .系统学习常用基本数据结构及其在不同存储方式下的实现,驾收分析、选择

11、不同的数据结构和存储结构的原则和方法。2 .学习和驾双在各种存储结构上实现的各种峰法及其设计思想，从而学习各种分析问题和解决问遨的实力.3 .与驭各种算法的时空效率的分析方法,学会在实际应用中选择合适的尊法.4 .驾驭各种在找和持序的算法以及效率，并将其应用在程序设计中。教学学点和教学难点1R点驾驭数据结构之间的逻册结构、存储结构和对其施加的运算，如；线性衣、校、队列、串、数组、广义表、树,图等。应驾驭各种肯找和排序的算法.难点奉节：第六聿：树和第七章：图.教学进程授课求节学时备注第I次课笫1章络出：1什么是数据结构、1,2携本概念和术语2第2次课第I章：13抽软数据类型的去现与实现1.4盛法

12、和算法分析2第3次课笫2章线性表：2跷性衣的类型定义2.2战性去的依次表示2第4次课第2整：2.3线性表的魅式衣示和实现（1）2第5次课第2章：2.32）2.4一元多项式的表示及相加2第6次课第3埴校和队列：3.1、2第7次课第3章栈和队列：、3.2.5,3.32第8次课第3章栈和队列：3.42第9次课综合习题课（1）：加3章的相关内容2第10次课琮合成脸课（1）：前3章的相关内容2第Il次课第4章耶：4.1、2第12次课第S址数处和广义衣：5.1,5.22第13次课第5章效汨和广义表：5.32第14次课Sii!R（2）；第45章的相关内容2第15次课笫6章树和二叉树：6.1.6.22第16次

13、课第6章树和二叉树:6.3、2第17次课第6章树和二叉树：、6.62第18次课第6章树和二叉树：2第19次课综合习题课（2）：树的相关内容2第20次课第7章图：7.k7.22第21次课第7章图：73、2第22次课第7章图：7.62第23次课第7举图：2第24次课媒合习的课（3）：图的相关内容2第25次课第9章杳找：9.1、932第26次课淙合状验课（3）；第9章的相关内容2第27次课第IO章内部排序：10,1、10.22第28次深第IO章内部排序：10.3、10.42第29次课综合习阳深（3）：第9、10章的相关内容2第前次深综合试胎课（4）：第10章的相关内容2课次：1学时：2章节第1章结论

14、：1.1什么是数据结构、1.2基本概念和术语教学目的和教学要求了解数据结构的课程性质、内容、应用领域及其与其他学科的关系：驾取数据结构的相关概念和术谱：学狈四类基本的数据关系.教学点难点教学或点：数据结构的相关概念和术语教学难点：四类基本的数据关系教学进程(含章节教学内容、学时安排、教学方法、协助手段)帙学进程，计算机的应用不再局限于科学计算,更多地用于限制.管理.数据处理等非数值计算的处理工作.计算机加工处理的对:ft(ft.字符，表格，图形用音，图望等具彳I肯定结岗的故据，进行程序设计时必需分析待处理的对象的特性及各对象之间存在的关系产生背景.1.1 什么是数据结构1.2 数据结构的基本概念和术语1 .数据(Dala)2 .数据元泰(DutaEleme