顺序表的实现

  • 开发
  • 5

这里写目录标题

1. 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

在这里插入图片描述

2. 顺序表

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

  1. 静态顺序表：使用定长数组存储元素。

在这里插入图片描述

  1. 动态顺序表：使用动态开辟的数组存储。

在这里插入图片描述

3. 接口实现

接口就是定义函数的实现。

//初始化
void SLInit(SL* psl);

//释放
void SLDestroy(SL* psl);

//打印
void SLPrint(SL* psl);

//尾插
void SLPushBack(SL* psl, SLDatatype x);

//头插
void SLPushFront(SL* psl, SLDatatype x);

//尾删
void SLPopBack(SL* psl);

//头删
void SLPopFront(SL* psl);

//中间插入
void SLInsert(SL* psl, int pos, SLDatatype x);

//中间删除
void SLErase(SL* psl, int pos);

//查找
//找到返回下标，没有找到返回-1
int SLFind(SL* psl, SLDatatype x);

//修改
void SLModify(SL* psl, int pos, SLDatatype x);

3.1 菜单

顺序表是不建议写菜单的，这也是我最后一次顺序表写菜单，后面的链表就不会写了，因为写菜单，不仅没有高级感，也妨碍我们调试代码。

void menu()
{
	printf("**********************\n");
	printf("*** 1. 尾插  2. 尾删***\n");
	printf("*** 3. 头插  4. 头删***\n");
	printf("***  5. 打印        ***\n");
	printf("***  6. 查找及修改  ***\n");
	printf("***   -1. 退出      ***\n");
	printf("**********************\n");
}

效果展示：
在这里插入图片描述

3.2 动态顺序表

方便动态扩容

//动态顺序表
typedef int SLDatatype;
typedef struct SeqList
{
	SLDatatype* a;
	int size;//存储有效数据的个数
	int capacity;//容量
}SL;

3.3 初始化

不初始化，存放的都是随机值

//动态初始化
void SLInit(SL* psl)
{
	assert(psl);
	psl->a = (SLDatatype*)malloc(sizeof(SLDatatype)*4);
	if (psl == NULL)
	{
		perror("SLInit");
		return;
	}
	psl->capacity = 4;//刚开始有4个空间
	psl->size = 0;
}

3.4 释放

动态开辟的内存空间，需要手动释放，防止出现野指针的情况。

//销毁
void SLDestroy(SL* psl)
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->capacity = 0;
	psl->size = 0;
}

3.5 打印

按照数组的方式进行打印

//打印
void SLPrint(SL* psl)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}

3.6 尾插

//尾插
void SLPushBack(SL* psl, SLDatatype x)
{
	assert(psl);
	//检查容量
	SLCheckCapacity(psl);

	/*psl->a[psl->size] = x;
	psl->size++;*/

	SLInsert(psl, psl->size, x);//复用
}

运行展示：
在这里插入图片描述

3.7 尾删

//尾删
void SLPopBack(SL* psl)
{
	assert(psl);
	//有效数据不能小于0
	//暴力检查
	assert(psl->size > 0);

	温柔检查
	//if (psl->size == 0)
	//	printf("数据为空，不能删除");


	/*psl->size--;*/

	SLErase(psl, psl->size - 1);//复用
}

运行展示：
在这里插入图片描述

3.8 头插

//头插
void SLPushFront(SL* psl, SLDatatype x)
{
	assert(psl);
	//SLCheckCapacity(psl);

	//挪动数据
	/*int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}

	psl->a[0] = x;
	psl->size++;*/

	SLInsert(psl, 0, x);//复用
}

运行展示：
在这里插入图片描述

3.9 头删

//头删
void SLPopFront(SL* psl)
{
	assert(psl);
	//暴力检查
	assert(psl->size > 0);
	/*int start = 0;
	while (start < psl->size - 1)
	{
		psl->a[start] = psl->a[start + 1];
		start++;
	}*/

	/*int start = 1;
	while (start < psl->size)
	{
		psl->a[start - 1] = psl->a[start];
		start++;
	}

	psl->size--;*/
	SLErase(psl, 0);//复用
}

运行展示：
在这里插入图片描述

3.10 中间插入

随机位置插入，想插哪都可以，先找到pos的位置

//中间插入
void SLInsert(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);
	//检查容量
	SLCheckCapacity(psl);

	int end = psl->size - 1;
	while (end >= pos)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[pos] = x;
	psl->size++;
}

