顺序表简介

特点：

1、使用一组地址连续的存储单元依次存储表中的数据元素，常见的就是使用数组去实现。

2、顺序表中逻辑相邻的数据元素，在物理内存上也相邻。

3、顺序表中的任意数据元素都可随机访问，即访问一个数据元素的时间复杂度为O(1)。

 假设每个数据元素的占用内存大小为L，表中第一个数据元素的地址为LOC(a1)，难么第i个元素的地址就可以直接计算出来：LOC(ai) = LOC(a1) + (i-1)*L，这是顺序表支持随机访问的基本依据。

 

优点：访问表中的元素很快，时间复杂度为O(1)。

缺点：插入，删除元素需要移动大量的元素，时间复杂度为O(n) 。

 

因此如果我们在编程中需要这样一种线性表数据结构：构造后对元素的访问操作很频繁，而很少进行增，删等元素位置的调整操作，那么就可以考虑使用顺序表。

 

 

 

代码实现

#include
     
      #include
      
            #include
       
        using namespace std;class ArrayList{private:     enum{ INCREMENT_SIZE = 20,    //容量不足时，每次增加10个           INIT_CAPACITY = 10      //初始容量20         };     int   size;                  //实际元素个数     int   capacity;              //容量     int*  elements;              //存储元素的数组的基地址    //确保表的容量至少为 reqCapacity 个。否则就增加容量 。     void ensureCapacity(int reqCapacity)     {         int* nelements;         if(capacity
        
         size || index < 0) return false;  //索引不合法        ensureCapacity(size+1);            for(int i=size-1;i>=index;--i)        {            elements[i+1] = elements[i];        }                    elements[index] = e;        size++;         return true;              }              /*    * 删除索引为index 的元素 。    * 合法的index值为  [0,size-1] ，当index=0时，删除的是第一个元素。    * 当index为size-1时，删除的是最后一个元素    **/    bool remove(int index)    {        if(index>=size || index <0) return false;    //索引不合法        for(int i=index;i
         
          =size || index < 0)          //如果索引不合法 ，则抛异常            throw std::out_of_range(0);        return elements[index];       }    //重载索引运算符[]，元素可读可写版本    int& operator[](int index)    {        if(index >=size || index < 0)            throw std::out_of_range(0);        return elements[index];    }}; //end classint main(){    ArrayList list1;        list1.append(1);    list1.append(2);    list1.append(5);        list1.insert(0,100);        list1.remove(2);        list1.show();    return 0;}
         
        
       
      
     

 

 

顺序表的短板

插入元素，时间复杂度 O(n)

 

插入为 第 i  个 元素，则需要移动  n - i +1  个数据元素. 需要移动 第 n  到第 i 个 元素。

均值的计算:  一共为   (n+1)(n+0)  / 2 ，因为一共计算插了 n+1 个位置。则均值为 :  n / 2

插为第 i 个 元素	1	2	...	n+1
移动 元素的个数	n	n-1	...	0

 

 

 

删除元素,时间复杂度 O(n)

 

删除 第 i  个 元素，则需要移动 n - i  个数据元素 。 需要移动 第   i+ 1  到 第  n 个 元素。

均值的计算:一共为   (n)(n-1+0)  / 2 ，因为一共计算删除 n  个位置。则均值为 :  (n-1) / 2

 

删除第 i 个 元素	1	2	...	n
移动 元素的个数	n-1	n-2	...	0

 

 

 

小提示

1、一般在实际开发时，为了尽量避免移动元素的开销，都会使用贴近硬件的API去完成内存数据的移动，而不是使用循环。例如使用memmove函数。

2、当内部数组的容量不够时，需要重新调整数组的大小，上面的例子我们使用了realloc函数去实现，且每次增加20。然而我们必须认识到，调整大小是很销耗资源的一个操作，因此在实际开发时，我们必须做出明智的容量增长策略。例如：Java中的ArrayList每次将容量扩展为原来的1.5倍。

 

编程语言中的实现类	增长因子
Java ArrayList	1.5 (3/2)
Python PyListObject	~1.125 (n + n >> 3)
VC++ 2013	1.5 (3/2)
G++ 5.2.0	2
Clang 3.6	2

 

 

 

编程练习

将2个非递减排序的顺序表合并为1个表，且新表也保持非递减排序。

如  [1,56,88 ]  和 [ 2,75] 合并后为 [ 1,2,56,75,88  ]

 

#include
     
      #include
      
            #include
       
        using namespace std;class ArrayList{private:     enum{ INCREMENT_SIZE = 20,    //容量不足时，每次增加10个           INIT_CAPACITY = 10      //初始容量20         };     int   size;                  //实际元素个数     int   capacity;              //容量     int*  elements;              //存储元素的数组的基地址    //确保表的容量至少为 reqCapacity 个。否则就增加容量 。     void ensureCapacity(int reqCapacity)     {         int* nelements;         if(capacity
        
         size || index < 0) return false;  //索引不合法        ensureCapacity(size+1);            for(int i=size-1;i>=index;--i)        {            elements[i+1] = elements[i];        }                              elements[index] = e;        size++;         return true;              }                /*    * 删除索引为index 的元素 。    * 合法的index值为  [0,size-1] ，当index=0时，删除的是第一个元素。    * 当index为size-1时，删除的是最后一个元素    **/    bool remove(int index)    {        if(index>=size || index <0) return false;    //索引不合法        for(int i=index;i
         
          =size || index < 0)          //如果索引不合法 ，则抛异常            throw std::out_of_range(0);        return elements[index];       }    //重载索引运算符[]，元素可读可写版本    int& operator[](int index)    {        if(index >=size || index < 0)            throw std::out_of_range(0);        return elements[index];    }}; //end class/** 功能：将2个非递减排序的顺序表合并为1个表re，且re表也保持非递减排序*/void MergeList(const ArrayList& list1,const ArrayList& list2,ArrayList&re){    int i=0,j=0;    //用于访问list1和list2的索引    int k=0;        //访问re的索引    int e1,e2;      //保存从list1和list2中提出的元素        while(i