数据结构

c语言数据结构考研

学习笔记

发布日期: 2021-04-11

文章字数: 7.9k

使用的教材：

数据结构（C语言版）严蔚敏

王道数据结构考研复习指导（2022）

2021/4/11

考研大纲（408）

【408考查目标】

掌握数据结构的基本概念、基本原理和基本方法。
掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。
能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用 C 或 C++语言设计与实现算法的能力。

一、线性表

(一)线性表的基本概念
(二)线性表的实现（顺序存储、链式存储）
(三).线性表的应用

二、栈、队列和数组

(一)栈和队列的基本概念
(二)栈和队列的顺序存储结构
(三)栈和队列的链式存储结构
(四)多维数组的存储
(五)特殊矩阵的压缩存储
(六)栈、队列和数组的应用

三、树与二叉树

(一)树的基本概念

(二)二叉树
1.二叉树的定义及其主要特征
2.二叉树的顺序存储结构和链式存储结构
3.二叉树的遍历
4.线索二叉树的基本概念和构造

(三)树、森林
1.树的存储结构
2.森林与二叉树的转换
3.树和森林的遍历

(四)树与二叉树的应用
1.二叉搜索树
2.平衡二叉树
3.哈夫曼(Huffman)树和哈夫曼编码

四、图

(一)图的基本概念
(二)图的存储及基本操作
1.邻接矩阵法
2.邻接表法
3.邻接多重表、十字链表
(三)图的遍历
1.深度优先搜索
2.广度优先搜索
(四)图的基本应用
1.最小(代价)生成树
2.最短路径
3.拓扑排序
4.关键路径

五、查找

(一)查找的基本概念
(二)顺序查找法
(三)分块查找法
(四)折半查找法
(五)B 树及其基本操作、B+树的基本概念
(六)散列(Hash)表
(七)字符串模式匹配
(八)查找算法的分析及应用

六、排序

(一)排序的基本概念
(二)插入排序
1.直接插入排序
2.折半插入排序
(三)起泡排序(bubble sort)
(四)简单选择排序
(五)希尔排序(shell sort)
(六)快速排序
(七)堆排序
(八)二路归并排序(merge sort)
(九)基数排序
(十)外部排序
(十一)各种内部排序算法的比较
(十二)排序算法的应用

第1章绪论

本章的内容是数据结构概述，不在考研大纲中，但是分析算法的时间复杂度和空间复杂度是本章的重点，属于必考内容，一定要熟练掌握。

1.1 数据结构的基本概念

1.1.1 基本概念和术语

数据：信息的载体，是对客观事物的符号表示
数据元素：数据的基本单位，一个数据元素可由若干个数据项组成。如：一个学生记录（学号、姓名、…）数据项是构成数据元素的不可分割的最小单位
数据对象：具有相同性质的数据元素的集合，是数据的一个子集。
数据结构：是相互存在一种或多种特定关系的数据元素的集合；数据结构包括三方面的内容：逻辑结构，存储结构和数据的运算
数据类型：原子类型、结构类型、抽象数据类型
抽象数据类型：指一个数学模型以及定义在该模型上的一组操作
- 通常用（数据对象，数据关系，基本操作集）这样的三元组来表示抽象数据类型。
- ADT 抽象数据类型名{
  数据对象:<数据对象的定义>
  数据关系:<数据关系的定义>
  基本操作:<基本操作的定义>
  }ADT 抽象数据类型名

1.1.2 数据结构三要素

1.数据的逻辑结构

线性结构：一对一
树形结构：一对多
图结构：多对多
集合

2.数据的存储结构

顺序存储
链式存储
索引存储
散列存储

绪论部分只需要理解三点:
1.若采用顺序存储，则各个数据元素在物理上必须是连续的；若采用非顺序存储，则各个数据元素在物理上可以是离散的。
2.数据的存储结构会影响存储空间分配的方便程度。
3.数据的存储结构会影响对数据运算的速度。

3.数据的运算

施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

1.2 算法和算法分析

1.2.2 算法效率的度量

1.时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作

