计算机科学基础 线性表

前言

这一章的主题是线性表,数据结构中最基础的部分。主要的内容是线性表本身的定义,线性表的一些基本操作,线性表的两种实现方法和其对比。文中代码不必拘泥细节,重点在于它所展现的核心步骤与思想。

线性表的定义与基本操作

线性表的定义

线性表是一种逻辑结构,是一种抽象的概念,而非具体的某个数据结构,他所表征的是数据元素之间的关系应该如何组织。

线性表的定义:具有相同特性数据元素的一个有限序列。
所包含元素个数为其表长,当表长为零的时候,该线性表为空表。

线性表核心的四大逻辑特性:

  1. 存在唯一的一个表头元素;
  2. 存在唯一的一个队尾元素;
  3. 除表头元素外,线性表中每个数据元素有且仅有一个直接前驱;
  4. 除表尾元素外,线性表中每个数据元素有且仅有一个直接后继。

线性表的基本操作

  1. 初始化——构造一个空表;
  2. 求表长——获得线性表的表长;
  3. 按值查找——根据给定元素值查找线性表中是否含有该元素并返回位置;
  4. 按位查找——根据给定线性表的某个位置获得其元素值;
  5. 插入——将给定的位置和元素值添加到线性表中;
  6. 删除——将给定的线性表的某个位置删除该位置的元素值并返回该值;
  7. 遍历——按顺序访问所有的元素;
  8. 判空——判断线性表当前是否为空表;
  9. 销毁——回收线性表所占空间。

线性表的实现

线性表的顺序存储结构

顺序表的定义

用顺序存储结构实现的线性表叫做顺序表。

顺序存储结构是指,把线性表中的所有元素按照其逻辑顺序,依次存储从指定的存储位置开始的一块连续的物理存储空间中。其特点是逻辑顺序与物理顺序相同。

顺序表的基本操作(三个)

顺序表的插入(五步)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 在顺序表L的第i个位置(1<=i<=L.length+1)插入新元素e
bool ListInsert(SqList &L, int i, ElemType e) {
// 1.判断要插入的位置是否合法
if(i < 1 || i > L.length+1) {
return false;
}
// 2.检查顺序表是否还有多余的物理空间可以插入
if(L.length >= MaxSize) {
return false;
}
// 3.后面的元素往后移一个单位为新元素腾出空间
for(int j = L.length; j >= i; j--) {
L.data[j] = L.data[j - 1];
}
// 4.插入元素
L.data[i - 1] = e;
// 5.顺序表的长度加一
L.length++;
return true;
}

顺序表的删除(四步)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool ListInsert(SqList &L, int i, ElemType &e) {
// 1.判断要删除的位置是否合法
if(i < 1 || i > L.length) {
return false;
}
// 2.获得即将删除的元素
e = L.data[i - 1];
// 3.将后面的元素往前移一个单位覆盖原来删除元素的位置又不改变顺序
for(int j = i; j < L.length; j++) {
L.data[j - 1] = L.data[j];
}
// 4.顺序表长度减一
L.length--;
return true;
}

顺序表的按值查找(两步)

1
2
3
4
5
6
7
8
9
10
11
int LocateElem(SqList L, ElemType e) {
int i;
for(i = 0; i < L.length; i++) {
// 1.遍历查找,返回位序(即下标加一)
if(L.data[i] == e) {
return i + 1;
}
}
// 2.如果没找到就返回位序0表示不存在
return 0;
}

三种操作的时间复杂度都是O(n)。

线性表的链式存储结构

链表的定义

用链式存储结构实现的线性表叫链表。

链式存储结构是指,不需要使用连续的物理存储空间,但是通过使用额外空间在每一个数据元素上都附加数据元素之间的逻辑关系,从而在离散的物理存储空间里实现线性表。

单链表

单链表是指除了包含数据域外,还包含一个指针域用来指向其直接后继结点的链表。

单链表还可以细分为带头结点的单链表和不带头结点的单链表。在带头结点的单链表中,头指针head指向头结点,头结点的数据域不带有任何信息,而头结点的指针域则指向单链表的第一个结点。之所以引入头结点的概念,是为了在操作上能统一,而不用刻意为了head指向的第一个元素单独做一个处理,同时head不会有指向NULL的情况。

在带头结点的单链表中,在head->next为NULL的时候,才表示这个单链表是空的。在不带头结点的单链表中,头指针head直接指向链表中的第一个结点,那么head为NULL的时候就表示链表是空的。

以下介绍单链表核心的六大操作。

单链表的头插法初始化(数据顺序与实际数据顺序相反但是简单)(四步)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
LinkList List_HeadInsert(LinkList &L) {
LNode *s;
int x;
// 1.分配头结点的空间并设置为空表
L = (LNodeList)malloc(sizeof(LNode));
L->next = NULL;

scanf("%d", &x);
while(x != 9999) {
// 2.根据输入数据创建一个新结点
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
// 3.将新结点添加到已有链表的首元素结点位置
s->next = L->next;
L->next = s;
// 4.继续创建下一个结点
scanf("%d", &x);
}
return L;
}

单链表的尾插法初始化(数据顺序与实际顺序相同但是需要额外操作)(七步)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
LinkList List_TailInsert(LinkList &L) {
int x;
// 1.分配头结点的空间
L = (LinkList)malloc(sizeof(LNode));
// 2.创建两个指针分别指向新结点和尾结点
LNode *s, *r = L;
scanf("%d", &x);
while(x != 9999) {
// 3.根据输入数据创建一个新结点
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
// 4.把新结点添加到尾结点之后
r->next = s;
// 5.添加完新结点后,新结点变成尾结点
r = s;
// 6.继续创建下一个结点
scanf("%d", &x);
}
// 7.将尾结点的指针域设置为NULL
r->next = NULL;
return L;
}

