数据结构导论【二】之 线性表_线性表可以方便地随机读取插入删除表中的任一结点

接上一篇：数据结构导论【一】之 概论

一、线性表的基本概念

1.线性表的基本概念

线性表是由n（n >= 0）个数据元素（结点）a1, a2, …, an组成的有限序列。
数据元素的个数n定义为表的长度，n = 0时称为空表，记作()

将非空的线性表（n > 0）记作：L = (a1, a2, …, an)
a1称为起始结点，an为终端结点。对任意一对相邻结点ai和ai+1（1 <= i < n）, ai称为ai+1的直接前驱，ai+1称为ai的直接后继。

PS: 数据元素ai（1 <= i <= n）只是个抽象符号，其具体含义在不同情况下可以不同。

2.线性表的基本术语

起始结点、终端结点、直接前驱、直接后继、线性表长度、空表

3.线性表的逻辑结构特征

对于非空的线性表：线性表中结点具有一对一的关系

线性表中只有一个起始结点，一个终端结点
起始结点没有直接前驱，有一个直接后继
终端结点有一个直接前驱，没有直接后继
除上述俩个结点外，每个结点都有且只有一个直接前驱和一个直接后继。

4.线性表的基本运算

---

二、线性表的顺序实现

线性表顺序存储的方法是：将表中的结点依次存放在计算机内存中一组连续的存储单元中，数据元素在线性表中的邻接关系决定它们在存储空间中的存储位置，即逻辑结构中相邻的结点其存储位置也相邻。

用顺序存储实现的线性表称为顺序表。一般使用数组来表示顺序表。

1.线性表顺序存储的类型定义

假定有一组数据，数据间有顺序：
12、10、5、78、56、45、32
此处数据间的顺序即表示数据间的逻辑关系即线性关系，这一组数据为线性表。

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

1）线性表概念

此处数据间的顺序即表示数据间的逻辑关系即线性关系，这一组数据为线性表

顺序存储线性表时，需要存储：
存储单元大小、数据个数

线性表大小：10 MaxSize
线性表长度：7 Length
所存放数据的类型： DataType

顺序表的结构体定义：

const int Maxsize = 100;
typedef struct {
	DataType data[Maxsize];
	int length;
} Seqlist;

Seqlist L;
1
2
3
4
5
6
7

2）小试题

假设已知a1地址为Loc(a1)，每个数据占c个单元，
则计算ai地址：
Loc(ai) = Loc(a1) + c * (i - 1)

假设线性表中所有结点的类型相同，则每个节点所占用存储空间大小亦相同。
假设表中每个结点占用L个存储单元，其中第一个单元的存储地址则是该结点的存储地址。
并设表中开始结点a1的存储地址是d，
那么结点ai的存储地址Loc(ai):
Loc(ai) = d + L * (i - 1)

b.结论

1. 顺序表是用一维数组实现的线性表，数组下标可以看成是元素的相对地址
2. 逻辑上相邻的元素，存储在物理位置也相邻的单元中

c.顺序存储结构的特点

1. 线性表的逻辑结构与存储结构一致
2. 可以对数据元素实现随机读取

2.线性表的基本运算在顺序表上的实现

// 根据学生档案信息，给出顺序表具体的类型定义
const int Maxsize = 7; // 预先定义数组大小
typedef struct {
	int num; // 学号
	char name[8]; // 姓名
	char sex[2]; // 性别
	int age; // 年龄
	int score; // 入学成绩
} DataType; // 定义结点的类型

typedef struct {
	DataType data[Maxsize]; // 存放数据的数组
	int length; // 线性表的实际长度
} SeqList; // 顺序表的类型
SeqList student; // student 为顺序表的名称
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

根据上述定义，该顺序表的名称为 student，表的最大长度为 7，表的实际长度值在 student.length中。

a.插入

线性表的插入运算是指在表的第i（1 <= i <= n+1）个位置上，插入一个新结点x，使长度为 n 的线性表：(a1, a2, …, ai-1, ai, ai+1,…, an) 变成长度为 n+1 的线性表：(a1, a2, …, ai-1, x, ai, ai+1,…, an)

注意：
1、当表空间已满，不可再做插入操作
2、当插入位置为非法位置，不可做正常插入操作

① 顺序表的插入操作过程

将表中位置为 n，n-1，…， i上的结点，依次后移到位置 n+1, n, …, i+1上，空出第i个位置

