数据结构之顺序表的增删查改等操作详解

news/2024/5/20 7:13:19 标签: 顺序表, 数据结构

顺序表的增删查改

文章目录

顺序表

一段物理地址连续的存储单元依次存储数据元素的线性结构，其实就是数组，要求存储的数据是依次连续存储

顺序表的顺序存储示意图如下：

image-20210802091020155

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

固定大小的定义，给小了可能不够用，给大可能浪费

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

动态适应我们需求的大小，比较灵活

所

以我们主要针对动态顺序表进行讲解顺序表的增删查改等操作实现

首先我们创建三个文件，分别是：

image-20210802091637636

SeqList.h对相关头文件的包含，以及实现顺序表的结构和函数的声明

SeqList.c对实现顺序表增删查改等操作的函数进行定义

test.c文件进行顺序表相关函数和顺序表功能的测试

我们实现顺序表，首先需要对顺序表结构进行定义

//动态顺序表结构
typedef struct SeqList
{
    int* a;//定义一个指针指向动态开辟的内存，即存储顺序表数据的空间
    int size;//当前顺序表的数据个数
    int capacity;//顺序表的容量
};

在动态顺序表结构中，我们定义了一个指针指向动态开辟的内存，即存储顺序表数据的空间，定义size记录当前顺序表的数据个数，定义capacity记录当前顺序表的容量，但是我们想一下，我们顺序表的存储数据一定是整形吗？万一我想改变顺序表的数据类型呢？这样定义的话，我们想要改变顺序表的数据类型时，就会很麻烦，所有涉及到的地方都需要修改，所以我们这样定义：

typedef int SQDataType
//动态顺序表结构
typedef struct SeqList
{
    SQDataType* a;//定义一个指针指向动态开辟的内存，即存储顺序表数据的空间
    int size;//当前顺序表的数据个数
    int capacity;//顺序表的容量
}SLT;

这样定义我们在想要修改顺序表存储的数据类型时，就直接在typedef(类型重定义)这里修改就可以了，这样就方便了很多。

接下来我们在test.c中创建一个结构体变量(注意包含SeqList.h头文件)，开始定义顺序表的增删查改等操作。

然后我们来写顺序表的初始化接口的实现：

在定义函数之前，我们考虑这么一件事情

注意：

InitSeqList(s);
InitSeqList(&s);

我们在传结构体变量时是传值呢还是传址呢？

答案是传地址，因为函数传参的时候，参数是需要压栈的。如果传递一个结构体对象的时候，结构体过大，参数压栈的系统开销比较大，所以会导致性能的下降。

顺序表的初始化

void SeqListInit(SLT* psl)
{
    assert(psl);//我们断言一下，因为创建结构体变量的地址不能为NULL
    psl->a=NULL;
    psl->size=psl->capacity=0;
}

因为创建结构体变量的地址不能为NULL，所以我们在里面断言一下，将指针a置为空以及size和capacity置为0。

有初始化顺序表那就有销毁顺序表，下面我们看顺序表的销毁

顺序表的销毁

void SeqListDestory(SLT* psl)
{
    assert(psl);
    if(psl->a)
    {
       	free(psl->a); 
    	psl->a=NULL;  
    }   
}

当指向动态开辟的内存的指针不为NULL时，说明有顺序表的数据，我们将这段动态开辟的空间释放掉，并把它置为NULL。

然后我们再写一个打印顺序表数据的函数：

打印顺序表数据

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

打印的函数十分简单，就是相当于数组的遍历而已

写完上面的这些函数，我们就要进入我们顺序表的增删查改等操作的正题了。

顺序表尾插数据

首先是尾插数据函数，那么我们如何尾插一个元素呢？有人会说，我们不是有一个记录数据个数的变量size嘛，那么比如当前元素个数是size，那么我们要尾插的位置的下标应该就是size，仔细想一想对不对呢？是对的。但是我们在尾插前需要考虑的是，我们现在都没有空间，怎么存放数据呀，就算有了空间，你怎么知道当前这块空间有没有满呢？这里就需要用到我们的capacity变量了，故我们在尾插前一定要先检查是不是需要增容。

