数据结构第二章（线性表）

2024-04-17 21:18:05

写在前面：

本系列笔记主要以《数据结构（C语言版）》为参考，结合下方视频教程对数据结构的相关知识点进行梳理。所有代码块使用的都是C语言，如有错误欢迎指出。
视频链接：第01周a--前言_哔哩哔哩_bilibili

一、线性表的定义和特点

同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序偶关系。

由n（n≥0）个数据特性相同的元素构成的有限序列称为线性表，线性表中元素的个数n定义为线性表的长度，当n=0时称之为空表。

对于非空的线性表或线性结构，其特点是：

①存在唯一的一个被称作“第一个”的数据元素。

②存在唯一的一个被称作“最后一个”的数据元素。

③除第一个元素之外，结构中的每个数据元素均只有一个前驱。

④除最后一个元素之外，结构中的每个数据元素均只有一个后继。

二、线性表的顺序表示和实现

1、线性表的顺序表示

（1）线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像，通常称这种存储结构的线性表为顺序表，其特点是逻辑上相邻的数据元素，其物理位置也是相邻的。

（2）假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储起始位置，则线性表中第i+ 1个数据元素的存储位置 $LOC\left ( a_{i+1} \right )$ 和第i个数据元素的存储位置 $LOC\left ( a_{i} \right )$ 之间满足关系 $LOC\left ( a_{i+1} \right )=LOC\left ( a_{i} \right )+l$ 。

（3）一般来说，线性表的第i个数据元素的存储位置为 $LOC\left ( a_{i+1} \right )=LOC\left ( a_{1} \right )+\left ( i-1 \right )\times l$ ，其中 $LOC\left ( a_{1} \right )$ 是线性表的第一个数据元素的存储位置，通常称作线性表的起始位置或基地址。由此可见，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

（4）在C语言中可用动态分配的一维数组表示线性表，描述如下：

#define MAXSIZE 100    //数组空间大小

typedef int ElemType;  //元素类型以整型为例

typedef struct SqList
{
	ElemType* elem;  //存储空间的基地址
	int length;      //当前长度
}SqList;

enum Status          //表示状态的枚举，用来表示针对数据结构操作的结果
{
	OVERFLOW,
	ERROR,
	OK
};

①数组空间通过初始化动态分配得到，初始化完成后，数组指针elem指示顺序表的基地址，数组空间大小为MAXSIZE。

②元素类型定义中的ElemmType数据类型是为了描述统一而自定的，在实际应用中、用户可根据实际需要具体定义表中数据元素的数据类型，既可以是基本数据类型，如int、float、char等，也可以是构造数据类型，如struct结构体类型。

③length表示顺序表中当前数据元素的个数。因为C语言数组的下标是从0开始的，而位置序号是从1开始的，所以要注意区分元素的位置序号和该元素在数组中的下标位置之间的对应关系。

elem[0]	elem[1]	elem[2]	…	elem[length-1]	空闲区
$a_{1}$	$a_{2}$	$a_{3}$	…	$a_{length}$	空闲区

④Status表示针对顺序表的操作是否有效，用来返回给调用顺序表操作的代码段，代码段可根据返回值判断操作是否有效。

2、顺序表中基本操作的实现

（1）初始化：顺序表的初始化操作就是构造一个线性表。

Status InitList(SqList* L)  //初始化
{
	(*L).elem = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);  //为顺序表分配一个大小为MAXSIZE的数组空间
	if (!(*L).elem)
		exit(OVERFLOW);  //存储分配失败，退出
	(*L).length = 0;     //表的当前长度为0，没有任何元素
	return OK;
}

①算法步骤：

[1]为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。

[2]将表的当前长度设为0。

②时间复杂度：O(1)。

（2）取值：取值操作是根据指定的位置序号i获取顺序表中第i个数据元素的值。

Status GetElem(SqList L, int i, ElemType* e)  //取值
{
	if (i<1 || i>L.length)
		return ERROR;
	*e = L.elem[i - 1];
	return OK;
}

①算法步骤：

[1]判断指定的位置序号i是否合理，如果相应位置上没有元素存在或者序号超出取值范围，都返回ERROR表示操作有误。

[2]若i值合理，则将第i个数据元素赋给参数e，通过e返回第i个数据元素的传值。（需要说明的是，返回值已被表示状态的枚举使用，所以这里使用指针传递的方式返回取值）

