线性表-顺序表的操作（增删查改，扩容，缩容）
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;
}