一、概念
1.顺序存储
顺序存储结构，是指用一段地址连续的存储单元依次存储线性表的数据元素
2.存储方式
在编程语言中，用一维数组来实现顺序存储结构，在C语言中，把第一个数据元素存储到下标为0的位置中，把第 2 个数据元素存储到下标为 1 的位置中，以此类推。
3.长度和容量
数组的长度指的是数组当前有多少个元素，数组的容量值的是数字最大能存放多少个元素，数组越界就是因为超过了自己申请的数组的最大容量
4.数据结构定义
#define DataType int // (1)
struct SeqList {
DataType data[MAXN]; // (2)
int length; // (3)
};（1）数组类型为DataType，定义为int；
（2）SeqList定义的就是一个最多存放MAXN个元素的数组，MAXN代表数组容量；
（3）length代表数组长度，即当前的元素个数
二、常用接口实现
1.只读接口（帮助理解）
（1）索引
索引就是通过数组下标寻找数组元素的过程
DataType SeqListIndex(struct SeqList *sq, int i) {
return sq->data[i]; // (1)i的取值必须为非负整数
}索引的算法时间为O(1)
（2）查找
通过数组元素寻找数组下标的过程
DataType SeqListFind(struct SeqList *sq, DataType dt) {
int i;
for(i = 0; i < sq->length; ++i) { // (1)遍历数组
if(sq->data[i] == dt) {
return i; // (2)找到了，返回下标
}
}
return -1; // (3)没找到，返回-1
}（3）获取长度
获取 数组的长度 指的是查询当前有多少元素。可以直接用结构体的内部变量。C语言代码实现如下：
DataType SeqListGetLength(struct SeqList *sq) {
return sq->length;
}2.可写接口
（1）插入
在数组的第K个元素前插入一个数V，因为数组是连续存储的，那么从K开始的所有元素都得往后移一位，给插入的元素V腾出一个空间，那么当K=0时，所有元素都得移动，所有最坏的时间复杂度为O(n).
C语言代码实现如下：
int SeqListInsert(struct SeqList *sq, int k, DataType v) {
int i;
if(sq->length == MAXN) {
return 0; // (1)当元素个数已经满的时候，说明无法再插入了
}
for(i = sq->length; i > k; i--) {
sq->data[i] = sq->data[i-1]; // (2)从该数组的最后一位往后移动，一直到第K位也后移一位
}
sq->data[k] = v; // (3) 将第K位数变成V
sq->length ++; // (4) 数组长度加一
return 1; // (5) 返回1代表插入成功
}
（2)删除
将数组的第K个元素删除，因为数组存储是连续的，那么第K个元素删除，往后的元素势必要往前移动一位，当K=0时，所有元素都得移动，所以最坏时间复杂度为O(n)
C语言代码实现如下：
int SeqListDelete(struct SeqList *sq, int k) {
int i;
if(sq->length == 0) {
return 0; // (1) 返回0代表失败
}
for(i = k; i < sq->length - 1; ++i) {
sq->data[i] = sq->data[i+1]; // (2) 从前往后覆盖
}
sq->length --; // (3) 数组长度减一
return 1; // (4) 返回1代表删除成功
}
三、优缺点
1.优点
（1）无须为表示表中元素逻辑关系而增加额外的存储空间
（2）随机存取元素时可以达到O(1),效率高
2.缺点
（1）插入和删除时需要移动大量元素
（2）必须一开始就确定存储空间的容量
四、数组相关算法
1、线性枚举
（1）问题描述
给定一个长度为 n(1≤n≤105) 的整型数组，求所有数组元素中的其中的最小值
（2）算法描述
遍历数组，进行条件判断，条件满足则执行逻辑。这里的条件就是 枚举到的数 是否小于 当前最小值，执行逻辑为 将 当前枚举到的数 赋值给 当前最小值；
代码示例如下：
int findMin(int* nums, int numsSize){
int min = 100000;
for(int i = 0; i < numsSize; ++i) { // (1)从第一个元素开始遍历
if(nums[i] < min) { // (2)如果当前枚举到的数小于记录的变量min，则将它赋值给min
min = nums[i];
}
}
return min; // (3)拿到的就是该数组中最小的数
}2、前缀和差分
（1）问题描述
给定一个 n(n≤105) 个元素的整型数组 ai，再给出 m(m≤105)次询问，每次询问是一个区间 [l,r]，求 h(l,r)=∑rk=lak
（2）算法描述
第一个枚举，利用一个数组sum，存储前i个元素的和
第二个枚举，读入m 组数据 l,r，对每组数据，通过 O(1)获取答案，即 sumr-suml-1
代码示例如下：
int sum[maxn];
int* prefixSum(int* nums, int numsSize, int m, int *l, int *r){
int i;
int *ret;
for(i = 0; i < numsSize; ++i) {
sum[i] = nums[i];
if(i)
sum[i] += sum[i-1]; // (1) 计算前缀和
}
ret = (int *) malloc( m * sizeof(int) ); // (2) 需要返回的数组
for(i = 0; i < m; ++i) {
int leftsum = l[i]==0? 0 : sum[l[i]-1]; // (3) 为了防止数组下标越界
int rightsum = sum[r[i]];
ret[i] = rightsum - leftsum; // (4) 差分计算
}
return ret;
}
3、双指针
（1）问题描述
给定一个长度为 n(1≤n≤107)的字符串 s，求一个最长的满足所有字符不重复的子串。
（2）算法描述
如上文所述，这种利用问题特性，通过两个指针，不断调整区间，从而求出问题最优解的算法就叫 “尺取法”，由于利用的是两个指针，所以又叫 “双指针” 算法。
这里 “尺” 的含义，主要还是因为这类问题，最终要求解的都是连续的序列（子串），就好比一把尺子一样，故而得名。
算法描述如下：
（1）初始化 ,
，代表一开始 “尺子” 的长度为 0；
（2）增加 “尺子” 的长度，即 ；
(3）判断当前这把 “尺子” 是否满足题目给出的条件：
(3.a）如果不满足，则减小 “尺子” 长度，即 ，回到 (3)；
(3.b）如果满足，记录最优解，回到 (2）；
核心算法就是：满足条件，j++，反之，i++
代码示例如下：
int getmaxlen(int n, char *str, int& l, int& r) {
int ans = 0, i = 0, j = -1, len; // （1)初始化
memset(h, 0, sizeof(h)); // （2)h代表的是一个哈希表，memset是初始化哈希
哈希表记录的是当前枚举的区间S[i，j]中每个字符的个数
while (j++ < n - 1) { // （3)j往右移动
++h[ str[j] ]; // （4)在哈希表中记录字符的个数
while (h[str[j]] > 1) { // （5)当h[str[j]] > 1时，说明出现了重复字符串str[j]
左端点i开始右移，直到没有重复字符为止
--h[ str[i] ];
++i;
}
len = j - i + 1;
if(len > ans) // （6)len = j - i + 1;记录当前最优解的长度，更新
ans = len, l = i, r = j;
}
return ans;
}4、二分枚举
（1）问题描述
给定一个 n(n≤106)个元素的有序整型数组和一个 target值，求在 O(log2n) 的时间内找到值为 target 的整型的数组下标，不存在则返回 -1。
（2）算法描述
(a)初始情况下，令右端点r=n-1；左端点l=0；
(b)生成一个中间值mid = (r+l)/2；
(b.1)目标等于mid，返回mid；
(b.2)目标元素大于mid, l=mid+1;
(b.3)目标元素小于mid, r=mid-1;
(c)当l>r的时候，则说明没有找到目标值，返回-1，否则，回到b，继续迭代
代码示例如下：
int search(int *nums, int numsSize, int target) {
int l = 0, r = numsSize - 1; // (1)初始化l,r
while(l <= r) { // (2) 一直迭代左右区间的端点，直到左端点大于右端点结束
int mid = (l + r) >> 1; // (3)中间点
if(nums[mid] == target) {
return mid; // (4)找到目标，返回下标mid
}else if(target > nums[mid]) {
l = mid + 1; // (5)左端点移动到 mid+1
}else if(target < nums[mid]) {
r = mid - 1; // (6)右端点移动到 mid-1
}
}
return -1; // (7)找不到给定值，返回-1
}5、三分枚举
三分枚举 类似 二分枚举 的思想，也是将区间一下子砍掉一块基本完全不可能的块，从而减小算法的时间复杂度。只不过 二分枚举 解决的是 单调性 问题。而 三分枚举 解决的是 极值问题。
6、插入排序
（1）问题描述
给定一个n个元素的数组，数组下标从0开始，采用插入排序将数组升序排列
（2）算法描述
（1） 循环迭代变量 ；
（2） 每次迭代，令 ，
，循环执行比较
和
，如果产生
则执行
。然后执行
，继续执行 （2）；否则，跳出循环，回到 （1）。
示例代码如下：
void InsertSort(int n, int *a) {
int i, j;
for(i = 1; i < n; ++i) {
int x = a[i]; // (1)认为前i-1个数都是排好序的，令x=a[i]
for(j = i-1; j >= 0; j--)
{ // (2)逆序的枚举所有已经排好序的数
if(x <= a[j])、
{ // (3)枚举的数大于插入的数x，则当前数后移一个位置
a[j+1] = a[j];
}else
break; // (4)否则跳出循环
}
a[j+1] = x; // (5)将x插入到合适的位置
}
}7、选择排序
（1）问题描述
给定 个元素的数组，数组下标从
开始，采用「 选择排序 」将数组按照 「升序」排列
（2）示例代码
void Swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}void SelectionSort(int n, int *a) {
int i, j;
for(i = 0; i < n - 1; ++i) {
int min = i; // (1)记录最小值下标
for(j = i+1; j < n; ++j) { // (2)开始遍历，min下标对应的数组的值为最小
if(a[j] < a[min]) {
min = j;
}
}
Swap(&a[i], &a[min]); // (3)第i个元素个最小的元素进行交换
}
}
8、冒泡排序
void MaoPao(int n,int *a)
{
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-1-i;j++)
{
if(a[j]<a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}时间复杂度为O(n2)