Ch2 线性表 | 数据结构

第 2 章 线性表

---

2.1 线性表

线性结构

线性结构是一个数据元素的有序（次第）集合

例如：26 个英文字母、一副扑克牌的点数

线性结构的四个特征

• 集合中必存在仅有的一个“榜首元素”
• 集合中必存在仅有的一个“最终元素”
• 除最终元素之外，其它数据元素均有仅有的“后继”
• 除榜首元素之外，其它数据元素均有仅有的“前驱”

常见的线性结构：线性表、栈、行列、循环行列、数组、串

例如：成绩单、通讯录、工资表、图书目录。常用的操作是增修改查。

线性表定义

具有相同数据类型的 n（n >= 0）个数据元素的有限序列，一般记为 (a1,a2,…an)(a_{1},a_{2},…a_{n})(a1​,a2​,...an​) ，其间 n 为表长，n=0 时称为空表。

线性表的 ADT 定义

ADT {

• 数据目标(D):

  • D=(ai∣ai∈ElementSet,i=1,2,…,n,n>=0)D=(a_{i} | a_{i} \in ElementSet, i=1,2,…,n,n>=0)D=(ai​∣ai​∈ElementSet,i=1,2,...,n,n>=0)

• 数据联系(S):

  • $S=$

• 根本操作(P):

  • 线性表初始化
  • 销毁线性表
  • 将线性表置空
  • 判别线性表是否为空
  • 求线性表表长
  • 取表元
  • 按值查找
  • 取前驱
  • 取后继
  • 刺进操作
  • 删去操作
  • 遍历操作
    }

例：两个线性表取并集

void union(List &La, List Lb) {
	La_len = ListLength(La);
	Lb_len = ListLength(Lb);
	for (i = 1; i <= Lb_len; i++) {
		GetElem(Lb, i, e);
	}
}

---

2.2 线性表的次序存储与完成

用一组地址连续的存储单元顺次寄存线性表中的数据元素，即以存储方位相邻表明位序相继的两个数据元素之间的前驱和后继的联系，并以表中榜首个元素的存储方位作为线性表的起始方位，称作线性表的基地址。

typedef struct {
	ElemType *elem;
	int length;
	int listsize;
} SqList;

次序表的初始化（时刻复杂度为 $O(1)$ ）

bool InitList_Sq(SqList &L)
{  
	// 结构一个空的线性表 L
 L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); 　　　
	if (!L.elem)
		exit(OVERFLOW);　　 // 存储分配失败　　
                L.length = 0;　　　　　　// 次序表的初始长度为0  
	L.listsize = LIST_INIT_SIZE; // 初始存储容量
	return OK;  
} // InitList_Sq

按位序取表元

bool GetElem_Sq(SqList L, int i, ElemType &e)
{
	if (i < 1 || i > L.length)
		return ERROR; //i值不合法
	e = L.elem[i - 1];
		return OK;
}

次序表的刺进（时刻复杂度为 $O(n)$ ）

bool Insert_Sq(SqList &L, int pos, ElemType e)
{
	if (pos < 1 || pos > L.length + 1)
		return ERROR; //刺进方位不合法
	if (L.length > L.lisesize)
		return ERROR; //当时存储空间已满，无法刺进
	q = &(L, elem[i - 1]);
	for (p = &(L.elem[L.length - 1]); p <= q; p--) { //从最终一个到刺进方位
		*(p + 1) = *p; //刺进最终方位及之后元素右移
	}
	L.elem[pos - 1] = e; // 刺进 e  
	L.length++; // 表长增1  
	return TRUE;  
}

删去元素（时刻复杂度为 $O(n)$ ）

bool ListDelete_Sq(SqList &L, int pos, ElemType &e)
{
	if ((pos < 1) || (pos > L.length))
		return FALSE ; // 删去方位不合法
	e = L.elem[pos - 1];  
	for (j = pos + 1; j <= L.length; ++j) { //从pos后边一个开端一直到最终  
	L.elem[j - 2] = L.elem[j - 1]; } // 被删去元素之后的元素左移 　　
	L.length--;　 // 表长减1  
	return TRUE;  
} // ListDelete