②时间复杂度：O(1)。

（3）查找：查找操作是根据指定的元素值e查找顺序表中第一个值与e相等的元素，若查找成功则返回该元素在表中的位置序号，若查找失败则返回0。

int LocateElem(SqList L, ElemType e)  //查找
{
	for (int i = 0; i < L.length; i++)
	{
		if (L.elem[i] == e)
			return i + 1;
	}
	return 0;  //查找失败，返回0
}

①算法步骤：

[1]从第一个元素起，依次将其值和e相比较，若找到值与e相等的元素，则查找成功，返回该元素的序号i+1。

[2]若查遍整个顺序表都没有找到，则查找失败，返回0。

②在查找时，为确定元素在顺序表中的位置，需和给定值进行比较的数据元素个数的期望值称为查找算法在查找成功时的平均查找长度（ASL）。假设 $p_{i}$ 是查找第i个元素的概率， $C_{i}$ 为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数，则在长度为n的线性表中，查找成功时的平均查找长度为 $ASL=\sum_{i=1}^{n}p_{i}C_{i}$ 。在顺序表查找的过程中， $C_{i}$ 取决于所查元素在表中的位置，假设每个元素的查找概率相等，则 $ASL=\frac{n+1}{2}$ ，由此可见，顺序表按值查找算法的平均时间复杂度为O(n)。

（4）插入：线性表的插入操作是指在表的第i个位置插入一个新的数据元素e，使长度为n的线性表变成长度为n+1的线性表。

Status ListInsert(SqList* L, int i, ElemType e)  //插入
{
	if ((i < 1) || (i > L->length + 1))
		return ERROR;
	if (L->length == MAXSIZE)
		return ERROR;
	for (int j = (*L).length - 1; j >= i - 1; j--)
	{
		L->elem[j + 1] = L->elem[j];
	}
	L->elem[i - 1] = e;
	L->length++;
	return OK;
}

①插入操作示意图：

②算法步骤：

[1]判断插入位置i是否合法（i值的合法范围是1≤i≤n+1），若不合法则返回ERROR。

[2]判断顺序表的存储空间是否已满，若满则返回ERROR。

[3]将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置（当i=n+1时无需移动）。

[4]将要插入的新元素e放入第i个位置。

[5]表长加1。

③假设在线性表的任何位置上插入元素都是等概率的， $E_{ins}$ 为在长度为n的线性表中插入一个元素时所需移动元素次数的期望值（平均次数），则 $E_{ins}=\frac{1}{n+1}\sum_{i=1}^{n+1}(n-i+1)=\frac{n}{2}$ ，由此可见，顺序表插入算法的平均时间复杂度为O(n)。

（5）删除：线性表的删除操作是指将表的第i个元素删去，将长度为n的线性表变成长度为n-1的线性表。

Status ListDelete(SqList* L, int i)   //删除
{
	if ((i < 1) || (i > L->length))
		return ERROR;
	for (int j = i; j < L->length; j++)
	{
		L->elem[j - 1] = L->elem[j];
	}
	L->length--;
	return OK;
}

①删除操作示意图：

②算法步骤：

[1]判断删除位置i是否合法（合法值为1≤i≤n），若不合法则返回ERROR。

[2]将第i+1个至第n个元素依次向前移动一个位置（i=n时无须移动）。

[3]表长减1。

③假定在线性表的任何位置上删除元素都是等概率的， $E_{del}$ 为在长度为n的线性表中删除一个元素时所需移动元素次数的期望值（平均次数），则 $E_{del}=\frac{1}{n}\sum_{i=1}^{n}(n-i)=\frac{n-1}{2}$ ，由此可见，顺序表删除算法的平均时间复杂度为O(n)。

（6）销毁：线性表的销毁操作是指将线性表从存储空间中移除，释放其所占有的存储空间。

void DestoryList(SqList* L)  //销毁
{
	if (L->elem)
		free(L->elem);
}

（7）清空：线性表的清空操作是指将线性表中的元素全部进行逻辑删除（物理上还存储在内存中，只是没办法用前面写的算法访问它们，待新元素进入数据结构后旧元素将被覆盖）。

void ClearList(SqList* L)  //清空
{
	L->length = 0;
}

