温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

C语言顺序表的概念及结构是什么

发布时间:2022-05-12 11:25:14 来源:亿速云 阅读:141 作者:zzz 栏目:开发技术

这篇文章主要介绍“C语言顺序表的概念及结构是什么”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“C语言顺序表的概念及结构是什么”文章能帮助大家解决问题。

    1.顺序表的概念及结构

    顺序表是使用一段连续物理地址的单元来依次储存数据的线性结构,一般采用数组存储。在数组上完成增删查改。

    C语言顺序表的概念及结构是什么

    顺序表分为两类:

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

    struct SeqList
    {
        int data;//存储的数据
        int size;//记录数据个数
        int 1000;//给定当前顺序表的总容量为1000
    };

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

    struct SeqList
    {
        int data;//存储的数据
        int size;//记录数据个数
        int capacity;//顺序表的总容量
    };

    2.增删查改的实现

    当我们需要储存的数据数目不确定时我们使用动态顺序表更佳,所以下面就用动态顺序表来实现增删查改。

    2.1扩容

    首先我们动态顺序表想要实现自动扩容,当当前数据量size等于总容量capacity时我们就需要自动增容,具体就是使用malloc函数开辟一定数量的空间,假如我们设定每次扩充二倍,代码如下:

    //增容
    void SLCheckcapacity(SL* pc)
    {
    	assert(pc != NULL);
    	//检查容量,满了就扩容
    	if (pc->sz == pc->capacity)
    	{
    		//一次扩容二倍,如果初始为0就先扩容到4
    		int newcapacity = pc->capacity == 0 ? 4 : pc->capacity * 2;
    		//注意类型转换
    		SLDatatype* tmp = (SLDatatype*)realloc(pc->data, sizeof(SLDatatype) * newcapacity);
    		if (tmp == NULL)
    		{
    			perror("SLCheckcapacity::realloc");
    			exit(-1);
    		}
    		//讲开辟的空间tmp给到数组
    		pc->data = tmp;
    		pc->capacity = newcapacity;
    	}
    }

    2.2插入数据

    插入数据时我们有三种情况,头插尾插和中间任意位置插。

    2.2.1尾插

    先从最简单的尾插开始,我们尾插时需要记录下当前的size,这样插入的时候就可以直接找到尾部,我们需要注意的是,我们插入之前需要判断一下当前的容量满了没有,如果满了就需要扩容,没满就可以直接插入。

    //尾插
    void SLPushBack(SL* pc, SLDatatype x)
    {
    	assert(pc != NULL);
    	//需要判断是否需要增容
    	SLCheckcapacity(pc);
    	pc->data[pc->sz] = x;
    	pc->sz++;
    }
    2.2.2头插

    头插相对来说要复杂一点,当头上没有数据时,我们就可以看成尾插直接插入,当头上有数据时,我们为了避免数据的覆盖,需要将所有数据向后移动,再放入在头部,在我们向后移动数据时我们也需要判断是否满容了。

    //头插
    void SLPushFront(SL* pc, SLDatatype x)
    {
    	assert(pc != NULL);
    	SLCheckcapacity(pc);
    	//挪动数据
    	int end = pc->sz - 1;
    	while (end >= 0)
    	{
    		pc->data[end + 1] = pc->data[end];
    		--end;
    	}
    	//插入数据
    	pc->data[0] = x;
    	pc->sz++;
    }
    2.2.3任意位置插入

    我们任意位置插入时有三种情况,当在第一个位置时就是头插可以调用头插的函数,在最后一个位置时就是尾插,就调用尾插的函数,当我们在中间的时我们需要找到需要插入的位置,然后将数据从这个位置开始向后挪动,再插入进去。

    //任意位置插入
    void SLInsert(SL* pc, int pos, SLDatatype x)
    {
    	assert(pc);
        //判断pos是否在有效数据范围内
    	assert(pos >= 0 && pos <= pc->sz);
    	SLCheckcapacity(pc);
        //挪动数据
    	int end = pc->sz - 1;
    	while (end >= pos)
    	{
    		pc->data[end+1] = pc->data[end];
    		--end;
    	}
    	pc->data[pos] = x;
    	pc->sz++;
    }

    2.3删除数据

    删除数据和上面的插入数据差不多,我们也需要凑够三个方面来撕开,头部删除,尾部删除,中间任意位置删除,当我们删除数据时我们只需要将这个数据后的数据依次向前挪动,覆盖住这个数据即可。这里我们不能用free函数去释放那块地址的空间来删除,因为顺序表的物理地址是连续的。链表可以,下一章会介绍。

    2.3.1尾删

    尾部后面没有数据那么就把最后一个数据制成0就好了

    //尾删
    void SLPopBack(SL* pc)
    {
    	assert(pc != NULL);
    	//不能删多了
    	assert(pc->sz > 0);
    	pc->sz--;
    }
    2.3.2头删

    将从第二个位置开始的数据往前挪动,这里需要注意,删除需要检查,以免越界。

    //删除需要检查,删多了会越界
    //头删
    void SLPopFront(SL* pc)
    {
    	assert(pc != NULL);
    	//检查
    	assert(pc->sz > 0);
    	//从第二个元素开始从后往前挪直接将其覆盖
    	int begin = 0;
    	while (begin <= pc->sz)
    	{
    		pc->data[begin-1] = pc->data[begin];
    		++begin;
    	}
    	pc->sz--;
    }
    2.3.3任意位置删除

    任意位置删除我们只需要将我们需要删除的位置后面的数往前挪动就行了

    //任意位置删除
    void SLErase(SL* pc, int pos)
    {
    	assert(pc != NULL);
    	assert(pos >= 0 && pos < pc->sz);
    	int begin = pos;
    	while (begin < pc->sz-1)
    	{
    		pc->data[begin] = pc->data[begin + 1];
    		begin++;
    	}
    	pc->sz--;
    }

    2.4查找

    我们给一个数据x来表示我们想要查找的数据,从前往后把顺序表遍历一遍,当给的X等于顺序表中的X时就找到了,返回当前位置的下标。

    //查找
    int SLFind(SL* pc, SLDatatype x)
    {
    	assert(pc != NULL);
    	for (int i = 0; i < pc->sz; ++i)
    	{
    		if (pc->data[i] == x)
    		{
    			return i;
    		}
    	}
    	printf("找不到\n");
    	return;
    }

    2.5修改数据

    当我们想要修改某一个地方的数据时,直接将那个位置的数据输入新的数据覆盖掉就行了。

    //改数据
    void SlModify(SL* pc, int pos, SLDatatype x)
    {
    	assert(pc != NULL);
    	if (pos >= 0 && pos <= pc->sz)
    	{
    		pc->data[pos] = x;
    	}
    	else
    	{
    		printf("超出范围了\n");
    	}
    }

    2.6销毁空间

    当我们顺序表使用完成过后,我们需要注意的是,我们malloc的空间并没有得到释放,可能会造成内存泄漏等问题(可参考前面的博客 '动态内存开辟' ),释放内存就需要用到free函数

    //销毁空间
    void SLDestory(SL* pc)
    {
    	if (pc->data)
    	{
    		free(pc->data);
    		pc->data = NULL;
    		pc->capacity = pc->sz = 0;
    	}
    }

    关于“C语言顺序表的概念及结构是什么”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识,可以关注亿速云行业资讯频道,小编每天都会为大家更新不同的知识点。

    向AI问一下细节

    免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

    AI