（数据构造）教案_4.docx

《（数据构造）教案_4.docx》由会员分享，可在线阅读，更多相关《（数据构造）教案_4.docx（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、点、表示和实现，十分注意与基本数据构造的区别，把握各种遍历的递归和非递归算法，能熟练完成下面的应用：最优树、Huffman编码、拓扑排序、关键途径和最短途径问题。3数据构造的应用：查找和内部排序。熟练把握静态查找表的查找方法和实现，了解哈希表的构造和查找方法。把握各种内部排序方法的基本思想、算法特点、排序经过以及它们的时间复杂度分析。（数据构造）教学大纲课程名称：数据构造课程编号：014100028适用专业：计算机、信息管理总学时数：60学分数：4一、课程的性质、目的与任务数据构造是计算机科学技术、信息管理等专业的核心课程之一，是一门理论与工程实践密切相关的综合性课程，在计算机学科教学中具有特

4、别重要的作用。大力加强数据构造课程的建设，提高数据构造课程的教学质量，有利于教学改革和教育创新，有利于高级应用型人才和创新人才的培养。（数据构造）课程是计算机专业的专业基础课程，介绍计算机领域的常用数据构造以及各种查找和排序的算法，是计算机专业学生必修的一门技术基础课程，也是计算机专业的核心课程。数据构造是计算机专业的一门重要的专业基础课，主要解决数据的表示和数据的处理，系统介绍三大数据构造及其实现，为操作系统等课程提供必要的知识基础，为计算机人员提供必要的基本技能。二、课程教学基本要求本课程介绍常用数据构造之间的逻辑构造、存储构造和对其施加的运算，如：线性表、栈、队列、串、数组、广义表、树、

5、图等。同时还介绍各种查找和排序的算法。通过本门课程的学习，应使学生把握下面几个方面的知识：1：系统学习常用基本数据构造及其在不同存储方式下的实现，把握分析、选择不同的数据构造和存储构造的原则和方法。2：学习和把握在各种存储构造上实现的各种算法及其设计思想，进而学习各种分析问题和解决问题的能力。3：把握各种算法的时空效率的分析方法，学会在实际应用中选择适宜的算法。4：把握各种查找和排序的算法以及效率，并将其应用在程序设计中。三、课程教学内容体系第一章：概论1.1什么是数据构造1.2基本概念和术语1.3抽象数据类型的表现与实现1.4算法和算法分析教学要求：理解数据、数据元素、数据项的概念；把握逻辑

6、构造和存储构造的关系；理解算法的基本概念；学会分析算法的时间复杂性和空间复杂性。第二章：线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现静态查找表不讲2.4一元多项式的表示及相加教学要求：理解线性表的定义和特点；把握顺序表和链表的特点，把握在这两种存储构造上各种基本运算的实现算法以及效率的分析，并学习在这两种存储构造上进行算法设计的方法；以到达利用基本算法进行较复杂算法设计的目的。第三章：栈、队列3.1栈3.2栈的应有和举例3.2.1数制转换3.3.4迷宫求解3.3栈与递归的实现3.4队列教学要求：理解栈和队列的定义、特点，学习它们的各种组织方式及算法；把握

7、它们的空和满的判定条件；并学会它们的简单应用。第四章：串4.1串类型的定义4.2串的表示和实现4.2.1定长顺序存储表示4.2.3串的块链存储表示4.3串的形式匹配算法4.3.1求字串位置的定位函数教学要求：了解串的概念，把握串的基本运算，学习串运算在不同存储构造下的实现经过。第五章：多维数组和广义表5.1数组的定义5.2数组的顺序表现和实现5.3矩阵的压缩存储教学要求：领会数组的定义，数组的两种顺序存储构造，并领会几种特殊矩阵和稀疏矩阵的压缩存储方法。第六章：树6.1树的定义和基本术语6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储构造6.3遍历二叉树和线索二叉

8、树6.3.1遍历二叉树6.4树和森林6.4.1树的存储构造6.4.2森林与二叉树的转换6.4.3树和森林的遍历6.6赫夫曼树及其应用6.6.1最优二叉树赫夫曼树6.6.2赫夫曼编码教学要求：理解树型构造的概念和术语，领会二叉树的定义、形态、性质和存储构造，把握二叉树的各种遍历算法极其实现经过，了解树和森林及其互相转换；把握哈夫曼树极其应用。第七章：图7.1图的定义和术语7.2图的存储构造7.2.1数组表示法7.2.2邻接表7.2.3十字链表7.2.4邻接多重表7.3图的遍历7.3.1深度优先搜索7.3.2广度优先搜索7.4图的连通性问题7.4.1无向图的连通分量和生成树7.4.3最小生成树7.

9、5有向无环图及其应用7.5.1拓扑排序7.5.2关键途径7.6最短途径7.6.1从某个源点到其余各顶点的最短途径教学要求：理解图型构造的概念和术语，把握图的邻接矩阵和邻接表两种存储形式，理解图的遍历的基本思想，把握图的两种遍历的方法和其实现的经过，学会图在最小生成树、拓扑排序、最短途径、关键途径中的应用。第九章：查找9.1静态查找表9.1.1顺序表的查找9.1.2有序表的查找9.1.4索引顺序表的查找9.3哈希表9.3.1什么是哈希表9.3.2哈希函数的构造方法9.3.3处理冲突的方法教学要求：把握查找表的定义和分类，熟练把握顺序查找和二分查找的思想，了解二叉排序树及其查找，了解散列查找的思想

