您的位置: 首页  >  IT文章  >  数据结构之线性表

数据结构之线性表

分类: IT文章 • 2022-08-03 17:14:18

概要

参考《大话数据结构》，把常用的基本数据结构梳理一下。

 

线性表

 

定义

 
   线性表（List）：零个或多个数据元素的有限序列。

若将线性表记为 ((a_1, cdots, a_{i-1}, a_i, a_{i+1}, cdots, a_n))，则表中 (a_{i-1}) 领先于 (a_i)，(a_i) 领先于 (a_{i+1})，称 (a_{i-1}) 是 (a_i) 的直接前驱元素，(a_{i+1}) 是 (a_i) 的直接后继元素。线性表的元素个数 (n) 定义为线性表的长度，当 (n=0) 时，称为空表。

 

线性表的顺序存储结构

 
线性表的顺序存储结构就是在内存中找了块地儿，通过占位的形式，把一定的内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。因此可以用一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为 (0) 的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

来看看线性表的顺序存储结构的代码。

# define MAXSIZE 20    //存储空间初始分配量
typedef int ElemType;    // ElemType 类型根据实际情况而定，这里假设为 int
typedef struct
{
    ElemType data[MAXSIZE];    // 数组存储数据元素，最大值为 MAXSIZE
    int length;     // 线性表当前长度
}SqList;

这里注意描述顺序存储结构需要三个属性：

  • 存储空间的起始位置：数组 data，它的存储位置就是存储空间的存储位置
  • 线性表的最大存储容量：数组长度 MAXSIZE（注意不等于线性表的长度）。
  • 线性表的当前长度：length.

 

线性表顺序存储结构的优缺点

 
线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是 (O(1))；而插入或删除时，时间复杂度都是 (O(n)). 这就说明它比较适合元素个数不太变化，而更多是存取数据的应用。优缺点总结如下：

优点：

  • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速地存取表中任一位置的元素

缺点：

  • 插入和删除操作需要移动大量元素
  • 当线性表长度变化较大时，难以确定存储空间的容量
  • 造成存储空间的 “碎片”

 

线性表的链式存储结构

 
在链式结构中，除了要存数据元素信息外，还要存储它的直接后继元素的存储地址，我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素 (a_i) 的存储映像，称为结点。(n) 个结点链结成一个链表，即为线性表 ((a_1, a_2, cdots, a_n)) 的链式存储结构*，因为此链表的每个结点只包含一个指针域，所以叫做单链表**。

对于线性表来说，总得有个头有个尾，我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个后继指针指向的位置。最后一个结点的指针为“空”（通常用 NULL 或 “^” 符号来表示）。

有时，为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针，如图

数据结构之线性表

注意头指针与头结点的异同点：

头指针：

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

头结点

  • 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
  • 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了
  • 头结点不一定是链表必须要素
     
    来看看线性表的链式存储结构的代码。
// 线性表的单链表存储结构
typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList;   // 定义 LinkList

从这个结构定义中，我们也就知道，结点由存放数据元素的数据域存放后继结点地址的指针域组成。假设 (p) 是指向线性表第 (i) 个元素的指针，则该结点 (a_i) 的数据域我们可以用 (p->data) 来表示，(p->data) 的值是一个数据元素，结点 (a_i) 的指针域可以用 (p->next) 来表示，(p->next) 的值是一个指针，指向第 (i+1) 个元素，即指向 (a_{i+1}) 的指针。也就是说，如果 (p->data = a_i)，那么 (p->next->data = a_{i+1}).
 

单链表结构与顺序存储结构优缺点

 
简单地对单链表结构和顺序结构做对比：

数据结构之线性表

通过上面的对比，我们可以得出一些经验性的结论

  • 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。
  • 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。如果事先知道线性表的大致长度，比如一年 12 个月，一周就是 7 天，这种用顺序存储结构效率会好很多

总之，线性表的存储结构和单链表结构各有优缺点，视实际情况而定。

最后简单说一下静态链表。静态链表是用数组描述的链表，我们让数组的元素都是由两个数域组成， data 和 cur. 也就是说，数组的每个下标都对应一个 data 和下一个 cur. 数据域 data，用来存放数据元素，也就是通常我们要处理的数据；而游标 cur 相当于单链表中的 next 指针，存放该元素的后继在数组中的下标。所以它还有个别名：游标实现法。它有单链表的插入和删除操作性能，但是没有解决连续存储分配带来的表长难以确定的问题，而且失去了顺序存储结构随机存取的特性。

相关推荐