• 1.顺序表-头插、头删、尾插、尾删

    文章目录

    简介

    	本文主要介绍顺序表的头插、头删、尾插、尾删、查找、插入和删除，提供全部的.c和.h文件，确保使用者直接复制粘贴到编译器上即可直接运行程序。

    • 1

    动态顺序表结构体

    typedef int SLDataType;	/*存储数据的类型*/

/*动态顺序表*/
typedef struct SeqList
{
	SLDataType* a;
	int size;		/*表示数据中存储了多少个数据*/
	int capacity;	/*数组实际能存储数据的空间容量是多大*/
}SL;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    1.头插功能

    	思路是先找到数组的最后一个元素，然后把元素一个一个都往后挪一位。最后将要插入的数据x放在数组的头的位置。

    • 1
    void SeqListPushFront(SL* ps, SLDataType x)
{
	/*检查是否扩容*/
	SeqListCheckCapacity(ps);

	int end = ps->size - 1;

	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}

	ps->a[0] = x;
	ps->size++;

	return;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    	检查是否扩容，是在插入元素时，检查数据个数是否超过了最大容量或者是否需要开辟空间，如果是需要进行空间的开辟或扩容。

    • 1
    void SeqListCheckCapacity(SL* ps)
{
	/*如果没有空间或空间不足，就扩容*/
	if (ps->capacity == ps->size)
	{
		int newCapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
		SLDataType* temp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (NULL == temp)
		{
			printf("realloc fail!\n");
			exit(-1);
		}

		ps->a = temp;
		ps->capacity = newCapacity;
	}

	return;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    2.头删功能

    	思路是先找到数组的第2个元素，然后从第2个数据开始，每个数据往前挪动一位进行数据覆盖。

    • 1
    void SeqListPopFront(SL* ps)
{
	assert(ps->size > 0);

	int begin = 1;

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

	return;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    3.尾插功能

    	思路是先检查是否需要扩容，然后将需要插入的数据x直接放到数组的尾部即可。

    • 1
    void SeqListPushBack(SL *ps, SLDataType x)
{
	/*检查是否扩容*/
	SeqListCheckCapacity(ps);
	
	ps->a[ps->size] = x;
	ps->size++;

	return;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    4.尾删功能

    	思路是直接减1有效数据的个数，以此达到删除数组中最后一个元素的目的。

    • 1
    /*尾删*/
void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->size--;

	return;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    5.查找功能

    	思路是遍历顺序表中的数字，找出符合条件的数字并返回对应下标，否则返回-1。

    • 1
    /*查找指定数字*/
int SeqListFind(SL* ps, SLDataType x)
{
	int i = 0;
	/*查找到之后返回下标，找不到返回-1*/
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			printf("找到x，下标为%d\n", i);
			return i;
		}
	}

	printf("x 不在顺序表中!\n");

	return -1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    6.插入功能

    	思路是先找到数组的最后位置，然后将数据一个一个往后挪一位。
	注意：插入函数可以实现头插功能和尾插功能
	头插：SeqListInsert(ps, 0, 10);
	尾插：SeqListInsert(ps, ps->size, 10);

    • 1
    • 2
    • 3
    • 4
    /*在指定位置插入数字*/
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(pos >= 0 && pos <= ps->size);

	int end = ps->size - 1;

	SeqListCheckCapacity(ps);

	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}

	ps->a[pos] = x;
	ps->size++;

	return;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    7.删除功能

    	思路是先找到插入位置的后一个位置，然后一个一个数据往前一个位置去覆盖。
	注意：删除函数可以实现头删功能和尾删功能
	头删：SeqListErase(ps, 0);
	尾删：SeqListErase(ps, ps->size - 1);

    • 1
    • 2
    • 3
    • 4
    /*删除指定位置的数字*/
void SeqListErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);

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

	ps->size--;

	return;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    8.此程序共包含4个文件，2个.c文件和2个.h文件

    8.1 SeqList.h文件

    	文件中包含了函数功能的头文件以及对应的结构体。

    • 1
    #pragma once
#include 
#include 


typedef int SLDataType;	/*存储数据的类型*/

/*动态顺序表*/
typedef struct SeqList
{
	SLDataType* a;
	int size;		/*表示数据中存储了多少个数据*/
	int capacity;	/*数组实际能存储数据的空间容量是多大*/
}SL;

