顺序表的基本操作(非常全，非常详细)

1.顺序表的定义

#define LIST_INIT_SIZE 100
typedef char ElemType;
typedef struct
{
	ElemType data[LIST_INIT_SIZE];//存储顺序表元素空间
	int length;//顺序表长度(以sizeof(ElemType)为单位)
}SqList;//顺序表类型定义
1
2
3
4
5
6
7

2.初始化顺序表
在主函数中利用malloc函数向堆区分配一个大小为Sqlist的空间并返回一个指向该内存空间的无类型的指针，利用强制转化，将指针转化为一个Sqlist*类型的指针，并赋值给L。
使用 初始化函数将顺序表的现有长度初始化0。

//构造一个空的顺序表L
void InitSqList(SqList *L)
{
	L->length=0;//初始长度为0
}
1
2
3
4
5

3.增加元素
顺序表的添加可以想象成排队时有人插队。排队时每个人的位置都是固定的，当有人要插队时，那它插队时后面的每个人都要向后移动，不然没有位置让他插。
还需要判断插入的位置是否合法，比如那里本来就没人，你怎么去插队是吧。判断时还需注意数组下标是从0开始的，所以判断是否合法时，临界值要注意不能出错。
因此步骤是：判断插入位置是否合法->元素后移->最后插入。

