线性表-顺序表的操作（增删查改，扩容，缩容）

SeqList.h

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


typedef struct SeqList
{
	int* data;
	int size;
	int capacity;
}SL;


// 顺序表的初始化
void SeqListInit(SL* ps);

// 顺序表的遍历
void SeqListPrint(SL* ps);

// 释放空间
void SeqDestroy(SL* ps);

// 缩容
void SeqListReduce(SL* ps, int new_size);

// 扩容
void SeqListExpand(SL* ps);

// 尾插元素
void SeqListPushBack(SL* ps, int x);

// 尾删元素
void SeqListPopBack(SL* ps);

// 头插元素
void SeqListPushFront(SL* ps, int x);

// 头删元素
void SeqListPopFront(SL* ps);

// 按下标查找元素
void SeqAtIndex(SL* ps, int x);

// 按值查找元素
void SeqAtValue(SL* ps, int x);

// 按值修改元素
void SeqModifyAtValue(SL* ps, int oldx, int newx);

// 按下标修改元素
void SeqModifyAtIndex(SL* ps, int oldx, int newVal);

// 随机插入元素
void SeqListPushPos(SL* ps, int pos, int value);

// 随机删除元素
void SeqListPopPos(SL* ps, int pos);

// 清空顺序表
void SeqListClear(SL* ps);

SeqList.c

#include "SeqList.h"


// 顺序表的初始化
void SeqListInit(SL* ps)
{
	ps->data = NULL;
	ps->size = ps->capacity = 0;
}

// 顺序表的遍历
void SeqListPrint(SL* ps)
{
	for (int i = 0; i < ps->size; ++i)
	{
		printf("%d ", ps->data[i]);
	}
	putchar('\n');
}

// 扩容
void SeqListExpand(SL* ps)
{
	// 此时有两种情况，一是初始化后ps->size == ps->capacity，二是经过多种对元素的插入导致ps->size == ps->capacity
	if(ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		int* temp = (int*)realloc(ps->data, newCapacity * sizeof(int));
		if(NULL == temp)
		{
			printf("realloc fail!\n");
			exit(-1);
		}

		ps->data = temp;
		ps->capacity = newCapacity;

		printf("扩容成功，容量为：%d\n", ps->capacity);
	}
}


// 缩容
void SeqListReduce(SL* ps, int new_size)
{
	ps->data = (int*)realloc(ps->data, new_size * sizeof(int));
	ps->capacity = new_size;
	printf("缩容成功! 容量为%d\n", ps->capacity);
}

// 尾插元素
void SeqListPushBack(SL* ps, int x)
{
	SeqListExpand(ps);
	ps->data[ps->size] = x;
	++ps->size;
}

// 尾删元素
void SeqListPopBack(SL* ps)
{
	if(ps->size)
	{
		--ps->size;
		if(ps->size * 5 < ps->capacity)
			SeqListReduce(ps, ps->size);
	}
	else
		printf("删除失败！\n");
}

// 头插元素
void SeqListPushFront(SL* ps, int x)
{
	SeqListExpand(ps);
	for (int i = ps->size - 1; i >= 0; --i)
	{
		ps->data[i+1] = ps->data[i];
	}
	ps->data[0] = x;
	++ps->size;
}

// 头删元素
void SeqListPopFront(SL* ps)
{
	if(ps->size)
	{
		for (int i = 1; i < ps->size; ++i)
		{
			ps->data[i-1] = ps->data[i];
		}
		--ps->size;
	}
	else
		printf("删除失败！\n");
}

// 按下标查找元素
void SeqAtIndex(SL* ps, int x)
{
	if(x >= ps->size || x < 0)
		printf("无效下标\n");
	else
	{
		for (int i = 0; i < ps->size; ++i)
		{
			if(ps->data[i] == ps->data[x])
				printf("找到了，下标为%d的值是%d\n", x, ps->data[i]);
		}
	}
}