元素定位（时刻复杂度为 $O(n)$ ）

在次序表中“查询”是否存在一个和给定值满意断定条件的元素的最简略的办法是，顺次取出结构中的每个元素和给定值进行比较。

int LocateElem_Sq(SqList L, ElemType e)
{ // 在次序表L中查找第1个值与 e 满意持平条件的元素
 // 若找到，则回来其在 L 中的位序，否则回来0。　 
	i = 1;　　　　　　　　　// i 的初值为第1元素的位序　 
	p = L.elem; 　　　　　　// p 的初值为第1元素的存储方位　　
	while (i <= L.length && !equal(*p++, e))  
　　　 ++i;　 　　　　　　　// 顺次进行断定　　
	if (i <= L.length)
		return i; // 找到满意断定条件的数据元素为第 i 个元素  
	else
		return 0;　// 该线性表中不存在满意断定的数据元素　
} // LocateElem

次序表使用举例

使用1：将次序表(a1，a2，… ，an)从头排列为以a1为界的两部分：a1 前面的值均比 a1 小，a1 后边的值都比a1大。

根本思路：

从第二个元素开端到最终一个元素，逐个向后扫描

1）当时数据元素比 a1 大时，表明它已经在后边，不用改动方位，持续比较下一个

2）当时数据元素比 a1 小，需求将它前面的元素都顺次向后移动一个方位，然后把它置于最前面。（能够优化）

使用2：有次序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个次序表C，要求C的元素也是从小到大的升序排列。

---

2.3 线性表的链式存储与完成

单链表

为树立起数据元素之间的线性联系，对每个数据元素ai，除了寄存数据元素的自身的信息ai之外，还需求和ai一起寄存其后继元素ai+1所在的存储单元的地址，这两部分信息组成一个“结点”

typedef struct LNode {
	ElemType data;
	struct LNode *next;
} LNode，*LinkList;

树立链表

LinkList CreateList_T() {
	LinkList L = NULL;
	LNode *s, *r = NULL;
	int x;
	std:cin >> x;
	while (x != flag) {
		s = new LNode;
		s->data = x;
		if (L == NULL) L = s;
		else r->next = s;
		r = s;
		std::cin >> x;
	}
	if (r != NULL) r->next = NULL;
	return L;
}

求表长

int ListLength_1(LinkList L) {
	LNode *p = L;
	int j = 0;
	while (p->next) {
		p = p->next;
		j++;
	}
	return j;
}

查找操作

• 按序号查找

Status GetElem(LinkList L, int i, ElemType &e)
{
	LNode *p = L->next;
	int j = 1;
	while (p && j < i) {
		p = p->next;
		++j;
	}
	if (!p || j > i) return ERROR;
	e = p->data;
	return OK;
}

• 按值查找

LNode *LocateElem(LinkList L, ElemType e)
{
	LNode *p = L->next;
	while (p && p->data != e)
		p = p->next;
	return p;
}

刺进操作

