当前位置:   article > 正文

【数据结构】顺序表 C语言代码实现 以及realloc的使用_顺序表c语言代码

顺序表c语言代码

简介

顺序表(Sequential List)是一种线性表的存储结构,用于表示元素之间的顺序关系。顺序表中的元素在内存中是连续存储的。

顺序表可以使用数组实现,它具有以下特点

  • 元素在内存中的存储是连续的,可以通过下标直接访问元素,使得随机访问非常高效
  • 插入和删除操作的效率相对较低,因为需要移动其他元素来保持顺序性。

顺序表的创建

静态顺序表

在这里插入图片描述

//SeqList.h
#define N 20
typedef int SLDataType; //使用typedef可以使顺序表中元素的类容方便修改

struct SeqList
{
	SLDataType a[N];//定义数组长度
	int size;		//定义有效数据个数
};//静态顺序表--N太小,可能不够用,N太大,可能浪费空间
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

动态顺序表

在这里插入图片描述
在不知道所存储的内容的数量时,一般使用动态的顺序表,以节省空间。

//SeqList.h
typedef int SLDataType; //使用typedef可以使顺序表中元素的类容方便修改

typedef struct SeqList
{
	SLDataType* a;  //指向动态数组指针
	int size;       //数据个数
	int capacity;   //容量空间大小
}SL; //这里使用typedef创建该结构体类型变量时更方便
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

初始化与销毁顺序表(SLInit 、 SLDestory)

  • 初始化:将结构体指针 sl 置为 NULL, 大小与容积置为0;
  • 销毁:将结构体指针 sl 释放,指针置为空,大小与容积置为0;
//SeqList.h
//初始化/销毁
void SLInit(SL* ps);
void SLDestory(SL* ps);
  • 1
  • 2
  • 3
  • 4
