线性表

数据元素之间存在一对一的关系，即前驱和后继的关系，也就是线性关系，所以称之为线性结构。

线性表，简单来说就是一种存储一组元素的结构

1665122136592

例子：一元多项式的表示和相加

定义：线性表是n个数据元素的有限序列。
记作：L= <a1,……,an>存在先后关系
S={a1,……an}， 集合无顺序关系

特点：
⑴ 同一线性表中的元素具有相同特性-数组
⑵ 所有元素具有次序之分-数组可以通过下标访问
⑶ 线性表长度n：元素的个数

顺序表

  • 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
  • 顺序表：可动态增长的数组，要求数据是连续存储的

顺序表分为：

1.静态顺序表：使用定长数组存储元素

1
2
3
4
5
6
#define MAXSIZE 256
typedef struct
{
 ElemType data[MAXSIZE]; // 静态连续存储空间
 int length; // 存储数据元素的个数
}SeqFixedList;

2.使用动态开辟的数组存储元素

1
2
3
4
5
6
7
8
#define LISTINITSIZE 256 // 初次分配空间大小
#define LISTINCREMENT 128 // 空间分配增量大小
typedef struct SeqList
{
 ElemType *pData; // 动态存储空间的基地址
 int length; // 存储数据元素的个数
 int size; // 当前已分配的存储空间大小
}SeqList;

顺序表初始化

1
2
3
4
5
6
7
8
Status InitList( SeqList &L )
{ //初始化顺序表
 L.pData = (ElemType *)malloc(LISTINITSIZE*sizeof(ElemType)); //申请存储空间
 if( L.pData == NULL ) exit(OVERFLOW); // 存储空间申请失败
 L.size = LISTINITSIZE; // 当前已分配的存储空间大小
 L.length = 0; // 存储数据元素个数为零
 return OK;
} // InitList

顺序表销毁

1
2
3
4
5
6
7
8
9
10
11
Status DestroyList( SeqList &L )
{ //销毁顺序表
 if( L.pData ！= NULL ) 
{ 
free(L.pData);
L.pData = NULL;
} 
 L.size = 0; 
 L.length = 0; 
 return OK;
} //DestroyList

顺序表清空

1
2
3
4
5
Status ClearList( SeqList &L )
{ //清空顺序表
 L.length = 0; 
 return OK;
} //ClearList

顺序表元素获取

1
2
3
4
5
6
7
Status GetElem( SeqList L, int i, ElemType &e )
{ //获取顺序表第 i 个数据元素
 if( i<1 || i>L.length ) //参数检查
 return PARA_ERROR;
e = L.pData[i-1]; //获得数据元素
return OK;
} //GetElem

顺序表元素查找

1
2
3
4
5
6
7
8
9
Status LocateElem( SeqList L, ElemType e )
{ //查找元素 e 所在的位置
 for( i=0; i<L.length; i++) 
 {
 if ( L.pData[i] == e )
 return i+1; //查找成功
}
return 0; //查找失败
} //LocateElem

顺序表元素插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Status InsertElem( SeqList &L, int i, ElemType e )
{ //在顺序表第 i 个位置上（逻辑位置）插入数据元素 e
 if( i<1 || i>L.length+1 ) // 参数检查
 return PARA_ERROR;
if( L.length >= L.size ) // 当前存储空间已满，需增加存储空间
{
 newbase = ( ElemType* ) realloc( L.pData, (L.size+LISTINCREMENT)*sizeof(ElemType) ); 
 if ( newbase == NULL ) exit(OVERFLOW); // 内存申请失败
 L.pData = newbase;
 L.size += LISTINCREMENT;
}
// 从最后一个元素开始，直到下标为 i-1（物理位置）的元素，依次向后挪一个位置
for( j = L.length-1; j>=i-1; j-- )
 L.pData[j+1] = L.pData[j];
L.pData[i-1] = e; // 在数组下标为 i-1 的位置（物理位置）上插入元素 e
L.length += 1 ; // 顺序表的长度加 1
return OK;
} //InsertElem

顺序表元素删除

1
2
3
4
5
6
7
8
9
10
11
12
13
Status DeleteElem( SeqList &L, int i，ElemType &e )
{ //将顺序表第 i 个（逻辑位置）元素删除，并用 e 返回
 if( i<1 || i>L.length ) // 参数检查
 return PARA_ERROR;
 e = L.pData[i-1]; // 第 i 个元素存储在数组下标为 i-1 的位置上
 //从第 i 个位置（物理位置）开始到最后一个元素，依次向前挪一个位置
for( j=i; j<=L.length-1; j++) 
 {
 L.pData[j-1] = L.pData[j]; 
}
L.length -= 1; // 顺序表长度减 1
return OK; // 删除成功
} //DeleteElem

单链表

用顺序方式表示线性表的优点是存储结构简单、空间利用率高、存取速度快。但对于数据元
素的动态变化（如在插入或删除元素时，平均需要移动约一半元素）来说效率较低。为解决这个
问题，出现了另外一种存储方式，即链式表示。用链式表示的线性表也称为链表（linked list）。
链表不要求逻辑上相邻的数据元素在物理位置上也相邻，它通过指针来表示前驱、后继的关系，
因此它常用于插入或删除频繁、存储空间需求不定的情况。

