线性表：
在数据元素的非空有限集中
- 存在唯一的一个被叫做“第一个”的数据元素
- 存在唯一的一个被叫做“最后一个”的数据元素
- 除第一个之外，集合中的每个数据元素均只有一个前驱
- 除最后一个之外，每个集合元素均只有一个后继
- 数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构
- 线性表有：数组、队列、链表以及堆栈
- 非线性表有： 二维数组，多维数组，广义表，树 (二叉树等)，图
数组：
它可以存储一个固定大小的相同类型元素的顺序集合，是相同类型的，不可以扩展容量。
向量：
但其大小可以不预先指定，并且自动扩展。 它可以像数组一样 被操作，由于它的特性我们完全可以将vector 看作动态数组。（动态扩展：不是在原空间后添加新空间 而是找更大的空间 把数据拷贝到新的空间 释放原空间）
矩阵：
一般用二维数组来存储矩阵元
压缩存储：为多个值相同的元只分配一个存储空间；对零元不分配空间。
- 特殊矩阵 ：有相同的元素或零元素在矩阵中的分布有一定的规律
- 稀疏矩阵：与特殊矩阵相反
对称矩阵的压缩：（根据对角线对称）
可以把对称矩阵压缩为一维数组：
- 通过下三角压缩 K=i*（i-1）/2+j-1 i>=j
- 通过上三角压缩 K=j*（j-1）/2+i-1 i<j
三对角矩阵：主对角线上下两条对角线，其他皆为0
K=2+（i-2）*3-（i-j）+2 -1
K=2i+j-3
稀疏矩阵：（数据大多数都为0，当非0元素<=5%时为稀疏矩阵）
稀疏矩阵的压缩方法：
- 三元组
- 十字链表
三元组：
（（x，y），data），使用x，y来存储位置，data存储数据
十字链表：
当矩阵中的零元个数和位置在操作过程中变化较大时，使用十字链表。
十字链表的格式：
∧的作用：代表没有相关联的链域
∧的使用规则;
- 行列中的使用：如果该行或该列全为0，则使用∧
- 后继链域的使用：如果该位置的同行或同列后全为0，使用∧
数组的运用：
1.数组以列或行为主存放的区别：
- 以列为主存取：按照列的方式存储
- 以行为主存取：按照的方式存储
A[i,j] 每个元素的长度为3，i的范围为1-8 j的范围为1-10，首地址为G
计算A[5,8]的地址
红线位置表示地址的偏移量
- 以列为主存取：（(7*8+5)-1）*3=180
- 以行为主存取：（4*10+8-1）*3=141
2.对a[0]的访问
char c[2][3] = { {'a','b','c'},{'1','\0','2'} };printf("%s", c[0]);c[0]代表的是以c[0][0]为首地址的一维数组（将数组c摊开）
%s 到\0结束
结果为：abc1
Vector的模板类：
（只是实现简单的功能，有些地方并未严格处理）
#define MAX_Capacity 100 //默认容量template<class T>
class Vector
{
public:Vector(int a = 0, int b = MAX_Capacity, T c = 0)//默认的构造函数{_elem = new T[_capacity=b];//开辟空间for (_size = 0; _size < a; _elem[_size++] = v);//初始化数据}~Vector(){delete[]_elem;//释放空间}
private:int _size;//规模int _capacity;//容量T* _elem;//数据
};可以添加以下功能：
1.判空
template<class T>
bool Vector<T>::empty()//判空
{return !_size;
}2.查看规模
template<class T>
int Vector<T>::size()//规模
{return _size;
}3.扩容
template<class T>
void Vector<T>::expand()//扩容
{if (_size < _capacity) return;//规模小于容量，不需要扩容if (_capacity < MAX_Capacity) _capacity = Default_Capacity;//当容量小于默认容量时设为默认容量//这两个都不满足时扩容T* oldelem = _elem;//用一个新指针指向内容_elem = new T[_capacity <<= 1];//_elem的容量翻倍for (int i = 0; i <= _size; i++){_elem[i] = oldelem[i];}delete[] oldelem;//释放空间
}4.缩容
template<class T>
void Vector<T>::shrink()//缩容
{if (_capacity < Default_Capacity << 1) return; //防止收缩后小于Default_Capacityif (_size << 2 > _capacity) return;//以1/4为边界T* oldelem = _elem;_emem = new[_capacity >>= 1];//容量减半for (int i = 0; i < size; i++){_elem[i] = oldelem[i];}delete[] oldelem;//释放原空间
}5.重载下表操作符
template<class T>
T& Vector<T>::operator[](int a)const
{return _elem[a];
}6.复制区间A[a.b]
template<class T>
void Vector<T>::copyFrom(T const *A,int a,int b)//复制区间
{_elem = new T[_capacity = (b - a) << 1];//开辟区间两倍容量_size = 0;//复制，把规模置0while (a < b)//复制区间[a,b){_elem[_size++] = A[a++];}
}7.重载=
template<class T>
Vector<T>& Vector<T>::operator=(Vector<T>const&A)//重载[]
{if (_elem)delete[] _elem;//_elem有内容的话就释放内容copyFrom(A._elem, 0, A.size());//整体复制return *this;
}7.删除
template<class T>
void Vector<T>::remove(int t)//删除位置为t的数据
{if (t<0 || t>=_size) return;//如果t不符合范围，则返回0for (int i = t; i < _size; i++){_elem[i] = _elem[i + 1];}--_size;
}8.删除一个区间
template<class T>
int Vector<T>::remove(int a,int b)//删除一个区间
{if (a == b)return 0;while (a < b){_elem[a++] = _elem[b++];}_size = _size - (b - a);shrink();//是否要扩容return b - a;
}
9.插入元素
template<class T>
void Vector<T>::insert(int a,T const& b)//插入一个数据
{expand();//是否需要扩容if (int i = _size; i > r; i--){_elem[i] = elem[i - 1];}_elem[a] = b;
}
10.对区间排序
template<class T>
void Vector<T>::sort(int a,int b)//对区间排序
{for（int i = a; i < b- 1; i++）{for (int j = a; j < b- i - 1; j++){if (arr[j] > arr[j + 1]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}
11.对整体排序
template<class T>
void Vector<T>::sort()//对整体排序
{sort(0, size());
}11.置乱器
template<class T>
void Vector<T>::permute()//对整体排序
{for (int i = _size; i > 0; i--){swap(elem[i-1],V[rand()%i])//v[i-1]与[0,i)中的某一个元素交换}
}
12.查找
template<class T>
void Vector<T>::search(T const& g,int a,int b)//查找
{while (a < b){int mi = (a + b) >> 1;(e < _elem[mi]) ? b = a : a = mi + 1;}return --a;
}
