前瞻

一些基本概念

逻辑结构

逻辑结构包含集合(前后没关系,也是一种关系)、线性关系(前后一对一)、非线形关系(一对多、多对一、多对多)

存储结构

存储结构包括链式存储和顺序存储

表

顺序表ArrayList（顺序存储的线性表）

通过下标（索引）来反应数据的逻辑结构。即下标1是下标0的下一个数据
数组来反应存储结构，即数据是连续存储的。

1
2
3
4
5
6
typedef struct
{
    int   capacity; // 顺序表容量
    int   last;     // 最末元素下标
    int * data;     // 顺序表，以整型数据为例
}sequenceList;

增删： 在头部插入（删除），时间n . 在尾部插入（删除）时间1 .
每次头部的增删都要将所有元素移动一位

链表LinkList（链式存储的线性表）

排序方式

每种排序方式的实现可能有好多种，看经典代码和参透基本思想。

冒泡排序 Bubble Sort

比较相邻元素，将大（小）值一步步换到一边。
每次大循环会将最大（小）值排到正确的位置。像泡泡一样一个一个冒出来。

选择排序

开始时已排序部分为空，遍历所有未排序部分，找到最小值放到已排序部分。继续遍历未排序部分，找最小的插入。

插入排序和希尔排序 Insert Sort

假设一个边缘元素是有序的，遍历其他所有元素，和上一个遍历的元素比较，找到它的相对正确位置，插入。

希尔排序则是先根据间距梯度，先将元素分组，在调用经典插入排序。
这样可以减少插入次数

快排序 Quick Sort （时间复杂度nlogn，因此常用）

两个特点
1、partition算法（左右两个指针通过与基准大小判断和交换元素，最终让指针相遇停止）算法结果即能够让基准值左右两边是小值和大值
2、递归调用。

快排序的实现方式很多，经典的是将最左值即a[0]值作为pivot，也可以将随机位置和最右值作为pivot

归并排序 Merge Sort

归并排序的主要思想

二叉树

查找二叉树是一种严格有序的，规定左中右为相对小中大的顺序。可以让查找的速度大大降低。而且二叉树通过递归进行各种操作，代码量相对比较小。