复习课1上海交通大学继续教育学院ppt课件.ppt

《复习课1上海交通大学继续教育学院ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构学位考复习课(1)主要内容：1.第一部分概述2.第二部分线性表、栈、队列第一部分：数据结构与算法的基本概念考核内容及要求：理解算法、算法正确性、复杂性的概念；了解算法的时间与空间复杂性级别；重点掌握数据类型、数据结构和表示、实现的概念；掌握抽象数据类型的说明、高级语言对抽象数据类型的支持。基本概念和术语数据(Data)：数据元素(DataElement)：数据的基本单位，计算机中通常作为一个整体来考虑，如一棵树中的一个结点、一个图中的一个结点。一个数据元素可以有若干个数据项(DataItem)组成。数据对象(DataObject)：性质相同的数据

2、元素的集合数据结构：数据元素之间的关系——结构四种基本结构集合线性结构树形结构图状结构/网状结构数据结构的形式定义：一个二元组：Data_Structure=(D,S)其中：D是数据元素的集合，S是D上的关系集合数据的逻辑、物理（存储）结构逻辑结构：数据元素之间的逻辑关系物理结构：数据元素在计算机中的存储方法（表现和实现）数据结构的分类：按照逻辑结构的不同分为：集合、线性结构、树状结构、网状结构按照物理结构的不同分为：顺序结构：利用在存储器中的物理关系来表示逻辑关系。链式结构：用在存储器中附加指针的方式来表示逻辑关系。算法：对特定问题求解步骤的一种描述，是

3、指令的有序序列算法的五个特性：有穷性、确定性、可行性、输入、输出算法设计的要求：时间复杂度，空间复杂度时间复杂度：算法执行时间随规模增长而增长的趋势T(n)=O(f(n))f(n)算法规模，T(n)称算法复杂度估算办法：以算法中重复执行的次数作为算法时间复杂度的依据。三种最常见时间复杂度：O(1)常量级O(n)线性级O(n2)平方级算法的空间复杂度S(n)=O(f(n))算法执行过程中所需的最大空间估算方法：输入数据所占空间+程序所占空间+辅助变量所占空间第二部分线性表、栈、队列考核内容及要求：熟练掌握顺序分配、链接分配的表示及实现方法；熟练掌握各种链表：

4、单链、双链、多链、循环链表；理解栈、队列、双向队列的顺序、链式表示及其算法复杂度分析；熟练掌握表达式计算原理。1.线性表的顺序表示和实现线性表的存储结构：顺序存储、链接存储顺序存储：用一组地址连续的存储单元依次存储线性表的数据元素。a1a2aianbb+lb+(i-1)lb+(n-1)lb+nl存储地址存储内容顺序存储结构基地址：起始位置第i个元素的位置LOC(ai)=LOC(a1)+(i-1)*ll：每个元素占用的存储单元顺序表的特点（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构于存储结构（物理结构）一致；（2）在

5、访问线性表时，可以利用上述给出的数学公式，快速计算任何一个数据元素的存储地址。即访问每个数据元素所花费的时间相等。（3）这种存取元素的方法被称为随机存取法。使用这种存取方法的存储结构被称为随机存储结构。表示方法：在高级语言中，用一维数组表示：表示方法：constLIST_INIT_SIZE=100;//表初始分配空间constLISTINCREMENT=10;//空间分配增量typedefstruct{ElemType*elem;　//存储空间intlength;//当前长度intlistsize;//当前存储容量intLISTINCREMENT;//可增

6、加存储空间}SqList;注意：1.数组指针elem指示线性表的基地址，length:线性表的当前长度。2.C语言数组的下标从0开始，即数组中的第i个元素为L.elem[i-1]2.线性表的链式表示和实现顺序表的局限：插入、删除时要移动大量的元素，耗费大量时间。链式表示：用一组任意的存储单元存储线性表存储单元不要求连续：物理结构不反应逻辑结构不可以随机存取，但插入和删除方便需要两个域：一个表示数据本身；一个表示数据元素间的先后关联。——一个结点。结点中表示关联的部分为指针域，内部存放指针或链。n个结点链接成一个链表。线性链表线性链表的物理存储结构(Zhao

7、,Qian,Sun,Li,Zhou,Wu,Zheng,Wang)ZhaoQianSunLiWangZhengWuZhou数据域指针域存储地址171319253137434931头指针LZhaoQianSunWang^线性链表（单链表）的定义：typedefstructLNode{ElemTypedata;structLnode*next;}Lnode,*LinkListLa1aiai-1an^La1aiai-1an^带头结点的链表循环链表循环链表：线性表的另一种链式存储结构。Ha1anH特点：从表的任何位置出发，都可以找到其他结点；操作与单链表的差别：判断

8、表尾的条件：P->next=H空表循环链表双向链表每一个结点有两个