单链表的按位查找(线性表位序是从1开始的,返回位序的结点指针)(四步)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
LNode *GetElem(LinkList L, int L) {
int j = 1;
// 1.初始化遍历指针为首元素结点
LNode *p = L->next;
// 2.如果位序不和法就返回NULL
if(i < 1) {
return NULL;
}
// 3.如果p不为空且遍历索引小于要找的位序就继续循环遍历
while(p&&(j < i)) {
p = p->next;
j++;
}
// 4.返回给定位序结点的指针
return p;
}

单链表的按值查找(三步)

1
2
3
4
5
6
7
8
9
10
LNode *LocateElem(LinkList L, ElemType e) {
// 1.初始化遍历指针为首元素结点
LNode *p = L->next;
// 2.遍历直到遍历指针为NULL或者为给定元素值的结点
while(p != NULL && p->data != e) {
p = p->next;
}
// 3.返回遍历指针,没找到就是NULL
return p;
}

单链表的插入(三步)

1
2
3
4
5
6
// 1.获得前驱结点
p = GetElem(L, i - 1);
// 2.前驱结点的后继变成新结点的后继
s->next = p->next;
// 3.前驱结点的后继设置为新结点
p->next = s;

单链表的删除(四步)

1
2
3
4
5
6
7
8
// 1.获得前驱结点
p = GetElem(L, i - 1);
// 2.获得要删除的当前结点
q = p->next;
// 3.让前驱结点的指针域指向要删除的结点的后继
p->next = q->next;
// 4.释放删除结点空间
free(q);

单链表的六个重要算法(头插法、尾插位、按位查找、按值查找、插入、删除)的时间复杂度都是O(n)。

但是当给定前驱结点进行插入的时候,就不需要其第一步,所以时间复杂度就是O(1)。另外删除也可以在给定要删除的结点的情况下实现O(1)的时间复杂度,即把后继的数据覆盖要删除的结点的数据,然后删除后继的结点。

双链表

双链表是指除了包含数据域外,还包含两个指针域分别用来指向其直接前驱结点和直接后继结点的链表。

带头结点的双链表为空的条件是head->next为NULL,不带头结点的双链表为空的条件为head为NULL。

以下重点介绍双链表的两大操作。

双链表的插入(四步)

1
2
3
4
5
6
7
8
// 1.插入结点的后继设置为被插入的结点的后继
s->next = p->next;
// 2.被插入的结点的后继的前驱设置为插入结点
p->next->prior = s;
// 3.插入结点的前驱设置为被插入结点
s->prior = p;
// 4.被插入结点的后继设置为插入结点
p->next = s;

双链表的删除

1
2
3
4
5
6
// 1.要删除的结点的前驱的后继设置为要删除的结点的后继
p->next = q->next;
// 2.要删除的结点的后继的前驱设置为要删除的结点的前驱
q->next->prior = p;
// 3.释放删除结点的空间
free(q);

在给定插入/删除位置结点的情况下上述操作时间复杂度都是O(1)。

循环单链表

循环单链表是指在单链表的基础上,把最后一个结点的指针域,由NULL变为指向第一个结点(带头结点的循环单链表的最后一个结点的指针域指向头结点,而不带头结点的循环单链表的最后一个结点的指针域则指向首元素结点,形式上都是指向head),那么这个链表就由一个单链表变为了一个循环单链表。

带头结点的循环单链表为空时,head等于head->next;不带头结点的循环单链表为空时,head为NULL。

循环双链表

循环双链表是指在双链表的基础上,把最后一个结点的后继指针域指向第一个结点,同时把第一个结点的前驱指针域指向最后一个结点(这里提到的第一个结点的定义与循环单链表相同),那么这个链表就由一个双链表变味了一个循环双链表。

带头结点的循环双链表为空时,head->next等于head->prior等于head。不带头结点的循环双链表为空时,head为NULL。

静态链表

静态链表是借助一维数组实现的,是用顺序存储空间实现离散存储结构的线性表。具体表现为一个结构体数组,每个结构体里包含一个数据域和一个指针域,指针域里存储的实际是结构体数组的下标,而非上述四种链表的物理地址。

对于结束的标志(替代NULL),静态链表的指针域可以设置为-1。

线性表的顺序存储结构(顺序表)与链式存储结构(链表)的比较

空间比较

顺序表是在创建的时候就一次性把空间给分配好了,使用的是连续存储空间,所以能够存储的元素数量是有限的。

链表的存储空间是多次分配的,用多少分配多少,使用的是离散存储空间,理论上不存在上限。

存储密度比较

存储密度可以用数据域所占空间比结点实际使用总空间的比值来度量。

顺序表的每个结点只包含数据域本身,所以存储密度是1。

链表的每个结点除了数据域本身外,还包含指向其他结点的指针域,所以存储密度小于1。

存取方式的比较

顺序表可以随机存取,也可以顺序存取。

链表只能顺序存取(访问某个元素前需要访问其之前所有的数据元素)。

插入/删除效率比较

顺序表插入/删除算法的平均时间复杂度均为O(n),平均需要移动一半的元素。

链表插入/删除算法的平均时间复杂度为O(1),不需要移动元素,只需修改指针。

总结

线性表两种实现方式:顺序表、链表。
其中链表可以根据有无头结点分为两类,但一般默认含有头结点。
链表根据指针域的特点可以分为:单链表、双链表、循环单链表、循环双链表。
同时结合顺序存储,可以实现静态链表。

线性表核心的三大操作分别是:查找、插入、删除。
其中顺序表要理解插入和删除需要移动元素的特点。
链表则需要知道头插尾插两种初始化方法、插入、删除、按值查找和按位查找。

理解两种存储方式的差异与各自的优缺点。