（8）判断是否为空：判断线性表中是否有元素。

int IsEmpty(SqList L)  //判断线性表是否为空
{
	if (L.length == 0)
		return 1;
	return 0;
}

（9）返回线性表的长度：返回线性表当前的元素个数。

int GetLength(SqList L)  //获取线性表的长度
{
	return (L.length);
}

3、顺序表的优缺点

（1）优点：

①存储密度大。（存储密度指的是结点本身所占存储量和结点结构所占存储量的比值，在顺序表中结点结构只比结点本身多了一个顺序表的长度）

②可以随机存取表中任一元素。

（2）缺点：

①在插入、删除某一元素时需要移动大量元素。

②属于静态存储模式，数据元素的个数不能*扩充。（当然，去掉MAXSIZE的限制后是可以*扩充的，只是要反复使用realloc函数进行动态内存开辟，也很麻烦）

③当存储的元素个数远小于MAXSIZE时，会造成存储空间的浪费。

三、线性表的链式表示和实现

1、单链表的定义和表示

（1）线性表链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素 $a_{i}$ 与其直接后继数据元素 $a_{i+1}$ 之间的逻辑关系，对数据元素 $a_{i}$ 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（直接后继的存储位置），这两部分信息组成数据元素 $a_{i}$ 的存储映像，称为结点。结点包括两个域，其中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域，指针域中存储的信息称作指针或链，n个结点链接成一个链表，即为线性表的链式存储结构（此链表的每个结点中只包含一个指针域，故又称线性链表或单链表）。

（2）根据链表结点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等，其中单链表、循环链表和双向链表多用于实现线性表的链式存储结构。

（3）对于单链表而言，整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点（第一个数据元素的存储映像，也称首元结点）的存储位置。同时，由于最后一个数据元素没有直接后继，则单链表中最后一个结点的指针为空（NULL）。

（4）在C语言中可用“结构指针”来表示单链表，描述如下：

typedef int ElemType;  //以整型为例

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

enum Status
{
	ERROR,
	OK
};

①这里定义的是单链表中每个结点的存储结构，它包括两部分：存储结点的数据域data，其类型用通用类型标识符ElemType表示；存储后继结点位置的指针域next，其类型为指向结点的指针类型LNode *。

②为了提高程序的可读性，在此对同一结构体指针类型起了两个名称——LinkList与LNode *，两者本质上是等价的。通常习惯上用LinkList定义单链表，强调定义的是某个单链表的头指针，用LNode *定义指向单链表中任意结点的指针变量。

③单链表由头指针唯一确定，因此单链表可以用头指针的名字命名。

④若定义LinkList或LNode *p，则p为指向某结点的指针变量，表示该结点的地址，而*p为对应的结点变量，表示该结点的名称。

（5）为了处理方便，在单链表的第一个结点之前附设一个结点，称之为头结点，头结点是在首元结点之前附设的一个结点，其指针域指向首元结点，另外头结点的数据域可以不存储任何信息，也可存储与数据元素类型相同的其它附加信息。

①头指针是指向链表中第一个结点的指针。若链表设有头结点，则头指针所指结点为线性表的头结点；若链表不设头结点，则头指针所指结点为该线性表的首元结点。

②增加了头结点后，首元结点的地址保存在头结点（其“前驱”结点）的指针域中，则对链表的第一个数据元素的操作与对其它数据元素的操作相同，无须进行特殊处理。

③当链表不设头结点时，假设L为单链表的头指针，它应该指向首元结点，则当单链表为长度n为0的空表时，L指针为空（头结点不计入链表长度值）；增加头结点后，无论链表是否为空，头指针都是指向头结点的非空指针。

（6）链表（链式存储结构）的特点：

①结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上大概率不相邻。

②访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描剩余结点（顺序存取法）。

2、单链表中基本操作的实现

（1）初始化：单链表的初始化操作就是构造一个空表。

Status InitList(LinkList* L)   //初始化
{
	*L = (LinkList)malloc(sizeof(LNode));  //生成新结点作为头结点，用头指针指向头结点
	(*L)->next = NULL;                     //头结点的指针域为空
	return OK;
}

①算法步骤：

[1]生成新结点作为头结点，用头指针L指向头结点。

[2]头结点的指针域置空。

②时间复杂度：O(1)。

