【C数据结构】顺序表的基本操作_顺序表的基本操作代码

1、顺序表的定义

使用结构体来构造顺序表的结构。

typedef struct SeqList
{
	SLDataType* arr;//顺序表的数据元素存储空间
	int size;//顺序表的当前数据个数
	int capacity;//顺序表的最大容量
}SL;
1
2
3
4
5
6

2、顺序表初始化

使用动态分配构造一个空的顺序表，即顺序表最开始的模样。

void SLInit(SL* p)//初始化
{
	p->arr = (SLDataType*)malloc(sizeof(SLDataType) * Init_CAPACITY);//动态开辟一块空间给arr
						
		if (p == NULL)
		{
			perror("malloc fail");
			return;
		}
	p->size = 0;
	p->capacity = Init_CAPACITY;
}
1
2
3
4
5
6
7
8
9
10
11
12

3、顺序表的扩容

当我们的顺序表容量不够用时，这时我们需要扩容，扩容可以使顺序表变得更灵活。

void SLCheckCapacity(SL* p)
{
	assert(p);//assert是断言操作，我们要确保指针p不为NULL。如p==NULL,assert就会将其报错，并且不在往后操作。
	if (p->capacity == p->size )//扩容条件：数据元素个数==最大容量
	{
		SLDataType* tmp = (SLDataType*)realloc(p->arr, sizeof(SLDataType) * p->capacity * 2);//再次动态开辟新的空间
									 //realloc（需改变内存大小的指针名，新大小）
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		p->capacity *= 2;//容量2倍增长
		p->arr = tmp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4、顺序表的插入

4.1、头插

注意点：
1、确保指针不为NULL。
2、插入前检查容量是否满了，即还有没有位置插入数据。
3、插入前，我们需要先对原有的数据进行往后移。
4、插入完成后，数据元素个数增加了，所以需要对 size+1。

void SLPushFront(SL* p,SLDataType x)
{
	assert(p);//断言p是否为NULL
	SLCheckCapacity(p);//插入数据前检查容量是否满了
	
	int end = p->size - 1;
	while (end >= 0)
	{
		p->arr[end + 1] = p->arr[end];//把数据往后移。
		end--;
	}
	p->arr[0] = x;
	p->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.2、尾插

相较于头插，尾插就比较简单了。
注意点：
1、确保指针不为NULL。
2、插入数据前检查容量是否满了。

void SLPushBack(SL* p,SLDataType x)
{
	assert(p);
	SLCheckCapacity(p);
	p->arr[p->size++] = x;//这里是后置++，
						  //相当于先p->arr[p->size]＝x
						  //再p->size++
}
1
2
3
4
5
6
7
8

4.3、按位插入

注意点：
1、确保指针不为NULL，确保pos(下标)不能小于0和超过顺序表。
2、插入前检查容量是否满了。
3、插入前要把pos及后面的位置后移。

void SLInsert(SL* p,SLDataType pos,SLDataType x)//在pos位置插入数据
{
	assert(p);
	assert(pos >= 0 && pos <= p->size);//注意pos不能超过表长和小于0
									   //这里可以pos = p->size是我们接下来会扩容检查，所以不怕越界行为。
	SLCheckCapacity(p);

	for (int i = p->size-1; i >= pos; i--)
	{
		p->arr[i + 1] = p->arr[i];//pos及后面的数据后移
	}
	p->arr[pos] = x;
	p->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5、顺序表的删除

5.1、头删

注意点：
1、确保指针不为NULL。
2、删除前要确保还有数据可以删，如果没有数据了，就不能在删。
3、不需要先把数据置成什么，可以直接把后面的数据往前移即可，即从后往前覆盖，这样就可以实现删除操作。

void SLPopFront(SL* p)//头删
{
	assert(p);
	assert(p->size > 0);
	for (int i = 0; i < p->size; i++)
	{
		p->arr[i] = p->arr[i+1];
	}
	p->size--;
}
1
2
3
4
5
6
7
8
9
10

5.2、尾删

注意点：
1、确保指针不为NULL。
2、删除前要确保还有数据可以删，如果没有数据了，就不能在删。

void SLPopBack(SL* p)//尾删
{
	assert(p);
	assert(p->size > 0);
	p->arr[p->size - 1] = 0;//这里只是置成0，这条语句可有可无。
	p->size--;
}
1
2
3
4
5
6
7

5.3、按位删除

注意点：
1、确保指针不为NULL。
2、pos(下标)不能等于或超过顺序表长度。
3、当pos(下标)是最后一个元素时，我们删除的是下标上的元素，而不是将表长其简单的减1，所以不能让pos=p->size。

void SLErase(SL* p, SLDataType pos)
{
	assert(p);
	assert(pos >= 0 && pos < p->size);//注意pos不能等于或超过数组和小于0
	
	for (int  i = pos+1; i < p->size; i++)
	{
		p->arr[i-1] = p->arr[i];//注意[]里一定是i而不是pos
	}
	p->size--;
}
1
2
3
4
5
6
7
8
9
10
11

6、顺序表的查找

6.1、按值查找

void SLFind(SL* p, SLDataType x)
{
	assert(p);
	int flag = 1;
	for (int i = 0; i < p->size; i++)
	{
		if (p->arr[i] == x)
		{
			printf("找到了！要查找的%d，下标为%d",p->arr[i], i);
			flag = 0;
			break;
		}
	}
	if (flag != 0)
		printf("%d不存在于表中!!!",x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6.2、按位查找

注意点：
1、确保p不为NULL。
2、这里我用的是按位置查找，不是用数组从0开始算的第1个位置，所以我们断言的时候需要注意是i是可以等于顺序表的长度的。

void SLBitFind(SL* p, SLDataType i)
{
	assert(p);
	assert(i >=1 && i <= p->size);//注意不能超过顺序表长度和小于1
	printf("要查找的第%d位，值为：%d",i,p->arr[i-1]);
}
1
2
3
4
5
6

7、求顺序表长度

void SLLength(SL* p)
{
	assert(p);
	printf("顺序表长度为：%d",p->size);
}
1
2
3
4
5

8、顺序表的打印

void SLPrint(SL* p)
{
	assert(p);
	for (int i = 0; i < p->size ; i++)
	{
		printf("%d ",p->arr[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9

9、顺序表的销毁

void SLDestroy(SL* p)
{
	assert(p);
	free(p->arr);
	p->capacity = p->size = 0;
}
1
2
3
4
5
6

10、完整代码

10.1、SeqList.h

头文件：声明函数

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define Init_CAPACITY 4
typedef int SLDataType;

typedef struct SeqList
{
	SLDataType* arr;//顺序表的数据元素存储空间
	int size;//顺序表的当前数据个数
	int capacity;//顺序表的最大容量
}SL;

void SLInit(SL* p);//初始化顺序表
void SLCheckCapacity(SL* p);//扩容
void SLPushFront(SL* p, SLDataType x);//头插
void SLPushBack(SL* p,SLDataType x);//尾插
void SLInsert(SL* p,SLDataType pos,SLDataType x);//按位插入
void SLPopFront(SL* p);//头删
void SLPopBack(SL* p);//尾删
void SLErase(SL* p, SLDataType pos);//按位删除
void SLFind(SL* p, SLDataType x);//按值查找
void SLBitFind(SL* p, SLDataType i);//按位查找
void SLLength(SL* p);//求表长
void SLPrint(SL* p);//打印
void SLDestroy(SL* p);//销毁顺序表


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

10.2、SeqList.c

源文件：函数功能实现

#include"SeqList.h"

void SLInit(SL* p)//初始化
{
	p->arr = (SLDataType*)malloc(sizeof(SLDataType) * Init_CAPACITY);

	if (p == NULL)
	{
		perror("malloc fail");
		return;
	}
	p->size = 0;
	p->capacity = Init_CAPACITY;
	printf("顺序表初始化完成！\n");
}


void SLCheckCapacity(SL* p)//扩容
{
	assert(p);
	if (p->capacity == p->size)
	{
		SLDataType* tmp = (SLDataType*)realloc(p->arr, sizeof(SLDataType) * p->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		p->capacity *= 2;
		p->arr = tmp;

		printf("表长已等于容量！已自动扩容成功！！！\n");
	}
}


void SLPushFront(SL* p, SLDataType x)//头插
{
	assert(p);
	SLCheckCapacity(p);
	int end = p->size - 1;
	while (end >= 0)
	{
		p->arr[end + 1] = p->arr[end];
		end--;
	}
	p->arr[0] = x;
	p->size++;
	printf("元素%2d头插成功：",x);
	SLPrint(p);
}


void SLPushBack(SL* p, SLDataType x)//尾插
{
	assert(p);
	SLCheckCapacity(p);
	p->arr[p->size++] = x;
	printf("元素%2d尾插成功：", x);
	SLPrint(p);
}


void SLInsert(SL* p, SLDataType pos, SLDataType x)//按位插入
{
	assert(p);
	assert(pos >= 0 && pos <= p->size);
	SLCheckCapacity(p);

	for (int i = p->size - 1; i >= pos; i--)
	{
		p->arr[i + 1] = p->arr[i];
	}
	p->arr[pos] = x;
	p->size++;
	printf("在下标为%d处插入%d成功：",pos,x);
	SLPrint(p);
}


void SLPopFront(SL* p)//头删
{
	assert(p);
	assert(p->size > 0);
	for (int i = 0; i < p->size; i++)
	{
		p->arr[i] = p->arr[i + 1];
	}
	p->size--;
	printf("头删成功：");
	SLPrint(p);
}


void SLPopBack(SL* p)//尾删
{
	assert(p);
	assert(p->size > 0);
	p->arr[p->size - 1] = 0;
	p->size--;
	printf("尾删成功：");
	SLPrint(p);
}


void SLErase(SL* p, SLDataType pos)//按位删除
{
	assert(p);
	assert(pos >= 0 && pos < p->size);

	printf("在下标为%d处删除%d成功：", pos, p->arr[pos]);

	for (int i = pos + 1; i < p->size; i++)
	{
		p->arr[i - 1] = p->arr[i];
	}
	p->size--;
	SLPrint(p);
}


void SLFind(SL* p, SLDataType x)//按值查找
{
	assert(p);
	int flag = 1;
	for (int i = 0; i < p->size; i++)
	{
		if (p->arr[i] == x)
		{
			printf("找到了，要查找的%d，在下标为%d处\n", p->arr[i], i);
			flag = 0;
			break;
		}
	}
	if (flag != 0)
		printf("要查找的%d不存在于表中!\n", x);
}


void SLBitFind(SL* p, SLDataType i)//按位查找(非下标查找)
{
	assert(p);
	assert(i >= 1 && i <= p->size);
	printf("要查找的第%d位，值为：%d\n", i, p->arr[i - 1]);
}

void SLLength(SL* p)//求表长
{
	assert(p);
	printf("顺序表长度为：%d\n", p->size);
}


void SLPrint(SL* p)//打印
{
	assert(p);
	for (int i = 0; i < p->size; i++)
	{
		printf("%d ", p->arr[i]);
	}
	printf("\n");
}


void SLDestroy(SL* p)//销毁顺序表
{
	assert(p);
	free(p->arr);
	p->capacity = p->size = 0;
	printf("顺序表销毁成功！");
}
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171

10.3、test.c

源文件：测试功能

#include"SeqList.h"
int main()
{
	SL s;
	//初始化
	SLInit(&s);
	printf("\n");
	//头插
	SLPushFront(&s, 5);
	SLPushFront(&s, 9);
	printf("\n");
	//尾插
	SLPushBack(&s, 88);
	SLPushBack(&s, 24);
	printf("\n");
	//按位插入
	SLInsert(&s, 3, 37);
	SLInsert(&s, 1, 19);
	printf("\n");
	//尾删
	SLPopBack(&s);
	SLPopBack(&s);
	printf("\n");
	//头删
	SLPopFront(&s);
	printf("\n");
	//按位删除
	SLErase(&s, 1);
	printf("\n");
	//按值查找
	SLFind(&s, 99);
	SLFind(&s, 5);
	printf("\n");
	//按位查找
	SLBitFind(&s, 2);
	printf("\n");
	//求表长
	SLLength(&s);
	printf("\n");
	//销毁表
	SLDestroy(&s);
	printf("\n");
}
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

测试结果：

ps：如果有什么需要补充的地方可以在评论区发表或私信！！！