数据结构导论复习大纲第1章概论一、程序设计的实质（计算机专业人员必须完成的两项基本任务）：数据表示：机外表示->逻辑结构->存储结构数据处理：处理要求->基本运算和运算->算法数据表示和数据处理是密切相关的，数据处理方式总是与数据的某种表示形式相联系。

二、“数据”分成三个不同的层次，即数据、数据元素和数据项。

凡能被计算机存储、加工的对象通称为数据。

数据元素是数据的基本单位，又被称为元素、结点、顶点或记录。

数据项是数据不可分割的最小单位。

三、数据的逻辑结构数据的逻辑结构就是数据的组织形式。

所谓逻辑关系是指数据元素之间的关联方式或称“邻接关系”。

通常有集合、线性结构、树形结构、图状结构。

＊逻辑结构与数据元素本身的形式、内容、相对位置、结点个数无关四、运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。

分为两种基本类型：1. 加工型运算：插入、删除、更新2. 引用型运算：读取、查找五、存储实现的基本目标是建立数据的机内表示。

数据的机内表示称为数据的存储结构。

包括三个主要部分：1. 存储结点。

每个结点存放一个数据元素2. 数据元素之间关联方式的表示，也就是逻辑结构的机内表示3. 附加设施。

存储结构的主要部分是数据元素之间关联方式的表示。

由于每个存储结点存放一个数据元素，数据元素之间的关联方式便由存储结点之间的关联方式间接地表达。

通常有四种基本存储方式：1. 顺序存储方式2. 链式存储方式3. 索引存储方式4. 散列存储方式六、运算实现运算的实现是指一个完成该运算功能的程序。

运算实现的核心是算法设计。

算法分为三类：（1）运行终止的程序（2）伪语言算法（3）非形式算法七、算法质量的评价：（1）正确性：算法应能正确地实现预定的功能（2）易读性：算法应易于阅读和理解。

（3）健壮性：当环境发生变化时，算法能适当地做出反应或进行处理（4）高效性：达到所需要的时空性能。

算法在所有输入下的计算量的最大值称为算法的最坏情况时间复杂性或最坏情况时间复杂度算法在所有输入下的计算量的加权平均值称为平均时间复杂性或平均时间复杂度。

常见时间复杂性的量级：O(1)<O(log2n)<O(n)<O(n2)<O(2n)数据结构的基本任务：数据结构的设计和实现。

数据结构课程的主要内容：（1）数据结构的定义（2）数据结构的实现（3）数据结构的评价和选择八、典型例题分析九、复习与习题讲解第2章线性表一、线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，通常记为（a1,a2,…….ai-1,ai,ai+1,…an）i称为ai在线性表中的序号或位置ai是序号为i的数据元素，每个数据元素都有一个确定的位置。

ai-1是ai的直接前驱ai+1是ai的直接后继。

除了起始结点之外，集合中的每个元素均有且仅有一个前驱除了终端结点之外，集合中的每个数据元素均有且仅有一个后继所含结点个数称为表长，当表长为0时为空表。

线性结构邻接关系是”一对一”线性表中的元素可以是各种各样的，但同一线性表中的元素必定具有相同的特性。

二、顺序表：顺序存储的线性表特点：逻辑上相邻的结点在存储结构中仍相邻类型定义：const maxsize=顺序表的容量typedef struct{datatype data[maxsize];int last;}sqlist;表长为last,last-1是终端结点在表中的位置，从last到maxsize-1为空闲区或称备用区定义sqlist L则表长为st终端结点为L.data[st-1]结点表示为L.data[0]~L.data[st-1]三、顺序表的插入、删除、定位运算算法四、插入算法的平均时间复杂性为n/2删除算法平均时间复杂性为（n-1）/2三、链表带头结点空表条件：head->next==NULL不带头结点空表条件：head==NULL单链表的简单操作：初始化、求表长、按序号查找等算法基本运算在单链表上的实现算法：定位、删除、插入循环链表：头结点、尾结点存储位置：rear->next-->next 和rear双链表：(1)摘除操作P->prior->next=p->next;P->next->prior=p->prior;(2)链入操作q->prior=p;q->next=p->next;P->next->prior=q;P->next=q;四、顺序实现与链表实现的比较（空间、时间性能）第3章栈、队列和数组一、栈（1）栈的基本概念：先进后出；允许进行插入、删除的一端称为栈顶，另一端称为栈底。

（2）栈的基本运算：初始化InitStack(S),加工型运算进栈Push(S,X),加工型运算退栈Pop(S,X)，加工型运算读栈顶Top(S,X)，引用型运算判栈空Empty（S)，引用型运算（3）掌握以上基本运算的算法（4）栈的链接实现二、队列（1）队列的基本概念：先进先出；允许插入的一端称为队尾，允许删除的一端称为队首。

注意对头指针指示对头元素在数组中实际位置的前一个位置;实现递归调用属于栈的应用。

（2）队列的基本运算：队列初始化，InitQueue(Q),加工型运算入队列EnQueue(Q,X),加工型运算出队OutQueue(Q,X)，加工型运算判断列空EmptyQueue(Q)，引用型运算读队头GetHead(Q,x)，引用型运算（3）以上基本运算的算法（4）队列的顺序实现（5）队列的链接实现三、数组(1)数组的逻辑结构和运算(2)数组的基本运算:读:给定一组下标，读取相应的数据元素；写：给定一组下标，修改相应的数据元素。