$T(n)=O(f(n))$

它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。

常见的渐进时间复杂度为

$O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$

2.空间复杂度

算法的空间复杂度作为算法所需存储空间的量度，记作

$S(n)=O(f(n))$ 2021/4/12

第2章线性表

线性表是考研的重点，实现起来比较容易而且代码量较少，但却要求具有最优的性能才能获得满分。

408大纲

(一)线性表的基本概念
(二)线性表的实现（顺序存储、链式存储）
(三).线性表的应用

2.1 线性表的定义和基本操作

2.1.1 线性表的定义

线性表是具有相同数据类型的n个数据元素的有限序列，其中n为表长，当n=0时，是一个空表。
若将线性表记为

$L=(a_1,a_2,...,a_n)$

除第一个元素外，每一个元素有且仅有一个直接前驱，每个元素有且仅有一个直接后继。

注意：线性表是一种逻辑结构，顺序表和链表是指存储结构。

2.1.2 线性表的基本操作

InitList(&L)：初始化表。构造一个空的线性表。
Length(L)：求表长。返回线性表I的长度，即L中数据元素的个数。
LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e.
ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值
PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L)：判空操作。若L为空表，则返回true,否则返回false.
DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

2.2 线性表的顺序表示

2.2.1 顺序表的定义

顺序表是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。因此，顺序表的特点是表中元素的逻辑地址与其物理顺序相同。

注意：线性表中元素的位序是从1开始的，而数组中元素的下标是从0开始的。

#define InitSize 100
typedef struct{
    Elemtype *data;
    int maxSize;
    int length; 						//在进行增删操作后记得更改length
}Sqlist;

//动态增加动态数组的长度
void IncreaseSize(SeqList &L，int len){
    int *p=L.data;
    L.data=(int*)malloc((L.MaxSize+len)*sizeof(int));
    for(int i=0;i<L.length;i++){
        L.data[i]=p[i];
    }
    L.MaxSize=L.MaxSize+len;
    free(p);
}

顺序表最主要的特点是随机访问，即通过首地址和元素序号可在时间O(1)内找到指定的元素。
顺序表的存储密度高，每个结点只存储数据元素。
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

2.2.2 顺序表上基本操作的实现

略

2021/4/13

2.3 线性表的链式表示

链式存储线性表时，不要求逻辑上相邻的两个元素在物理位置上也相邻，因此对线性表的插入、删除不需要移动元素，只需要修改指针。

2.3.1 单链表的定义

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。

单链表中结点类型的描述如下：

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

利用单链表可以解决顺序表需要大量连续存储空间的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。单链表是非随机存取的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。通常用头指针来标识一个单链表，如单链表L，头指针为NULL时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等相关信息。头结点的指针域指向线性表的第一个元素结点。

