思维导图
算法
一、概念
- 定义：把基于存储结构的运算实现的步骤或过程称为算法。
2 五大特点：
- 有穷性：在有穷步之后结束，算法能够停机。
- 确定性：无二义性。
- 可行性：可通过基本运算有限次执行来实现， 也就是算法中每一个动作能够被机械地执行。
- 有输入
- 有输出
- 空间复杂度
- 空间复杂度：用于量度一个算法在运行过程中临时占用的存储空间大小。
- 一般也作为问题规模n的函数，采用数量级形式描述，记作：S(n) = O(g(n))
二、 算法分析
原则上只求出T(n)的最高阶，忽略低阶项和常系数
-
常数阶：记作O(1)，基本运算次数与问题规模n无关
-
线性阶：记作O(n)，基本运算次数与问题规模n的增长呈线性关系
-
平方阶：记作O(n2),
-
立方阶：记作O(n3)
-
对数阶：记作O(log2n)
线性表
-
概念
-
线性表是一个具有相同特性的数据元素的有限序列。
-
线性表中所含元素的个数叫做线性表的长度，用n表示，n≥0。n=0时，表示线性表是一个空表，即表中不包含任何元素。
-
逻辑序号：1≤i≤n
物理序号：0≤i≤n-1
二、顺序存储结构
- 线性表的顺序存储结构：按逻辑顺序依次存储到存储器中一片连续的存储空间中。
2.
- 顺序表类型定义
typedef struct
{ ElemType data[MaxSize];
int length;
} SqList; //顺序表类型
4.顺序表指针的含义
SqList *L;
L=(SqList *)malloc(sizeof(SqList));
顺序表指针引用
void CreateList(SqList *&L，ElemType a[]，int n) 引用参数：将执行结果回传给实参
三、链式存储结构
-
线性表中每个结点有唯一的前驱结点和前驱结点。
-
单链表中结点类型LinkNode的定义
typedef struct LNode //定义单链表结点类型
{ ElemType data;
struct LNode *next; //指向后继结点
} LinkNode;
栈（后进先出）
一、顺序栈
-
定义：栈是一种只能在一端进行插入或删除操作的线性表。
-
假设栈的元素个数最大不超过正整数MaxSize，所有的元素都具有同一数据类型ElemType，则可用下列方式来定义顺序栈类型SqStack:
typedef struct
{ ElemType data[MaxSize]；
int top； //栈顶指针
} SqStack
-
四要素
栈空条件：top=-1
栈满条件：top=MaxSize-1
进栈e操作：top++; 将e放在top处
退栈操作：从top处取出元素e; top--;
二、链栈
-
采用链表存储的栈称为链栈，这里采用带头结点的单链表实现。
- 链栈中数据结点的类型LinkStNode定义如下:
typedef struct linknode
{ ElemType data; //数据域
struct linknode *next; //指针域
} LinkStNode;
- 四要素
栈空条件：s->next=NULL
栈满条件：不考虑
进栈e操作：将包含e的结点插入到头结点之后
退栈操作：取出头结点之后结点的元素并删除之
队列（先进先出）
-
顺序队
-
队列简称队，它也是一种运算受限的线性表
-
顺序队类型SqQueue定义如下：
typedef struct
{ ElemType data[MaxSize]；
int front,rear； //队首和队尾指针
} SqQueue;
- 四要素（初始时front=rear=-1）
队空条件：front = rear
队满条件：rear = MaxSize－1
元素e进队：rear++; data[rear]=e;
元素e出队：front++; e=data[front];
二、链队
采用链表存储的队列称为链队，这里采用不带头结点的单链表实现。
- 链队中头结点类型LinkQuNode定义如下：
typedef struct
{ DataNode *front; //指向单链表队头结点
> DataNode *rear; //指向单链表队尾结点
> } LinkQuNode;
- 四要素
队空条件：front=rear=NULL
队满条件：不考虑
进队e操作：将包含e的结点插入到单链表表尾
出队操作：删除单链表首数据结点
串
-
概念
-
串（或字符串）是由零个或多个字符组成的有限序列。
-
串中所含字符的个数称为该串的长度（或串长），含零个字符的串称为空串，用Ф表示。
-
串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的。
-
子串：一个串中任意个连续字符组成的子序列（含空串）称为该串的子串。
二、顺序串
1.对于非紧缩格式的顺序串，其类型定义如下：
#define MaxSize 100
typedef struct
{ char data[MaxSize];
int length;
} SqString;
三、链串
链串的组织形式与一般的链表类似。
链串中的一个结点可以存储多个字符。通常将链串中每个结点所存储的字符个数称为结点大小。
四、串的模式匹配
1.BF算法（不推荐）
2.KMP算法
疑难问题及解决方案
前几天对KMP算法一直很迷惑不解，后来在网上看了一篇文章，顿觉醍醐灌顶，茅塞顿开。
https://segmentfault.com/a/1190000008575379