计蒜客课程数据结构(顺序表)

2018-06-18 00:06:09来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

1.线性表是由相同数据类型的 n 个数据元素a0,a1,......,an-1 组成的有限序列。一个数据元素可以由若干个数据项组成。若用 L 命名线性表,则其一般表示如下:

     L=(a0,a1,......,an-1)

其中, a0?? 是唯一的“第一个”数据元素,又称为表头元素;an-1?? 是唯一的“最后一个”数据元素,又称为表尾元素。

线性表按照存储结构,可以分为顺序表和链表两种类型。

2.顺序表是在计算机内存中以数组形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。

3.顺序表最主要的特点是可以进行 随机访问,即可以通过表头元素的地址和元素的编号(下标),在 O(1)O(1) 的时间复杂度内找到指定的元素。

顺序表的不足之处是插入和删除操作需要移动大量的元素,从而保持逻辑上和物理上的连续性。

4.顺序表的构造,插入,扩容,删除,遍历

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 class Vector {
 5 private:
 6     int size, length;                //顺序表当前的最大容量和当前顺序表中的元素个数
 7     int *data;                       //动态分配,指向存储元素的数组的指针
 8 public:
 9     Vector(int input_size) {         //构造函数,构造一个容量为input_size的顺序表
10         size = input_size;
11         length = 0;
12         data = new int[size];        //让data指向一段连续size个int空间
13     }
14     ~Vector() {                     //析构函数
15         delete[] data;              //将data指向的空间回收
16     }
17     bool insert(int loc, int value) {//顺序表的插入
18         if (loc < 0 || loc > length) {//判断插入的位置是否合法
19             return false;
20         }
21         if (length >= size) {           //判断容量是否已经达到上限
22             return false;               //这句可注释掉并调用扩容操作
23         }
24         for (int i = length; i > loc; --i) { //loc位置后元素后移
25             data[i] = data[i - 1];
26         }
27         data[loc] = value;
28         length++;
29         return true;
30     }
31     void expand(){                      //顺序表的扩容
32         int *old_data=data;
33         size=size*2;
34         data=new int[size];
35         for(int i=0;i<length;i++){
36             data[i]=old_data[i];
37         }
38         delete[]old_data;
39     }  
40     int search(int value) {                 //顺序表的查找
41         for (int i = 0; i < length; ++i) {
42             if (data[i] == value) {
43                 return i;
44             }
45         }
46         return -1;
47     }
48     bool remove(int index) {               //顺序表的删除
49         if (index < 0 || index >= length) {
50             return false;
51         }
52         for (int i = index + 1; i < length; ++i) {
53             data[i - 1] = data[i];
54         }
55         length = length - 1;
56         return true;
57     }
58     void print() {                            //顺序表的遍历
59         for(int i=0;i<length;i++){
60             if(i>0){
61                 cout<<" ";
62             }
63             cout<<data[i];
64         }
65         cout<<endl;
66     }
67 };
68 int main() {
69     Vector a(2);
70     cout << a.insert(0, 1) << endl;
71     cout << a.insert(0, 2) << endl;
72     a.print();
73     cout << a.remove(1) << endl;
74     a.print();
75     cout << a.search(0) << endl;
76     cout << a.search(1) << endl;
77     return 0;
78 }

 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:c/c++常见面试题

下一篇:LRU页面置换算法