/*接口函数*/
void SeqListInit(SL *ps);
void SeqListPushBack(SL *ps, SLDataType x);		/*尾插*/
void SeqListPopBack(SL *ps);					/*尾删*/
void SeqListPushFront(SL *ps, SLDataType x);	/*头插*/
void SeqListPopFront(SL *ps);					/*头删*/
void SeqListCheckCapacity(SL* ps);				/*检查容量*/
void SeqListFree(SL *ps);						/*释放空间*/

int SeqListFind(SL* ps, SLDataType x);			/*查找指定数字*/
void SeqListInsert(SL* ps, int pos, SLDataType x);/*指定位置插入数字*/
void SeqListErase(SL* ps, int pos);				/*删除指定位置的数据*/

/*辅助打印函数*/
void SeqListPrint(SL *ps);						/*辅助打印*/

    • 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

    8.2 SeqList.c文件

    	文件中包含了功能函数的具体实现方式。

    • 1
    #define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"
#include 

/*初始化*/
void SeqListInit(SL *ps)
{
	ps->a = NULL;
	ps->size = ps->capacity = 0;

	if ((NULL == ps->a) && (0 == ps->size) && (0 == ps->capacity))
	{
		printf("Init Success!\n");
	}
	else
	{
		printf("Init Fail!\n");
	}
	return;
}
/*尾插*/
void SeqListPushBack(SL *ps, SLDataType x)
{
	/*检查是否扩容*/
	SeqListCheckCapacity(ps);

	ps->a[ps->size] = x;
	ps->size++;

	return;
}

/*尾删*/
void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->size--;

	return;
}

/*头插*/
void SeqListPushFront(SL* ps, SLDataType x)
{
	/*检查是否扩容*/
	SeqListCheckCapacity(ps);

	int end = ps->size - 1;

	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}

	ps->a[0] = x;
	ps->size++;

	return;
}

/*头删*/
void SeqListPopFront(SL* ps)
{
	assert(ps->size > 0);

	int begin = 1;

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

	return;
}

/*扩容*/
void SeqListCheckCapacity(SL* ps)
{
	/*如果没有空间或空间不足，就扩容*/
	if (ps->capacity == ps->size)
	{
		int newCapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
		SLDataType* temp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (NULL == temp)
		{
			printf("realloc fail!\n");
			exit(-1);
		}

		ps->a = temp;
		ps->capacity = newCapacity;
	}

	return;
}

/*释放空间*/
void SeqListFree(SL* ps)
{
	free(ps->a);

	ps->a = NULL;
	ps->capacity = ps->size = 0;

	return;
}


/*辅助打印函数*/
void SeqListPrint(SL* ps)
{
	assert(ps != NULL);

	int i = 0;
	for (i = 0; i < (ps->size); i++)
	{
		printf("a[%d] = %d\n", i, ps->a[i]);
	}

	printf("\n");

	return;
}
/*查找指定数字*/
int SeqListFind(SL* ps, SLDataType x)
{
	int i = 0;
	/*查找到之后返回下标，找不到返回-1*/
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			printf("找到x，下标为%d\n", i);
			return i;
		}
	}

	printf("x 不在顺序表中!\n");

	return -1;
}
/*在指定位置插入数字*/
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
	assert(pos >= 0 && pos <= ps->size);

	int end = ps->size - 1;

	SeqListCheckCapacity(ps);

	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}

	ps->a[pos] = x;
	ps->size++;

	return;
}
/*删除指定位置的数字*/
void SeqListErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos < ps->size);

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

	ps->size--;

	return;
}

    • 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

    8.3 test.h文件

    	文件中定义了控制宏的开关，用来测试时方便的控制插入和删除的个数。

    • 1
    #pragma once

/*控制插入和删除个数的宏定义开关*/

#define SEQ_LIST_PUSH_BACK_NUM				5	/*尾插-插入数据个数*/
#define SEQ_LIST_POP_BACK_NUM				3	/*尾删-删除数据个数*/

#define SEQ_LIST_PUSH_FRONT_NUM				15	/*头插-插入数据个数*/
#define SEQ_LIST_POP_FRONT_NUM				3	/*头删-删除数据个数*/

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    8.4 test.c文件

    	用来进行相应功能的测试，TestSeqList1()和TestSeqList2()，分别测试尾插、尾删和头插、头删。使用者可以自己控制注释，来测试不同的功能。

    • 1
    #define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"
