数据结构期末复习

—１—数据结构期末复习——计算机1405杨程皓版权所有，翻版必究。附录是最小生成树和拓扑排序的代码及讲解，还有一些主要算法的演示一、基本概念及基本结构1、数据结构及其逻辑结构、存储（物理）结构的基本概念答：数据结构是相互之间存在一种或多种特定关系的数据元素的集合，在任何问题中，数据元素都不是孤立存在的，而是在他们之间存在着某种关系，这种数据元素相互之间的关系称为结构。根据数据元素之间关系的不同特性，通常分为下列4类(1)集合(2)线性结构(3)树形结构(4)图状结构或网状结构数据结构在计算机中的表示(又称映像)称为数据的物理结构，又称存储结构。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序映像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。2、动态存储顺序表的基本概念。（不准确）线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构是一种随机存取的存储结构。3、单链表、循环单链表、双链表的基本概念。线性表的链式存储结构的特点使用一组任意的存储单元存储线性表的数据元素，为了表示每个数据元素A(i)与其直接后继数据元素A(i+1)之间的逻辑关系，对数据元素A(i)来说，除了存储其本身的信息之外，还需储存一个指示其直接后继的信息。这两部分信息组成数据元素A(i)的存储映像，称为结点。它包括两个域：其中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。n个结点链接成一个链表，即为线性表的链式存储结构。由于此链表的每个节点中只包含一个指针域，故又称线性链表或单链表。循环链表是另一种形式的链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。每个节点只包含一个指针域则为循环单链表。双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。4、顺序栈的基本概念。顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。5、循环队列、链队列的基本概念。队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针的队列叫循环队列。（这里需要掌握循环队列的判空的三种方法）。用链表表示的队列简称为链队列。—２—6、字符串的概念、存储结构、传统模式匹配算法思想。串是由零个或多个字符组成的有限队列。串的顺序存储结构简称为顺序串，与顺序表类似，顺序串是用一组地址连续的存储单元来存储串中的字符序列的。其描述如下：#defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];串的堆分配存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但他们的存储空间是在程序执行过程中动态分配得到。描述如下：typedefstruct{char*ch;intlength;}HString;为了便于进行串的操作，当以链表存储串值时，除头指针外还可附设一个尾指针指示链表中的最后一个结点，并给出当前串的长度。称如此定义的串存储结构为块链结构，声明如下：#defineCHUNKSIZE80typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{chunk*head,*tail;intcurlen;}LString;算法的基本思想是：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较之。以此类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，否则称匹配不成功。7、特殊矩阵压缩存储的基本概念及基本计算。特殊矩阵一般为对称矩阵，上（下）三角矩阵，对角矩阵。对称矩阵，只存储一半的元素，将元素按顺序存进一维数组，对于下三角存储的公式为：k=i*(i+1)/2+j;对于上三角存储的公式为：k=j*(j+1)/2+i;下三角k={i*(i+1)/2+j(i=j)n*(n+1)/2(ij)[n*(n+1)/2位置所存元素为上三角中的重复元素]上三角k={i*(n-i+1)/2+j-i;i=j)n*(n+1)/2(ij)[n*(n+1)/2位置所存元素为下三角中的重复元素]对角矩阵将斜对角线视为维度存入二维数组，再转化为一维数组，公式视对角条数自行推导此部分可以去下面网址看相关方法的图解、二维数组按行、按列存储的基本概念及基本计算。行优先顺序存储：将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。【例】二维数组Amn的按行优先存储的线性序列为：a00,a01,…,a0(n-1),a10,a11,…,a1(n-1),……，a(m-1)1,a(m-1)2,…，a(m-1)(n-1)—３—LOC(aij)=LOC(a00)+[i×n+j]×d其中：①LOC(a00)是开始结点的存放地址（即基地址）②d为每个元素所占的存储单元数③由地址计算公式可得，数组中任一元素可通过地址公式在相同时间内存取。即顺序存储的数组是随机存取结构。列优先顺序存储：将数组元素按列向量排列，第i+1个列向量紧接在第i个列向量后面。【例】二维数组Amn的按列优先存储的线性序列为：a00,a10,…,a(m-1)0,a01,a11,…,a(m-1)1,……，a0(n-1),a1(n-1),…，a(m-1)(n-1)LOC(aij)=LOC(a00)+[j×m+i]×d9、二叉树的基本概念、存储结构、基本性质。二叉树是一种树形结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。顺序存储结构#defineMAX_TREE_SIZE100typedefTElemtypeSqBiTree[MAX_TREE_SIZE];SqPiTreebt;链式存储结构typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;二叉树的基本性质性质1：在二叉树的第i层上至多有2^(i-1)个结点（i=1）性质2：深度为k的二叉树至多有2^k-1个结点（k=1）性质3：对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。性质4：具有n个结点的完全二叉树的深度为[lgn/lg2]+1。性质5：如果对一颗有n个结点的完全二叉树的结点按层序编号(从第1层到第[lgn/lg2]+1层，每层从左到右)，则对任一结点i(1=i=n),有（1）如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲PARENT(i)是结点[i/2];（2）如果2in，则结点i无左孩子（结点i为叶子节点）；否则其左孩子LCHILD(i)是结点2i。（3）如果2i+1n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1。10、线索二叉树的基本概念、存储结构。若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。为了避免混淆，尚需改变节点结构，增加两个标志域，结构如下lchildLTagdataRTagrchild其中LTag={0lchild域指示结点的左孩子1lchild域指示结点的前驱}RTag={0rchild域指示结点的右孩子1rchild域指示结点的后继}—４—以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称之为线索二叉树。存储表示：typedefenumPointerTag{Link,Thread};//Link==0:指针,Thread==1,线索typedefstructBiThrNode{TElemTypedata;structBiThrNode*lchild,*rchild;PointerTagLTag,RTag;}BiThrNode,*BiThrTree;11、树的孩子兄弟链表的基本概念及存储结构。3种常用的链表结构1.双亲表示法2.孩子表示法这两种表示法可以看书P135~P136※3.孩子兄弟表示法孩子兄弟表示法又称二叉树表示法，即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibling域。typedefstructCSNode{ElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;12、哈夫曼树及哈夫曼编码的基本概念。（P144）假设有n个权值{w1,w2,……wn}，试构造一棵有n个叶子节点的二叉树，每个叶子节点带权为wi，则其中带权路径长度WPL最小的二叉树称为最优二叉树或哈夫曼树。设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一棵哈夫曼树的问题，由此得到的二进制前缀编码便称为哈夫曼编码。13、图的基本概念、邻接矩阵图、邻接表图、逆邻接表图、十字链表的存储结构。图形结构中，结点之间的关系是可以任意的，图中任何两个数据元素之间都可能相关。图是一种数据结构，在图中的数据元素通常称做顶点，V是顶点的有穷非空集合；VR是两个顶点之间的关系的集合。若v,w∈VR，则v,w表示从v到w的一条弧，且称v为弧尾或初始点，称w为弧头或终端点，此时的图称为有向图。若v,w∈VR必有若w,v∈VR即VR是对称的，则以无序对(v,w)代替这两个有序对，表示v和w的一条边，此时的图称为无向图。（还需了解完全图，稀疏图，稠密图，邻接点，入度，出度，连通图，连通分量，强连通图，强连通分量等概念）邻接矩阵存储表示#defineINFINITYINT_MAX//最大值#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向图，有向网，无向图，无向网}typeedefstructArcCell{VRTypeadj;//VRType是定点关系类型，无权图用1或0表示相邻否；带权图，—５—则为权值类型InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数Graphkind;//图的种类标志}MGrap;邻接表存储表示#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针InfoType*info;//该弧相关信息的指针}ArcNode;typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数和弧数intkind;//图