数据结构：顺序表（动态顺序表）

专栏说明：本专栏用于数据结构复习，文章中出现的代码由C语言实现，在专栏中会涉及到部分OJ题目，如对你学习有所帮助，可以点赞鼓励一下博主喔💓

博客主页：Duck Bro 博客主页
系列专栏：数据结构专栏
关注博主，后期持续更新系列文章
如果有错误感谢请大家批评指出，及时修改
感谢大家点赞👍收藏⭐评论✍

数据结构：顺序表（动态顺序表）

数据结构：顺序表（动态顺序表）
- 1. 概念与结构
- - 1.1 概念
  - 1.2 结构
- 2. 接口实现
- - 2.1 动态顺序表结构
  - 2.2 顺序表初始化
  - 2.3 顺序表销毁
  - 2.4 检查空间、扩容
  - 2.5 顺序表尾插
  - 2.6 顺序表尾删
  - 2.7 顺序表头插
  - 2.8 顺序表头删
  - 2.9 顺序表查找
  - 2.10 在pos位置插入x
  - 2.11 删除pos位置值
  - 2.12 修改pos位置值
  - 2.13 打印顺序表
- 3. 详细代码页
- - 3.1 SeqList.h
  - 3.2 SeqList.c
  - 3.3 main.c

1. 概念与结构

1.1 概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
储。在数组上完成数据的增删查改。

1.2 结构

静态顺序表：使用定长数组存储元素。
在这里插入图片描述

#define N 7
typedef int DataType;
typedef struct SeqList
{
	DataType a[N];
	int size;
	int capacity;
}SL;

动态顺序表：使用动态开辟的数组存储。
在这里插入图片描述

typedef int DataType;
typedef struct SeqList
{
	DataType* a;
	int size;
	int capacity;
}SL;

2. 接口实现

2.1 动态顺序表结构

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

2.2 顺序表初始化

void SLInit(SL* pc)
{
	//断言
	assert(pc);
	//pc->a = NULL;
	pc->a = (DataType*)malloc(sizeof(DataType) * 4);
	//判断是否为空
	if (pc->a == NULL)
	{
		//报错提示
		perror("SLInit faild");
		//退出程序
		exit(-1);
	}
	//顺序表内的数据个数
	pc->size = 0;
	//顺序表内的容量
	pc->capacity = 4;
}

2.3 顺序表销毁

void SLDestroy(SL* pc)
{
	//断言
	assert(pc);
	//释放内存
	free(pc->a);
	//将指针置为空
	pc->a = NULL;
	//设置数据个数和容量为0个
	pc->size = 0;
	pc->capacity = 0;
}

2.4 检查空间、扩容

void SLCheckCapacity(SL* pc)
{
	//断言
	assert(pc);
	//如果size==capacity,则进行二倍扩容
	if (pc->size == pc->capacity)
	{
		DataType* temp = (DataType*)realloc(pc->a, pc->capacity * sizeof(DataType) * 2);
		//进行判断是否开辟成功
		if (temp == NULL)
		{
			perror("SLCheckCapacity faild");
			exit(-1);
		}
		pc->a = temp;
		pc->capacity *= 2;
	}
}

2.5 顺序表尾插

void SLPushBack(SL* pc, DataType x)
{
	assert(pc);

	/*assert(pc);
	SLCheckCapacity(pc);
	pc->a[pc->size] = x;
	pc->size++;*/
	SLInsert(pc, pc->size, x);
}

2.6 顺序表尾删

void SLPopBack(SL* pc)
{
	assert(pc);
	/*assert(pc);
	assert(pc->size);
	pc->size--;*/
	SLErase(pc, pc->size - 1);
}

2.7 顺序表头插

void SLPushFront(SL* pc, DataType x)
{
	assert(pc);

	断言
	//assert(pc);
	检查空间是否足够
	//SLCheckCapacity(pc);
	end为顺序表中最后一个数据的下标
	//int end = pc->size - 1;
	将所有数据进行后移
	//while (end >= 0)
	//{
	//	pc->a[end + 1] = pc->a[end];
	//	--end;

	//}
	//pc->a[0] = x;
	//pc->size++;
	SLInsert(pc, 0, x);

}

2.8 顺序表头删

