《考研数据结构备课教案》由会员分享，可在线阅读，更多相关《考研数据结构备课教案（367页珍藏版）》请在金锄头文库上搜索。
1、数据结构,课程性质：专业基础课 授课时段：2004年下半学期 授课单位：软件学院 任课教师：李青山、徐学洲,任课教师：李青山、徐学洲 工作单位：软件工程研究所 工作地点：科技楼9层A座907室 联系电话：029-88202457(办) 电子邮件：,课程特点,很强的理论性本课程不是以掌握应用性知识为目的，而是以掌握基本理论，基本方法，基本技能为目的。让学生把握解决什么样的问题，用什么思想，采用什么样方法解决，以及用什么方法最优解决等一系列问题。 很强的概念性 本课程要求学生不但应该深刻理解某些概念的所有要素，要领，精神实质。同时也要求理解为什么要引入某些概念，某些概念的形成过程，引入某些概念是解
2、决什么样的问题 。,课程特点（续）,很强的连贯性 本课程结构紧奏，每部分所述问题层层推进，逐步深入，逐步解决。全课程始终是以数据间的关系即“结构”为主线索展开。其中“基本数据结构”部分围饶数据结构三要素即逻辑结构、物理结构、运算特性展开，辅以一定该数据结构基本应用的讲述；而“应用数据结构部分”以基本概念、基本方法、性能分析的讲解顺序展开，使全课程大量庞杂的内容条理分明，轮廓分明 。 很多的混淆性 本课程中首先有很多容易混淆的基本概念。其次有很多算法，状态等等一系列问题都容易混淆。比如要解决某类问题，也许有很多方法和很多途径，每种方法和途径适用于什么场合，各自存在什么优缺点（例如“内部排序”这一
3、章中各中内排方法的比较与应用），都容易产生相互混淆 。,课程学习方法,循序渐进学习法 由于本课程很强的理论性、概念性和连贯性，所以学习过程中要从概念入手，逐段、逐节、逐章深刻理解和掌握，层层推进，从基础到应用，最后达到完全掌握该课程内容。 概括提炼学习法 每学完一节、一章内容，都要从中概括提炼出本部分内容要点、重点、非重点。一则可以达到内容总结、有效复习的目的，二则可以自检学习中存在的问题 。,课程学习方法（续）,归纳对比学习法 针对课程中容易混淆的概念以及课程中同类、非同类容易混淆的问题，进行归纳并加以有效的比较，从中找出它们的异同点，各自的优缺点，各自针对要解决的问题。这种方法不仅能搞清楚
4、容易混淆的问题，而且能更深刻理解本课程的内容实质。 循环学习法 由于课程中许多基本概念和复杂算法在一次顺序学习过程中 并不能准确和透彻的理解，有些概念和方法可以应用在多种场合，他们的学习就需要循环往复，借助后续内容的信息来全面把握。,课程内容框架,数 据 结 构,基础数据结构,应用数据结构,栈,队 列,线 性 表,线性结构,非线性结构,串,查 找,内 部 排 序,外 部 排 序,文 件,动 态 存 管 理 储,数 组,广 义 表,树,二 叉 树,图,1.绪论 2.线性表 3.栈、队列和串 4.数组 5.广义表 6.树和二叉树,教学内容-第一章,7.图 8.动态存储管理 9.查找 10.内部排序
5、 11.外部排序 12.文件,数据结构学科发展背景,1.1什么是数据结构,应用领域从科学计算到非数值计算 起初数据结构中内容在其他课程中表述 1968年美国唐.欧.克努特开创数据结构最初体系。在计算机程序设计技巧第一卷基本算法系统阐述数据的逻辑结构、存储结构及操作 数据结构的两个发展方向：面向专门领域特殊问题的数据结构；从抽象数据类型的观点讨论数据结构,计算机解决问题的过程,1.1什么是数据结构（续）,具体问题,数学模型,算法,数据结构,程序,解答,抽象建模,数据结构,数据结构,算法分析与设计,程序设计语言(范型),数据结构示例(对弈),1.1什么是数据结构（续）,描述非数值计 算问题的数学
6、模型不再是数 学方程，而是 诸如表、树和 图之类的数据 结构,s0,数据结构学科的地位,1.1什么是数据结构（续）,综合性的专业基础课 介于数学、计算机硬件和计算机软件之间的核心课程 不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础 本课程前继课程：离散数学、C语言 本课程后续课程：面向对象程序设计、操作系统、编译原理、数据库系统、人工智能等,什么是数据结构,1.1什么是数据结构,数据结构是一门研究非数值计 算的程序设计问题中计算机的操 作对象以及它们之间的关系和操 作等等的学科。,基本概念,1.2基本概念和术语,数据：指所有能输入
7、到计算机中并被计算机程序加工处理的符号的总称。不仅包括数字、字符串，还包括图形、图像、声音、动画、视频等能通过编码而被加工的数据形式。 数据元素：是数据的基本单位，数据集合中的元素。 数据项：是数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。,结构的定义,1.2基本概念和术语（续）,内涵：数据元素之间的关系，成为“结构” 分类：*集合：松散的关系*线性结构：一对一的关系*树形结构：一对多的关系*网状结构：多对多的关系,数据结构的定义,1.2基本概念和术语（续）,描述性定义：相互之间存在一种或多种特定关系的数据元素的集合 形式
8、化定义：Data_Structure=（D，S）D=数据元素的有限集合S=D上关系的有限集合,数据结构的分类,1.2基本概念和术语（续）,逻辑结构：数据元素之间的逻辑关系（本来的关系） 存储结构：数据结构在计算机中的映象。包括数据元素的表示和关系的表示两个方面。分类：*顺序存储结构*链式存储结构描述方式：用高级语言中的“数据类型”来描述,数据类型,1.2基本概念和术语（续）,内涵：一个值的集合和定义在这个值集上的一组操作的总称。本质是封装：实现由处理器完成 分类：*原子类型：值不可分解，如整型、指针类型等*结构类型：值由若干成分按照某种结构组成，如 数组、结构（记录）等,抽象数据类型（ADT）
9、与数据类型,1.2基本概念和术语（续）,ADT指一个数学模型以及定义在该模型上的一组操作。ADT的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。ADT比数据类型的范畴更广，除了具有固有数据类型的特性之外，还包括用户在设计软件系统时自己定义的数据类型。,抽象数据类型形式化定义,1.2基本概念和术语（续）,ADT=（D，S，P）D=数据对象S=D上的关系集P=对D的基本操作集定义形式：ADT 抽象数据类型名数据对象：数据关系：基本操作： ADT 抽象数据类型名,ADT Triplet 数据对象：D=e1,e2,e3|e1,e2,e3属于ElemSet数据关系：R1=,基本操作
10、：InitTriplet(&T,v1,v2,v3)DestroyTriplet(&T)Get(T ，i，&e)Put(&T，i，e) ADT Triplet,抽象数据类型示例,1.2基本概念和术语（续）,基本操作的定义格式：基本操作名（参数表）初始条件：操作结果：,抽象数据类型分类,1.2基本概念和术语（续）,分类标准：按照值的不同特性*原子类型：变量的值不可分解*固定聚合类型：变量的值成分的数目确定*可变聚合类型：变量的值成分的数目不确定*多形数据类型：变量的值成分不确定（成分类型可变）,抽象数据类型表示与实现,1.2基本概念和术语（续）,抽象数据类型表示与实现抽象数据类型通过固有数据类型来
11、表示和实现。即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。 类C语言的描述语法类C语言精选了C语言的一个核心子集，也做了若干扩充，以利于描述。如：存储结构用typedef；数据元素类型约定为ElemType；在形参表中，以&打头的参数为引用参数；等等,算法,1.3算法和算法分析,内涵:是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。 特性:*有穷形：有穷步+有穷时间/每一步*确定性：指令的语义无二义性*可行性：算法能用基本操作完成*输入：零个或多个输入*输出：一个或多个输出,算法设计的要求,1.3算法和算法分析（续）,正确性（
12、Correctness） 可读性（Readablity） 健壮性（Robustness） 高时间效率与低存储量需求,算法的描述方式,1.3算法和算法分析（续）,自然语言 程序设计语言 流程图 类高级语言（类C语言、类Pascal语言等）,算法选择时效率的考虑,1.3算法和算法分析（续）,虽然我们希望所选的算法占用额外空间小，运行时间短，其他性能也好，但计算机时间和空间这两大资源往往相互抵触。所以，一般算法选择的原则是：对于反复使用的算法应选择运行时间短的算法；而使用次数少的算法可力求简明、易于编写和调试；对于数据量较大的算法可从如何节省空间的角度考虑。,算法时间效率的度量（一）,1.3算法和算
13、法分析（续）,程序运行消耗时间取决于下列因素*算法策略*问题规模*语言层次*编译程序所产生的机器代码的质量*机器执行指令的速度 算法时间效率度量 算法时间效率在软硬件环境相同的情况下取决于问题的规模，即T(n)=f(n),算法时间效率的度量（二）,1.3算法和算法分析（续）,算法时间效率度量的基本做法在算法中选取一种对于所研究问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。一般而言，这个基本操作是最深层循环内的语句中的原操作。 算法时间复杂度 T(n)=O (f(n) 称为算法的渐近时间复杂度，简称时间复杂度。,算法时间效率的度量（三）,1.3算法和算法分析（续）,算法语句频度与时间复杂度的关系一般算法消耗的实际时间为算法中每条语句频度之和，是n的函数T(n)。当n趋于无穷大时，T(n)的同阶无穷小即是算法时间复杂度。,for (i=1; i=n; +i)for (j=1; j=n; +j)cij = 0;for (k=1; k=0)。 空表：n=0时的线性表称为空表。 位序：非空表中数据元素 ai 是此表的第 i 个元 素，则称 i 为 ai 在线性表中的位序。,线性表的抽象数据类型定义,
