数据结构--顺序表

1.定义

顺序表是线性表的一种存储结构，用一组地址连续的存储单元依次存储线性表的数据元素。它把逻辑上相邻的数据元素存储在物理位置上也相邻的存储单元中，元素之间的逻辑关系由存储单元的邻接关系来体现。

2.基本操作

1. 容量检查和扩容：SeqListCheckCapacity 会检查顺序表是否已满，若满则进行扩容操作，扩容策略是初始容量为 4，后续每次扩容为原来的 2 倍。
2. 插入和删除操作：支持头插（SeqListPushFront）、尾插（SeqListPushBack）、头删（SeqListPopFront）、尾删（SeqListPopBack），以及在指定位置插入（SeqListInsert）和删除元素（SeqListErase）。
3. 查找和修改操作：SeqListFind 用于查找指定元素的位置，SeqListModity 用于修改指定位置的元素值。
4. 打印操作：SeqListPrint 用于打印顺序表中的所有元素。

3.代码实现

3.1初始化

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

3.2销毁顺序表

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

3.3检查空间(扩容）

void SeqListCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SQDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
}

3.4打印顺序表

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

3.5尾插

void SeqListPushBack(SL* ps, SQDataType x)
{
	SeqListCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
}

3.6头插

void SeqListPushFront(SL* ps, SQDataType 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++;

}

3.7头删

void SeqListPopFront(SL* ps)
{
	assert(ps->size > 0);
	int start = 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		++start;
	}
	ps->size--;
}

3.8 尾删

void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->a[ps->size - 1] = 0;
	ps->size--;
}

3.9任意位置插入

void SeqListInsert(SL* ps, int pos, SQDataType x)
{
	assert(pos <= ps->size);
	SeqListCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[pos] = x;
	ps->size++;
}

3.10在任意位置删除

void SeqListErase(SL* ps, int pos)
{
	assert(pos < ps->size);
	int start = pos + 1;
	while (start < ps->size)
	{
		ps->a[start-1] = ps->a[start];
		++start;
	}
	ps->size--;
}

3.11查找数据所在位置

int SeqListFind(SL* ps, SQDataType x)
{
	for (int i = 0; i < ps->size; ++i)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

3.12在任意位置修改数据

void SeqListModity(SL* ps, int pos, SQDataType x)
{
	assert(pos < ps->size);
	ps->a[pos] = x;
}

C 语言实现顺序表操作代码详解 在数据结构的学习与实践进程中，顺序表作为线性表的一种基础且关键的实现形式，占据着重要地位。接下来，我们将对一段 C 语言代码进行深度剖析，以此深入探究顺序表在初始化、增容、插入、删除、查找及销毁等核心操作上的具体实现逻辑。 代码整体架构 整个代码以结构体SL（代表顺序表）为核心展开设计。SL结构体内部包含用于存储数据的数组指针arr、记录当前数据个数的size，以及表示数组容量的capacity 。后续所有针对顺序表的操作函数，均以SL*类型的指针作为参数，实现对顺序表的各项操作。 #include"SeqList.h"

// 假设SLDataType为顺序表存储的数据类型，如int typedef int SLDataType;

// 顺序表结构体定义 typedef struct SeqList { SLDataType* arr; int size; int capacity; }SL;

核心操作函数详解 初始化函数SLInit //初始化 void SLInit(SL* ps) { ps->arr = NULL; ps->size = ps->capacity = 0; }

SLInit函数用于对顺序表进行初始化操作。它将顺序表指针ps所指向的顺序表的相关属性进行初始化设置：把数据存储指针arr赋值为NULL，表示当前没有分配实际的存储内存；同时将数据个数size和容量capacity均设置为0，为后续的顺序表操作搭建好初始环境。 容量检查与增容函数SLCheckCapacity void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity) { int newCapacity = ps->capacity == 0? 4 : 2 * ps->capacity; //增容 //realloc第二个参数，单位是字节 SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType)); if (tmp == NULL) { perror(“realloc fail!”); exit(1); } ps->arr = tmp; ps->capacity = newCapacity; } }

SLCheckCapacity函数承担着检查顺序表容量并在必要时进行增容的重要职责。当顺序表中已存储的数据个数size达到当前设定的容量capacity时，函数会触发增容逻辑。若当前容量为0，则将新容量设定为4；若当前容量不为0，则新容量为原来的2倍。借助realloc函数对顺序表的存储内存进行重新分配，若内存重新分配失败，函数会通过perror打印错误信息，并调用exit(1)终止程序运行；若分配成功，则更新顺序表的存储指针arr和容量capacity，确保顺序表能够容纳更多数据。 尾插函数SLPushBack //尾插 void SLPushBack(SL* ps, SLDataType x) { assert(ps); //判断空间是否足够 SLCheckCapacity(ps); //空间足够的情况下 ps->arr[ps->size++] = x; }

SLPushBack函数实现了在顺序表尾部插入数据的功能。首先，通过assert宏对传入的顺序表指针ps进行有效性检查，确保指针不为NULL 。接着调用SLCheckCapacity函数检查顺序表的容量，若容量不足则进行增容操作。在容量充足的条件下，将数据x直接插入到顺序表的末尾位置，并通过ps->size++操作更新顺序表中数据的个数，使顺序表能够及时反映新数据的插入情况。 头插函数SLPushFront //头插 void SLPushFront(SL* ps, SLDataType x) { assert(ps != NULL); //判断空间是否足够 SLCheckCapacity(ps); //将顺序表中所有数据向后挪动一位 for (int i = ps->size; i > 0; i–) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[0] = x; ++ps->size; }

SLPushFront函数负责在顺序表的头部插入数据。同样，先使用assert宏确保传入的顺序表指针ps有效。随后检查顺序表容量，若需要则进行增容。在容量满足要求后，通过循环将顺序表中已有的所有数据整体向后移动一位，为新数据在头部腾出空间。最后将数据x插入到顺序表的头部位置，并将数据个数size加1，完成头插操作。 尾删函数SLPopBack //尾删 void SLPopBack(SL* ps) { //ps：限制参数不能直接给NULL //ps->size：顺序表为空 assert(ps && ps->size); –ps->size; }

SLPopBack函数用于实现顺序表的尾删操作。借助assert宏，对传入的顺序表指针ps以及当前顺序表中的数据个数size进行双重检查，确保顺序表指针有效且顺序表中存在数据。在满足条件的情况下，直接将数据个数size减1，即可实现删除顺序表末尾数据的功能，该操作简单直接，通过修改数据个数来达到删除效果。 头删函数SLPopFront //头删 void SLPopFront(SL* ps) { assert(ps && ps->size); for (int i = 0; i < ps->size - 1; i++) { ps->arr[i] = ps->arr[i + 1]; } –ps->size; }

SLPopFront函数用于执行顺序表的头删操作。首先通过assert宏验证顺序表指针有效且顺序表不为空。然后，通过循环将顺序表中除最后一个元素之外的所有数据依次向前移动一位，从而覆盖掉原来的头部数据。最后将数据个数size减1，完成头删操作，实现从顺序表头部移除数据的目的。 指定位置插入函数SLInsert //指定位置之前插入数据 void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size);

SLCheckCapacity(ps);
//pos及之后的数据整体向后挪动一位
for (int i = ps->size; i > pos; i--)
{
    ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
++ps->size;

}

SLInsert函数实现了在顺序表指定位置插入数据的功能。函数首先对传入的顺序表指针ps进行有效性检查，并确保插入位置pos在合法范围内（即0到size之间）。接着检查顺序表容量，若容量不足则进行增容。在满足容量条件后，通过循环将插入位置pos及之后的数据整体向后移动一位，为新数据腾出插入空间。然后将数据x插入到指定的pos位置，并将数据个数size加1，完成在指定位置插入数据的操作。 指定位置删除函数SLErase // 删除POS位置的数据 void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size);

//pos之后的数据整体向前挪动一位
for (int i = pos; i < ps->size - 1; i++)
{
    ps->arr[i] = ps->arr[i + 1];
}
--ps->size;

}

