C语言程序设计：线性表顺序表示和实现

1.线性表的顺序存储表示

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，称这种存储结构的线性表为顺序表（Sequential List）。其特点是，逻辑上相邻的数据元素，其物理次序也是相邻的。

顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：

LOC（ai）＝LOC（a1）＋（i－1）*L

其中，L是每个元素占用存储单元的长度。所以线性表的顺序存储结构是一种随机存取的存储结构。在高级程序设计语言中数组具有随机存取的特性，因此通常用数组来描述数据结构中的顺序存储结构。在C语言中可用动态分配的一维数组表示线性表：

/*顺序表的存储结构*/

＃define MAXSIZE 100　　//顺序表可能达到的最大长度

typedef struct

｛

　Elem Type*elem；

　int length；

｝Sq List；

需要注意：

Elem Type是自定义的数据类型的统称，在实际应用中，用户根据实际需要定义数据元素的数据类型。length表示顺序表中当前数据元素的个数。在C语言中数组的下标是从0开始的，而位置序号是从1开始的，所以要注意两者的对应关系。

例如，用顺序表存储图书数据，每本图书包括书号、书名和价格，顺序存储分配情况如图9.2所示。

图9.2　图书数据顺序存储结构

1　＃define MAXSIZE 10000　　　//图书表可能达到的最大长度

2　typedef struct　　　　　　　　//图书信息定义

3　｛

4　　char no［20］；

5　　char name［50］；

6　　float price；

7　｝Book；

8　typedef struct

9　｛

10　　Book*elem；

11　　int length；

12　｝Sq List；

在上述定义后，可以通过变量定义语句“Sq List L；”将L定义为Sq List类型的变量，可以利用“L.elem［i－1］”访问表中位置序号为i的图书记录。

2.顺序表中基本操作的实现

下面讨论顺序表中几个主要操作的实现。

（1）初始化

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

Status Init List（Sq List&L）　　　　　　　//构造一个空的顺序表L

｛

　L.elem＝new Elem Type［MAXSIZE］；//分配大小为MAXSIZE的数组空间

　if（！L.elem）exit（OVERFLOW）；　//存储分配失败退出

　L.length＝0；　　　　　　　　　　　//空表长度为0

　return OK；

｝

（2）取值(www.xing528.com)

取值操作是根据指定的位置序号i获取顺序表中第i个数据元素的值。根据数组的随机存取，直接通过数组下标定位得到，elem［i－1］存储第i个数据元素。

Status GetElem（Sq List L，int i，Elem Type&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。

int LocateElem（Sq List L，Elem Type e）

｛

　for（int i＝0；i＜L.Length；i＋＋）

if（L.elem［i］＝＝e）return i＋1；

　return 0；

｝

（4）插入

插入操作是指在表的第i个位置插入一个新的数据元素e，线性表长度由n变成n＋1，并且在插入前后数据元素在存储空间中的位置发生变化。原表中从第n个元素到第i个元素依次向后移动一个位置，共n－i＋1个。

Status ListInsert（Sq List&L，int i，Elem Type e）

｛

　if（（i＜1）||（i＞L.length＋1））return ERROR；

　if（L.length＝＝MAXSIZE）return ERROR；

　for（j＝L.length－1；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，且元素之间的逻辑关系发生变化。若删除第i个元素需将第i＋1个至第n个元素依次向前移动一个位置，共n－i个。

Status List Delete（Sq List&L，int i）

｛

　if（（i＜1）||（i＞L.length））return ERROR；

　for（j＝i；j＜＝L.length－1；j＋＋）

L.elem［j－1］＝L.elem［j］；　　　　　//删除元素后的位置前移

－－L.length；　//表长减1

　return OK；

｝

顺序表可以随机存取表中任意元素，但在进行插入或删除操作时需移动大量元素，且数组长度相对固定，表中数据元素个数较多且变化较大时，操作复杂，会导致存储空间浪费。为了解决上述问题，我们学习线性表的另一种表示方法—链式存储结构。