[数据结构与算法]数据结构入门2-1（线性表）

目录

注：

线性表的定义和特点

线性表的类型定义

线性表的顺序表示和实现

线性表的顺序存储表示

顺序表中基本操作的实现

线性表的链式表示和实现

单链表的定义和表示

单链表基本操作的实现

循环链表

双向链表

顺序表和链表的比较

空间性能的比较

时间性能的比较

注：

??????? 本笔记参考：《数据结构（C语言版）（第2版）》

??????? 线性表属于线性结构，是最基本且最常用的一种线性结构，同时也是其他数据结构的基础。尤其是单链表，是贯穿整个数据结构课程的基本技术。

线性表的定义和特点

????????线性表的例子，如26个字母的字母表：(A, B, C, ..., Z)。表中的元素就是单个字母。如果是更复杂的线性表，一个数据元素可以包含若干个数据项。

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

??????? 由n（n≥0）个数据特性相同的元素构成的有限序列称为线性表。

??????? 线性表中元素的个数n（n≥0）定义为线性表的长度，n=0时被称为空表。

非空线性表或线性结构的特点是：

1. 存在唯一一个被称为“第一个”的数据元素；
2. 存在唯一一个被称为“最后一个”的数据元素；
3. 除第一个外，结构中的每一个元素均只有一个先驱；
4. 除最后一个外，结构中的每一个数据元素均只有一个后继。

??????? 在现实生活中，类似于图书信息管理问题，这类问题包含由n个数据特性相同的元素，可以表示为线性表。这些数据类型可以是简单数据类型，也可以是复杂数据类型，这些问题涉及的操作有很大的相似性，如果为每一个问题单独编写程序，不免过于麻烦。

??????? 为了解决这类问题，最好的办法就是从具体应用中抽象出共性的逻辑结构和基本操作（即抽象数据类型），然后进行编程实现。

线性表的类型定义

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

注：

1. 抽象数据模型仅是一个模型的定义，不涉及模型的具体实现。
2. 上述模型给出的操作只是基本操作，这些基本操作还可以构成更复杂的操作。
3. 对于不同的操作，基本操作的接口可能不同。
4. 有抽象数据类型定义的线性表，可以根据实际所采用的存储结构形式，进行具体的表示和实现。

线性表的顺序表示和实现

线性表的顺序存储表示

??????? 线性表的顺序表示：指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表。

??????? 顺序表的特点：逻辑上相邻的数据元素，其物理次序也是相邻的。

????????实际上，只要确定了线性表的起始位置，线性表中的任一数据都可以被随机存取。因此，线性表的顺序存储结构是一种随机存取的存储结构。

??????? 通常，我们用高级设计语言中的数组描述数据结构中的顺序存储结构。

??????? 因为线性表的长度是可变的，所以在C语言中，我们通过动态内存分配的方式描述线性表，此处先描述线性表的存储结构：

#define MAXSIZE 100
typedef struct
{
    ElemType *elem;     //存储空间的基地址。（ElemType可以是int、char乃至struct等类型）
    int length;         //当前长度
}SqList;                //顺序表的结构类型为SqList

??????? 在这之后，通过动态内存分配（在之后详细记录）可以得到一个 数组指针elem指向顺序表的基地址，数组空间大小为MAXSIZE的数组空间。

??????? 接下来先讨论在应对稀疏性多项式数据式，顺序存储分配的情况：

#define MAXSIZE 100
typedef struct
{
    float coef;        //存储系数
    int expn;          //存储指数
}Polynomial;
typedef struct
{
    Polynomial *elem;
    int length;
}SqList;

??????? 接下来通过 SqList L; 将L定义成SqList类型的变量，就可以通过L.elem[i-1]访问位置序号为i的图书记录。

顺序表中基本操作的实现

??????? 接下来，我们可以通过返回length的值实现求表的长度，通过判断length的值是否为0判断表是否为空，且这些操作算法的时间复杂度都可以是O(1)。

1. 初始化

??????? 以下代码涉及C++语法，需要先行了解C++中关于引用传入函数参数的操作。这里稍微解释需要用到的知识：

??????? 通过类似于以下InitList函数中 SqList& L 中的 &操作符 ，可以较为便利地传入参数，这种操作方式下，函数内部的 L 的地址和引用函数中 L 原本的地址是一致的。