SLErase函数用于删除顺序表中指定位置的数据。同样，先对顺序表指针ps和删除位置pos进行合法性检查，确保顺序表有效且删除位置在合理范围内（即0到size - 1之间）。然后通过循环将删除位置pos之后的数据整体向前移动一位，覆盖掉要删除的数据。最后将数据个数size减1，实现从顺序表中删除指定位置数据的功能。 查找函数SLFind //查找 int SLFind(SL* ps, SLDataType x) { for (int i = 0; i < ps->size; i++) { if (ps->arr[i] == x) { //找到了 return i; } } //未找到 return -1; }

SLFind函数的作用是在顺序表中查找指定数据x。函数通过遍历顺序表中的每一个数据元素，将其与目标数据x进行逐一比较。若在遍历过程中找到与x相等的数据元素，则返回该元素在顺序表中的下标；若遍历完整个顺序表（即遍历次数达到数据个数size）仍未找到匹配的数据，则返回-1，表示目标数据在当前顺序表中不存在。 销毁函数SLDestroy //销毁 void SLDestroy(SL* ps) { assert(ps); if (ps->arr) free(ps->arr); ps->arr = NULL; ps->size = ps->capacity = 0; }

SLDestroy函数用于完成对顺序表的销毁操作。首先使用assert宏确保传入的顺序表指针ps有效。然后检查顺序表的数据存储指针arr，若arr不为NULL，则调用free函数释放其指向的内存空间，避免内存泄漏。接着将arr置为NULL，并将数据个数size和容量capacity都设置为0，完成整个顺序表的销毁过程，使顺序表恢复到初始化前的状态。 总结 上述 C 语言代码完整且系统地实现了顺序表的各项基本操作。借助这些函数，我们能够灵活地对顺序表进行数据的插入、删除、查找等操作，满足不同场景下的数据处理需求。在实际应用场景中，顺序表凭借其随机访问效率高的显著优点，在许多场景中发挥着重要作用。然而，由于其在插入和删除操作时，可能需要移动大量的数据，导致时间复杂度相对较高，这也是在使用顺序表时需要重点考虑的因素。深入理解这些操作的实现原理，不仅有助于我们在合适的场景中精准选择和高效使用顺序表这种数据结构，还能为我们进一步探索和学习其他更为复杂的数据结构奠定坚实的基础。 如果你还想对博客内容进行更多优化，比如增加代码运行示例、对比不同操作的时间复杂度图表，欢迎告诉我。