数据结构-线性表-顺序存储

线性表概念

线性表是一种线性结构，它是由n(n≥0)个数据元素a1，a2,…，an组成的有限序列。

线性表的基本运算

1. 初始化 Initiate (L)：建立一个空表 L=()，L 不含数据元素。
2. 求表长度 Length(L)：返回线性表 L 的长度。
3. 读表元素 Get (L，i)：返回线性表第 i 个数据元素，当i 不满足1≤i≤Length(L)时，返回一特殊值。
4. 定位 Locate(L，x)：查找线性表中数据元素值等于x 的结点序号，若有多个数据元素值与 x 相等，运算结果为这些结点中序号的最小值，若找不到该结点，则运算结果为0。
5. 插入 Insert(L，x，i)：在线性表 L 的第 i 个数据元素之前插入一个值为 x 的新数据元素，参数 i 的合法取值范围是 1≤i≤n+1。操作结束后线性表L 由（a1，…，a（i-1）， ai，…，an)变为（a1，…，a（i-1），x， ai，…，an)，表长度加 1。
   1. 当插入位置为非法位置，不可做正常插入操作。
   2. 当表空间已满，不可再做插入操作。
6. 删除 Delete (L，i)：删除线性表 L 的第 i 个数据元素ai，i 的有效取值范围是 1≤i≤ n。删除后线性表 L 由（a1，…，a（i-1）， ai，…，an)变为（a1，…，a（i-1）， a（i+1），…，an)，表长度减 1。 当要删除元素的位置i不在表长度内（即i<1或i>L.length）时为非法位置，不能做正常的删除操作。

线性表的顺序存储

1. 将表中的结点依次存放在计算机内存中一组连续的存储单元中，数据元素在线性表中的邻接关系决定它们在存储空间中的存储位置，即逻辑结构中相邻的结点其存储位置也相邻。用顺序存储实现的线性表称为顺序表。一般使用数组来表示顺序表。顺序存储线性表时，需要存储存储单元大小，数据个数。

顺序存储插入方法

1. 在该位置上插入新结点x，将表中位置为n，n-1，…，i上的结点，依次后移到位值n+1，n，…，i+1上，空出第i个位置。
2. 仅当插入位置i=n+1时，才无须移动结点，直接将x插入表的末尾。该顺序表长度+1。
3. 存储算法，算法的平均复杂度是O(n)

   void insert(Array arr, DataType x, int i) {
           //将元素 x 插入到顺序表arr 的第 i 个数据元素之前  
           if (arr.length == Maxsize)
               exit("表已满");
           if (i < 1 || i > arr.length + 1)
               exit("插入位置错误");//检查插入位置是否合法 
           for (j = arr.length; j >= i; j--) { //初始 i=arr.length  	   
               arr.data[j] = L.data[j - 1]; //依次后移  	
           }
           arr.data[i - 1] = x; //元素 x 调整到下标为 i-1 的位置  	
           arr.length++;  //表长度加 1 
       }

顺序存储删除方法

1. 删除第i个元素，若1≤i≤n-1，则必须将表中位置i+1，i+2，…，n的结点，依次前移到位置i，i+1，…，n-1上，以填补删除操作造成的空缺；该表长度减1。
2. 仅当删除位置i=n时，才无须移动结点，直接令表长度减1即可
3. 删除算法，算法的平均复杂度是O(n)

   void delete(Array A, int i) {
           //删除线性表L中的第i个数据结点
           if (i < 1 || i > A.length) //检查位置是否合法
               exit("非法位置");
           for (j = j; j < A.length; j++) { //第i个元素的下标为i-1
               A.data[j - 1] = A.data[j]; //依次左移
           }
           A.length--;//表长度减1
       }
   

顺序存储的定位方法

定位算法：平均时间复杂度为 O(n)

int Locate(Array arr, DataType x) {
        int i = 0;
        while ((i < arr.length) && (arr.data != x)) { //在顺序表中查找值为 x 的结点
            i++;
        }
        if (i < arr.length) return i + 1;//若找到值为x的元素，返回元素的序号
        else return 0;//未查找到值为x的元素，返回0
    }

求表长和读表元素算法的时间复杂度为 O(1)

线性表顺序存储的优缺点

优点

1. 无需为表示结点间的逻辑关系而增加额外存储空间；
2. 可以方便地随机存取表中的任一结点。

缺点

1. ???????插入和删除运算不方便，需要移动大量的结点；???????
2. 顺序表要求占用连续的空间，存储分配只能预先进行，因此当表长变化较大时，难以确定合适的存储规模。