顺序表的基本操作

这篇具有很好参考价值的文章主要介绍了顺序表的基本操作。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一.什么是顺序表

二.顺序表的基本操作

  1.初始化

2.增容

3.尾插

4.头插

5.尾删

6.头删

7.指定位置插入

8.指定位置删除

9.打印

10.查找

11.销毁


一.什么是顺序表

        顺序表是用一段物理地址连续 的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
        顺序表一般分为静态顺序表和动态顺序表,静态顺序表一般是用定长数组存储,而动态顺序表则是用动态内存管理函数进行动态分配空间,当空间不够时可以进行增容
        静态顺序表:
#define MAX 100
typedef int SLDataType;//对类型重定义,方便适应不同的数据类型
struct SeqList
{
    SLDataType a[MAX];//定长数组
    int size;         //当前数据个数
};

动态顺序表:

typedef int SLDataType;//对类型重定义,方便适应不同的数据类型
typedef struct SeqList
{
	SLDataType *a;//定义指针指向动态开辟的空间
	int size;    //当前存储的数据个数
	int capacity; //数据最大个数
}SL;

        一般我们不太经常使用静态顺序表,因为实际需求往往空间都是不定的,因此我们只讨论动态顺序表

        顺序表的本质还是对数组进行操作,只是和数组有所不同的是,顺序表的数据是连续存放的

二.顺序表的基本操作

        一般地,我们都是用结构体定义顺序表,对顺序表的基本操作分为初始化,插入,删除,打印,查找,增容等操作,下面我们就来学习一下这些基本操作

  1.初始化

        顺序表的初始化我们只需要讲指针置为空指针,然后将当前数据元素个数和最大数据元素个数置为0,到插入时我们便会动态开辟空间给指针a

void SLInit(SL * ps)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	ps->a = NULL;//置为空指针
	ps->size = 0;//初始化为0
	ps->capacity = 0;
}

2.增容

        当当前数据元素个数等于最大数据元素个数时,说明空间已满,此时则需要我们进行扩容,而扩容需要我们利用的动态内存管理函数开辟空间,我们选择的是realloc函数,打开cpp网站查看该函数有关信息

顺序表的基本操作,数据结构和算法,数据结构,c语言,开发语言

          realloc函数的的两个参数分别为空间的地址和扩容后的空间大小,返回值是指向扩容后空间的地址,返回值void*,因此我们需要将其强制类型转换为我们需要的类型

        当realloc函数的第一个指针为空指针时,其作用相当于malloc,第一次增容,由于我们初始化时给了最大容量capacity为0,因此需要给capacity赋一个初始值4,后面再扩容时则最大容量翻倍

        第一次调用realloc函数时,由于我们初始化时将指针a赋为空指针,故第一次调用realloc函数作用和malloc函数相当,后面再次调用则实现扩容功能

void SLCheckCapacity(SL* ps)
{
	assert(ps);断言是否为空指针,如传入空指针则报错,防止函数被误用
	if (ps->size == ps->capacity)//判断当前数据个数是否到达最大值,是则增容
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//第一次给值为4,后面则翻倍
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));//利用动态内存管理函数realloc开辟空间
		if (tmp == NULL)//判断是否开辟成功,如果返回空指针说明开辟失败则报错,否则将空间的地址付给a指针
		{
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity = newCapacity;//最大容量更新为扩容之后的容量
	}
}

3.尾插

        尾插先判断空间是否已满,若空间已满,则需要扩容,然后再直接从尾部插入,后将数据个数加1即可

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	SLCheckCapacity(ps);//检查是否需要增容
	ps->a[ps->size] = x;//在尾部插入值
	ps->size++;			//数据个数加1
}

4.头插

        头插也需要判断空间是否已满,若空间已满,则需要扩容,然后再从头部插入,插入过程:先将顺序表里面已有的每一个元素往后挪动一个位置,相当于头部就腾出了一个“空位”,然后我们将需要插入的元素放到这个“空位”即可,后将数据元素加1

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	SLCheckCapacity(ps);//检查是否需要增容
	int end = ps->size - 1;
	while (end >= 0)//从尾部依次挪动元素
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;//将值赋给第一个元素
	ps->size++;  //数据个数加1
}

