【algo&ds】2.线性表
ericling 人气:01.线性表
线性表（英语：Linear List）是由n（n≥0）个数据元素（结点）a[0]，a[1]，a[2]…，a[n-1]组成的有限序列。
其中：
- 数据元素的个数n定义为表的长度 = "list".length() （"list".length() = 0（表里没有一个元素）时称为空表）
- 将非空的线性表（n>=1）记作：（a[0]，a[1]，a[2]，…，a[n-1]）
- 数据元素a[i]（0≤i≤n-1）只是个抽象符号，其具体含义在不同情况下可以不同
一个数据元素可以由若干个数据项组成。数据元素称为记录，含有大量记录的线性表又称为文件。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。
2.线性表的存储结构
- 顺序表
- 链表
- 单链表
- 动态单链表
- 静态单链表
- 双链表
- 循环链表
- 单循环链表
- 双循环链表
- 静态链表
- 单链表
3.顺序表
利用数组的连续存储空间顺序存放线性表的各元素
3.1结构体定义
如果需要使用自定义的结构体来维护一个顺序表，通常来讲结构体的元素一般是一个固定大小的数组（可用长度足够大），以及当前数组存放的元素个数，也即数组的长度
typedef struct LNode *List;
struct LNode {
ElementType Data[MAXSIZE];
int Last;//记录顺序表的最后一个元素的下标
} ;
struct LNode L;
List PtrL;访问结构体的成员
- 访问下标为 i 的元素：L.Data[i] 或 PtrL->Data[i]
- 线性表的长度：L.Last+1 或 PtrL->Last+1
- 指针变量PtrL还可以这样访问两个属性
(*PtrL).Data[i]和(*PtrL).Last，不过这种访问方式并不常用
而一般来讲，为了简单，不会去维护这样一个结构体，(因为一旦维护了这个结构体，就需要去封装相应的函数，比如说常见的插入、删除、查找等操作)，而是直接类似下面这样
ElementType data[MaxSize];
int length;定义一个足够大的数组，然后定义一个对应关联的变量来时刻维护数组的长度。
这两种定义方式没有什么区别，一种是把常用操作封装好，方便调用，另一种则是需要时刻自己维护对应的属性。因为顺序表的结构足够简单，所以不定义结构体也是可以的。
3.2顺序表的常见操作
为了方便，这一节内容记录的都是在定义的结构体基础上，封装的常见操作。
1.初始化
List MakeEmpty( ) {
List PtrL;
PtrL = (List )malloc( sizeof(struct LNode) );
PtrL->Last = -1;
return PtrL;
}初始化的顺序表，长度为0，所以Last为-1
2.查找
int Find( ElementType X, List PtrL ) {
int i = 0;
while( i <= PtrL->Last && PtrL->Data[i]!= X )
i++;
if (i > PtrL->Last) return -1; /* 如果没找到，返回-1 */
else return i; /* 找到后返回的是存储位置 */
}查找操作比较简单，从顺序表的第一个元素（下标为0开始）开始遍历。
还有一种更加巧妙一点的实现方式，就是引入哨兵思想。
int Find( ElementType X, List PtrL ) {
PtrL->Data[0] = x;//顺序表第一个元素就是哨兵，赋值为x
int i = PtrL->Last;//从最后一个元素开始遍历
while( PtrL->Data[i]!= X )
i--;
return i;
}这样做的好处很明显，少了边界的判断，可以优化时间复杂度，编码也更加简单。
注意：这里把下标为0的元素设置为哨兵，则要求顺序表从下标为1开始存储。而且，函数如果没有找到，则一定返回i=0
3.插入
看图示应该要注意，移动的方向是从后往前移，如果从前往后移，则Data[i]=Data[i+1]=...=Data[n]，因为后面的元素都被前面移过来的元素给覆盖了。
void Insert( ElementType X, int i, List PtrL ) {
int j;
if ( PtrL->Last == MAXSIZE-1 ) { /* 表空间已满，不能插入*/
printf(＂表满＂);
return;
}
if ( i < 1 || i > PtrL->Last+2) { /*检查插入位置的合法性*/
printf(＂位置不合法＂);
return;
}
for ( j = PtrL->Last; j >= i-1; j-- )
PtrL->Data[j+1] = PtrL->Data[j]; /*将 ai～ an倒序向后移动*/
PtrL->Data[i-1] = X; /*新元素插入*/
PtrL->Last++; /*Last仍指向最后元素*/
return;
}为什么这里需要判断顺序表的空间是否已满？
因为这个数组，是在初始化之后就固定了数组可容纳的元素个数MaxSize，一旦超出，则程序下标就会越界。C++提供了动态数组vector，可以很方便的支持动态扩展数组长度，而且基本的插入删除等操作都封装好了，可以很方便的使用。
4.删除
同样的，需要注意元素移动的方向，如果从后往前移，则最后面的元素会一直覆盖到Data[i]。
void Delete( int i, List PtrL ) {
int j;
if( i < 1 || i > PtrL->Last+1 ) { /*检查空表及删除位置的合法性*/
printf (“不存在第%d个元素”, i );
return ;
}
for ( j = i; j <= PtrL->Last; j++ )
PtrL->Data[j-1] = PtrL->Data[j]; /*将 ai+1～ an顺序向前移动*/
PtrL->Last--; /*Last仍指向最后元素*/
return;
}5.排序
因为排序算法比较多，本文不展开讲解，可以参考以下博文，内容包括了常见的十大排序算法的算法分析，时间复杂度和空间复杂度分析以及c实现和动图图解。
https://www.cnblogs.com/ericling/p/11877219.html
4.链表
不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建立起数据元素之间的逻辑关系。插入、删除不需要移动数据元素，只需要修改“链”。
4.1单链表
typedef struct LNode *List;
struct LNode {
ElementType Data;
List Next;
};
struct Lnode L;
List PtrL;1.求表长
int Length ( List PtrL ) {
List p = PtrL; /* p指向表的第一个结点*/
int j = 0;
while ( p ) {
p = p->Next;
j++; /* 当前p指向的是第 j 个结点*/
}
return j;
}时间复杂度O(n)
2.查找
按序查找
List FindKth( int K, List PtrL ) {
List p = PtrL;
int i = 1;
while (p !=NULL && i < K ) {
p = p->Next;
i++;
}
if ( i == K ) return p;
/* 找到第K个，返回指针 */
else return NULL;
/* 否则返回空 */
}时间复杂度O(n)
按值查找
List Find( ElementType X, List PtrL ) {
List p = PtrL;
while ( p!=NULL && p->Data != X )
p = p->Next;
return p;
}时间复杂度O(n)
3.插入
（1）先构造一个新结点，用s指向；
（2）再找到链表的第 i-1个结点，用p指向；
（3）然后修改指针，插入结点 ( p之后插入新结点是 s)
List Insert( ElementType X, int i, List PtrL ) {
List p, s;
if ( i == 1 ) { /* 新结点插入在表头 */
s = (List)malloc(sizeof(struct LNode)); /*申请、填装结点*/
s->Data = X;
s->Next = PtrL;
return s; /*返回新表头指针*/
}
p = FindKth( i-1, PtrL ); /* 查找第i-1个结点 */
if ( p == NULL ) { /* 第i-1个不存在，不能插入 */
printf("参数i错");
return NULL;
} else {
s = (List)malloc(sizeof(struct LNode)); /*申请、填装结点*/
s->Data = X;
s->Next = p->Next; /*新结点插入在第i-1个结点的后面*/
p->Next = s;
return PtrL;
}
}4.删除
（1）先找到链表的第 i-1个结点，用p指向；
（2）再用指针s指向要被删除的结点（p的下一个结点）;
（3）然后修改指针，删除s所指结点;
（4）最后释放s所指结点的空间。
List Delete( int i, List PtrL ) {
List p, s;
if ( i == 1 ) { /* 若要删除的是表的第一个结点 */
s = PtrL; /*s指向第1个结点*/
if (PtrL!=NULL) PtrL = PtrL->Next; /*从链表中删除*/
else return NULL;
free(s); /*释放被删除结点 */
return PtrL;
}
p = FindKth( i-1, PtrL ); /*查找第i-1个结点*/
if ( p == NULL ) {
printf("第%d个结点不存在", i-1);
return NULL;
} else if ( p->Next == NULL ) {
printf("第%d个结点不存在", i);
return NULL;
} else {
s = p->Next; /*s指向第i个结点*/
p->Next = s->Next; /*从链表中删除*/
free(s); /*释放被删除结点 */
return PtrL;
}
}4.2双链表
双向链表，又称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
typedef struct DuLNode {
ElemType data;
struct DuLNode *prior, *next;
} DuLNode, *DuLinkList;4.3循环链表
4.3.1单循环链表
存储结构和单链表相同。
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
// 设立尾指针的单循环链表的12个基本操作
void InitList(LinkList *L) { // 操作结果：构造一个空的线性表L
*L = (LinkList)malloc(sizeof(struct LNode)); // 产生头结点，并使L指向此头结点
if (!*L) // 存储分配失败
exit(OVERFLOW);
(*L)->next = *L; // 指针域指向头结点
}
void DestroyList(LinkList *L) { // 操作结果：销毁线性表L
LinkList q, p = (*L)->next; // p指向头结点
while (p != *L) { // 没到表尾
q = p->next;
free(p);
p = q;
}
free(*L);
*L = NULL;
}
void ClearList(LinkList *L) /* 改变L */ { // 初始条件：线性表L已存在。操作结果：将L重置为空表
LinkList p, q;
*L = (*L)->next; // L指向头结点
p = (*L)->next; // p指向第一个结点
while (p != *L) { // 没到表尾
q = p->next;
free(p);
p = q;
}
(*L)->next = *L; // 头结点指针域指向自身
}
Status ListEmpty(LinkList L) { // 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE
if (L->next == L) // 空
return TRUE;
else
return FALSE;
}
int ListLength(LinkList L) { // 初始条件：L已存在。操作结果：返回L中数据元素个数
int i = 0;
LinkList p = L->next; // p指向头结点
while (p != L) { // 没到表尾
i++;
p = p->next;
}
return i;
}
Status GetElem(LinkList L, int i, ElemType *e) { // 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
int j = 1; // 初始化，j为计数器
LinkList p = L->next->next; // p指向第一个结点
if (i <= 0 || i > ListLength(L)) // 第i个元素不存在
return ERROR;
while (j < i) { // 顺指针向后查找，直到p指向第i个元素
p = p->next;
j++;
}
*e = p->data; // 取第i个元素
return OK;
}
int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) { // 初始条件：线性表L已存在，compare()是数据元素判定函数
// 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。
// 若这样的数据元素不存在，则返回值为0
int i = 0;
LinkList p = L->next->next; // p指向第一个结点
while (p != L->next) {
i++;
if (compare(p->data, e)) // 满足关系
return i;
p = p->next;
}
return 0;
}
Status PriorElem(LinkList L, ElemType cur_e, ElemType *pre_e) { // 初始条件：线性表L已存在
// 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，
// 否则操作失败，pre_e无定义
LinkList q, p = L->next->next; // p指向第一个结点
q = p->next;
while (q != L->next) { // p没到表尾
if (q->data == cur_e) {
*pre_e = p->data;
return TRUE;
}
p = q;
q = q->next;
}
return FALSE; // 操作失败
}
Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e) { // 初始条件：线性表L已存在
// 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，
// 否则操作失败，next_e无定义
LinkList p = L->next->next; // p指向第一个结点
while (p != L) { // p没到表尾
if (p->data == cur_e) {
*next_e = p->next->data;
return TRUE;
}
p = p->next;
}
return FALSE; // 操作失败
}
Status ListInsert(LinkList *L, int i, ElemType e) /* 改变L */ { // 在L的第i个位置之前插入元素e
LinkList p = (*L)->next, s; // p指向头结点
int j = 0;
if (i <= 0 || i > ListLength(*L) + 1) // 无法在第i个元素之前插入
return ERROR;
while (j < i - 1) { // 寻找第i-1个结点
p = p->next;
j++;
}
s = (LinkList)malloc(sizeof(struct LNode)); // 生成新结点
s->data = e; // 插入L中
s->next = p->next;
p->next = s;
if (p == *L) // 改变尾结点
*L = s;
return OK;
}
Status ListDelete(LinkList *L, int i, ElemType *e) /* 改变L */ { // 删除L的第i个元素，并由e返回其值
LinkList p = (*L)->next, q; // p指向头结点
int j = 0;
if (i <= 0 || i > ListLength(*L)) // 第i个元素不存在
return ERROR;
while (j < i - 1) { // 寻找第i-1个结点
p = p->next;
j++;
}
q = p->next; // q指向待删除结点
p->next = q->next;
*e = q->data;
if (*L == q) // 删除的是表尾元素
*L = p;
free(q); // 释放待删除结点
return OK;
}
void ListTraverse(LinkList L, void(*vi)(ElemType)) { // 初始条件：L已存在。操作结果：依次对L的每个数据元素调用函数vi()
LinkList p = L->next->next; // p指向首元结点
while (p != L->next) { // p不指向头结点
vi(p->data);
p = p->next;
}
printf("\n");
}4.3.2双循环链表
// 线性表的双向链表存储结构
typedef struct DuLNode {
ElemType data;
struct DuLNode *prior, *next;
} DuLNode, *DuLinkList;
// 带头结点的双向循环链表的基本操作(14个)
void InitList(DuLinkList *L) {
// 产生空的双向循环链表L
*L = (DuLinkList)malloc(sizeof(DuLNode));
if (*L)
(*L)->next = (*L)->prior = *L;
else
exit(OVERFLOW);
}
void DestroyList(DuLinkList *L) {
// 操作结果：销毁双向循环链表L
DuLinkList q, p = (*L)->next; // p指向第一个结点
while (p != *L) { // p没到表头
q = p->next;
free(p);
p = q;
}
free(*L);
*L = NULL;
}
void ClearList(DuLinkList L) { // 不改变L
// 初始条件：L已存在。操作结果：将L重置为空表
DuLinkList q, p = L->next; // p指向第一个结点
while (p != L) { // p没到表头
q = p->next;
free(p);
p = q;
}
L->next = L->prior = L; // 头结点的两个指针域均指向自身
}
Status ListEmpty(DuLinkList L) {
// 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE
if (L->next == L && L->prior == L)
return TRUE;
else
return FALSE;
}
int ListLength(DuLinkList L) {
// 初始条件：L已存在。操作结果：返回L中数据元素个数
int i = 0;
DuLinkList p = L->next; // p指向第一个结点
while (p != L) { // p没到表头
i++;
p = p->next;
}
return i;
}
Status GetElem(DuLinkList L, int i, ElemType *e) {
// 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
int j = 1; // j为计数器
DuLinkList p = L->next; // p指向第一个结点
while (p != L && j < i) { // 顺指针向后查找，直到p指向第i个元素或p指向头结点
p = p->next;
j++;
}
if (p == L || j > i) // 第i个元素不存在
return ERROR;
*e = p->data; // 取第i个元素
return OK;
}
int LocateElem(DuLinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) {
// 初始条件：L已存在，compare()是数据元素判定函数
// 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。
// 若这样的数据元素不存在，则返回值为0
int i = 0;
DuLinkList p = L->next; // p指向第1个元素
while (p != L) {
i++;
if (compare(p->data, e)) // 找到这样的数据元素
return i;
p = p->next;
}
return 0;
}
Status PriorElem(DuLinkList L, ElemType cur_e, ElemType *pre_e) {
// 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，
// 否则操作失败，pre_e无定义
DuLinkList p = L->next->next; // p指向第2个元素
while (p != L) { // p没到表头
if (p->data == cur_e) {
*pre_e = p->prior->data;
return TRUE;
}
p = p->next;
}
return FALSE;
}
Status NextElem(DuLinkList L, ElemType cur_e, ElemType *next_e) {
// 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，
// 否则操作失败，next_e无定义
DuLinkList p = L->next->next; // p指向第2个元素
while (p != L) { // p没到表头
if (p->prior->data == cur_e) {
*next_e = p->data;
return TRUE;
}
p = p->next;
}
return FALSE;
}
DuLinkList GetElemP(DuLinkList L, int i) { // 另加
// 在双向链表L中返回第i个元素的地址。i为0，返回头结点的地址。若第i个元素不存在，
// 返回NULL
int j;
DuLinkList p = L; // p指向头结点
if (i < 0 || i > ListLength(L)) // i值不合法
return NULL;
for (j = 1; j <= i; j++)
p = p->next;
return p;
}
Status ListInsert(DuLinkList L, int i, ElemType e) {
// 在带头结点的双链循环线性表L中第i个位置之前插入元素e，i的合法值为1≤i≤表长+1
// 改进算法2.18，否则无法在第表长+1个结点之前插入元素
DuLinkList p, s;
if (i < 1 || i > ListLength(L) + 1) // i值不合法
return ERROR;
p = GetElemP(L, i - 1); // 在L中确定第i个元素前驱的位置指针p
if (!p) // p=NULL,即第i个元素的前驱不存在(设头结点为第1个元素的前驱)
return ERROR;
s = (DuLinkList)malloc(sizeof(DuLNode));
if (!s)
return OVERFLOW;
s->data = e;
s->prior = p; // 在第i-1个元素之后插入
s->next = p->next;
p->next->prior = s;
p->next = s;
return OK;
}
Status ListDelete(DuLinkList L, int i, ElemType *e) {
// 删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长
DuLinkList p;
if (i < 1) // i值不合法
return ERROR;
p = GetElemP(L, i); // 在L中确定第i个元素的位置指针p
if (!p) // p = NULL,即第i个元素不存在
return ERROR;
*e = p->data;
p->prior->next = p->next; // 此处并没有考虑链表头，链表尾
p->next->prior = p->prior;
free(p);
return OK;
}
void ListTraverse(DuLinkList L, void(*visit)(ElemType)) {
// 由双链循环线性表L的头结点出发，正序对每个数据元素调用函数visit()
DuLinkList p = L->next; // p指向头结点
while (p != L) {
visit(p->data);
p = p->next;
}
printf("\n");
}
void ListTraverseBack(DuLinkList L, void(*visit)(ElemType)) {
// 由双链循环线性表L的头结点出发，逆序对每个数据元素调用函数visit()
DuLinkList p = L->prior; // p指向尾结点
while (p != L) {
visit(p->data);
p = p->prior;
}
printf("\n");
}4.4静态链表
前面讲解的都是动态链表，即需要指针来建立结点之间的连接关系。而对有些问题来说结点的地址是比较小的整数（例如5位数的地址），这样就没有必要去建立动态链表，而应使用方便得多的静态链表。
静态链表的实现原理是hash，即通过建立一个结构体数组，并令数组的下标直接表示结点的地址，来达到直接访问数组中的元素就能访问结点的效果。另外，由于结点的访问非常方便，因此静态链表是不需要头结点的。静态链表结点定义的方法如下：
struct Node{
typename data;//数据域
int next;//指针域
}node[size];参考资料：
- 《数据结构和算法》——中国大学MOOC，浙江大学，陈越、何钦铭
- https://zh.wikipedia.org/wiki/%E7%BA%BF%E6%80%A7%E8%A1%A8
- https://zh.wikipedia.org/wiki/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8
- 《算法笔记》
- 《数据结构和算法》-极客时间专栏
加载全部内容