【数据结构】顺序表专题--＞动态顺序表实现详解！(附:全部码源)

发布于：2024-05-04 ⋅ 阅读:(29) ⋅ 点赞:(0)

🔥博客主页🔥：【 坊钰_CSDN博客 】

欢迎各位点赞👍评论✍收藏⭐

目录

1. 数据结构相关概念

1.1 什么是数据结构

1.1.1 什么是数据

1.1.2 什么是结构

1.2 数据结构概念

1.3 为什么需要数据结构

2. 顺序表

2.1 顺序表概念和结构

2.1.1 线性表

3. 顺序表分类

3.1  静态顺序表

3.2 动态顺序表

 4. 动态顺序表实现

4.1 分文件存放

4.2 建立结构体

4.3 初始化和销毁

4.3.1 初始化

4.3.2 销毁

4.4 判断空间是否扩容及打印

4.4.1 扩容

4.4.2 打印

4.5 顺序表的头插和尾插

4.5.1 尾插

4.5.2 头插

4.6 顺序表的头删和尾删

4.6.1 尾删

4.6.2 头删

4.7 指定位置插入和删除

4.7.1 指定位置插入

4.7.2 指定位置删除

5. 全部码源+运行结果

5.1 运行结果

5.2 全部码源

6. 小结

1. 数据结构相关概念

1.1 什么是数据结构

看下面两张图

 

 数据结构是由“数据”和“结构”两词组合⽽来

1.1.1 什么是数据

常⻅的数值1、2、3、4.....、教务系统⾥保存的⽤⼾信息（姓名、性别、年龄、学历等 等）、⽹⻚⾥⾁眼可以看到的信息（⽂字、图⽚、视频等等），这些都是数据

1.1.2 什么是结构

当我们想要使⽤⼤量使⽤同⼀类型的数据时，通过⼿动定义⼤量的独⽴的变量对于程序来说，可读性 ⾮常差，我们可以借助数组这样的数据结构将⼤量的数据组织在⼀起，结构也可以理解为组织数据的⽅式

想要找到草原上名叫“咩咩”的⽺很难，但是从⽺圈⾥找到1号⽺就很简单，⽺圈这样的结构有效将 ⽺群组织起来

1.2 数据结构概念

数据结构是计算机存储、组织数据的⽅式

总结 ：

  1. 能够存储数据（如顺序表、链表等结构）
  2. 存储的数据能够⽅便查找

1.3 为什么需要数据结构

通过数据结构，能够有效将数据组织和管理在⼀起。按照我们的⽅式任意对数据进⾏增删改查等操 作

最基础的数据结构：数组

有了数组，为什么还要学习其他的数据结构？

假定数组有10个空间，已经使⽤了5个，向数组中插⼊数据步骤：

求数组的⻓度，求数组的有效数据个数，向下标为数据有效个数的位置插⼊数据（注意：这⾥是 否要判断数组是否满了，满了还能继续插⼊吗）.....

假设数据量⾮常庞⼤，频繁的获取数组有效数据个数会影响程序执⾏效率 

总结：最基础的数据结构能够提供的操作已经不能完全满⾜复杂算法实现

2. 顺序表

2.1 顺序表概念和结构

2.1.1 线性表

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

3. 顺序表分类

  • 顺序表和数组的区别
  • 顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝

顺序表可分为静态顺序表和动态顺序表

3.1  静态顺序表

概念：使⽤定⻓数组存储元素

 静态顺序表缺点：空间给少了不够⽤，给多了造成空间浪费

3.2 动态顺序表

 4. 动态顺序表实现

以下位实现的全部函数声明；

//初始化和销毁 
void SLInit(SL* ps);
void SLDestroy(SL* ps);

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

//扩容 
void SLCheckCapacity(SL* ps);

//头部/尾部插入
void SLPushBack(SL* ps, SLDataType x);   //尾部
void SLPushFront(SL* ps, SLDataType x);  //头部

//头部/尾部删除
void SLPopBack(SL* ps);   //尾部
void SLPopFront(SL* ps);  //头部

//指定位置之前插⼊/删除数据 
void SLInsert(SL* ps, int pos, SLDataType x);  //指定位置插入
SLErase(SL* ps, int pos);                      //指定位置删除

4.1 分文件存放

要分为三个文件

SeqList.h    ----------->顺序表结构及函数声明
SeqList.c    ----------->顺序表的函数实现
test.c    -------------->代码测试

4.2 建立结构体

//定义类型
typedef int SLDataType;

//定义动态顺序表结构
typedef struct SeqList
{
	SLDataType* arr;   //指针
	int size;    //有效个数
	int capacity;   //空间容量
}SL;

4.3 初始化和销毁

4.3.1 初始化

//动态顺序表初始化
void SLInit(SL* ps);
//动态顺序表初始化的实现
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

4.3.2 销毁

