2.1 线性表的定义和特点

线性表（Linear List）：由n(n>=0) 个数据元素（结点）a1，a2，a3，......an 组成的有限序列

• 其中数据元素的个数 n 定义为表的长度
• 当n=0是称为空表
• 非空的线性表（n>0）记作：（a1，a2，a3，......an ）
• 这里的数据元素 ai （1<= i <= n）只是一个抽象的符号，其具体含义在不同的情况下可以不同

例：26个英文字母组成的英文表

（A，B，C，D，......，Z）

同一线性表中的元素必定具有相同特性，数据元素间的关系是线性关系（1 : 1）

从上述例子可以放出线性表的逻辑特征：

• 在非空的线性表中，有且仅有一个开始结点 a1，它没有直接前趋，而仅有一个直接后继 a2
• 有且仅有一个终端结点 an，它没有直接后继，而仅有一个直接前趋 a(n-1)
• 其余的内部结点 ai (2<= i <= n-1)都有且仅有一个直接前趋 a(i-1)和一个直接后继 a(i+1)

2.2 线性表的类型定义

2.2.1 数据类型定义

抽象数据类型线性表的定义如下：

ADT List{
    数据对象：D = {ai | ai属于Element，(i = 1，2，...，n n>=0)}
	数据关系：R = {<a(i-1)，ai> | a(i-1)，ai属于D，(i=2，3，... ，n)}
	基本操作：
		InitList(&L);
		DestroyList(&L);
		InsertList(&L, i, e);
		DeleteList(&L, i, &e);
	......
}ADT List

2.2.2 基本操作定义

initList(&L)

• 操作结果：构造一个空的线性表

destroyList(&L)

• 初始条件：线性表L已经存在
• 操作结果：销毁线性表L

clearList(&L)

• 初始条件：线性表L已经存在
• 操作结果：将线性表L重置为空表

listIsEmpty(L)

• 初始条件：线性表L已经存在
• 操作结果：若线性表L为空表，则返回TRUE；否则返回FALSE

lengthList(L)

• 初始条件：线性表L已经存在
• 操作结果：返回线性表L中数据元素个数

getElement(L, i, &e)

• 初始条件：线性表L已经存在，1<=i<=lengthList(L)
• 操作结果：用e返回线性表中第 i 个数据元素的值

locateElement(L, e, compare())

• 初始条件：线性表L已经存在，compare()是数据元素判定函数
• 操作结果：返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为 0

priorElement(L, cur_e, &pre_e)

• 初始条件：线性表L已经存在
• 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败；pre_e 无意义

nextElement(L, cur_e, &next_e)

• 初始条件：线性表L已经存在
• 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败；next_e 无意义

insertList(&L, i, e)

• 初始条件：线性表L已经存在，1<=i<=lengthList(L) + 1
• 操作结果：在L的第 i 个位置之前插入新的数据元素e，L的长度 + 1

deleteList(&L, i, &e)

• 初始条件：线性表L已经存在，1<=i<=lengthList(L)
• 操作结果：删除L的第 i 个数据元素，并用e返回其值，L的长度 - 1

traverseList(&L, visvited())

• 初始条件：线性表L已经存在
• 操作结果：依次对线性表中每个元素调用visited()

以上提及的运算是逻辑结构上的运算。只描述了这些运算的功能是“做什么”，至于“如何做”等实现细节，只有待确定了存储结构之后才考虑。后文会给出详细代码

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

2.3.1 线性表的顺序表示

线性表的顺序表示又称为顺序存储结构或顺序映像

顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构

顺序表中元素存储位置的计算

假设线性表的每个元素需占 L 个存储单元，则第 i+1 个数据元素的存储位置和第 i 个数据元素的存储位置之间满足关系：

由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到：

例：如果每个元素占用8个存储单元，ai存储位置是2000单元，则a(i+1)存储位置是 2008单元

但是线性表长可变（删除），数组长度不可动态定义

C语言中一维数组的定义方式：类型说明符 数组名[常量表达式]

常量表达式中可以包含常量和符号常量，不能包含变量。即C语言中不允许对数组的大小作动态定义

所以我们可以用一变量表示顺序表的长度属性

#define LIST_INIT_SIZE 100	// 线性表存储空间的初始分配量
typedef struct{
	elemType elem[LIST_INIT_SIZE];	// 数组
	int length;	// 当前长度
}sequenceList;

注意这是类C语言，并不是C语言！！！
其中 elemType 代表元素类型，它可以是：int、float、double等等

后文有许多这种类C语言

多项式的顺序存储结构类型定义

多项式如下：

代码实现

/**
* 多项式的顺序存储结构定义.
*/
#ifndef POLYNOMIALLIST  
#define POLYNOMIALLIST


#define MAXSIZE 100		// 多项式能达到的最大值


typedef struct {
    float p;	// 系数
    int e;		// 指数
}polynomial;


typedef struct {
    polynomial* data;	// 这里我用了指针，后续可以用malloc()动态分配空间
    int length;			// 多项式中当前项的个数
}polynomialList;


#endif // !POLYNOMIALLIST

动态分配：

polynomialList list;

list.data = (polynomial*)malloc(sizeof(polynomial) * MAXSIZE);

list.length = 0;

2.3.2 顺序表中基本操作的实现

定义：

#define LIST_INIT_SIZE 100	// 线性表存储空间的初始分配量
typedef struct{
	elemType* elem;	// 数组
	int length;		// 当前长度
}sequenceList;

sequenceList L;		// 定义变量L，L是sequenceList这种类型的，L是个顺序表

顺序图示意图

我在 StatusCode.h 定义了状态码

#pragma once


#ifndef JUST_INCLUDE_ONCE
#define JUST_INCLUDE_ONCE