10、和有关方法。第十章：内部排序10.1概述10.2插入排序10.2.1直接插入排序10.2.2其他插入排序表的插入排序不讲10.2.3希尔排序10.3快速排序10.4选择排序10.4.1简单项选择择排序10.5归并排序教学要求：熟练把握各种排序方法的思想和特点，如：插入排序、交换排序、选择排序、分配排序等，学会分析它们的优点和缺点以及时空性能，并学会选择和应用各种排序方法解决实际问题。五、推荐教材及教学参考书1.教材（数据构造）；严蔚敏编著；清华大学出版社2.教学参考书（算法与数据构造C语言版），范策等编著，机械工业出版社，2004（数据构造C语言版），严蔚敏等编著，清华大学出版社2004（数据

11、构造与算法），许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004（数据构造实用教程第二版），徐孝凯编著，清华大学出版社2006（数据构造辅导与提高实用教程第二版），徐孝凯，清华大学出版社2003（数据构造），谢楚屏等，人民邮电出版社，2001（算法与数据构造C语言描绘），张乃孝等，高等教育出版社，2002（数据构造），殷人昆，清华大学出版社，2001（计算机算法设计与分析），苏德富，电子工业出版社，2001（算法与数据构造），傅清祥，王哓冬，电子工业出版社，1998（数据构造C+与面向对象的途径），张乃孝，裘宗燕，高等教育出版社，2001（数据构造用面向对象方法与C+描绘），殷人昆等清华大

12、学出版社（算法设计与分析），梁田贵，张鹏编著，冶金工业出版社，2004六、考核办法和成绩评定标准根据教学要求进行期末考试，由任课老师根据完成情况进行评定，并最终结合平常成绩的考核给出综合成绩。制定：制定日期：教学进程：计算机的应用不再局限于科学计算，更多地用于控制，管理，数据处理等非数值计算的处理工作。计算机加工处理的对象：数值，字符，表格，图形声音，图象等具有一定构造的数据。进行程序设计时必须分析待处理的对象的特性及各对象之间存在的关系产生背景。1.1什么是数据构造1.2数据构造的基本概念和术语1.数据Data2.数据元素DataElement3.数据对象DataObject4.构造Data

13、Structure存储构造、抽象数据类型抽象数据类型(AbstractDataType)ADT的定义格式不唯一,我们采用下述格式定义一个ADT:ADT抽象数据类型名数据对象:数据关系:基本操作:ADT抽象数据类型名教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书教学进程：1.3抽象数据类型的表示和实现1.4算法1.算法Algorithm的定义Algorithmisafinitesetofruleswhichgivesasequenceofoperationforsolvingaspecifictypeofproblem.(算法是规则的有限集合，是为解决特定问题而规定的一系列

14、操作。)是指令的有限序列，其中每一条指令表示一个或多个操作。2.算法的特性3.算法设计的要求算法的正确性(1)所设计的程序没有语法错误；(2)所设计的程序对于几组输入数据能够得出知足要求的结果；(3)所设计的程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得到知足要求的结果。(4)程序对于一切合法的输入数据都能产生知足要求的结果。2可读性3强健性4高效率和低存储量、算法、语言和程序的关系时间复杂度教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书章节第2章线性表：2.1线性表的类型定义2.2线性表的顺序表示教学目的和教学要求理解线性表的定义和特点；把握顺序表以到达利

15、用基本算法进行较复杂算法设计的目的。教学重点难点教学重点：线性表的定义和特点；线性表的顺序表示教学难点：线性表的顺序表示教学进程含章节教学内容、学时分配、教学方法、辅助手段教学进程：线性构造的特点：在数据元素的非空有限集中，?存在唯一的一个被称为“第一个的数据元素；?存在唯一的一个被称为“最后一个的数据元素；?除第一个元素之外，集合中的每个元素均只要一个前驱；?除最后一个元素之外，集合中的每个元素均只要一个后继。2.1线性表的类型定义2.1.1线性表的逻辑构造2.1.2线性表的抽象数据类型定义2.2线性表的顺序表示和实现2.2.1线性表的顺序存储构造2.2.2线性表顺序存储构造上的基本运算1.

16、初始化操作2.插入操作3.删除操作算法2.1算法2.3教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业1：算法2.1、图2.2、算法2.42：算法2.5、算法2.6主要参考资料（算法与数据构造C语言版），范策，周世平，胡哓琨等编著，机械工业出版社，2004（数据构造C语言版），严蔚敏等编著，清华大学出版社2004（数据构造与算法），许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析备注章节第2章：2.3线性表的链式表示和实现1教学目的和教学要求理解线性表的链表的特点，把握在这种存储构造上各种基本运算的实现算法以及效率的分析，并学习在这种存储构造上进行

17、算法设计的方法；以到达利用基本算法进行较复杂算法设计的目的。教学重点难点教学重点：线性表的链式表示和实现；教学难点：单链表的插入、删除、查找和归并操作；教学进程含章节教学内容、学时分配、教学方法、辅助手段教学进程：2.3线性表的链式表示和实现2.3.1单链表线性表的链式存储：图2.6单链表的逻辑状态图2.7带头结点单链表图示2.3.2单链表上的基本运算1.建立单链表2.查找3.单链表插入操作4.删除5合并单链表：教学方法、课堂讲解、例题演示，课件演示辅助手段：电脑、投影仪、教科书作业1：图2.5、图2.8、图2.92：算法2.8、算法2.9、算法2.10、算法2.11主要参考资料（算法与数据构造C语言版），范策，周世平，胡哓琨等编著，机械工业出版社，2004（数据构造C语言版），严蔚敏等编著，清华大学出版社2004（数据构造与算法），许卓群，杨冬青，唐世渭，张铭，高等教育出版社，2004课后自我总结分析备注