由于后面的一些操作也会用到考虑是不是需要增容，所以我们将判断是不是需要增容封装成一个函数：

void SeqListCheckCapacity(SLT* psl)
{
    assert(psl);
    if(psl->size==psl->capacity)//当当前元素个数等于我们的当前容量时我们要增容
    {
        //增容
        int newcapacity = psl->capacity==0?4:psl->capacity*2;
        psl->a=(SQDataType*)realloc(psl->a,newcapacity*sizeof(SQDataType));
        if(psl->a==NULL)
        {
            perror("psl->a");
            return;
        }
        psl->capacity=newcapacity;
    }
}

当当前元素个数等于我们的当前容量时我们要增容，我们在增容时，如果capacity是0时我们先开辟存储4个数据的内存，不是0时，我们就进行二倍的增容，如果开辟失败了，我们加一个判断pal->a是不是NULL，是NULL则打印错误返回，最后将capacity更新。

这时我们就可以写尾插的函数了：

void SeqListPushBack(SLT* psl,SQDataType x)
{
    assert(psl);
    //检查增容
    SeqListCheckCapacity(psl);
    psl->a[psl->size]=x;
    psl->size++;
}

首先检查增容，然后进行插入，我们要尾插的位置的下标就是size，插入然后将size++，就实现了尾插的操作。

我们进行测试发现，没有任何问题，完成了插入。

image-20210802103115735

下面我们进行下一个操作：头插。

顺序表头插数据

同样地，在头插之前我们需要检查是否需要增容

void SeqListPushFront(SLT* psl,SQDataType x)
{
    assert(psl);
    //检查增容
    SeqListCheckCapacity(psl);
    int end=psl->size-1;
    while(end>=0)
    {
        psl->a[end+1]=psl->a[end];
        end--;
    }
    psl->a[0]=x;
    psl->size++;
}

image-20210802104411992

在头插时，我们需要将后面的元素依次向后移动一个单元，然后在第一个位置插入，最后size++。

注意：

在移动元素时，我们需要从后往前开始移动，从前往后会将后面元素覆盖。

下面我们再进行下一个操作：尾删

void SeqListPopBack(SLT* psl)
{
    assert(psl);
    if(psl->size>=)
    {
    	psl->size--;
    }
}

尾删非常简单，我们直接将size–，就相当于删除了最后一个元素。

尾删之后我们再来看看头删：

顺序表头删数据

void SeqListPopFront(SLT* psl)
{
    assert(psl);
   	int begin=0;
    while(begin<psl->size-1)
    {
        psl->a[begin]=psl->a[begin+1];
        begin++;
    }
    psl->size--;
}

image-20210802105903503

头删我们只需要将第一个元素后面的元素从前往后依次向前移，就将第一个元素删除，然后size–即可。

注意：

在移动元素时，我们需要从前往后开始移动，从后往前会将前面元素覆盖。

之后我们再来看看如何找到一个元素x

int SeqListFind(SLT* psl, SQDataType x)
{
    assert(psl);
    int i=0;
    for(i=0;i<psl->size;i++)
    {
        if(psl->a[i]==x)
        {
            return i;//找到，返回下标
        }
    }
    return -1;//找不到
}

找到一个元素x也十分简单，就是遍历数组似的遍历一遍，判断是不是等于x，是的话返回下标，循环遍历完，说明没有找到，那么返回-1(找不到)。

那么我们能不能在一个指定位置进行插入元素呢？

答案是可以的，接下来我们来看在指定位置插入一个元素：

顺序表指定位置插入元素

