线性表的顺序存储结构

线性表的顺序存储结构

       相关概念

       举个栗子：

       大学的时候，宿舍有一个同学，帮大家去图书馆占座。他每次去图书馆，挑一个好地儿，把他书包里的书，一本一本按座位放好，若书不够，再把水杯，水笔都用上，长长一排，九个座硬是被他占了。

       1.  顺序存储的定义

       线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

       示意图：

       

       2.  顺序存储方式

       线性表的顺序存储结构，其实就和刚才图书馆占座的例子一样，就是在内存中找了块地儿，通过占位的形式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空地中。

       既然线性表的每个数据元素的类型都相同，所以可以用一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

       这里有几个关键的地方：

      1）为了建立一个线性表，要在内存中找一块地，这块地的第一位置就非常关键，他是存储空间的起始位置

      2）数组的长度就是这个最大存储容量

      3）线性表的当前长度

      3. 数据长度与线性表长度区别

      1）数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。当然，一般高级语言是可以通过编程手段实现动态分配数组，不过这会带来性能上的损耗。

      2）线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。

      在任意时刻，线性表的长度应该小于等于数组的长度。

      4.  地址计算方法

      数组是从0开始第一个下标的，于是线性表的第i个元素是要存储在数组下标为i-1的位置，即数据元素的序号和存放它的数组下标之间存在对应关系：

      

      存储器中的每个存储单元都有自己的编号，这个编号称为地址。

      假设每个数据元素占用的都是c个存储单元，那么每个数据元素地址可通过公式计算得到:  LOC(ai)=LOC(a1)+(i-1)*c

      

      它的存取时间性能为O(1)。我们通常把具有这一特点的存储结构称为随机存取结构。

      相关操作

      1.  获得元素操作（GetElem）

       获取元素的思路：

       1）考虑边界问题，顺序线性表L已存在（非空表），并且i必须在1<=i<=ListLength(L)范围内，否则抛出异常

       2）将数值下标为i-1的值返回即可

       C语言的实现如下：

 1 // 获得元素操作
 2 #define OK 1
 3 #define ERROR 0
 4 #define TRUE 1
 5 #define FALSE 0
 6 typedef int Status;
 7 /*Status是函数的类型,其值是函数结果状态代码，如OK等*/
 8 /*初始条件：顺序线性表L已存在，1<=i<=ListLength(L)*/
 9 /*操作结果：用e返回L中第i个数据元素的值*/
10 
11 Status GetElem(SqList L, int i, ElemType *e)
12 {
13     if (L.length == 0 || i < 1 || i > L.length)
14         return ERROR;
15     *e = L.data[i-1];
16     return OK;
17 }

       PHP的实现如下：

 1 <?php
 2 class Seqlist{
 3 
 4     private $seq_list; //顺序表
 5     /**
 6      * 顺序表初始化
 7      *
 8      * @param mixed $seq_list
 9      * @return void
10      */
11     public function __construct($seq_list=array()){
12         $this->seq_list = $seq_list;
13     }
14 
15     /**
16      * 返回顺序表元素个数
17      *
18      * @return int
19      */
20     public function listLength(){
21         return count($this->seq_list);
22     }
23 
24     /**
25      * 返回顺序表中下标为i的元素值
26      *
27      * @param int i
28      * @return mixed 如找到返回元素值，否则返回false
29      */
30     public function getElem($i){
31         if ($this->seq_list && $i > 0 && $i <= $this->listLength()) {
32             return $this->seq_list[$i-1];
33         }else{
34             return false;
35         }
36     }
37 }

       2.  插入操作

       插入算法的思路：

       1）如果插入位置不合理（1<=i<=ListLength(L)+1），抛出异常

       说明：最好的情况就是，插入的位置为末尾：ListLength(L)+1（不是数组下标）,这个时候不用移动元素，时间复杂度是O(1)

       2）如果线性表长度大于等于数组长度，则抛出异常或动态增加容量

       3）从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置

       4）将要插入元素填入位置 i 处

       5）表长加1

       C语言的实现如下：

 1 // 插入操作
 2 #define OK 1
 3 #define ERROR 0
 4 #define TRUE 1
 5 #define FALSE
 6 typedef int Status;
 7 /*初始条件：顺序线性表L已存在，1<=i<=ListLength(L)*/
 8 /*操作结果：在L中第i个位置之前插入新的数据元素e,L的长度加1*/
 9 
