当前位置： 首页 > article >正文

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

article 2024/11/12 16:23:42

专栏说明：本专栏用于数据结构复习，文章中出现的代码由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;
}

在这里插入图片描述


http://www.kler.cn/a/387125.html

相关文章：

  • 线性表-数组描述补充 迭代器（C++）
  • Lodash的常用方法整理
  • 【人工智能】Transformers之Pipeline（二十三）：文档视觉问答（document-question-answering）
  • Android 开发指南：初学者入门
  • macos中安装和设置ninja
  • 最新网盘资源搜索系统，电视直播，Alist聚合播放
  • 使用Pytorch Geometric建立异构图HeteroData数据集
  • CycleGAN算法简述
  • 15分钟学 Go 第 40 天：使用ORM库
  • AnaTraf | 网络性能监控系统保障音视频质量的秘籍
  • 【Three.js基础学习】21.Realistic rendering
  • css:基础
  • go语言中如何使用 select 语句处理多通道
  • 基于STM32的LCD1602显示Proteus仿真设计(仿真+程序+设计报告+讲解视频）
  • 论软件可靠性设计及其应用
  • Linux: network: ip link M-DOWN的具体含义是什么？
  • 论文阅读--基于MLS点云语义分割和螺栓孔定位的盾构隧道错位检测方法
  • 如何在 Rust 中实现内存安全：与 C/C++ 的对比分析
  • 怎么解决码流多slice场景下的马赛克、绿屏问题？
  • 云原生安全解决方案NeuVector 5.X部署实践
  • 鸿蒙笔记--skills
  • NestJS 项目中如何使用 class-validator 进行数据验证
  • 从认识 VNode VDOM 到实现 mini-vue
  • 【数据结构与算法】第9课—数据结构之二叉树(链式结构)
  • es数据同步（仅供自己参考）
  • 机器学习中的分类：决策树、随机森林及其应用