Status ListInsert(LinkList &L, int i, ElemType e)
{
	LNode *p = L;
	int j = 0;
	while (p && (j < i - 1)) {
		p = p->next;
		++j;
	}
	if (!p || j > i - 1) return ERROR;
	LNode *s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

删去操作

Status ListDelete(LinkList &L, int i)
{
	LNode *p = L;
	int j = 0;
	while (p && (j < i - 1)) {
		p = p->next;
		++j;
	}
	if (!p || j > i - 1) return ERROR;
	LNode *q = p->next;
	p->next = q->next;
	delete q;
	return OK;
}

循环链表

关于单链表而言，最终一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。

双向链表

单链表的结点中只要一个指向其后继结点的指针域next，找后继的时刻功能是O(1)，找前驱的时刻功能是O(n)；能够支付空间的代价使得找前驱的时刻性到达O(1)：每个结点再加一个指向前驱的指针域。

用这种结点组成的链表称为双向链表。

typedef struct dlnode {
	ElemType data;
	struct dlnode *prior,*next;
} DLNode, *DLinkList;

和单链表类似，双向链表一般也是用头指针标识，也能够带头结点和做成循环结构。

在双向链表中，经过某结点的指针p既能够直接得到它的后继结点的指针p->next，也能够直接得到它的前驱结点的的指针p->prior。

在双向链表中刺进一个结点：设p指向双向链表中某结点，s指向待刺进的值为x的新结点，将*s刺进到*p的前面。

在双向链表中删去指定结点：设p指向双向链表中某结点，删去*p。

单链表使用举例

• 已知单链表，写一算法将其逆置

算法思路：顺次取原链表中的每个结点，将其作为榜首个结点刺进到新链表中去，指针q用来当时要处理的结点，指针p指向下一个要处理结点，p为空时完毕。

void reverse(LinkList H)
{
	LNode *p;
	p = H->next;
	H->next = NULL;
	while (p) {
		q = p;
		p = p->next;
		q->next = H->next;
		H->next = q;
	}
}

• 已知单链表，写一算法，删去其重复结点

算法思路：用指针p指向榜首个数据元素结点，从它的后继结点开端到表的完毕，查找与其值相同的结点并删去之；p指向下一个结点；依此类推，p指向最终结点时算法完毕。

void pur_LinkList(LinkList H)
{
	LNode *p, *q, *r;
	p = H->next;
	if (p == NULL) return;
	while (p->next) {
		q = p;
		while (q->next) {
			if (q->next->data == p->data) {
				r = q->next;
				q->next = r->next;
				free(r);
			} else {
				q = q->next;
			}
		}
		p = p->next;
	}
}

• 设有两个单链表A、B，其间元素递增有序，编写算法将A、B归并成一个按元素值递减（答应有相同值）有序的链表C，要求用A、B中的原结点构成，不能从头申请结点。

算法思路：使用A、B两表有序的特色，顺次进行比较，将当时值较小者摘下，刺进到C表的头部，得到的C表则为递减有序的。

LinkList merge(LinkList A, LinkList B)
{
	LinkList C;
	LNode *p, *q, *s;
	p = A->next;
	q = B->next;
	C = A;
	C->next = NULL;
	free(B);
	while (p && q) {
		if (p->data < q->data) {
			s = p;
			p = p->next;
		} else {
			s = q;
			q = q->next;
		}
		s->next = C->next;
		C->next = s;
	}
	if (p == NULL) p = q;
	while (p) {
		s = p;
		p = p->next;
		s->next = C->next;
		C->next = s;
	}
	return C;
}

---

2.4 次序表和链表的比较

次序存储有3个长处：

• 方法简略，各种高级语言中都有数组，简单完成。

• 不用为表明结点间的逻辑联系而增加额定的存储开销。

• 次序表具有按元素序号随机拜访的特色。

次序存储两个缺点：

• 在次序表中做刺进删去操作时，均匀移动大约表中一半的元素，因而对n较大的次序表效率低。

• 需求预先分配足够大的存储空间，估量过大，可能会导致次序表后部很多闲置；预先分配过小，又会形成溢出。

链表的优缺点恰好与次序表相反。

在实践中怎样选取存储结构呢？一般有以下几点考虑：

1. 根据存储的考虑

2. 根据运算的考虑

3. 根据环境的考虑

---

2.5 单链表的使用：多项式

能够看这个题解

02-线性结构2 一元多项式的乘法与加法运算

---

2.6 本章小结

• 线性表的概念

• 线性表的次序存储

• 次序存储线性表的操作

• 线性表的链式存储

• 链式存储线性表的操作

• 头结点及其效果

• 单链表

• 循环链表

• 双向链表

• 次序存储线性表的特色

• 链式存储线性表的特色

• 单链表的使用：多项式及其运算