数据结构是指数据元素的集合及元素间的相互作用和构造方法。元素之间的相互关系是数据的逻辑结构，数据元素及元素之间关系的存储称为物理结构（或存储结构）。

数据结构按照逻辑关系的不同分为线性结构和非线性结构两大类。线性结构主要就是线性表（顺序表、单链表）、栈、队列数组和串这些，而非线性结构主要就是树结构、图结构。

算法与数据结构密切相关，数据结构是算法设计的基础，设计合理的数据结构可使算法简单而高效。

2.数组

对于一维数组来说，a[i]的存储地址计算公式为：a + i×len，a代表起始位置，i代表数组下标，len代表每个元素所占字节数。

假设数组a中每个元素占两个字节，那么对于起始位置为0、元素a[1]来说，它的存储地址为：0 + 1×2=2，因为0和1两个位置被数组的第一个元素a[0]占用。

对于上面这道例题，二维数组中，根据计算公式，元素a[2][3]按行优先存储的存储地址为：a + （2×5+3）×2=a + 26。

3.稀疏矩阵

对于上三角矩阵和下三角矩阵，大家需要搞懂的就是上面这种例题。（不建议大家死记硬背这两个公式，推荐大家采取代入数字直接验证的方式！！！）

例题中是一个下三角矩阵，我们看到A[0，0]存储在一维数组M[1]这个位置（注意数组M的下标从1开始），所以我们取 i=0、j=0代入四个选项，BC两个选项得到的结果是0，直接排除；而AD两个选项得到的结果是1，满足题意。我们再看到A[1，0]存储在一维数组M[2]这个位置，所以我们再取 i=1、j=0代入AD两个选项，D选项得到的结果是1；A选项得到的结果是2。综上所述，通过两次取值验证，A选项正确！！！

4.线性表

一个线性表是n（n≥0）个元素的有限序列，通常表示为（a1，a2，......，an）。非空线性表的特点如下：

①存在唯一的一个称作“第一个”的元素。

②存在唯一的一个称作“最后一个”的元素。

③除第一个元素外，序列中的每个元素均只有一个直接前驱。

④除最后一个元素外，序列中的每个元素均只有一个直接后继。

4.1 顺序表与链表


单链表的插入操作：
s->next=p->next;
p->next=s;
 
单链表的删除操作：
q=p->next;
p->next=q->next;
(上面两句等价于：p->next=p->next->next)

4.2 顺序存储与链式存储

对于顺序存储和链式存储，进行查找的时间复杂度显然就是O（n/2）。

读运算：顺序存储中，无论元素在哪个位置，直接访问数组下标即可，所以是O（1）；链式存储中，如果读取第一个，则为最好情况1，如果读取最后一个，则为最坏情况n，因为要依次访问这些元素的指针域，所以总的为O（（n+1）/2）。

插入运算：顺序存储中，假设元素依次为2、5、6、1、9（n=5），那么最好情况是在最后一个元素后面插入一个新元素，此时不需要移动任何元素，为0，最坏情况是在第一个元素前面插入一个新元素，此时需要将2、5、6、1、9全部向后移动一个位置，为5，所以平均下来需要移动（0+5）/2个元素，即为O（0+5）/2=O（n/2）；链式存储中，只需要移动插入元素位置的前驱指针和后继指针就可以了，所以为O（1）。

删除运算：顺序存储中，假设元素依次为2、5、6、1、9（n=5），那么最好情况是将最后一个元素删除，此时不需要移动任何元素，为0，最坏情况是将第一个元素删除，此时需要将5、6、1、9全部向前移动一个位置，为4，所以平均下来需要移动（0+4）/2个元素，即为O（0+4）/2=O（（n-1）/2）；链式存储中，只需要移动删除元素位置的前驱指针和后继指针就可以了，所以为O（1）。

4.3 栈与队列

栈和队列最重要的一点就是：栈为先进后出；队列为先进先出。（广度队列，深度栈！！！）

对于上面这个习题，元素a、b、c依次入栈，则可能得到哪些出栈序列？

首先，我们可以利用数学中的排列组合知识，3个元素，全排列一共有3！=6种情况，但是出栈真的有6种吗？实则不然！

①元素a进栈，元素a出栈，元素b进栈，元素b出栈，元素c进栈，元素c出栈，此时得到出栈序列为：abc。

②元素a进栈，元素a出栈，元素b进栈，元素c进栈，元素c出栈，元素b出栈，此时得到出栈序列为：acb。

③元素a进栈，元素b进栈，元素b出栈，元素a出栈，元素c进栈，元素c出栈，此时得到出栈序列为：bac。

④元素a进栈，元素b进栈，元素b出栈，元素c进栈，元素c出栈，元素a出栈，此时得到出栈序列为：bca。

⑤元素a进栈，元素b进栈，元素c进栈，元素c出栈，元素b出栈，元素a出栈，此时得到出栈序列为：cba。

为什么出栈序列中没有cab这种情况呢？如果元素c第一个出栈，则说明元素a和b已经在栈中，而a被b压在下面，如果b不出来，a是肯定出不来的，所以不存在cab这种情况。即一共有5中出栈序列。

我们再来看上面这道例题，左端可进可出，右端只能进不能出。四个元素依次入队，得不到哪种出队序列？？？

A选项：e1、e2、e3、e4依次从左端入队，就得到了e4、e3、e2、e1这样的队列，此时依次出队即可得到A选项的结果。

B选项：e1、e2先从左端入队，之后e3从右端入队，最后e4从左端入队，就能得到e4、e2、e1、e3的队列，满足B选项。

C选项：e1、e2先从右端入队，之后e3、e4再从左端入队，就可以得到e4、e3、e1、e2的队列，即符合C选项。

D选项：仔细分析这个队列的入队出队规则，我们发现e1和e2无论如何都是相邻的元素，所以无法得到D选项这样的队列。

4.4 线性表的推广——广义表

例1：广义表LS1的长度为元素的个数（单个元素算一个元素，子表这个整体算一个元素），所以LS1中，a是一个元素，（b，c）是一个元素，（d，e）是一个元素，即长度为3。深度为所含括号的层数，LS1中最外层有一层括号，内部的（b，c）和（d，e）算同样的一层，所以总层数为2，即深度为2。

例2：要获取LS1中的字母b，则需要的操作为：先取表尾，得到（（b，c），（d，e））；再取表头，得到（b，c）；再取表头即可得到字母b。即操作序列为：Head（Head（Tail（LS1）））。

5.树与二叉树

5.1 基本概念

①结点的度：当前结点的孩子结点的个数。比如结点2有两个孩子结点4和5，所以结点2的度为2；而结点4和5没有孩子节点，所以度为0；结点3只有一个孩子节点6，所以度为1。

②树的度：树中所有结点的度最大的那个。比如上面这棵树中，结点的度最大为2，所以该树的度为2。

③叶子结点：度为0的结点。

④内部节点：度不为0的结点，也称为分支结点或非终端结点。除根结点外，分支结点也称为内部结点。

⑤父结点、子结点、兄弟结点：1是2和3的父结点，4和5是2的子结点，4和5、2和3称为兄弟结点。

⑥层次：根结点为第一层，之后层数依次加1。

5.2 二叉树的重要性质

再补充一条性质：具有n个结点的完全二叉树的深度为：「log2n」+ 1（前面的对数部分是向下取整）

5.3 二叉树的遍历

对于上面的二叉树，我们来求一下它的先序、中序、后序以及层次遍历：
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/620243