#include "test.h"

/*测试尾插和尾删功能*/
void TestSeqList1()
{
	SL s;
	int i = 0;
	/*初始化*/
	SeqListInit(&s);

	/*尾插*/
	for (i = 0; i < SEQ_LIST_PUSH_BACK_NUM; i++)
	{
		SeqListPushBack(&s, i);
	}
	
	/*打印*/
	SeqListPrint(&s);

	/*尾删*/
	for (i = 0; i < SEQ_LIST_POP_BACK_NUM; i++)
	{
		SeqListPopBack(&s);
	}

	/*打印*/
	SeqListPrint(&s);

	/*释放空间*/
	SeqListFree(&s);

	return;
}

/*测试头插和头删功能*/
void TestSeqList2()
{
	SL s;
	int i = 0;
	/*初始化*/
	SeqListInit(&s);

	/*尾插*/
	for (i = 0; i < SEQ_LIST_PUSH_BACK_NUM; i++)
	{
		SeqListPushBack(&s, i);
	}

	/*打印*/
	SeqListPrint(&s);

	/*头插*/
	for (i = 10; i < SEQ_LIST_PUSH_FRONT_NUM; i++)
	{
		SeqListPushFront(&s, i);
	}

	/*打印*/
	SeqListPrint(&s);
	
	/*头删*/
	for (i = 0; i < SEQ_LIST_POP_FRONT_NUM; i++)
	{
		SeqListPopFront(&s);
	}
	
	/*打印*/
	SeqListPrint(&s);

	/*释放空间*/
	SeqListFree(&s);

	return;
}
/*测试查找和插入*/
void TestSeqList3()
{
	SL s;
	int i = 0;
	/*初始化*/
	SeqListInit(&s);

	/*尾插*/
	for (i = 0; i < SEQ_LIST_PUSH_BACK_NUM; i++)
	{
		SeqListPushBack(&s, i);
	}

	/*打印*/
	SeqListPrint(&s);

	/*查找*/
	SeqListFind(&s, 1);

	/*插入*/
	SeqListInsert(&s, 3, 100);

	/*打印*/
	SeqListPrint(&s);

	/*删除指定位置数字*/
	SeqListErase(&s, 2);

	/*打印*/
	SeqListPrint(&s);

	/*释放空间*/
	SeqListFree(&s);

	return;
}
int main()
{
	TestSeqList1();	/*测试尾插和尾删*/

//	TestSeqList2();	/*测试头插和头删*/

//	TestSeqList3();	/*测试查找和插入*/

	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

    9.测试结果

    9.1 测试尾插和尾删的运行结果

    	从运行结果可以看出，尾插函数插入了5个元素分别是0,1,2,3,4。执行过尾删后，删除了后边的3个元素。

    • 1

    在这里插入图片描述

    9.2 测试头插和头删的运行结果

    	从运行结果可以看出，通过尾插先插入5个元素分别是0,1,2,3,4。
	然后执行头插，插入了10,11,12,13,14这5个元素，最后执行了头删，删除了前边的3个元素。

    • 1
    • 2

    在这里插入图片描述

    9.3 测试查找、插入和删除的运行结果

    	从运行结果可以看出，通过查找的函数，找到数字1在下标为1的位置上；
	然后执行插入函数，可以看出在下标为3的位置上，插入数字100；
	最后执行删除函数，可以看出删除了下标为2的位置上的数字2。

    • 1
    • 2
    • 3

    在这里插入图片描述

    10.温馨提示

    	插入和删除的个数，均是通过test.h中的宏定义来控制的。

    • 1
  • 相关阅读:
    《痞子衡嵌入式半月刊》 第 57 期
    Node.js和浏览器在JavaScript运行环境方面存在一些区别和联系
    前端面试宝典React篇01 如何拿下大厂前端面试
    jQuery+AJAX请求的统一封装
    前序中序、中序后序以及前序后序构造二叉树
    格雷希尔GripSeal密封测试接头，你了解多少？
    linux系统 常用命令(全面总结)
    每日汇评：黄金的回调可能会在周五上涨3%之后延续
    PyTorch构建分类网络（DNN，Mnist数据集）
    常用RFC规范汇总
  • 原文地址：https://blog.csdn.net/ls3614140/article/details/133998962