精华内容
下载资源
问答
  • 数据结构期末复习笔记

    千次阅读 多人点赞 2019-12-22 21:15:26
    文章目录数据结构前言逻辑结构与物理结构算法线性表线性与非线性结构头指针与头结点链表为空判断单链表结构与顺序存储结构的优缺点栈和队列串子串的个数树二叉树遍历树和二叉树遍历对应关系树转成二叉树二叉树性质图...

    数据结构

    前言

    逻辑结构与物理结构

    逻辑结构:是指数据对象中数据元素之间的相互关系。

    • 集合结构:集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系。
    • 线性结构:线性结构中的数据元素是一对一的关系
    • 树形结构:树形结构中的数据元素之间存在一种一对多的层次关系
    • 图形结构:图形结构的数据元素时多对多的关系

    物理结构:是指数据的逻辑结构在计算机中的存储形式

    • 顺序存储结构:是把数据元素存放在地址连续的存储单元里,其数据元素间的逻辑关系和物理关系是一致的。
    • 链式存储结构:是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的。

    算法

    线性表

    线性与非线性结构

    线性结构是一个有序数据元素的集合。常用的线性结构有:线性表,栈,队列,双队列,一维数组,串。

    非线性结构,数学用语,其逻辑特征是一个结点元素可能有多个直接前趋和多个直接后继。常见的非线性结构有:二维数组,多维数组,广义表,树(二叉树等)。

    传统文本(例如书籍中的文章和计算机的文本文件)都是线性结构,阅读是需要注意顺序阅读,而超文本则是一个非线性结构。在制作文本时,可将写作素材按内部联系划分成不同关系的单元,然后用制作工具将其组成一个网型结构。阅读时,不必按线性方式顺序往下读,而是有选择的阅读自己感兴趣的部分。

    在超文本文件中,可以用一些单词,短语或图像作为连接点。这些连接点通常同其他颜色显示或加下划线来区分,这些形式的文件就成为超文本文件。通过非线性结构,可能实现页面任意跳转。

    有一个以上根结点的数据结构一定是非线性结构。

    头指针与头结点

    头指针头结点
    头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针头结点是为了操作统一和方便设立的,放在第一元素的节点之前,其数据域一般无意义(也可存放链表长度)
    头指针具有标识作用,所以长用头指针冠以链表的名字有了头结点,对在第一元素的节点前插入节点和删除第一节点,其操作与其他节点的操作就统一了
    无论链表表是否为空,头指针均不为空。头指针是链表的必要元素头结点不一定是链表的必要元素

    链表为空判断

    循环链表与单链表的判断主要差异就在于循环判断条件上:

    • head->next = null , 单链表为空
    • head->next = head, 循环链表为空

    栈和队列

    栈:限定在表尾进行插入和删除的线性表

    队列:只允许在一端进行插入操作,而在另一端进行删除操作的线性表

    链栈与顺序栈相比,一个明显的优点是通常不会出现栈满的情况

    循环队列满的条件是:(rear +1) % QueueSize == front

    循环队列长度计算公式:(rear - front + QueueSize) % QueueSize

    栈满的时候要考虑上溢的情况,栈空的时候要考虑下溢的情况。

    子串的个数

    串(string):是由零个或多个字符组成的有限序列,又名叫字符串。

    子串:串中任意个连续的字符组成的子序列称为该串的子串,空串也属于子串。

    • n个字符构成的字符串,假设每个字符都不一样,则共有n(n+1)/2+1个字符串

      实例应用:若串S=′software′,其子串的数目是()

      解析:n(n+1)/2+1=8(8+1)/2+1=37

    • 串中字符出现重复:字符串’wwwpqqpcom’所有非空子串(两个子串如果内容相同则只算一个)个数是()

      答案:50
      解析:包含重复子串共:n(n+1)/2+1=10(10+1)/2+1=55,减去重复:2个w,1个ww,1个q,1个.,所以共55-5=50个

    串的定位操作通常称为串的模式匹配

    二叉树遍历

    如果一个二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足所有的节点全部没有左子树或者所有的节点全部没有右子树,即二叉树的高度等于节点数。

    树和二叉树遍历对应关系

    二叉树森林
    先序遍历先序遍历先序遍历
    后序遍历中序遍历中序遍历

    树的先序对应二叉树的先序

    树的后序对应二叉树的中序

    树转成二叉树

    加线:在所有的兄弟节点之间加一条线

    去线:对树中每个结点,只保留它与第一个孩子节点的连线,删除它与其他孩子节点之间的连线。

    层次调整:以树的根节点为轴心,将整颗树顺时针旋转一定的角度,使之结构层次分明。

    在这里插入图片描述

    任何一棵和树对应的二叉树,其右子树必定为空

    二叉树性质

    如果对一棵有n个节点的完全二叉树(其深度为 [ l o g 2 n ] + 1 [log_2n]+1 [log2n]+1 )的节点按层序编号(从第 1 层到第$[log_2n]+1 $)层,每层从左到右),对任一节点 i ( 1 ≤ i ≤ n ) i \left( 1\leq i \leq n\right) i(1in) 有:

    1. 如果 i = 1, 则节点 i 是二叉树的根, 无双亲;如果 i > 1,则其双亲是节点 [i/2]
    2. 如果 2i > n,则节点 i 无左孩子(节点 i 为 叶子节点);否则其左孩子是节点2i
    3. 如果2i + 1 > n, 则节点 i 无右孩子;否则其右孩子是节点 2i + 1

    完全二叉树的最后一个结点的编号是1001,则它的父结点的编号为1001/2=500,则叶子结点个数为1001-500=501.

    总结一下:完全二叉树的最后一个结点的编号是n,则它的父结点的编号为[n/2],则叶子结点个数为n-[n/2]。

    无向图

    一个有n个顶点的无向图最多有 n ( n − 1 ) / 2 n(n-1)/2 n(n1)/2 条边

    关键路径

    在一个表示工程队的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网,我们成之为AOE网(Activity On Edge Network)

    用一个有向图表示一个工程的各子工程及其相互关系,其中以顶点表示活动,狐表示活动之间的优先制约关系,称这种有向图为顶点表示活动的网,简称AOV网(Activity On Vertex network)。

    我们把路径上各个活动所持续的时间之和称为路径长度,从原点到汇点具有最大长度的路径叫关键路径,在关键路径上的活动称为关键活动

    拓扑排序

    设有向图有 n 个顶点 e 条边,进行拓扑排序时总的时间复杂度为 O ( n + e ) O(n + e) O(n+e)

    查找

    二分查找

    二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

    根据顺序表二分法查找比较次数的计算公式:
    a < l o g 2 n < b ( a , b , n ∈ Z + ) a<log_2n<b (a,b,n \in Z^+) a<log2n<b(a,b,nZ+)
    当顺序表有n个关键字时:

    查找失败时,至少比较a次关键字;查找成功时,最多比较关键字次数是b。

    如果顺序表记录数 n=97 ,log₂64<log₂97<log₂128,即6<log₂97<7,最大比较次数为7次。

    分块查找

    分块查找的平均查找长度不仅取决于数据集的总记录个数 n,还和每一块的记录个数 t 相关。

    二叉排序树

    二叉排序树(Binary Sort Tree),又称二叉查找树。它或者是一颗空树,或者是具有以下性质的二叉树。

    • 若它的左子树不空,则左子树上所有的节点的值均小于它的根结点的值;
    • 若它的右子树不空,则右子树上所有的节点的值均大于它的根结点的值;
    • ⑶ 左、右子树本身又各是一棵二叉排序树。 按中序遍历二叉排序树,所得到的中序遍历序列是一个递增有序序列

    平衡二叉树(AVL树)

    平衡二叉树(Height-Balanced Binary Search Tree),是一种二叉排序树,其中的每一个节点的左子树和右子树的高度差至多等于1。

    我们将二叉树上节点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor)

    散列表查找

    对于散列表长为m的散列函数,构造方法有:

    1. 除留余数法

    Hash(key) = key mod p (p<=m)

    p一般取小于m的最大质数(素数)

    1. 直接定址法

    H a s h ( k e y ) = a × k e y + b ( a , b 为 常 数 ) Hash(key) = a\times key + b \quad \left( a, b 为常数 \right) Hash(key)=a×key+b(a,b)

    1. 数字分析法
    2. 平方取中法
    3. 折叠法
    4. 随机数法

    Hash表的平均查找长度与处理冲突的方法和散列表的装填因子有关

    • 装填因子 = 填入表中的记录个数 / 散列表长度。

    查找成功=查找次数/数据个数。

    查找失败=查找次数/散列后的地址个数。

    排序

    七种排序算法的各种指标比较

    排序方法平均情况最好情况最坏情况辅助空间稳定性
    冒泡排序 O ( n 2 ) O(n^{2}) O(n2) O ( n ) O(n) O(n) O ( n 2 ) O(n^{2}) O(n2)O(1)稳定
    简单选择排序 O ( n 2 ) O(n^{2}) O(n2) O ( n 2 ) O(n^{2}) O(n2) O ( n 2 ) O(n^{2}) O(n2)O(1)稳定
    直接插入排序 O ( n 2 ) O(n^{2}) O(n2) O ( n ) O(n) O(n) O ( n 2 ) O(n^{2}) O(n2)O(1)稳定
    希尔排序O(n logn)~O(n^2)O(n^1.3) O ( n 2 ) O(n^{2}) O(n2)O(1)不稳定
    堆排序O(n logn)O(n logn)O(n logn)O(1)不稳定
    归并排序O(n logn)O(n logn)O(n logn)O(n)稳定
    快速排序O(n logn)O(n logn) O ( n 2 ) O(n^{2}) O(n2)O(logn)~O(n)不稳定

    在这里插入图片描述

    展开全文
  • 数据结构复习笔记 由HDU-STEA_banjiu修改于2021年1月9日 参考书目:严蔚敏《数据结构(第二版)》、王导论坛《数据结构考研复习指导》、HDU-STEA_YY《<数据结构>复习笔记》 第一章 概 论 1.数据的概念...

    《数据结构》复习笔记

    HDU-STEA_banjiu修改于2021年1月9日

    参考书目:严蔚敏《数据结构(第二版)》、王导论坛《数据结构考研复习指导》、HDU-STEA_YY《<数据结构>复习笔记》

    第一章 概 论

    1.数据的概念(data)

    信息的载体,能被计算机识别、存储和加工处理。

    是客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

    2.数据元素(data element)

    数据的基本单位,在计算机程序里通常作为一个整体进行考虑和处理。

    可由若干个数据项(data item)组成,数据项是构成数据元素不可分割的最小标识单位。

    3.数据对象(data object)

    性质相同的数据元素的集合,是数据的一个子集。

    4.数据类型(data type)

    数据类型是一个值的集合和定义在此集合上的一组操作的总称。

    • 原子类型:其值不可再分的数据类型。
    • 结构类型:其值可以再分解为若干成分(分量)的数据类型。
    • 抽象数据类型:抽象数据组织及与之相关的操作。

    5.数据结构(data structure)

    是相互之间存在一种或多种特定关系的数据元素的集合。

    • 数据的逻辑结构

      数据元素之间的逻辑关系,即从逻辑关系上描述数据。与数据的存储无关,是独立于计算机的。

      • 线性结构:若结构是非空集则仅有一个开始和终端结点,并且所有结点最多只有一个直接前趋和后继。即,结构中的数据元素存在一个对一个的关系。(栈、队列、串/数组、广义表)
      • 非线性结构:一个结点可能有多个直接前趋和后继。
        • 集合:结构中的数据元素之间除了“同属于一个集合“的关系外,别无其他关系。
        • 树形结构:结构中的元素存在一个对多个的关系。(一般树、二叉树)
        • 图状结构或网状结构:结构中的元素存在多个对多个的关系。(有向图、无向图)
    • 数据的存储结构

      数据结构在计算中的表示(又称映像),也称物理结构。包括数据元素的表示和关系的表示。数据的存储结构是用计算机语言实现的逻辑结构,它依赖于计算机语言。

      • 顺序存储,把逻辑相邻的结点存储在物理上相邻的存储单元内。(循环队列、顺序表)
      • 链接存储,结点间的逻辑关系由附加指针字段表示。(单/双链表)
      • 索引存储,存储结点信息的同时,建立附加索引表,有稠密索引和稀疏索引。
      • 散列存储,按结点的关键字直接计算出存储地址。(哈希表)
    • 数据的运算

      • 运算的定义:针对逻辑结构,指出运算的功能
      • 运算的实现:运算的具体操作步骤

    6.算法效率的度量

    • 时间复杂度T(n)

      一个语句的频度指的是该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n),它是该算法问题规模n的函数,时间复杂度主要分析T(n)的数量级。

      该算法的时间耗费,是求解问题规模n的函数。记为O(n)。
      时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、……k次方阶O(nk)、指数阶O(2n)。

    • 空间复杂度S(n)

      该算法所耗费的存储空间,是问题规模n的函数。

    展开全文
  • 数据结构期末复习

    2020-12-12 18:04:53
    数据结构(一)基本概念1.数据结构2.逻辑结构3.存储结构4.算法5.时间复杂度与空间复杂度(二)线性表1.线性表的顺序表示和实现2.线性表的链式表示和实现(单链表、循环链表、循环链表)3.线性表的应用(多项式运算、...

    (一)基本概念

    1.数据结构

    在这里插入图片描述
    在这里插入图片描述

    2.逻辑结构

    在这里插入图片描述

    3.存储结构

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    4.算法

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    5.时间复杂度与空间复杂度

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    (二)线性表

    1.线性表的顺序表示和实现

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    2.线性表的链式表示和实现(单链表、双链表、循环链表)

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    3.线性表的应用(多项式运算、链表合并)

    多项式运算

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    链表合并

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    (三)栈和队列

    1.栈和队列的定义及其相关概念

    2.进栈和出栈算法

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    3.循环队列中入队列与出队列算法

    在这里插入图片描述

    (四)串、数组和广义表

    1.串匹配算法

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    2.数组地址、特殊矩阵存储方法

    3.广义表取表头和表尾操作

    在这里插入图片描述
    在这里插入图片描述

    (五)树和二叉树

    1.树和二叉树的基本概念

    2.二叉树的性质

    3.二叉树的存储复试

    4.二叉树的遍历

    5.哈夫曼树和哈夫曼编码

    (六)图

    1.图的基本概念

    2.图的三种存储结构:数组表示法,邻接表和十字链表

    3.图的遍历

    4.图的应用,包括最小生成树,拓扑排序,关键路径,最短路径

    (七)查找

    1.静态查找表和动态查找表的特点

    2.折半查找

    3.索引顺序表的查找

    4.二叉排序树

    5.平衡二叉树的

    6.哈希表的定义,构造方法、处理冲突方法、查找及性能分析

    (八)排序

    1.直接插入排序

    2.希尔排序

    3.冒泡排序

    4.快速排序

    5.堆排序

    6.归并排序

    7.基数排序

    展开全文
  • 数据结构复习笔记 由HDU-STEA_banjiu修改于2021年1月9日 参考书目:严蔚敏《数据结构(第二版)》、王导论坛《数据结构考研复习指导》、HDU-STEA_YY《<数据结构>复习笔记》 第二章 线性表 1.线性表的...

    《数据结构》复习笔记

    HDU-STEA_banjiu修改于2021年1月9日

    参考书目:严蔚敏《数据结构(第二版)》、王导论坛《数据结构考研复习指导》、HDU-STEA_YY《<数据结构>复习笔记》

    第二章 线性表

    1.线性表的定义

    相同数据类型 n ( n ≥ 0 ) n(n\ge0) n(n0)个数据元素的有限序列,其中 n n n为表长,当 n = 0 n=0 n=0时,线性表是一个空表。

    若用 L L L命名线性表,则一般表示为:
    L = ( a 1 , a 2 , . . . , a i , a i + 1 , . . . , a n ) L=(a_1,a_2,...,a_i,a_{i+1},...,a_n) L=(a1,a2,...,ai,ai+1,...,an)
    线性表的逻辑特性如下:

    • a 1 a_1 a1是唯一的”第一个元素“,称为表头元素
    • a n a_n an是唯一的”最后一个元素“,称为表尾元素
    • 除表头元素外,每个元素有且仅有一个直接前驱。
    • 除表尾元素外,每个元素有且仅有一个直接后驱。

    线性表的特点如下:

    • 元素的个数有限
    • 元素具有逻辑上的顺序性,表中元素有先后次序
    • 元素都是数据元素,每个元素都是单个元素
    • 元素的数据类型都相同,占有相同大小的存储空间

    线性表是一种逻辑结构,顺序表和链表是指存储结构。

    2.线性表的基本操作

    1. InitList(&L)
      

      构造空表,即表的初始化;

    2. DestroyList(&L)
      

      销毁线性表;

    3. ListLength(L)
      

      求表的结点个数,即表长;

    4. GetNode(L,i,&e)
      

      按位查找,取表中第i个结点,要求1≤i≤ListLength(L);

    5. LocateNode(L,x)
      

      按值查找,查找L中值为x的结点并返回结点在L中的位置,有多个x则返回首个,没有则返回特殊值表示查找失败。

    6. InsertList(&L,i,x)
      

      插入操作,在表的第i个位置插入值为x的新结点,要求 1 ≤ i ≤ L i s t L e n g t h ( L ) + 1 1≤i≤ListLength(L)+1 1iListLength(L)+1

    7. DeleteList(L,i)
      

      删除操作,删除表的第i个位置的结点,要求 1 ≤ i ≤ L i s t L e n g t h ( L ) 1≤i≤ListLength(L) 1iListLength(L)

    3.顺序表的定义

    线性表的顺序存储,用一组地址连续的存储单元依次存储线性表中的数据元素,使得逻辑上相邻的两个元素在物理位置上也相邻。

    第1个元素存储在线性表的起始位置,第 i i i个元素的存储位置后面紧接着存储的是第 i + 1 i+1 i+1个元素, i i i为元素 a i a_i ai在线性表中的位序

    4.顺序表结点的存储地址计算公式

    假设线性表 L L L存储的起始位置为 L O C ( A ) LOC(A) LOC(A),每个元素的占用空间为 s i z e o f ( E l e m T y p e ) sizeof(ElemType) sizeof(ElemType)

    则线性表中第 i + 1 i+1 i+1个数据元素的存储位置 L O C ( a i + 1 ) LOC(a_{i+1}) LOC(ai+1)和第 i i i个数据元素的存储位置 L O C ( a i ) LOC(a_{i}) LOC(ai)之间满足下列关系:
    L O C ( a i + 1 ) = L O C ( a i ) + s i z e o f ( E l e m T y p e ) LOC(a_{i+1})=LOC(a_{i})+sizeof(ElemType) LOC(ai+1)=LOC(ai)+sizeof(ElemType)
    一般来说,线性表的第 i i i个数据元素 a i a_{i} ai的存储位置为
    L O C ( a i ) = L O C ( A ) + ( i − 1 ) × s i z e o f ( E l e m T y p e ) LOC(a_{i})=LOC(A)+(i-1)\times sizeof(ElemType) LOC(ai)=LOC(A)+(i1)×sizeof(ElemType)

    线性表中元素的位序是从1开始的,而数组元素的下标是从0开始的

    5.线性表的顺序存储类型

    (1)静态分配

    #define Maxsize 50 		//定义线性表的最大长度
    typedef struct{		
        int data[Maxsize];	//顺序表的元素
        int length;			//顺序表的当前长度
    }SqList;				//顺序表的类型定义
    

    (2)动态分配

    #define InitSize 100 	//定义线性表的最大长度
    typedef struct{		
        int *data;			//指示动态分配数组的指针
        int MaxSize,length;	//数组的最大容量和当前个数
    }SeqList;				//动态分配数组顺序表的类型定义
    

    C的初始动态分配语句为

    L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
    

    动态分配并不是链式存储,同样属于顺序存储结构,只是分配的空间大小可以在运行时决定

    6.顺序表上的基本操作

    (1)插入

    void insertlist(SeqList *L, ElemType x, int i)
    {
        if (i < 1 || i > L->length + 1)
            error("position error"); 	//位置i不合法
        if (L->length >= listsize)
            error("overflow"); 			//存储空间已满
        for (int j = L->length - 1; j >= i - 1; j--)
            L->data[j + 1] = L->data[j]; //结点后移
        L->data[i - 1] = x;              //插入节点x
        L->length++;                     //表长度加一
    }
    

    在顺序表上插入要移动表的 n / 2 n/2 n/2结点,算法的平均时间复杂度为 O ( n ) O(n) O(n)

    (2)删除

    void delete (SeqList *L, int i)
    {
        int j;
        if (i < 1 || i > L->length)
            error("position error"); //位置i不合法
        for (j = i; j <= L->length - 1; j++)
            L->data[j - 1] = L->data[j]; //结点前移
        L->length--;                     //表长度减一
    }
    

    在顺序表上删除要移动表的 ( n + 1 ) / 2 (n+1)/2 (n+1)/2结点,算法的平均时间复杂度为 O ( n ) O(n) O(n)

    (3)按值查找(顺序查找)

    int LocateNode(SqList L,ElemTye x){
    	int i;
    	for(i = 0; i < L.length; i++)
            if(L.data[i] == x)
                return i+1;			//下表为i的元素等于x,返回其位序i+1
        return 0;					//退出循环,说明查找失败
    }
    

    在顺序表上查找的次数为 ( n + 1 ) / 2 (n+1)/2 (n+1)/2次,算法的平均时间复杂度为 O ( n ) O(n) O(n)

    (4) 合并

    void merge(SeqList La, SeqList Lb, SeqList &Lc)
    {
        //已知顺序线性表La和Lb的元素按值非递减排列
        //归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列
        ElemType *pa, *pb, *pc, *pa_last, *pb_last;
        pa = La.elem;
        pb = Lb.elem;                      // 指针pa,pb的初始值分别指向两个表的第一个元素
        Lc.length = La.length + Lb.length; // 新表长度为待合并两表的长度之和
        Lc.elem = new ElemType[Lc.length]; // 为合并后新表分配一个数组空间
        pc = Lc.elem;                      // 指针pc指向新表的第一个元素
        pa_last = La.elem + La.length - 1; // 指针pa_last指向La表的最后一个元素
        pb_last = Lb.elem + Lb.length - 1; // 指针pb_last指向Lb表的最后一个元素
    
        while (pa <= pa_last && pb <= pb_last)
        { // 两个表都非空
            if (*pa <= *pb)
                *pc++ = *pa++; // 一次摘取两表中值最小的节点
            else
                *pc++ = *pb++;
        }
        while (pa <= pa_last)
            *pc++ = *pa++; // Lb表已经达到表尾,将La中剩余元素加入Lc
        while (pb <= pb_last)
            *pc++ = *pb++; // La表已经达到表尾,将Lb中剩余元素加入Lc
    }
    

    算法的时间复杂度为 O ( L a . l e n g t h + L b . l e n g t h ) O(La.length+Lb.length) O(La.length+Lb.length)

    7.单链表的定义

    线性表的链式存储,通过一组任意的存储单元(可连续,可不连续)来存储线性表中的数据元素。为了建立数据元素之间的线性关系,对每个链表结点,除存放元素自身的信息外,还需要存放一个指向其后继的指针。

    (1)单链表的结点结构

    单链表的结点结构如下:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IzSgVOhd-1610297169031)(C:\Users\HP\AppData\Roaming\Typora\typora-user-images\image-20210110163847722.png)]

    其中data为数据域,存放数据元素;next为指针域,存放其后继结点的位置。

    指针域中存储的信息称作指针。n个节点的链结成一个链表,即为线性表的链式存储结构。

    以下为单链表中结点类型的描述:

    typedef struct LNode	//定义单链表结点类型
    {
        ElemTyoe data;		//数据域
        struct LNode *next;	//指针域
    }LNode,*LinkList;
    

    有一个指针域的链表称单链表。
    在C语言中,单链表可由头指针唯一确定,可用“结构指针”来描述。此外,为了操作上的方便,在单链表第一个结点前附加一个结点,称为头结点

    (2)头结点和头指针的区分:

    • 不管带不带头结点,头指针始终指向链表的第一个结点
    • 头结点是带头结点的链表的第一个结点,结点内通常不存储信息。

    (3)引入头结点的优点

    • 链表第一个位置的操作无需特殊处理;
    • 将空表和非空表的处理统一。

    8.单链表上的基础操作的实现

    (1)建立单链表

    头插法

    前插法通过将新结点逐个插入链表的头部(头结点之后)来创建链表,每次申请一个新结点,读入相应的数据元素值,然后将新结点插入到头结点之后 。

    1. 创建一个只有头结点的空链表。
    2. 根据创建链表结点元素个数 n ,循环n次执行以下操作:
      1. 生成一个新结点 *p ;
      2. 将输入元素赋新结点 *p 的数据域中;
      3. 将新结点 *p 插入到头结点之后。
    //采用头插法建立单链表
    /*
    	建立链表 - 头插法 - 有头节点
    
    	+------+	     +------+	 +------+	 +------+
    	|   L  |   =>    |node_1| -> |node_2| -> |node_3| -> NULL
    	+------+	     +------+	 +------+	 +------+
    		  \			  /
    			 +------+
    			 |   s  |
    			 +------+
    
    */
    LinkList List_headInsert(LinkList &L){
    	LNode* s; 							//临时节点,用于保存声明的节点
    	L = (LinkList)malloc(sizeof(LNode));//生成链表头节点
    	L->next = NULL;
    	L->data = 0;						//头节点的data保存链表长度
    	int x;								//暂时存储输入元素,用作赋值
    	scanf("%d", &x);
    	while (x!= -1) {
    		s = (LNode*)malloc(sizeof(LNode));
    		s->data = x;
    		s->next = L->next;
    		L->next = s;					//将新节点插入表中,L为头指针
    		L->data++;
            
    		scanf("%d", &x);
    	}
    	return L;
    }
    
    尾插法

    头插法虽然简单,但生成的链表中结点的次序和输入数据的顺序不一致。尾插法则可保证两者的次序一致。

    1.增加一个尾指针r,使其始终指向当前链表的尾结点。

    2.将新结点插入当前链表的表尾。

    //采用尾插法建立单链表
    /*
    	创建链表 - 尾插法 - 有头节点
    
    	+------+	+------+	+------+
    	|   L  | -> |node_1| -> |node_2|   ____
    	+------+	+------+	+------+	  |
    										  v
    						+------+ 	  +------+
    						|  r   |  ->  |   s  |
    						+------+	  +------+
    
    */
    LinkList List_TailInsert(LinkList &L) {
    	L = (LinkList)malloc(sizeof(LNode));
    	LNode* s,*r=L;					//用r来保存尾部位置
    	
    	L->next = NULL;
    	L->data = 0;
    	int x;							//暂时存储结点的值
    	scanf("%d", &x);
    	while (x != -1) {
    		s = (LNode*)malloc(sizeof(LNode));
    		s->data = x;				
    		r->next = s;				//r指向新的表尾结点
    		r = s;
    		scanf("%d", &x);
    	}
    	r->next = NULL;					//尾结点指针置空
    	return L;
    }
    

    (2)查找运算

    时间复杂度为O(n)。

    1) 按序号查找
    LNode* GetELem(LinkList L, int i) {
    	int j = 1;				//计数,初始为1
    	LNode* p = L->next;
    	if (i == 0)
    		return 0;			//若i=0,则返回头节点
    	if (i < 1)
    		return NULL;		//若i无效,则返回NULL
    	while (p && j < i) {	//从第一个节点开始找,查找第i个节点
    		p=p->next;
    		j++;
    	}
    	return p;				//返回第i个节点的指针,若i大于表长,则返回NULL
    }
    
    2) 按值查找
    LNode* LocateElem(LinkList L, int e) {
    	LNode* p = L->next;
    	while (p!=NULL&&p->data!=e)	//从第一个节点开始查找data域为e的节点
    	{
    		p = p->next;
    	}
    	return p;					//找到后返回该节点指针,否则返回NULL
    }
    
    (3)插入运算

    时间复杂度为O(n)。

    void Insertlist(linklist L, datatype x, int i)
    {
        listnode *p;
        int j;
        p = L;
        j = 0;
        while (p && j < i - 1) //寻找第i-1个节点
        {
            p = p->next;
            ++j;
        }
    
        if (!p || j > i - 1)
            error("position error");              //i小于1或者大于表长加1
        s = (listnode *)malloc(sizeof(listnode)); //生成新节点
        s->data = x;                              //数据域赋值
        s->next = p->next;                        //新结点*s的指针域指向*p的后继结点
        p->next = s;							  //*p指针域指向新插入结点*s
    }
    
    (4) 删除运算

    时间复杂度为O(n)。

    Void DeleteList(linklist head, int i)
    {
        //删除第i个节点
        listnode *p, *r;
        p = GetNode(head, i - 1); //寻找第i-1个节点
        if (p == NULL || p->next == NULL)
            error(“position error ”);
        r = p->next;
        p->next = r->next; //将第i-1个节点的指针域指向第i+1个节点
        free(r); //释放空间
    }
    

    9.双链表

    在结点中增加一个指针域,形成的链表中有两条不同方向的链称为双链表。

    双链表结点中有两个指针prior和next,分别指向其前驱节点和后继结点。

    typedef struct DNode			//定义双链表结点类型
    {
        ElemType data;				//数据域
        struct DLNode *prior;		//前驱指针
        struct DLNode *next;		//后继指针
    } DLNode, *DLinkList;
    

    1) 双链表的前插操作

    时间复杂度为 O ( 1 ) O(1) O(1)

    Void dinsertbefore(dlistnode *p, datatype x)
    {
        dlistnode *s = malloc(sizeof(dlistnode));
        s->data = x;
        s->prior = p->prior;
        s->next = p;
        p->prior->next = s;
        p->prior = s;
    }
    

    2) 双链表的删除操作

    时间复杂度为O(1)。

    Void ddeletenode(dlistnode *p)
    {
        p->prior->next = p->next;
        p->next->prior = p->prior;
        free(p);
    }
    

    10.循环链表

    循环链表是一种首尾相连的链表。它的特点是表中最后一个节点的指针域指向头结点,整个链表形成一个环。

    在执行增加节点操作时,无需增加存储量,仅对表的链接方式修改使表的处理灵活方便。

    循环链表的操作和线性链表基本一致,差别仅在于算法中的循环条件不是p或p->next是否为空,而是它们是否等于头指针。

    (1)空循环链表

    仅由一个自成循环的头结点表示。

    (2)循环单链表的表示

    很多时候表的操作是在表的首尾位置上进行,此时头指针表示的单循环链表就显的不够方便,改用尾指针 r e a r rear rear来表示循环单链表。用头指针表示的循环单链表查找开始结点的时间是 O ( 1 ) O(1) O(1),查找尾结点的时间是 O ( n ) O(n) O(n);用尾指针表示的循环单链表查找开始结点和尾结点的时间都是 O ( 1 ) O(1) O(1)

    (3)循环双链表

    与循环单链表不同的是,在循环双链表中,头结点的prior指针还要指向表尾结点。

    在循环双链表 L L L中,某结点*p为尾结点时,p->next==L;当循环双链表为空表时,其头结点的prior域和next域都等于 L L L

    11.静态链表

    与前面所讲的指针不同的是,这里的指针是结点的相对地址(数组下标),又称游标。和顺序表一样,静态链表也要预先分配一块连续的内存空间。

    静态链表结构类型的描述如下:

    #define Maxsize 50			//静态链表的最大长度
    typedef struct{				//静态链表的结构定义
        ElemType data;			//存储数据元素
        int next;				//下一个元素的数组下标
    }SLinkList[MaxSize];
    

    静态链表以next==-1作为其结束的标志。

    12.顺序表和链表的比较

    1. 基于空间的考虑:顺序表的存储空间是静态分配的,链表的存储空间是动态分配的。顺序表的存储密度比链表大。因此,在线性表长度变化不大,易于事先确定时,宜采用顺序表作为存储结构。
    2. 基于时间的考虑:顺序表是随机存取结构,若线性表的操作主要是查找,很少有插入、删除操作时,宜用顺序表结构。对频繁进行插入、删除操作的线性表宜采用链表。若操作主要发生在表的首尾时采用尾指针表示的单循环链表。

    13.存储密度公式

    ( 结 点 数 据 本 身 所 占 的 存 储 量 ) / ( 整 个 结 点 结 构 所 占 的 存 储 总 量 ) (结点数据本身所占的存储量)/(整个结点结构所占的存储总量) ()/()

    存储密度:顺序表=1,链表<1。

    展开全文
  • 2019年准备哈工大计算机初始时自己整理的 主要内容为哈工大PPT内容
  • 数据结构复习笔记 由HDU-STEA_banjiu修改于2021年1月9日 参考书目:严蔚敏《数据结构(第二版)》、王导论坛《数据结构考研复习指导》、HDU-STEA_YY《<数据结构>复习笔记》 第三章 栈和队列 1.栈的定义...
  • 哈工大2018年秋数据结构期末复习

    千次阅读 2020-06-02 21:39:29
    就是一篇很普通的数据结构复习时的笔记而已 本文原载于我的博客,地址:https://blog.guoziyang.top/archives/19/
  • 1. 计算机体系结构的基本概念 ...系统结构的重大转折:从单纯依靠指令级并行转向开发线程级并行和数据级并行 1.2 计算机系统结构的概念 1.2.1 计算机系统的层次结构 从计算机语言的角度出发,把计算机系统按功能
  • 有一说一,如果按题目所给的数据范围,n 是完全不能跑Floyd的,且因为他的边并没有很多,所以标程应该是每个点跑一遍堆优化的dij。 但是呢问题来了qwq,我比较懒,所以就写了一个Floyd扔上去准备看着大大的tle令我...
  • 目录 关于链表的例题: 邻接表例题 AOV和AOE图的讲解 ...前言:前几天我还做了两套卷子,但是我们老师出的卷子只有大题,还是分享一下把,做了这两套卷子我觉得要去复习的一些知识点。以及还有一些例题...
  • 算法期末复习笔记

    千次阅读 多人点赞 2018-12-30 17:08:45
    技术类电子书大放送:电子书 友链:操作系统复习 第一章算法引论 1.算法时间复杂度 第二章 递归与分治策略 一.算法设计思想 分治法的设计思想是,将一个难以直接解决的大问题,分隔成一些规模较小的相同问题,以便...
  • 这是个对你数据结构期末复习起到一定作用的复习资料
  • 数据库期末复习笔记

    千次阅读 2017-06-24 21:14:45
    数据库期末复习笔记1. 四个基本概念a. 数据数据是描述事物的符号记录,是数据库中存储的基本对象。 b. 数据库数据库(DB)是长期储存在计算内、有组织的、可共享的大量数据的集合。 c. 数据库管理系统数据库管理系统...
  • 移动通信期末复习笔记

    万次阅读 多人点赞 2020-06-29 18:26:13
    移动通信复习笔记 1.1移动通信的主要特点 一.必须使用无线电波进行传播 无线电波传播特性:信号衰落 原因: 能量扩散------>弥漫损耗 地形地物的影响------>阴影效应 直射反射绕射---->多径传播---&...
  • 数据结构复习笔记

    2021-01-26 14:04:47
    描述数据元素之间的关系就是数据结构。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CN3IhJcd-1611122439191)(https://uploader.shimo.im/f/mlNje3cI7rO3dTCb.png!thumbnail?fileGuid...
  • 期末复习的时候对课本进行了系统的整理,现在发上来希望能对大家有用www 正文 第1章 引言 数据库系统由一个互相关联的数据的集合和一组用以访问这些数据的程序组成。这个数据的集合通常称作数据库。 DBMS的主要特性 ...
  • 根据浙大mooc内容和自己的理解,挑了重点内容做的整理。适合考前浏览复习。用onenote打开
  • 操作系统理论笔记(二)期末复习笔记

    万次阅读 多人点赞 2018-07-09 21:48:11
    前言,以下期末复习建议建立在第四版的 2017年10月第54次印刷下的第一章 操作系统引论 P31课后习题 10、11 思考题:23、2510.试从交互性、及时性以及可靠性方面,将分时系统与实时系统进行比较。答:(1)及时性:...
  • python期末复习笔记

    2021-01-01 16:43:33
    笔记视频来源——链接: link 由本人整理了一部分,记得比较仓促,若有错误,欢迎纠正,不说了,备考期末去啦。(•́︿•̀) 在python中,不需要先在前面定义数据的类型,在下面直接就可以使用 先定义后调用 ...
  • 数据结构绪论 一、数据结构起源 早期人们把计算机作为数值计算工具,就是说,人们认为计算机只能进行数据计算。因此为了解决问题,需要先从具体问题中抽象出一个适当的数据模型,设计出一个解决该模型的算法,然后再...
  • 由于在平板备忘录上写的,因此转成pdf较为方便,部分截图来源于蜂考课件,侵删
  • 一.栈的基本概念 (1)栈是限定仅在表尾进行插入和删除操作的线性表。所谓的表尾是指栈顶,而不是栈底。 (2)栈是后进先出的线性表。...(3)把允许插入和删除的一端称为栈顶,另一端...1.栈的顺序结构定义 说...
  • Linux期末复习笔记

    2021-05-28 13:58:35
    ④允许灵活地使用数据流,提供通配符、输入/输出重定向、管道线等机制,方便模式匹配、IO处理和数据传输。 ⑤结构化的程序模块,提供顺序、条件、循环等控制沉程。 ⑥提供在后台(&)执行命令的能力。 ⑦提供可配置...
  • 数据库系统原理 第1讲 数据:描述事物的符号记录,是数据库中存储的基本对象。 DB:数据库是长期储存在计算机内、有组织...数据控制功能:数据的安全性保护:保护数据,以防止不合法的使用造成的数据的泄密和破坏。数据
  • 图是由顶点(vertex)集合及顶点间的关系组成的一种数据结构。Graph=(V,E)Graph=(V,E)其中,顶点集合 V={x|x∈某个对象数据集}V={x|x∈某个对象数据集} 是有穷非空集合;E={(x,y)|x,y∈V}E={(x,y)|x,y∈V} 是顶点间...
  • JavaEE期末复习笔记

    千次阅读 多人点赞 2018-07-05 17:23:20
    非UI标签:数据访问,逻辑控制 流程控制标签 数据访问标签 UI标签:生成HTML元素 表单标签 非表单标签 Ajax标签:支持Ajax 值栈中存在的对象:模型对象,action对象,request对象 OGNL的跟对象为值栈 值栈对应...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,122
精华内容 448
关键字:

数据结构期末复习笔记

数据结构 订阅