数据结构-考研课程总结

《数据结构-考研课程总结》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构主讲刘铁铭单位工院一系二教Tel:319468/6/20211数据结构讲课安排：串讲全书内容典型习题分析前年、去年考题分析8/6/20212数据结构第一章概论数据结构及其概念如何评价一个算法8/6/20213数据结构第一章概论1.1数据结构的概念一、术语1.数据(Data):是信息的载体，能被计算机识别、存储、加工处理。2.数据元素(DataElement):数据的基本单位,即数据集合中的一个个体。也称元素、结点、顶点、记录数据项:是具有独立含义的最小标识单位关键字（key)：唯一能识别一个数据元素的数据项。数据元素

2、由数据项(dataitem)组成8/6/20214数据结构3、数据类型(DataType):是具有相同性质的计算机数据的集合及在这个集合上的一组操作。原子数据类型(atomicdatatype)结构数据类型(aggregatedatatype)4、数据结构数据的逻辑结构数据的存储结构数据的运算：既对数据施加的操作8/6/20215数据结构逻辑结构：(有时直接称为数据结构）线性结构：线性表、栈、队列、串(最多只有一个直接前趋和一个直接后继)非线性结构：树、图、多维数组、广义表说明：1、逻辑结构与数据元素本身的形式、内容无关2、逻

3、辑结构与数据元素的相对位置无关3、逻辑结构与所含结点个数无关8/6/20216数据结构存储结构：顺序存储方法：数据元素在内存中按序连续存储，结点间的逻辑关系由存储单元的邻接关系来体现链接存储方法：用指针指出其直接后继结点的存储位置，结点间的逻辑关系由存储单元的邻接关系来体现索引存储方法：数据元素连续存放，再设一个索引表（有序），索引表由索引项组成，每个索引项由关键字和地址构成分为稠密索引和稀疏索引散列存储方法：确定散列函数后，根据结点的关键字直接计算出该结点的存储地址。8/6/20217数据结构关系：逻辑结构是从逻辑关系上描述

4、数据，与存储无关，是独立于计算机的。逻辑结构是从具体问题抽象出来的数学模型存储结构是逻辑结构用计算机语言的实现（亦称映象）数据的运算是定义在数据的逻辑结构上的一个运算的集合运算的实现与存储结构密切相关逻辑结构与存储结构是多对多的关系8/6/20218数据结构例：一个学生成绩表：是一个数据结构每行是一个结点（或记录），由学号、姓名、各科成绩及平均成绩等数据项组成。逻辑关系：线性结构存储结构：表的运算：8/6/20219数据结构逻辑结构上定义的基本运算在存储结构上的实现是通过算法来描述的。一、算法定义算法是对特定问题求解步骤的一种

5、描述，由有限的指令序列构成，其中每一条指令表示一个或多个操作。第一章概论1.3算法描述8/6/202110数据结构二、算法应具有的五个特性：（1）输入一个算法有零个或多个的输入，它们是算法开始前给出的最初量（2）输出一个算法至少有一个输出，它们是同输入有某种关系的量（3）有穷性每一条指令的执行次数必须是有限的（4）确定性每一条指令必须有确切的含义，无二义性（5）可行性每条指令的执行时间都是有限的。8/6/202111数据结构第一章概论一、算法评价五要素（1）正确性（2）执行算法所耗费的时间（3）执行算法所耗费的空间（4）可读

6、性（5）健壮性1.4算法分析8/6/202112数据结构第一章概论二、算法的时间复杂度一个算法所耗费的时间:该算法中每条语句的执行时间之和。每条语句的执行时间：该语句的执行次数乘以该语句执行一次所需时间。频度：语句重复执行的次数算法的时间耗费T(n)=每条语句的执行的时间=（语句频度×语句执行一次所需时间）=语句频度算法的时间复杂度：就是算法的时间耗费T(n)8/6/202113数据结构第一章概论三、（渐进）时间复杂度(O(f(n))当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级（阶）称为算法的渐近时间复杂度，简

7、称时间复杂度四、最坏时间复杂度依据数据集中可能出现的最坏情况估算出的时间复杂度称为最坏时间复杂度。五、平均时间复杂度在假设数据集的分布是等概率的条件下，估算出的时间复杂度称为平均时间复杂度。例：顺序查找8/6/202114数据结构五、空间复杂度S(n)：算法所耗费的存储空间，仍是问题规模n的函数。第一章概论8/6/202115数据结构第一章概论本章要求:1、掌握数据、数据元素、数据结构等基本概念。2、掌握数据逻辑结构和物理结构的分类。3、学会算法分析的基本方法。8/6/202116数据结构第二章线性表本章要学习的主要内容1、线

8、性表的逻辑结构及基本运算2、线性表的顺序存储结构3、线性表的链式存储结构：单链表、循环链表、双链表、静态链表4、顺序表和链表的比较8/6/202117数据结构2.1线性表的概念及运算1.描述:线性表是由n(n>=0)个数据元素(点)a1,a2,….,ai,….,an组成的有限