（2）取值：根据给定的结点位置序号i，在链表中获取该结点的值，不过这里不能像顺序表那样随机访问，只能从链表的首元结点触发，顺着链域next逐个结点向下访问。

Status GetElem(LinkList L, int i, ElemType* e)  //取值
{
	LinkList p;
	p = L->next;  //p指向首元结点
	int j = 1;    //计数器j初值赋为1
	while (p && (j < i))  //顺链域向后查找，直到p为空或p指向第i个元素
	{
		j++;  //计数器j相应加1
		p = p->next;  //p指向下一个结点
	}
	if (!p || (j > i))  //i值不合法
	{
		return ERROR;
	}
	*e = p->data;  //取第i个结点的数据域
	return OK;
}

①算法步骤：

[1]用指针p指向首元结点，用j做计数器，初值赋为1。

[2]从首元结点开始依次顺着链域next向下访问，只要指向当前结点的指针p不为空（NULL），并且没有达到序号为i的结点，则循环执行两步操作——p指向下一个结点、计数器j相应加1。

[3]退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i值不合法（i大于表长n或i小于等于0），取值失败返回ERROR，否则取值成功，此时j=i，p所指的结点就是要找的第i个结点，用参数e保存当前结点的数据域，返回OK。

②该算法的平均时间复杂度为O(n)。

（3）查找：链表中按值查找的过程和顺序表类似，从链表的首元结点出发，依次将结点值和给定值e进行比较，返回查找结果。

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

①算法步骤：

[1]用指针p指向首元结点。

[2]从首元结点开始依次顺着链域next向下查找，只要指向当前结点的指针p不为空，并且p所指结点的数据域不等于给定值e，则循环执行操作——p指向下一个结点。

[3]返回p，若查找成功，p此时指向结点的地址值，若查找失败，则p的值为NULL。

②该算法的平均时间复杂度为O(n)。

（4）插入：在单链表的两个数据元素a和b之间插入一个数据元素x。

Status ListInsert(LinkList* L, int i, ElemType e)  //插入
{
	LinkList p;
	p = *L;
	int j = 0;
	while (p && (j < i - 1))  //查找第i-1个结点，p指向该结点
	{
		p = p->next;
		j++;
	}
	if (!p || (j > i - 1))  //i值不合法
	{
		//printf("ERROR\n");
		return ERROR;
	}
	LinkList s = (LinkList)malloc(sizeof(LNode));  //生成新结点*s
	s->data = e;        //将结点*s的数据域置为e
	s->next = p->next;  //将结点*s的指针域指向结点第i个结点
	p->next = s;        //将结点*p的指针域指向结点*s
	return OK;
}

①插入操作示意图：

②算法步骤：

[1]查找第i-1个结点的位置，并由指针p指向该结点。

[2]生成一个新结点*s。

[3]将新结点*s的数据域置为e。

[4]将新结点*s的指针域指向第i个结点。

[5]将结点*p的指针域指向新结点*s。

③该算法的平均时间复杂度为O(n)。

（5）删除：删除单链表中指定位置的元素。

Status ListDelete(LinkList* L, int i)  //删除
{
	LinkList p;
	p = *L;
	int j = 0;
	while (p->next && (j < i - 1))  //查找第i-1个结点，p指向该结点
	{
		p = p->next;
		j++;
	}
	if (!p->next || (j > i - 1))  //i值不合法
	{
		return ERROR;
	}
	LinkList q = p->next;
	p->next = p->next->next;
	free(q);
	return OK;
}

①删除操作示意图：

②算法步骤：

[1]查找第i-1个结点并由指针p指向该结点。

[2]临时保存待删除结点（第i个结点）的地址在q中，以备释放。

[3]将结点*p的指针域指向第i个结点的直接后继结点。

[4]释放第i个结点的空间。

③该算法的平均时间复杂度为O(n)。

（6）求单链表的表长：返回单链表中的元素个数。

int ListLength(LinkList L)  //求单链表表长
{
	LinkList p;
	p = L->next;    //p指向第一个结点
	int count = 0;
	while (p)       //遍历单链表，统计结点数
	{
		p = p->next;
		count++;
	}
	return count;
}

（7）销毁：将整个单链表从内存中移除，释放其先前所占有的存储空间。