typedef  int status;	// 函数返回值类型


#define	TRUE  1
#define	FALSE  0
#define	OK 11
#define	ERROR  10
#define	INFEASIBLE  -1
#define	OVERFLOW  -2


#endif // !JUST_INCLUDE_ONCE

定义

typedef struct {
	char elem;
}sequence;


typedef struct {
	sequence* data;		// 这里我用了指针，后续可以用malloc()动态分配空间
	int length;			// 多项式中当前项的个数
}sequenceList;

初始化

/*******************************************************************************************************************************
 * @description：初始化顺序表
 * @param：list
 * @return：状态码
 */
status initSequenceList(sequenceList* list)
{
	list->data = (sequence*)malloc(sizeof(sequence) * MAXSIZE);
	if (!list->data) {
		exit(OVERFLOW);		// 分配失败直接退出
	}

	list->length = 0;
	return OK;
}

销毁

/*******************************************************************************************************************************
 * @description：销毁顺序表
 * @param：list
 */
void destroySequenceList(sequenceList* list)
{
	// 判断是否为空
	if (list->data) {
		free(list->data);
	}
}

清空

/*******************************************************************************************************************************
 * @description：清空顺序表
 * @param：list
 */
void clearSequenceList(sequenceList* list)
{
	list->length = 0;
}

获取顺序表长度

/*******************************************************************************************************************************
 * @description：获取顺序表的长度
 * @param：list
 * @return：长度
 */
int getSequenceListLength(sequenceList* list)
{
	return list->length;
}

判断顺序表是否为空

/*******************************************************************************************************************************
 * @description：判断顺序表是否为空
 * @param：list
 * @return：为空 返回 1
 */
status isSequenceListEmpty(sequenceList* list)
{
	return list->length == 0 ? TRUE : FALSE;
}

取值

/*******************************************************************************************************************************
 * @description：取顺序表第i个元素
 * @param：list	顺序表指针
 * @param：i	位置
 * @param：e	元素
 * @return：状态码
 */
status getSequenceListElement(sequenceList* list, int i, sequence* e)
{
	if (i < 1 || i > list->length) {
		return ERROR;
	}

	*e = list->data[i - 1];
	return OK;
}

这个算法时间复杂度为：O(1)

按值查找

这里我们用顺序查找，是最简单的查找（暴力破解）

• 在线性表L中查找与指定值e相同的数据元素的位置
• 从表的一端开始，逐个进行记录的关键字和给定值的比较。找到，返回该元素的位置序号，未找到，返回0

/*******************************************************************************************************************************
 * @description：按值查找，找元素与给定元素相同的那一项的位置
 * @param：list	顺序表指针
 * @param：e	字符
 * @return：找到返回位置；没找到返回 0
 */
int locateSequenceListElement(sequenceList* list, char e)
{
	int i = 0;
	for (i = 0; i < list->length; i++) {
		if (list->data[i].elem == e) {
			return i + 1;
		}
	}
	return 0;
}

算法分析：

• 查找次数跟给出的值有关，所以我们看平均查找长度
• 平均查找长度ASL（Average Search Length）

• 为了确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度

所以上面算法的时间复杂度：O(n)

插入

算法思想：

1. 判断插入位置 i 是否合法
2. 判断存储空间是否已满，若已满返回ERROR
3. 将第 n 至第 i 的元素依次向后移动一个位置，空出第 i 个位置

图解：

插入位置在最后

/*******************************************************************************************************************************
 * @description：插入元素，位置在最后
 * @param：list	顺序表指针
 * @param：e	要插入的元素
 * @return：	状态码
 */
status lastInsertSequenceListElement(sequenceList* list, sequence e)
{
	// 判断是否已满
	if (list->length == MAXSIZE) {
		return ERROR;
	}
	list->data[list->length] = e;
	list->length++;
	return OK;
}

插入位置在中间

/*******************************************************************************************************************************
 * @description：插入元素，位置在中间
 * @param：list	顺序表指针
 * @param：i	要插入的位置
 * @param：e	要插入的元素
 * @return：状态码
 */
status middleInsertSequenceListElement(sequenceList* list, int i, sequence e)
{
	int j = 0;
	// 判断是否已满
	if (list->length == MAXSIZE) {
		return ERROR;
	}
	// 判断位置是否合法
	if (i < 1 || i > list->length + 1) {
		return ERROR;
	}
	// 从最后一个元素开始，依次向后移动一位
	for (j = list->length - 1; j >= i - 1; j--) {
		list->data[j + 1] = list->data[j];
	}
	list->data[i - 1] = e;
	list->length++;
	return OK;
}

插入位置在最前

/*******************************************************************************************************************************
 * @description：插入元素，位置在最前面
 * @param：list	顺序表指针
 * @param：e		要插入的元素
 * @return：状态码
 */
status firstInsertSequenceListElement(sequenceList* list, sequence e)
{
	// 调用插在中间位置的函数，把 i 设为 1
	return middleInsertSequenceListElement(list, 1, e);
}

完整的插入函数，根据 i 调用上面的函数

/*******************************************************************************************************************************
 * @description：完整的插入函数
 * @param：list	顺序表指针
 * @param：i	要插入的位置
 * @param：e	要插入的元素
 * @return：	状态码
 */
status insertSequenceListElement(sequenceList* list, int i, sequence e)
{
	// 判断位置是否合法
	if (i < 1 || i > list->length + 1) {
		return ERROR;
	}
	// 判断是否已满
	if (list->length == MAXSIZE) {
		return ERROR;
	}
	// 判断插入位置
	if (i == 1) {
		return firstInsertSequenceListElement(list, e);
	}
	else if (i == list->length + 1) {
		return lastInsertSequenceListElement(list, e);
	}
	else {
		return middleInsertSequenceListElement(list, i, e);
	}
}

