顺序表中基本操作的实现
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表。起特点是，逻辑上相邻的数据元素，其物理次序也是相邻的。
线性表的每一个数据元素的存储位置都和线性表的起始位置相差一个常数，这个常数和数据元素在线性表中的位序成正比。由此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。
由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在C语言中可用动态分配的一维数组来表示线性表，格式如下：
1
2
3
4
5
6
7
|
#define MAXISIZE 100
typedef struct
{
ElemType* elem;
int length;
}sqlist;
|
注意
- 数组空间通过后面算法初始化动态分配得到，初始化完成后，数组指针elem指示顺序表的基地址，数组空间大小为MAXSIZE。
- 元素类型定义中的ElemType数据类型是为了描述统一而自定的，在实际应用中，用户可根据实际需要具体定义表中数据元素的数据类型，可以是基本数据类型，如int ,float ,char 等，也可以是构造数据类型，如struct结构体类型。
- length表示顺序表中当前数据元素的个数。
线性表初始化，取值，查找，插入，删除的完整代码
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
59
60
61
62
| #include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
#define OVERFLOW 0
#define ERROR 0
#define OK 1
typedef struct
{
int* elem;
int length;
}SqList;
int InitList(SqList& L)
{
L.elem = new int[MAXSIZE];
if (!L.elem) exit (OVERFLOW);
L.length = 0;
return 0;
}
char GetElem(SqList L, int i, int e)
{
if (i<1 || i>L.length) return ERROR;
e = L.elem[i - 1];
return OK;
}
int LocateElem(SqList L, int e)
{
int i;
for (i = 0;i < L.length;i++) {
if (L.elem[i] == e)return i + 1;
return 0;
}
}
int ListInsert(SqList& L, int i, int e)
{
int j;
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;
++L.length;
return OK;
}
int ListDelete(SqList& L, int i)
{
int j;
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;
return OK;
}
int main()
{
return 0;
}
|
