数据结构-顺序表基本操作-C语言代码_顺序表的基本操作代码

目录

一、准备工作

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* a;	//指向动态开辟的数组
	int size;	 //存储数据的个数
	int capacity;//存储空间的大小
}SL;
1
2
3
4
5
6
7
8
9
10
11
12

1.这里SLDataType 是给int的一个别名，因为顺序表的类型不一定是int，也有可能是double等其他类型，为了后续的修改。

二、顺序表的结构

使用结构体来构造一个顺序表

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* a;	//指向动态开辟的数组
	int size;	 //存储数据的个数
	int capacity;//存储空间的大小
}SL;
1
2
3
4
5
6
7

三、顺序表的基本操作

1.顺序表-初始化

代码如下：

//顺序表初始化
void SLInit(SL* psl)
{
	assert(psl);
	psl->a = NULL; //a是指针
	psl->capacity = psl->size = 0;
}
1
2
3
4
5
6
7

2.顺序表-头插头删 尾插尾删

可以分别进行头插头删，尾插尾删进行操作，或者直接调用下列代码中SLInsert()函数在指定位置插入数据。用SLErase()函数在指定位置删除数据。
代码如下：

//尾插
void SLPushBack(SL* psl, SLDataType x)	//插入之前，要判断内存是否够用
{
	assert(psl);

	SLCheckcapacity(psl);
	psl->a[psl->size] = x;
	psl->size++;
	 
	//或者直接调用尾插
	//SLInsert(psl, psl->size, x);
}
//头插
void SLPushFront(SL* psl, SLDataType x)
{
	assert(psl);//必须是连续的空间
	SLCheckcapacity(psl);
	//挪动数据(从后往前)
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		--end;
	}
	psl->a[0] = x;
	psl->size++;

	//或者直接调用头插
	//SLInsert(psl, 0, x);

//尾删
void SLPopBack(SL* psl)
{
	assert(psl);
	//温柔检查
	if (psl->size == 0)
	{
		return;
	}
	//暴力检查
	//assert(psl->size > 0);
	psl->size--;

	//或者直接调用SLErase进行尾删
	SLErase(psl, psl->size - 1);
}