5.尾删

        尾删需要先判断当前顺序表是否有元素,没有元素则直接报错,如果有元素,我们只需要将数据个数减1即达到删除效果,而不需要对最后一个元素进行操作,后续操作直接将它覆盖就行

void SLPopBack(SL* ps)
{
	assert(ps->size > 0);//判断当前是否有元素
	ps->size--;//直接将数据个数减1即可
}

6.头删

        头删也需要先判断当前顺序表是否有元素,没有元素则直接报错,如果有元素,则删除的过程为:以我们排队打饭为例,当队伍的最前面一个人打完饭,后面的每一个人就都会往前一个位置,此时删除元素也是一样,从第二个位置开始到最后一个元素每个元素都依次往前挪动一个元素即可,后将数据个数减1

void SLPopFront(SL* ps)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	assert(ps->size > 0);//判断当前是否有元素
	
	int begin = 0;
	while (begin < ps->size - 1)//从尾部一次挪动元素
	{
		ps->a[begin] = ps->a[begin+1];
		begin++;
	}
	ps->size--;//数据个数减1
}

7.指定位置插入

        指定位置我们需要先判断指定位置是否合法,如果小于0或者大于最大元素个数则直接报错,再判断是否需要增容,然后从指定位置开始到最后一个元素每个元素依次往后挪动一个位置,然后再将所插入的元素放到指定位置即可,后将数据元素个数加1

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	assert(pos >= 0 && pos<=ps->size);//判断给定的位置是否合法
	SLCheckCapacity(ps);//检查是否需要增容
	int end = ps->size - 1;
	while (end >= pos)//从尾部依次挪动元素,直到到达给定位置
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;//将值赋给指定位置
	ps->size++;//数据个数加1
}

8.指定位置删除

        指定位置删除野需要先判断给定位置是否合法,不合法则直接报错,然后从指定位置到最后一个元素依次往前挪动一个位置即可,后将数据元素减1

void SLErase(SL* ps, int pos)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	assert(pos >= 0 && pos < ps->size);//判断给定的位置是否合法
	int begin = pos;
	while (begin < ps->size - 1)//从指定位置依次挪动元素,直到到达尾部的前一个元素
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}
	ps->size--;//数据个数减1
}

9.打印

        打印只需要定义一个循环变量,以下标的形式遍历顺序表打印即可

void SLPrint(SL* ps)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	int i = 0;
	for (i = 0; i < ps->size; i++)//依次遍历打印顺序表即可
	{
		printf("%d ", ps->a[i]);
	}
}

10.查找

        查找也是遍历顺序表,将每一个元素与查找的元素比较,若相等则返回元素下标,若遍历完没有找到元素,则返回-1,证明找不到该元素

int SLFind(SL* ps, SLDataType x)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	int i = 0;
	for (i = 0; i < ps->size; i++)//遍历数组,比较是否相等,相等则返回元素下标
	{
		if (ps->a[i] == x)
			return i;
	}
	return -1;//如果遍历没有找到该元素,则返回-1
}

11.销毁

        由于我们前面开辟空间是利用动态内存管理函数realloc开辟的,而该函数开辟的空间是由程序员自行开辟的,空间位于堆上,使用完空间后需要我们手动销毁,否则会导致内存泄露

        销毁空间我们需要用到free函数,我们打开cpp网站查看该函数有关信息

顺序表的基本操作,数据结构和算法,数据结构,c语言,开发语言

        freea函数的参数是一个指针,即所需要销毁的空间的地址,我们销毁顺序表只需要将指针a传给free函数即可,后讲指针a赋为空指针,防止其成为野指针

void SLDestroy(SL* ps)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	if (ps->a)
	{
		free(ps->a);//释放a指针指向的空间
		ps->a = NULL;//将a指针置为空,防止其成为野指针
		ps->size = ps->capacity = 0;//当前数据元素个数和最大数据元素个数全置为0
	}
}

        可以看到,上面的基本操作都是有相应的接口函数,我们只需要调用相应的函数即可实现顺序表的一些基本操作

        上面所有的接口函数都用到了assert函数,且都位于函数体开头,assert函数称之为断言函数,当表达式为真是继续执行,当表达式为假时则直接报错,而这种报错可以让我们快速了解错误出在什么地方

        我们打开cpp网站查看该函数有关信息