插入算法的时间复杂度为：O(n)

删除

算法思想：

1. 判断删除位置 i 是否合法（合法值为 1<= i <= n）
2. 将欲删除的元素保留在e中
3. 将第 i+1 至 第 n 位的元素依次向前移动一个位置
4. 表长减 1，删除成功返回OK

/*******************************************************************************************************************************
 * @description：删除线性表L中第 i 个元素，用 e 返回其值
 * @param：list	顺序表指针
 * @param：i	要插入的位置
 * @param：e	要插入的元素
 * @return：	状态码
 */
status deleteSequenceListElement(sequenceList* list, int i, sequence* e)
{
	int j = 0;
	// 判断位置是否合法
	if (i < 1 || i > list->length) {
		return ERROR;
	}
	// 用 e 返回被删除的元素
	*e = list->data[i - 1];

	// 从第 i 个元素开始，依次向前移动一位
	for (j = i; j < list->length; j++) {
		list->data[j - 1] = list->data[j];
	}
	list->length--;
	return OK;
}

时间复杂度：O(n)

打印顺序表

/*******************************************************************************************************************************
 * @description：打印顺序表
 * @param：list
 */
void printSequenceList(sequenceList* list)
{
	for (int i = 0; i < list->length; i++) {
		printf("%c ", list->data[i].elem);
	}
	printf("\n");
}

2.3.3 测试代码

void SequenceListMain()
{
	sequenceList list;

	// 初始化
	initSequenceList(&list);

	// 插入5个值，分别为：a，b，c，d，e
	for (int i = 1; i < 6; i++)
	{
		sequence e = { i + 96 };
		insertSequenceListElement(&list, i, e);
	}


	// 打印线性表
	printSequenceList(&list);
	// 输出：a b c d e


	// 获取顺序表长度
	int length = getSequenceListLength(&list);
	printf("\n顺序表长度为：%d\n", length);
	// 输出：顺序表长度为：5


	// 获取顺序表中第3个元素
	sequence getedElement;
	getSequenceListElement(&list, 3, &getedElement);
	printf("\n顺序表中第3个元素为：%c\n", getedElement.elem);
	// 输出：顺序表中第3个元素为：c


	// 获取顺序表中第一个匹配到的元素
	int indexGet = locateSequenceListElement(&list, 'd');
	if (indexGet) {
		printf("\n顺序表中第一个匹配到的元素为第 %d 个\n", indexGet);
	}
	else {
		printf("\n顺序表中没有匹配到的元素\n");
	}
	// 输出：顺序表中第一个匹配到的元素为第 4 个


	// 获取顺序表中第一个匹配到的元素
	int indexNotGet = locateSequenceListElement(&list, 'z');
	if (indexNotGet) {
		printf("\n顺序表中第一个匹配到的元素为第 %d 个\n", indexNotGet);
	}
	else {
		printf("\n顺序表中没有匹配到的元素\n");
	}
	// 输出：顺序表中没有匹配到的元素


	// 定位元素在顺序表中的位置
	int localtion = locateSequenceListElement(&list, 'c');
	printf("\n字符c在顺序表中的位置为：%d\n", localtion);
	// 输出：字符c在顺序表中的位置为：3


	// 删除顺序表中的某个元素
	sequence delElement;
	deleteSequenceListElement(&list, 3, &delElement);
	// 打印线性表
	printf("\n删除第3个元素后的顺序表为：");
	printSequenceList(&list);
	// 输出：删除第3个元素后的顺序表为：a b d e


	// 清空顺序表
	clearSequenceList(&list);
	printf("\n清空顺序表后，顺序表中的元素为：");
	printSequenceList(&list);
	// 输出：清空顺序表后，顺序表中的元素为：


	// 销毁顺序表
	destroySequenceList(&list);

}

下面你只需在main.c 中调用 SequenceListMain()

int main()
{
	// 顺序表
	SequenceListMain();

	return 0;
}

测试截图

2.3.4 顺序表小结

顺序存储的特点

• 利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表中的逻辑结构与存储结构一致
• 在访问线性表时，可以快速地计算出任何一个数据元素地存储地址。因此可以粗略地认为，访问每个元素所花时间相等
• 存取元素的方法称为随机存取法

顺序表的操作算法分析：

• 时间复杂度：查找、插入、删除算法的平均时间复杂度为 O(n)
• 空间复杂度：O(1) 没有占用辅助空间

优点：

• 存取密度大
• 可以随机存取表中任意元素

缺点：

• 在插入、删除某一元素时，需要移动大量元素
• 浪费存储空间
• 属于静态存储函数，数据元素的个数不能自由扩充，不灵活

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

• 用一组物理位置任意的存储单元来存放线性表的数据元素
• 这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中任意位置上的
• 链表中元素的逻辑次序和物理次序不一定相同

2.4.1 相关术语

1. 结点：数据元素的存储映像。由数据域和指针域两部分组成

2. 链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构

示意图

用 ^ 表示 0 null，即最后一个结点

单链表：结点只有一个指针域的链表，称为单链表或线性链表

双链表：结点有两个指针域的链表，称为双链表

循环链表：首尾相接的链表称为循环链表

3. 头指针、头结点和首元结点

头指针：是指向链表中第一个结点的指针

头结点：是在链表的首元结点之前附设的一个结点

首元结点：是指链表中存储第一个数据元素 a1 的结点

链表的存储结构示意图有以下两种形式

表示空表：

• 无头结点时，头指针为空时表示空表

• 有头结点时，当头结点的指针域为空时表示空表

设置头结点的好处：

• 便于首元结点的处理：首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理

头结点的数据域内装的是什么：