可入头结点后，可以带来两个优点:
①在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。
②无论链表是否为空，其头指针都指向头结点的非空指针(空表中头结点的指针域为空，因此空表和非空表的处理也就得到了统一。

2.3.2 单链表上基本操作的实现

只写全一个例子

1.采用头插法建立单链表

LinkList List_HeadInsert(LinkList &L){
	LNode *s,int x;
	L=(LinkList)malloc(sizeof(LNode));	//创建头结点
	L->next=NULL;
	scanf("%d",&x);
	while(x!=9999){
		s=(LinkList)malloc(sizeof(LNode));
		s->data=x;
		s->next=L->next
		L->next=s;
		scanf("%d",&x);
	} 
	return L;
}

单链表在插入元素时，在给定的结点后插入，时间复杂度仅为O(1)，但在前面插入时，如果从头开始寻找第前置元素，时间复杂度为O(n)，我们可以通过另一种方法转化为后插操作（后插+换数据）使得时间复杂度为O(1)。

删除元素同理。

2.3.3 双链表

双链表结点中有两个指针prior和next，分别指向其前驱结点和后驱结点。

typedef struct DNode{
	ElemType data;
	struct DNode *prior,*next;
}DNode,*DLinkList;

双链表可以很方便地找到其前驱结点，因此，插入，删除操作的时间复杂度仅为O(1)。

2.3.4 循环链表

1.循环单链表

在循环单链表中，表尾结点*r的next域指向L，故表中没有指针域为NULL的结点，因此，循环单链表的判空条件是头结点的指针是否等于头指针。

2.循环双链表

2.3.5 静态链表

2021/4/14

2.3.6 顺序表和链表的比较

1.存取(读写)方式
顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序依次存取元素。

2.逻辑结构与物理结构
采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的。

3.查找、插入和删除操作
对于按值查找，顺序表无序时，两者的时间复杂度均为O(n)；顺序表有序时，可采用折半查找，此时的时间复杂度为O($\log_2n$)。
对于按序号查找，顺序表支持随机访问，时间复杂度仅为0(1)；而链表的平均时间复杂度为O(n)。
顺序表的插入、删除操作，平均需要移动半个表长的元素。链表的插入、删除操作，只需修改相关结点的指针域即可。由于链表的每个结点都带有指针域，故而存储密度不够大。

4.空间分配
顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。
链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。

在实际中存储结构的选择

1.基于存储的考虑
难以估计线性表的长度或存储规模时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低。

2.基于运算的考虑
若经常做的运算是按序号访问数据元素，则显然顺序表优于链表。
进行插入、删除操作时，显然后者优于前者。

总之，两种存储结构各有长短，选择哪一种由实际问题的主要因素决定。通常较稳定的线性表选择顺序存储，而频繁进行插入，删除操作的线性表（动态性较强）宜选择链式存储。

2021/4/16

第3章栈和队列

本章通常以选择题的形式考查，题目不算难，但命题的形式比较灵活，其中栈(出入栈的过程、出栈序列的合法性)和队列的操作及其特征是重点。由于它们均是线性表的应用和推广，因此也容易出现在算法设计题中。此外，栈和队列的顺序存储、链式存储及其特点、双端队列的特点、栈和队列的常见应用，以及数组和特殊矩阵的压缩存储都是必须掌握的内容。

408大纲

3.1 栈

3.1.1 栈的基本概念

1.栈的定义

栈是只允许在一端进行插入或删除操作的线性表。
栈顶：线性表允许进行插入删除的那一端。
栈底：固定的，不允许进行插入和删除的另一端。

栈的操作特性可以明显地概括为后进先出（LIFO）

2.栈的基本操作

InitStack(&S)：初始化一个空栈S。
StackEmpty(S)：判断一个栈是否为空，若栈s为空则返回true，否则返回false。
Push(&S,x)：进栈，若栈s未满，则将x加入使之成为新栈顶。
Pop(&S,&x)：出栈，若栈s非空，则弹出栈项元素，并用x返回。
GetTop(S,&x)：读栈顶元素，若栈s非空，则用x返回栈项元素。
DestroyStack(&S)：销毁栈，并释放栈S占用的存储空间

在解答算法题时，若题干未做出限制，则可直接使用这些基本的操作函数。

3.1.2 栈的顺序存储结构

栈是一种操作受限的线性表，类似于线性表，它也有对应的两种存储方式。

1.顺序栈的实现

栈的顺序存储类型可描述为：

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int top;
}sqstack;

栈项指针：S.top，初始时设置S.top=-1；栈项元素：S.data[S.top]。
进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。
出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1。
栈空条件：s. top=\=-1；栈满条件: S.top==MaxSize-1; 栈长: s. top+1。

注意:栈和队列的判空、判满条件，会因实际给的条件不同而变化，需具体问题具体分析。

2.顺序栈的基本运算

同上。

3.共享栈

利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
共享栈是为了更有效地利用存储空间，两个栈的空间相互调节。

3.1.3 栈的链式存储结构

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头结点，Lhead 指向栈顶元素。

栈的顺序存储类型可描述为：

typedef struct Linknode{
    ELemType data;
    struct Linknode *next;
} *Listack;

采用链式存储，便于结点的插入与删除。链栈的操作与链表类似，入栈和出栈的操作都在链表的表头进行。

