顺序表Plus版本

1.介绍

在上一篇顺序表的基础上添加了中间插入等功能，并且实现了简单的复用以介绍系统资源，并写了一个简单的菜单。(7来打印表中数据)

2.顺序表优缺点

2.1 顺序表的缺点

1. 头部和中部插入删除的效率不行 时间复杂度为O（N）
2. 空间不够了，扩容有一定的消耗（尤其是异地扩容）
3. 扩容逻辑，可能还存在空间，利用率不高

2.2?顺序表的优点

1. 尾插尾删足够快
2. 下标可以随机访问和修改

下一篇博客我们就会引入链表，大家记得关注哦

链表优点：按需申请释放

3.代码

3.1 SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "SeqList.h"
#include <string.h>
#include <stdlib.h>

void SLInit(SL* ps)		//顺序表初始化
{
	assert(ps);
	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4); //创建四个int大小的空间
	if (ps->a == NULL)		//检查错误
	{
		perror("malloc failed");
		exit(-1);
	}
	ps->size = 0;
	ps->capacity = 4;
}

void SLCheckCapacity(SL* ps)
{
	assert(ps);
	if ((ps->size) == ps->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType)));
		//创建一个临时变量，大小扩充到原来的两倍
		if (tmp == NULL)
		{
			perror("malloc failed");
			exit(-1);
		}
		ps->a = tmp;		//原表赋值到新的地址
		ps->capacity *= 2;	//大小扩充到原来的两倍
	}
}

void SLPushBack(SL* ps, SLDataType x)	//尾部插入数据
{
	assert(ps);
	//SLCheckCapacity(ps);
	//ps->a[ps->size] = x;	//原表赋值
	//ps->size++;				//赋值后有效数据+1
	//优化改进利用插入函数
	SLInsert(ps, ps->size, x);

}

void SLPopBack(SL* ps)		//尾部删除数据
{
	assert(ps);
	//温柔的检查
	//if (ps->size == 0)
	//{
	//	;
	//}
	//else
	//暴力检查（直接报错）
	//assert(ps->size > 0);
	//ps->size--;
	//复用
	SLErase(ps, ps->size-1);
}

void SLPushFront(SL* ps, SLDataType x) //头插
{
	assert(ps);
	//SLCheckCapacity(ps);
	//int end = ps->size - 1;	//从后往前挪动数据
	//for (int i = end; i >= 0; i--)
	//{
	//	ps->a[i + 1] = ps->a[i];
	//}
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	//ps->a[0] = x;     
	SLInsert(ps,0, x);
}

void SLPopFront(SL* ps) //头删
{
	assert(ps);
	//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);
	SLCheckCapacity(ps);

	int end = ps->size - 1;
	while (end>=pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	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;
}

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

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

void SLDestroy(SL* ps)		//释放表
{
	assert(ps);
	free(ps->a);		//释放空间
	ps->a = NULL;		//指针置零
	ps->size=ps->capacity = 0;
}

void SLPrint(SL* ps)		//打印表
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);			//打印表
	}
	printf("\n");
}
 
void TestSeqList1()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);

	SLPrint(&sl);  //增加五个数后打印

	SLPopBack(&sl);

	//删除一个后打印
	SLPrint(&sl);

	SLPopBack(&sl);
	SLPopBack(&sl);
	//插入数据

	SLInsert(&sl, 1, 89);
	//删除多个后打印查看报错再打印
	SLPrint(&sl);
	SLDestroy(&sl);
}

void TestSeqList2()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	printf("尾插打印");
	SLPrint(&sl);
	printf("\n");

	SLPushFront(&sl, 10);
	SLPushFront(&sl, 20);
	SLPushFront(&sl, 30);
	SLPushFront(&sl, 40);
	SLPushFront(&sl, 50);
	printf("头插打印：");
	SLPrint(&sl);
	printf("\n");
	SLPopFront(&sl);
	SLPopFront(&sl);
	//插入数据
	printf("中间插入打印：");
	SLInsert(&sl, 1, 89);
	SLPrint(&sl);
	printf("\n");
	//查找数据,在x前面插入一个值
	int x;
	scanf("%d", &x);
	int pos = SLFind(&sl, x);
	if (pos != -1)
	{
		SLInsert(&sl, pos, x * 10);
	}
	SLPrint(&sl);

	SLDestroy(&sl);
}

void TestSeqList3()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	printf("尾插打印");
	SLPrint(&sl);
	printf("\n");

	SLPushFront(&sl, 10);
	SLPushFront(&sl, 20);
	SLPushFront(&sl, 30);
	SLPushFront(&sl, 40);
	SLPushFront(&sl, 50);

	printf("头插打印：");
	SLPrint(&sl);
	printf("\n");

	SLPopFront(&sl);
	SLPopFront(&sl);
	//插入数据
	printf("中间插入打印：");
	SLInsert(&sl, 1, 89);
	SLPrint(&sl);
	printf("\n");

	//删除第五个值
	SLErase(&sl, 2);
	SLPrint(&sl);

	SLDestroy(&sl);
}

void menu()
{
	printf("***********************************\n");
	printf("1、尾插 2、头插\n");
	printf("3、头插 2、尾删\n");
	printf("-1、退出\n");
	printf("***********************************\n");
}

int main()
{
	SL sl;
	SLInit(&sl);
	int option = 0;
	do
	{
		menu();
		scanf("%d", &option);

		if (option == 1)
		{
			printf("输入要插入值的个数，并输入要插入的值\n");
			int n = 0;
			scanf("%d", &n);

			int x = 0;
			for (int i=0;i<n;i++)
			{
				scanf("%d", &x);
				SLPushBack(&sl, x);
			}
		}
		else if (option == 7)
		{
			SLPrint(&sl);
		}
	} while (option!=-1);
	menu();



	return 0;


}

1.2 SeqList.h

#pragma once
#define N 7
#include <stdio.h>
#include < assert.h >
typedef int SLDataType;

//typedef struct SeqList
//{
//	SLDataType a[N];
//	int size;	//存储有效数据个数
//	int capacity;	//容量的大小
//}SL;




typedef struct SeqList
{
	SLDataType* a;
	int size;	//存储有效数据个数
	int capacity;	//容量的大小
}SL;


void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLCheckCapacity(SL* ps);
void SLPrint(SL* ps);

//头插头删 尾插尾删
void SLPushBack(SL* ps,SLDataType x);	//尾插
void SLPopBack(SL* ps);	//尾删

void SLPushFront(SL* ps, SLDataType x); //头插
void SLPopFront(SL* ps);	//头删

//中间插入
void SLInsert(SL* ps, int pos, SLDataType x);
//查找数据,在x前面插入一个值
int SLFind(SL* ps, SLDataType x);
//清楚
void SLErase(SL* ps, int pos);
void SLModify(SL* ps, int pos, SLDataType);//修改