1.数据结构的基本概念

1.数据结构的定义：带结构的数据元素的集合

2.数据结构的逻辑结构：线性表（一对一），树（一对多），图（多对多）

3.数据元素的存储结构：顺序存储结构（可直接通过下标访问），链式存储结构（通过指针进行访问）

4.思维导图

2.算法

1.算法定义：对特定问题求解步骤的一种描述，它是指令的有限序列，每一条指令表示一个或多个操作

2.算法的特性：有穷性，确定性，可行性，输入，输出

3.算法的描述：自然语言，流程图，程序设计语言，伪代码

4.算法设计目标：正确性，可使用性，可读性，健壮性，时间效率高与存储量低

5.算法的效率分析：时间复杂度（最好，最坏，平均），空间复杂度

6.思维导图

3.线性表

-线性表的基本运算：初始化，销毁，判断，查找，插入，删除

1.顺序表

-优点：可通过下标访问
-缺点：顺序表在非表尾的地方插入，删除时，其他元素也要移动，使时间复杂度更高

2.链表（节点=数据元素+指针）

-优点：链表在任意位置进行插入，删除时，只需改动对应的指针即可，不用移动其他元素
-缺点：访问的时候需要for循环，不停的next，时间复杂度较高

1.单链表（头插法或尾插法）

2.双链表：相对单链表，它有两个指针域，指向前驱节点和后继节点，这样的话，就很方便的查找一个节点的前驱和后继。

3.循环链表：尾指针指向头节点

4.思维导图

3.栈

1.特点：是一种操作受限的线性表，只能在栈顶进行操作，先进后出

2.操作：进栈（push），出栈（pop），判断栈空，取栈顶元素等

3.类型：顺序栈，链栈

4.运用：后缀表达式的转换，求解迷宫问题

递归与栈的关系

1.递归的特点：自我调用，必须有递归出口

2.递归的过程是一个不断压栈的过程，遇到递归出口时再依次退栈。

4.队列

1.特点：是一种操作受限的线性表，只能在队头删除，在队尾插入，先进先出

2.操作：入队，出队，判断队空

循环队列

-用于解决队列的假溢出问题

方法：少用一个元素空间，队空时‘q.rear=q.front‘,队满时‘q.front=(q.rear+1)%m‘

-栈和队列思维导图

5.字符串

1.定义：由零或多个字符组成的1有限序列。注意点，空串（长度为零）不等于空格串。

2.基本操作：与其他的线性表差别较大，通常以整体作为操作对象。

串的模式匹配

-BF算法

1.特点：匹配失败时，i指针需要不停的回溯
2.最坏时间复杂度为O（n*m）

-KMP算法

1.特点：i指针不需要回溯
2.方法：利用next[j]函数计算出，失配后需要与模式串中的第几位进行比较。或者用nextval[j]进行计算

4.数组和广义表

-这个不太熟悉，就写一些主要的内容。

1.数组时多维结构，而存储空间是一维结构。
二维数组的存储位置公式：行优先：LOC(i,j)=LOC(0,0)+(ni+j)L

5.总结与反思

1.对一些重难点，如KMP算法和循环队列问题，在课后没有及时的巩固和消化。

2.课后的实际操作做的太少，对线性表的一些基本操作还不够熟悉。

3.以后会多做pta上的习题，注意课后知识的巩固。

数据结构慨念总结1

原文：https://www.cnblogs.com/yj-123/p/12587969.html