//动态顺序表的销毁
void SLDestroy(SL* ps);
//动态顺序表销毁的实现
void SLDestroy(SL* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

4.4 判断空间是否扩容及打印

4.4.1 扩容

//判断容量空间是否足够
void SLCheckCapacity(SL* ps);
//判断容量空间是否足够
void SLCheckCapacity(SL* ps)
{
	if (ps->capacity == ps->size)
	{
		int newcapacity = (ps->capacity == 0 ? 4 : ps->capacity * 2);
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
		assert(tmp);
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}

4.4.2 打印

//打印顺序表
void SLPrint(SL s);

//打印顺序表实现
void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{

		printf("%d ", s.arr[i]);
	}
	printf("\n");
}

4.5 顺序表的头插和尾插

4.5.1 尾插

//动态顺序表插入（尾部）
void SLPushBack(SL* ps,SLDataType x);
//动态顺序表插入（尾部）实现
void SLPushBack(SL* ps,SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}

4.5.2 头插

//动态顺序表插入（头部）
void SLPushFront(SL* ps);
//动态顺序表插入（头部）实现
void SLPushFront(SL* ps,SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size;i>0; i--)
	{
		ps->arr[i] = ps->arr[i-1];
	}
	ps->arr[0] = x;
	ps->size++;
}

4.6 顺序表的头删和尾删

4.6.1 尾删

//动态顺序表删除（尾部）
void SLPopBack(SL* ps);
//动态顺序表删除（尾部）实现
void SLPopBack(SL* ps)
{
	ps->size--;
}

4.6.2 头删

//动态顺序表删除（头部）
void SLPopFront(SL* ps);
//动态顺序表删除（头部）实现
void SLPopFront(SL* ps)
{
	assert(ps);
	for (int i = 0;i<ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

4.7 指定位置插入和删除

4.7.1 指定位置插入

//指定位置插入(之前)
void SLInsret(SL* ps, int pos, SLDataType x);   //pos-->代表数组的下标
//指定位置插入（之前）实现
void SLInsret(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	for (int i = ps->size;i>pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

4.7.2 指定位置删除

//指定位置删除
void SLErase(SL* ps, int pos);
//指定位置删除实现
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos;i<ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

5. 全部码源+运行结果

5.1 运行结果

5.2 全部码源

<test.c>    测试文件

#include "SeqList.h"

SL sl;

//测试插入函数
void SLcheck01()
{
	//初始化
	SLInit(&sl);
	//尾部插入
	printf("尾部插入1 2 3 4 ：\n");
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(sl);
	//头部插入
	printf("头部插入4 ：\n");
	SLPushFront(&sl, 4);
	SLPrint(sl);
	//指定位置插入（之前）
	printf("在下标位2的地方插入6 ：\n");
	SLInsret(&sl, 2, 6);
	//打印
	SLPrint(sl);
}

//测试删除函数
void SLcheck02()
{
	//尾部删除
	printf("删除尾部 ：\n");
	SLPopBack(&sl);
	SLPrint(sl);
	//指定位置删除
	printf("删除下标位2的地方 ：\n");
	SLErase(&sl, 2);
	SLPrint(sl);
	//头部删除
	printf("删除头部 ：\n");
	SLPopFront(&sl);
	SLPrint(sl);
	//销毁
	SLDestroy(&sl);
}


int main()
{
    SLcheck01();
	SLcheck02();
	return 0;
}

<SeqList.h>    头文件声明

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

//定义类型
typedef int SLDataType;

//定义动态顺序表结构
typedef struct SeqList
{
	SLDataType* arr;   //指针
	int size;    //有效个数
	int capacity;   //空间容量
}SL;

//动态顺序表初始化
void SLInit(SL* ps);

//动态顺序表的销毁
void SLDestroy(SL* ps);

//判断容量空间是否足够
void SLCheckCapacity(SL* ps);

//动态顺序表插入（尾部）
void SLPushBack(SL* ps,SLDataType x);

//动态顺序表插入（头部）
void SLPushFront(SL* ps);

//指定位置插入(之前)
void SLInsret(SL* ps, int pos, SLDataType x);   //pos-->代表数组的下标

//打印顺序表
void SLPrint(SL s);

//动态顺序表删除（尾部）
void SLPopBack(SL* ps);

//动态顺序表删除（头部）
void SLPopFront(SL* ps);

//指定位置删除
void SLErase(SL* ps, int pos);

<SeqList.c>    文件实现

#include "SeqList.h"

//动态顺序表初始化的实现
void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

//动态顺序表销毁的实现
void SLDestroy(SL* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

//判断容量空间是否足够
void SLCheckCapacity(SL* ps)
{
	if (ps->capacity == ps->size)
	{
		int newcapacity = (ps->capacity == 0 ? 4 : ps->capacity * 2);
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
		assert(tmp);
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}

//动态顺序表插入（尾部）实现
void SLPushBack(SL* ps,SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;
}

//动态顺序表插入（头部）实现
void SLPushFront(SL* ps,SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size;i>0; i--)
	{
		ps->arr[i] = ps->arr[i-1];
	}
	ps->arr[0] = x;
	ps->size++;
}

//指定位置插入（之前）实现
void SLInsret(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	for (int i = ps->size;i>pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

//打印顺序表实现
void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{

		printf("%d ", s.arr[i]);
	}
	printf("\n");
}

//动态顺序表删除（尾部）实现
void SLPopBack(SL* ps)
{
	ps->size--;
}

//动态顺序表删除（头部）实现
void SLPopFront(SL* ps)
{
	assert(ps);
	for (int i = 0;i<ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

//指定位置删除实现
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos;i<ps->size-1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

6. 小结

以上就是关于顺序表的内容了，具体还需宝子们去实践，如果觉得该博客对你有用的话，希望一键三连，点个关注不迷路，谢谢支持！

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布