顺序表的定义

顺序表这种数据结构类似数组。除此之外,还要求记录当前表的长度和分配时定义的表的最大长度。

法一:使用动态数组

1
2
3
4
5
6
typedef int ElemType;
typedef struct SeqList{
ElemType * elem;
int length;
int size;
}SeqList,* ListPtr;

法二:使用静态数组

1
2
3
4
5
6
7
typedef int ElemType;
#define MAXSIZE 10
typedef struct SeqList{
ElemType elem[MAXSIZE];
int length;
int size;
}SeqList,* ListPtr;

至于选用哪种定义方式,肯定还得看实际情况。我更倾向于使用动态数组。因为动态数组使用更灵活,也更节省空间。而且后面的一些基本操作,比如插入,如果数组的大小不够,动态数组还可以重新分配内存大小。所以,后面的操作也都以动态数组为例。

顺序表的初始化

初始化顺序表,要求给表分配内存空间,同时记录下最大长度,并把当前长度记为0。

法一:通过返回值进行传递

1
2
3
4
5
6
7
8
9
SeqList InitSeqList(){
SeqList list;
list.elem=(ElemType*)malloc(list.size*sizeof(ElemType));
if(list.elem==NULL)
exit(0);
list.length=0;
list.size=MAXSIZE;
return list;
}

法二:通过指针进行传递

1
2
3
4
5
6
7
void InitSeqList(SeqList * list){
list->elem=(ElemType*)malloc(list->size*sizeof(ElemType));
if(list->elem==NULL)
exit(0);
list->length=0;
list->size=MAXSIZE;
}

上面两种方法都行,不过使用方法不同。

  • 法一:

    SeqList list=InitSeqList;

  • 法二:

    1
    2
    SeqList list;
    InitSeqList(&list);

顺序表的四大基本操作

顺序表的四大基本操作即按址查找、按值查找、插入、删除。四种操作都应该要十分熟练掌握,而且其精确的时间复杂度应该记下来。

1. 按址查找

由于顺序表物理存储空间的连续性,即顺序存储方式,使得其存取方式为随机存取。只需要知道首元素的位置以及要访问元素的位序,即可通过寻址公式Loc(a[i])=Loc(a[0])+i*sizeof(ElemType)求得其位置。

顺序表的按值查找一般不需要定义函数,直接通过下面的语句即可:

1
list.elem[location];

话说这不就是访问吗,戳了一下elem[localtion]……

严谨点的话可以增加一个判断是否越界的语句。

时间复杂度为O(1)。

2. 按值查找

按值查找的时间复杂度为(n+1)/2。

1
2
3
4
5
6
7
int ListLocate(SeqList list,ElemType e){
for(int i=0;i<list.length;i++){
if(list.elem[i]==e)
return (i+1);
}
return -1;
}

最好把return -1写在for循环外面。因为有的编译器没有搜索到最直接的返回值可能会警告甚至报错。

3. 插入

插入的时间复杂度为n/2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int ListInsert(SeqList * list,ElemType e,int pos){
if((pos<1)||(pos>list->size+2))
return -1;
else if(list->length==list->size){
list->elem=(ElemType*)realloc(list->elem,(list->size+1)*sizeof(ElemType));
if(list->elem==NULL)
return -1;
list->size++;
}
for(int i=list->length-1;i>=pos-1;i--){
list->elem[i+1]=list->elem[i];
}
list->elem[pos-1]=e;
list->length++;
return 0;
}

注意这里是通过指针来进行主函数和被调函数之间的联系,所以访问结构题元素应该用->。说实话,我不是很喜欢用这个符号……因为比起.要多打一个字符……汗

4. 删除

删除操作的时间复杂度为(n-1)/2。

1
2
3
4
5
6
7
8
9
int ListDelete(SeqList * list,int pos){
if(pos<1||pos>=list->length)
return -1;
for(int i=pos-1;i<list->length-1;i++){
list->elem[i]=list->elem[i+1];
}
list->length--;
return 0;
}

有的时候还可能会需要删除的值,则代码修改为:

1
2
3
4
5
6
7
8
9
10
int ListDelete(SeqList * list,int pos,ElemType * need){
if(pos<1||pos>=list->length)
return -1;
*need=list->elem[pos-1];
for(int i=pos-1;i<list->length-1;i++){
list->elem[i]=list->elem[i+1];
}
list->length--;
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdio.h>
#include <stdlib.h>
//宏定义MAXSIZE
#define MAXSIZE 10
//重命名
typedef int ElemType;
typedef struct SeqList{
ElemType * elem;
int length;
int size;
}SeqList,*ListPtr;
//函数原型
void InitSeqList(SeqList * list);
int ListLocate(SeqList list,ElemType e);
int ListInsert(SeqList * list,ElemType e,int pos);
int ListDelete(SeqList * list,int pos);
void ListDisplay(SeqList * list){
for(int i=0;i<list->length;i++){
printf("%d",list->elem[i]);
}
printf("\n");
}

int main(){
SeqList list;
InitSeqList(&list);
for(int i=0;i<list.size;i++){
list.elem[i]=i;
list.length++;
}
//打印初始化后顺序表中的元素
printf("原始的序列:");
ListDisplay(&list);

//查值查找
int pos;
ElemType e=6;
pos=ListLocate(list,e);
printf("定位元素的位置:");
printf("%d\n",pos);

//删除线性表中的元素并打印删除后线性表的元素
ListDelete(&list,pos);
printf("删除后的序列:");
ListDisplay(&list);

//向线性表中添加元素并打印
ListInsert(&list,pos,e);
printf("添加元素后的序列:");
ListDisplay(&list);

return 0;
}

//函数定义
void InitSeqList(SeqList * list){
list->elem=(ElemType*)malloc(list->size*sizeof(ElemType));
if(list->elem==NULL)
exit(0);
list->length=0;
list->size=MAXSIZE;
}

int ListLocate(SeqList list,ElemType e){
for(int i=0;i<list.length;i++){
if(list.elem[i]==e)
return (i+1);
}
return -1;
}

int ListInsert(SeqList * list,ElemType e,int pos){
if((pos<1)||(pos>list->size+2))
return -1;
else if(list->length==list->size){
list->elem=(ElemType*)realloc(list->elem,(list->size+1)*sizeof(ElemType));
if(list->elem==NULL)
return -1;
list->size++;
}
for(int i=list->length-1;i>=pos-1;i--){
list->elem[i+1]=list->elem[i];
}
list->elem[pos-1]=e;
list->length++;
return 0;
}

int ListDelete(SeqList * list,int pos){
if(pos<1||pos>=list->length)
return -1;
for(int i=pos-1;i<list->length-1;i++){
list->elem[i]=list->elem[i+1];
}
list->length--;
return 0;
}

output:

1
2
3
4
原始的序列:0123456789      
定位元素的位置:7
删除后的序列:012345789
添加元素后的序列:0123456789