// 按值查找元素
void SeqAtValue(SL* ps, int x)
{
	for (int i = 0; i < ps->size; ++i)
	{
		if(ps->data[i] == x)
		{
			printf("找到了%d\n", x);
			return;
		}
	}

	printf("没找到！\n");
}

// 按值修改元素
void SeqModifyAtValue(SL* ps, int oldx, int newx)
{
	for (int i = 0; i < ps->size; ++i)
	{
		if(ps->data[i] == oldx)
		{
			ps->data[i] = newx;
			return;
		}
	}

	printf("没有这个元素！\n");

}

// 按下标修改元素
void SeqModifyAtIndex(SL* ps, int oldx, int newVal)
{
	if(oldx >= ps->size || oldx < 0)
		printf("无效下标！\n");
	ps->data[oldx] = newVal;	
}

// 随机插入元素
void SeqListPushPos(SL* ps, int pos, int value)
{
	// 判断合法下标
	if(pos >= ps->size || pos < 0)
	{
		printf("无效下标！\n");
		return;
	}

	SeqListExpand(ps);
	for (int i = ps->size - 1; i >= pos; --i)
	{
		ps->data[i+1] = ps->data[i];
	}
	ps->data[pos] = value;
	++ps->size;
}

// 随机删除元素
void SeqListPopPos(SL* ps, int pos)
{

	// 判断合法下标
	if(pos >= ps->size || pos < 0)
	{
		printf("无效下标！\n");
		return;
	}

	if(ps->size)
	{
		for (int i = pos+1; i < ps->size; ++i)
		{
			ps->data[i-1] = ps->data[i];
		}
		--ps->size;
	}

}

// 清空顺序表
void SeqListClear(SL* ps)
{
	ps->size = 0;
}

// 释放空间
void SeqDestroy(SL* ps)
{
	free(ps->data);
	ps->data = NULL;
}

main.c

#include "SeqList.h"


void SeqListTest()
{
	SL s;
	// 初始化顺序表
	SeqListInit(&s);

	for (int i = 0; i < 100; ++i)
	{
		SeqListPushBack(&s, i);
	}

	for (int i = 0; i < 100; ++i)
	{
		SeqListPopBack(&s);
	}

	// // 尾插元素
	// SeqListPushBack(&s, 1);
	// SeqListPushBack(&s, 2);
	// SeqListPushBack(&s, 3);
	// SeqListPushBack(&s, 4);
	// SeqListPushBack(&s, 5);
	// SeqListPushBack(&s, 6);
	// SeqListPushBack(&s, 7);
	
	// // 顺序表的遍历
	// SeqListPrint(&s);

	// // 尾删元素
	// SeqListPopBack(&s);
	// SeqListPopBack(&s);

	// // 顺序表的遍历
	// SeqListPrint(&s);

	// // 头插元素
	// SeqListPushFront(&s, 0);

	// // 顺序表的遍历
	// SeqListPrint(&s);

	// // 头删元素
	// SeqListPopFront(&s);

	// // 顺序表的遍历
	// SeqListPrint(&s);

	// // 按下标查找元素
	// SeqAtIndex(&s, 2);

	// // 按值查找元素
	// SeqAtValue(&s, 1);

	// // 按值修改元素
	// SeqModifyAtValue(&s, 1, 4);

	// // 顺序表的遍历
	// SeqListPrint(&s);

	// // 按下标修改元素
	// SeqModifyAtIndex(&s, 0, 5);
	
	// // 顺序表的遍历
	// SeqListPrint(&s);

	// // 随机插入元素
	// SeqListPushPos(&s, 2, 8);

	// // 顺序表的遍历
	// SeqListPrint(&s);

	// // 随机删除元素
	// SeqListPopPos(&s, 0);

	// // 顺序表的遍历
	// SeqListPrint(&s);
}


int main(void)
{

	SeqListTest();

	return 0;
}