线性表的顺序存储结构_线性表顺序存储

一、线性表的顺序存储结构

（一）基本原理

设线性表的第一个元素在内存中的存储地址为 $location(a_0)$，每个元素的占用的空间大小为 $k$ 个存储单元，则任意元素的内存地址为：
$$location(a_i)=location(a_0)+k\ast i$$

优点：顺序存储，存储空间少，便于查找。
缺点：插入元素要移动全部的元素，速度慢。

（二）线性表的数据结构

typedef struct SeqList
{
	int n;
	int maxLength;
	ElemType *element;
}SeqList;
1
2
3
4
5
6

二、顺序表的数据结构实现

（一）顺序表的初始化

顺序表的舒适化是使用动态内存生成一个空的线性表。

Status Init(SeqList* list, int mSize)
{
	list->n = 0;
	list->maxLength = mSize;
	list->element = (ElemType*)malloc(sizeof(ElemType) * mSize);
	if (!list->element)
		return Error;
	return OK;
}
1
2
3
4
5
6
7
8
9

（二）顺序表的插入

顺序表的插入是指，若插入位置为 $i$，则将插入元素插入到原顺序表元素 $a_i$ 的后面。若插入位置为 $-1$，则将元素插入到头结点的位置。

1、算法步骤

（1）判断插入下标是否越界

（2）检查顺序表是否已满

（3）将元素（ai+1, ai+2, …, an-1）依次向后移动一个位置

（4）将新元素插入到 i+1 的位置

（5）表长 + 1

2、算法代码

Status Insert(SeqList* list, int i, ElemType x)
{
	if (i < 0 || i > list->n)
		return Error;
	if (list->n == list->maxLength)
		return Error;
	for (int j = list->n; j > i; j--)
		list->element[j] = list->element[j-1];
	list->element[i] = x;
	list->n = list->n + 1;
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12

（三）顺序表的查找

因为顺序表采用顺序存储的方式进行存储，所以，我们只要有顺序表头结点的地址和所需查找元素在顺序表中的索引下标，我们即可找到所查找元素的内存地址，取出所要查找元素的值。

1、算法步骤

（1）算法步骤1：判断是否越界
（2）算法步骤2：取出所查找的值并返回

2、算法代码

Status Find(SeqList* list, int i, ElemType* x)
{
	if (i < 0 || i > list->n - 1)
		return Error;
	*x = list->element[i];
	return OK;
}
1
2
3
4
5
6
7

三、完整代码

#include <stdio.h>
#define ElemType int
#define Error 0
#define OK 1
#define Overflow 2
#define Underflow 3
#define NotPresent 4
#define Duplicate 5
typedef int Status;


typedef struct SeqList
{
	int n;
	int maxLength;
	ElemType *element;
}SeqList;

Status Init(SeqList* list, int mSize)
{
	list->n = 0;
	list->maxLength = mSize;
	list->element = (ElemType*)malloc(sizeof(ElemType) * mSize);
	if (!list->element)
		return Error;
	return OK;
}

Status Insert(SeqList* list, int i, ElemType x)
{
	if (i < 0 || i > list->n)
		return Error;
	if (list->n == list->maxLength)
		return Error;
	for (int j = list->n; j > i; j--)
		list->element[j] = list->element[j-1];
	list->element[i] = x;
	list->n = list->n + 1;
	return OK;
}

Status Find(SeqList* list, int i, ElemType* x)
{
	if (i < 0 || i > list->n - 1)
		return Error;
	*x = list->element[i];
	return OK;
}

int main()
{
	SeqList* list = malloc(sizeof(SeqList));
	Insert(list, 0, 0);
	int* x = malloc(sizeof(int));
	*x = Find(list, 0, x);
	printf("%d\n", *x);
	return 0;
}
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
48
49
50
51
52
53
54
55
56
57
58