- 用低劣的水平描述数据结构的东西，后续考研还要细学
- 目前主要加深对数据结构的理解，大体过一遍，如果你质疑我的文章，那一定是我错了，我会忽略一些专业术语，更偏向于自己的理解思考
- 对于初学者来说可能会有一定的帮助
前置
- 一堆概念
- 数据：客观事物的符号描述
- 数据元素：数据的基本单位
- 数据项：组成数据元素的、有独立含义的、不可分割的最小单位
- 数据对象：性质相同的数据元素的集合
- 逻辑结构
- 线性与非线性
- 线性、树、图、集合
- 存储结构
- 散列与性能分析
为什么学习数据结构？
- 学习数据结构和算法，并非为了死记硬背几个知识点。而是为建立时间复杂度、空间复杂度意识，写出高质量代码，能够设计基础架构，提升编程技能，训练逻辑思维，积攒人生经验，以此获得工作回报，实现你的价值，完善你的人生。 掌握数据结构与算法，看待问题的深度，解决问题的角度就会完全不同。
线性表
顺序表
前哨
输入特殊值后，表示输入结束的特殊值为前哨。
typedef
语句格式
typedef 实存类型 类型别名
一系列操作
定义的结构体
typedef struct
{
Type* data;
int max;
int size;
}Seqlist
尾插
插入前判断一下是否需要扩展空间，需要的话执行
void Reserve(Seqlist * l,int newmax)
{
int i ;
Type * old;
if(newmax <= l->max)
return ;
old = l -> data;
l -> max = newmax;
l -> data = (Type *) malloc (newmax * sizeof(Type));
for(int i = 0 ; i < l -> size ; i ++)
l -> data[i] = l -> old[i];
free (old);
}
尾插操作
void PushBack(Seqlist * l ,Type item)
{
if(l -> size == l -> max)
Reserve(l,2*max);
l -> data[l -> size ] = item;
l -> size++;
}
进行读取操作时，指针前面加const可以确保不会修改数据
删除
void Erase(Seqlist * l , int id)//删除第id元素
{
int i ;
for(i = id +1 ; i < l -> size ; i ++)
l -> data[i-1] = l -> data[i];
l ->size --;
}
定点插入
void intsert(Seqlist* l ,int id , Type item)
{
int i;
if(l -> size == l -> max)
Reserve(l,2*l -> max);
for(i = l -> size-1 ; i >= id ; i --)
l -> data[i+1] = l -> data[i];
l -> data[id] = item;
l -> size ++;
}
链表
单链表
循环链表
双向链表
链表逆置
将第二个结点及以后节点进行遍历，执行先首插再删除的操作，直到next==last
栈和队列
栈(先进先出)
- 没什么说的
队列
- 普通队列 queue
- 循环队列
- 双向队列 deque
- 优先队列 priority_queue
KMP字符串匹配
- 根据模式串t，求出next数组（只与模式串有关，与主串无关），利用next数组进行匹配，当匹配失败时，主串的指针 i 不再回溯！
- 所谓next，就是每个字符的最长相同前后缀，代码上注意递归求解即可
结构体设置
#define MAXSIZE 1024
typedef struct{
char ch[MAXSIZE+1]; //字符串
int length; //长度
}String;
求解next数组
void Get_Next(String t, int nextval[])
{
nextval[0] = -1;
int i = 0, j = -1;
while(i < t.length){
//相同前后缀，进入判断
if(j == -1 || t.ch[i] == t.ch[j]){
i++, j++; //修改位置
if(t.ch[i] != t.ch[j])
nextval[i] = j; //不相等，直接取值
else
nextval[i] = nextval[j]; //相等，无意义，再次向前求解
}else
j = nextval[j]; //非相同前后缀，向前递归
}
}
KMP
int KMP(String s, String t)
{
int nextval[MAXSIZE+1];
Get_Next(t, nextval); //求解nextval
int i = 0, j = 0;
while(i < s.length && j < t.length){
if(j == - 1 || s.ch[i] == t.ch[j]){ //相同，可匹配
i++, j++;
}else //不可匹配，向前追溯
j = nextval[j];
}
//输出匹配位置
if(j >= t.length)
return i - t.length + 1; //输出实际位置长度，非数组下标
return 0;
}