//在顺序表L中第i(1≤i≤ListLength(L))个位置上插入新的数据元素e
void SqListInsert(SqList *L,int i,ElemType e)
{
	int j;
	if(i>=1&&i<=L->length+1)//判断i是否合法
	{
		i--;
		for(j=L->length;j>i;j--)//找到插入的位置
			L->data[j]=L->data[j-1];
		L->data[i]=e;//将元素插入到已找到的适当位置
		L->length++;    //顺序表L长度增一
	}
	else
		printf("i不符合要求");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这里if语句就是判断是否合法，for语句用来找到插入位置并后移元素，之后插入。
假设插入位置为3。

进行元素后移

最后进行添加。
4.显示顺序表中元素个数
这个没什么好说的，直接返回就行了。

//求顺序表L中数据元素个数
int SqListLength(SqList *L)
{
	return L->length;
}
1
2
3
4
5

5.判断顺序表是否为空
这里根据顺表长度判断。返回值1代表不为空，返回值为0代表顺序表为空。

//判断顺序表L是否为空
int SqListEmpty(SqList *L)
{
	//调用函数可通过判断函数返回值确定结果状态
    if(L->length==0)//根据顺序表L当前长度判断
        return 0;
    else
        return 1;
}
1
2
3
4
5
6
7
8
9

6.求顺序表特定位置的元素
这里同理，也要先判断位置是否合法。如果合法则直接返回该位置的元素。不合法则退出函数。

//求顺序表L中第i(1≤i≤ListLength(L))个数据元素的值
char GetSqListElem(SqList *L,int i,ElemType e)
{
	if(i>=1&&i<=L->length)//判断i是否合法
	{
		e=L->data[i-1];//获取第i个元素的值
		return e;
	}
	else
		printf("i不符合要求");
}
1
2
3
4
5
6
7
8
9
10
11

7.求顺序表L中第1个与e的值相等的数据元素的位序
这里也很简单，直接遍历一遍顺序表，进行与e值得比较，那怎样判断顺序表中没有与e相等得元素呢？遍历结束时i值就等于顺序表得长度，因此可以根据i得值来判断。

//求顺序表L中第1个与e的值相等的数据元素的位序
int LocateSqListElem(SqList* L, ElemType e)
{
	int i;
	for (i = 0; L->data[i] != e && i < L->length; i++)//判断条件，在i合法的基础上逐个比较当前值与e值是否相等
		;
	if (i == L->length)//根据情况返回相应的值
		return -1;
	else
		return i + 1;
}
1
2
3
4
5
6
7
8
9
10
11

8.删除指定位置得元素
删除元素时也可以想象成排队。正在排队时你前面的人走了，这时（你内心是不是很高兴）你立马向前走一步把那个空位补上，同理你后面的人也向前走补空位。因此删除时步骤：判断位置是否合法->合法则删除->补空位。

//删除顺序表L的第i(1≤i≤ListLength(L))个数据元素
void SqListDelete(SqList *L,int i)
{
	int j;
	if(i>=1&&i<=L->length)//判断i是否合法
	{
		i--;
		for(j=i;j<L->length-1;j++)//找到插入的位置
			L->data[j]=L->data[j+1];//元素前移
		L->length--;    //顺序表L长度减一
	}
	else
		printf("i不符合要求");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

9.销毁顺序表
主函数创建顺序表时，利用malloc函数向堆区申请了空间，堆区内存需要我们自己释放，因此销毁顺序表时，利用free函数将内存释放。

//销毁顺序表L
void DestroySqList(SqList *L)
{
	free(L);
}
1
2
3
4
5

完整代码如下：

#include<stdio.h>
#include<malloc.h>
#define LIST_INIT_SIZE 100
typedef char ElemType;
typedef struct
{
	ElemType data[LIST_INIT_SIZE];//存储顺序表元素空间
	int length;//顺序表长度(以sizeof(ElemType)为单位)
}SqList;//顺序表类型定义
//基本操作算法代码实现

//构造一个空的顺序表L
void InitSqList(SqList* L)
{
	L->length = 0;//初始长度为0
}

//销毁顺序表L
void DestroySqList(SqList* L)
{
	free(L);
}

//判断顺序表L是否为空
int SqListEmpty(SqList* L)
{
	//调用函数可通过判断函数返回值确定结果状态
	if (L->length == 0)//根据顺序表L当前长度判断
		return 0;
	else
		return 1;
}

//求顺序表L中数据元素个数
int SqListLength(SqList* L)
{
	int l;
	l = L->length;
	return l;
}

//输出顺序表L中的元素
void DispSqList(SqList* L)
{
	int i = 0;
	while (i < L->length)//依次输出元素
	{
		printf("%c ", L->data[i]);
		i++;
	}
	printf("\n");
}

//在顺序表L中第i(1≤i≤ListLength(L))个位置上插入新的数据元素e
void SqListInsert(SqList* L, int i, ElemType e)
{
	int j;
	if (i >= 1 && i <= L->length + 1)//判断i是否合法
	{
		i--;
		for (j = L->length; j > i; j--)//找到插入的位置
			L->data[j] = L->data[j - 1];
		L->data[i] = e;//将元素插入到已找到的适当位置
		L->length++;    //顺序表L长度增一
	}
	else
		printf("i不符合要求");
}

//删除顺序表L的第i(1≤i≤ListLength(L))个数据元素
void SqListDelete(SqList* L, int i)
{
	int j;
	if (i >= 1 && i <= L->length)//判断i是否合法
	{
		i--;
		for (j = i; j < L->length - 1; j++)//找到插入的位置
			L->data[j] = L->data[j + 1];//元素前移
		L->length--;    //顺序表L长度减一
	}
	else
		printf("i不符合要求");
}

//求顺序表L中第i(1≤i≤ListLength(L))个数据元素的值
char GetSqListElem(SqList* L, int i, ElemType e)
{
	if (i >= 1 && i <= L->length)//判断i是否合法
	{
		e = L->data[i - 1];//获取第i个元素的值
		return e;
	}
	else
		printf("i不符合要求");
}

//求顺序表L中第1个与e的值相等的数据元素的位序
int LocateSqListElem(SqList* L, ElemType e)
{
	int i;
	for (i = 0; L->data[i] != e && i < L->length; i++)//判断条件，在i合法的基础上逐个比较当前值与e值是否相等
		;
	if (i == L->length)//根据情况返回相应的值
		return -1;
	else
		return i + 1;
}

//整体建立顺序表L
void CreateSqList(SqList* L, ElemType a[], int n)
{
	for (int i = 0; i < n; i++)
		L->data[i] = a[i];
	L->length = n;//设置长度
}

//主函数
void main()
{
	SqList* L = (SqList*)malloc(sizeof(SqList));
	ElemType e = 0;
	printf("1、初始化顺序表\n");
	InitSqList(L);
	printf("2、插入元素h、e、l、l、o\n");
	SqListInsert(L, 1, 'h');//插入元素'h'
	SqListInsert(L, 2, 'e');//插入元素'e'
	SqListInsert(L, 3, 'l');//插入元素'l'
	SqListInsert(L, 4, 'l');//插入元素'l'
	SqListInsert(L, 5, 'o');//插入元素'o'
	printf("3、顺序表元素为:");
	DispSqList(L);//输出顺序表L
	printf("4、长度为%d\n", SqListLength(L));//显示顺序表L中数据元素个数
	printf("5、顺序表是否为空？");
	if (SqListEmpty(L) == 1)//判断当前顺序表L的状态
		printf("非空\n");
	else
		printf("空\n");
	printf("6、顺序表的第5个元素是：%c\n", GetSqListElem(L, 5, e));//求顺序表L中第5个数据元素的值
	printf("7、元素'h'的位置是：%d\n", LocateSqListElem(L, 'l'));//查找顺序表L中第1个与e的值相等的数据元素的位序
	printf("8、删除第2个元素，并在第2个元素位置上插入‘w’元素\n");
	SqListDelete(L, 2);//删除顺序表L的第2个数据元素
	SqListInsert(L, 2, 'w');//在顺序表L中第2个位置上插入新的数据元素'w'
	printf("输出当前顺序表：");
	DispSqList(L);//输出顺序表L
	printf("9、销毁顺序表");
	DestroySqList(L);//销毁顺序表L
}
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147