#include<iostream>
#define MAXSIZE 100
#define Status int
//#define ElemType int
#define OK 1

typedef struct
{
    //……
}SqList;

Status InitList(SqList& L)          
{//创建空的顺序表L
    L.elem = new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
    if (!L.elem)
        exit(OVERFLOW);             //存储空间分配失败
    L.length = 0;
    return OK;
}

????????上述代码完成的操作有：

1. 分配预定义大小的数组空间。（此时elem指向这段空间的基地址）
2. 将表的当前长度设为0。

????????通过动态分配，我们可以更有效率地使用空间，当不需要线性表或者需要缩小线性表时，我们可以较为轻松地销毁并释放存储空间。

2. 取值

#include<iostream>
#define MAXSIZE 100
#define Status int
#define ElemType int
#define OK 1
#define ERROR 0

//省略中间的函数

Status GetElem(SqList L, int i, ElemType& e)
{
    if (i < 1 || i > L.length)      //判断i值是否合理，若不合理，返回ERROR
        return ERROR;
    e = L.elem[i - 1];              //让e存储elem第i-1个数据元素
    return OK;
}

这一步的时间复杂度为 O(1) 。

??????? 在这一步需要完成的操作是：

1. 判断指定的位置序号i是否合理（1≤i≤L.length），若不合理，返回ERROR。
2. 若i值合理，进行上述赋值，通过e返回第i个数据元素的值。

3. 查找

#include<iostream>
#define MAXSIZE 100
#define Status int
#define ElemType int
#define OK 1
#define ERROR 0

//省略中间的函数

int LocateElem(SqList L, ElemType e)
{//在顺序表中查找值为e的数据元素，返回其序号
    int i = 0;
    for (i = 0; i < L.length; i++)
    {
        if (L.elem[i] == e)
            return i + 1;           //查找成功，返回 下标i+1
    }
    return 0;                       //查找失败，返回0
}

??????? 还是先解释算法步骤：

1. 从第一个元素开始找值与e相同的元素L.elem[i]，找到，返回 下标+1；
2. 找不到，认为查找失败，返回0。

??????? 在查找时，为确定元素在顺序表中的位置，需要和给定值进行比较的数据元素的期望值称为查找算法在查找成功时的平均查找长度（Average Search Length, ASL）。

【算法分析】

??????? 在长度为n的线性表中，查找成功时的平均查找长度为：

??????? 假设每个元素的查找概率相等，即

则可以把原式简化为：

从这个式子可以看出，这个算法的平均时间复杂度为 O(n) 。

4. 插入

在线性表的顺序存储结构中，逻辑上相邻的数据元素在物理位置上也是相邻的。

#include<iostream>
#define MAXSIZE 100
#define Status int
#define ElemType int
#define OK 1
#define ERROR 0

//省略中间的函数

Status ListInsert(SqList& L, int i, ElemType e)
{//顺序表L中第i个位置插入新的元素e，i值的合法范围是1≤i≤L.length+1
	if ((i < 1) || (i > L.length + 1))
		return ERROR;				//i值不合法
	if (L.length == MAXSIZE)		//讨论当前存储空间是否已满
		return ERROR;

	int j = 0;
	for (j = L.length - 1; j >= i - 1; j--)
		L.elem[j + 1] = L.elem[j];	//插入位置及元素后移

	L.elem[i - 1] = e;				//将新元素e放入第i个位置
	++L.length;						//表长加1
	return OK;
}

????????注意：这个算法没有处理表的动态扩充，因此当表已经达到预设的最大空间时，不能再插入元素。

?例如：

一般情况下，要在第i（1≤i≤n）个位置插入一个元素时，需从最后一个元素即第n个元素开始，依次向后移动一个位置，总共移动 n-i+1 个元素。

??????? 讨论算法步骤：

1. 判断插入位置i是否为合法（i值合法范围是 1 ≤ i ≤ n+1），不合法返回ERROR；
2. 判断顺序表存储空间是否已满，若已满，返回ERROR；
3. 将第n个至第i个位置的元素依次向后移一位，空出第i个位置（该算法下 i = n + 1 时无需移动）；
4. 将插入的新元素e放入第i个位置；
5. 表长加1。