• 头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能记入链表长度值

链式存储的特点：

• 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
• 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等 （这种存取元素的方法称为：顺序存取法）

2.4.2 单链表

单链表的定义与表示

定义

typedef struct {
	ElementType data;	// 结点的数据域
	node* next;			// 结点的指针域

}node, * linkList;		// node: 结点类型, linkList: 结点指针类型

// 定义链表
linkList linklist;

// 定义结点指针
linkList p;

例如：存储学生学号、姓名、成绩的单链表结点类型定义如下

typedef struct {
	char name[8];	// 数据域
	char num[8];	// 数据域
	int score;		// 数据域
}elemType;

typedef struct {
	elemType data;	// 数据域
	node* next;		// 指针域
}node, * linkList;

单链表的操作

这里指的是带头结点的单链表

定义

为了好测试我把结构定义的简单点

typedef struct Node {
	char data;				// 结点的数据域
	struct Node* next;		// 结点的指针域

}node, * singleLinkList;	// node: 结点类型, singleLinkList: 结点指针类型

初始化

算法步骤：

1. 生成新结点作为头结点，用头指针L指向头结点
2. 将头结点的指针域置空

/*******************************************************************************************************************************
 * @description：初始化带头结点的单链表
 * @param：L	指向头结点的头指针
 * @return：状态码
 */
status initSingleLinkList(singleLinkList* L)
{
	*L = (singleLinkList)malloc(sizeof(node));
	if (!*L) {
		return ERROR;
	}
	(*L)->next = NULL;
	return OK;
}

判断空表

链表中无元素，称为空链表（头指针和头结点仍然在）

算法思路：

• 判断头结点的指针域是否为空

/*******************************************************************************************************************************
 * @description：判断头结点的指针域是否为空
 * @param：L		头结点
 * @return：若为空，返回 1
 */
status isSingleLinkListEmpty(singleLinkList L)
{
	if (L->next == NULL) {
		return TRUE;
	}
	else {
		return FALSE;
	}
}

销毁

算法思路：

• 从头指针开始，依次释放所有结点

/*******************************************************************************************************************************
 * @description：销毁单链表
 * @param：L	指向头结点的指针
 * @return：状态码
 */
status destroySingleLinkList(singleLinkList* L)
{
	singleLinkList p;
	while (*L) {
		p = *L;
		*L = (*L)->next;
		free(p);
	}
	return OK;
}

清空

链表仍然存在，但链表中无元素，称为空链表（头指针和头结点仍然在）

算法思路：

• 依次释放所有结点，并将头结点指针域设置为空

/*******************************************************************************************************************************
 * @description：清空单链表
 * @param：L	指向头结点的指针
 * @return：	状态码
 */
status clearSingleLinkList(singleLinkList* L)
{
	singleLinkList p, q;
	p = (*L)->next;
	while (p) {
		q = p->next;
		free(p);
		p = q;
	}
	// 头结点指针域置空
	(*L)->next = NULL;
	return OK;
}

到这里要说明一下：

可以看到上面几个函数有的参数是 linkList* L ， 有的是 linkList L

带 * 的表示指向头结点的头指针

不带的表示为头结点

其实用C++的引用(linkList& L) 代码会整洁很多

获取表长

算法思路：

• 从首元结点开始，依次计数所有结点

/*******************************************************************************************************************************
 * @description：获取链表表长
 * @param：L	头结点
 * @return：	表长
 */
int getSingleLinkListLength(singleLinkList L)
{
	int count = 0;
	singleLinkList p = L->next;	// p 指向第一个结点，即首元结点
	while (p) {
		count++;
		p = p->next;
	}
	return count;
}

取值

取单链表中的第 i 个元素的内容

从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第 i 个结点为止。因此，链表不是随机存取结构

算法思路：

1. 从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值p = L->next
2. count 做计数器，累计当前扫描过的结点数，j初值为1
3. 当p指向扫描到的下一节点时，计数器count 加 1
4. 当 count = i 时，p所指的结点就是要找的第 i 个结点

/*******************************************************************************************************************************
 * @description：取单链表中的第 i 个元素的内容
 * @param：L	单链表头结点
 * @param：i	第几个元素
 * @param：e	元素的内容，由于我定义时是 char 类型，所以这边用 char*
 * @return：	状态码
 */
status getSingleLinkListElement(singleLinkList L, int i, char* e)
{
	int count = 1;
	singleLinkList p = L->next;	// p 指向第一个结点，即首元结点
	while (p && count < i) {
		p = p->next;
		count++;
	}
	// 循环结束找到了第 i 个的位置，再次进行判断
	if (!p || count > i) {
		return ERROR;
	}
	*e = p->data;
	return OK;
}

查找

返回地址

根据指定数据获取该数据所在的位置地址

算法步骤：

1. 从第一个结点起，依次和e相比较
2. 如果找到一个其值与e相等的数据元素，则返回其在链表中的”地址“

/*******************************************************************************************************************************
 * @description：根据指定数据获取该数据所在的位置（地址）
 * @param：L	头结点
 * @param：e	要查找的值
 * @return：	在单链表中的地址
 */
singleLinkList getSingleLinkListElementAddress(singleLinkList L, char e)
{
	singleLinkList p = L->next;
	while (p && p->data != e) {
		p = p->next;
	}
	return p;
}

时间复杂度：O(n)

返回位置序号

根据指定数据获取该数据所在的位置序号

算法步骤：

1. 从第一个结点起，依次和e相比较
2. 如果找到一个其值与e相等的数据元素，则返回其在链表中的”位置序号“

/*******************************************************************************************************************************
 * @description：根据指定数据获取该数据所在的位置序号
 * @param：L	头结点
 * @param：e	要查找的值
 * @return：	在单链表中的位置序号
 */
