《数据结构总结》由会员分享，可在线阅读，更多相关《数据结构总结（14页珍藏版）》请在金锄头文库上搜索。
1、数据结构总结一、绪论1、数据结构：数据结构是一门讨论“描述现实世界实体的数学模型（非数值计算）及其上的操作在计算机中如何表示 和实现”的学科。具有相同特征的数据元素的集合，如果在这些数据元素之间存在一种或多种特定的关系，则称为 一种数据结构。2、建立模型：3、数据：客观对象的符号表示；数据元素：数据的基本单位，在计算机程序中通常作为一个整体考虑和处理，通常具有完整确定的实际意义。（节 点、顶点、记录）数据项：数据不可分割的最小标识单位。一个数据元素可由若干数据项组成，通常不具有完整确定的实际意义。4、数据的逻辑结构：数据之间的逻辑关系，是抽象的数学模型。5、数据元素之间存在四种基本结构：集合（
2、无关系），线性结构（一对一）：除第一个元素和最后一个元素外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后 继，如表、栈。树形结构（一对多）：每一个元素只有一个直接前趋，有0个或多个直接后继。如树图状结构（多对多）：每一个元素可以有0个或多个直接前趋，有0个或多个直接后继。如图。7、数据的存储结构：顺序存储结构，链式存储结构，散列结构和索引结构。8、一个算法必须满足以下五个重要特性：有穷性、确定性、可行性、有输入和有输出。9、评价算法的标准：正确性，可读性，可维护性，健壮性，效率。10、算法效率的度量：计算复杂度、渐进复杂度11、老师的课后题：数据结构定义：是一门研究非数值计算的程序设计问
3、题中计算机的操作对象以及它们之间的关系和操作等的学科。数据结构：数据元素和数据元素关系的集合。数据的逻辑结构：只抽象反映数据元素的逻辑关系数据的存储（物理）结构：数据的逻辑结构在计算机存储器中的实现。存储结构分为：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。数据的逻辑结构与存储结构密切相关：算法设计-逻辑结构；算法实现-存储结构。数据的运算：检索、排序、插入、删除、修改等第二章、线性表的基本概念1、线性表特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素。存在唯一的一个被称作“最后一
4、个”的数据元素。除第一个外，集合中的每个数据元素均只有一个前驱。除最后一个外，集合中的每个数据元素均只有一个后继。2、线性表的元素1）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；2）在表中a.1领先于a.，a.领先于a.+1，称a是a.的直接前趋，a.+1是a.的直接后继；3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。线性表是一种线性数据结构；4）元素的个数n称为表的长度，n=0时称为空表；5）气是表的第.个元素，称.为数据元素气的序号，每个元素在线性表中的位置，仅取决于它的序号。6）可在表的任意位置进行插入和
5、删除操作。13、顺序表的特点：用连续的存储单元存放线性表的元素，元素存储顺序与元素的逻辑顺序一致。4、线性表的链式存储结构特点：1）用一组任意的存储单元存储线性表的数据元素。2）利用指针实现了用不相邻的存储单元存放逻辑上相邻的一组元素。3）每个数据元素气，除存储本身信息外，还需存储其直接后继的信息（指针）。5、结点1数据域：数据元素本身的信息指针域：指示直接后继的存储位置6、几个概念：头指针：存放线性链表中第一个结点的存储地址；空指针：不指向任何结点，线性链表最后一个结点的指针通常是指针；头结点：线性链表的第一数据元素结点前面的一个附加结点，称为头结点。头结点不保存数据。带头结点的线性链表：第
6、一元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表；6、链表中没有数据结点称为：空表7、结点的形式定义：Typedef struct LNode ElemType data;/ 数据域struct Lnode *next; / 指针域 LNode， * LinkList；LinkList L；/ L为单链表的头指针，是LinkList类型的变量8、单链表操作的特点：单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。因 此，查找第i个数据元素的基本操作为：移动指针，比较j和i。9、静态链表：用数组实现的链式结构，称为静态链表。10、线性链表的特点：1. 用
7、一组任意的存储单元存储线性表中数据元素；2. 通过指针保存直接后继元素的存储地址来表示数据元素之间的逻辑关系；3. 通过头指针（或首结点）给出线性链表；4. 链表中结点空间是动态分配的；5. 插入、删除操作通过修改结点的指针实现；6. 只能顺序存取元素，不能直接存取元素。11、循环链表（带有头结点的单向环表）最后一个结点的指针域的指针又指回第一个结点（头结点）的链表。判断为是否空表的条件：h-next=h12、循环链表的特点：1. 从一个结点可找到链表中的任意一个结点；2. 判断是否为表尾结点的条件：p-next = L。3. 有时，用表尾指针表示循环链表。第三章栈1、栈是限定仅能在表尾一端进
8、行插入、删除操作的线性表。表尾端称为栈顶，表头端称为栈底。2、能进行插入和删除的一端称为栈顶，另一端称为栈底。称插入操作为进栈，删除操作为出栈。进栈出栈操作只能在 栈顶进行。3、第一个进栈的元素在栈底；最后一个进栈的元素在栈顶；第一个出栈的元素为栈顶元素；最后一个出栈的元素为栈底元素。栈的特点：后进先出4、 空栈top = base ； 栈满 top-base = stacksize （无可分配空间）7、栈的链式存储结构，也称链栈8、栈顶元素的位置由一个称为栈顶指针的变量指示，进栈和出栈操作都要修改栈顶指针9、队列是限定仅能在表头进行删除，表尾进行插入的线性表。10、能进行插入的一端称为队尾，
9、能进行删除的一端称为队头。称插入操作为入队，删除操作为出队。11、第一个入队的元素在队头；最后一个入队的元素在队尾；第一个出队的元素为队头元素；最后一个出队的元素为队尾元素，队列的特点：先进先出。13、存在问题：设数组大小为M，则：当front=0，rear= M时，再入队发生溢出真溢出，当front 0，rear= M时，再入队发生溢出一溢出。14、队列的应用:1）解决计算机主机与外设不匹配的问题；2）解决由于多用户引起的资源竞争问题；3) 离散事件的模拟一一模拟实际应用中的各种排队现象；4) 用于处理程序中具有先进先出特征的过程。第五章数组和广义表1、数量固定，数据类型相同的(变量)元素组
10、合在一起。使用一个名称代表它。这个名称就檄组名。如果要访问其 中某个元素(变量)，可以使用元素的索引值(下标)来访问它。在C语言中，数组元素的索引值从0开始。2、二维数组是数据元素为线性表的线性表。3、数组的逻辑结构：二维数组中的每个元素都受两个线性关系的约束一一关系、列关系。4、数组的基本操作：1)读：给定一组下标，读出对应的数组元素；2)写：给定一组下标，存储或修改与其相对应的数组元素。读/写操作本质上只对应一种操作一一寻址。确定指定元素在内存中的物理地址。5、数组的存储：两种形式，既可以是顺序存储，也可以采用链式结构。6、数组的存储结构与寻址一一一维数组设具有M个元素的一维数组的下标范围
11、为闭区间0, M-1，每个数组元素占用L个存储单元。气的存储地址：Loc( a. )=Loc(a) + iXL7、数组的存储结构与寻址一一二维数组常用的映射方法有两种：按行优先：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。按列优先：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。8、 值相同元素或者非零元素的分布有一定规律的矩阵，称为特殊矩阵。(对称矩阵、上(下)三角矩阵。)9、含有较多值相同或较多零元素，且值相同或者零元素分布没有一定规律的矩阵称为稀疏矩阵。10、稀疏矩阵采用三元组存储：(行，列，值)11、广义表是一种不同构的线性结构，*12、广义表的基本
12、性质1. 广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表；2. 在线性表中数据元素是单个元素，而在广义表中，元素可以是单个元素称为原子(atom)，也可以是广义表， 称为广义表的子表(sublist)；3. 当每个元素均为原子且类型相同时，就是线性表。*13、广义表的术语表头：LS的第一个元素称为表头表尾：其余元素组成的表称为LS的表尾表长：为最外层包含元素个数深度：所含括弧的重数。原子的深度为0，“空表”的深度为1例：A =() 空表表长：0；深度：1B = ( b, c, d )表长：3,深度：1C = ( a, B ) = ( a, (b,c,d)表长：2，深度：2D =
13、( A, B, C ) = ( ( ), (b,c,d), (a,(b,c,d)表长：3,深度：3*14任何一个非空广义表LS = (a1, a2,，an)均可分解为：表头Head(LS) = a1和表尾Tail(LS) = (a2,， an )两部分。例如：D = ( E, F ) = ( ( a, ( b, c )，)F ) Head( D ) =E Tail( D ) =(F)； Head( E ) =a Tail( E ) =(，b c) ； Head( (b, c) ) = (b， c)， Tail( (b, c) ) =() ； Head( (b, c) ) = b, Tail(
14、(b, c) ) = (c)； Head( ( c ) ) = c Tail( ( c )=()*15、求广义表的深度GListDepth( L ):广义表L的深度=广义表L中括号重数例 L = ( a , ( b ,c ) , ( ( d )GListDepth( a )= 0 原子GListDepth( (b,c) )= 1 线性表GListDepth( (d) )= 2GListDepth( L )= 316、比较广义表和线性表的结构特点。相似处：都是链表结构。不同处：1广义表的数据元素可能还是个广义表；2删除时，不仅要删除原子结点，还需要删除相应的表结点。17、广义表的特殊形态在广义表
15、中，若任意一个兀素（原子、子表）只能在广义表中出现一次，称为纯表，纯表：对应一棵树。线性表是只包含原子的纯表。若存在共享元素（原子或子表在表中出现多次），则称为再入表，如果再入表中没有 回路：对应一个DAG（有向无环图）。递归表是有回路的再入表，循环表（cyclic list，递归表）对应有向图。18、广义表应用：函数的调用关系，内存空间的引用关系，LISP语言第六章树和二叉树一、树是n个结点的有限集合。树是递归结构，树的定义是递归定义。任意一棵非空树中：（1）有且仅有一个称为根root的结点。（2）其余结点可分为若干个互不相交的集合，且这些集合中的每一集合本身又是一棵树，称为根的子树。二、树的应用常用的数据组织形式一计算机的文件系统。不论是DOS文件系统还是window文件系统，所有的文件都是用树的形式进行组织。三、树的基本术语树的结点：包含一个数据元素的内容及若干指向子树的分支