5. 删除

#include<iostream>
#define MAXSIZE 100
#define Status int
#define ElemType int
#define OK 1
#define ERROR 0

//省略中间的函数

Status ListDelete(SqList& L, int i)
{//顺序表L中删除第i个元素，i值的合法范围是1<=i<=L.length
	if ((i < 1) || (i > L.length))	//i值不合法
		return ERROR;

	int j = 0;
	for (j = i; j < L.length; j++)
		L.elem[j - 1] = L.elem[j];
	--L.length;
	return OK;						//表长减1
}

??????? 先看算法步骤：

1. 判断i的位置是否合法，不合法返回ERROR；
2. 将第i+1个至第n个元素依次向前移动一个位置（i = n 时无需移动）；
3. 表长减1。

【算法分析】

??????? 在删除操作中，时间的耗费主要体现在移动元素上，而移动元素的个数取决于决定删除的元素的位置。故有：

??????? 同样地，假设在线性表的任何位置删除元素的概率是相等的，有：

??????? 可得：

??????? 可知，该算法的平均时间复，杂度也是O(n)。

总结

??????? 线性表存储简单，外表直观。但是只要涉及元素移动，往往就是大量元素需要一起移动的情况。又因为数组相对固定，当表内元素较多，操作较大时，操作就会相对复杂，且造成存储空间的浪费。为了与之互补，接下来就介绍另一种线性表的表示方法——链式存储结构。

线性表的链式表示和实现

单链表的定义和表示

??????? 特点：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

??????? 因为上述特点，链式存储结构为了保证数据元素之间的逻辑关系，还需要在每一个数据元素中放入一个指示其直接后继的信息（即直接后继的存储位置）。这部分信息和数据元素本身的信息组成了存储印象，即结点。

??????? 结点包括了两个域：

1. 数据域：存储数据元素信息的域。
2. 指针域：存储直接后继位置的域。（存储指针或链）

??????? n个结点可以链接成一个链表，这就是线性表的链式存储结构。

