线性表总览
** 线性表是由相同数据类型的 nn 个数据元素 a0，a1 ... an−1 组成的有限序列。**一个数据元素可以由若干个数据项组成。若用 L命名线性表，则其一般表示如下：
其中， a0 是唯一的“第一个”数据元素，又称为表头元素；an−1 是唯一的“最后一个”数据元素，又称为表尾元素。
顺序表是线性表的一种顺序存储形式。
换句话说，线性表是逻辑结构，表示元素之间一对一的相邻关系；而顺序表是指存储结构，是指用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
设顺序表的第一个元素 a0 的存储地址为 Loc(a0)，每个元素占 d个存储空间，则第 i 个元素的地址为 Loc(ai−1)=Loc(a0)+(i−1)∗d
基本操作及示例代码
#include <iostream>
#include <cstring>
using namespace std;
class Vector {
private:
int size, length;
int *data;
public:
```
##构造方法
```
Vector(int input_size) {
size = input_size;
length = 0;
data = new int[size];
}
~Vector() {
delete[] data;
}
```
>**组成：size：表的容量
length：表的的实际大小，元素的个数
data【】数组**
##插入
```
bool insert(int loc, int value) {
//参数loc为位，表示插到data[loc]处，实际是表的第loc+1个元素
if (loc < 0 || loc > length) {
return false;
}
if (length >= size) {
expand();
}
for (int i = length; i > loc; --i) {
data[i] = data[i - 1];
}
data[loc] = value;
length++;
return true;
}
```
> 思路：首先判断插入是否合法，插入位置需要在，表数据所在的区间，插入范围【0，length】（位），0表示表头，length表尾
其次判断数据长度是否大于表的大小，如是则扩容
然后，进行插入操作：把表中元素从第length个元素（就是data[length-1]）不断地向后挪一位,知道
data[loc](标的第loc+1个元素)。此时把插入值插入。
最后把length动态加一。
##删除
```
bool remove(int index) {//参数也是位，即删除data[index],表中的index+1个元素，时间成本O（n）.
if (index < 0 || index >= length) {
return false;
}
for (int i = index + 1; i < length; ++i) {
data[i - 1] = data[i];
}
length = length - 1;
return true;
}
```
> 思路：首先判断删除是否合法，插入位置需要在，表数据所在的区间，插入范围【0，length-1】（位），
##遍历
```
void print() {
for(int i=0;i<length;i++)
{
if(i>0){
cout<<" ";
}
cout<<data[i];
}
cout<<endl;
}
```
## 基于无序向量的无脑查找
```
int search(int value) {
for(int i=0;i<length;i++)
{
if(data[i]==value)
{
return i;
}
}
return -1;
}
```
***
##扩容
```
void expand(){
int *old_data=data;
size=size*2;
data=new int[size];
for(int i=0;i<length;i++){
data[i]=old_data[i];
}
delete[] old_data;
}
};
```
***
##无序向量唯一化
每步迭代所需时间为O(n)，总体复杂度应为O(n2)
```
1. template <typename T> int Vector<T>::deduplicate() { //删除无序向量中重复元素（高效版）
2. int oldSize = _size; //j记录原始规模
3.Rank i = 1; //从_elem[1]开始
4. while (i < _size) //自前向后逐一考查各元素_elem[i]
5.(find(_elem[i], 0, i) < 0) ? //在其前缀中寻找雷同者（至少一个）
6.i++ : remove(i); //若无雷同则继续考查其后继，否则删除雷同者
7 return oldSize - _size; //向量规模变化量，即被删除元素总数
8 }
```
##有序向量唯一化
低效版
```
1 template <typename T> int Vector<T>::uniquify() { //有序向量重复元素删除算法（低效版）
2 int oldSize = _size; int i = 1; //当前比对元素的秩，起始于首元素
3 while (i < _size) //从前向后，逐一比对各对相邻元素
4 _elem[i - 1] == _elem[i] ? remove(i) : i++; //若雷同，则删除后者；否则，转至后一元素
5 return oldSize - _size; //向量规模变化量，即被删除元素总数
6 }
```
>这里的运行时间， 主要消耗while循环， 共需迭代_size - 1 =n - 1步。
所有元素均雷同时，用于所有这些remove()操作的时间总量将高达：
(n - 2) + (n - 3) + ... + 2 + 1= O(n2)
高效版
>稍加分析即不难看出，以上唯一化过程复杂度过高的根源是，在对remove()接口的各次调
用中，同一元素可能作为后继元素向前移动多次，且每次仅移动一个单元。
每一组重复元素，都必然前后紧邻地集中分布。 可以
区间为单位成批地删除前后紧邻的各组重复元素，并将其后继元素（若存在）统一地大跨度前移。
具体地， 若V[lo, hi)为一组紧邻的重复元素，则所有的后继元素V[hi, _size)可统一地整体
前移hi - lo - 1个单元。
按照上述思路，得到唯一化算法的新版本。
```
1 template <typename T> int Vector<T>::uniquify() { //有序向量重复元素剔除算法（高效版）
2 Rank i = 0, j = 0; //各对互异“相邻”元素癿秩
3 while (++j < _size) //逐一扫描，直至末元素
4 if (_elem[i] != _elem[j]) //跳过雷同者
5 _elem[++i] = _elem[j]; //収现丌同元素时，向前秱至紧邻亍前者右侧
6 _size = ++i; shrink(); //直接截除尾部夗余元素
7 return j - i; //向量规模变化量，即被删除元素总数
8 }
```
##有序性甄别
>作为无序向量的特例，有序向量自然可以沿用无序向量的查找算法。然而，得益于元素之间
的有序性，有序向量的查找、唯一化等操作都可更快地完成。 因此在实施此类操作之前，都有必
要先判断当前向量是否已经有序，以便确定是否可采用更为高效的接口。
```
1 template <typename T> int Vector<T>::disordered() const { //迒回向量中逆序相邻元素对癿总数
2 int n = 0; //计数器
3 for (int i = 1; i < _size; i++) //逐一检查_size - 1对相邻元素
4 if (_elem[i - 1] > _elem[i]) n++; //逆序则计数
5 return n; //x向量有序当且仅当n=0；
6 }
```
```java
int main() {
Vector a(2);
cout << a.insert(0, 1) << endl;
cout << a.insert(0, 2) << endl;
a.print();
cout << a.remove(1) << endl;
a.print();
cout << a.search(0) << endl;
cout << a.search(1) << endl;
return 0;
}
```
网友评论