顺序表的基本操作,数据结构和算法,数据结构,c语言,开发语言

        上面的所有接口函数调用assert函数,传的参数时指针a,当指针a为空指针时则直接报错,可以防止函数被误用而导致一些未知的错误 

        上面就是顺序表的一些基本操作,以下是全部代码:

SeqList.c

#include"SeqList.h"
void SLCheckCapacity(SL* ps)
{
	assert(ps);断言是否为空指针,如传入空指针则报错,防止函数被误用
	if (ps->size == ps->capacity)//判断当前数据个数是否到达最大值,是则增容
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//第一次给值为4,后面则翻倍
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));//利用动态内存管理函数realloc开辟空间
		if (tmp == NULL)//判断是否开辟成功,如果返回空指针说明开辟失败则报错,否则将空间的地址付给a指针
		{
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity = newCapacity;//最大容量更新为扩容之后的容量
	}
}
void SLInit(SL * ps)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	ps->a = NULL;//置为空指针
	ps->size = 0;//初始化为0
	ps->capacity = 0;
}
void SLDestroy(SL* ps)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	if (ps->a)
	{
		free(ps->a);//释放a指针指向的空间
		ps->a = NULL;//将a指针置为空,防止其成为野指针
		ps->size = ps->capacity = 0;//当前数据元素个数和最大数据元素个数全置为0
	}
}
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	SLCheckCapacity(ps);//检查是否需要增容
	ps->a[ps->size] = x;//在尾部插入值
	ps->size++;			//数据个数加1
}
void SLPrint(SL* ps)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	int i = 0;
	for (i = 0; i < ps->size; i++)//依次遍历打印顺序表即可
	{
		printf("%d ", ps->a[i]);
	}
}
void SLPopBack(SL* ps)
{
	assert(ps->size > 0);//判断当前是否有元素
	ps->size--;//直接将数据个数减1即可
}
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	SLCheckCapacity(ps);//检查是否需要增容
	int end = ps->size - 1;
	while (end >= 0)//从尾部依次挪动元素
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;//将值赋给第一个元素
	ps->size++;  //数据个数加1
}
void SLPopFront(SL* ps)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	assert(ps->size > 0);//判断当前是否有元素
	
	int begin = 0;
	while (begin < ps->size - 1)//从尾部一次挪动元素
	{
		ps->a[begin] = ps->a[begin+1];
		begin++;
	}
	ps->size--;//数据个数减1
}
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	assert(pos >= 0 && pos<=ps->size);//判断给定的位置是否合法
	SLCheckCapacity(ps);//检查是否需要增容
	int end = ps->size - 1;
	while (end >= pos)//从尾部依次挪动元素,直到到达给定位置
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;//将值赋给指定位置
	ps->size++;//数据个数加1
}
void SLErase(SL* ps, int pos)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	assert(pos >= 0 && pos < ps->size);//判断给定的位置是否合法
	int begin = pos;
	while (begin < ps->size - 1)//从指定位置依次挪动元素,直到到达尾部的前一个元素
	{
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}
	ps->size--;//数据个数减1
}
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);//断言是否为空指针,如传入空指针则报错,防止函数被误用
	int i = 0;
	for (i = 0; i < ps->size; i++)//遍历数组,比较是否相等,相等则返回元素下标
	{
		if (ps->a[i] == x)
			return i;
	}
	return -1;//如果遍历没有找到该元素,则返回-1
}

SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//动态顺序表
typedef int SLDataType;//对类型重定义,方便适应不同的数据类型
typedef struct SeqList
{
	SLDataType *a;//定义指针指向动态开辟的空间
	int size;    //当前存储的数据个数
	int capacity; //数据最大个数
}SL;
void SLCheckCapacity(SL *ps);
void SLInit(SL * ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);

void SLPushBack(SL * ps, SLDataType x);
void SLPopBack(SL * ps);

void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);

void SLInsert(SL* ps,int pos, SLDataType x);
void SLErase(SL* ps, int pos);

int SLFind(SL* ps, SLDataType x);

test.c

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"
void TestSeqList()
{
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPushBack(&sl, 5);
	SLPushFront(&sl, 0);
	SLInsert(&sl, 2, 9);
	SLErase(&sl, 2);
	int pos = SLFind(&sl, 5);
	if (pos != -1)
		SLErase(&sl, pos);
	SLPrint(&sl);
	SLDestroy(&sl);
}
int main()
{

	TestSeqList();
	return 0;
}