void SLPopFront(SL* pc)
{
	assert(pc);

	/*assert(pc->size > 0);
	int begin = 1;
	while (begin < pc->size)
	{
		pc->a[begin - 1] = pc->a[begin];
		begin++;

	}
	pc->size--;*/
	SLErase(pc, 0);
}

2.9 顺序表查找

int SLFind(SL* pc, DataType x)
{

	assert(pc);
	for (int i = 0; i < pc->size; i++)
	{
		if (x == pc->a[i])
		{
			return i;
		}
	}
	return -1;
}

2.10 在pos位置插入x

void SLInsert(SL* pc, int pos, DataType x)
{
	assert(pos >= 0 && pos <= pc->size);
	SLCheckCapacity(pc);
	int end = pc->size - 1;
	while (end >= pos)
	{
		pc->a[end + 1] = pc->a[end];
		end--;
	}
	pc->a[pos] = x;
	pc->size++;
}

2.11 删除pos位置值

void SLErase(SL* pc, int pos)
{
	assert(pc);
	assert(pos>=0&&pos<pc->size);

	int begin = pos + 1;
	while (begin < pc->size)
	{
		pc->a[begin-1] = pc->a[begin];
		begin++;
	}
	pc->size--;
}

2.12 修改pos位置值

void SLModify(SL* pc, int pos, DataType x)
{
	assert(pc);

	assert(pos <= 0 && pos < pc->size);
	pc->a[pos] = x;

}

2.13 打印顺序表

void SLPrintf(SL* pc)
{
	//断言
	assert(pc);
	//遍历
	int i = 0;
	for (i = 0; i < pc->size; i++)
	{
		printf("%d ", pc->a[i]);
	}
	printf("\n");
}

3. 详细代码页

3.1 SeqList.h

#define  _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int DataType;
typedef struct SeqList
{
	DataType* a;
	int size;
	int capacity;
}SL;

//顺序表初始化
void SLInit(SL* pc);
//顺序表销毁
void SLDestroy(SL* pc);
//容量检查,并进行扩容
void SLCheckCapacity(SL* pc);
//打印顺序表中的数据 遍历顺序表
void SLPrintf(SL* pc);

//顺序表头插
void SLPushFront(SL* pc, DataType x);
//顺序表尾删
void SLPopBack(SL* pc);
//顺序表尾插
void SLPushBack(SL* pc, DataType x);
//顺序表头删
void SLPopFront(SL* pc);

//查找位置
int SLFind(SL* pc ,DataType x);
//顺序表pos位置前插入X
void SLInsert(SL* pc, int pos,DataType x);
//顺序表删除pos位置值
void SLErase(SL* pc,int pos);
//修改pos位置值
void SLModify(SL* pc, int pos,DataType x);

3.2 SeqList.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"


void SLInit(SL* pc)
{
	//断言
	assert(pc);
	//pc->a = NULL;
	pc->a = (DataType*)malloc(sizeof(DataType) * 4);
	//判断是否为空
	if (pc->a == NULL)
	{
		//报错提示
		perror("SLInit faild");
		//退出程序
		exit(-1);
	}
	//顺序表内的数据个数
	pc->size = 0;
	//顺序表内的容量
	pc->capacity = 4;
}

void SLDestroy(SL* pc)
{
	//断言
	assert(pc);
	//释放内存
	free(pc->a);
	//将指针置为空
	pc->a = NULL;
	//设置数据个数和容量为0个
	pc->size = 0;
	pc->capacity = 0;

}

void SLCheckCapacity(SL* pc)
{
	//断言
	assert(pc);
	//如果size==capacity,则进行二倍扩容
	if (pc->size == pc->capacity)
	{
		DataType* temp = (DataType*)realloc(pc->a, pc->capacity * sizeof(DataType) * 2);
		//进行判断是否开辟成功
		if (temp == NULL)
		{
			perror("SLCheckCapacity faild");
			exit(-1);
		}
		pc->a = temp;
		pc->capacity *= 2;

	}
}

void SLPrintf(SL* pc)
{
	//断言
	assert(pc);
	//遍历
	int i = 0;
	for (i = 0; i < pc->size; i++)
	{
		printf("%d ", pc->a[i]);
	}
	printf("\n");
}

