数据结构专业知识讲座

关于本课程课程性质：必修考评方式：考试(闭卷)成绩(80%)+平时成绩(20%)3.5学分 课程试验成绩(程序验收＋汇报)100%1学分学习要求：①禁止旷课、迟到；②课前请关闭手机或调至振动，禁止课堂接听或拔打电话；③要独立思索，按时完成作业。在自己不会解答时可参考其它资料或他人答案，在分析他人处理思绪之后自己动手，勉励相互讨论，禁止剽窃；④上机试验前应先就要处理问题写出自己处理思绪和纲领，禁止在机房游戏、网上聊天、流览不相关网页；⑤上机程序要现场验收、禁止拷贝他人程序及汇报。1数据结构专业知识讲座第1页本课程内容框架数据结构基础数据结构应用数据结构非线性结构线性结构线性表栈队列串数组广义表树二叉树图查找内部排序外部排序文件动态存储管理2数据结构专业知识讲座第2页课程特点很强理论性 本课程不是以掌握应用性知识为目标，而是以掌握基本理论，基本方法，基本技能为目标。让学生把握处理什么样问题，用什么思想，采取什么方法处理，以及用什么方法最优处理等一系列问题。很强概念性

本课程要求学生不但应该深刻了解一些概念全部要素,同时也要求了解为何要引入一些概念，这些概念形成过程，以及引入这些概念处理什么样问题。3数据结构专业知识讲座第3页课程特点(续)很强连贯性本课程结构紧凑，每部分所述问题层层推进，逐步深入。全课程一直是以数据间关系即“结构”为根本索展开。其中“基本数据结构”部分围饶数据结构三要素即逻辑结构、物理结构、运算特征展开，辅以一定该数据结构基本应用讲述；而“应用数据结构部分”以基本概念、基本方法、性能分析次序展开，使全课程大量庞杂内容条理分明，轮廓分明。轻易混同性 本课程中有一些轻易混同基本概念，也有很多算法，状态等等一系列问题都轻易混同。比如要处理某类问题，可能有很多方法和很多路径，每种方法和路径适合用于什么场所，各自存在什么优缺点（比如“内部排序”这一章中各中内排方法比较与应用），都轻易产生相互混同。4数据结构专业知识讲座第4页本课程学习方法•循序渐进学习法

因为本课程很强理论性、概念性和连贯性，所以学习过程中要从概念入手，逐段、逐节、逐章深刻了解和掌握，层层推进，从基础到应用，最终到达完全掌握该课程内容要求，加强上机实践步骤是非常必要，能增强对数据结构了解和应用能力。•概括提炼学习法

每学完一节、一章内容，都要从中概括提炼出本部分内容关键点和重点。一则能够到达内容总结、有效复习目标，二则能够自检学习中存在问题。5数据结构专业知识讲座第5页课程学习方法(续)•归纳对比学习法

针对课程中轻易混同概念以及课程中同类、非同类轻易混同问题，进行归纳和比较，从中找出它们异同点、优缺点。这种方法不但能搞清楚轻易混同问题，而且能更深刻了解本课程内容实质。•循环学习法