1. 在该位置上插入新结点x。仅当插入位置 i = n + 1时，才无需移动结点，直接将x插入表的末尾
2. 该顺序表长度加1

② 插入算法的分析

// 将元素x插入到顺序表L的第i个数据元素之前
void InsertSeqlist(SeqList L, DataType x, int i) {
	if (L.length == Maxsize) exit('表已满');
	if (i < 1 || i > L.length + 1) exit('位置错'); // 检查插入位置是否合法
	for(j = L.length; j >= i; j--) { // 初始 i = L.length，当j大于等于i的时候执行
		L.data[j] = L.data[j - 1]; // 依次后移
	}
	L.data[i - 1] = x; // 元素x置入到下标为 i - 1 的位置
	L.length++; // 表长度加1
}
1
2
3
4
5
6
7
8
9
10

---

b.删除

线性表的删除运算是指将表的第i个结点删去，使长度为n的线性表(a1, a2, …, ai-1, ai, ai+1,…, an)变为(a1, a2, …, ai-1, ai+1,…, an)

当要删除元素的位置 i 不在表长范围内（即 i < 1 或 i > L.length）时，为非法位置，不能做正常的删除操作。

① 顺序表的删除操作过程

1. 若 i = n，则只要删除终端结点，无需移动结点；
2. 若 1 <= i <= n-1，则必须将表中位置 i + 1, i + 2, …, n的结点，依次前移到位置i，i + 1，…，n - 1上，以填补删除操作造成的空缺。
3. 该表长度减1

仅当删除位置 i = n时，
才无需移动结点，直接令表长度 -1 即可

② 删除算法的分析

// 删除线性表L中的第i个数据结点 
void DeleteSeqList(SeqList L, int i) {
	if (i < 1 || i > L.length) exit('非法位置'); // 检查位置是否合法
	for(j = i; j < L.length; j++) { // 第 i 个元素的下标为 i - 1
		L.data[j - 1] = L.data[j]; // 依次左移
	}
	L.length--; // 表长度减1
}
1
2
3
4
5
6
7
8

---

c.定位(查找)

定位运算 LocateSeqlist(L, X) 的功能是求L中值等于X的结点序号的最小值，当不存在这种结点时结果为0。

① 顺序表的定位操作过程

从第一个元素a1起依次和x比较
直到找到一个与x相等的数据元素，则返回它在顺序表中的存储下标或序号；
或者查遍整个表都没有找到与x相等的元素，返回0。

② 定位算法的分析

int LocateSeqlist(SeqList L, DataType x) {
	int i = 0;
	// 在顺序表中查找值为 x 的结点
	while(i < L.length && L.data[i] != x) {
		i++;
	}
	if (i < L.length) { // 若找到值为 x 的元素，返回元素的序号
		return i + 1;
	} else { // 未找到值为x的元素，返回0
		return 0;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

顺序表的求表长操作，直接输出 L.length 即可

d.分析结论

e.顺序表的优缺点

1）优点：

1. 无需为表示结点间的逻辑关系而增加额外存储空间
2. 可以方便地随机存取表中的任一结点

2）缺点：

1. 插入和删除运算不方便，必须移动大量的结点（平均需要移动大约一半的数据元素）
2. 顺序表要求占用连续的空间，存储分配只能预先进行，因此当表长变化较大时，难以确定合适的存储规模。

---

三、线性表的链接存储

链接方式存储的线性表简称为链表。


链表的具体存储表示为：
①用一组任意的存储单元来存放。
②链表中结点的逻辑次序和物理次序不一定相同。还必须存储指示其后继结点的地址信息。

1.单链表的类型定义

a.单链表

data域 – 存放结点值的数据域
next域 – 存放结点的直接后继的地址（位置）的指针域（链域）

所有结点通过指针链接而组成单链表
NULL称为空指针
Head称为头指针变量，存放链表中第一个结点地址。

b.单链表的一般图示法

由于我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针，单链表就可以表示为下图形式：

单链表中第一个结点内一般不存数据，称为头结点，利用头指针存放该结点地址。


为什么要加设头结点？
增加头结点的目的是：方便运算的实现。

c.单链表的类型定义

typedef struct node {
	DataType data; // 数据域
	struct node * next; // 指针域：存放该结点的直接后继结点的地址
} Node, *LinkList;
1
2
3
4

a)是非空的单链表
b)是空单链表

d.单链表的简单操作

1）单链表特点