void SeqListInsert(SLT* psl,size_t pos,SQDataType x)
{
    assert(psl);
    assert(pos<=psl->size-1&&pos>=0)
    size_t end=psl->size-1;
    while(end>=pos)
    {
        psl->a[end+1]=psl->a[end];
        end--;
    }
    psl->a[pos]=x;
   	psl->size++;
}

注意：size_t等价于unsigned int，有些人写出上面代码时，应该是觉得没什么问题，万无一失，感觉肯定是对的，但是不然，上面代码有隐含的错误点，是一个难点。

image-20210802121921434

代码崩了为什么呢？

这里的问题就出现在了无符号整形上，我们想一想，在size等于0时，此时end是-1，按理说while循环不会进去了，但是我们调试发现，他还是可以进去循环，为什么呢？就是因为end是无符号整形，这里会发生提升，end等于-1时，在内存中存储是：11111111111111111111111111111111，但end是无符号的，计算机会将他认为无符号的看待，会将32个全1翻译成4,294,967,295，故循环会进去。在pos等于0时，这个情况也会发生，因为要出循环，end就会减到-1，pos等于0时，end会减到-1，end是无符号整形，有符号整形和无符号整形进行运算时，会发生提升，-1会被提升为很大的数，此时循环也进去了，就会出现问题。

为了解决这个问题我们怎么做呢？

将end和pos都换成int类型，可以解决这个问题，但是由于C++库里面这个顺序表插入元素函数pos就用的是size_t类型，所以我们这里也用size_t类型，那么我们还要哪种改法呢？

改法一：

避免end等于-1，改变end的初始值以及进入循环条件

void SeqListInsert(SLT* psl,size_t pos,SQDataType x)
{
    assert(psl);
    assert(pos<=psl->size-1&&pos>=0)
    size_t end=psl->size;
    while(end > pos)
    {
        psl->a[end]=psl->a[end-1];
        end--;
    }
    psl->a[pos]=x;
   	psl->size++;
}

改法二：

将end改为int类型，因为无符号数遇到有符号数会转化为有符号数，所以将pos强制类型转换为有符号数

void SeqListInsert(SLT* psl,size_t pos,SQDataType x)
{
    assert(psl);
    assert(pos<=psl->size-1&&pos>=0);
    int end=psl->size-1;
    while(end>=(int)pos)
    {
        psl->a[end+1]=psl->a[end];
        end--;
    }
    psl->a[pos]=x;
   	psl->size++;
}

经过测试，发现可以正常运行了：

image-20210802121506888

总结：要避免负数给到无符号，或者避免有符号数变成负数以后，被提升或者强转为有符号。

明白了上面这个点，我们来看下一个函数实现，指定位置元素删除

指定位置元素删除

void SeqListErase(SLT* psl, size_t pos)
{
    assert(psl);
    assert(psl->size>0);
    assert(pos<=psl->size-1&&pos>=0);
    int begin=pos;
    while(begin<psl->size-1)
    {
        psl->a[begin]=psl->a[begin+1];
        begin++;
    }
    psl->size--;
}

和上面讲的头删原理差不多，唯一区别就是断言pos的取值范围，还有就是开始移动的位置不一样，这里的移动位置是参数传递的，位置是指定的。

我们测试可以发现可以正常运行：

image-20210802122055325

最后我们再讲解两个简单的操作，返回数据的个数和将一个位置的数据改为x

返回顺序表总数据的个数

//返回数据的个数
size_t SeqListSize(SLT* psl)
{
	assert(psl);
	return psl->size;
}

很多人好奇，这么简单的操作为什么要写成函数呢？我们写成函数是有道理的，如果我们直接在外面用s.size去访问size多简单呀，虽然可以这样访问，但是数据结构约定，我们进行数据访问以及修改都进行函数的方式进行，这样是更规范的行为

修改数据

//将一个位置的数据改为x
void SeqListAt(SLT* psl, size_t pos, SQDataType x)
{
	assert(psl);
	assert(pos < psl->size);

	psl->a[pos] = x;
}