Status DestoryList(LinkList* L)  //销毁单链表
{
	LNode* p;
	while ((*L))
	{
		p = (*L);
		(*L) = (*L)->next;
		free(p);
	}
	return OK;
}

（8）清空：将单链表中的元素全部清除，这里进行的是物理删除，当然，头结点需要保留。

Status ClearList(LinkList* L)  //清空单链表
{
	LNode *p, *q;
	p = (*L)->next;
	while (p)
	{
		q = p;
		p = p->next;
		free(q);
	}
	(*L)->next = NULL;
	return OK;
}

（9）判断单链表是否为空：判断单链表中是否有元素，这可以通过判断其头结点的指针域是否指向NULL来判断。

int ListEmpty(LinkList L)  //判断单链表是否为空
{
	if (L->next == NULL)
		return 1;   //单链表为空，返回1
	return 0;       //单链表不为空，返回0
}

（10）创建单链表：建立一个包括若干个结点的链表，不同于初始化，初始化仅创建了头结点。

①前插法：通过将新结点逐个插入链表的头部（头结点之后）来创建链表，每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后。（时间复杂度为O(n)）

void CreateList_H(LinkList *L, int n)  //前插法
{
	*L = (LinkList)malloc(sizeof(LNode));
	(*L)->next = NULL;       //先建立一个带头结点的空链表
	for (int i = 0; i < n; i++)
	{
		LinkList p = (LinkList)malloc(sizeof(LNode));  //生成新结点
		scanf("%d", &(p->data));    //输入元素值赋给新结点*p的数据域
		p->next = (*L)->next;       //新结点*p的指针域指向头结点之后的第一个结点
		(*L)->next = p;             //将新结点*p插入到头结点之后
	}
}

②后插法：通过将新结点逐个插入链表的尾部来创建链表，每次申请一个新结点，读入相应的数据元素值，为了使新结点能够插入表尾，需要增加一个尾指针r指向链表的尾结点。（时间复杂度为O(n)）

void CreateList_R(LinkList *L, int n)  //后插法
{
	*L = (LinkList)malloc(sizeof(LNode));
	(*L)->next = NULL;       //先建立一个带头结点的空链表
	LinkList r = *L;         //尾指针r初始化，指向头结点
	for (int i = 0; i < n; i++)
	{
		LinkList p = (LinkList)malloc(sizeof(LNode));  //生成新结点
		scanf("%d", &(p->data));    //输入元素值赋给新结点*p的数据域
		r->next = p;                //将新结点*p插入尾结点*r之后
		p->next = NULL;             //当前尾结点指针域为空
		r = r->next;                //r指向新的尾结点
	}
}

3、循环链表

（1）循环链表是另一种形式的链式存储结构，其特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环，由此，从表中任一结点出发均可找到表中其它结点。下图所示的是单链的循环链表的逻辑结构（当然，多重链也可有对应的循环链表）。

（2）循环单链表的操作和单链表基本一致，差别仅在于：当链表遍历时，判别当前指针p是否指向表尾结点的终止条件不同。在单链表中判别条件为“p != NULL”或“p -> next != NULL”，而在循环列表中判别条件为“p != L”或“p -> next != L”（L是头指针）。

（3）在某些情况下，若在循环链表中设立尾指针而不设头指针，可使一些操作简化，例如将两个线性表合并成一个表时，仅需将第一个表的尾指针指向第二个表的第一个结点，第二个表的尾指针指向第一个表的头结点，然后释放第二个表的头结点。当线性表以下图所示的循环链表作存储结构时，合并表的操作仅需改变两个指针值即可（同时需要释放其中一个表的头结点）。

4、双向链表

（1）以上讨论的链式存储结构的结点中只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针向后寻查其它结点，若要寻查结点的直接前驱，则必须从表头指针出发。为克服单链表这种单向性的缺点，可利用双向链表。

（2）在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱，在C语言中描述如下：

typedef int ElemType;  //以整型为例

typedef struct DuLNode
{
	ElemType data;
	struct DuLNode *prior;  //指向直接前驱
	struct DuLNode *next;   //指向直接后继
}DuLNode, *DuLinkList;

enum Status
{
	ERROR,
	OK
};

（3）和单循环链表类似，双向链表也可以有循环表，如下右图所示，链表中存有两个环，下左图所示为只有一个表头结点的空的双向循环链表。