因为课程中许多基本概念和复杂算法在次序地学习过程中并不能到达准确、透彻地了解程度，有些概念和方法能够应用在各种场所，对这些内容，在学习时就需要循环往复，借助后续内容信息来全方面把握。6数据结构专业知识讲座第6页第一章绪论本章内容：1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计要求1.4.3算法效率度量1.4.4算法存放空间需求7数据结构专业知识讲座第7页1.1什么是数据结构数据结构学科发展背景•应用领域从科学计算到非数值计算•起初数据结构中内容在其它课程中表述•1968年美国唐.欧.克努特(DonaldE.Knuth)开创数据结构最初体系。在《计算机程序设计技巧》第一卷《基本算法》系统阐述数据逻辑结构、存放结构及操作•数据结构两个发展方向：面向专门领域特殊问题数据结构；从抽象数据类型观点讨论数据结构8数据结构专业知识讲座第8页1.1什么是数据结构计算机处理问题过程详细问题数学模型抽象建模数据结构数据结构算法数据结构算法分析与设计程序设计程序问题求解描述非数值计算问题数学模型不再是数学方程，而是诸如表、树和图之类数据结构。9数据结构专业知识讲座第9页1.1什么是数据结构非数值型计算问题举例：学籍管理(信息处理类问题)IS19男张立95004IS19女刘晨95002MA18女王敏95003CS20男李勇95001SdeptSageSsexSnameSno46PASCAL语言72编译原理647数据结构536操作系统441信息系统32数学245数据库1CcreditCpnoCnameCno9500295002950019500195001Snoc5c2c4c2c1Cno7390886592Grade学生信息：课程：学生选课：这类问题已独立成为数据库学科，在《数据结构》中主要在文件一章有所包括。10数据结构专业知识讲座第10页1.1什么是数据结构非数值型计算问题举例：博弈类问题S0S11S10S1n……………………SK1Sqr……SK1Sqr……SK1Sqr……这类问题中数据结构可用树描述。还有更复杂问题需要用图来处理。11数据结构专业知识讲座第11页1.1什么是数据结构数据结构学科地位•综合性专业基础课•介于数学、计算机硬件和计算机软件之间关键课程•不但是普通程序设计基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序主要基础•本课程先修课程：离散数学、C语言(或其它程序设计语言)•本课程后续课程：面向对象程序设计、操作系统、编译原理、数据库系统、人工智能等12数据结构专业知识讲座第12页1.1什么是数据结构什么是数据结构

数据结构是一门研究非数值计算程序设计问题中计算机操作对象间逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义和实现对应运算学科。13数据结构专业知识讲座第13页1.2基本概念和术语基本概念•数据(Data)：指全部能输入到计算机中并被计算机程序加工处理符号总称。不但包含数字、字符串，还包含图形、图像、声音、动画、视频等能经过编码而被加工数据形式。•数据元素(DataElement)：是数据基本单位，数据集合中元素。•数据项(DataItem)：是数据不可分割最小单位。一个数据元素可由若干个数据项组成。•数据对象(DataObject)：是性质相同数据元素集合，是数据一个子集。•数据结构(DataStructure)

：是相互之间存在一个或各种特定关系数据元素集合。14数据结构专业知识讲座第14页1.2基本概念和术语逻辑结构•内涵：数据元素之间关系，或称为“结构”。•分类：

*集合：涣散关系

*线性结构：一对一关系

*树形结构：一对多关系

*网状结构：多对多关系•描述性定义： 用自然语言描述相互之间存在一个或各种特定关系数据元素集合。•形式化定义： Data_Structure=（D，S） D={数据元素有限集合} S={D上关系有限集合}15数据结构专业知识讲座第15页1.2基本概念和术语存放结构(物理结构)： 数据结构在计算机中映象。包含数据元素表示和关系表示两个方面。分类：*次序存放结构*链式存放结构描述方式：*数据元素用高级语言中“数据类型”来描述*数据元素间关系用数据元素间存放相对位置关系(次序存放结构)或在数据元素上增加指针(链式存放结构)来表示16数据结构专业知识讲座第16页1.2基本概念和术语数据类型 一组性质相同值集合,以及定义于这个值集合上一组操作总称。这种类型通常由高级语言提供。如C语言中数据类型: charintfloatdoublevoid字符型整型浮点型双精度型无值分类：*原子类型： 值不可分解，如整型、指针类型等。*结构类型： 值由若干成份按照某种结构组成，如数组、结构（统计）等。17数据结构专业知识讲座第17页1.3抽象数据类型表示与实现抽象数据类型(AbstractDataType，ADT) ADT指一个数学模型以及定义在该模型上一组操作。ADT定义仅取决于它一组逻辑特征，而与其在计算机内部怎样表示和实现无关。ADT比数据类型范围更广，除了含有固有数据类型特征之外，还包含用户在设计软件系统时自己定义数据类型。由用户定义，用以表示应用问题数据模型由基本数据类型组成,并包含一组相关服务（或称操作）信息隐蔽和数据封装，使用与实现相分离18数据结构专业知识讲座第18页1.3抽象数据类型表示与实现抽象数据类型形式化定义 ADT=（D，S，P） D={数据对象} S={D上关系集} P={对D基本操作集}定义形式：ADT抽象数据类型名{ 数据对象：…

数据关系：…

基本操作：…}ADT抽象数据类型名19数据结构专业知识讲座第19页1.3抽象数据类型表示与实现抽象数据类型示例ADTTriplet{数据对象：D={e1,e2,e3|e1,e2,e3属于ElemSet}数据关系：R={<e1,e2>,<e2,e3>}基本操作：InitTriplet(&T,v1,v2,v3) DestroyTriplet(&T) Get(T,i,&e)

Put(&T,i,e) ……}ADTTriplet