如果我们直接去修改，不用函数，则这样修改：例如s.a[3]=8;

这样编译器不会报错对你进行检查，我们举个例子：image-20210802123728767

我们这里只有两个元素，而s.a[3]=8，直接将第4个元素修改了，这里明明越界了，编译器没有报错，实际上我们没有真越界，因为我们刚开始是有4个元素的空间的，只是修改了size之外的空间。越界不一定报错，越界的检查是一种抽查。越界写是如果修改到标志位才会检查出来.而我们调用函数时，直接会检查出来错误，不会有那么多的麻烦。

以上就是我们约定：我们进行数据访问以及修改都进行函数的方式进行的原因

三个文件的源代码：

SeqList.h(头文件的包含以及顺序表结构以及函数的声明)

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

typedef int SQDataType;

//顺序表结构
typedef struct SeqList
{
	SQDataType *a;
	int size;//数据个数
	int capacity;//容量
}SLT;


//顺序表的初始化
void InitSeqList(SLT* psl);

//顺序表的销毁
void DestorySeqList(SLT* psl);

//顺序表的增删查改


void SeqListPushBack(SLT* psl, SQDataType x);//O(1)

void SeqListPushFront(SLT* psl, SQDataType x);//需要挪动数据O(N)

void SeqListPopBack(SLT* psl);//O(1)

void SeqListPopFront(SLT* psl);

//打印顺序表
void PrintSeqList(SLT* psl);

int SeqListFind(SLT* psl, SQDataType x);

//void SeqListInsert(SLT* psl,int pos, SQDataType x);

void SeqListInsert(SLT* psl,size_t pos, SQDataType x);
//
void SeqListErase(SLT* psl,size_t pos);
//
size_t SeqListSize(SLT* psl);
//
void SeqListAt(SLT* psl,size_t pos, SQDataType x);

SeqList.c(顺序表操作函数的定义)

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
//初始化顺序表
void InitSeqList(SLT* psl)
{
	assert(psl);

	psl->a = NULL;
	psl->size = psl->capacity = 0;
}
//销毁顺序表
void DestorySeqList(SLT* psl)
{
	assert(psl);
	if (psl->a)
	{
		free(psl->a);
		psl->a = NULL;
	}
	psl->capacity = psl->size = 0;
}


//检查增容
void SeqListCheckCapacity(SLT* psl)
{
	assert(psl);
	if(psl->size == psl ->capacity)
	{
		//增容
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity *2 ;
		psl->a =(SQDataType*)realloc(psl->a,newcapacity*sizeof(SQDataType));
		if (psl->a == NULL)
		{
			perror("SeqListCheckCapacity");
			return;
		}
		psl->capacity = newcapacity;
	}
}
//尾插头插，尾删头删
//尾插
void SeqListPushBack(SLT* psl, SQDataType x)
{
	assert(psl);
	//检查增容
	SeqListCheckCapacity(psl);
	psl->a[psl->size] = x;
	psl->size++;
}

//头插
void SeqListPushFront(SLT* psl, SQDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);
	int end = psl->size - 1;//最后一个元素下标
	while (end>=0)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[0] = x;
	psl->size++;
}

//尾删
void SeqListPopBack(SLT* psl)
{
	assert(psl);
	assert(psl->size > 0);
	if (psl->size>0)
	{
		psl->size--;
	}
}

//头删
void SeqListPopFront(SLT* psl)
{
	assert(psl);
	assert(psl->size > 0);
	int begin = 0;
	while (begin<psl->size-1)
	{
		psl->a[begin] = psl->a[begin + 1];
		begin++;
	}
	psl->size--;
}

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

