数据结构C++版复习资料讲解.pptVIP

已学习的数据结构：线性表、栈、队列、串、数组、广义表、树、图和散列表其中：栈、队列和串是特殊的线性表数组和广义表是广义的线性表树和图是非线性的数据结构散列表是一种查找数据结构还学习了在实际应用中应用广泛的查找技术、排序技术和索引技术

各章重点:第1章绪论数据结构定义:数据结构（datastructure）是指相互间存在一定关系的数据元素的集合。或数据结构是研究非数值问题中计算机的操作对象以及它们之间的关系和操作的学科。数据结构中的基本术语:数据元素--数据的基本单位数据项--是构成数据元素的不可再分的最小单位数据对象--是具有相同性质的数据元素的集合数据的逻辑结构--是数据元素间逻辑关系的整体存储结构--是数据及其逻辑结构在计算机中的物理表示。

数据的逻辑结构和存储结构的关系:数据的逻辑结构是数据的机外表示，数据的存储结构是数据的机内表示。一种逻辑结构可以用多种存储结构来实现。数据的基本操作是定义于逻辑结构，实现于存储结构。采用不同的存储结构，其数据处理的方法和效率往往是不同的。访问接口:操作的调用形式与规范数据结构的访问接口:数据结构基本操作接口的全体。数据类型（datatype）是一组值的集合以及定义于这个值集上的一组操作的总称抽象数据类型（AbstractDataType，ADT）:一个数据结构以及定义在该结构上的一组操作的总称。抽象数据类型的定义形式:ADT=D,O

算法（algorithm）是对特定问题求解的一种描述,是指令的有限序列。算法的五大特征:⑴输入⑵输出⑶有穷性⑷确定性⑸可行性算法的描述:1）自然语言高级语言伪代码N-S图

算法分析:“好”的算法至少应该满足以下几个条件1）正确性容错性可读性分级性高效性*算法的时间复杂度:刻画的是算法的运行时间算法的空间复杂度:主要对算法的执行过程中需要用到的辅助空间的度量。算法的时间复杂度和空间复杂度都用渐近阶来表示。通常用O来表示:T(n)=O(f(n))S(n)=O(f(n))

第2章线性表线性表的定义:线性表（linearlist）也简称表。是n(n个具有相同数据类型的数据元素的有限序列。L＝（a1,a2,…,ai-1,ai,…,an)线性表的几个术语:表长:线性表中的元素个数；空表:元素个数为零的线性表，常表示为L=（）；前驱与后继:a1无前驱,an无后继,其他元素有且仅有一个前驱和一个后继；性线表特征:顺序性、有限性、相同性、抽象性

线性表的顺序存储结构---顺序表顺序表是高级语言（C++语言)的一维数组intMaxSize;intlength;T*data;//存储表的允许长度//存储表的实际长度//存储数组的初地址主要函数（操作）说明:所有的操作都设计为函数（C++语言），不要求用C++的类构造顺序表:SeqList（a,n,m）--构造长为m,并从数组a复制n个数据的表PrintList（）voidInsert(inti,Tx)TDelete(inti)输出顺序表:顺序表插入:顺序表删除:顺序表查找:TGet(inti) intLocate(Tx)

顺序表的优点:⑴无需为表示表中元素之间的逻辑关系而增加额外的存储空间；⑵随机存取:可以快速地存取表中任一位置的元素顺序表的缺点:⑴表的容量难以确定，表的容量难以扩充；⑵插入和删除操作需要移动大量元素；⑶造成存储空间的碎片。

线性表的链接存储结构—单链表单链表是高级语言（C++语言)的指针单链表是使用一组任意的内存单元来存储线性表的数据元素,线性表中的逻辑关系是通过指针来表示的。结点结构:structNode{ T data;NodeT *next;};

三种单链表:ccdd ^^first带头结点的a单a链表:bb循环单链表:////////aabbccddrear一般单链表:头指针

{ T data;DulNodeTDulNodeT*prior;*next;双链表:也分一般双链表、带头结点的单链表、循环单链表template class Tstruct DulNode}在双向循环链表中求表长,按位置查找等操作与单链表基本相同,不同的是插入和删除操作。由于它是对称结构,使得插入和删除操作都很容易。要求掌握插入和删除指定结点的指针修改的相对顺序

主要函数（操作）说明:所有的操作都设计为函数（C＋＋语言），不要求用C++的类构造单链表: LinkList(Ta[],intn)--构造长为n，并从a复制n个数据的单链表,分头插法和尾插法输出单链表:单链表插入:PrintList（）voidInsert(inti,Tx);/