首页 > 其他分享 >＜数据结构＞——顺序表

＜数据结构＞——顺序表

时间：2024-07-31 20:52:55浏览次数：16  
标签：ps arr 顺序 int SL 数据结构 size

1.什么是顺序表

顺序表是用一段物理地址连续的单元依次存储数据元素的线性结构，一般情况下采用数组来存储 顺序表的底层结构就是数组。实际上顺序表是对数组进行封装，成为一个结构体。顺序表有静态顺序表与动态顺序表之分。

1.1静态顺序表

//静态顺序表
typedef int SLDateType;//方便后续的更改数据类型
#define N 7
typedef struct SeqList
{
    SLDataType a[N];//定长数组
    int size;//有效数据个数
}SL;
0123456

878aa5133d4c4aef9cbb872d4a099ad7.png

静态顺序表的缺点：空间给小了不够用，给大了会造成空间浪费。这个时候当空间小时，需要自动扩容，但又不至于扩容太大而造成空间浪费的一个操作应该怎么进行呢？不用担心，那么这时候动态顺序表的出现，就可以解决这个难题了。

1.2动态顺序表

动态顺序表可以根据输入的数据，以及后续的增删除改操作从而判断是否需要增容，达到自动增容的效果，但又不至于因增容过多而造成空间浪费。所以在顺序表中一般使用动态顺序表，便于后期的维护。

typedef int SeqDatetype;//便于后期的更改维护
typedef struct Seqlist
{
	SeqDatetype* arr;//顺序表存放的类型
	int size;//顺序表的有效数据个数
	int capacity;//顺序表的容量
}SL;

2增容

2.1如何增容

增容一般是以2~3倍之前的空间大小来进行增容操作。虽然这样仍会存在空间浪费，但是相比定长一个巨大的空间还是显得更划算。而且一个一个增容的话会频繁使程序进行扩容操作，从而导致程序的运行效率低下。

97b637c13cba45c2811be68a2f035cec.png

2.2增容的两种情况

42bde5f438304297a28405ee6701ff20.png

3.一个动态顺序表的使用

3.1个文件的设计

3.1.2Seqlist.h

Seqlist.h文件中存放的是顺序表的核心内容以及对顺序表进行增删操作等一些主要函数的声明

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

typedef int SeqDatetype;//便于后期的更改维护
typedef struct Seqlist
{
	SeqDatetype* arr;//顺序表存放的类型
	int size;//顺序表的有效数据个数
	int capacity;//顺序表的容量
}SL;


void SeqInit(SL *ps);//初始化顺序表
void SeqDelete(SL *ps);//销毁顺序表
void SLPrint(SL* ps);//打印顺序表

void SLcheckcapacity(SL* ps);//检查顺序表容量是否充足，不充足则对容量capacity进行翻倍


void SLPushBack(SL* ps, SeqDatetype x);//尾插一个SeqDatetype数据
void SLPushFront(SL* ps, SeqDatetype x);//头插一个数据在顺序表中
void SLInsert(SL* ps, SeqDatetype x, int pos);//任意位置插入


void SLPopBack(SL* ps);//尾删
void SLPopFront(SL* ps);//头删
void SLErase(SL* ps, SeqDatetype x, int pos);//任意位置删除

3.1.2Seqlist.c

Seqlist.c文件中存放的是增删顺序表等函数的具体实现方法

#include "Seqlist.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

void SeqInit(SL* ps)//初始化顺序表
{
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
	
}


void SeqDelete(SL* ps)//销毁顺序表
{
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
	printf("销毁成功");
}


void SLcheckcapacity(SL* ps)//检查顺序表容量是否充足，不充足则对容量capacity进行翻倍
{
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//创建一个新变量，防止由于capacity是0而无法增容
		SeqDatetype* temp = (SeqDatetype*)realloc(ps->arr, newcapacity * sizeof(SeqDatetype));
		//realloc的第二个参数是要申请多少个字节的空间，不是多少个空间，注意单位
		if (temp == NULL)
		{
			perror("realloc申请空间失败");
			exit(1);
		}
		ps->arr = temp;
		ps->capacity = newcapacity;
	}

}


void SLPushBack(SL* ps, SeqDatetype x)//尾插一个数据在顺序表中
{
	assert(ps);//等价于assert(ps!=NULL),用于判断，当ps不等于NULL时可运行
	SLcheckcapacity(ps);//判断顺序表容量是否充足，否，则扩容
	ps->arr[ps->size] = x;
	ps->size++;
}



void SLPushFront(SL* ps, SeqDatetype 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 SLInsert(SL* ps, SeqDatetype x, int pos)//任意位置插入
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLcheckcapacity(ps);
	
	for (int i = ps->size; i >pos; i--)
	{
		ps->arr[i] = ps->arr[i-1];
	}
	ps->arr[pos] = x;
	ps->size++;
}


void SLErase(SL* ps, SeqDatetype x, int pos)//任意位置删除
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLcheckcapacity(ps);

	if (pos == ps->size - 1)
		ps->size--;

	else
	{
		for (int i = pos; i < ps->size - 1; i++)
		{
			ps->arr[i] = ps->arr[i + 1];
		}
		ps->size--;
	}
}


