数据结构——顺序表的实现

• • SeqList.h
  • SeqList.c
  • Test.c

#pragma once

#include 
#include 
#include 
#include 

#define MAX_SIZE 100
typedef int SQDataType;

//顺序表的静态存储
// 问题：给少了不够用，给多了用不完浪费，不能灵活控制
//typedef struct SeqList
//{
//	SLDataType arry[MAX_SIZE];//定长数组
//	int size;//有效数据的个数
//}SL;

//顺序表的动态存储
typedef struct SeqList
{
	SQDataType* a;//指向动态开辟的数组
	int size;//有效数据个数
	int capicity;//容量空间的大小
}SL;

//增删查改等接口函数

void SeqListInit(SL* ps);
void SeqListPrint(SL* ps);
void SeqListDestory(SL* ps);

//头插 尾插 头删 尾删

//尾插
void SeqListPushBack(SL* ps, SQDataType x);
//头插
void SeqListPushFront(SL* ps, SQDataType x);
//尾删
void SeqListPopBack(SL* ps);
//头删
void SeqListPopFront(SL* ps);
//指定位置插入
void SeqListInsert(SL* ps, int pos, SQDataType x);
//指定位置删除
void SeqListErase(SL* ps, int pos);
//查找每个数据，若找到，则返回该数据的下标，若没有找到，返回-1
int SeqListFind(SL* ps, SQDataType x);
//修改指定位置的数据
void SeqListModify(SL* ps, int pos, SQDataType x);

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

//静态顺序表
//void SeqListInit(SL* ps)
//{
//	memset(ps->a, 0, sizeof(SQDataType) * MAX_SIZE);
//	ps->size = 0;
//}
//void SeqListPushBack(SL* ps, SQDataType x)
//{
//	if (ps->size == MAX_SIZE)
//	{
//		printf("SeqList is fulln");
//		return;
//	}
//	ps->a[ps->size] = x;
//	ps->size++;
//}

//动态顺序表
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capicity = 0;
}
void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capicity = ps->size = 0;
}
void SeqListCheckCapicity(SL* ps)
{
	//满了就要扩容
	if (ps->size == ps->capicity)
	{
		int newcapicity = ps->capicity == 0 ? 4 : ps->capicity * 2;
		SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapicity * sizeof(SQDataType));
		if (tmp = NULL)
		{
			printf("realloc failn");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capicity = newcapicity;
		}
	}
}
void SeqListPushBack(SL* ps, SQDataType x)
{
	SeqListCheckCapicity(ps);
	ps->a[ps->size] = x;
	ps->size++;
	//SeqListInsert(ps, ps->size, x);
}
void SeqListPushFront(SL* ps, SQDataType x)
{
	SeqListCheckCapicity(ps);
	//1.初始条件
	//2.结束条件
	//3.迭代过程
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[0] = x;
	ps->size++;
	//SeqListInsert(ps,0,x);
}

void SeqListPopBcak(SL* ps)
{
	assert(ps->size > 0);
	ps->a[ps->size - 1] = 0;
	ps->size--;
	//SeqListErase(ps,ps->size-1);
}

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--;
	//SeqListErase(ps,0);
}

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

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--;
}

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

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

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

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

void menu()
{
	printf("1.尾插数据，		2.头插数据n");
	printf("3.尾删数据，		4.头删数据n");
	printf("5.打印数据，		-1.退出n");
	printf("请输入你要选择的操作选项：");
}
int main()
{
	SL s;
	SeqListInit(&s);
	int option = 0;
	int x = 0;
	while (option != -1)
	{
		menu();
		scanf("%d", &option);
		switch (option)
		{
		case 1:
			printf("请输入你要尾入插入的数据，以-1结束：");
			do
			{
				scanf("%d", &x);
				if (x != -1)
				{
					SeqListPushBack(&s, x);
				}
			} while (x != -1);
			SeqListPrint(&s);
			break;
		case 2:
			printf("请输入你要头入插入的数据，以-1结束：");
			do
			{
				scanf("%d", &x);
				if (x != -1)
				{
					SeqListPushFront(&s, x);
				}
			} while (x != -1);
			SeqListPrint(&s);
			break;
		case 3:
			printf("请输入你要从尾部删除几个数据：>");
			scanf("%d", &x);
			int i = 0;
			for (i = 0; i < x; i++)
			{
				SeqListPopBack(&s);
			}
			SeqListPrint(&s);
			break;
		case 4:
			printf("请输入你要从头部删除几个数据：>");
			scanf("%d", &x);
			int j = 0;
			for (j = 0; j < x; j++)
			{
				SeqListPopFront(&s);
			}
			SeqListPrint(&s);
			break;
		case 5:
			SeqListPrint(&s);
			break;
		default:
			break;
		}
	}
	SeqListDestory(&s);
	return 0;
}