数据结构(c++ ) 线性表（一）顺序存储的实现

Dear 丶 2022-05-26 06:45 203阅读 0赞

### 1.0 线性表的顺序存储及实现 ###

啥子叫做线性表呢，原来我的理解就是数组，后来才知道这么理解并不准确，但是也差不多吧

**线性表：** 是表 是一种具有相同类型的数据元素的有序序列

#### 1.1 线性表的顺序存储结构——–顺序表 ####

线性表的顺序存储结构通常用一维数组实现 线性表的序号是从1开始的

因为线性表可能会插入数据，所以数组的大小要大于线性表的大小

例子

#include <iostream>
    
    using namespace std;
    const int maxSize = 100 ;//默认数组大小 
    class Array{
        private:
            int aq[maxSize];
            int length;
        public:
             Array(int a[],int n){
                length = n;//线性表的长度
                 for(int i =0;i<n;i++){
                    aq[i] = a[i];//赋值 
                 }
             }
             //增
             void addElement(int i,int value){
       //线性表的序号从1开始  所以i>0 
    
                if(length >= maxSize) throw "上溢出了";
                if(i<1 || i>length) throw "访问越界"; 
                for(int j = length;j >= i;j--){
                    aq[j] = aq[j-1];            
                 } 
                 aq[i-1] = value;
                 length++;
             } 
             //删
             int  deleteElement(int i){
       //位置从1开始 
    
                if(length >= maxSize) throw "上溢出了";
                if(i<1 || i>length) throw "访问越界"; 
                for(int j = i;j < length;j++){
                    aq[j-1] = aq[j];            
                 } 
    
                 length--;
                 return 1;
             } 
             //查 
             int selectValue(int value){
    
                for(int i = 0;i < length;i++ ){
                    if(aq[i] == value){
                        return i+1;
                    }
                }
                //0 代表不存在 
                return 0;
             }
             //遍历        
             void showElements(){
                for(int i = 0;i < length;i++){
                    cout<<"aq["<<i<<"] = "<< aq[i]<<endl;
                 }
             } 
    };
    
    int main(){
        int a[] = {
       1,2,3,4,5,6};
        //构造方法赋值 
        Array arr(a,6);
        arr.addElement(3,49);
        arr.deleteElement(3);
        arr.showElements();
        cout<<arr.selectValue(4);
    }

结果：  
![这里写图片描述][70]

分析：

1.  线性表 按值查的平均时间复杂度是O(n)，最好是O(1)，最次是O(n); 按位查的时间复杂度是O(1)
2.  线性表 增加元素的平均时间复杂度是O(n) 最好是O(1)，最次是O(n);
3.  线性表 删除操作的平均时间复杂度为O(n) 最好是O(1)，最次是O(n);
4.  线性表 遍历操作的时间复杂度为O(n)

[70]: /images/20220526/daa436dcbfd9456c87044c8bb57ec93f.png