void SLPopBack(SL* ps)//尾删
{
	assert(ps);
	assert(ps->size);//判断顺序表是否为有效数据size是否为0，若为0，则不可以删除
	ps->size--;
}


void SLPopFront(SL* ps)//头删
{
	assert(ps);
	assert(ps->size);//判断顺序表是否为有效数据size是否为0，若为0，则不可以删除
	for (int i = 0; i < ps->size - 1; i++)
		ps->arr[i] = ps->arr[i + 1];
	ps->size--;
}


void SLPrint(SL* ps)//打印顺序表
{
	for (int i = 0; i < ps->size; i++)
		printf("%d ", ps->arr[i]);//这里可以优化一下，根据SeqDatetype来确定占位符的类型
	puts("");
}

3.2简要介绍顺序表以及各函数功能细分

3.2.1顺序表的介绍

typedef int SeqDatetype;//便于后期的更改维护
typedef struct Seqlist
{
	SeqDatetype* arr;//顺序表存放的类型
	int size;//顺序表的有效数据个数
	int capacity;//顺序表的容量
}SL;

3.2.1.1typedef的妙用

如果根据功能的需要，需要将顺序表中的int类型数据更改为char类型，类型更改势必会把后面的函数的一些数据更改。那么如果进行更改这一操作（int->char），必然会有更多地方需要修改，但是第一行代码就巧妙的运行用了typedef，使得后期的更改只需修改第一行代码中的int即可

3.2.1.2存放类型为指针类型

可以直接存放数据的类型，不需要思考有多少个数据，且传地址的方式可以直接对数组进行操作，而值传递则是拷贝一份原来数组数据再进行操作，浪费空间。

3.2.2初始化顺序表

直接将数组的地址初始化置为为NULL，并将顺序表的容量和有效数据都初始化为0

void SeqInit(SL* ps)//初始化顺序表
{
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
	
}

注意：此处不可使用值传递的方法，需要使用传地址的方法，否则会使顺序表的初始化出现错误

即：是错误的f11d1e9795be427fb1bda4ef5dbc2fc8.png

3.2.3销毁顺序表

每次使用完顺序表之后，需要释放空间（free），将数组地址置空，容量以及有效数据置为0，即完成销毁顺序表的操作

void SeqDelete(SL* ps)//销毁顺序表
{
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
	printf("销毁成功");
}

3.2.4检查顺序表的容量是否充足

检查顺序表的容量是否充足，若不充足，则根据扩容的规则，对顺序表进行二倍扩容操作

void SLcheckcapacity(SL* ps)//检查顺序表容量是否充足，不充足则对容量capacity进行翻倍
{
	if (ps->size == ps->capacity)//判断是否充足
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        //创建一个新变量，防止由于capacity是0而无法增容
		SeqDatetype* temp = (SeqDatetype*)realloc(ps->arr, newcapacity * sizeof(SeqDatetype));
		//realloc的第二个参数是要申请多少个字节的空间，不是多少个空间，注意单位
		if (temp == NULL)
		{
			perror("realloc申请空间失败");
			exit(1);
		}
		ps->arr = temp;
		ps->capacity = newcapacity;//扩容成功操作
	}

}

3.2.5头插、尾插、任意位置插入

由易至复杂来介绍一下SeqDatetype类型数据在顺序表中的插入


若原来的顺序表

SeqDatetype类型数据1234567
pos0123456

进行第一次头插操作，比如头插入在顺序表头插一个数据0：

SeqDatetype类型数据01234567
pos01234567

这时再进行一次尾插操作，比如在顺序表尾插入一个数据8

SeqDatetype类型数据012345678
pos012345678

若对原顺序表进行任意位置插入操作，需要确定插入位置pos，比如再pos=3这个位置插入10

SeqDatetype类型数据123104567
pos01234567

头插具体实现代码

