【数据结构】清华版严蔚敏《数据结构》重点要点第二章线性表1线性表的特点及逻辑结构2．线性表的顺序存储结构及基本操作（插入、删除、定位）本章难点线性表的顺序存储结构，基本操作在顺序表上的实现及时间复杂度的计算。
内容和要求线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素，存在唯一的一个被称作“最后一个”的数据元素，除第一个外，集合中的每个数据元素均只有一个前驱，除最后一个外，集合中的每个数据元素均只有一个后继。
§2.1线性表的定义和逻辑结构定义：一个线性表是n个数据元素的有限序列。
§2.2线性表的顺序存储结构一、顺序表：1、定义：用一组地址连续的存储单元存放一个线性表叫顺序表。
2、元素地址计算方法：LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中：L—一个元素占用的存储单元个数LOC(ai)—线性表第i个元素的地址3、特点：实现逻辑上相邻—物理地址相邻；实现随机存取4、实现：可用C语言的一维数组实现1）插入定义：线性表的插入是指在第I（1£i£n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表。
算法时间复杂度T(n)2）删除定义：线性表的删除是指将第i（1£i£n）个元素删除，使长度为n的线性表。
算法评价5、顺序存储结构的优缺点优点：逻辑相邻，物理相邻；可随机存取任一元素；存储空间使用紧凑缺点：插入、删除操作需要移动大量的元素；预先分配空间需按最大空间分配，利用不充分；表容量难以扩充。
习题第19页1,4第三章链式存储结构本章重点1．线性表的链式存储结构的特点2．单链表的基本运算及实现，循环链表，双向链表单链表的基本运算（建立、查找、插入、删除）实现及算法内容和要求§3.1线性表的链式存储结构特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点数据域：元素本身信息指针域：指示直接后继的存储位置实现单链表的基本运算：单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢循环链表(circular linked list)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p或p->link=NULL循环链表p或p->link=H双向链表（double linked list）单链表具有单向性的缺点结点定义习题第34页3，4，5，8第四章栈和队列本章重点1．栈的七种基本操作，两种存储结构（顺序、链式）2．队列的七种基本操作，两种存储结构（顺序、链式）本章难点1．顺序栈上实现栈的几个基本操作所对应的算法2．链栈上元素进栈和出栈的算法3．队列的表现和操作实现内容和要求栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS§4.1栈（stack）栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）栈的存储结构顺序栈的实现和入栈、出栈算法链栈的入栈和出栈算法§4.2队列队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)——允许插入的一端队头(front)——允许删除的一端队列特点：先进先出(FIFO)链队列：结点定义队列的顺序存储结构实现：用一维数组实现sq[M]存在问题设数组维数为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出当front¹-1,rear=M-1时，再有元素入队发生溢出——假溢出解决方案队首固定，每次出队剩余元素向下移动——浪费时间循环队列基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;习题第51页1,2，5，第五章其他线性数据结构本章重点1．串的存储结构及基本操作实现2．二维数组基本操作，向量存储结构3．稀疏矩阵的压缩存储、转置算法本章难点1．串的堆分配存储结构2．二维数组向量存储结构、地址的计算方法、稀疏矩阵的压缩存储、转置算法自学内容和要求§5.1串定义※定栈的定义：串是由零个或多个字符组成的有限序列。
一般记为：S＝‘a1a2….an’(n≥0)※基本操作有九种«定义串的存储结构※串的顺序定长存储结构※堆分配存储结构※串的基本操作的实现1．在串的顺序定长相信结构上实现CONCAT（S，T1，T2）操作2．在串的堆分配存储结构上实现CONCAT（S，T1，T2）操作3．在串的顺序定长存储结构上实现子串的定位操作INDEX（S，T）§5.2多维数组定义二维数组※定义及基本操作定义：数组是由下标和值组成的序对的集,数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表※基本运算：给定一组下标，存取对应的数据元给定一组下标，修改相应数据元素的值。
数组的顺序存储结构次序约定以行序为主序以列序为主序数组元素地址计算方法矩阵的压缩存储对称矩阵三角矩阵稀疏矩阵的压缩存储方法顺序存储结构三元组表带辅助行向量的二元组表求转置矩阵问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题分析一般矩阵转置算法：十字链表设行指针数组和列指针数组，分别指向每行、列第一个非零元结点定义习题第65页2,3，5,6，7第六章树本章重点1．二叉树的存储结构及其各种操作，遍历二叉树2．树和森林与二叉树的转换关系，树的遍历本章难点1．遍历二叉树的算法2．树和森林与二叉树的转换关系，哈夫曼树及编码内容和要求§6.1树的定义定义定义：树(tree)是n(n>0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(root)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：树中至少有一个结点——根树中各子树是互不相交的集合基本术语§6.2二叉树定义定义：二叉树是n(n³0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成特点每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒基本形态二叉树性质性质1：«几种特殊形式的二叉树满二叉树定义：u性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1£i£n)，有：(1)如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是ëi/2û(2)如果2i>n，则结点i无左孩子；如果2i£n，则其左孩子是2i(3)如果2i+1>n，则结点i无右孩子；如果2i+1£n，则其右孩子是2i+1§6.3树的存储结构树的存储结构双亲表示法实现：定义结构数组存放树的结点，每个结点含两个域：数据域：存放结点本身信息双亲域：指示本结点的双亲结点在数组中位置特点：找双亲容易，找孩子难孩子表示法多重链表：每个结点有多个指针域，分别指向其子树的根结点同构：结点的指针个数相等，为树的度D结点不同构：结点指针个数不等，为该结点的度d孩子兄弟表示法（二叉树表示法）实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点特点操作容易破坏了树的层次二叉树的存储结构顺序存储结构实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树链式存储结构二叉链表树与二叉树转换森林转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构§6.4树和二叉树的遍历树的遍历遍历——按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列常用方法先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点二叉树的遍历方法先序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点l按层次遍历：从上到下、从左到右访问各结点算法递归算法§6.5二叉树的应用哈夫曼树(Huffman)——带权路径长度最短的树定义路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的~路径长度：路径上的分支数树的路径长度：从树根到每一个结点的路径长度之和树的带权路径长度：树中所有带权结点的路径长度之和构造Huffman树的方法——Huffman算法构造Huffman树步骤根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令起权值为wj在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和在森林中删除这两棵树，同时将新得到的二叉树加入森林中重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树算法按中序线索化二叉树二叉排序树定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值它的左、右子树也分别为二叉排序树二叉排序树的插入二叉排序树的删除习题第96页1,4,7，15，16,21，22第七章图本章重点1．图的存储结构，遍历2．图的生成树和最小生成树，拓扑排序、最短路径本章难点1．图的遍历：深度优先搜索遍历和广度优先搜索遍历2．最小生成树及最短路径的计算3．树和森林与二叉树的转换关系，哈夫曼树及编码内容和要求§7.1图的定义和术语§7.2图的存储结构多重链表邻接矩阵——表示顶点间相联关系的矩阵定义：设G=(V,E)是有n³1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵特点邻接表实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）特点无向图中顶点Vi的度为第i个单链表中的结点数有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表有向图的十字链表表示法§7.3图的遍历深度优先遍历(DFS)方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止深度优先遍历算法递归算法§7.4生成树生成树定义：所有顶点均由边连接在一起，但不存在回路的图叫~深度优先生成树与广度优先生成树生成森林：非连通图每个连通分量的生成树一起组成非连通图的~说明一个图可以有许多棵不同的生成树所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图一个有n个顶点的连通图的生成树有n-1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路含n个顶点n-1条边的图不一定是生成树最小生成树构造最小生成树方法方法一：普里姆(Prim)算法算法思想：设N=(V,{E})是连通网，TE是N上最小生成树中边的集合初始令U={u0},(u0ÎV),TE=F在所有uÎU,vÎV-U的边(u,v)ÎE中，找一条代价最小的边(u0,v0)将(u0,v0)并入集合TE，同时v0并入U重复上述操作直至U=V为止，则T=(V,{TE})为N的最小生成树算法实现：图用邻接矩阵表示算法描述算法评价：T(n)=O(n²)方法二：克鲁斯卡尔(Kruskal)算法算法思想：设连通网N=(V,{E})，令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V,{F})，每个顶点自成一个连通分量在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边依此类推，直至T中所有顶点都在同一连通分量上为止§7.5拓扑排序问题提出：学生选修课程问题顶点——表示课程有向弧——表示先决条件，若课程i是课程j的先决条件，则图中有弧<i,j>学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业——拓扑排序定义AOV网——用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网(Activity On Vertex network)，简称AOV网若<vi,vj>是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继AOV网中不允许有回路，这意味着某项活动以自己为先决条件拓扑排序——把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫~检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环拓扑排序的方法在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和所有以它为尾的弧重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止算法实现以邻接表作存储结构把邻接表中所有入度为0的顶点进栈栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈重复上述操作直至栈空为止。