logo资料库

数据结构知识点总复习.docx

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.05M 资料格式：docx 举报 版权申诉
第1页 / 共37页
第2页 / 共37页
第3页 / 共37页
第4页 / 共37页
第5页 / 共37页
第6页 / 共37页
第7页 / 共37页
第8页 / 共37页
资料共37页，剩余部分请下载后查看
    数据结构知识点总结 概论 1：数据的结构直接影响算法的选择和效率。 2：数据->数据元素（元素，结点，记录） 数据的基本单位->数据项（字段，域）这是数据不可分割的最小单位 3：数据类型：原子数据类型：值不可分（整型，字符型，实型）和结构数据类型：值可分 解（数组类型，结构类型）用户自己定义的 4：数据结构：逻辑结构，物理结构：存储结构（数据结构在计算机中的表示），运算特征。 逻辑结构：集合，线性结构（一对一），树型结构（一对多），图状结构（多对多） 运算：插入，删除，查找，排序。 数据结构定义：按某种逻辑关系组织起来的一批数据，应用计算机语言，按一定的存储表示 方法把它们存储在 计算机的存储器中，并在这些数据上定义了一个运算的集合。 数据的 4 种基本存储方法： 顺序存储方法：逻辑上相邻的节点存储在物理位置相邻的存储单位中，结点之间的逻辑关系 由存储单元的邻接关系来体现。 该方法主要应用于线性的数据结构。 链接存储方法：不要求逻辑上相邻的结点在物理位置上也相邻，结点之间的逻辑关系是由附 加的指针来表示的。 索引存储方法：存储结点信息的同时，建立附加的索引表。索引表中的每一项称为索引项。 索引项的一般形式：（关键字，地址）
    散列存储方法：根据结点的关键字直接计算出该结点的存储地址。 例子：线性结构+顺序存储方法+栈=顺序栈，线性结构+链接存储方法+队列=链队列。 5：算法特性：有穷性，确定性，可行性，输入，输出。 6：算法好坏的判断依据：正确性，健壮性，可读性，执行耗费时间，执行耗费空间。 7：常用函数关系排序：c < log2n
    3：线性表的存储结构用数组来实现 4：顺序表：顺序存储结构的线性表 特点：元素在计算机内部存储的物理位置相邻来表示线性表中数据元素之间的逻辑相邻关系。 一段连续的内存空间来保存线性表结点的值。 5：在顺序存储中，能够方便的查找指定位置的结点值，但是，插入和删除结点比较麻烦。 5：链表：链式存储结构的线性表 6：单链表：一个结点只包含一个指针域，一个结点结构=数据域+指针域。指针域保存地址 信息。 用单链表来表示线性表时，结点之间的逻辑关系是由结点中的指针来指示的。 7：为了方便判断空表，插入和删除结点，我们在单链表的第一个结点前面加上一个头结点。 单链表的头指针 L 指向头结点，如果 L->next=null,表示链表为空表。 8：单链表中，任何两个结点的存储位置之间没有固定的联系，要寻找某一个结点，必须从 头指针出发， 一个一个结点地向后寻找。 9：线性表的链式存储方式利用不连续的内存空间来保存结点的信息，因此，在结点中，不 仅需要保存结点 本身的数据值，还需要利用指针域保存指向直接后继的指针。 10：单链表的操作：清除链表，求表长，定位查找，插入数据，删除数据时间复杂度为 O （n） 11：在链式存储中，插入或者删除结点不需要大量的移动结点；但是在定位时，却需要遍历 整个链表。 12：单循环链表：如果把单链表的最后一个节点的指针域指向第一个结点（头结点）。则构
    成一个首尾相连的循环链表。 13：循环链表中判断一个链表是否为空，需要看头结点的 next 域是否等于自身。 14：循环链表建立和判断的时间复杂度为 O（1），插入和删除的时间复杂度为 O（n） 15：双向链表：两个指针域，一个指向直接前趋，一个指向直接后继。 16：双向链表中结点的特点，结点的 next 的 prior 是结点本身，结点的 prior 的 next 是结点 本身。 17：判断双向链表为空表：看是否两个指针域都为 NULL。 18：双向链表的建立和判断时间复杂度为 O（1），插入和删除的时间复杂度为 O（n） 19：双向循环链表：双向链表中的头结点和尾结点连接起来。 20：判断双向循环链表为空表：看是否两个指针域都指向自身。 21：线性表顺序存储与链式存储的比较 时间角度：当线性表的操作操作主要是进行查找，而很少进行插入和删除时，应该采用顺序 表进行存储 当对于频繁的插入和删除操作的线性表，则应该采用链表作为为存储结构 空间角度：顺序表的存储空间是静态分配的，在程序引入前必须规定其存储闺蜜，如果估计 过大，会造成空间的浪费。估计过小，会造成空间的溢出。 动态链表是动态分配的，只要内存空间有空闲，就不会产生溢出。 线性表的长度变化比较大时，应该采用动态链表为存储结构。 22：顺序表是采用数组实现的，链表是采用指针（动态链表）或者游标（静态链表）来实 现的。
    栈和队列 1：栈和队列：操作受限的线性表，称为限定性的线性表结构。 2：栈：仅允许在一端进行插入和删除运算线性表。后进先出（LIFO）线性表 栈顶：允许进行插入和删除的那一端。 栈底：不可以进行插入和删除的那一端（线性表的表头） 进栈，入栈，压栈：在一个栈中插入新元素，成为新的栈顶元素 出站，退栈：在一个栈中删除一个元素，删除栈顶元素，使下一个成为新的栈顶元素。 3：栈的基本操作：构造空栈，清除所有元素，判断栈是否为空，返回栈顶元素，入栈，出 栈。 4：根据存储结构：顺序栈，链栈 顺序栈：利用地址连续的存储单元依次存放从栈底到栈顶的数组元素，数组 0 位置的元素 作为栈底元素 top=-1，表示栈空；top=maxsize-1，表示栈满，就相当于一维数组 在做入栈操作前，首先要判定栈是否满（满了叫上溢）；入栈指针 top 先加 1，然后入栈。 在做出栈操作前，先要判定栈是否为空（空的为下溢）；出栈指针 top 先减 1，然后出栈（指 针+1）。 链栈：相当于结点构成的单链表。 栈顶元素为单链表的第一个结点，因为栈顶元素操作频繁，所以经常用没有头结点的单链表。 链栈是动态分配结点空间的，所以操作时无需考虑上溢问题。 链栈的优点：可使多个栈共享空间；在栈中元素变化的数量较大，且存在多个栈的情况下， 链栈是栈的首选存储方式。 5：栈的应用：数值进制转换，括号匹配问题，子程序的调用，递归实现
    6：队列：限定在表的一段进行插入而在另一端进行删除的线性表。先进先出线性表（FIFO） 队头：允许删除的一端 队尾：允许插入的一端 入队：向队列中插入新元素，成为新的队尾元素 出队：从队列中删除元素，其后继元素成为新的队头元素。 7：队列的基本操作：构造空队列，判断队列为空，求队列长度，返回队头元素，插入队尾 元素，删除队头元素，清除队列元素。 8：根据存储结构：链队列，顺序队列 链队列：限制仅在表头进行删除和在表尾进行插入的单链表。拥有两个指针（头指针，尾指 针） 头指针指向头结点，队尾指针指向真正的队尾元素结点。 判断链队列为空：头指针和尾指针全部指向头结点。 入队：先将尾指针指向的元素的指针指向入队元素，然后尾指针指向入队元素。 出队：修改头指针中的指针，指向后继结点，但是当删除的元素是最后一个元素时，尾指针 需要指向回头结点。 顺序队列：用一组地址连续的存储单元依次存放从队列头到队列尾的元素。 这里除了定义一维数组还需要两个指针指向队头和队尾。 初始化空队列：front=rear=0； 入队：元素插入到 rear 所指向的空单元内，rear+1； 出队：删除数组头结点，front+1 在非空队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一个位置。 假溢出：当发生了若干次出队入队操作后，尾指针到了最后，无法插入了，但是队列元素<
    队列的单元数。 避免假溢出现象：使用循环队列。 循环队列：数组大小 maxsize，数组所表示的循环队列最多允许有 maxsize-1 个结点，rear 所指的单元始终为空。 循环队列队满条件：(rear+1)%maxsize==front 循环队列队空条件：rear==front 9：队列的应用：打印杨辉三角，迷宫问题。 10：递归：如果一个函数直接调用自己或者通过一系列调用间接地调用自己。 直接递归：在函数体内直接调用自身 间接调用：一个函数通过调用其他函数并由其他函数反过来又调用该函数 11:用到递归方法的情况： 第一种情况：定义是递归的。比如阶乘，Fibonacci 数列 第二种情况：数据结构时递归的。比如链表就是一种递归的数据结构 第三种情况：有些问题自身没有明显的递归结构，但用递归方法求解更简单。 12：递归消除：由于递归程序运行时要花费较多的时间和空间，效率较低，有时需要消去一 个程序中最经常执行部分的递归调用。 常用的是用迭代和栈进行递归消除。 串 1：串（字符串）：是一种特殊的线性表，它的每个节点仅由一个字符组成。通常用双引号把 串中字符括起来。 2：空串：长度为 0 的串
    3：空格串：串中都是空格字符，它有长度。 4：子串：串中任意个连续字符组成的子序列。 5：串：串变量（值可以改变），串常量（只能被引用不能改变其值） 6：顺序串：串的顺序存储结构，用一组地址连续的存储单元来依次存放串中的字符序列。 字符数组表示。 串结束标志：一般使用“\0”来确定串是否结束。也可以把串长度放在 ch[0]中。 基本操作：求串长，串复制，串连接，求子串，串删除。 缺点：事先定义了串长，这在程序运行前是很难估计的 定义了串的最大长度，串值空间被确定，是静态的，插入，连接操作被限制。 7：串的堆存储结构：依然是一组空间足够大的，地址连续的存储单元存放串值字符序列， 不同的是 存储空间的大小不是预先定义的，而是在程序执行过程中动态分配的。 指向字符串存储空间的是字符指针而非数组，若为空串，则指针为 null。 8：链串：串的链式存储结构：每个结点仅存储一个字符。便于插入和删除。 9：块链：由于链串每个结点的指针域所占空间比字符域大，存储空间利用率低， 所以在链串的每个结点存放多个字符，这样的结点叫做块。块的大小就是结点所容纳字符的 个数。 当结点大小大于 1 时，串的长度不一定正好是结点大小的整数倍，因此用特殊字符“#”填充。 10：串的模式匹配：子串定位操作。 两种方法：n 是主串长度，m 是模式串长度 第一种：时间复杂度 O（mn） KMP 算法：时间复杂度 O（m+n）
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料