void SLPushFront(SL* pc, DataType x)
{
	assert(pc);

	断言
	//assert(pc);
	检查空间是否足够
	//SLCheckCapacity(pc);
	end为顺序表中最后一个数据的下标
	//int end = pc->size - 1;
	将所有数据进行后移
	//while (end >= 0)
	//{
	//	pc->a[end + 1] = pc->a[end];
	//	--end;

	//}
	//pc->a[0] = x;
	//pc->size++;
	SLInsert(pc, 0, x);

}

void SLPopBack(SL* pc)
{
	assert(pc);
	/*assert(pc);
	assert(pc->size);
	pc->size--;*/
	SLErase(pc, pc->size - 1);
}

void SLPushBack(SL* pc, DataType x)
{
	assert(pc);

	/*assert(pc);
	SLCheckCapacity(pc);
	pc->a[pc->size] = x;
	pc->size++;*/
	SLInsert(pc, pc->size, x);
}

void SLPopFront(SL* pc)
{
	assert(pc);

	/*assert(pc->size > 0);
	int begin = 1;
	while (begin < pc->size)
	{
		pc->a[begin - 1] = pc->a[begin];
		begin++;

	}
	pc->size--;*/
	SLErase(pc, 0);
}

void SLInsert(SL* pc, int pos, DataType x)
{
	assert(pos >= 0 && pos <= pc->size);
	SLCheckCapacity(pc);
	int end = pc->size - 1;
	while (end >= pos)
	{
		pc->a[end + 1] = pc->a[end];
		end--;
	}
	pc->a[pos] = x;
	pc->size++;
}

void SLErase(SL* pc, int pos)
{
	assert(pc);
	assert(pos>=0&&pos<pc->size);

	int begin = pos + 1;
	while (begin < pc->size)
	{
		pc->a[begin-1] = pc->a[begin];
		begin++;
	}
	pc->size--;
}

int SLFind(SL* pc, DataType x)
{

	assert(pc);
	for (int i = 0; i < pc->size; i++)
	{
		if (x == pc->a[i])
		{
			return i;
		}
	}
	return -1;
}

void SLModify(SL* pc, int pos, DataType x)
{
	assert(pc);

	assert(pos <= 0 && pos < pc->size);
	pc->a[pos] = x;

}

3.3 main.c


#include "SeqList.h"
void test1()
{
	//测试创建顺序表初始化 销毁
	SL s;
	SLInit(&s);
	SLDestroy(&s);
}

void test2()
{
	//测试顺序表尾插插
	SL s1;
	SLInit(&s1);
	
	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	//SLPushFront(&s1, 4);
	//SLPushFront(&s1, 4);

	//SLPopBack(&s1);
	//SLPopBack(&s1);
	SLPopBack(&s1);
	SLPopBack(&s1);


	SLPushBack(&s1, 67);
	SLPushBack(&s1, 67);
	SLPushBack(&s1, 67);

	SLPrintf(&s1);
	SLDestroy(&s1);
}

void test3()
{
	//测试顺序表尾插插
	SL s1;
	SLInit(&s1);

	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	SLPrintf(&s1);

	//SLPushFront(&s1, 4);
	SLPushFront(&s1, 66);



	SLPrintf(&s1);
	SLDestroy(&s1);
}

void test4()
{
	//测试顺序表尾插插
	SL s1;
	SLInit(&s1);

	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	SLPushBack(&s1, 5);
	//SLInsert(&s1, 2, 7);
	int x = 0;
	scanf("%d", &x);
	int pos = SLFind(&s1, x);
	if (pos != -1)
	{
		SLInsert(&s1, pos, 50);
	}


	SLPrintf(&s1);
	SLDestroy(&s1);
}
void test5()
{
	//测试顺序表尾插插
	SL s1;
	SLInit(&s1);

	SLPushBack(&s1, 1);
	SLPushBack(&s1, 2);
	SLPushBack(&s1, 3);
	SLPushBack(&s1, 4);
	SLPushBack(&s1, 5);
	//SLInsert(&s1, 2, 7);
	SLPopBack(&s1);
	SLPopFront(&s1);


	SLPrintf(&s1);
	SLDestroy(&s1);
}
int main()
{
	//test1();
	//test2();
	//test3();
	//test4();
	test5();

	return 0;
}