????????一个链表中的每一个结点只包含一个指针域的，我们称这个链表为线性链表或单链表。由此扩展，根据链表中所含的指针个数、指针指向和指针连接方式，可以将链表分为单链表、循环链表、双向链表]? 左边的链表通常被使用在线性表的链式存储结构中，右边则多用在非线性结构里? [二叉链表、十字链表、邻链表、邻接多重表等。

??????? 在单链表中，整个链表的存取必须从头指针开始，最后一个指针为空（NULL）：

??????? 这些数据元素在其存储的物理位置上不要求紧邻，数据元素之间的逻辑关系是通过指针指示的（指针为数据元素之间的逻辑关系的映像）。这种存储结构被称为链式映像或者非顺序映像。

??????? 在这种结构中，关心的只是数据元素之间的逻辑关系，实际位置就显得不那么重要了。

??????? 接下来通过C语言的“结构指针”描述单链表的头指针特点：

#define ElemType int

typedef struct LNode 
{
	ElemType data;		//节点的数据域
	struct LNode* next;	//节点的指针域
}LNode,*LinkList;       //LinkList为指向结构体LNode的指针类型

【代码解析】

??????? 在上述代码中：

• ElemType是通用类型标识符；
• next是存储后续结点位置的指针域，其类型为指向结点的指针类型。

??????? 在上述代码中，对同一个结构体指针类型起了两个名称，LinkList与LNode*，两者本质上是一样的。

习惯上：

• 用LinkList定义单链表，强调定义的是某个单链表的头指针；
• 用LNode*定义指向单链表中任意结点的指针变量。

??????? 例如：定义 LinkList L ，则L为单链表的头指针，若定义LNode* p，则p为指向单链表中某个结点的指针，*p代表该结点。

??????? 单链表是由表头指针位移确定的，因此，若头指针名为L，一般简称该链表为表L。

注意：

??????? 指针变量和结点变量是两个不同的概念，现在定义LinkList p或LNode* p：

• 则p就是指向某结点的指针变量，表示该结点的地址；
• *p为对应的结点变量，表示该结点的名称。

??????? 一般情况下，会在单链表的第一个结点之前附设应该结点，称之为头结点：

??????? 首元结点、头节点和头指针的概念：

• 首元节点：是链表中存储第一个数据元素的结点。在上图中所示的节点“PQR”；
• 头节点：是在首元节点之前附设的一个节点，其指针域指向首元节点。头节点的数据域可以不存储任何信息，也可以存储域数据元素类型相同的其他附加信息。例如，当数据元素为整数型是，头节点的数据域中可存放该线性表的长度。
• 头指针：是指向链表中的第一个结点的指针。① 若链表设有头结点，则头指针所指结点为线性表的头结点；② 若链表不设头结点，则头指针所指结点为该线性表的首元结点。

??????? 链表增加头结点的作用：

??????? （1）便于首元结点的处理

?????????增加了头结点后，首元结点的地址保存在头节点的指针域中。此时对于链表中的第一个数据元素的操作与其他数据元素相同，无需特殊处理。

??????? （2）便于空表和非空表的统一操作

??????? ① 当链表不设头结点时，假设L为单链表的头指针，它应该指向首元结点。若出现空表（长度n为0），则L指针为空（判断空表的条件：L==NULL）。

??????? ② 增加头结点后，无论链表是否为空，头指针都是指向头结点的非空指针：

若为非空单链表，头指针指向头结点。若为空表，则头结点的指针域为空（判断空表的条件：L->next == NULL）。

??????? 单链表作为非随机存取的存储结构，要取得第i个数据元素就必须从头指针出发顺链进行寻找，也称为顺序存取的存取结构。其基本操作的实现是不同于顺序表的。

单链表基本操作的实现

前提：

#include<iostream>
#define Status int
#define ElemType int
#define OK 1
#define ERROR 0
using namespace std;

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

1. 初始化

????????此处依旧使用C++语法中的[new]进行空间开辟，在C语言中，可以考虑使用malloc函数进行此操作。

Status InitList(LinkList& L)
{//构建一个空的单链表L
	L = new LNode;				//生成新结点作为头结点，用头指针L指向头结点
	L->next = NULL;				//头结点的指针域置空
	return OK;
}

2. 取值

??????? 链表只能从它的首元结点出发，顺着链域next逐个结点向下访问。

Status GetElem(LinkList L, int i, ElemType& e)
{//在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值
	LNode* p = L->next;
	int j = 1;					//初始化，p指向首元结点，计算器j初值赋为1

	while (p && j < i)			//顺链向后扫描，直到p为空或p指向第i个元素
	{
		p = p->next;
		++j;
	}
	if (!p || j > i)			//i值不合法（i > n 或 i <= 0）
		return ERROR;
	e = p->data;				//取第i个结点的数据域
	return OK;
}

注：其中n为链表最大长度。

【算法分析】

??????? 该算法的基本操作是比较 j 和 i 并后移指针p，while循环中的语句频度与 位置i 有关。我们可以将此处可能发送的情况大体分为两种：

1. 若1≤i≤n，则频度为 i-1 ，一定能成功；
2. 若i>n，则频度为n，取值失败。

??????? 综上所述，该算法的最坏时间复杂度为O(n)。

??????? 继而，假设每个位置上元素的取值概率相等，则有

由式子可知，单链表的取值算法的平均时间复杂度为O(n)。

3. 查找

LNode* LocateElem(LinkList L, ElemType e)
{//在带头结点的单链表L中查找值为e的元素
	LNode* p = L->next;			//初始化，p指向首元结点

	while (p && p->data != e)	//顺链域向后扫描，直到 p为空 或者 找到目标
		p = p->next;
	return p;					//查找成功返回值为e的结点地址p，查找失败时p = NULL
}

??????? 该算法的指向时间和待查找的e值有关，其平均时间复杂度分析和上面的取值算法接近，也是O(n)。

4. 插入

Status ListInsert(LinkList& L, int i, ElemType e) 
{//在带头结点的单链表L中第i个位置插入值为e的新结点
	LNode* p = L;
	int j = 0;
	
	while (p && (j < i - 1))	//查找第i-1个结点
	{
		p = p->next;
		++j;
	}
	if (!p || j > i - 1)		// i>n+1 或者 i<1
		return ERROR;
	LinkList s = new LNode;
	s->data = e;				//将结点*s的数据域置为e
	s->next = p->next;
	p->next = s;				//将结点*p的指针域指向结点*s
	return OK;
}

??????? 和顺序表一样，有n个结点的链表中，插入操作合法的插入位置有n+1个，即 1≤i≤n+1 。当 i=n+1 时，新结点插在链表尾部。

【思路说明】

??????? 假设要在单链表的两个数据元素a和b之间插入一个数据元素x，已知p为其单链表存储结构中指向结点a的指针。再假设s是指向结点x的指针，即有：

???????? 最终的目标是实现3个元素a、b和x之间逻辑关系的变化。

【算法分析】

??????? 单链表的插入操作不用移动元素，但是平均时间复杂度还是O(n)。因为，为了在第i个结点之前插入一个新结点，必须首先找到第 i-1 个结点。这就和上述的算法类似了。

5. 删除

Status ListDelete(LinkList& L, int i)
{//在带头结点的单链表中，删除第i个元素
	LinkList 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>n 或 i<1 时，删除位置不合理
		return ERROR;
	LinkList q = p->next;				//临时保存被删结点的地址已被释放
	q = p->next;
	p->next = q->next;					//改变删除结点前驱结点的指针域
	delete q;							//释放删除结点的空间
	return OK;
}

??????? 和插入不同，在删除结点时，除了要修改结点a的指针域外，还要释放结点b所占的空间，所以在修改指针前，应该再引入另一个指针q，临时保存结点b的地址以备释放。

一点细节

1. 在删除算法中，循环条件是：(p->next && (j < i - 1)) ；
2. 在插入算法中，循环条件是：(p && (j < i - 1)) 。

??????? 之所以这里会出现这种情况，是因为插入操作中合法的插入位置有n+1个，而删除操作中合法的删除位置只有n个。如果使用与插入操作相同的循环条件，会出现引用空指针的情况，使删除操作失败。

【算法分析】

??????? 类似于插入算法，删除算法时间复杂度亦为O(n)。

6. 创建单链表

??????? 作为一种动态结构，链表所占的空间不需要预先分配划定，而是由系统按需即使生成。因此，建立线性表的链式存储结构的过程就是一个动态生成链表的过程。

??????? 根据结点插入位置的不同，链表的创建方法可分为前插法和后插法。

（1）前插法

??????? 这种方法是通过将新结点逐个插入链表的头部（头结点之后）来创建链表。每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后。

void GreateList_H(LinkList& L, int n)
{//逆位序输入n个元素的值，建立带表头结点的单链表
	L = new LNode;
	L->next = NULL;				//先建立一个带头结点的空链表
	int i = 0;
	for ( i = 0; i < n; ++i)
	{
		LinkList p = new LNode;	//生成新结点*p
		cin >> p->data;			//输入元素值赋给新结点*p的数据域
		p->next = L->next;
		L->next = p;			//将新结点*p插入到头结点之后
	}
}

分析：

??????? 因为每次插入都在链表的头部进行，所以应该是逆位序输入数据，依次输入e、d、c、b、a，输入顺序和线性表中的逻辑顺序是相反的。

??????? 显然，该算法的时间复杂度是O(n)。

（2）后插法

??????? 在后插法的创建过程中，读入数据的顺序和线性表中的逻辑顺序是相同的。

void GreateList_R(LinkList& L, int n)
{//正位序输入n个元素的值，建立代表头结点的单链表L
	L = new LNode;
	L->next = NULL;				//先建立一个带头结点的空链表
	LinkList r = L;				//尾指针r指向头结点
	int i = 0;
	for (i = 0; i < n; i++)
	{
		LNode* p = new LNode;
		cin >> p->data;			//输入元素值赋给新结点*p的数据域
		p->next = NULL;
		r->next = p;			//将新结点*p插入尾指针*r之后
		r = p;					//r指向新的尾结点*p
	}
}

??????? 这种算的的时间复杂度亦是O(n)。

循环链表

??????? 循环链表（Circular Linked List）是另一种形式的链式存储结构。这种链表的特点是：

????????表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点。

类似地，还可以有多重链的循环列表。

??????? 循环单链表的操作和单链表基本一致，差别仅在于：当链表遍历时，判别当前指针p是否指向表尾结点的终止条件不同。

• 在单链表中，判别条件是 p != NULL 或者 p->next != NULL ；
• 在循环单链表中，判别条件是 p != L 或者 p->next != L 。

??????? 在某些情况下，循环链表只设置尾指针而不设置头指针。譬如：

????????在合并两个循环链表时，如果不设置头指针，那么在合并的过程中就可以省去处理第二个链表头指针的步骤，使操作得到简化。

??????? 这种操作的时间复杂度为O(1)。

双向链表

??????? 在单链表中，由于其查找方向的单一，查找直接后继结点的指向时间为O(1)，查找直接前驱的执行时间为O(n)。为了克服这种缺点，就要提到双向链表（Double Linked List）。

??????? 双向链表的结点中有两个指针域，一个指向直接后继，一个指向直接前驱，接下来用C语言进行描述：

#define ElemType int

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

??????? 当然，和单链表类似，双向链表也可以有循环表，此时链表中存在两个环：

??????? 在双向链表中，设d为指向表中某一结点的指针（即d为DuLinkList型变量），则有：

????????????????????????d->next->prior = d->prior->next = d

这就可以看出这种结构的特性。

??????? 在双向链表中，执行插入、删除操作和线性链表有较大不同：在插入结点时，双向链表需要修改四个指针，在删除结点时需要修改两个指针。两者的时间复杂度都是O(n)。

??????? 接下来对上述操作进行描述。先看前提：

#include<iostream>
#define ElemType int
#define Status int
#define ERROR 0
#define OK 1

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

DuLinkList GetElem_DuL(DuLinkList L, int i)
{//在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值
	DuLNode* p = L->next;
	int j = 1;					//初始化，p指向首元结点，计算器j初值赋为1

	while (p && j < i)			//顺链向后扫描，直到p为空或p指向第i个元素
	{
		p = p->next;
		++j;
	}
	if (!p || j > i)			//i值不合法（i > n 或 i <= 0）
		return NULL;
	return p;
}

插入

Status ListInsert_Dul(DuLinkList& L, int i, ElemType e)
{//在带头结点的双向链表L中第i个位置之前插入元素e
	DuLinkList p;
	if (!(p = GetElem_DuL(L, i)))		//在L中确定第i个元素的位置指针p
		return ERROR;
	DuLinkList s = new DuLNode;			//生成新结点*s
	s->data = e;
	s->prior = p->prior;				//将结点*s插入L中，此处对应上图①
	p->prior->next = s;					//此处对应上图②
	s->next = p;						//此处对应上图③
	p->prior = s;						//此处对应上图④
	return OK;
}

删除

Status ListDelete_DuL(DuLinkList& L, int i)
{//删除带头结点的双向链表L中的第i个元素
	DuLinkList p;
	if (!(p = GetElem_DuL(L, i)))		//在L中确定第i个元素的位置指针p
		return ERROR;
	p->prior->next = p->next;			//修改被删结点的前驱结点的后继指针，对应图中的①
	p->next->prior = p->prior;			//修改被删结点的后继结点的前驱结点，对应图中的②
	delete p;							//释放被删结点的空间
	return OK;
}

顺序表和链表的比较

??????? 对于这两种各有优缺点的结构，在具体的使用情景中，应该进行具体的分析。通常，我们从空间性能和时间性能这两个方面进行比较。

空间性能的比较

（1）存储空间的分配

??????? 综上所述，在线性表的长度比较大，难以预估存储规模时，适合使用链表作为存储结构。

（2）存储密度的大小

??????? 所谓的存储密度就是：

????????存储密度越大， 存储空间的利用率就越高。

??????? 在链表中，除了用于存储数据的数据域外，还有额外的指针域用来保证元素之间的逻辑关系，从存储密度上来讲，这是不合算的。显然，顺序表的存储密度是大于链表的，而且这种差距会因为数据域的大小不同而发生改变。

??????? 因此，当线性表的长度变化不大，易于事先确定大小时，为了节约空间，适合使用顺序表作为存储结构。

时间性能的比较

（1）存取元素的效率

??????? 综上，若线性表的主要操作是和元素位置紧密相关的这类取值操作，很少做插入或删除时，这种情况适合顺序表存储结构。

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

??????? 故对于需要频繁增删的线性表，宜使用链表作为存储结构。