1. 起始结点又称为首结点，无前驱，故设头指针head指向开始结点
2. 链表由头指针唯一确定，单链表可以用头指针的名字来命名。头指针名是head的链表可称为表head。
3. 终端结点又称为尾结点，无后继，故终端结点的指针域为空，即NULL
4. 除头结点之外的结点为表结点
5. 为运算操作方便，头结点中不存数据

head是链表的头指针，所以是指针类型变量。
head内存放的是头结点的地址。
第一个元素结点：head -> next

2.线性表的基本运算在单链表上的实现

a.初始化

建立一个空的单链表L，InitiateLinkList(L)
一个空的单链表是头指针和一个头结点构成的

假设已定义指针变量t，令t指向一个头结点
并令头结点的next为NULL。

注意：产生头结点时由malloc函数产生一个新节点。

特别注意：malloc函数的使用格式及作用：
动态分配内存函数 malloc 函数格式如下：
（数据类型*） malloc （sizeof(数据类型)）
如：
int *p;
p = (int *);
malloc(sizeof(int));

空表由一个头指针和一个头结点组成。算法描述如下：

// 建立一个空的单链表
LinkList InitiateLinkList() {
	LinkList head;  // 头指针
	head = malloc(sizeof(Node));  // 动态构建一结点，它是头结点
	head -> next = NULL;
	return head;
}
1
2
3
4
5
6
7

在算法中，变量 head 是链表的头指针，它指向新创建的结点，即头结点。一个空单链表仅有一个头结点，初始化的时候它的指针域为NULL。

---

b.求表长

在单链表存储结构中，线性表的长度等于单链表所含结点的个数（不含头结点）

步骤：
1、令计数器 j 为 0
2、令 p 指向头结点
3、当下一个结点不空时，j 加 1，p 指向下一个结点
4、j 的值即为链表中结点个数，即表长度

int lengthLinklist(LinkList head) {
	Node *p;
	j = 0; // 1、令计数器 j 为 0
	p = head; // 2、令 p 指向头结点
	// 3、当下一个结点不空时(代表不是表尾)，j 加 1，p 指向下一个结点
	while (p -> next != NULL) {
		p = p -> next;
		j++;
	}
	// 4、j 的值即为链表中结点个数，即表长度
	return (j);
}
1
2
3
4
5
6
7
8
9
10
11
12

---

c.读表元素

步骤：查找第 i 个结点
1、令计数器 j 为 0
2、令 p 指向头结点
3、当下一个结点不空时，并且 j < i 时，j + 1，p 指向下一个结点
4、如果 j 等于 i，则 p 所指结点为要找的第 i 结点。否则，链表中无第 i 结点