3.11 中间删除

//中间删除
void SLErase(SL* psl, int pos)
{
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);
	int start = pos;
	while (start < psl->size - 1)
	{
		psl->a[start] = psl->a[start + 1];
		start++;
	}

	psl->size--;
}

3.12 查找

查找数据，找到就返回i，没找到就返回-1

//查找
int SLFind(SL* psl, SLDatatype x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

3.13 修改

前提是得先找到你想要进行修改的数据

//修改
void SLModify(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);

	psl->a[pos] = x;
}

运行展示：
在这里插入图片描述

3.14 扩容

测试容量是否满，满了就增容，以2倍增容

//扩容
void SLCheckCapacity(SL* psl)
{
	if (psl->size == psl->capacity)
	{
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) *psl->capacity* 2);
		if (tmp == NULL)
		{
			perror("SLCheckCapacity");
			return;
		}

		psl->a = tmp;
		psl->capacity *= 2;
	}
	
}

其中头插，头删，尾插，尾删用了中间插入，中间删除，复用实现，如果不用复用，把注释删除，再把复用的代码删除即可运行。

4. test.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "seqList.h"

void menu()
{
	printf("**********************\n");
	printf("*** 1. 尾插  2. 尾删***\n");
	printf("*** 3. 头插  4. 头删***\n");
	printf("***  5. 打印        ***\n");
	printf("***  6. 查找及修改  ***\n");
	printf("***   -1. 退出      ***\n");
	printf("**********************\n");
}

int main()
{
	int input = 0;
	SL s;
	SLInit(&s);
	while (input != -1)
	{
		menu();
		printf("请输入你的操作:>");
		scanf("%d", &input);
		if (input == 1)
		{
			/*printf("请输入要尾插的数据，以-1结束：");
			int x = 0;
			scanf("%d", &x);
			while (x != -1)
			{
				SLPushBack(&s, x);
				scanf("%d", &x);
			}*/
			int n = 0;
			printf("请输入要尾插的数据的个数，再依次输入要插入的数据：");
			scanf("%d", &n);
			int x = 0;
			while (n > 0)
			{
				scanf("%d", &x);
				SLPushBack(&s, x);
				n--;
			}
			
			
		}
		else if (input == 2)
		{
			int n = 0;
			printf("请输入要尾删的数据：");
			scanf("%d", &n);
			SLPopBack(&s);
		}
		else if (input == 3)
		{
			int n = 0;
			printf("请输入要头插的数据的个数，再依次输入要插入的数据：");
			scanf("%d", &n);
			int x = 0;
			while (n > 0)
			{
				scanf("%d", &x);
				SLPushFront(&s, x);
				n--;
			}
		}
		else if (input == 4)
		{
			int n = 0;
			printf("请输入要头删的数据：");
			scanf("%d", &n);
			SLPopFront(&s);
		}
		
	
		else if (input == 5)
		{
			SLPrint(&s);
		}

		else if (input == 6)
		{
			int n = 0;
			printf("请输入要查找的数据：");
			scanf("%d", &n);
			int pos = SLFind(&s,n);
			if (pos != -1)
			{
				int a = 0;
				printf("请选择修改的数据: ");
				scanf("%d", &a);
				SLModify(&s, pos, a);
			}
		}

		else if (input == -1)
		{
			break;
		}
		else
		{
			printf("输入错误，重新输入\n");
		}
	}
	SLDestroy(&s);
	return 0;
}

5. seqLish.h文件

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//静态的顺序表

//#define N 10
//typedef int SLDatatype;
//struct SeqList
//{
//	SLDatatype a[N];
//	int size;
//};

//动态顺序表
typedef int SLDatatype;
typedef struct SeqList
{
	SLDatatype* a;
	int size;//存储有效数据的个数
	int capacity;//容量
}SL;

//初始化
void SLInit(SL* psl);

//释放
void SLDestroy(SL* psl);

//打印
void SLPrint(SL* psl);

//尾插
void SLPushBack(SL* psl, SLDatatype x);

//头插
void SLPushFront(SL* psl, SLDatatype x);

//尾删
void SLPopBack(SL* psl);

//头删
void SLPopFront(SL* psl);

//中间插入
void SLInsert(SL* psl, int pos, SLDatatype x);

//中间删除
void SLErase(SL* psl, int pos);