//头删
void SLPopFront(SL* psl)
{
	assert(psl);
	int begin = 0;
	while (begin < psl->size)
	{
		psl->a[begin] = psl->a[begin + 1];
		++begin;
	}
	--psl->size;

	//或者直接调用SLErase进行头删
	SLErase(psl, 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

3.顺序表-元素查找

int SLFind(SL* psl, SLDataType x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;//下标
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12

4.顺序表-指定位置插入数据

void SLInsert(SL* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos <= psl->size);
	SLCheckcapacity(psl);//检查扩容

	//挪动数据
	//size_t  end = psl->size - 1;	//注意：size-1
	//while(end >= (int)pos)	//两个类型不同，0不可以,所以强转一下int		  
	//{
	//	psl->a[end + 1] = psl->a[end];
	//	end--;
	//}
	//或者
	size_t  end = psl->size ;//注意：size
	while (end > pos)	//两个类型不同，0不可以,所以强转一下int		  
	{
		psl->a[end] = psl->a[end-1];
		end--;
	}
	psl->a[pos] = x;
	psl->size++;
	 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

5.顺序表-指定位置删除数据

void SLErase(SL* psl, size_t pos)
{
	assert(psl);
	assert(pos < psl->size);
	size_t begin = pos;
	while (begin < psl->size - 1)
	{
		psl->a[begin] = psl->a[begin + 1];
		begin++;
	}
	psl->size--;
	 
}
1
2
3
4
5
6
7
8
9
10
11
12
13

6.顺序表-打印数据

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

7.顺序表-修改数据

void SLModify(SL* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos < psl->size);
	psl->a[pos] = x;

}	
1
2
3
4
5
6
7

8.顺序表-销毁数据

//顺序表销毁
void SLDestory(SL* psl)
{
	assert(psl);
	if (psl->a)
	{
		free(psl->a);
		psl->a = NULL;
		psl->capacity = psl->size = 0;
	}
}
1
2
3
4
5
6
7
8
9
10
11

四.全部代码

1.SeqList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* a;	//指向动态开辟的数组
	int size;	 //存储数据的个数
	int capacity;//存储空间的大小
}SL;

//初始化
void SLInit(SL* psl);

//顺序表的销毁
void SLDestory(SL* psl);

//打印
void SLPrint(const SL* psl);

// 头插头删 尾插尾删
void SLPushBack(SL* psl, SLDataType x);
void SLPushFront(SL* psl, SLDataType x);
void SLPopBack(SL* psl);
void SLPopFront(SL* psl);

// 没有找到就返回-1
int SLFind(SL* psl, SLDataType x);
// 顺序表在pos位置插入x
void SLInsert(SL* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SLErase(SL* psl, size_t pos);
//修改某个位置
void SLModify(SL* psl, size_t pos, SLDataType x);

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

2.SeqList.c

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"

void SLPrint(const SL* psl)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}

//顺序表初始化
void SLInit(SL* psl)
{
	assert(psl);
	psl->a = NULL; //a是指针
	psl->capacity = psl->size = 0;
}

//顺序表销毁
void SLDestory(SL* psl)
{
	assert(psl);
	if (psl->a)
	{
		free(psl->a);
		psl->a = NULL;
		psl->capacity = psl->size = 0;
	}
}

//检查容量函数
void SLCheckcapacity(SL* psl)
{
	//检查容量
	if (psl->size == psl->capacity)
	{
		//刚开始是0，给四个容量，不是的话，扩展2倍
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		//用一个临时指针，来判断开辟空间是否失败
		SLDataType* tmp = realloc(psl->a, newcapacity * sizeof(SLDataType)); //扩容：长度*单个长度//原地扩容或者异地扩容
		if (tmp == NULL)
		{
			perror("realloc fail");
			//return;
			exit(-1);
		}
		psl->a = tmp;
		psl->capacity = newcapacity;
	}
}

void SLPushBack(SL* psl, SLDataType x)	//插入之前，要判断内存是否够用
{
	//assert(psl);

	//SLCheckcapacity(psl);
	//psl->a[psl->size] = x;
	//psl->size++;
	 
	//或者直接调用尾插
	SLInsert(psl, psl->size, x);
}

void SLPushFront(SL* psl, SLDataType x)
{
	//assert(psl);//必须是连续的空间
	//SLCheckcapacity(psl);
	挪动数据(从后往前)
	//int end = psl->size - 1;
	//while (end >= 0)
	//{
	//	psl->a[end + 1] = psl->a[end];
	//	--end;
	//}
	//psl->a[0] = x;
	//psl->size++;

	//或者直接调用头插
	SLInsert(psl, 0, x);
}

void SLPopBack(SL* psl)
{
	//assert(psl);
	温柔检查
	//if (psl->size == 0)
	//{
	//	return;
	//}
	暴力检查
	assert(psl->size > 0);
	//psl->size--;

	//或者直接调用SLErase进行尾删
	SLErase(psl, psl->size - 1);
}

void SLPopFront(SL* psl)
{
	//assert(psl);
	//int begin = 0;
	//while (begin < psl->size)
	//{
	//	psl->a[begin] = psl->a[begin + 1];
	//	++begin;
	//}
	//--psl->size;

	//或者直接调用SLErase进行头删
	SLErase(psl, 0);

}

int SLFind(SL* psl, SLDataType x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;//下标
		}
	}
	return -1;
}

void SLInsert(SL* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos <= psl->size);
	SLCheckcapacity(psl);//检查扩容

	//挪动数据
	//size_t  end = psl->size - 1;	//注意：size-1
	//while(end >= (int)pos)	//两个类型不同，0不可以,所以强转一下int		  
	//{
	//	psl->a[end + 1] = psl->a[end];
	//	end--;
	//}
	//或者
	size_t  end = psl->size ;//注意：size
	while (end > pos)	//两个类型不同，0不可以,所以强转一下int		  
	{
		psl->a[end] = psl->a[end-1];
		end--;
	}
	psl->a[pos] = x;
	psl->size++;
	 
}