3.2 队列

3.2.1 队列的基本概念

1.队列的定义

队列简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。其操作的特性是先进先出(FIFO)
队头：允许删除的一端，又称队首
队尾：允许插入的一端

2.队列常见的基本操作

InitQueue(&Q)：初始化队列，构造个空队列Q。
QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
EnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue(&Q, &x)：出队，若队列Q非空，删除队头元素，并用x返回。
GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给X。

3.2.2 队列的顺序存储结构

1.队列的顺序存储

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置（不同教材对front和rear的定义可能不同，对于不同的定义，出队入队的操作是不同的）。

队列的顺序存储类型可描述为：

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
}SqQueue;

初始状态（队空条件）: Q.front==Q.rear==0。
进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。
出队操作：队不空时，先取队头元素值，再将队头指针加1。

这样存储可能会发生“假溢出”。

2021/4/22

2.循环队列

为了克服顺序存储的缺点，这里引出循环队列的概念，即把存储队列元素的表从逻辑上视为一个环。当队首指针Q.front=MaxSize-1后，再前进一个位置就自动到0，这可以利用除法取余运算来实现。

初始时：Q.front=Q.rear=0。
队首指针进1：Q.front= (Q.front+1)%MaxSize。
队尾指针进1：Q.rear= (Q.rear+1)%MaxSize。
队列长度：(Q.rear+MaxSize-Q.front)%MaxSize。

但是队空和队满的条件都是Q.front==Q.rear，为了区分队空还是队满的情况，有三种处理方式：
（1）牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法，约定以“队头指针在队尾指针的下-一位置作为队满的标志。
队满条件：(Q.rear+1) %MaxSize==Q.front。
队空条件仍：Q.front==Q.rear.
队列中元素的个数：(Q.rear-Q.front+MaxSize)%MaxSize。
（2）类型中增设表示元素个数的数据成员。这样，队空的条件为Q.size==0；队满的条件为Q.size==MaxSize。这两种情况都有Q.front==Q. rear。
（3）类型中增设tag 数据成员，以区分是队满还是队空。（入队置1，出队置0，初试设0）tag等于0时，若因删除导致Q. front==Q.rear，则为队空；tag等于1时,若因插入导致Q.front==Q.rear,则为队满。

3.循环队列的操作

（1）初始化
（2）判断空
（3）入队

bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize==Q.front) return false;
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;
    return ture;
}

（4）出队

3.2.3 队列的链式存储结构

1.队列的链式存储

队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点。

队列的链式存储类型可描述为：

typedef struct{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front, *rear;
} LinkQueue;

当Q.front==NULL且Q.rear==NULL时，链式队列为空。

不带头结点的链式队列在操作上往往比较麻烦，因此通常将链式队列设计成一个带头结点的单链表，这样插入和删除操作就统一了。

用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。

2.链式队列的基本操作

（1）初始化
（2）判断空
（3）入队
（4）出队

3.2.4 双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列。其元素的逻辑结构仍是线性结构。将队列的两端分别称为前端和后端，两端都可以入队和出队。
输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列称为输出受限的双端队列。
输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列称为输入受限的双端队列。
若限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈。

3.3栈和队列的应用

3.3.1 栈在括号匹配中的应用

3.2.2 栈在表达式求值中的应用

中缀表达式(a 操作符 b)	后缀表达式(逆波兰式)(a b 操作符)	前缀表达式(波兰式)(操作符 a b)
a+b	ab+	+ab
a+b-c	ab+c-	-+abc
a+b-c*d	ab+cd*-	-+ab*cd
a+b*(c-d)-e/f	abcd-*+ef/-	+a-*-cdb/ef

后缀表达式的运算：

在后缀表达式中已考虑了运算符的优先级，没有括号，只有操作数和运算符。
中缀表达式A+B*(C-D)-E/F所对应的后缀表达式为ABCD-*+EF/-。

若项是操作数，则将其压入栈中；若项是操作符，则连续从栈中退出两个操作数Y和X，形成运算指令X op Y,并将计算结果重新压入栈中。全部处理完后，栈顶存放的就是结果。