int getSingleLinkListElementIndex(singleLinkList L, char e)
{
	int count = 1;
	singleLinkList p = L->next;
	while (p && p->data != e) {
		p = p->next;
		count++;
	}
	// 没找到
	if (!p) {
		return 0;
	}
	return count;
}

时间复杂度：O(n)

插入

在第 i 个结点前插入值为e的新结点

算法思路：

/*******************************************************************************************************************************
 * @description：在第 i 个结点前插入值为e的新结点
 * @param：L	头结点
 * @param：i	要插入的位置
 * @param：e	要插入的元素
 * @return：	状态码
 */
status insertSingleLinkListElement(singleLinkList L, int i, char e)
{
	int count = 1;
	singleLinkList p = L;
	singleLinkList s;
	while (p && count < i) {
		p = p->next;
		count++;
	}
	// 循环结束找到了第 i 个的位置，再次进行判断
	if (!p || count > i) {
		return ERROR;
	}
	s = (singleLinkList)malloc(sizeof(node));		// 创建一个新节点 s
	if (!s) {
		return ERROR;
	}
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

时间复杂度：O(n)

删除

删除第 i 个结点

算法思路：

/*******************************************************************************************************************************
 * @description： 删除第 i 个结点
 * @param：L	头结点
 * @param：i	要删除的位置
 * @param：e	用于接受删除的值
 * @return：	状态码
 */
status deleteSingleLinkListElement(singleLinkList L, int i, char* e)
{
	int count = 1;
	singleLinkList p = L;
	singleLinkList q;
	while (p->next && count < i) {
		p = p->next;
		count++;
	}
	// 循环结束找到了第 i 个的位置，再次进行判断
	if (!p->next || count > i) {
		return ERROR;
	}
	// p->next = p->next->next
	q = p->next;
	p->next = q->next;
	*e = q->data;	// 将删除的值用 e 接收
	free(q);
	return OK;
}

时间复杂度：O(n)

单链表的建立

头插法

元素插入在链表头部，也叫前插法

算法思路：

1. 从一个空表开始，重复读入数据
2. 生成新节点，将数据存放到新节点的数据域中
3. 从最后一个结点开始，依次将各结点插入到链表的前端

/*******************************************************************************************************************************
 * @description：单链表的建立--头插法
 * @param：L	头指针
 * @param：n	要创建几个元素
 * @return：	状态码
 */
status createSingleLinkList_Head(singleLinkList* L, int n)
{
	singleLinkList p;
	// 初始化单链表，调用之前写的初始化函数
	if (!initSingleLinkList(L)) {
		return ERROR;
	}
	for (int i = 0; i < n; i++) {
		p = (singleLinkList)malloc(sizeof(node));
		if (!p) {
			return ERROR;
		}
		// scanf("%c", p->data);
		p->data = i + 97;	// e d c b a ......
		p->next = (*L)->next;
		(*L)->next = p;
	}
	return OK;
}

时间复杂度：O(n)

尾插法

元素插入在链表尾部，也叫做后插法

算法思路：

1. 从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针 r 指向链表的尾结点
2. 初始时，r 同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r 指向新结点

/*******************************************************************************************************************************
 * @description：单链表的建立--尾插法
 * @param：L	头指针
 * @param：n	要创建几个元素
 * @return：	状态码
 */
status createSingleLinkList_Tail(singleLinkList* L, int n)
{
	singleLinkList p, r;
	// 初始化单链表，调用之前写的初始化函数
	if (!initSingleLinkList(L)) {
		return ERROR;
	}
	r = *L;	// r 指向尾结点
	for (int i = 0; i < n; i++) {
		p = (singleLinkList)malloc(sizeof(node));
		if (!p) {
			return ERROR;
		}
		// scanf("%c", p->data);
		p->data = i + 65;	// A B C D E ......
		r->next = p;
		r = p;	// r 指向新的尾结点
	}
	r->next = NULL;
	return OK;
}

时间复杂度：O(n)

打印单链表

/*******************************************************************************************************************************
 * @description：打印单链表中的元素
 * @param：L	头结点
 */
void printSingleLinkList(singleLinkList L)
{
	singleLinkList p = L->next;
	while (p) {
		printf("%c ", p->data);
		p = p->next;
	}
	printf("\n");
}

测试代码

void SingleListMain() {

	singleLinkList single_link_list_head;

	/*******************************************************************************************************************************
	 * @description：测试单链表的创建--头插法
	 */
	 // 用头插法创建一个单链表，里面元素为：e d c b a
	createSingleLinkList_Head(&single_link_list_head, 5);
	printf("用头插法创建的单链表中的元素为：");
	printSingleLinkList(single_link_list_head);
	// 输出：用头插法创建的单链表中的元素为：e d c b a



	singleLinkList single_link_list_tail;

	/*******************************************************************************************************************************
	 * @description：测试单链表的创建--尾插法
	 */
	createSingleLinkList_Tail(&single_link_list_tail, 5);
	printf("\n用尾插法创建的单链表中的元素为：");
	printSingleLinkList(single_link_list_tail);
	// 输出：用尾插法创建的单链表中的元素为：A B C D E



	/*******************************************************************************************************************************
	 * @description：测试清空操作，删除头插法创建的单链表 single_link_list_head
	 */
	clearSingleLinkList(&single_link_list_head);
	printf("\n清空头插法创建的单链表后，单链表中的元素为：");
	printSingleLinkList(single_link_list_head);
	// 输出：清空头插法创建的单链表后，单链表中的元素为：



	/*******************************************************************************************************************************
	 * @description：测试判断空表操作，上面已经将 single_link_list_head 清空
	 */
	if (isSingleLinkListEmpty(single_link_list_head)) {
		printf("\n头插法创建的单链表为空\n");
	}
	else {
		printf("\n头插法创建的单链表不为空\n");
	}
	// 输出：头插法创建的单链表为空



	/*******************************************************************************************************************************
	 * @description：测试销毁操作，销毁头插法创建的单链表 single_link_list_head，销毁成功返回 1
	 */
	if (destroySingleLinkList(&single_link_list_head)) {
		printf("\n成功销毁头插法创建的单链表\n");
	}
	else {
		printf("\n销毁头插法创建的单链表失败\n");
	}
	// 输出：成功销毁头插法创建的单链表



	/*******************************************************************************************************************************
	 * @description：测试获取表长操作，获取尾插法创建的链表的长度  single_link_list_tail
	 */
	int tailLinkListLength = getSingleLinkListLength(single_link_list_tail);
	printf("\n尾插法创建的单链表的长度为：%d\n", tailLinkListLength);
	// 输出：尾插法创建的单链表的长度为：5



	/*******************************************************************************************************************************
	 * @description：测试取值操作，查找在 single_link_list_tail 中 第 3 个元素的内容
	 */
	char c;
	getSingleLinkListElement(single_link_list_tail, 3, &c);
	printf("\n尾插法创建的单链表中的第 3 个元素为：%c\n", c);
	// 输出：尾插法创建的单链表中的第 3 个元素为：C




	/*******************************************************************************************************************************
	 * @description：测试取值操作--返回地址
	 */
	singleLinkList p = getSingleLinkListElementAddress(single_link_list_tail, 'C');
	printf("\n尾插法创建的单链表中的元素 C 的地址为：%p\n", p);
	// 输出：尾插法创建的单链表中的元素 C 的地址为：0x000000000061FEB0   ps：地址是会变化的




	/*******************************************************************************************************************************
	 * @description：测试取值操作--返回位置序号
	 */
	int num = getSingleLinkListElementIndex(single_link_list_tail, 'C');
	printf("\n尾插法创建的单链表中的元素 C 的位置序号为：%d\n", num);
	// 输出：尾插法创建的单链表中的元素 C 的位置序号为：3




	/*******************************************************************************************************************************
	 * @description：测试插入操作，在 C 前面插入 Z
	 */
	insertSingleLinkListElement(single_link_list_tail, 3, 'Z');
	printf("\n在 C 前面插入 Z 后，尾插法创建的单链表中的元素为：");
	printSingleLinkList(single_link_list_tail);
	// 输出：在 C 前面插入 Z 后，尾插法创建的单链表中的元素为：A B Z C D E




	/*******************************************************************************************************************************
	 * @description：测试删除操作，删除 single_link_list_tail 中第3个元素
	 */
	char deletedChar;
	deleteSingleLinkListElement(single_link_list_tail, 3, &deletedChar);
	printf("\n删除尾插法创建的单链表中的第 3 个元素后，单链表中的元素为：");
	printSingleLinkList(single_link_list_tail);
	// 输出：删除尾插法创建的单链表中的第 3 个元素后，单链表中的元素为：A B C D E
	printf("\n删除的元素为：%c\n", deletedChar);
	// 输出：删除的元素为：Z

}

测试截图

2.4.3 循环链表

定义

循环链表：是一种头尾相接的链表（即：表中最后一个结点的指针域指向头结点，整个链表形成一个环）

优点：从表中任一结点出发均可找到表中其它结点

注意：由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断 p 或 p->next是否为空，而是判断它们是否等于头指针

表的操作通常是在表的首尾位置上进行的，所以对循环链表我们用尾指针

合并两个循环链表

带尾指针循环链表的合并（将Tb合并在Ta之后）

操作步骤：

1. p存表头结点 p = Ta->next
2. Tb表头连接到Ta表尾 Ta->next = Tb->next->next
3. 释放Tb表头结点 delete Tb->next
4. 修改指针 Tb->next = p

//循环链表定义和带头结点单链表定义一样
typedef struct CircularNode {
	char data;				// 结点的数据域
	struct CircularNode* next;		// 结点的指针域
}circularNode, * circularLinkList;


/*******************************************************************************************************************************
 * @description：带尾指针循环链表的合并（将Tb合并在Ta之后）
 * @param：Ta
 * @param：Tb
 * @return：Tb的尾指针
 */
circularLinkList mergeCircularLinkList(circularLinkList Ta, circularLinkList Tb)
{
	circularLinkList p;
	circularLinkList temp;

	// 1. p存表头结点
	p = Ta->next;

	// 2. 将Ta的尾结点的指针域指向Tb的首元结点
	temp = Tb->next;	//	借用临时变量找到Tb的头结点
	Ta->next = temp->next;

	// 3. 将Tb的尾结点的指针域指向Ta的头结点
	Tb->next = p;

	// 4. 释放Tb的头结点
	free(temp);

	return Tb;
}

时间复杂度：O(1)

测试代码

void circularLinkListMain()
{
	// 1. 创建两个循环链表Ta，Tb，并把尾结点返回
	circularLinkList Ta;
	circularLinkList Tb;

	circularLinkList Ta_tail = createCircularLinkList(&Ta, 5);	// 元素：A B C D E
	printf("循环链表 Ta 中元素为：");
	printCircularLinkList(Ta);
	// 输出：循环链表Ta中元素为：A B C D E

	circularLinkList Tb_tail = createCircularLinkList(&Tb, 5);	// 元素：A B C D E
	printf("\n循环链表 Tb 中元素为：");
	printCircularLinkList(Tb);
	// 输出：循环链表Tb中元素为：A B C D E


	// 2. 将Tb拼接在Ta后
	mergeCircularLinkList(Ta_tail, Tb_tail);
	printf("\n拼接后循环链表中元素为：");
	//printCircularLinkList(ret);
	printCircularLinkList(Ta);
	// 输出：拼接后循环链表中元素为：A B C D E A B C D E

}

测试截图

2.4.4 双向链表

定义

在单链表的每个结点里再增加一个指向直接前驱的指针域 prior，这样链表中就形成了有两个方向不同的链，故称为双向链表

类C语言定义如下：

typedef struct DoublyNode
{
	struct DoublyNode* prior;
	ElementType data;
	struct DoublyNode* next;
}doublynode, * doublyLinkList;

双向循环链表：

• 让头节点的前驱指针指向链表的最后一个结点
• 让最后一个结点的后继指针指向头结点

双向链表的对称性（设指针p指向某一结点）

p->prior->next = p = p->next->prior

在双向链表中有些操作（如：ListLength、GetElem等），因仅涉及一个方向上的指针，故它们的算法与线性链表相同。但在插入、删除时，则需要同时修改两个方向上的指针，两者的操作的时间复杂度为：O(n)

插入

/*******************************************************************************************************************************
 * @description：在带头结点的双向循环链表L中第i个位置之前插入元素e
 * @param：L	头指针
 * @param：i	要插入的位置
 * @param：e	要插入的元素
 * @return：	状态码
 */
status doublyLinkListInsert(doublyLinkList* L, int i, char e)
{
	doublyLinkList p, s;
	int j;

	// 1.判断i是否合法
	if (i < 1) {
		return ERROR;
	}

	// 2.找到第i个结点
	p = *L;
	j = 0;
	while (p && j < i) {
		p = p->next;
		++j;
	}

	// 3.判断i是否合法
	if (!p || j > i) {
		return ERROR;
	}

	// 这时候以及找到第i个结点了

	// 4.分配内存
	s = (doublyLinkList)malloc(sizeof(doublynode));
	if (!s) {
		return ERROR;
	}

	// 5.插入
	s->data = e;
	s->prior = p->prior;
	p->prior->next = s;
	s->next = p;
	p->prior = s;

	return OK;
}

删除

在带头结点的双向循环链表L中删除第i个元素，并用e返回其值

/*******************************************************************************************************************************
 * @description：在带头结点的双向循环链表L中删除第i个元素，并用e返回其值
 * @param：L	头指针
 * @param：i	要删除第几个元素
 * @param：e	用于接收删除的元素
 * @return：	状态码
 */
status doublyLinkListDelete(doublyLinkList* L, int i, char* e)
{
	doublyLinkList p;
	int j;
	// 1.判断i是否合法
	if (i < 1) {
		return ERROR;
	}
	// 2.找到第i个结点
	p = *L;
	j = 0;
	while (p->next && j < i) {
		p = p->next;
		++j;
	}
	// 3.判断i是否合法
	if (!p->next || j > i) {
		return ERROR;
	}
	// 这时候以及找到第i个结点了

	// 4.删除
	*e = p->data;
	p->prior->next = p->next;
	p->next->prior = p->prior;
	free(p);
	return OK;
}

创建

/*******************************************************************************************************************************
 * @description：创建双向循环链表
 * @param：L	头指针
 * @param：n	要创建几个元素
 * @return：	状态码
 */
status createDoublyLinkList(doublyLinkList* L, int n)
{
	doublyLinkList p, r;
	*L = (doublyLinkList)malloc(sizeof(doublynode));
	if (!(*L)) {
		return ERROR;
	}
	(*L)->prior = NULL;
	(*L)->next = NULL;
	r = *L;
	for (int i = 0; i < n; i++) {
		p = (doublyLinkList)malloc(sizeof(doublynode));
		if (!p) {
			return ERROR;
		}
		p->data = i + 65;	// data char类型：A B C D E
		r->next = p;
		p->prior = r;
		r = p;
	}
	r->next = *L;
	(*L)->prior = r;
	return OK;
}

测试

void DoublyLinkListMain()
{
	/*******************************************************************************************************************************
	 * @description：测试创建双向循环链表
	 */
	doublyLinkList doubly_link_list;
	createDoublyLinkList(&doubly_link_list, 5);
	printf("双向循环链表中元素为：");
	printDoublyLinkList(doubly_link_list);
	// 输出：双向循环链表中元素为：A B C D E



	/*******************************************************************************************************************************
	 * @description：测试插入操作，在第3个元素前插入 Z
	 */
	insertdoublyLinkList(&doubly_link_list, 3, 'Z');
	printf("\n插入Z后，双向循环链表中元素为：");
	printDoublyLinkList(doubly_link_list);
	// 输出：插入Z后，双向循环链表中元素为：A B Z C D E



	/*******************************************************************************************************************************
	 * @description：测试删除操作，删除第3个元素 Z
	 */
	char delDoublylinkchar;
	deletedoublyLinkList(&doubly_link_list, 3, &delDoublylinkchar);
	printf("\n删除Z后，双向循环链表中元素为：");
	printDoublyLinkList(doubly_link_list);
	// 输出：删除Z后，双向循环链表中元素为：A B C D E
	printf("\n被删除的元素为：%c\n", delDoublylinkchar);
	// 输出：被删除的元素为：Z

}

测试截图

2.5 顺序表和链表的比较

链式存储结构：

• 优点

• 结点空间可以动态申请和释放
• 插入和删除操纵不需要移动数据元素

• 缺点：

• 存储密度小，每个结点的指针域需额外占用存储空间
• 非随机存取

比较

2.6 线性表的应用

2.6.1 线性表的合并

问题描述：

假设利用两个线性表La和Lb分别表示两个集合A和B，现要求一个新的集合A=A U B，去掉重复元素

算法思路：依次取出Lb中的每个元素，执行以下操作：

1. 在La中查找该元素
2. 如果找不到，则将其插入La的最后

类C语言

void union(List &La, List Lb)
{
    La_len = Listlength(La);
    Lb_len = Listlength(Lb);
    for(i=1; i<=Lb_len; i++)
    {
        GetElement(Lb, i, e);
        
        if(!(LocateElem(La, e)))
        {
            ListInsert(&La, ++La_len, e);
        }
    }
}

时间复杂度：O(La_len * Lb_len)

2.6.2 有序表合并

已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列

算法步骤：

1. 创建一个空表Lc
2. 依次从La或Lb中“摘取”元素较小的结点插入到Lc表的最后，直至其中一个表变为空表为止
3. 继续将La或Lb其中一个表的剩余结点插在Lc表的最后

用顺序表实现

类C语言

void MergeList_Sq(SqList LA, SqList LB, SqList& LC)
{
    // 指针pa和pb的初值分别指向两个表的第一个元素
    pa = LA.elem;
    pb = LB.elem;
    // 新表的长度为待合并两表的长度之和
    LC.length = LA.length + LB.length;
    // 为合并后的新表分配一个数组空间
    LC.elem = new ElemType[LC.length];
    // 指针pc指向新表的第一个元素
    pc = LC.elem;
    // pa_last，pb_last分别指向两表的最后一个元素
    pa_last = LA.elem + LA.length - 1;
    pb_last = LB.elem + LB.length - 1;
    // 赋初值操作结束

    while(pa<=pa_list&&pb<=pb_last)
    {
        // 依次“摘取”两表中值较小的值
        if(*pa<*pb)
            *pc++ = *pa++;
        else
            *pc++ = *pb++;
    }

    while(pa<=pa_list)		// LB表已到达表尾，将LA中剩余元素加入LC
        *pc++ = *pa++;
    while(pb<=pb_last)		// LA表已到达表尾，将LB中剩余元素加入LC
         *pc++ = *pb++;
}

时间复杂度：O(Listlength(La) + Listlength(Lb))

空间复杂度：O(Listlength(La) + Listlength(Lb))

用链表实现

类C语言

void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc)
{
    pa = La->next;
    pb = Lb->next;
    pc = Lc = La;	// 用La的头结点作为Lc的头结点

    while(pa&&pb)
    {
        if(pa->data<=pb->data){
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else{
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa:pb;	// 插入剩余段
    delete Lb;				// 释放Lb头结点
}

时间复杂度：O(Listlength(La) + Listlength(Lb))

空间复杂度：O(1)

2.7 案例分析与实现

2.7.1 连续多项式运算

实现两个多项式加、减、乘运算

即将问题转化为对数组操作

相加

2.7.2 稀疏多项式运算

问题分析：

则有：

再：

• 创建一个新数组c
• 分别从头遍历比较a和b的每一项

• 指数相同：对应系数相加，若其和不为0，则在c中增加一个新项
• 指数不同：则将指数较小的项复制到c中

• 一个多项式已遍历完毕时，将另一个剩余项依次复制到c中即可

类C语言

void CreatePolyn(Polynomial& P, int n)
{
    P = new PNode;
    P->next = NULL;
    for(i=1; i<=n;i++)
    {
        s = new PNode;
        cin>>s->coef>>s->expn;
        pre = P;
        q = P->next;
        while(q && q->expn < s->expn)
        {
            pre = q;
            q = q->next;
        }
        s->next = q;
        pre->next = s;
    }
}

多项式相加

算法步骤：

1. 初始化指针p1和p2，分别指向Pa和Pb的首元结点
2. p3指向多项式的当前结点，初值为Pa的头结点
3. 当指针p1和p2均未到达相应表尾时，则循环比较p1和p2所指结点对应的指数值（p1->expn与p2->expn）有下列三种情况：

1. 当 p1->expn == p2->expn 时，则将两个结点中的系数相加

1. 若和不为0：则修改p1所指结点的系数值，同时删除p2所指结点
2. 若和为0：则删除p1和p2所指结点

2. 当 p1->expn < p2->expn时，则应摘取p1所指结点插入到“和多项式”链表中去
3. 当 p1->expn > p2->expn时，则应摘取p2所指结点插入到“和多项式”链表中去

4. 将非空多项式的剩余段插入到p3所指结点之后
5. 释放Pb的头结点

/*******************************************************************************************************************************
 * @description：稀疏多项式相加
 * @param：La
 * @param：Lb
 * @return：多项式和
 */
polynomialList addPolynomialList(polynomialList La, polynomialList Lb)
{
	polynomialList Lc;
	initPolynomialList(&Lc);

	polynomialList pa = La->next;
	polynomialList pb = Lb->next;
	polynomialList pc = Lc;

	while (pa && pb) {
		if (pa->expn == pb->expn) {
			int sum = pa->coef + pb->coef;
			if (sum) {
				insertPolynomialListElement(pc, 1, sum, pa->expn);
				pc = pc->next;
			}
			pa = pa->next;
			pb = pb->next;
		}
		else if (pa->expn > pb->expn) {
			insertPolynomialListElement(pc, 1, pb->coef, pb->expn);
			pc = pc->next;
			pb = pb->next;
		}
		else {
			insertPolynomialListElement(pc, 1, pa->coef, pa->expn);
			pc = pc->next;
			pa = pa->next;
		}
	}
	while (pa) {
		insertPolynomialListElement(pc, 1, pa->coef, pa->expn);
		pc = pc->next;
		pa = pa->next;
	}
	while (pb) {
		insertPolynomialListElement(pc, 1, pb->coef, pb->expn);
		pc = pc->next;
		pb = pb->next;
	}
	return Lc;
}