一、前言
线性表的顺序表示是指用一组地址连续的存储单元依次存储线性表的数据元素。
一般来说，线性表的第i个数据元素ai的存储位置为：
LOC(ai) = LOC(a0)+(i-1)Xl;
其中LOC(a0)表示的是第一个数据元素的存储位置，通常称为线性表的起始位置或者基地址。
l代表的时每个数据元素需要占用l个存储单元。
二、顺序表
1、概念：线性表的这种机内表示称为线性表的顺序存储结构或者顺序映像，通常，称这种存储结构的线性表为顺序表。
2、特点：以元素在计算机内“物理位置相邻”来表示线性表中数据u之间的逻辑关系。只要确定存储线性表的起始位置，线性表中的任一元素都可以随机存取，所以线性的顺序存储结构式一种随机存储的存储结构。
3、通常用数组来描述数据结构中的顺序存储结构。
4、线性表的动态分配顺序存储结构
// 线性表的动态分配顺序存储结构
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
typedef
struct
{
ElemType *elem;
//存储空间基地址
int
length;
//当前长度
int
listsize;
//当前分配的的存储容量（以sizeof(ElemType)为单位）
}SqList;
|
5、初始化线性表
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
Status InitList_Sq(SqList &L)
{
//构造一个空的线性表
L.elem = (ElemType *)malloc(LIST_INIT_SIZE*
sizeof
(ElemType));
if
(!L.elem)
//存储空间分配失败
{
exit(OVERFLOW);
}
L.length = 0;
//空表长度为0
L.listsize = LIST_INIT_SIZE;
//初始存储容量
return
OK;
}
//InitList_Sql
|
6、线性表的插入
一般情况下，在第i（1<=i<=n）个元素之前插入一个元素时，需要将第n个到第i（共n-i+1）个元素向后移动一个位置。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
Status ListInsert_Sq(SqList &L,
int
i,ElemType e)
{
//在顺序线性表L中第i个位置之前插入新的元素e ，i的合法值为1<=i<=ListLength_Sq(L)+1
if
(i<1 || i>L.length+1)
{
return
ERROR;
//i值不合法
}
if
(L.length>=L.listsize)
//当前存储空间已满，增加分配
{
newBase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*
sizeof
(ElemType));
if
(!newBase)
{
exit(OVERFLOW);
//存储分配失败
}
L.elem = newBase;
//新基址
L.listsize+=LISTINCREMENT;
//增加存储容量
}
q = &(L.elem[i-1]);
//q为插入位置
for
(p=&(L.elem[L.length-1]);p>=q;--p);--p)*(p+1) = *p;
*q = e;
++L.length;
return
OK;
}
|
7、线性表顺序存储结构的特点：
逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素，它的存储位置可以用一个简单直观的公式表hi
8、线性表顺序存储结构的缺点
每次做插入和删除操作时，需要移动大量的元素。