//SeqList.c
void SLInit(SL* ps)
{
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

void SLDestory(SL* ps)
{
	if (ps->a)
	{
		free(ps->a);
		ps->a = NULL;
		ps->capacity = ps->size = 0;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

扩容(SLCheckCapacity)

因为创建的顺序表示个动态存储的顺序表那么就得满足当容量不足的时候,能够进行扩容,而不是一开始在定义结构体的时候就将顺序表的容量写死。
这里采用的是检查容量的方式来实现顺序表的动态存储,size 是已经存入的数据个数,capacity 是可以存储数据的个数,当存入和容量相等即空间满了的时候,这里采用realloc函数对顺序表进行扩容。
因为realloc函数实在堆区申请空间的所以一次扩容不宜过多这里是一次扩容到原来的两倍

//SeqList.h
//检查容量空间,满了扩容
void SLCheckCapacity(SL* ps);
  • 1
  • 2
  • 3
//SeqList.c
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int  newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)//指针判空,以防ralloc失败
		{
			printf("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

realloc

在这里插入图片描述

realloc(void *__ptr, size_t __size):更改已经配置的内存空间,即更改由malloc()函数分配的内存空间的大小
如果将分配的内存减少,realloc仅仅是改变索引的信息。

如果是将分配的内存扩大,则有以下情况:

  • 如果当前内存段后面有需要的内存空间,则直接扩展这段内存空间,realloc()将返回原指针。
  • 如果当前内存段后面的空闲字节不够,那么就使用堆中的第一个能够满足这一要求的内存块,将目前的数据复制到新的位置,并将原来的数据块释放掉返回新的内存块位置
  • 如果申请失败,将返回NULL,此时,原来的指针仍然有效。

注意:如果调用成功,不管当前内存段后面的空闲空间是否满足要求,都会释放掉原来的指针,重新返回一个指针,虽然返回的指针有可能和原来的指针一样,即不能再次释放掉原来的指针。

头插、头删(SLPushBack、SLPopBack)

在这里插入图片描述
在这里插入图片描述

//SeqList.h
//尾插/尾删
//时间复杂度O(1)
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
  • 1
  • 2
  • 3
  • 4
  • 5
//SeqList.c
void SLPushBack(SL* ps, SLDataType x)
{
	//SLCheckCapacity(ps);

	//	ps->a[ps->size] = x; //在顺序表得尾部添加一个数据
	//ps->size++;  

	SLInsert(ps, ps->size, x);//复用SLInsert,SLPushFront相当于插入到最后一个元素
}

void SLPushFront(SL* ps, SLDataType x)
{
	//SLCheckCapacity(ps);
	
	将所有数据向后挪一个
	//int end = ps->size - 1;
	//while (end >= 0)
	//{
	//	ps->a[end + 1] = ps->a[end];
	//	--end;
	//}
	//ps->a[0] = x;
	//ps->size++;


	SLInsert(ps, 0, x);//复用SLInsert,SLPushFront相当于插入第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

头插、头删(SLPushFront、SLPopFront)

在这里插入图片描述
在这里插入图片描述

//SeqList.h
//时间复杂度O(N)
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
  • 1
  • 2
  • 3
  • 4
//SeqList.c
void SLPopBack(SL* ps)
{
	//ps->a[ps->size - 1] = 0;

	//以防越界
	//if (ps->size == 0)
	//{
	//	printf("SeqList is empty\n");
	//	return;
	//}

	//暴力检查
	//assert(ps->size > 0);

	//ps->size--;


	SLErase(ps, ps->size - 1);//复用
}

void SLPopFront(SL* ps)
{
	//assert(ps->size > 0);

	//挪移
	//int begin = 1;
	//while (begin < ps->size )
	//{
	//	ps->a[begin - 1] = ps->a[begin];
	//	++begin;
	//}

	//ps->size--;

	SLErase(ps, 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

在任意的位置插入、删除(SLInsert、SLErase)

在这里插入图片描述

在这里插入图片描述

//SeqList.h
//在任意的位置插入删除
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
  • 1
  • 2
  • 3
  • 4
//SeqList.c
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);//可以在最后一个元素后面添加,所以用<=size

	SLCheckCapacity(ps);

	//挪用数据
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[pos] = x;
	ps->size++;
}

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	//1.
	//int begin = pos;
	//while (begin < ps-> size - 1)
	//{
	//	ps->a[begin] = ps->a[begin + 1];
	//	++begin;
	//}

	//2.
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}

	ps->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
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

查找、修改(SLFind、SLModify)

在这里插入图片描述
在这里插入图片描述

//SeqList.h
//查找/修改
int* SLFind(SL* ps, SLDataType x);//找到返回数据下标数组,没有找到则返回-1
void SLModify(SL* ps, int pos, SLDataType x);
  • 1
  • 2
  • 3
  • 4
//SeqList.c
int* SLFind(SL* ps, SLDataType x)
{
	//只能找一个
	//assert(ps);
	//for (int i = 0; i < ps->size; ++i)
	//{
	//	if (ps->a[i] == x)
	//	{
	//		return i;
	//	}
	//}
	//return -1;

	//找多个
	assert(ps);
	SLDataType val;
	int* arr;
	int t = 0;
	arr = (int*)malloc((ps->size + 1) * sizeof(int));
	if (arr == NULL) //指针判空,以防malloc失败
	{
		perror("InitContact::malloc");
		exit(-1);
	}
	for (int i = 0; i < ps->size; ++i)
	{
		if (ps->a[i] == x)
		{
			arr[t++] = i;
		}
	}
	arr[t] = -1;
	return arr;
}

void SLModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	ps->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

完整代码

test.c

#define _CRT_SECURE_NO_WARNINGS 1


#include "SeqList.h"

enum op
{
	Exit,     //0
	PushBack, //1
	PopBack,  //2
	PushFront,//3 
	PopFront, //4
	Insert,   //5
	Erase,    //6
	Find,     //7
	Modify,   //8
};

void menu()
{
	printf("\n");
	printf("**************************************\n");
	printf("********1.PushBack    2.PopBack ******\n");
	printf("********3.PushFront   4.PopFront******\n");
	printf("********5.Insert      6.Erase   ******\n");
	printf("********7.Find        8.Modify  ******\n");
	printf("********0.Exit                  ******\n");
	printf("**************************************\n");
}

void MultiPushBack(SL* ps)
{
	assert(ps);
	SLDataType val;
	printf("请连续输入你要“尾插”的数据,以-1结束:>");
	scanf("%d", &val);
	while (val != -1)
	{
		SLPushBack(ps, val);
		scanf("%d", &val);
	}
	SLPrint(ps);
}

void MultiPopBack(SL* ps)
{
	assert(ps);
	int num;
	printf("请连续输入你要“尾删”的个数:>");
	scanf("%d", &num);
	for (int i = 0; i < num; i++)
	{
		SLPopBack(ps);
	}
	SLPrint(ps);
}

void MultiPushFront(SL* ps)
{
	assert(ps);
	SLDataType val;
	printf("请连续输入你要“头插”的数据,以-1结束:>");
	scanf("%d", &val);
	while (val != -1)
	{
		SLPushFront(ps, val);
		scanf("%d", &val);
	}
	SLPrint(ps);
}

void MultiPopFront(SL* ps)
{
	assert(ps);
	int num;
	printf("请连续输入你要“头删”的个数:>");
	scanf("%d", &num);
	for (int i = 0; i < num; i++)
	{
		SLPopFront(ps);
	}
	SLPrint(ps);
}

void MultiInsert(SL* ps)
{
	assert(ps);
	SLDataType val;
	int pos;
	printf("请输入你要“插入”的位置:>");
	scanf("%d", &pos);
	printf("请连续输入你要“插入”的数据,以-1结束:>");	
	scanf("%d", &val);
	while (val != -1)
	{
		SLInsert(ps, pos++, val);
		scanf("%d", &val);
	}
	SLPrint(ps);
}

void MultiErase(SL* ps)
{
	assert(ps);
	int num;
	int pos;
	printf("请输入你要“删除”的位置:>");
	scanf("%d", &pos);
	printf("请连续输入你要“删除”的数据的个数:>");
	scanf("%d", &num);
	for (int i = 0; i < num; i++)
	{
		SLErase(ps, pos);
	}
	SLPrint(ps);
}

void MultiFind(SL* ps)
{
	assert(ps);
	SLDataType val;
	int* arr;
	int t;
	arr = (int*)malloc((ps->size + 1) * sizeof(int));
	if (arr == NULL) //指针判空,以防malloc失败
	{
		perror("InitContact::malloc");
		exit(-1);
	}
	printf("请输入你要找的内容:>");
	scanf("%d", &val);
	arr = SLFind(ps, val);
	if (*arr == -1)
	{
		printf("你所找的内容不存在!\n");
		return;
	}
	printf("你所找的内容下标分别为:");
	for (int i = 0; arr[i] != -1; i++)
	{
		printf("%-5d", arr[i]);
	}
	printf("\n");
	free(arr);
}

void MultiModify(SL* ps)
{
	assert(ps);
	SLDataType val;
	SLDataType C_val;
	int* arr;
	int t;
	arr = (int*)malloc((ps->size + 1) * sizeof(int));
	if (arr == NULL) //指针判空,以防malloc失败
	{
		perror("InitContact::malloc");
		exit(-1);
	}
	printf("请输入你“修改的内容”以及“修改后的值”:>");
	scanf("%d%d", &val, &C_val);
	arr = SLFind(ps, val);
	if (*arr == -1)
	{
		printf("你所修改的内容不存在!\n");
		return;
	}
	for (int i = 0; arr[i] != -1; i++)
	{
		SLModify(ps, arr[i], C_val);
	}
	SLPrint(ps);
	free(arr);
}

void SeqListTest()
{
	SL sl;
	SLInit(&sl);
	int option;
	do
	{
		menu();
		printf("请输入选项:>");
		scanf("%d", &option);
		switch (option)
		{
		case 0:
			SLDestory(&sl);
			printf("退出程序!\n");
			exit(-1);
			break;
		case PushBack:
			MultiPushBack(&sl);
			break;
		case PopBack:
			MultiPopBack(&sl);
			break;
		case PushFront:
			MultiPushFront(&sl);
			break;
		case PopFront:
			MultiPopFront(&sl);
			break;
		case Insert:
			MultiInsert(&sl);
			break;
		case Erase:
			MultiErase(&sl);
			break;
		case Find:
			MultiFind(&sl);
			break;
		case Modify:
			MultiModify(&sl);
			break;
		default:
			printf("输入无效!\n");
			break;
		}
	} while (1);

}

int main()
{
	SeqListTest();
	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
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "SeqList.h"

void SLPrint(SL* ps)
{
	//assert(ps != NULL)
	assert(ps);//暴力的防御检查,可以指出错误地方
	printf("\n");
	printf("序号: ");
	for (int i = 0; i < ps->size; ++i)
	{
		printf("%-5d", i);
	}
	printf("\n");
	printf("内容: ");
	for (int i = 0; i < ps->size; ++i)
	{
		printf("%-5d", ps->a[i]);
	}
	printf("\n");
}

void SLInit(SL* ps)
{
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

void SLDestory(SL* ps)
{
	if (ps->a)
	{
		free(ps->a);
		ps->a = NULL;
		ps->capacity = ps->size = 0;
	}
}

void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int  newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)//指针判空,以防ralloc失败
		{
			printf("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
}
/***************************************************
因为创建的顺序表示个动态存储的顺序表那么就得满足当容量不足的时候,
能够进行扩容,而不是一开始在定义结构体的时候就将顺序表的容量写死。
这里采用的是检查容量的方式来实现顺序表的动态存储,
(size)是已经存入的数据个数,(capacity)是可以存储数据的个数,
当存入和容量相等即空间满了的时候,这里采用realloc函数对顺序表进行扩容。
因为realloc函数实在堆区申请空间的所以一次扩容不宜过多这里是一次扩容到原来的两倍。
******************************************************************************/


void SLPushBack(SL* ps, SLDataType x)
{
	//SLCheckCapacity(ps);

	//	ps->a[ps->size] = x; //在顺序表得尾部添加一个数据
	//ps->size++;  

	SLInsert(ps, ps->size, x);//复用SLInsert,SLPushFront相当于插入到最后一个元素
}

void SLPushFront(SL* ps, SLDataType x)
{
	//SLCheckCapacity(ps);
	
	将所有数据向后挪一个
	//int end = ps->size - 1;
	//while (end >= 0)
	//{
	//	ps->a[end + 1] = ps->a[end];
	//	--end;
	//}
	//ps->a[0] = x;
	//ps->size++;


	SLInsert(ps, 0, x);//复用SLInsert,SLPushFront相当于插入第0个元素
}

void SLPopBack(SL* ps)
{
	//ps->a[ps->size - 1] = 0;

	//以防越界
	//if (ps->size == 0)
	//{
	//	printf("SeqList is empty\n");
	//	return;
	//}

	//暴力检查
	//assert(ps->size > 0);

	//ps->size--;


	SLErase(ps, ps->size - 1);//复用
}

void SLPopFront(SL* ps)
{
	//assert(ps->size > 0);

	//挪移
	//int begin = 1;
	//while (begin < ps->size )
	//{
	//	ps->a[begin - 1] = ps->a[begin];
	//	++begin;
	//}

	//ps->size--;

	SLErase(ps, 0);//复用
}

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);//可以在最后一个元素后面添加,所以用<=size

	SLCheckCapacity(ps);

	//挪用数据
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[pos] = x;
	ps->size++;
}

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	//1.
	//int begin = pos;
	//while (begin < ps-> size - 1)
	//{
	//	ps->a[begin] = ps->a[begin + 1];
	//	++begin;
	//}

	//2.
	int begin = pos + 1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}

	ps->size--;
}


int* SLFind(SL* ps, SLDataType x)
{
	//只能找一个
	//assert(ps);
	//for (int i = 0; i < ps->size; ++i)
	//{
	//	if (ps->a[i] == x)
	//	{
	//		return i;
	//	}
	//}
	//return -1;

	//找多个
	assert(ps);
	SLDataType val;
	int* arr;
	int t = 0;
	arr = (int*)malloc((ps->size + 1) * sizeof(int));
	if (arr == NULL) //指针判空,以防malloc失败
	{
		perror("InitContact::malloc");
		exit(-1);
	}
	for (int i = 0; i < ps->size; ++i)
	{
		if (ps->a[i] == x)
		{
			arr[t++] = i;
		}
	}
	arr[t] = -1;
	return arr;
}

void SLModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	ps->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
  • 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
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214

SeqList.h

#pragma once

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

//#define N 20
typedef int SLDataType; //使用typedef可以使顺序表中元素的类容方便修改

//struct SeqList
//{
//	SLDataType a[N];//定义数组长度
//	int size;		//定义有效数据个数
//};//静态顺序表--N太小,可能不够用,N太大,可能浪费空间

typedef struct SeqList
{
	SLDataType* a;  //指向动态数组指针
	int size;       //数据个数
	int capacity;   //容量空间大小
}SL; //这里使用typedef创建该结构体类型变量时更方便

//打印顺序表
void SLPrint(SL* ps);

//初始化/销毁
void SLInit(SL* ps);
void SLDestory(SL* ps);

//检查容量空间,满了扩容
void SLCheckCapacity(SL* ps);

//尾插/尾删/头插/头删/
//时间复杂度O(1)
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);

//时间复杂度O(N)
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);

//在任意的位置插入删除
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);

//查找/修改
int* SLFind(SL* ps, SLDataType x);//找到返回数据下标数组,没有找到则返回-1
void SLModify(SL* ps, int 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
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/凡人多烦事01/article/detail/416607
推荐阅读
相关标签
  

闽ICP备14008679号