// 读 head 表中第 i 个元素的值
Node * GetLinkList(LinkList head, int i) {
	Node *p;
	int j = 0; // 1、令计数器 j 为 0
	p = head -> next; // 2、令 p 指向头结点
	// 3、当下一个结点不空时，并且 j < i 时，j + 1，p 指向下一个结点
	while ((j < i) && (p != NULL)) {
		p = p -> next;
		j++;
	}
	// 4、如果 j 等于 i，则 p 所指结点为要找的第 i 结点。否则，链表中无第 i 结点
	if (i == j) return (p);
	else return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

d.定位

定位运算是对给定表元素的值，找出这个元素的位置。对于单链表，给定一个结点的值，找出这个结点是单链表的第几个结点。定位运算又称为按值查找。
在定位运算中，也需要从头至尾访问链表，直至找到需要的结点，返回其序号。若未找到，返回0。

具体步骤：
1、令 p 指向头结点
2、令 i = 1；
3、当下一个结点不空时，p 指向下一个结点，同时 i 的值加1
4、直到 p 指向的结点的值为 x，返回 i 的值。
5、如果找不到结点值为 x 的话，返回值为 0.

// 求表head中第一个值等于x结点的序号，若不存在这种结点，返回结果为0
int LocateLinkList(LinkList head, DataType x) {
	Node *p = head;  // p 是工作指针
	p = p -> next;  // 1、令 p 指向头结点
	int i = 1;  // 2、令 i = 1；(i 代表结点的序号)
	// 3、当下一个结点不空时，p 指向下一个结点，同时 i 的值加1
	while (p != NULL && p -> data != x) {
		i++;
		p = p -> next;
	}
	// 4、直到 p 指向的结点的值为 x，返回 i 的值。
	// 5、如果找不到结点值为 x 的话，返回值为 0.
	if (p != NULL) return i;
	else return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

e.插入

插入运算是将值为 x 的新结点插入到表的第 i 个结点的位置上，即插入到 ai-1 与 ai 之间。
具体步骤：
1、找到 ai-1 存储位置q
2、生成一个数据域为 x 的新结点 *p
3、令结点 *p 的指针域指向 *q 的后继结点
4、新结点的指针域指向结点ai。

void InsertLinkList(LinkList head, DataType x, int i) {
	Node *p, *q;
	
	if (i == 1) { // 如果要查找第1个位置，那么我们就得指向头结点了
		q = head;
	} else {
		q = GetLinkList(head, i - 1); // 1、找到 ai-1 存储位置q
	}
	if (q == NULL) { // 找 i - 1 个结点不存在
		exit('找不到插入的位置');
	} else {
		// 2、生成一个数据域为 x 的新结点 *p
		p = malloc(sizeof(Node));
		p -> data = x;
		// 3、令结点 *p 的指针域指向 *q 的后继结点
		p -> next = q -> next;
		// 4、新结点的指针域指向结点ai。
		q -> next = p;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

注意：
链接操作 p -> next = q -> next 和q -> next = p 俩条语句的执行顺序不能颠倒，否则结点 *q 的链域值（即指向原表第 i 个结点的指针）将丢失。

f.删除

1）算法思路（此算法描述删除第 i 个结点）

1、找到第 i - 1 个结点；若存在则继续，否则结束
2、删除第i个结点，并释放对应的内存，结束。

2）算法步骤

1、找到ai - 1（待删结点的直接前驱）的存储位置q
2、令 q -> next指向 ai 的直接后继结点
3、释放结点 ai 的空间，将其归还给“存储池”。

3）程序实现

// 删除表 head 的第 i 个结点
void DeleteLinkList（LinkList head, int i） {
	Node *q;
	// 1、找到ai - 1(待删结点的直接前驱)的存储位置q
	if (i == 1) q = head;
	else q = GetLinkList(head, i - 1);
	// 若直接前驱存在且待删结点存在
	if (q != NULL && q.next != NULL) {
		// p指向待删结点
		p = q.next;
		// 2、令 q -> next指向 ai 的直接后继结点
		q.next = p.next;
		// 3、释放结点 ai 的空间，将其归还给“存储池”。
		free(p);
	} else { // 结点不存在
		exit('找不到要删除的结点');
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

注意：
free§是必不可少的，因为当一个结点从链表移出后，如果不释放它的空间，它将变成一个无用的结点，它会一直占用着系统内存空间，其他程序将无法使用这块空间。

四、其他运算在单链表上的实现

1.建表

步骤：
1.首先建立带头结点的空表
2.其次建立一个新结点，然后将新结点链接到头结点之后，这个结点为尾结点（也是首结点）
3.重复建立新结点和将新结点链接到表尾这俩个步骤，直到线性表中所有元素链接到单链表中。

下述代码用int代替DataType

方法1：

通过调用前面实现的InitiateLinklist和InsertLinklist实现建表算法。

// 假定0是输入结束标志
LinkList CreatLinklist1() {
  Linklist head;
  int x, i;
  head = InitiateLinklist(); // 建立空表
  i = 1; // 置插入位置初值
  scanf("%d", &x); // 读入用户输入的值到x中
  // 输入的不是结束标志时继续插入
  while(x != 0) {
  	InsertLinklist(head, x, i); // 将其插入到head表尾
  	i++; // 修改表尾指针
  	scanf("%d", &x); // 读取用户输入的下一值
  }
  return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法2：

上面的算法由于每次插入都从表头开始查找，比较浪费时间。因为每次都是把新的结点链接到表尾，我们可以用一个指针指向尾结点，这样就为下一个新结点指名了插入位置。

LinkList CreateLinklist2() {
	// q是一个LinkList类型的变量，用来指示链入位置
	LinkList head;
	Node *q, *t;
	int x;
	head = malloc(sizeof(Node)); // 生成头结点
	q = head; // 尾指针置初值
	scanf("%d", &x); // 读入用户输入的值
	// 输入的不是结束标志时继续链入
	while(x != 0) {
		// 生成一个新结点
		t = malloc(sizeof(Node));
		t -> data = x;
		// 新结点t链入
		q -> next = t;
		// 修改尾指针q，指向新的尾结点
		q = t;
		// 读取用户输入的下一个值
		scanf("%d", &x); 
	}
	// q指向尾结点，置尾结点标志
	q -> next = NULL;
	// 返回链表
	return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

示意图：
时间复杂度 O(n)

方法3：

与输入顺序正好相反的倒序插入

LinkList CreateLinklist3() {
	Linklist head;
	Node *p;
	int x;
	// 生成头结点
	head = malloc(sizeof(Node));
	head -> next = NULL;
	scanf("%d", &x);
	// x == 0时结束输入
	while(x) {
		p = malloc(sizeof(Node));
		p -> data = x;
		// 前插：插入到链表的第一个结点处
		p -> next = head -> next;
		head -> next = p;
		scanf("%d", &x);
	}
	return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

示意图：
时间复杂度：O(n)

---

2.删除重复结点

清除单链表中值为 x 的重复结点

步骤：
1、找到值为x的第一个结点位置，p指向该结点
2、从p所指结点开始向后查找，若存在值为x的结点，令q指向x结点前一个执行删除操作。继续查找直到链表末尾。

逐步求精法分析：
整体步骤：
当未到达链表末尾时（ai不是终端结点时）
删除ai+1到an结点中值为ai的结点
i++

伪代码：
i = 1;
while(ai不是终端结点) {
// 删除ai + 1 到 an 结点中值为 ai 的结点
i++;
}

// 删除表head中多余的重复结点
void PurgeLinklist(LinkList head) {
	Node *p, *q, *r;
	// q指示当前检查结点的位置，置其初值指向首结点
	q = head -> next;
	// 当检查结点q不是尾结点时，寻找并删除它的重复结点
	while (q != NULL) {
		p = q; // 工作指针p指向q
		// 当p的后继结点存在时，将其数据域与q数据域比较
		while (p -> next != NULL) {
			// 若p->next是q的重复结点
			if (p -> next -> data == q -> data) {
				r = p -> next; // r指向待删结点
				// 移出结点p->next,p->next指向原来p->next的后继结点
				p -> next = r -> next;
				free(r);
			} else {
				// 否则，让p指向下一个结点
				p = p -> next;
			}
		}
		// 更新检查结点
		q = q -> next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

五、其他链表

1.循环链表

普通链表的终端结点的next值为NULL
循环链表的终端结点的next指向头结点
在循环链表中，从任一结点出发能够扫描整个链表。

如何找到普通链表的尾结点？
如何找到循环链表的尾结点？
在循环链表中附设一个 rear 指针指向尾结点适用于经常使用头尾结点的链表操作中

2.双向循环链表

在链表中设置俩个指针域，
一个指向后继结点
一个指向前驱结点
这样的链表叫做双向链表。

在双向循环链表中：
头指针的prior是链尾
链尾的next是头指针。

a.双向链表的结构体定义

双向循环链表适合应用在需要经常查找结点的前驱和后继的场合。找前驱和后继的复杂度均为：O(1)。

struct dbnode {
	DataType data;
	struct dbnode *prior, *next;
}
typedef struct dbnode *dbpointer;
typedef dbpointer Dlinklist;
1
2
3
4
5
6

假设双向链表中p指向某节点
则有：
p -> prior -> next === p -> next -> prior

---

b.双向链表中结点的删除

设p指向待删结点，删除*p可通过下述语句完成：

// p前驱结点的next链向 p的后继结点
p -> prior -> next = p -> next;
// p后继结点的prior链向 p的前驱结点
p -> next -> prior = p -> prior;
// 释放p的空间
free(p);
1
2
3
4
5
6

---

c.双向链表中结点的插入

在 p 所指结点的后面插入一个新结点*t，需要修改四个指针：

t -> prior = p; // 将新插入的结点的prior指针设置为 p
t -> next = p -> next; // 将新插入的结点的next指针设置为 p 的next结点
p -> next -> prior = t; // 将插入后方的结点的prior指针设置为新插入的结点t
p -> next = t; // 将p的next指针设置为新插入的结点t
1
2
3
4

---

六、顺序实现与链式实现的比较

1. 线性表与链表的优缺点

1、单链表的每个结点包括数据域与指针域，指针域需要占用额外空间。
2、从整体考虑，顺序表要预分配存储空间，如果预先分配得过大，将造成浪费，若分配得过小，又将发生上溢；单链表不需要预先分配空间，只要内存空间没有耗尽，单链表中的结点个数就没有限制。

2. 时间性能的比较

顺序表：

链表：

---

---

---

下一篇：数据结构导论【三】之 栈队列和数组