10 Status ListInsert(SqList *L, int i, ElemType e)
11 {
12     int k;
13     if (L->length == MAXSIZE) /*顺序线性表已经满*/
14         return ERROR;
15     if (i < 1 || i > L->length + 1) /*当i不在范围内时*/
16         return ERROR;
17 
18     if (i <= L->length) /*若插入数据位置不在表尾*/
19     {
20         for (k = L->length - 1; k >= i - 1; k--) /*将要插入位置后数据元素向后移动一位*/
21         {
22             L->data[k + 1] = L->data[k];
23         }
24     }
25     L->data[i - 1] = e; /*将新元素插入*/
26     L->length++;
27     return OK;
28 }

       PHP的实现如下：

 1 <?php
 2 class Seqlist{
 3 
 4     private $seq_list; //顺序表
 5     /**
 6      * 顺序表初始化
 7      *
 8      * @param mixed $seq_list
 9      * @return void
10      */
11     public function __construct($seq_list=array()){
12         $this->seq_list = $seq_list;
13     }
14 
15     /**
16      * 在指定位置 i 插入一个新元素 $value
17      *
18      * @param int $i
19      * @param mixed $value
20      * @return bool 插入成功返回 true, 否则返回 false
21      */
22     public function listInsert($i, $value){
23         // 三种情况：插入位置不合理
24         if ($i > $this->listLength()+1 || $i < 1) {
25             return false;
26         }elseif ($i == $this->listLength()+1) {
27             // 最好的情况：元素插入到最后一个位置，不需要移动元素，时间复杂度为O(1)
28             $this->seq_list[$i-1] = $value;
29         }else{
30             // 从 $i-1 到最后的元素位置向后移动一位
31             for ($k = $this->listLength()-1; $k >= $i-1; $k--) {
32                 $this->seq_list[$k+1] = $this->seq_list[$k];
33             }
34             $this->seq_list[$i-1] = $value;
35         }
36 
37         return true;
38     }
39 }

       这里有一个疑问，因为前面我们提到了：在任意时刻，线性表的长度应该小于数组的长度。

       在用C语言实现的版本中，我们用到了L->length == MAXSIZE去考虑可能会产生异常的情况，但是php版本实现中却没有相应代码的体现，为什么呢？我们知道php中的变量是不需要申请可以直接使用的。那这个地方数组的长度是多大，如何计算呢？

       其实，PHP中的所谓“数组”实际上并不是纯粹的数组！而是“哈希表”或者说是“字典”。PHP的数组本身不是由基础的数据结构构成，但是其内部实现方式应用到了大部分的线性表数据结构，等到后面再来重新回顾PHP数组的内部实现原理。

       3.  删除操作

       删除算法的思路：

       1）如果删除位置不合理，抛出异常

       2）取出删除元素

       3）从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置

       4）表长减1

       C语言的实现如下：

 1 // 删除操作
 2 #define OK 1
 3 #define ERROR 0
 4 #define TRUE 1
 5 #define FALSE
 6 typedef int Status;
 7 /*初始条件：顺序线性表L已存在，1<=i<=ListLength(L)*/
 8 /*操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1*/
 9 Status ListDelete(SqList *L, int i, ElemType *e)
10 {
11     int k;
12     if (L->length == 0) /*线性表为空*/
13         return ERROR;
14     if (i < 1 || i > L->length) /*删除位置不正确*/
15         return ERROR;
16     *e = L->data[i - 1];
17     if (i < L->length) /*如果删除不是最后位置*/
18     {
19         for (k = i; k < L->length; k++)
20 
21             L->data[k - 1] = L->data[k];
22     }
23     L->length--;
24     return OK;
25 }

       PHP的实现如下：

 1 <?php
 2 class Seqlist{
 3 
 4     private $seq_list; //顺序表
 5     /**
 6      * 顺序表初始化
 7      *
 8      * @param mixed $seq_list
 9      * @return void
10      */
11     public function __construct($seq_list=array()){
12         $this->seq_list = $seq_list;
13     }
14 
15     /**
16      * 返回顺序表元素个数
17      *
18      * @return int
19      */
20     public function listLength(){
21         return count($this->seq_list);
22     }
23 
24     /**
25      * 删除顺序表中 i 位置的元素， 并用 $value 返回其值
26      *
27      * @param int $i
28      * @return mixed 删除成功返回 $value，否则返回 false
29      */
30     public function listDelete($i)
31     {
32         //两种情况：删除位置不合理
33         if ($i < 1 || $i > $this->listLength()) {
34             return false;
35         } else {
36             $value = $this->seq_list[$i - 1];
37             for ($k = $i - 1; $k < $this->listLength() - 1; $k++) {
38                 $this->seq_list[$k] = $this->seq_list[$k + 1];
39             }
40             unset($this->seq_list[$this->listLength() - 1]);
41 
42             return $value;
43         }
44     }
45 }

      线性表顺序存储结构的优缺点  

      1.  优点：

      1）无须为表示表中元素之间的逻辑关系而增加额外的存储空间

      2）可以快速地存取表中任一位置的元素

      2.  缺点：

      1）物理上相邻存储，不便于内存利用。例如一个容量为10的数组，需要内存为10字节，但是目前没有连续10个字节空余的内存空间，但是有很多不连续的小于10字节的内存空间，这样也没办法分配。造成存储空间的”碎片”。

      2）顺序表的容量很难确定。对于C语言而言，定义一个数组是需要指定数组大小的。这个大小就是为了方便底层用于申请连续内存空间。PHP源码中在初始化一个空数组的时候，也会先创建一个长度为16的arData数组，在需要扩容的时候再进行数组扩容。

      3）不便于插入和删除操作，需要移动整个顺序表元素

参考资料：程杰《大话数据结构》

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/hld123/p/14443128.html