//找到一个元素x
int SeqListFind(SLT* psl, SQDataType x)
{
	assert(psl);
	int i = 0;
	for (i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			printf("找到了，下标为：%d\n", i);
			return i;
		}
	}
	printf("找不到\n");
	return -1;
}
//
//void SeqListInsert(SLT* psl, size_t pos, SQDataType x)
//{
//	assert(psl);
//	assert(pos >= 0 && pos <= psl->size);
//	size_t end = psl->size - 1;//size==0时end=-1，-1>=0,本来循环进不去，但是这里end会提升，所以进去了，就出问题了
//	while (end >= pos)//pos等于0时，end会减到-1，end是无符号整形，-1会被算术转换为很大的数，此时循环也进去了，就会出现问题
//	{
//		psl->a[end + 1] = psl->a[end];
//		end--;
//	}
//	psl->a[pos] = x;
//	psl->size++;
//}

//上面这个不能插入在顺序表的头怎么解决呢？
//这里将pos和end类型改为int类型可以解决
//void SeqListInsert(SLT* psl, int pos, SQDataType x)
//{
//	assert(psl);
//	assert(pos <= psl->size && pos >= 0);
//	int end = psl->size - 1;
//	while (end >= pos)
//	{
//		psl->a[end + 1] = psl->a[end];
//		end--;
//	}
//	psl->a[pos] = x;
//	psl->size++;
//}

//但是我们c++中库里面这个pos是size_t类型,不改变类型我们如何解决问题呢？
//怎么让pos类型不改变，就为size_t,也让头插可以复用



//解决方案1：
void SeqListInsert(SLT* psl, size_t pos, SQDataType x)
{
	assert(psl);
	assert(pos <= psl->size && pos >= 0);//有效数字范围内
	SeqListCheckCapacity(psl);
	size_t end = psl->size;//将end改为psl->size，end就不会变成-1
	while (end > pos)//只有pos==0或者size==0才会出问题导致end会等于-1，提升就会出问题，
	{
		psl->a[end] = psl->a[end-1];
		end--;
	}
	psl->a[pos] = x;
	psl->size++;
}

//解决方案2
//void SeqListInsert(SLT* psl, size_t pos, SQDataType x)
//{
//	assert(psl);
//	assert(pos <= psl->size && pos >= 0);//有效数字范围内
//	SeqListCheckCapacity(psl);
//	int end = psl->size - 1;
//	while (end >=(int) pos)
//	{
//		psl->a[end + 1] = psl->a[end];
//		end--;
//	}
//	psl->a[pos] = x;
//	psl->size++;
//}

//避免负数给到无符号，或者避免有符号数变成负数以后，被提升或者强转成有符号

//删除某个位置的元素
void SeqListErase(SLT* psl, size_t pos)
{
	assert(psl);
	assert(pos <= psl->size&&pos>=0);

	size_t begin = pos + 1;
	while (begin < psl->size)
	{
		psl->a[begin - 1] = psl->a[begin];
		begin++;
	}
	psl->size--;
		
}

//返回数据的个数
size_t SeqListSize(SLT* psl)
{
	assert(psl);
	return psl->size;
}

//将一个位置的数据改为x
void SeqListAt(SLT* psl, size_t pos, SQDataType x)
{
	assert(psl);
	assert(pos < psl->size);

	psl->a[pos] = x;
}

test.c(顺序表操作的测试)

#include"SeqList.h"
void TestSeqList1()
{

	SLT s;
	//顺序表的初始化
	InitSeqList(&s);//值传递
	//SeqListPushFront(&s, 5);

	/*SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);*/


	SeqListInsert(&s, 0, 6);
	SeqListInsert(&s, 1, 7);
	PrintSeqList(&s);

	//s.a[3] = 8;
	//SeqListErase(&s, 1);
	//PrintSeqList(&s);
	
	//SeqListPopBack(&s);
	//SeqListPopFront(&s);

	//PrintSeqList(&s);
	SeqListFind(&s, 3);



	//PrintSeqList(&s);

	

	//SeqListAt(&s, 2, 9);
	//PrintSeqList(&s);

	//DestorySeqList(&s);
}

