Skip to main content

线性表

1. 基本概念

线性表是具有像线一样的性质的表,它是零个或多个数据元素的有限序列。

在物理结构中的线性结构又称线性表,线性表中的数据元素可以是各种各样的,但是同一线性表中的元素必定具有相同的特性,即属于同一个数据对象,相邻的数据元素之间存在着序偶关系。若将线性表记为(a1,a2,..an),则有以下的特性:

  • 存在唯一的一个被称为"第一个"的数据元素。
  • 存在唯一的一个被称为"最后一个"的数据元素。
  • 除了第一个外,集合中每个数据元素均只有一个前驱结点。
  • 除最后一个外,集合中每个数据元素均只有一个后驱结点。

2. 线性表的顺序存储结构

线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。数组就是一个典型的顺序存储结构。

下面是线性表的顺序存储结构代码。

#define SIZE 8

typedef struct
{
int a[SIZE];
int length;
}sqlint;

在地址连续的空间存储数据:

0x10000x10040x10080x100C0x10100x10140x10180x101C
a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]

描述顺序存储结构的需要三个属性:

  • 存储空间的起始位置:数组 a ,它的存储位置就是存储空间的存储位置。
  • 线性表的最大存储容量:数组长度SIZE。
  • 线性表的当前长度:length。

注意:数组的长度是存放线性表的存储空间的长度,存储分配后这个量是不变的,线性表的长度是线性表中数据元素的个数,随着线性表的增删步骤,这个量是变化的。

在任意时刻,线性表的长度应该小于或等于数组的长度。

3. 线性表的链式存储结构

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。这就意味着,这些数据元素可以存在内存未被占用的任意位置。

数据元素在链式结构中,除了要存数据元素信息外,还要存储它后继元素的存储地址。

3.1 指针域、数据域以及结点

  • 数据域:直接存储数据信息的域。
  • 指针域:存储后继信息位置的域(后继信息的地址)。
  • 结点:数据域和指针域组成数据元素的存储映像。

Zh3RAR.png

3.2 头结点与头指针

  • 头指针:
    • 头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针。
    • 头指针具有标识作用,常用头指针作为链表的名字。
    • 无论链表是否为空,头指针均不为空,头指针是链表的必要元素。

整个链表的存取必须是从头指针开始进行,之后的每一个结点,其实就是上一个结点的后继指针指向的位置。

最后一个结点它的指针指向的是“ 空 ”(通常用 NULL 或 **“ ^ ”**表示)。 ZhJpLh.png

  • 头结点:
    • 头结点是为了更方便对链表进行操作而设立的,放在第一元素的结点之前,其数据域一般无意义(也可以存放链表的长度)。
    • 有了头结点,对在第一要素结点前插入结点和删除第一结点与其他结点的操作就统一了。
    • 头结点不一定是链表的必须要素。

ZhJQZm.png

4. 链表的分类

  • 无头结点的单链表(LinkedList.c)

  • 有头结点的单链表(LinkedListWithHead.c)

  • 双向链表(BothwayLinkedList.c)

  • 循环链表(CircledLinkedList.c)

  • 内核链表(LinuxLinkedList.c)