输出结果:

顺序表的基本操作,数据结构和算法,数据结构,c语言,开发语言

  好啦,顺序表我们就先学到这里,如果喜欢我的文章,欢迎动动手指一键三连~文章来源地址https://www.toymoban.com/news/detail-807822.html

到了这里,关于顺序表的基本操作的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言---数据结构实验---顺序表的合并---链表的基本操作---重点解析约瑟夫问题

    实验的写法多种多样,但本文并未采用 #define 定义容量的写法,这样写已经是很老旧过时的写法。所有实验主体采用均为动态开辟,后续如果利用 C++ 来写或许会应用更多语法… 本篇展示数据结构的两个实验 其中,重点分析约瑟夫问题 实验中代码的命名风格等均与下方博客

    2024年02月16日
    浏览(70)
  • 【数据结构】线性表(一)线性表的定义及其基本操作(顺序表插入、删除、查找、修改)

    目录 一、线性表 1. 线性表的定义 2. 线性表的要素 二、线性表的基本操作 三、线性表的顺序存储结构 1. 定义 2. 顺序表的操作       a. 插入操作 b. 删除操作 c. 查找操作 d. 修改操作 e. 代码实例          一个线性表是由零个或多个 具有相同类型的结点 组成的有序集合。

    2024年02月03日
    浏览(70)
  • 数据结构---双向链表的基本操作

    头插法 遍历链表 尾插法 头删法 尾删法 按位置插入数据 按位置删除数据 dooublelinklist.c doublelinklist.h doublemain.c

    2024年02月22日
    浏览(53)
  • 【数据结构】——单链表的基本操作(带头结点)

            单链表解决了顺序表需要大量连续存储单元的缺点,但单链表附加指针域, 存储密度较顺序表低(考点!!) 。由于单链表的元素离散地分布在存储空间中,所以单链表是 非随机存取 的存储结构,即不能直接找到表中某个特定的结点。当查找某个特定结点时,需要

    2024年02月05日
    浏览(52)
  • 【Java】实现顺序表基本的操作(数据结构)

    在了解顺序表之前我们要先了解什么是线性表,线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构

    2024年02月03日
    浏览(53)
  • 【数据结构】C语言实现双链表的基本操作

    大家好,很高兴又和大家见面啦!!! 经过前面几个篇章的内容分享,相信大家对顺序表和单链表的基本操作都已经熟练掌握了。今天咱们将继续分享线性表的链式存储的第二种形式——双链表。在今天的内容中,咱们将介绍双链表的创建以及一些基本操作,接下来跟我一起

    2024年02月04日
    浏览(63)
  • 【数据结构】单链表的基本操作 (C语言版)

    目录 一、单链表 1、单链表的定义: 2、单链表的优缺点: 二、单链表的基本操作算法(C语言) 1、宏定义 2、创建结构体 3、初始化 4、插入 4、求长度 5、清空 6、销毁  7、取值 8、查找 9、删除 10、头插法创建单链表 11、尾插法创建单链表 三、单链表的全部代码(C语言)

    2024年01月22日
    浏览(60)
  • 数据结构 2.1 线性表的定义和基本操作

    数据结构三要素——逻辑结构、数据的运算、存储结构(物理结构) 线性表是具有 相同数据类型 的n(n=0)个数据元素的 有限序列 ,其中n为表长,当n=0时,线性表是一个空表。 每个数据元素所占空间一样大,有次序。 几个概念 1.ai是线性表中的第i个 i表示元素线性表中的

    2024年02月07日
    浏览(53)
  • c语言数据结构——链表的实现及其基本操作

    顺序表的问题及思考 问题: 中间/头部的插入删除,时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有数据插

    2023年04月09日
    浏览(85)
  • 【数据结构】C语言实现单链表的基本操作

    大家好,很高兴又和大家见面啦!!! 在上一篇中,我们详细介绍了单链表的两种创建方式——头插法与尾插法,相信大家现在对这两种方式都已经掌握了。今天咱们将继续介绍单链表的基本操作——查找、插入与删除。在开始今天的内容之前,我们先通过尾插法创建一个单

    2024年02月03日
    浏览(65)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包