（4）在双向链表中，有些操作仅需涉及一个方向的指针，则它们的算法描述和线性链表相同，但在插入、删除时有很大的不同，在双向链表中进行插入（下左图）、删除（下右图）时需同时修改两个方向上的指针（只要会改变链表存储情况的操作，基本都需要修改两个方向的指针）。

①双向链表（非循环列表）的插入操作：

Status DuListInsert(DuLinkList* L, int i, ElemType e)  //插入
{
	DuLinkList p;
	p = *L;
	int j = 0;
	while (p && (j < i - 1))  //查找第i-1个结点，p指向该结点
	{
		p = p->next;
		j++;
	}
	if (!p || (j > i - 1))  //i值不合法
	{
		return ERROR;
	}
	DuLinkList s = (DuLinkList)malloc(sizeof(DuLNode));  //生成新结点*s
	s->data = e;        //将结点*s的数据域置为e
	s->prior = p;
	s->next = p->next;
	p->next = s;
	s->next->prior = s;

	return OK;
}

②双向链表（非循环列表）的删除操作：

Status DuListDelete(DuLinkList* L, int i)  //删除
{
	DuLinkList p;
	p = *L;
	int j = 0;
	while (p->next && (j < i - 1))  //查找第i-1个结点，p指向该结点
	{
		p = p->next;
		j++;
	}
	if (!p->next || (j > i - 1))  //i值不合法
	{
		return ERROR;
	}
	DuLinkList q = p->next;
	p->next = p->next->next;
	p->next->prior = p;
	free(q);
	return OK;
}

四、顺序表和链表的比较

1、空间性能的比较

（1）存储空间的分配：

顺序表的存储空间必须预先分配，元素个数有一定限制，易造成存储空间浪费或空间溢出现象；链表不需要为其预先分配空间，只要内存空间允许，链表中的元素个数就没有限制。基于此，当线性表的长度变化较大，难以预估存储规模时，宜采用链表作为存储结构。

（2）存储密度的大小：

链表的每个结点除了设置数据域用来存储数据元素外，还要额外设置指针域，用来存储指示元素之间逻辑关系的指针，从存储密度上来讲，这是不经济的。所谓存储密度是指数据元素本身所占用的存储量和整个结点结构所占用的存储量之比，存储密度越大，存储空间的利用率就越高。

2、时间性能的比较

（1）存取元素的效率：

顺序表是由数组实现的，它是一种随机存取结构，指定任意一个位置序号，都可以在O(1)时间内直接存取该位置上的元素，即取值操作的效率高；而链表是一种顺序存取结构，按位置访问链表中第i个元素时，只能从表头开始依次向后遍历链表，直到找到第i个位置上的元素，时同复杂度为O(n)，即取值操作的效率低。基于此，若线性表的主要操作是和元素位置紧密相关的一类取值操作，很少做插入或删除时，宜采用顺序表作为存储结构。

（2）插入和删除操作的效率：

对于链表，在确定插入或删除的位置后，插入或删除操作无须移动数据，只需要修改指针，时间复杂度为O(1)；而对于顺序表，进行插入或删除时，平均要移动表中近一半的结点，时间复杂度为O(n)，尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。基于此，对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构。

（3）单链表、循环链表和双向链表的比较：

链表名称

操作名称

查找表头结点

查找表尾结点

查找结点*p的前驱节点

带头结点的单链表L

L->next

时间复杂度O(1)

从L->next依次向后遍历

时间复杂度O(n)

通过p->next无法找到其前驱

带头结点仅设头指针L的循环单链表

L->next

时间复杂度O(1)

从L->next依次向后遍历

时间复杂度O(n)

通过p->next可以找到其前驱

时间复杂度O(n)

带头结点仅设尾指针L的循环单链表

R->next->next

时间复杂度O(1)

通过p->next可以找到其前驱

时间复杂度O(n)

带头结点的双向循环链表L

L->next

时间复杂度O(1)

L->prior

时间复杂度O(1)

p->prior

时间复杂度O(1)

五、算法设计举例

1、例1

（1）问题描述：已知长度为n的线性表A采用顺序存储结构，请设计一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法可删除线性表中所有值为item的数据元素。

（2）代码：

#define MAXSIZE 100    //数组空间大小

typedef int ElemType;  //以整型为例
typedef struct SqList
{
	ElemType* elem;  //存储空间的基地址
	int length;      //当前长度
}SqList;