前缀表达式的运算：

前缀表达式从右往左扫，原理差不多

中缀表达式转后缀表达式：

初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
从左到右处理各个元素，直到末尾。可能遇到三种情况: .
①遇到操作数。直接加入后缀表达式。
②遇到界限符。遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(” 为止。注意:“(” 不加入后缀表达式。
③遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(”或栈空则停止。之后再把当前运算符入栈。
按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

中缀表达式转后缀表达式/中缀表达式的计算（用栈实现）:

3.3.3 栈在递归中的作用

适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题
栈递归算法大大减少了程序的代码量，但在通常情况下，它的效率不是太高。

递归函数的实现需要借助一个函数调用栈来实现。
（也可以将递归算法转换为非递归算法，通常需要借助栈来实现这种转换。）

3.3.4 队列在层次遍历中的应用（广度优先遍历）

逐层\逐行处理（广度优先遍历）。这类问题的解决方法往往是在处理当前层或当前行时就对下一层或下一行做预处理，把处理顺序安排好，待当前层或当前行处理完毕，就可以处理下一层或下一行。使用队列是为了保存下一步的处理顺序。表3.2显示了层次遍历二叉树的过程。
该过程的简单描述如下:
①根结点入队。
②若队空（所有结点都已处理完毕），则结束遍历；否则重复③操作。
③队列中第一个结点出队并访问。若其有左孩子，则将左孩子入队；若其有右孩子，则将右孩子入队，返回②。

3.3.5 队列在计算机系统中的应用

打印数据缓冲区、CPU进程访问队列……

2021/4/23

3.4 特殊矩阵的压缩存储

矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最小的内存空间来存储同样的一组数据。

3.4.1 数组的定义

3.4.2 数组的存储结构

3.4.3 矩阵的压缩存储

压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是为了节省存储空间。

1.对称矩阵

2.三角矩阵

3.三对角矩阵

3.4.4 稀疏矩阵

稀疏矩阵：非零元素远远少于矩阵元素的个数

2021/4/27

第4章串

统考大纲只要求掌握字符串模式匹配，需重点掌握KMP匹配算法的原理及next数组的推理过程，了解nextval数组的求解方法。

408大纲

字符串模式匹配

4.1 串的定义和实现

字符串简称串，计算机上非数值处理的对象基本都是字符串数据。

4.1.1 串的定义

串(string) 是由零个或多个字符组成的有限序列。一般记为

$S='{a_1a_2...a_n}'(n\geq0)$

子串：串中任意个连续的字符组成的子序列。
主串：包含子串的串。
字符在主串中的位置：字符在串中的序号。
子串在主串中的位置：子串的第一个字符在主串中的位置。

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符集。

串的基本操作通常以子串作为操作对象，如查找、插入或删除一个子串等。

4.1.2 串的顺序结构

1.定长顺序存储表示

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN];
    int length;
}SString;

串长有两种表示方法：一是如上述定义描述的那样，用一个额外的变量len来存放串的长度；二是在串
值后面加一一个不计入串长的结束标记字符“\0”，此时的串长为隐含值。

2.堆（动态）分配存储表示

typedef struct{
    char *ch;
    int length;
}SString;

3.块链存储表示

也可采用链表方式存储串值。由于串的特殊性(每个元素只有一个字符)，在具体实现时，每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为块，整个链表称为块链结构。最后一个结点占不满时通常用“#”补上。

4.1.3 串的基本操作

StrAssign(&T, chars)：赋值操作。把串T赋值为chars。
StrCopy(&T,S)：复制操作。由串S复制得到串T。
StrEmpty(S)：判空操作。若S为空串，则返回TRUE，否则返回FALSE。
StrCompare(S,T)：比较操作。若S>T，则返回值>0；若S=T，则返回值=0;若S<T，则返回值<0。
StrLength(S)：求串长。返回串S的元素个数。
SubString (&Sub,S,pos,len)：求子串。用Sub返回串S的第pos个字符起长度为len的子串。
Concat (&T,S1,S2)：串联接。用T返回由S1和S2联接而成的新串。
Index(S,T)：定位操作。若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0。
ClearString(&S)：清空操作。将S清为空串。
DestroyString(&S)：销毁串。将串S销毁。

在上述定义的操作中，串赋值StrAssign、串比较StrCompare、求串长StrLength、串联接Concat及求子串SubString五种操作构成串类型的最小操作子集，即这些操作不可能利用其他串操作来实现；反之，其他串操作（除串清除ClearString和串销毁DestroyString外）均可在该最小操作子集上实现。

例如，可利用判等、求串长和求子串等操作实现定位函数Index(S,T)。算法思想为:在主串S中取从第一个字符起、长度和串T相等的子串，与串T比较，若相等则求得函数值为i，否则i值增1，直至串S中不存在和串T相等的子串为止。

int Index(String S，String T) {
    int i=1,n=StrLength(S),m=StrLength(T);
    while(i<=n-m+1){
        SubString(sub,S,i,m);
        if(StrCompare(sub,T)!=0) ++i;
        else return i;
    }
    return 0;
}

4.2 串的模式匹配

子串的定位操作通常称为串的模式匹配，它求的是子串(常称模式串)在主串中的位置。

4.2.1 简单的模式匹配算法

Ep4l

https://Ep4l.top/2021/04/11/data-structure/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Ep4l !

c语言数据结构考研

线性代数

考研线性代数

2021-06-22 学习笔记

考研数学线性代数

又一次搞崩博客的经历

2021-02-14 Ep4l

考研大纲（408）

一、线性表

二、栈、队列和数组

三、树与二叉树

四、图

五、查找

六、排序

第1章 绪论

1.1 数据结构的基本概念

1.1.1 基本概念和术语

1.1.2 数据结构三要素

1.数据的逻辑结构

2.数据的存储结构

3.数据的运算

1.2 算法和算法分析

1.2.2 算法效率的度量

第2章 线性表

408大纲

2.1 线性表的定义和基本操作

2.1.1 线性表的定义

2.1.2 线性表的基本操作

2.2 线性表的顺序表示

2.2.1 顺序表的定义

2.2.2 顺序表上基本操作的实现

2.3 线性表的链式表示

2.3.1 单链表的定义

2.3.2 单链表上基本操作的实现

2.3.3 双链表

2.3.4 循环链表

2.3.5 静态链表

2.3.6 顺序表和链表的比较

第3章 栈和队列

408大纲

3.1 栈

3.1.1 栈的基本概念

1.栈的定义

2.栈的基本操作

3.1.2 栈的顺序存储结构

1.顺序栈的实现

2.顺序栈的基本运算

3.共享栈

3.1.3 栈的链式存储结构

3.2 队列

3.2.1 队列的基本概念

1.队列的定义

2.队列常见的基本操作

3.2.2 队列的顺序存储结构

1.队列的顺序存储

2.循环队列

3.循环队列的操作

3.2.3 队列的链式存储结构

1.队列的链式存储

2.链式队列的基本操作

3.2.4 双端队列

3.3栈和队列的应用

3.3.1 栈在括号匹配中的应用

3.2.2 栈在表达式求值中的应用

3.3.3 栈在递归中的作用

3.3.4 队列在层次遍历中的应用（广度优先遍历）

3.3.5 队列在计算机系统中的应用

3.4 特殊矩阵的压缩存储

3.4.1 数组的定义

3.4.2 数组的存储结构

3.4.3 矩阵的压缩存储

1.对称矩阵

2.三角矩阵

3.三对角矩阵

3.4.4 稀疏矩阵

第4章 串

408大纲

4.1 串的定义和实现

4.1.1 串的定义

4.1.2 串的顺序结构

1.定长顺序存储表示

2.堆（动态）分配存储表示

3.块链存储表示

4.1.3 串的基本操作

4.2 串的模式匹配

4.2.1 简单的模式匹配算法

第1章绪论

第2章线性表

第3章栈和队列

第4章串