欢迎大家前来讨论学习，如果觉得文章不错，点赞评论+收藏哦！！！


http://www.niftyadmin.cn/n/880348.html

相关文章

AssetBundle for unity

AssetBundle for unity

AssetBundle for Unity 首先推荐读取官方doc:https://docs.unity3d.com/Manual/AssetBundlesIntro.html 基础&#xff1a;打包&加载 打包 使用自编译打包工具 [MenuItem("AssetBundles/BunildBundles")]static void BulidAssetBundles(){//Assets/AssetBundl…
阅读更多...
数据结构之单链表的增删查改等操作画图详解

数据结构之单链表的增删查改等操作画图详解

单链表 文章目录单链表链表的概念及其结构概念结构链表的实现开辟一个新结点链表的销毁打印链表单链表的尾插单链表的头插单链表的头删单链表的尾删找到单链表中的一个结点在pos位置后插入结点在pos位置前插入一个结点pos位置后删除结点pos位置删除结点返回链表大小判断链表是否…
阅读更多...
strangeioc test learn

strangeioc test learn

strangeioc test learn 文中所有步骤根据StrangeIoc框架示意图来的&#xff0c;这个图得下载地址&#xff1a;http://pan.baidu.com/s/1hs3bOAo 我们首先要创建root,作为启动框架的脚本&#xff0c;资料里面说这个类还做了初始化&#xff0c;到底是什么初始化&#xff0c;暂时…
阅读更多...
数据结构之带头结点的循环双向链表详细图片+文字讲解

数据结构之带头结点的循环双向链表详细图片+文字讲解

双向循环链表 文章目录双向循环链表前言文件的创建双向链表结构的定义创建返回链表的头结点值传递时&#xff1a;地址传递&#xff1a;双向链表的销毁双向链表的打印开辟一个新结点双向链表的尾插双向链表的头插双向链表的尾删双向链表的头删双向链表查找双向链表在pos的前面进…
阅读更多...
由堆栈所能想到的以及ref,out参数

由堆栈所能想到的以及ref,out参数

由堆栈所能想到的&#xff1f;&#xff1f; 提到堆栈区别&#xff0c;大部分首先想到的是&#xff0c;“值类型存储在栈中&#xff0c;引用类型存储在堆中&#xff0c;引用类型在栈上存储指向堆的地址”这句话。说这个我先想说一下值类型和引用类型&#xff0c;以及值传递和引…
阅读更多...
数据结构之顺序表和链表的区别

数据结构之顺序表和链表的区别

顺序表和链表的区别 存储空间上 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素&#xff0c;物理上连续 链式存储结构用一组任意的存储单元存放线性表的元素&#xff0c;逻辑上连续&#xff0c;但物理上不一定连续(逻辑上就是我们想象出来的&#xff0c;看着它是链…
阅读更多...
数据结构之栈以及栈的基本操作

数据结构之栈以及栈的基本操作

栈 文章目录栈前言进栈出栈的变化形式栈的实现栈的顺序存储结构&#xff1a;栈的链式存储结构&#xff1a;文件的创建栈结构的定义栈的初始化入栈出栈获取栈顶元素获取栈中有效元素个数检测栈是否为空销毁栈括号匹配问题前言 栈是限定仅仅在表尾进行插入和删除操作的线性表。 在…
阅读更多...
数据结构之队列的基本操作以及栈和队列的OJ题画图详解

数据结构之队列的基本操作以及栈和队列的OJ题画图详解

队列 文章目录队列队列的概念队列的实现文件的创建队列结构的定义队列初始化队列的销毁队列的打印队列的插入队列的删除队列的大小取队头元素取队尾元素判断是否是空队列源代码栈和队列的OJ题用队列实现栈设计循环队列两个栈实现队列队列的概念 只允许在一端进行插入数据操作&a…
阅读更多...
最新文章

Copyright @ 2022~2023