线性表链式存储结构的特点是采用称为结点（node）的存储单元存储元素，结点的物理位置是
任意的。为了表示数据元素之间的前驱、后继的关系，结点中包含指针项，用来指出它的前驱、
后继结点的物理位置。也就是说，结点的指针项用于存放它的前驱、后继结点的存储地址，链表
中所谓的链就是由指针串联起来的。
单链表（single linked list）是一种最简单的链表表示，也叫作线性链表。单链表每个结点有两
个域组成：一个数据域 data 存放数据元素，一个指针域 next 存放指向该链表中下一个结点的指针
（后继结点的存储地址）。

单链表结点的存储结构定义如下：

1
2
3
4
5
typedef struct LNode
{
ElemType data; // 数据域
struct LNode *next; // 指针域
} LNode, *LinkList;

为了操作方便，经常会同时记录单链表的头结点指针位置、当前指针位置、尾结点指针位置
和单链表的长度等信息，可采用如下结构体记录：

1
2
3
4
5
6
7
typedef struct SListInfo
{
LinkList head; // 表头结点指针
LinkList tail; // 表尾结点指针
LNode *pCurNode; // 当前结点指针位置
int length; // 单链表的长度（元素个数）
} SListInfo;

单链表初始化

1
2
3
4
5
6
7
8
9
10
Status InitList( SListInfo &L )
{ // 初始化单链表
L.head = (LNode *)malloc(sizeof(LNode); // 申请头结点存储空间
if( L.head == NULL ) exit(OVERFLOW); // 存储空间申请失败
L.head->next = NULL; // 头结点后无其他结点
L.tail = L.head; // 尾结点指针也指向头结点
L.pCurNode = L.head; // 当前指针也指向头结点
L.length = 0; // 单链表长度为零
return OK;
} // InitList

单链表销毁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status DestroyList( SListInfo &L )
{ // 销毁单链表
 while ( L.head->next != NULL ) // 从头结点开始逐个释放链表中的结点
 {
 p = L.head->next;
 L.head->next = p->next;
 free(p);
 }
 free(L.head);
 L.head = NULL;
 L.tail = NULL;
 L.pCurNode = NULL;
 L.length = 0;
 return OK;
} // DestroyList

单链表清空操作与销毁操作相似，只是最后不需要释放头结点。单链表的清空操作无法像顺
序表那样只是将 length 赋值为 0 而保留结点复用

单链表数据元素获取

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status GetElem( SListInfo &L, int i, ElemType &e )
{ //获取单链表第 i 个数据元素
 if( i<1 || i>L.length ) // 参数检查
 return PARA_ERROR;
p = L.head->next;
j = 1;
while( j<i ) // 还未到达第 i 个元素，指针和计数器同步更新
{
 p = p->next;
 j++;
}
e = p->data; // 获得数据元素
L.pCurNode = p; // 单链表的当前指针指向该结点
return OK;
} //GetElem

在单链表当前结点后插入新结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Status InsertElemAfterCurNode( SListInfo &L, ElemType e )
{ // 在单链表当前结点后插入新结点并存入数据元素 e
// 1. 申请新的结点 s
s = (LNode *) malloc( sizeof(LNode) );
if ( s == NULL ) exit(OVERFLOW); // 内存申请失败
s.data = e;
// 2. 将结点 s 链接到 pCurNode 结点之后
s->next = L.pCurNode->next;
L.pCurNode->next = s;
// 3. 根据当前结点是否为表尾结点，进行表尾结点指针更新
if ( L.tail == L.pCurNode) 
{ // 更新表尾指针
L.tail = s;
}
// 4. 单链表的长度加 1
L.length += 1; 
return OK;
} // InsertElemAfterCurNod

在单链表当前结点后删除后续结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Status DeleteElemAfterCurNode( SListInfo &L, ElemType &e )
{ // 将单链表当前结点之后的结点删除，并用 e 返回
 if ( L.pCurNode->next == NULL ) return DELE_FAIL; // 当前结点为最后结点，后续无结点可删除
 //1. 将待删除结点的数据元素赋值给 e
e = L.pCurNode->next.data; 
 //2. 删除当前结点的下一个结点
p = L.pCurNode->next; 
 L.pCurNode->next = p->next;
 free(p);
 if (L.pCurNode->next == NULL) L.tail = L.pCurNode; // 若删除结点是尾结点则修改尾指针
 //3. 单链表长度减 1
L.length -= 1; 
return OK; 
} //DeleteElemAfterCurNode

双向链表

从对单链表的算法分析可见，单链表的单向性导致了无法逆向搜索的缺点。自然地，人们想
到增加一个从后向前的链接，这样就形成了双向链表（double linked list）

结构体修改如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct DuLNode
{
ElemType data; // 数据域
struct DuLNode *prev; // 指向前一个结点
struct DuLNode *next; // 指向下一个结点
} DuLNode, *DuLinkList;
typedef struct DuListInfo
{
DuLinkList head; // 表头结点指针
DuLinkList tail; // 表尾结点指针
DuLNode *pCurNode; // 当前结点指针位置
int length; // 双向链表的长度（元素个数）
} DuListInfo;

在双向链表当前结点之前插入新结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status InsertElemBeforeCurNode( DuListInfo &L, ElemType e )
{ // 在双向链表当前结点之前插入新结点并存入数据元素 e
// 1. 申请新的结点 s
s = (DuLNode *) malloc( sizeof(DuLNode) );
if ( s == NULL ) exit(OVERFLOW); // 内存申请失败
s.data = e;
// 2. 将结点 s 链接到 pCurNode 结点之前
s->prev = L.pCurNode->prev;
L.pCurNode->prev->next = s;
s->next = L.pCurNode;
L.pCurNode->prev = s;
// 3. 单链表的长度加 1
L.length += 1 ; 
return OK;
} //InsertElemBeforeCurNode

在双向链表当前结点之前删除新结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Status DeleteElemBeforeCurNode( DuListInfo &L, ElemType &e )
{ // 将双向链表当前结点之前的结点删除，并用 e 返回
 if ( L.pCurNode->prev == L.head ) return DELE_FAIL; // 当前结点为第一个结点，前面无结点可删除
 // 1. 将待删除结点的数据元素赋值给 e
e = L.pCurNode->prev.data; 
 // 2. 删除当前结点的前一个结点
p = L.pCurNode->prev; 
 p->prev->next = L.pCurNode;
 L.pCurNode->prev = p->prev;
 free(p);
// 3. 单链表长度减 1
L.length -= 1; 
return OK; 
} //DeleteElemBeforeCurNode

1665122154255

循环链表和双向循环链表

有时，链表中会出现到达表尾后折回表头的情形，这就是循环链表（circular linked list）。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。从表中任一结点出发均可找到表中其他结点。

1
2
3
4
5
6
typedef struct CircListInfo // 循环链表定义
{
LinkList head; // 循环链表表头结点指针
LNode *pCurNode; // 当前结点指针位置
int length; // 循环链表的长度（元素个数）
} CircListInfo;

循环链表的操作与单链表基本一致，差别在于表尾结点的 next 域指针不为空，而是指向表头
结点。
相应地，也有双向循环链表

静态链表

果在某些环境下无法动态申请结点空间，则可采用一维数组作为链表的存储结构，这就是
静态链表。在静态链表中，每个数组元素包括两个数据项：一个是数据元素本身；另外一个是静
态链接指针，即指向下一个数据元素的数组下标，它给出了逻辑上下一个结点在数组中的位置。
对静态链表进行操作时，可不改变各元素的物理位置，只需要修改链接数组元素的链接下标值就
可以改变这些元素的逻辑顺序。

栈

栈（Stack）是仅能在表的一端进行插入和删除的线性表。允许插入和删除的一端称作栈顶
（top）, 另外一端则称作栈底（bottom）。当栈中没有任何元素时则为空栈。

栈又称为后进先出（Last In First Out, LIFO）的线性表。

1665122204182

在栈的抽象数据类型定义中，与线性表不同的地方在于插入和删除操作被改成栈顶位置的压
栈 Push 和弹栈 Pop 操作。
通过压栈和弹栈的操作组合，可以形成原始序列的多种输出形式。

顺序栈

顺序栈（Sequential Stack）是栈的顺序存储表示，可用一块连续的存储单元作为其存储结构。
与线性表类似，该存储空间既可以是静态分配的固定大小的一维数组，也可以是动态分配的一块
连续存储空间。

1
2
3
4
5
6
7
8
9
顺序栈的动态存储描述方式如下：
#define STACKINITSIZE 256 // 初次分配空间大小
#define STACKINCREMENT 128 // 空间分配增量大小
typedef struct SeqStack
{
 ElemType *pBase; // 动态存储空间的基地址，作为栈底
 ElemType *pTop; // 栈顶指针，指向真实栈顶元素的下一个位置
 int stacksize; // 当前已分配的存储空间大小
}SeqStack;

在这里，pBase 既是动态分配空间的基地址也是栈底指针，始终指向栈底位置。pTop 为栈顶
指针，这里为了操作的方便，令其指向真实栈顶元素的下一个位置。当 pTop==pBase 时为空栈，
pTop-pBase 值则为栈中元素的个数。

1665122214536

顺序栈初始化

1
2
3
4
5
6
7
8
Status InitStack( SeqStack &S )
{ // 初始化顺序栈
S.pBase = (ElemType *)malloc(STACKINITSIZE*sizeof(ElemType)); // 申请存储空间
if( S.pBase == NULL ) exit(OVERFLOW); // 存储空间申请失败
S.pTop = S.pBase; // 栈顶指针同时指向栈底
S.stacksize = STACKINITSIZE; // 当前已分配的存储空间大小
return OK;
} // InitStack

顺序栈销毁

1
2
3
4
5
6
7
8
9
10
11
Status DestroyStack( SeqStack &S )
{ // 销毁顺序栈
 if( S.pBase != NULL ) 
{ 
free(S.pBase);
S.pBase = NULL;
} 
 S.pTop = NULL; 
 S.stacksize = 0; 
 return OK;
} // DestroyStack

顺序栈清空

1
2
3
4
5
Status ClearStack( SeqStack &S )
{ // 清空顺序栈
 S.pTop = S.pBase; 
 return OK;
} // ClearStack

访问顺序栈栈顶元素

1
2
3
4
5
6
Status GetTop( SeqStack S, ElemType &e )
{ // 若栈不空，用参数 返回栈 的栈顶元素；否则返回 ERROR
 if ( S.pTop==S.pBase ) return ERROR; // 空栈，无数据元素可访问
 e = *(S.pTop-1); // 将真实栈顶元素赋值给 e
 return OK;
} // GetTop

注意，我们只是将栈顶数据元素赋值给 e，并观察栈顶元素值但没有将栈顶元素从栈
中弹出，注意它与 Pop 操作的区别。

顺序栈压栈操作

1
2
3
4
5
6
7
8
9
10
11
12
13
Status Push( SeqStack &S, ElemType e )
{ // 插入数据元素 e 作为新的栈顶元素
if( S.pTop-S.pBase >= S.stacksize ) // 当前存储空间已满，需增加存储空间
{
S.pBase = ( ElemType* ) realloc( S.pBase, (S.stacksize+STACKINCREMENT)*sizeof(ElemType) ); 
if ( S.pBase == NULL ) exit(OVERFLOW); // 内存申请失败
S.pTop = S.pBase + S.stacksize; // 重新计算栈顶指针位置
S.stacksize += STACKINCREMENT;
}
*S.pTop = e; // 插入元素 e 作为新的栈顶元素
S.pTop++; // 栈顶指针指向真实栈顶的下一个位置
return OK;
} // Push

顺序表弹栈操作

1
2
3
4
5
6
7
Status Pop( SeqStack &S, ElemType &e )
{ // 若栈不空，则删除 S 的栈顶元素并用 e 返回，然后返回 OK；否则返回 ERROR
 if( S.pTop == S.pBase ) return ERROR; // 空栈，无数据可弹出
 e = *(S.pTop-1); // 将栈顶元素赋值给 e
S.pTop--; // 栈顶指针指向新的栈顶位置
return OK;
} // Pop

链式栈

采用链式表示的栈称为链式栈（Linked Stack）

为了方便压栈和弹栈的操作，应将栈顶设在单链表的表头，并将栈底放在单链表的表尾。

1665122226748

链式栈结点的存储结构与单链表结点一致，定义如下：

1
2
3
4
5
typedef struct LNode
{
ElemType data; // 数据域
struct LNode *next; // 指针域
} LNode, *LinkStack;

链式表压栈操作

1
2
3
4
5
6
7
8
9
10
11
Status Push( LinkStack &S, ElemType e )
{ // 将数据元素 e 压栈
//1. 申请新的结点 s
s = (LNode *) malloc( sizeof(LNode) );
if ( s == NULL ) exit(OVERFLOW); // 内存申请失败
 s->data = e;
//2. 将结点 s 链接到链式栈的头结点之后
s->next = S->next;
S->next = s;
return OK;
} //Push

链式表弹栈操作

1
2
3
4
5
6
7
8
9
10
11
Status Pop( LinkStack &S, ElemType &e )
{ // 将栈顶数据元素弹出，并用 e 返回
 if ( S->next == NULL ) return ERROR; // 空栈，无数据元素可弹出
 //1. 将栈顶数据元素赋值给 e
e = S->next.data; 
 //2. 删除栈顶元素
p = S->next; 
 S->next = p->next;
 free(p);
return OK; 
} //Pop

在一些特定场合下，可以利用一个连续存储空间同时实现两个栈。这两个栈的栈底分别设置
在数组的两端，栈顶则向数组中间移动，因此称作双端栈。这样，两个栈可以共享同一个存储空
间，互相调剂且灵活性强。

栈的应用举例

逆序输出问题

例：回文判断

正读和反读都相同的字符序列称为回文。例如，‘abcba’是回文，‘abcde’则不是回文。试给出一个算法，判别给定的字符串是否为回文。

从回文的定义可以看出，回文字符串的正序和逆序输出结果是相同的。算法需要做的就是将
输入字符串进行栈逆序操作，然后将其与正序字符串进行比较，判断两者是否相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Status CheckPalindrome( char *str )
{ // 检查 str 字符串是否是回文，是回文返回 RET_YES；否则返回 RET_NO
InitStack( S );
//1. 将字符串逐个字符压栈
 str_len = strlen(str);
for( i=0; i<str_len; i++ )
{
 Push(S, str[i]);
}
//2. 从栈中逐个弹出字符并将其与字符串的正序序列进行比较
tag = RET_YES; // 是否为回文标记，初始化为 RET_YES
for( i=0; i<str_len; i++ )
{
 Pop(S, e);
 if ( e!=str[i] )
 {
 tag = RET_NO; // 不是回文
 break;
 }
}
Destroy(S);
return tag;
} //CheckPalindrome

最近匹配与比较问题

例：括号匹配校验

队列

队列也是一种特殊的线性表，只允许在表的一端进行插入操作，在表的另一端进行删除操作。

表中允许进行插入操作的一端叫做队尾，允许进行删除操作的一端成为队头

队列插入称为入队，队列删除操作通常称为出队

队列没有别的元素时称为空队列

队列又被称为先进先出的线性表

然而直接用顺序表表示队列时，出队操作比较麻烦，每次出队都需要移动整个队列的元素，但是不移动又会浪费表前面的存储空间，所以下面用循环队列的思想。

1
2
3
4
5
6
7
#define MAXQSIZE 256 // 最大队列长度
typedef struct SeqQueue
{
 ElemType *pBase; // 动态存储空间的基地址
 int front; // 队头指针，若队列不空，指向队头元素
 int rear; // 队尾指针，若队列不空，指向队尾的下一个位置
}SeqQueue;

当 front==rear 时为空队列；当(rear+1)%MAXQSIZE==front 时，队尾追上了队
头，则队列满；队列的长度可表示为(rear+MAXQSIZE-front)%MAXQSIZE，这种计算方法巧妙地
处理了头尾循环相接的问题

顺序表示

循环队列的初始化

1
2
3
4
5
6
7
8
Status InitQueue( SeqQueue &Q )
{ // 初始化循环队列
 Q.pBase = (ElemType *)malloc(MAXQSIZE*sizeof(ElemType)); // 申请存储空间
 if( Q.pBase == NULL ) exit(OVERFLOW); // 存储空间申请失败
 Q.front = 0; // 空队列，队头指向 0 号单元
 Q.rear = 0; // 空队列，队尾指向 0 号单元
return OK;
} // InitQueue

循环队列的入队操作

1
2
3
4
5
6
7
8
Status EnQueue( SeqQueue &Q, ElemType e )
{ // 插入数据元素 e 为新的队尾元素
if( (Q.rear+1)%MAXQSIZE == Q.front ) // 队列满
 return ERROR;
Q.pBase[Q.rear] = e; // 插入元素 e 作为新的队尾元素
Q.rear = (Q.rear+1)%MAXQSIZE; // 队尾指针指向队尾元素的下一个位置
return OK;
} //EnQueue

循环队列的出队操作

1
2
3
4
5
6
7
Status DeQueue( SeqQueue &Q, ElemType &e )
{ // 若队列不空，则删除 Q 的队头元素并用 e 返回，并返回 OK；否则返回 ERROR
 if( Q.rear == Q.front ) return ERROR; // 空队列，无数据元素可出队
 e = Q.pBase[Q.front]; // 将队头元素赋值给 e
Q.front = (Q.front+1)%MAXQSIZE; // 队头指针指向新的队头位置
return OK;
} //DeQueue

队列的链式表示

链式队列的初始化

1
2
3
4
5
6
7
8
Status InitQueue( LinkQueue &Q )
{ // 构造一个空的链式队列 Q
// 1. 申请头结点
Q.front = Q.rear = (LNode *) malloc( sizeof(LNode) );
if ( Q.front == NULL ) exit(OVERFLOW); // 内存申请失败
Q.front->next = NULL;
return OK;
} //InitQueue

链式队列入队操作

1
2
3
4
5
6
7
8
9
10
11
12
Status EnQueue( LinkQueue &Q, ElemType e )
{ // 将数据元素 e 插入队列成为新的队尾
// 1. 申请新的结点 s
s = (LNode *) malloc( sizeof(LNode) );
if ( s == NULL ) exit(OVERFLOW); // 内存申请失败
 s->data = e;
 s->next = NULL;
// 2. 将结点 s 链接到队尾结点之后
Q.rear->next = s; 
Q.rear = s; // 更新队尾指针指向新的队尾
return OK;
} //EnQueue

链式队列出队操作

1
2
3
4
5
6
7
8
9
10
11
12
Status DeQueue( LinkQueue &Q, ElemType &e )
{ //将队头元素数据元素出队，并用 e 返回，若是空队列，返回 ERROR
 if ( Q.front == Q.rear ) return ERROR; // 空队列
 //1. 将队头数据元素赋值给 e
p = Q.front->next;
e = p->data; 
 //2. 删除队头结点
Q.front->next = p->next;
if ( Q.rear == p ) Q.rear = Q.front; // 如果已是队尾，则要更新队尾指针
 free(p);
 return OK; 
} //DeQueue

字符串

串(String): 是由零个或多个字符组成的有限序列。
记为：s= (n>=0)
空串：零个字符的串。
子串：串中任意一个字符的子序列称为这
个串的子串
主串：包含子串的串相应地称为主串
串相等：长度相等，对应位置字符相等

模式匹配算法

判断两个串之间是否具有”主串与子串”关系的算法

算法思想:从主串S的第pos个字符起和模式的第一
个字符比较之.
◼ 若相等,则继续逐个比较后续字符,
◼ 否则从主串的下一个字符起再重新和模式的字符比较.
◼ 依次类推,直到模式T中的每个字符依次和主串S中的
一个连续的字符序列相等,则称匹配成功,否则匹配不成
功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void SubStringFile(fstream &f_in,CharArray &in)
   {
       array=new char[MAXSTRLINE];
       char buf[MAXSTRLINE];
       const char sep[]=" ,.;\n\0";
       int count=0;
       while(f_in.eof()==false)
       {
           f_in.getline(buf,MAXSTRLINE);
           if(strlen(buf)==0) continue;
           char*token;
           token=strtok(buf,sep);
           while(token!=NULL)
           {
               if(strlen(token)>=in.Length())
               {
                   CharArray temp_obj(token);
                   if(temp_obj.SubString(in))//判断token和in是否相等
                   {
                       count++;
                   }
               }
               token=strtok(NULL,sep);
           }
       }
       if(count>0)
       {
           cout<<"匹配的字符串数量为:"<<count<<endl;
       }
       else
       {
           cout<<"没有找到匹配的字符串"<<endl;
       }
   }

数组

数组是存储于一个连续存储空间中的相同数据类型的数据元素的集合，通过数组元素的下标可以找到存放该数组元素的存储地址，从而可以访问该数组元素的值。就此意义来看，可以将数组看作线性表。

二维数组，在数学里可以看成一个矩阵

稀疏矩阵的压缩存储

我们称矩阵里非零元素非常少的矩阵为稀疏矩阵

由于非零元素的分布没有规律，所以在矩阵中可用一个三元组（行，列，值）确定一个矩阵
的非零元素。由此可将非零元素的三元组作为线性表的元素来表示一个稀疏矩阵，

1666589597204

定义

下面是三元组数据结构类的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Triple
{
public:
	int i;
	int j;
	int value;
	Triple()
	{
		i = 0;
		j = 0;
		value = 0;
	}
	Triple(int i1, int j1, int value1)
	{
		i = i1;
		j = j1;
		value = value1;
	}

	Triple&operator=(Triple t)
	{
		i = t.i;
		j = t.j;
		value = t.value;
		return *this;
	}
};

下面是稀疏矩阵类的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
class Matrix
{
private:
	int row;
	int col;
	int count;
	Triple tp[900];
public:
	Matrix()
	{
		row = 0;
		col = 0;
		count = 0;
	}
	Matrix(int i, int j)
	{
		row = i;
		col = j;
		count = 0;
	}
	void AddThreeTuple(int i, int j, int d)
	{
		if (i > 0 && i <= row && j > 0 && j <= col)
		{
			tp[count].value = d;
			tp[count].i = i;
			tp[count].j = j;
			count++;
		}
		else
		{
			cout << "out of range";
			exit(0);
		}
	}

	void PrintMatrix()
	{
		int temp = 0;
		for (int i = 0; i < row; i++)
		{
			for (int j = 0; j < col; j++)
			{
				if (tp[temp].i - 1 == i && tp[temp].j - 1 == j && j < col-1)
				{
					cout << tp[temp].value << " ";
					temp++;
				}
				else if (tp[temp].i - 1 == i && tp[temp].j - 1 == j && j == col-1)
				{
					cout << tp[temp].value << endl;
					temp++;
				}
				else if ((tp[temp].i - 1 != i || tp[temp].j - 1 != j) && j < col-1)
				{
					cout << 0 << " ";
				}
				else
				{
					cout << 0 << endl;
				}
			}
		}
	}

	void Set(int i, int j, int c)
	{
		col = i;
		row = j;
		count = c;
	}

	Matrix&operator=(Matrix t)
	{
		col = t.col;
		row = t.row;
		count = t.count;
		for (int ii = 0; ii < count; ii++)
		{
			tp[count] = t.tp[count];
		}
		return *this;
	}
	void TransposeMatrix1(Matrix &m);//将m矩阵转置的第一种方式，然后返回一个矩阵
	void TransposeMatrix2(Matrix &m);//将m矩阵转置的第二种方式，然后返回一个矩阵
	void TransposeMatrix3(Matrix &m);//将m矩阵转置的第三种方式，然后返回一个矩阵
};

要注意，三元组的i,j都是从1开始的，而不是从0开始

稀疏矩阵的转置

对于一个m×n的矩阵M,它的转置矩阵T应该是n×m
的矩阵, 同时满足T[i, j]=M[j, i],并且1<=i<=n,1<=j<=m
算法：
⑴将矩阵的行列值相互交换
⑵将每个三元组中的i和j相互调换
⑶重排三元组之间的次序（将T.data按行序排序法）

方法1：

先令三元组的i，j互换，然后再根据换了之后的三元组来排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void Matrix::TransposeMatrix1(Matrix &m)
{
	m.col = row;
	m.row = col;
	m.count = count;
	for (int ii = 0; ii < count; ii++)	//转置三元组
	{
		m.tp[ii].i = tp[ii].j;
		m.tp[ii].j = tp[ii].i;
		m.tp[ii].value = tp[ii].value;
	}
	for (int ii = 0; ii < count; ii++)	//三元组排序
	{
		for (int jj = ii + 1; jj < count; jj++)
		{
			if (m.tp[ii].i > m.tp[jj].i)
			{
				Triple temp = m.tp[ii];
				m.tp[ii] = m.tp[jj];
				m.tp[jj] = temp;
			}
			if (m.tp[ii].i == m.tp[jj].i&&m.tp[ii].j > m.tp[jj].j)
			{
				Triple temp = m.tp[ii];
				m.tp[ii] = m.tp[jj];
				m.tp[jj] = temp;
			}
		}
	}
}

方法2：

相当于可以理解为先按照原来的列排序，然后再转置三元组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void Matrix::TransposeMatrix2(Matrix &m)
{
	m.col = row;
	m.row = col;
	m.count = count;

	if (count)
	{
		int q = 0;
		for (int k = 0; k < col; k++)
		{
			for (int p = 0; p < count; p++)
			{
				if (tp[p].j == k)
				{
					m.tp[p].i = tp[p].j;
					m.tp[p].j = tp[p].i;
					m.tp[p].value = tp[p].value;
					q++;
				}
			}
		}
	}
}

方法3：

和前两个方法差别有点大

显然，可以在第一次遍历稀疏矩阵A 的三元组时，统计出 A 中每列的三元组个数，即转置后稀疏矩阵 B 中每行的三元组个数。这样，就可以方便地得到转置后稀疏矩阵 B 中每行三元组的起始位置。在第二次遍历稀疏矩阵 A 的
三元组时，每访问到一个三元组，就可以直接将其放到稀疏矩阵 B 中相应的位置。
为了能快速确定 A 中每个三元组在 B 中的位置，这里我们引入两个辅助数组。

（1） rowNum[col]：存放稀疏矩阵 A 各列的非零元素个数，也就是转置矩阵 B 各行的非零元
素个数。具体做法是：先把这个数组清零，然后遍历矩阵 A 的三元组表，逐个取出三元组的列号
col，把以此列号为下标的辅助数组元素的值累加 1。
（2） rowStart[col]：存放转置矩阵 B 中各行三元组应存放的起始位置。显然有
rowStart[col] = 0 ( col=0)
rowStart[col] = rowStart[col-1] + rowNum[col-1] （1≤col≤Cols）

类似于：

1666591837315

具体来说，快速转置算法思想如下。
第 1 步：对稀疏矩阵 A 进行第一趟遍历，根据矩阵 A 的列号，统计 A 中各列非零元素的个
数，即转置后各行非零元素个数。
第 2 步：根据第 1 步的统计结果，计算在转置矩阵 B 的三元组表中各行对应的起始位置。
第 3 步：对稀疏矩阵 A 的三元组表进行第二趟遍历，对每个三元组交换其行号和列号，连同其值构成一个新的转置后的三元组。根据行号，按辅助数组所指示的位置，将该三元组直接存放到转置矩阵 B 中对应的位置上，并将该行的位置指示值加 1，为放置该行下一个三元组做准备。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void Matrix::TransposeMatrix3(Matrix &m)
{
	m.col = row;
	m.row = col;
	m.count = count;
	if (count) 
	{ // 第 1 步：统计 A 中每列非零元素个数
		int *rowNum = new int[col]; 
		for (int k = 0; k < col; k++) rowNum[k] = 0; // rowNum 数组初始化清零 

		for (int p = 0; p < count; p++) rowNum[tp[p].j]++; // 统计 A 中每列（即 B 中每行）非零元素个数
		// 第 2 步：计算 B 中每行三元组的起始位置
		int *rowStart = new int[count];
		rowStart[0] = 0;
		for (int k = 1; k < col; k++)
			rowStart[k] = rowStart[k - 1] + rowNum[k - 1]; // 矩阵 B 每行三元组的起始位置
			 // 第 3 步：遍历 A 的三元组，进行矩阵转置
		int q = 0;
		for (int p = 0; p < count; p++)
		{
			q = rowStart[tp[p].j]; // 取出 B 当前行的起始位置
			m.tp[q].i = tp[p].j; 
			m.tp[q].j = tp[p].i; 
			m.tp[q].value = tp[p].value; 
			rowStart[tp[p].j]++; // B 当前行的起始位置增加 1，为该行下一个三元组的放入做准备
		} 
	} 
}

广义表

广义表一般记为:1666593845713
其中GL是广义表(a1,a2,……,an) 的名称，n 是广义表的长度。在线性表中,ai是单元素。在广义表中,ai既可以是单元素，也可以是广义表，它们分别称为广义表的原子和子表。

当广义表GL非空时，第一个元素a1为GL的表头（head），其余元素组成的子表(a2,a3,……,an)称为GL的表尾（tail）。

存储结构

由于广义表中的元素可以是原子，也可以是广义表，两者结构不同，大小不一，且难以用顺
序结构存储，因此通常采用链式结构表示广义表。

其中，结点必须设计成两种类型：表结点和原子结点。

层次结构

层次结构考虑存储广义表的层次信息。在层次结构的链式存储中，表结点设有两个指针域(next，down)。next 指向同一层的下一个元素，down 指向下一层子表的第一个元素 ；原子结点不存在下一层次，因此只有一个 next 指针域指向同一层的下一个元素。两者用标志位 1 和 0 区别。

1
2
3
4
5
6
7
8
typedef struct Node {
    int tag;//标志域
    union {
        int atom;//原子结点的值域
        struct Node* hp;//子表结点的指针域，hp指向表头
    }un;
    struct Node* tp;//这里的tp相当于链表的next指针，用于指向下一个数据元素
}GLNode, * Glist;

例如，广义表 (a,(b,c,d))

1666598168517

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Glist creatGlist(Glist C) {
    C = (Glist)malloc(sizeof(GLNode));
    C->tag = 1;
    C->un.hp = (Glist)malloc(sizeof(GLNode));
    C->tp = NULL;
    //存储 'a'
    C->un.hp->tag = 0;
    C->un.hp->un.atom = 'a';
    //存储(b,c,d)
    C->un.hp->tp = (Glist)malloc(sizeof(GLNode));
    C->un.hp->tp->tag = 1;
    C->un.hp->tp->un.hp = (Glist)malloc(sizeof(GLNode));
    C->un.hp->tp->tp = NULL;
    //存储'b'
    C->un.hp->tp->un.hp->tag = 0;
    C->un.hp->tp->un.hp->un.atom = 'b';
    C->un.hp->tp->un.hp->tp = (Glist)malloc(sizeof(GLNode));
    //存储'c'
    C->un.hp->tp->un.hp->tp->tag = 0;
    C->un.hp->tp->un.hp->tp->un.atom = 'c';
    C->un.hp->tp->un.hp->tp->tp = (Glist)malloc(sizeof(GLNode));
    //存储'd'
    C->un.hp->tp->un.hp->tp->tp->tag = 0;
    C->un.hp->tp->un.hp->tp->tp->un.atom = 'd';
    C->un.hp->tp->un.hp->tp->tp->tp = NULL;
    return C;
}

表头表尾结构

表头表尾结构考虑存储广义表的表头表尾信息。在表头表尾结构中，表结点设有两个指针域
(head，tail)，head 指向广义表的表头元素，tail 指向广义表的表尾；原子结点不设指针域，只存储
元素值。两者用标志位 1 和 0 区别.

1
2
3
4
5
6
7
8
9
typedef struct Node {
    int tag;//标志域
    union {
        char atom;//原子结点的值域
        struct {
            struct Node* hp, * tp;
        }ptr;//子表结点的指针域，hp指向表头；tp指向表尾
    }un;
}GLNode, * Glist;

同一时间此节点不是原子节点就是子表节点，当表示原子节点时，就使用 atom 变量；反之则使用 ptr 结构体。

例如，广义表 (a,(b,c,d))

1666597519078

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Glist creatGlist(Glist C) {
    //广义表C
    C = (Glist)malloc(sizeof(GLNode));
    C->tag = 1;
    //表头原子‘a’
    C->un.ptr.hp = (Glist)malloc(sizeof(GLNode));
    C->un.ptr.hp->tag = 0;
    C->un.ptr.hp->un.atom = 'a';
    //表尾子表(b,c,d),是一个整体
    C->un.ptr.tp = (Glist)malloc(sizeof(GLNode));
    C->un.ptr.tp->tag = 1;
    C->un.ptr.tp->un.ptr.hp = (Glist)malloc(sizeof(GLNode));
    C->un.ptr.tp->un.ptr.tp = NULL;
    //开始存放下一个数据元素(b,c,d),表头为‘b’，表尾为(c,d)
    C->un.ptr.tp->un.ptr.hp->tag = 1;
    //存储 'b'
    C->un.ptr.tp->un.ptr.hp->un.ptr.hp = (Glist)malloc(sizeof(GLNode));
    C->un.ptr.tp->un.ptr.hp->un.ptr.hp->tag = 0;
    C->un.ptr.tp->un.ptr.hp->un.ptr.hp->un.atom = 'b';
    //存放子表(c,d)，表头为c，表尾为(d)
    C->un.ptr.tp->un.ptr.hp->un.ptr.tp = (Glist)malloc(sizeof(GLNode));
    C->un.ptr.tp->un.ptr.hp->un.ptr.tp->tag = 1;
   
    //存储原子 'c'
    C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.hp = (Glist)malloc(sizeof(GLNode));
    C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.hp->tag = 0;
    C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.hp->un.atom = 'c';
    //存放表尾(d)
    C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.tp = (Glist)malloc(sizeof(GLNode));
    C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.tp->tag = 1;
    //存储 'd'
    C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.tp->un.ptr.hp = (Glist)malloc(sizeof(GLNode));
    C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.tp->un.ptr.hp->tag = 0;
    C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.tp->un.ptr.hp->un.atom = 'd';
    C->un.ptr.tp->un.ptr.hp->un.ptr.tp->un.ptr.tp->un.ptr.tp = NULL;
    return C;
}