• 复习三：线性表

    一、线性表定义

          线性表是具有 相同 数据类型的n （n   > 0 ） 个 数据元素 的 有限序列 ,其中 n 为表长 ， 当 n = 0
    时线性表是一个空表 。 线性表是一种逻辑结构，顺序表与链表是存储结构
             线性表特点：
    1. 表中元素的个数有限
    2. 表中元素具有逻辑上的顺序性，表中元素有其先后次序。
    3. 表中元素都是数据元素，每个元素都是单个元素。
    4. 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
    5. 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

    二、顺序表

            线性表的顺序存储又称顺序表。顺序表的特点是表中元素的逻辑顺序与其物理顺序相同；

            顺序表最主要的特点是 随机访问 ， 即通过首地址和元素序号可在时间 0(1) 内找到指定的
    元素 。顺序表的存储密度高， 每个结点只存储数据元素 。 顺序表逻辑上相邻的元素物理上也相邻， 所以 插入和删除操作需要移动大量元素 。
    静态顺序表定义【用数组表示】

     动态顺序表定义【利用指针、malloc()函数】 初始动态分配语句

    动态分配并不是链式存储、它同样属于顺序存储结构，物理结构没有变化，依然是随
    机存取方式，只是分配的空间大小可以在运行时动态决定。

    三、顺序表基本操作

    (1) 插入操作
    在顺序表L的第 i (l<=i<=L. length+1) 个位置插入新元素 e 。 若 i 的输入不合法 ， 则返回false, 表示插入失败 ； 否则 ， 将第 i 个元素及其后的所有元素依次往后移动一个位置 ， 腾岀一个空位置插入新元素e, 顺序表长度增加1 , 插入成功 ， 返回 true 。
    最好情况∶在表尾插入（即 i=n+1），元素后移语句将不执行，时间复杂度为 O（1）。
    最坏情况∶在表头插入（即i=1），元素后移语句将执行n次，时间复杂度为O（n）。
    平均情况∶时间复杂度为 0(n ) 。
    (2) 删除操作
    删除顺序表L中第 i (l<=i<=L. length) 个位置的元素 ， 用引用变量 e 返回 。 若 i的输入不合法，则返回false；否则，将被删元素赋给引用变量e,并将第i+ l个元素及其后的所有
    元素依次往前移动一个位置 ，线性表长度减一，返回true
    最好情况 ： 删除表尾元素(即 i =n) ,无须移动元素，时间复杂度为0(1)。
    最坏情况 ： 删除表头元素(即i=l),需移动除表头元素外的所有元素，时间复杂度为0(n) 。
    平均情况：时间复杂度为O(n)

    (3)按值查找(顺序查找)
    在顺序表L中查找第一个元素值等于 e 的元素 ， 并返回其位序 。
    四、顺序表的链式表示
    1、单链表：线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。单链表结点结构如图2.3所示，其中data为数据域，存放数据元素；next为指针域，存放其后继结点的地址。
    单链表中结点类型：

     

    头结点和头指针的区分 ： 不管带不带头结点 ， 头指针都始终指向链表的第一个结点 ， 而头结
    点是带头结点的链表中的第一个结点 ， 结点内通常不存储信息
    2、单链表的创建
    （1）头插法建立单链表：将新结点插入到当前链表的表头 ， 即头结点之后

    采用头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的。每个结
    点插入的时间为O1），设单链表长为n，则总时间复杂度为 O（n）
    （2）尾插法建立单链表：将新结点插入到当前链表的表尾，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点

     

    3、双链表
    双链表结点中有两个指针prior和next,分 别指向其前驱结点和后继结点，如图2.9所示

    （1）双链表的插入
    4、循环单链表
    循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点， 从而整个链表形成一个环，如图2.12所示。 在循环单链表中，表尾结点*r的 next 域指向L，故表中没有指针域为 NULL的结点，因此， 循环单链表的判空条件不是头结点的指针是否为空，而是它 是否等于头指针

    5、循环双链表

    由循环单链表的定义不难推出循环双链表。不同的是在循环双链表中，头结点的prior指 针还要指向表尾结点，如图2.13所示

    在循环双链表L中，某结点*p为尾结点时，p->next==L;当循环双链表为空表时，其 头结点的 prior域和 next域都等于L
    6、静态链表
    静态链表借助数组来描述线性表的链式存储结构，结点也有数据域 data 和指针域 next，静态链表也要预先分配一块连续的内存空间

     

                                                             习题                

    参考答案：C

     参考答案：A

     参考答案D

     

    参考答案D

     

     

     

     

    参考答案D

     

     参考答案c

      

     参考答案C

  • 相关阅读:
    5.2 创建个人中心页面-前端部分
    JS 实现自定义弹窗
    广东省工业和信息化厅关于组织开展2022年创新型中小企业评价、专精特新中小企业认定和复核工作的通知
    Docker 容器连接：构建安全高效的容器化网络生态
    halcon如何识别硬币？
    torch.mv
    MySQL安全问题
    Linux命令--在后台运行程序--方法/实例
    入门力扣自学笔记110 C++ （题目编号1374）
    字面量运算符/字面量操作符
  • 原文地址：https://blog.csdn.net/yyy_zxc/article/details/126660918