void DeleteItem(SqList* L, ElemType item)
{
	int k = 0;
	for (int i = 0; i < L->length; i++)
	{
		if (L->elem[i] != item)
		{
			L->elem[k] = L->elem[i];
			k++;
		}
	}
	L->length = k;
}

2、例2

（1）问题描述：将两个递增的有序链表合并为一个递增的有序链表，要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间，表中不允许有重复的数据。

（2）代码：

typedef int ElemType;  //以整型为例
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LNode, *LinkList;

void List_work(LinkList* LA, LinkList* LB, LinkList* LC)
{
	LinkList pa, pb;
	pa = (*LA)->next;
	pb = (*LB)->next;
	*LC = *LA;
	LinkList pc = (*LC);
	while (pa != NULL)
	{
		if (pa->data > pb->data)
		{
			pc->next = pb;  //将pb所指结点链接到pc所指结点之后
			pc = pb;        //pc指向pb
			pb = pb->next;  //pb指向下一结点
		}
		else if (pa->data < pb->data)
		{
			pc->next = pa;  //将pa所指结点链接到pc所指结点之后
			pc = pa;        //pc指向pa
			pa = pa->next;  //pa指向下一结点
		}
		else if (pa->data == pb->data)
		{
			pc->next = pa;
			pc = pa;
			pa = pa->next;
			LinkList q = pb;
			pb = pb->next;
			free(q);
		}
	}
	if (pa == NULL)
	{
		pc->next = pb;
	}
	else
	{
		pc->next = pa;
	}
	free(*LB);
}

3、例3

（1）问题描述：将两个非递减的有序链表合并为一个非递减的有序链表，要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间，表中允许有重复的数据。

（2）代码：

typedef int ElemType;  //以整型为例
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LNode, *LinkList;

void List_work(LinkList* LA, LinkList* LB, LinkList* LC)
{
	LinkList pa, pb;
	pa = (*LA)->next;
	pb = (*LB)->next;
	*LC = *LA;
	LinkList pc = (*LC);
	pc->next = NULL;
	while (pa&&pb)
	{
		if (pa->data > pb->data)
		{
			pc->next = pb;  //将pb所指结点链接到pc所指结点之后
			pc = pb;        //pc指向pb
			pb = pb->next;  //pb指向下一结点
		}
		else
		{
			pc->next = pa;  //将pa所指结点链接到pc所指结点之后
			pc = pa;        //pc指向pa
			pa = pa->next;  //pa指向下一结点
		}
	}
	if (pa == NULL)
	{
		pc->next = pb;
	}
	else
	{
		pc->next = pa;
	}
	free(*LB);
}

4、例4

（1）问题描述：已知两个链表A和B分别表示两个集合，其元素递增排列，设计一个算法用于求出A和B的交集，并将结果存放在A链表中。

（2）代码：

typedef int ElemType;  //以整型为例
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LNode, *LinkList;

void List_work(LinkList* LA, LinkList LB)
{
	LinkList pa, pb;
	pa = (*LA)->next;
	pb = LB->next;
	LinkList pc = *LA;
	while (pa&&pb)
	{
		if (pa->data == pb->data)
		{
			pc->next = pa;
			pc = pc->next;
			pa = pa->next;
			pb = pb->next;
		}
		else if (pa->data > pb->data)
		{
			pb = pb->next;
		}
		else if (pa->data < pb->data)
		{
			LinkList q = pa;
			pa = pa->next;
			free(q);
		}
	}
	pc->next = NULL;
	while (pa)
	{
		LinkList q = pa;
		pa = pa->next;
		free(q);
	}
}

5、例5

（1）问题描述：已知两个链表A和B分别表示两个集合，其元素递增排列，设计一个算法用于求出A和B的差集（仅由在A中出现而不在B中出现的元素所构成的集合），并将结果以同样的形式存储，同时返回该集合的元素个数。

（2）代码：

typedef int ElemType;  //以整型为例
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LNode, *LinkList;