20数据结构专业知识讲座第20页1.3抽象数据类型表示与实现抽象数据类型分类

分类标准：按照值不一样特征原子类型：变量值不可分解固定聚合类型：变量值成份数目确定可变聚合类型：变量值成份数目不确定多形数据类型：变量值成份不确定（成份类型可变）抽象数据类型表示与实现 抽象数据类型表示与实现抽象数据类型经过固有数据类型来表示和实现。即利用处理器中已存在数据类型来说明新结构，用已经实现操作来组合新操作。类C语言描述语法 类C语言精选了C语言一个关键子集，也做了若干扩充，以利于描述。如：存放结构用typedef；数据元素类型约定为ElemType；在形参表中，以&打头参数为引用参数；等等。21数据结构专业知识讲座第21页1.4算法和算法分析算法内涵:

是对特定问题求解步骤一个描述，是指令有限序列，其中每一条指令表示一个或多个操作。特征:

•有穷性：有穷步+有穷时间/每一步

•确定性：指令语义无二义性

•可行性：算法能用基本操作完成

•输入：零个或多个输入

•输出：一个或多个输出22数据结构专业知识讲座第22页1.4算法和算法分析算法设计要求•正确性（Correctness）•可读性（Readablity）•健壮性（Robustness）•高时间效率与低存放量需求算法描述方式•自然语言•程序设计语言•流程图•类高级语言（类C语言、类Pascal语言等）23数据结构专业知识讲座第23页1.4算法和算法分析算法选择时效率考虑

即使我们希望所选算法占用额外空间小，运行时间短，其它性能也好，但计算机时间和空间这两大资源往往相互抵触。所以，普通算法选择标准是：对于重复使用算法应选择运行时间短算法；而使用次数少算法可力争简明、易于编写和调试；对于处理数据量较大算法可从怎样节约空间角度考虑。24数据结构专业知识讲座第24页1.4算法和算法分析算法时间效率度量程序运行消耗时间取决于以下原因算法策略问题规模语言层次编译程序所产生机器代码质量机器执行指令速度算法时间效率度量 算法时间效率在软硬件环境相同情况下取决于问题规模，即T(n)=f(n)。算法时间效率度量基本做法

在算法中选取一个对于所研究问题来说是基本操作原操作，以该基本操作重复执行次数作为算法时间度量。普通而言，这个基本操作是最深层循环内语句中原操作。25数据结构专业知识讲座第25页1.4算法和算法分析算法时间复杂度 T(n)=O(f(n))称为算法渐近时间复杂度，简称时间复杂度。算法语句频度与时间复杂度关系 普通算法消耗实际时间为算法中每条语句频度之和，是n函数T(n)。当n趋于无穷大时，T(n)同阶无穷小即是算法时间复杂度。时间复杂度举例：例1、{++x;s=0;}将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)假如将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。26数据结构专业知识讲座第26页1.4算法和算法分析例2、for(i=1;i<=n;++i){++x;s+=x;}

语句频度为：2n其时间复杂度为：O(n)

即时间复杂度为线性阶。例3、for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}

语句频度为：2n2，其时间复杂度为：O(n2)

即时间复杂度为平方阶。定理： 若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)。时间复杂度O(nk)，k为常数，称为该时间复杂度为k次多项式阶。27数据结构专业知识讲座第