数据结构与算法——线性表的顺序储存结构

#define size 40 //储存空间的初始分配量
typedef int typeone; //这里typeone的类型视情况而定，这里定义为int
typedef struct
{
typeone data[size]; //定义数组，用于储存数据元素
int length; //线性表当前的长度
}list;

这里我们就能知道顺序储存结构的三个属性：

1.储存空间的起始位置：数组data，它的储存位置就是储存空间的起始位置；

2.线性表的最大储存容量：数组长度size；

3.线性表的当前长度：length。

注：作为初学者需要注意“数组长度”和“线性表的长度”的区别。在任意时刻，线性表的长度小于等于数组的长度。

二、地址计算方法

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

对于每个数据元素，不管它是整型、实型还是字符型，它都是需要占用一定的储存单元空间的。假设占用的是 c 个储存单元，那么线性表中第i+1个数据元素的储存位置和第 i 个数据元素的储存位置满足下列关系（locate表示获得储存位置的函数）

locate（Ai+1）=locate（Ai）+c

对于，第 i 个数据元素的储存位置可以由第1个元素推算得到：

locate（Ai）=locate（A1）+（i-1)*c

有了这两个公式，我们就可以快速计算线性表中任意位置的地址，不论它是最后一个还是第一个，所需的时间都是相同的，也就是一个常数。所以根据时间复杂度的定义，这项操作的时间复杂度为O(1)。我们通常把具有这一特点的储存结构称为随机存取结构。

三、顺序存储结构的插入和删除

3.1 获得元素操作

获取元素实际上就是把第 i 个元素的值返回，其实是相对简单的。下面我们来看看代码：

#define right 1
#define wrong 0
//上面两个宏定义实际上就是用于函数返回代码运行状况的

int get(list a,int i,int *b) //i是线性表数据元素的位置，用b将第i个数据元素的值传递出来
{
   if(a.length==0||i<1||i>a.length) //length是线性表的长度
   {
       return wrong;
   }
   *b=a.data[i-1]; //注意i是在线性表中是从1开始的，数组下标是从0开始的

   return right;
}

3.2 插入操作

对于顺序储存结构的插入操作，同样可以用排队的思想来看待。你就可以想象一下你在排队，假设说有一个人突然在你面前插队，而且对方又很强壮你打不过他，只好自认倒霉，往后退一步。关键来了，你后退一步必将导致你后面的所有人都将后退一步，这下造成了后面的人群情激愤，直接把那个插队的人给赶跑了。

我们回到顺序储存结构来，如果要将一个元素进行插入操作，那么必将使其后面的元素的位置后退一个。我们这里给出插入算法的思路：

1.如果插入位置不合理或者线性表长度大于等于数组长度，返回异常值；

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

3.将要插入的元素填入位置 i 处；

4.线性表长度+1；

实现代码如下：

//在线性表a中第i个位置插入新的数据元素e，若插入成功线性表长度+1
int insert(int *a,int i,int b)
{
   if(a.length==maxsize) //表明线性表已满，不能再插入
   {
       return wrong;
   }
   if(i<1||i>a.length+1) //i的第一个位置和最后一位的后一位
   {
       return wrong;
   }

   if(i<=a.length)
   {
       for(k=a.length-1;k<=i-1;k--) //将要插入位置后的元素向后移一位
       {
           a.data[k+1]=a.data[k];
       }
   }
   a.date[i-1]=e; //将新元素插入到i位置
   a.length++; //线性表的长度+1

   return right;
}

3.3 删除操作

删除操作实际上就是插入操作的反向操作，这里直接给出算法思路：

1.如果删除的位置不合理或者线性表为空，则返回异常值；

2.取出删除元素；

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

4.线性表长度-1。

实现代码如下：

//删除第i个数据元素，并用b传递出其值，线性表的长度-1
int insert(int *a,int i,int *b)
{
   if(a.length==0) //表明线性表为空
   {
       return wrong;
   }
   if(i<1||i>a.length) //表明删除位置不正确
   {
       return wrong;
   }
   *b=a.data[i-1]; //取出被删除的数据元素
   if(i<a.length) //如果删除的不是最后一位
   {
       for(k=1;k<a.length;k++) //将删除位置后继元素向前移一位
       {
           a.data[k-1]=a.data[k];
       }
   }

   a.length--; //线性表的长度-1

   return right;
}

四、分析插入和删除操作的时间复杂度

先假设一个最好的情况，如果删除或者插入的数据元素恰好都是最后一个，那么就无需移动其他元素的位置，直接进行插入和删除即可，所以其时间复杂度为O(1) 。但是，对于最坏的情况，即删除或者插入的数据元素的位置都是第一个，那么就必须将全部的元素向前或者向后移一位，其时间复杂度显然就为O(n)。

对于平均的情况，根据概率原理，每个位置插入和删除的可能性是相同的。所以，最终平均移动次数和最中间的那个元素的移动次数相等，为（n-1）/2。

因此，顺序储存结构的删除和插入操作的时间复杂度都是O(n)。这就说明它比较适合元素个数不太变化，而更多的是存取数据的应用。

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

优点：

无需为表示表中元素之间的逻辑关系而增加额外的储存空间
可以快速地存取表中任一位置的元素

缺点：

插入和删除操作需要大量元素
当线性表长度变化比较大时，难以确定储存空间的容量
造成储存空间的“碎片”

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)