备考蓝桥杯：次序表详解（静态次序表，vector用法）

目次

1.次序表的概念
2.静态次序表的实现
总代码
3.stl库动态次序表vector
测试代码

---

1.次序表的概念

要明白次序表，我们要先相识一下什么是线性表
线性表是n个具有类似特性的数据元素的序列

这就是一个线性表 a1是表头 a4是表尾 a2是a3的前驱 a3是a2的后继
空表体现一个元素也没有，用空寂体现
用次序存储的方式实现的线性表就叫次序表
用链式存储的方式实现的线性表就是链表


2.静态次序表的实现

   由于实现动态次序表要很多很多delete和new，斲丧很多的时间复杂度，而且我们已经有vecor这个东西了，以是我们就不实现动态的次序表了，我们只实现一下静态次序表
  创建静态次序表

1. const int N = 1e6 + 10;
2. int a[N],n;

复制代码

静态次序表的尾插

1. void push_back(int x)
2. {
3.         a[++n]=x;
4. }

复制代码

测试尾插

   由此可见，尾插的时间复杂度为O（1）
  静态次序表的头插

1. void push_front(int x)
2. {
3.         //我们头插要把所有元素向右移动一位，给我们要插入的元素腾出位置出来
4.         //但是如果我们从第一个元素右移，就会有覆盖的情况，所以我们从最后一个元素开始右移
5.         //把[1,n]的元素统一后移1位
6.         for(int i = n;i>=1;i--)
7.         {
8.                 a[i+1] = a[i];
9.          }
10.          a[1] = x;
11.          n++;
12. }

复制代码

头插的时间复杂度是O（N）
测试头插

恣意位置插入

1. void insert(int p,int x)
2. {
3.         //和我们头插保持一致，在p之前插入 ，头插是在下标为0之前插入
4.         //把[p,n]的元素统一右移
5.         for(int i =n;i>=p;i--)
6.         {
7.                 a[i+1] = a[i];
8.         }
9.         a[p] = x;
10. }

复制代码

最坏情况下就是头插，以是我们的时间复杂度还是O（N）
测试恣意位置插入

尾删
我们直接把有用元素减1，就能实现尾删操纵，我们尾删的时间复杂度是O（1）

1. void pop_back()
2. {
3.         n--;
4. }

复制代码

测试尾删

头删

1. void pop_front()
2. {
3.         for(int i = 2;i<=n;i++)
4.         {
5.                 a[i-1] = a[i];
6.         }
7.         n--;
8.        
9. }

复制代码

我们头删的时间复杂度是O（N）
测试代码

恣意位置删除

1. void erase(int p)
2. {
3.         for(int i = p+1;i<=n;i++)
4.         {
5.                 a[i-1] = a[i];
6.         }
7.         n--;
8. }

复制代码

按值查找

1. int find(int x)
2. {
3.         for(int i = 1;i<=n;i++)
4.         {
5.                 if(a[i]==x)
6.                 return i;
7.         }
8. return 0;
9. }

复制代码

测试查找操纵

按位查找

1. int at(int p)
2. {
3.         return a[p];
4. }

复制代码

清空操纵

1. void clear()
2. {
3.         n = 0;
4. }

复制代码

修改操纵

1. void change(int p,int x)
2. {
3.         a[p] = x;
4. }

复制代码

总代码

