线性表的特点

• 只有唯一一个首元素

• 只有唯一一个尾元素

• 除首元素外，每个元素只有唯一一个前驱

• 除尾元素外，每个元素只有唯一一个后继

2.1 线性表的类型定义

一个线性表是n个数据元素的有限序列

2.2 线性表的顺序表示和实现

用一组地址连续的存储单元（数组）依次存储线性表的数据元素，即逻辑上相邻的数据元素在物理存储结构上也是相邻的。

存储位置关系

​

特点

• 可以随机存取

• 删除、插入元素较慢

结构定义

• 动态分配内存的顺序存储结构

typedef struct{
    ElemType *elem;  //存储空间首地址
    int length;  //当前长度
    int listsize;  //分配的存储容量
}SqlList;

• 静态顺序存储结构

#define LIST_INIT_SIZE 100
typedef struct{
    ElemType elem[LIST_INIT_SIZE];
    int length;  //当前长度
    int listsize;  //分配的存储容量
}SqlList;

插入和删除的注意点

由于是顺序存储结构，在中间插入或删除元素时，需要移动元素，假若顺序线性表非常长时， 则插入和删除就会较为耗时，时间复杂度为​

插入和删除元素平均移动次数

image

2.3 线性表的链式表示和实现

2.3.1 线性链表

单链表

链表使用一组任意的存储单元存储线性表的数据元素，相邻元素通过指针进行相连，也就是逻辑上相邻的数据元素在物理存储上不必相邻。

结点组成

• 数据域

  存储数据信息

• 指针域

  存储指向下一个结点的指针

结构定义

typedef struct LNode{
    ElemType data; //存储数据
    struct LNode *next;  //存储下一个元素的位置
}LNode, * LinkList;

头指针

通常我们在单链表的第一个结点之前添加一个头结点，头结点可以不存储数据，也可以存储链表的长度等信息，头结点指向链表的第一个结点。

特点

• 不能随机存取

  要找一个元素只能从第一个结点开始，一直沿着这条链找下去，时间复杂度为

• 插入、删除结点很快

  只需断开链表，插入、删除结点即可（不算上找到对应操作位置的时间），算上找到操作位置的时间，总的时间复杂度为

链表的建立

• 头插法

  每次新结点都插在头结点后面

  元素的顺序与插入的顺序相反，先插入的在最后面，后插入的在最前面

  

• 尾插法

  每次新结点都插入在最后面，需要维护一个尾指针来记录最后一个结点的位置.

  元素的顺序与插入的顺序相同

  

静态链表

使用数组存储整个链表，用元素的下标代替指针。

结构定义

#define MAXSIZE 100
typedef struct{
    ElemType data;
    int next;
}component, SLinkList[MAXSIZE];

查找

• 操作和单链表一致

添加/删除结点

• 添加结点需要知道数组中有哪些位置是空的，因此需要维护一条所有未被使用的数组分量的链表
  • 添加结点时，从该链表中取下一个结点使用
  • 删除结点时，将删除的结点链接到该链表中

2.3.2 循环链表

将链表中最后一个结点的指针不再指向NULL,而是指向头结点，从而形成循环。

与单链表的差异

• 单链表在判断是否搜寻到链表尾部时，使用这个判断条件
• 循环链表在判断是否搜寻到链表尾部时，使用这个判断条件

2.3.3 双向链表

上述的链表都为单向链表，只能沿着链表从前往后查找，即每个节点只储存了指向后继的指针，在双向链表中，每个节点不仅存储了指向后继的指针，还存储了指向前驱节点的指针（head->next == NULL）

结构定义

typedef struct DuLNode{
    ElemType data;
    struct DuLNode *prior;
    struct DulNode *next;
}DuLNode, * DuLinkList;