数据结构基本概念基本概念?数据数据是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。?数据元素数据元素也称为结点，是表示数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。?数据项数据项是构成数据元素的不可分割的最小单位。?数据对象数据对象是具有相同性质的数据元素的集合，是数据的子集。注意：在不产生混淆的情况下，将数据对象简称为数据。?数据结构数据结构是指相互之间存在一定关系的数据元素的集合，即数据结构是一个二元组DataStructure=(D,R)，其中D是数据元素的集合，R是D上关系的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。?数据的逻辑结构数据的逻辑结构是指数据元素之间逻辑关系的整体。根据数据元素之间逻辑关系的不同，数据结构分为四类:集合：数据元素之间就是“属于同一个集合”，除此之外，没有任何关系；线性结构：数据元素之间存在着一对一的线性关系；树结构：数据元素之间存在着一对多的层次关系；图结构：数据元素之间存在着多对多的任意关系。注意：数据结构分为两类：线性结构和非线性结构。?数据的存储结构数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常有两种存储结构：顺序存储结构和链接存储结构。顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的存储位置来表示的。链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。注意：存储结构除了存储数据元素之外，必须存储数据元素之间的逻辑关系。?抽象数据类型抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称。抽象数据类型提供了使用和实现两个不同的视图，实现了封装和信息隐藏。?算法的定义通俗地讲，算法是解决问题的方法，严格地说，算法是对特定问题求解步骤的一种描述，是指令的有限序列。?算法的特性输入：一个算法有零个或多个输入（即算法可以没有输入），这些输入通常取自于某个特定的对象集合。输出：一个算法有一个或多个输出（即算法必须要有输出），通常输出与输入之间有着某种特定的关系。有穷性：一个算法必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法中的每一条指令必须有确切的含义，不存在二义性。并且，在任何条件下，对于相同的输入只能得到相同的输出。可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。?线性表的定义线性表简称表，是零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性表的长度，长度等于零时称为空表。?线性表的逻辑关系在一个非空表L=(ai,a2,an)中，任意一对相邻的数据元素ai-i和ai之间(1in)存在序偶关系(ai-i,a),且ai-i称为ai的前驱，ai称为ai-i的后继。在这个序列中，ai无前驱，an无后继，其它每个元素有且仅有一个前驱和一个后继。?顺序表的存储结构定义用MaxSize表示数组的长度，顺序表的存储结构定义如下：Sizei00dataMaxSize;/ElemType表intlength;length表示线?顺序表是随机存取结构设顺序表的每个元素占用c个存储单元，则第i个元素的存储地址为：LOC(ai)=LOC(ai)+(i-1)xc?顺序表的优缺点顺序表利用了数组元素在物理位置上的邻接关系来表示线性表中数据元素之间的逻辑关系，这使得顺序表具有下列优点：无需为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速地存取表中任一位置的元素（即随机存取）同时，顺序表也具有下列缺点：插入和删除操作需移动大量元素。在顺序表上做插入和删除操作，等概率情况下，平均要移动表中一半的元素。表的容量难以确定。由于数组的长度必须事先确定，因此，当线性表的长度变化较大时，难以确定合适的存储规模。造成存储空间的“碎片”。数组要求占用连续的存储空间，即使存储单元数超过所需的数目，如果不连续也不能使用，造成存储空间的“碎片”现象。?单链表的存储结构定义单链表的存储结构定义如下：定的数据类型data;/ElemType表示不确数类型*强曲Node*nft为单链表的头指针?双链表的存储结构定义双链表存储结构定义如下:tructDulNode据类型驱指针域gexp为后继指针域ElemTypedata;/ElemType表示不确定的数*next;/prior为前:表示双链表的头指针?栈的定义栈是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。?栈的操作特性栈的操作具有后进先出的特性。?队列的定义队列是只允许在一端进行插入操作，而另一端进行删除操作的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。?队列的操作特性队列的操作具有先进先出的特性。?循环队列中解决队空队满的判断条件方法一：附设一个存储队列中元素个数的变量num,当num=0时队空，当num=QueueSize时为队满；方法二：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元；即队空的条件是front=rear，队满的条件是(rear+1)%QueueSize=front，队列长度为(rear-front+QueueSize)%QueueSize。方法三：设置标志flag，当front=rear且flag=0时为队空，当front=rear且flag=1时为队满。?串的定义串是零个或多个字符组成的有限序列。?空格串和空串的定义只包含空格的串称为空格串。串中所包含的字符个数称为串的长度，长度为0的串称空串，记作”“。?串的比较串的比较是通过组成串的字符之间的比较来进行的。给定两个串：X=X1X2XnY二yiy2ym则当n=m且xi=yi,，xn=ym时，称X=Y;当下列条件之一成立时，称XvY:nvm,且Xi=yi(i=1,2,，n);存在某个kmin(m,n)，使得Xi=y(i=1,2,k-1),Xkvyk。?改进的模式匹配算法中nextj的求法用nextj表示tj对应的k值(Kjj)在一个数组SA中的下标为：k=ix(i-i)/2+j-1。上三角中的元素aij(ivj)，贝I访问和它对应的下三角中的元素aji即可，即：k=jx(j-i)/2+i-i。?三角矩阵的压缩存储中：下三角矩阵中任一元素aij在一个数组SA中的下标k与i、j的对应关系为:1)xk=ix(i-1)/2+上三角矩阵元素aij在SA中的下标为：k=(i-(2n-i+2)/2+(j-i)。?稀疏矩阵的压缩存储方式三元组顺序表和十字链表?三元组的定义structelementint.row,epi;ElemTypeitem；?广义表的定义广义表是n(n0)个数据元素的有限序列。?表头当广义表LS非空时，称第一个元素为LS的表头；?表尾称广义表LS中除去表头后其余元素组成的广义表为LS的?长度广义表LS中的直接元素的个数称为LS的长度;?深度广义表LS中括号的最大嵌套层数称为LS的深度?树的定义树是n（n0）个结点的有限集合。当n=0时，称为空树；任意一棵非空树满足以下条件：有且仅有一个特定的称为根的结点；当n1时，除根结点之外的其余结点被分成m（m0）个互不相交的有限集合Ti,T2,，Tm,其中每个集合又是一棵树，并称为这个根结点的子树。?结点的度、树的度某结点所拥有的子树的个数称为该结点的度；树中各结点度的最大值称为该树的度。?叶子结点、分支结点度为0的结点称为叶子结点，也称为终端结点；度不为0的结点称为分支结点，也称为非终端结点。?孩子结点、双亲结点、兄弟结点?路径、路径长度为该结点的孩子结点;反之,如果树的结点序列ni,n2,nk满足如下关系：结点ni是结点ni+i的双亲（Kivk），则把ni,n2,nk称为一条由ni至nk的路径；路径上经过的边的个数称为路径长度。?祖先、子孙如果从结点x到结点y有一条路径，那么x就称为y的祖先，而y称为x的子孙。注意：某结点子树中的任一结点都是该结点的子孙。?结点的层数、树的深度（高度）规定根结点的层数为1,对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层；树中所有结点的最大层数称为树的深度，也称为树的高度。?二叉树的定义二叉树是n（n0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。?二叉树的特点二叉树的特点是：每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点；子树的次序不能任意颠倒，某结点即使只有一棵子树也要区分是左子树还是右子树。注意：二叉树和树是两种树结构。?二叉树的基本形态二叉树具有五种基本形态：空二叉树；只有一个根结点；根结点只有左子树；根结点只有右子树；根结点既有左子树又有右子树。?斜树所有结点都只有左子树的二叉树称为左斜树；所有结点都只有右子树的二叉树称为右斜树；左斜树和右斜树统称为斜树。斜树的特点：每一层只有一个结点，即只有度为1和度为0的结点并且只有一个叶子结点；斜树的结点个数与其深度相同。?满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。满二叉树的特点：叶子结点都在最下一层；只有度为0和度为2的结点。?完全二叉树对一棵具有n个结点的二叉树按层序编号，如果编号为i(1i1）。性质2在一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。性质3在一棵二叉树中，如果叶子结点的个数为no,度为2的结点个数为n2，则no=n2+1。性质4具有n个结点的完全二叉树的深度为log2n1。性质5对一棵具有n个结点的完全二叉树中的结点从1开始按层序编号，则对于任意的编号为i（Ki1,则结点i的双亲的编号为i/2；否则结点