本章重点：数据结构相关名词术语的含义。难点：时间复杂度的估算。

数据：是客观事物的符号表示。能被输入到计算机中被程序处理的符号的总称。 数据元素：也称顶点，结点或记录。数据的基本单位。 数据项：最小单位。 数据对象：性质相同的数据元素集合。 数据结构：带结构的相同性质数据元素集合。结构是一种或多种关系。

以上不知道怎么背，随便过过吧。

逻辑结构=数据元素+关系。 四类基本结构：

后三个是非线性结构。（即四类中除了线性结构的）

两种存储结构：顺序存储（数组），链式存储（结构体和指针）。 差别： 顺序存储：相邻位置表示元素逻辑关系。 链式存储：指针信息表示元素逻辑关系。

算法： 五特性：有穷，确定，可行，输入，输出。 优劣标准：正确性，可读性，健壮性，高效性。

时间复杂度：一般是最深层循环内的语句频度。

两个没什么用的表：（？）

重难点：顺序表和链表。

概念：非空的线性表或线性结构是一个有限数据元素的有序集合。 特点：存在唯一一个第一个，最后一个数据元素；每个数据元素只有一个前驱（除第一个）和后继（除最后一个）。 存储：连续地址。是随机存储结构。

线性表 线性表的一些操作： GetElem: i是位置。注意特判范围。第1个存在0号位，故取值要i-1；

LocateElem:存在就返回位序，不存在就返回0； 地址从0开始，位序从1开始。故return i+1;

时间复杂度O(n); 平均查找长度：(n+1)/2;

折半查找 就是二分。线性表要有序且有限。 跳出循环的条件是：找到了（a[mid]==e）或范围缩小到0也没找到.故循环条件是while**(l //j和j+1的比较 }

特点： 稳定，可用于链式，移动次数多。

第一趟确定最大的，第二趟确定第二大的…以此类推，大泡泡会沉底

快速排序 交换类。 动图来自：这里：以下动图均来自这里 如： 枢纽是：49—27—76； 逻辑大概是：第一次枢纽是第一个数，第二次是第一堆的第一个数，第三次是第二堆的第一个数 简述：枢纽暂放杂r[0]中，比枢纽小的移到枢纽前，大的后。 做了个小视频，是上面例子的快排示范，但是放不下orz

快排时间复杂度O(nlog2n) 空间复杂度：最好O(log2n),最坏O(n)

不稳定。要用在顺序结构。适合记录无序，n较大的情况。

简单选择排序 选择类，即选出一个关键字最大/小的记录，并移到法定位置。

例子： 这里选的是无序中最小的放入有序中。 时间复杂度O(n^2); 空间复杂度O(1); 不稳定。可顺序可链式结构。 移动记录次数较少，比直接插入快。

堆排序 堆排序是利用堆的特性对记录序列进行调整堆的排序方法。

动图： 时间复杂度O(nlog2n); 空间复杂度O(1); 不稳定。只可顺序。 适用于n较大或TOPN问题。

归并排序 将两个或以上有序子序列归并为一个有序序列。 代码：若要从小到大：小的就往下放并移动指针，直到有一条到结尾，另一条直接接上： 举个例子：两两比较！ 时间复杂度：O(nlog2n) 空间复杂度：O(n); 稳定，可链式。 要额外空间！

排序的综合比较 选择何种排序方式考虑原则：

红框框要考。