[数据结构与算法]C语言--数据结构之线性表的顺序存储

线性表的定义和特点

在日常生活中,线性表的例子比比皆是。例如，26个英文字母的字母表：(A,B,C,…,Z)
是一个线性表，表中的数据元素是单个字母。在稍复杂的线性表中，一个数据元素可以包含若干个数据项。
由n(n>=0)个数据特性相同的元素构成的有限序列称为线性表。
线性表中元素的个数n(n>=0)定义为线性表的长度，n=0时，称为空表。
对于非空的线性表或线性结构，其特点是：
1）存在唯一的一个被称作“第一个”的数据元素；
2）存在唯一的一个被称作“最后一个”的数据元素；
3）除第一个之外，结构中的每个数据元素均只有一个前驱；
4）除最后一个之外，结构中的每个数据元素均只有一个后继。

线性表的类型定义

线性表是一个相当灵活的数据结构，其长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，而且可以进行插入和删除等操作。

线性表的顺序存储表示

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表（Sequential List）。其特点是，逻辑上相邻的数据元素，其物理次序也是相邻的。
假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储起始位置。则线性表中第a(i+1)个数据元素的存储位置LOC(a)和第i个数据元素的存储位置LOC(a")之间满足下列关系（a"=i）：
LOC(a)=LOC(a")+L

每个数据元素的存储位置都和线性表的起始位置相差一个常数，这个常数和数据元素在线性表中的位序成正比。由此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。再此，由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在C语言中可用动态分配的一维数组表示线性表，描述如下：

//------顺序存储结构------
#define MAXSIZE 100        //顺序表可能达到的最大长度
typedef struct
{
   ElemType *elem;        //存成空间的基地址
   int length;            //当前长度
}SqList

顺序表中基本操作的实现

1.初始化
顺序表的初始化操作就是构造一个空的顺序表

【算法步骤】
(1) 为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。
(2) 将表的当前长度设为0.

【算法描述】：

Status InitList(SqList &L)
{
   //构造空的顺序表L
   L.elem=new ElemType[MAXSIZE];     //为顺序表分配一个大小为MAXSIZE的数组空间
   if(!L.elem)  return ERROR;        //存储分配失败并退出
   L.length=0;                       //空表长度为0
   return OK; 
}

2.取值
取值操作是根据指定的位置序号 i ，获取·顺序表中的第 i 个数据元素的值。
由于顺序存储结构具有随机存取的特点，可以直接通过数组下标定位得到，*elem[i-1]*单元存储第 i 个数据元素。

【算法步骤】
（1）判断指定位置序号i值是否合理（1<=i<=L.length），若不合理，则返回ERROR。
（2）若i值合理，则将第i个数据元素，L.elem[i-1]赋给参数e，通过e返回第i个数据元素的传值。

【算法描述】：

Status GetElem(SqList L,int i,ElemType &e)
{
   if(i<1||i>L.length) return ERROR;   //判断i值是否合理，若不合理，则返回ERROR
   e=L.elem[i-1];                     //elem[i-1]单元存储第i个数据元素
   return OK;
}

3.查找
查找操作是根据指定元素值e，查找表中第1个与e相等的元素。若查找成功，则返回该元素在表中的位置序号；若查找失败，则返回0。

【算法步骤】：
（1）从第一元素起，依次和e相比较，若找到与e相等的元素L.elem[i-1]，则查找成功，返回该元素序号i+1。
（2）若查遍整个顺序表都没有找到，则查找失败，返回0。

【算法描述】：

int LocateElem(SqList L,ElemType e)
{
   //在顺序表L中查找值为e的数据元素，返回其序号
   for(i=0;i<L.length;i++)
   if(L.elem[i]==e)  return i+1;    //查找成功，返回序号i+1
   return 0;                        //查找失败，返回0
}

4.插入
线性表的插入操作是指在表的第i个位置插入一个数据元素e，使长度为n的线性表变成长度为n+1的线性表。

【算法步骤】：
（1）判断插入位置i是否合法。
（2）判断顺序表的存储空间是否已满，若满则返回ERROR。
（3）将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置（i=n+1时无需移动）。
（4）将要插入的新元素e放入第i个位置。
（5）表长加1。

【算法描述】

Status ListInsert(SqList &L,int i,ElemType e)
{
   if(i<1||i>L.length+1)  return ERROR;     //i值不合法
   if(L.length==MAXSIZE) return ERROR;      //当前存储已满
   for(j=L.length;j>=i-1;j--)
   L.elem[j+1]=L.elem[j];        //插入位置及之后的元素后移
   L.elem[i-1]=e;                //将新元素e放入第i个位置
   ++L.length;                   //表长加1
   return OK;
}

5.删除
线性表的删除操作是指将表的第i个位置的元素删去，使长度为n的线性表变成长度为n-1的线性表。

【算法步骤】：
（1）判断删除位置i是否合法。
（2）将第i+1个至第n个元素依次向前移动一个位置（i=n时无需移动）。
（3）表长减1。

【算法描述】：

Status ListDelete(Sqlist &L,int i)
{
   //在顺序表L中删除第i个元素，i的合法范围是1<=i<=L.length
   if(i<1||i>L.length) return ERROR;    //i值不合法
   for(j=i;j<=L.length-1;j++)
   L.length[j-1]=L.elem[j];         //被删除元素之后的元素前移
   L.length--;
   return OK;
   
     
}