//查找
//找到返回下标，没有找到返回-1
int SLFind(SL* psl, SLDatatype x);

//修改
void SLModify(SL* psl, int pos, SLDatatype x);

6. seqLish.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "seqList.h"

//静态初始化
//void SLInit(SL* psl)
//{
//	psl->a = NULL;
//	psl->size = 0;
//	psl->capacity = 0;
//}

//动态初始化
void SLInit(SL* psl)
{
	assert(psl);
	psl->a = (SLDatatype*)malloc(sizeof(SLDatatype)*4);
	if (psl == NULL)
	{
		perror("SLInit");
		return;
	}
	psl->capacity = 4;//刚开始有4个空间
	psl->size = 0;
}

//销毁
void SLDestroy(SL* psl)
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->capacity = 0;
	psl->size = 0;
}

//打印
void SLPrint(SL* psl)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}

//扩容
void SLCheckCapacity(SL* psl)
{
	if (psl->size == psl->capacity)
	{
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) *psl->capacity* 2);
		if (tmp == NULL)
		{
			perror("SLCheckCapacity");
			return;
		}

		psl->a = tmp;
		psl->capacity *= 2;
	}
	
}

//尾插
void SLPushBack(SL* psl, SLDatatype x)
{
	assert(psl);
	//检查容量
	SLCheckCapacity(psl);

	/*psl->a[psl->size] = x;
	psl->size++;*/

	SLInsert(psl, psl->size, x);
}

//头插
void SLPushFront(SL* psl, SLDatatype x)
{
	assert(psl);
	//SLCheckCapacity(psl);

	//挪动数据
	/*int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}

	psl->a[0] = x;
	psl->size++;*/

	SLInsert(psl, 0, x);
}

//尾删
void SLPopBack(SL* psl)
{
	assert(psl);
	//有效数据不能小于0
	//暴力检查
	assert(psl->size > 0);

	温柔检查
	//if (psl->size == 0)
	//	printf("数据为空，不能删除");


	/*psl->size--;*/

	SLErase(psl, psl->size - 1);
}

//头删
void SLPopFront(SL* psl)
{
	assert(psl);
	//暴力检查
	assert(psl->size > 0);
	/*int start = 0;
	while (start < psl->size - 1)
	{
		psl->a[start] = psl->a[start + 1];
		start++;
	}*/

	/*int start = 1;
	while (start < psl->size)
	{
		psl->a[start - 1] = psl->a[start];
		start++;
	}

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

//中间插入
void SLInsert(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);
	//检查容量
	SLCheckCapacity(psl);

	int end = psl->size - 1;
	while (end >= pos)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[pos] = x;
	psl->size++;
}

//中间删除
void SLErase(SL* psl, int pos)
{
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);
	int start = pos;
	while (start < psl->size - 1)
	{
		psl->a[start] = psl->a[start + 1];
		start++;
	}

	psl->size--;
}

//查找
int SLFind(SL* psl, SLDatatype x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

//修改
void SLModify(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);

	psl->a[pos] = x;
}

8. 视频演示

顺序表的实现完整过程

阅读全部

相关推荐

  1. 顺序表的实现

    2024-06-07 09:50:06       15 阅读

  3. 顺序表的动态实现

    2024-06-07 09:50:06       11 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-06-07 09:50:06       16 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-06-07 09:50:06       16 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-06-07 09:50:06       15 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-06-07 09:50:06       18 阅读

热门阅读

  3. C++ STL std::vector的实现机制【面试】

    2024-06-07 09:50:06       7 阅读

  4. python使用appium截图手机屏幕图片

    2024-06-07 09:50:06       7 阅读

  10. 【CentOS】手动编译安装make、cmake、gcc、git

    2024-06-07 09:50:06       7 阅读

  11. centos如何压缩zip

    2024-06-07 09:50:06       8 阅读

  12. 【设计模式】责任链模式（行为型）⭐⭐

    2024-06-07 09:50:06       9 阅读

  13. 腾讯云的身份证核验，找不到这个类

    2024-06-07 09:50:06       8 阅读

  17. 适用于STM32的U8G2回调函数例程

    2024-06-07 09:50:06       9 阅读

  18. 介绍单例模式

    2024-06-07 09:50:06       8 阅读

  25. Jitsi meet 退出房间后，用户还在房间内

    2024-06-07 09:50:06       9 阅读

  26. lua vm 四: 表达式

    2024-06-07 09:50:06       7 阅读