void SLPushFront(SL* ps, SeqDatetype x)//头插一个数据在顺序表中
{
	assert(ps);//等价于assert(ps!=NULL),用于判断，当ps不等于NULL时可运行
	SLcheckcapacity(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;//将要插入的数据放在最后一个位置
	ps->size++;

}

尾插具体实现代码

void SLPushBack(SL* ps, SeqDatetype x)//尾插一个数据在顺序表中
{
	assert(ps);//等价于assert(ps!=NULL),用于判断，当ps不等于NULL时可运行
	SLcheckcapacity(ps);//判断顺序表容量是否充足，否，则扩容
	ps->arr[ps->size] = x;
	ps->size++;
}

任意位置（pos）插入具体实现代码

void SLInsert(SL* ps, SeqDatetype x, int pos)//任意位置插入
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);//使插入的位置不超过顺序表有效数据个数，使顺序表的数据连贯
	SLcheckcapacity(ps);
	
	for (int i = ps->size; i >pos; i--)
	{
		ps->arr[i] = ps->arr[i-1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

3.2.6头删、尾删、任意位置删除

有了3.2.5的基础应该容易理解接下来的头删、尾删、任意位置删除等操作

头删

void SLPopFront(SL* ps)//头删
{
	assert(ps);
	assert(ps->size);//判断顺序表是否为有效数据size是否为0，若为0，则不可以删除
	for (int i = 0; i < ps->size - 1; i++)
		ps->arr[i] = ps->arr[i + 1];
	ps->size--;
}

尾删

void SLPopBack(SL* ps)//尾删
{
	assert(ps);
	assert(ps->size);//判断顺序表是否为有效数据size是否为0，若为0，则不可以删除
	ps->size--;
}

任意位置删除

void SLErase(SL* ps, SeqDatetype x, int pos)//任意位置删除
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLcheckcapacity(ps);

	if (pos == ps->size - 1)
		ps->size--;

	else
	{
		for (int i = pos; i < ps->size - 1; i++)
		{
			ps->arr[i] = ps->arr[i + 1];
		}
		ps->size--;
	}
}

3.2.7打印顺序表

void SLPrint(SL* ps)//打印顺序表
{
	for (int i = 0; i < ps->size; i++)
		printf("%d ", ps->arr[i]);//这里可以优化一下，根据SeqDatetype来确定占位符的类型，本示例顺序表的类型为int，若为char类型的话，则占位符为%c
	puts("");
}

4.顺序表的用途

顺序表的用途很多，比如在结构体中增加一些内容就可以成为完成一个通讯录的项目实现，还可以在结构体数组中扩建，完成学生管理系统的一些核心设计，用途多多，看你要如何去使用

标签：ps,arr,顺序,int,SL,数据结构,size
From： https://blog.csdn.net/2302_80961600/article/details/140803955

相关文章

  • 【每日一题 | 数据结构】循环队列
    题目题型讲解核心：所有的循环队列的题，都使用“圆盘法”，即画图来解决。而不要死记公式！！循环队列即将队列空间想象为一个环形的空间，当front或rear位于线性表的最后一个元素时，再加1会回到第一个元素，如图所示：因此，基于这个特性，我们就可以用取模法来计算队列的最大长度等问题......
  • 达梦数据库的DM 数据守护（DM Data Watch）启动和关闭顺序
    达梦数据库的DM数据守护（DMDataWatch）启动和关闭顺序一数据守护关闭1退出监视器2关闭备机的守护进程[dmdba@test2arch]$DmWatcherServiceDMSVR02stopStoppingDmWatcherServiceDMSVR02:[OK]3关闭主机的守护进程[dmdba@test1~......
  • 【数据结构】排序算法（快速排序、归并排序、排序算法总结）
    当你清楚的知道自己想要什么，并且意愿非常强烈的时候，你总会有办法得到的。......
  • 【初阶数据结构】11.排序（2）
    文章目录2.3交换排序2.3.1冒泡排序2.3.2快速排序2.3.2.1hoare版本2.3.2.2挖坑法2.3.2.3lomuto前后指针2.3.2.4非递归版本2.4归并排序2.5测试代码：排序性能对比2.6非比较排序2.6.1计数排序3.排序算法复杂度及稳定性分析2.3交换排序交换排序基本思想：......
  • 编写一个函数，它接受一个 str/ 单词并按顺序输出这些字符的组合列表
    基本上是标题。输入示例是：'word'空格被标记为'~'，所需的输出将是：word工作~沃~dw~rdwo~~w~~d~~rd〜或〜哇～～～o～dw~~~~~r~~o~~Thereasonforthisistosearchforwordsthatmaynotbefullycompleteasthetextbeingsearchthroughfrom......
  • 数据结构之八大排序（上）
    找往期文章包括但不限于本期文章中不懂的知识点：个人主页：我要学编程(ಥ_ಥ)-CSDN博客所属专栏：数据结构（Java版） 目录排序的相关介绍直接插入排序 希尔排序（缩小增量排序）选择排序堆排序冒泡排序 排序的相关介绍排序的概念：所谓排序，就是使一串记录，按照其中的某个或......
  • 顺序表的实现
    一、顺序表的定义    顺序表是一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数据存储。在数组上完成数据的增删改查。二、顺序表的分类1、静态顺序表#defineN1000typedefintSLDataType;//静态顺序表typedefstructSeqList{ SL......
  • SQL执行顺序和逻辑
    SQL执行顺序和逻辑MySQL的执行顺序：  (9)SELECT  (6)SUM(聚合函数)  (10)DISTINCT<select_list>  (1)FROM<left_table>  (3)<join_type>JOIN<right_table>  (2)ON<join_condition>  (4)WHERE<where_condition>  (5)GROUP......
  • 【数据结构】之线段树理解与基础模板
    什么是线段树线段树是一种通过类似二分来实现的一种二叉树结构，方便区间的修改与性质的查询，是一种非常节约时间的数据结构。为什么使用线段树比如我们给你NNN......
  • 静态顺序表
    顺序表顺序表和链表都是线性表的一种，此处介绍顺序表数据的存储结构有分为逻辑存储结构和物理存储结构。顺序表和链表(之后的文章会详解)实际上都是线性表，是因为他们的逻辑存储关系都是线性的，只是因为在计算机内存中存储的方式(物理存储结构)不同。两种物理存储结构各有......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99