理工类专业课复习资料-《数据结构》基本概念

1数据数据是信息的载体，在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号数据元素虑和处理。数据项的不可分割的最小单位。数据对象数据结构相互之间存在一定关系的数据元素的集合，即数据结构是一个二元组DataStructure=(D,数据的逻辑结构数据的逻辑结构是指数据元素之间逻辑关系的整体。根据数据元素之间逻辑关系的不同，数据结构分两类：线性结构和非线性结构。数据的存储结构数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。通常有两种存储结构：顺顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指抽象数据类型构以及定义在该结构上的一组操作的总称。抽象数据类型提供了使用和实算法的定义通俗地讲，算法是解决问题的方法，严格地说，算法是对特定问题求解步骤的一种描述，是指令的有算法的特性法可以没有输入)，这些输入通常取自于某个特定的对象法必须要有输出)，通常输出与输入之间有着某种特定的2线性表的定义线性表简称表，是零个或多个具有相同类型的数据元素的有限序列。数据元素的个数称为线性表的长线性表的逻辑关系nan顺序表的存储结构定义#defineMaxSize100typedefstruct{ElemTypedataMaxSize//ElemType表示不确定的数据类型intlength;//length表示线性表的长度顺序表是随机存取结构LOC(ai)=LOC(a1)＋(i－1)×c顺序表的优缺点顺序表利用了数组元素在物理位置上的邻接关系来表示线性表中数据元素之间的逻辑关系，这使得顺；⑵可以快速地存取表中任一位置的元素(即随机存取)。单链表的存储结构定义StructNodeemTypedataElemTypeNodenext}*first;//first为单链表的头指针双链表的存储结构定义3ode{ElemTypedata//ElemType表示不确定的数据类型xt}*first;//first表示双链表的头指针栈的定义栈的操作特性队列的定义队列是只允许在一端进行插入操作，而另一端进行删除操作的线性表。允许插入的一端称为队尾，允队列的操作特性循环队列中解决队空队满的判断条件方法二：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元；即队空的条件是arfrontQueueSizeQueueSize串的定义空格串和空串的定义串的比较当下列条件之一成立时，称X＜Y：改进的模式匹配算法中next[j]的求法nextjtj对应的k值(1≤j≤m)，其定义如下：数组的基本操作数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。因此，在4二维数组的寻址按行优先，设二维数组的行下标与列下标的范围分别为[l1，h1]与[l2，h2]，则任一元素aij的存储特殊矩阵的定义矩阵压缩存储的基本思想ikjjiki×(i-k稀疏矩阵的压缩存储方式字链表三元组的定义nt{introwcollemTypeitem广义表的定义广义表是n(n≥0)个数据元素的有限序列。表头表尾长度深度树的定义结点的度、树的度5叶子结点、分支结点。孩子结点、双亲结点、兄弟结点结点称为该结点的孩子结点；反之，该结点称为其孩子结点的双亲路径、路径长度祖先、子孙如果从结点x到结点y有一条路径，那么x就称为y的祖先，而y称为x的子孙。结点的层数、树的深度(高度)二叉树的定义nn合或者为空集(称为空二叉树)，或者由一个根结点和两叉树组成。二叉树的特点叉树中不存在度大于2的结点；⑵子树的次二叉树的基本形态二叉树具有五种基本形态：⑴空二叉树；⑵只有一个根结点；⑶根结点只有左子树；⑷根结点只斜树所有结点都只有左子树的二叉树称为左斜树；所有结点都只有右子树的二叉树称为右斜树；左斜树和满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二点。完全二叉树二叉树的基本性质性质1二叉树的第i层上最多有2i-1个结点(i≥1)。6≤i≤n)的结点(简称为结点i)，有：二叉树的存储ode{TypedataBiNodelchildrchild}*root;//root表示二叉链表的头指针Node{TypedataTriNode*lchild,*rchild,*parent;//parent指向该结点的双亲}*root;//三叉链表的头指针遍历的含义所谓遍历就是无重复无遗漏地访问。二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的二叉树的遍历次序定义前序遍历(或称前根遍历、先序遍历)操作返回；否则中序遍历(或称中根遍历)操作返回；否则后序遍历(或称后根遍历)操作返回；否则7二叉树的层序遍历是从二叉树的第一层(根结点)开始，从上至下逐层遍历，在同一层中，则按从左线索二叉树的定义nn点在某种遍历序列中的前驱和二叉链表称为线索链表。线索二叉树的存储结构定义umflagChildThreadrNode{ElemTypedata//ElemType表示不确定的数据类型rNodelchildrchildtagrtag}*root;//root表示线索链表的头指针树的存储结构defineMaxSize100;de{mTypedatarent/树中最大结点个数数组元素的类型该结点的双亲在数组中的下标PNodeTreeMaxSizeode{孩子结点hildnextstructCBNode/表头结点{TypedataCTNodefirstchild/指向孩子链表的头指针de{TypedatafirstchildderightsibElemType表示不确定的数据类型firstchild指向该结点的第一个孩子/rightsib指向该结点的右兄弟树转换为二叉树8森林转换为二叉树二叉树转换为树或森林xyx孩子、……，都与结点y用线连起来；叉树的遍历序列之间的对应关系根据树与二叉树的转换关系以及树和二叉树遍历的操作定义可知，树的遍历序列与由树转化成的二叉树的遍历序列之间具有如下对应关系：树的前序遍历序列等于二叉树的前序遍历序列，树的后序遍历序列哈夫曼树中叶子结点的权值量。二叉树的带权路径长度n各个叶子结点的路径长度与相应叶子结点权值的乘：nWPL=wklkk=1哈夫曼树定义给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，将其中带权路径长度最小的二叉树称哈夫曼算法的基本思想；图的定义无向图与有向图9intarcMaxSizeMaxSize//存放图中边的信息intarcMaxSizeMaxSize//存放图中边的信息简单图邻接、依附无向完全图、有向完全图，则称该图为无向完全图。含有n个顶点的无向完全图互为相反的两条弧，则称该图为有向完全图。含有n个稠密图、稀疏图顶点的度、入度、出度nTD(vi)=2eennID(vi)=OD(vi)=ei=1i=1连通图、连通分量j强连通图、强连通分量邻接矩阵的存储结构定义defineMaxSize10typedefstruct{defineMaxSize10typedefstruct{ertexertexNumarcNumertexe/图的顶点数和边数邻接表的存储结构定义接存储相结合的存储方法，具体方法为：将顶点vi的所有邻接点链成一个单链表，称为顶点vi的边表(对于有向图则称为出边表)，边表的头指针和顶点的数据信息采用顺序存储 (称为顶点表)。所以，在邻接表中存在两种结点：顶点表结点和边表结点。ext边表结点结点结构exodejvex//定义边表结点/邻接点域ArcNodenext;texNode{Typevertex//定义顶点表结点//ElemType表示不确定的数据类型ArcNodefirstedge#defineMaxSize10typedefstruct{VertexNodeadjlistMaxSizetvertexNumarcNum图的遍历次序定义//顶点表图的顶点数和边数最小生成树的定义普里姆(Prim)算法的基本思想克鲁斯卡尔(Kruskal)算法的基本思想迪杰斯特拉(Dijkstra)算法的基本思想与原来的假设相比较，取路径长度较小者为当前最短路径。重复上述过程，直到集合V中全部顶点加入到Floyd算法的基本思想AOV网的定义在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶拓扑序列的定义j拓扑排序的基本思想查找算法的时间性能查找算法用关键码的比较次数来度量查找算法的时间性能。对于查找成功的情况，将关键码比较次数nASL=picii=1顺序查找算法的时间复杂度ni顺序查找的适用情况顺序查找对表中记录的存储没有任何要求，顺序存储和链接存储均可应用；对表中记录的有序性也没折半查找的适用情况折半查找(也称对半查找、对分查找、二分查找)要求线性表中的记录必须按关键码有序，并且必须折半查找的基本思想比较对象，则(1)若给定值与中间记录的关键码相等，则查找成功；(2)若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；(3)若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。折半查找的时间复杂度O(log2n)。二叉排序树的定义：二叉排序树的查找性能排序树是平衡的，则其查找效率为O(log2n)。如果二叉排序树为一棵斜树，则其查找效率为平衡二叉树的定义构造平衡二叉树的基本思想。平衡调整的四种类型散列查找的基本思想散列查找的基本概念采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表，将关键码映射。散列查找的关键问题处理冲突的方法冲突得到的散列表叫做闭散列表。所谓开放定址法，就是由关键码得到的散列地址一旦产生了冲突，就去寻找下一个空的散列地址，只测法H(key)=d，闭散列表的长度为m，则发生冲突时，寻找下一个散列地址的公式为：m争夺的现象，称为堆积或聚集。次探测法机探测法当发生冲突时，随机探测法探测下一个散列地址的位移量是一个随机数列，即寻找下一个散列地址的Hi=(H(key)+di)%m(di是一个随机数列，i=1，2，……，m-1)拉链法(链地址法)冲突构造的散列表叫做开散列表。拉链法的基本思想是：将所有散列地址相同的记录，即所有关键码为同义词的记录存储在一个单链表直接插入排序的基本思想直接插入排序的基本思想是：依次将待排序序列中的每一个记录插入到一个已排好序的序列中，直到直接插入排序算法的性能。希尔排序的基本思想希尔排序的基本思想是：先将整个待排序记录序列分割成若干个子序列，在子序列内分别进行直接插希尔排序算法的性能gnn起泡排序的基本思想的记录为止。起泡排序算法的性能快速排序的基本思想成独立的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值，然后分别快速排序的性能nn简单选择排序的基本思想简单选择