1. #include <iostream>using namespace std;const int N = 1e6 + 10;
2. int a[N],n;void push_back(int x)
3. {
4.         a[++n]=x;
5. }void push_front(int x)
6. {
7.         //我们头插要把所有元素向右移动一位，给我们要插入的元素腾出位置出来
8.         //但是如果我们从第一个元素右移，就会有覆盖的情况，所以我们从最后一个元素开始右移
9.         //把[1,n]的元素统一后移1位
10.         for(int i = n;i>=1;i--)
11.         {
12.                 a[i+1] = a[i];
13.          }
14.          a[1] = x;
15.          n++;
16. }void insert(int p,int x)
17. {
18.         //和我们头插保持一致，在p之前插入 ，头插是在下标为0之前插入
19.         //把[p,n]的元素统一右移
20.         for(int i =n;i>=p;i--)
21.         {
22.                 a[i+1] = a[i];
23.         }
24.         a[p] = x;
25. }void pop_back()
26. {
27.         n--;
28. } void Print(){        for(int i = 1;i<=n;i++)        {                cout << a[i] << " ";        }        cout << endl;}void pop_front()
29. {
30.         for(int i = 2;i<=n;i++)
31.         {
32.                 a[i-1] = a[i];
33.         }
34.         n--;
35.        
36. }void erase(int p)
37. {
38.         for(int i = p+1;i<=n;i++)
39.         {
40.                 a[i-1] = a[i];
41.         }
42.         n--;
43. }int find(int x){        for(int i = 1;i<=n;i++)        {                if(a[i]==x)                return i;        }        return 0;}void clear()
44. {
45.         n = 0;
46. }void change(int p,int x)
47. {
48.         a[p] = x;
49. }
50. int at(int p)
51. {
52.         return a[p];
53. }int main(){        push_back(2);        Print();        push_back(5);        push_back(1);        push_back(3);        Print();        push_front(10);        Print();        insert(3,0);        Print();//        cout << "尾删" << ": ";//        pop_back();//        Print();//        cout << "头删" << ": ";//        pop_front();//        Print();//cout << "删除" << ":";//erase(3);//Print(); for(int i = 1;i<=10;i++){        cout << "查找" << i << ":";        cout << find(i)<<" "; } }

复制代码

3.stl库动态次序表vector

创建vector

除此之外，我们vector的<>里还可以放stl和各种数据范例，vector<int> a[5]体现的就是创建一个元素为vector <int>的数组
三种打印方式 1 size（）返回元素个数

2.迭代器

3.范围for

resize（可以扩充元素个数，也可以缩容）

扩大的元素值默以为0

尾插和尾删，和上面静态的差不多的
不多报告
empty()判空

front和back分别是取头元素和尾元素

clear()清空元素

测试代码

1. #include <iostream>
2. #include <vector>
3. using namespace std;
4. const int N = 10;
5. void Print(vector<int>& pa)
6. {
7.         //用size返回元素个数
8.         for (int i = 0; i < pa.size(); i++)
9.         {
10.                 cout << pa[i] << " ";
11.         }
12.         cout << endl;
13.         //用begin（） end（）迭代器
14. //        for (auto it = pa.begin(); it != pa.end(); it++)
15. //        {
16. //                cout << *it << " ";
17. //        }
18. //        cout << endl;
19. //        //范围for （C++11支持）
20. //        for (auto e : pa)
21. //        {
22. //                cout << e << " ";
23. //        }
24. //        cout << endl;
25. //}
26. }
28. int main()
29. {
30.         vector <int> a1;//创建一个a1 的可变长数组,size为0
31.         vector <int> a2(N);//创建一个a2的可变长数组，size为N，元素值初始化为0
32.         vector <int> a3(N, 2);//创建一个a3的可变长数组，size为N 元素初始化为2
33.         vector <int> a4 = { 1,2,3,4,5 };
34.         vector <string> s1;
35.         vector <int> a[5];
36.         vector <int> aa(5, 1);
37.         aa.resize(10);
38.         aa.resize(3);
39.         for (int i = 3; i <= 6; i++)
40.         {
41.                 a1.push_back(i);
42.         }
43.         Print(a1);
44.         a1.pop_back();
45.         cout << "头为" << a1.front() << "尾为" << a1.back();
46.         Print(a1);
47.         //while (!a1.empty())
48.         //{
49.         //        a1.pop_back();
50.         //}
51.         a1.clear();
52.         cout << a1.size() << endl;
53.         return 0;
54. }

复制代码