void SLErase(SL* psl, size_t pos)
{
	assert(psl);
	assert(pos < psl->size);
	size_t begin = pos;
	while (begin < psl->size - 1)
	{
		psl->a[begin] = psl->a[begin + 1];
		begin++;
	}
	psl->size--;
	 
}

void SLModify(SL* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos < psl->size);
	psl->a[pos] = x;

}			
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
172
173
174
175

3.test.c(测试代码)

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"

void TestSeqList1()
{
	SL s;
	SLInit(&s);	//传地址

 	//SLPrint(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPushBack(&s, 6);

	//SLPrint(&s);

	SLPushFront(&s, 10);
	SLPushFront(&s, 20);
	SLPushFront(&s, 30);

	SLPrint(&s);

	SLPopBack(&s);

	SLDestory(&s);

}

void TestSeqList2()
{
	SL s;
	SLInit(&s);	  //传地址
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPrint(&s);

	//尾删
	SLPopBack(&s);
	SLPopBack(&s);
	SLPrint(&s);

	SLPopBack(&s);
	SLPopBack(&s);
	SLPrint(&s);

	//SLPopBack(&s);
	//SLPrint(&s);

	SLPushBack(&s, 10);
	SLPushBack(&s, 20);
	SLPushBack(&s, 30);
	SLPushBack(&s, 40);
	SLPrint(&s);

	SLDestory(&s);
}

void TestSeqList3()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPrint(&s);

	//头删
	SLPopFront(&s);
	SLPopFront(&s);
	SLPrint(&s);

	SLPopFront(&s);
	SLPopFront(&s);
	SLPrint(&s);

	SLPushBack(&s, 10);
	SLPushBack(&s, 20);
	SLPushBack(&s, 30);
	SLPushBack(&s, 40);
	SLPrint(&s);

	int* p1 = (int*)malloc(sizeof(int) * 10);
	assert(p1);
	printf("p1:%p\n", p1);	//检查是否原地扩容

	int* p2 = (int*)realloc(p1, sizeof(int) * 5);
	assert(p2);
	printf("p2:%p\n", p2);
}

void TestSeqList4()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPrint(&s);

	SLInsert(&s, 2, 30);//在第二个位置插入30
	SLPrint(&s);

	int x = 0;
	scanf("%d", &x);
	int pos = SLFind(&s, x);//在某个特定的位置插入数字
	if (pos != -1)
	{
		SLInsert(&s, pos, x * 100);
	}
	SLPrint(&s);
}

void TestSeqList5()
{
	SL s;
	SLInit(&s);
	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);
	SLPrint(&s);

	//删除头数字
	SLErase(&s, 0);
	SLPrint(&s);

	//也可以选择数字删除
	int x = 0;
	scanf("%d", &x);
	int pos = SLFind(&s, x);
	if (pos != -1)
	{
		SLErase(&s, pos);
	}
	SLPrint(&s);

}
//int main()
//{
//	TestSeqList2();
//	TestSeqList3();
//	//TestSeqList3();
//	//TestSeqList4();
//
//	return 0;
//}

//菜单
void memu()
{
	printf("****************************************\n");
	printf("1、尾插数据 2、头插数据\n");
	printf("7、打印数据 -1、退出\n");
	printf("****************************************\n");
}

int main()
{
	SL s;
	SLInit(&s);
	int option = 0;
	int x = 0;
	do
	{
		memu();
		printf("请输入你的操作:>");
		scanf("%d", &option);
		switch (option)
		{
		case 1:
			printf("请连续输入你要插入的数据，以-1结束\n");
			scanf("%d", &x);
			while (x != -1)
			{
				SLPushBack(&s, x);
				scanf("%d", &x);
			}
			break;
		case 2:
			break;
		case 3:
			break;
		case 7:
			SLPrint(&s);
			break;
		default:
			break;
		}

	} while (option != -1);

	SLDestory(&s);

	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
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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202