int List_work(LinkList* LA, LinkList* LB, LinkList* LC)
{
	LinkList pa, pb;
	pa = (*LA)->next;
	pb = (*LB)->next;
	LinkList pc = (*LC);
	pc->next = NULL;
	int count = 0;
	while (pa&&pb)
	{
		if (pa->data > pb->data)
		{
			pb = pb->next;
		}
		else if (pa->data < pb->data)
		{
			pa = pa->next;
		}
		else if (pa->data == pb->data)
		{
			LinkList q = (LinkList)malloc(sizeof(LNode));
			pc->next = q;
			q->data = pa->data;
			q->next = NULL;
			pc = pc->next;
			pa = pa->next;
			pb = pb->next;
			count++;
		}
	}
	return count;
}

6、例6

（1）问题描述：设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B和C，其中B表的结点为A表中值小于0的结点，而C表的结点为A表中值大于0的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）。

（2）代码：

typedef int ElemType;  //以整型为例
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LNode, *LinkList;

void List_work(LinkList* LA, LinkList* LB, LinkList* LC)
{
	LinkList pa, pb, pc;
	pa = (*LA)->next;
	pb = (*LB);
	pc = (*LC);
	while (pa)
	{
		if (pa->data > 0)
		{
			pb->next = pa;
			pb = pb->next;
			pa = pa->next;
		}
		else if (pa->data < 0)
		{
			pc->next = pa;
			pc = pc->next;
			pa = pa->next;
		}
		else if (pa->data == 0)
		{
			LinkList q = pa;
			pa = pa->next;
			free(q);
		}
	}
	pb->next = NULL;
	pc->next = NULL;
}

7、例7

（1）问题描述：设计一个算法，通过一趟遍历确定长度为n的单链表值中最大的结点。

（2）代码：

typedef int ElemType;  //以整型为例
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LNode, *LinkList;

void List_work(LinkList LA, ElemType *e, int *i)
{
	ElemType temp = LA->next->data;
	LinkList p = LA->next;
	int flag = 1;
	int j = 0;
	while (p)
	{
		j++;
		if (p->data > temp)
		{
			temp = p->data;
			flag = j;
		}
		p = p->next;
	}
	*e = temp;   //返回最大值
	*i = flag;   //返回最大值的位置
}

8、例8

（1）问题描述：设计一个算法，将链表中所有结点（头结点除外）的链接方向“原地”旋转，即要求仅利用原表的存储空间。

（2）代码：

typedef int ElemType;  //以整型为例
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LNode, *LinkList;

void List_work(LinkList *LA)
{
	LinkList p1 = (*LA)->next;  //p指向首元结点
	LinkList p2;                //用于记录原本*p1的后继
	(*LA)->next = NULL;         //头结点的指针域置为空
	while (p1)
	{
		p2 = p1->next;
		p1->next = (*LA)->next;
		(*LA)->next = p1;
		p1 = p2;
	}
}

9、例9

（1）问题描述：设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素。

（2）代码：

typedef int ElemType;  //以整型为例
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LNode, *LinkList;

void List_work(LinkList *LA, ElemType mink, ElemType maxk)
{
	LinkList p = (*LA);
	while (p->next)
	{
		LinkList t = p->next;
		if (t->data > mink && t->data < maxk)
		{
			LinkList q = t;
			p->next = t->next;
			free(q);
		}
		else
		{
			p = p->next;
		}
	}
}

10、例10

（1）问题描述：已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，设计算法交换p所指向的结点及其前驱结点的顺序。

（2）代码：

typedef int ElemType;  //以整型为例
typedef struct DuLNode
{
	ElemType data;
	struct DuLNode *prior;  //指向直接前驱
	struct DuLNode *next;   //指向直接后继
}DuLNode, *DuLinkList;

void Exchange(DuLinkList p)
{
	DuLinkList q;
	q = p->prior;
	q->prior->next = p;
	q->next = p->next;
	p->next = q;
	p->prior = q->prior;
	q->next->prior = q;
	q->prior = p;
}

码农公寓

一、线性表的定义和特点

二、线性表的顺序表示和实现

1、线性表的顺序表示

2、顺序表中基本操作的实现

3、顺序表的优缺点

三、线性表的链式表示和实现

1、单链表的定义和表示

2、单链表中基本操作的实现

3、循环链表

4、双向链表

四、顺序表和链表的比较

1、空间性能的比较

2、时间性能的比较

五、算法设计举例

1、例1

2、例2

3、例3

4、例4

5、例5

6、例6

7、例7

8、例8

9、例9

10、例10

相关文章