编辑
2022-09-27
数据结构
00
请注意,本文编写于 607 天前,最后修改于 559 天前,其中某些信息可能已经过时。

目录

第二章 线性表
2.1 线性表的顺序表示
2.2 线性表的链式存储
一、单向链表
二、循环链表
三、双向链表

本章重点

线性表的定义,顺序表和链表的定义与特点,顺序表和链表的插入删除查找移动等基本操作

第二章 线性表

2.1 线性表的顺序表示

  1. 线性表(list):n个具有相同数据类型的数据元素的优先序列。
  2. 顺序表:用一组地址连续的存储单元依次存储线性表中的数据元素。
  3. 特点
    1. 逻辑相邻的两个元素在物理地址上也相邻;
    2. 随机存取;
    3. 存储密度高;
    4. 插入删除不方便,需要移动大量元素。
  4. 操作
    1. 插入:在表长为n的顺序表的第i个位置上插入元素,将插入位置开始的元素都向后移动一个位置,移动 n-i+1 个元素,平均时间复杂度:O(n)
    2. 删除:在表长为n的顺序表中删除第i个元素,将ai~an都向前移动一个位置,共移动n-i个元素,平均时间复杂度:O(n)
    3. 查找:
      • 按照序号查找:根据线性表随机存取的特点,时间复杂度为O(1)
      • 按值查找:比较次数与查找值在表中位置、表长有关,平均比较次数(n+1)/2,时间复杂度O(n)

2.2 线性表的链式存储

一、单向链表

  1. 单链表:通过指针连接各数据元素,不需要使用物理地址连续的存储单元,非随机存取

    js
    //线性表的单链表存储结构: typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList;
  2. 结点(node):结点构成链表,由数据域和指针域(存储后续位置)构成,结构为:

    数据域(data)指针域(next)
  3. 头指针:用来标识单链表,指向链表中第一个结点的存储位置。头指针为NULL时为空表。

  4. 头结点:为了方便操作,在单链表的第一个结点之前设置一个数据域不存储任何信息、指针域指向第一结点的指针的结点。

    • 头结点与头指针:无论带不带头结点,头指针始终指向链表的第一个结点;
    • 头结点是带头结点的链表的第一个结点,结点内通常不存储信息。
  5. 带头结点的优点

    • 由于第一个数据结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作和在表中其他位置上的操作一致,无需进行特殊处理。
    • 无论链表是否为空,其头指针都指向头结点的非空指针(空表中头结点的指针域为空),因此空表和非空表的处理也就得到了统一。
  6. 基本操作

    1. 头插法建表:从空表开始将新结点插入当前链表的头结点后。 读入数据的顺序与生成链表中元素的顺序相反。时间复杂度为O(n) 核心代码

      js
      s->next = L->next; //1⃣先用新结点S的指针指向原链表的第一个结点; L->next = s; //2⃣再将头结点的指针L指向新结点。
    2. 尾插法:将新结点插入当前表尾,使用尾指针r始终指向尾结点。 读入数据的顺序与生成链表中元素的顺序一致。时间复杂度为O(n) 核心代码

      js
      r->next = s; //1⃣原尾结点指向新的结点; r = s; //2⃣插入的结点成为新的尾结点。
    3. 查找:按值查找和按序号查找;链表非随机存取,两种查找方式都需要从头结点开始遍历查找。时间复杂度为O(n)

    4. 插入:将数据域为x的新结点S插入第i个位置。时间复杂度为O(n) 核心代码

      js
      p = GetElem(L, i-1); //1⃣找到插入的位置; s->next = p->next; //2⃣新结点s指向插入位置的下一结点; p->next = s; //3⃣结点P指向S
    5. 删除:删除链表中的第i个结点。时间复杂度为O(n) 核心代码

      js
      p = GetElem(L, i-1); q = p->next; p->next = q->next

      插入删除时注意顺序,插入时要让新结点先指向插入位置的后一个结点,删除时要先让前驱结点指向删除位置的后继结点,避免链表断开结点丢失。

二、循环链表

  • 表中最后一个结点的指针域指向头结点,整个链表形成一个环。可以从表的任意位置开始遍历整个链表。
  • 判空条件:头结点的指针等于头指针。

三、双向链表

  • 克服单链表只能顺指针往后查找其他结点的缺点,双向链表中有两个指针域:一个指向前驱,一个指向后继。
  • 双向链表也可以有循环表示。
如果对你有用的话,可以打赏哦
打赏
ali pay
wechat pay

本文作者:Handy Zhang

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!