（3）矩阵的压缩存储对称矩阵：若一个矩阵A中的元素满足下述性质：aij=aji(1<=i,j<=n)数组M和矩阵A间下标存在着如下对应关系：k=i(i-1)/2+j 当i>=jk=j(j-1)/2+i 当i<j（4）三角矩阵分为上三角矩阵和下三角矩阵两种，所谓上（下）三角矩阵是指矩阵的下（上）三角（不包括对角线）中元素均为常数C或零的n阶矩阵。

（5）上三角矩阵M[k]和aij的对应关系是：k=(i-1)(2n-i+2)/2+j-i+1 当i<=jk=n(n+1)/2+1 当i<j（6）下三角矩阵M[k]和aij的对应关系是：k=i(i-1)/2+j 当i>=jk=n(n+1)/2+1 当i<j（7）稀疏矩阵：设矩阵中有S个非零元素，若S远远小于矩阵元素的个数，并且非零元素的分布没有规律。

第4章树一、树（1）树的基本概念:树是n（n>0）个结点的有穷集合，满足：（1）有且只有一个称为根的结点；（2）其余结点分为m(m>=0)个互不相交的非空集合,这些集合中的每一个都是一棵树，称为根的子树。

二、二叉树(1)关于树的一些概念:结点的度,树的度,节点的层树,树的深度等(千万别忽视这些概念,他们可是拿分的主角啊!)(2)二叉树与树的区别:<1>二叉树可以是空集，这种二叉树为空二叉树。

<2>二叉树的任一结点都有两棵子树（它们中的任何一个可以是空子树）并且这两棵子树之间有次序关系。

（3）二叉树的性质性质1 二叉树第i（i>=1）层上至多有2k-1个结点。

性质2 深度为k（k>=1）的二叉树至多有2k-1个结点。

性质3 对任何二叉树，若度为二的结点数为n2，则叶子数n0=n2+1。

深度为k（k>=1）且有2k-1个结点的二叉树称为满二叉树。

性质4 具有n个结点的完全二叉树的深度为└log2n┘+1性质 5 有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：<1>若I为结点编号则如果I<>1，则其父结点的编号为I/2；如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；<2>若2*I>N，则无左儿子；如果2*I+1<=N，则其右儿子的结点编号为2*I+1；<3>若2*I+1>N，则无右儿子。

范例：令一个二叉树的根的深度为1，则在深度为i的那一层最多可能有多少个叶子？解答：最多有2(i-1)个练习1：若一个二叉树共有n（如280）个节点，则其最小高度和最大高度是多少？解答：最小高度=[lbn]+1([ ]表示近似的最大整数)，最大高度=n如n=280时，最小高度=[lb280]+1=8+1=9，最大高度=280练习2：深度为5的二叉树，最多有几个节点，最少有几个接点？解答：深度为5时，最多节点数=2h-1=25-1=32-1=31，最少节点数=h=5(4)二叉树的遍历:先根遍历、中根遍历、后根遍历的原理和算法(5)树的存储结构：孩子链表表示法、孩子兄弟表示法、双亲表示法(6)树和二叉树的关系：二叉树与森林的相互转换(7)判定树、哈夫曼树、WPL的计算方法三、完全二叉树二叉树和满二叉树的结构之间，尚有一种称为完全二叉树。

定义：完全二叉树是外部节点相差的阶数在1阶以内，含0阶（0阶即是满二叉树），而且可以顺序编号。

满二叉树必是完全二叉树，但完全二叉树不一定是满二叉树。

【公式一】高度为k的完全二叉树，含有的节点数介于2(k-1)和2k-1之间，节点的编号次序与满二叉树类似（中间无缺）【公式二】有n个节点的完全二叉树，其高度为└lbn┘+1。

第5章图一、图（1）图的基本概念：无向图，其中为顶点(结点)集，为边集，，中元素为无向边，简称边。

有向图，其中为顶点(结点)集，为边集，，中元素为有向边，简称边。

有时，泛指有向图或无向图。

（2）图的存储结构主要有两种：邻接矩阵和邻接表的画法（3）图的遍历：深度优先搜索、广度优先搜索（4）最小生成树：一个图的最小生成树是该图所有生成树中权最小的生成树。

Prim算法的时间复杂度为O(n2)。

（5）拓扑排序，算法时间复杂度为O（n+e）。

二、顶点的度、入度、出度<1>在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD (v) 。

<2>在有向图中，顶点v 的入度是指以该顶点为弧头的弧的数目，记为ID (v) ；顶点v 出度是指以该顶点为弧尾的弧的数目，记为OD (v) 。

某顶点的入度和出度之和称为该顶点的度，即TD (v)=ID (v) ＋OD (v) 。

可以证明，在具有n 个顶点、e 条边的有向图G 中，有下式成立：三、无向完全图、有向完全图（1）在一个无向图中，如果任意两个顶点之间都有边相连，则称该图为无向完全图。

可以证明，含有n 个顶点的无向完全图有n （n － 1 ）／ 2 条边。