【数据结构】C语言实现顺序表(超级详细)

这篇具有很好参考价值的文章主要介绍了【数据结构】C语言实现顺序表(超级详细)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

概念及结构

接口函数实现

顺序表的初始化

容量判断

 顺序表尾插

 顺序表尾删

顺序表头插

顺序表头删

顺序表查找

顺序表指定位置插入

顺序表指定位置删除

打印顺序表

销毁顺序表

顺序表完整代码


概念及结构

顺序表作为线性表的一种,它是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般分为:

1、静态顺序表——使用定长数组进行存储元素。

#define N 100
//顺序表的静态存储
typedef int SLDatatype;
typedef struct SeqList
{
	SLDataType Data[N]; //定长数组
	int size;           //有效数据个数
}SeqList;

这种存储方式在存储数据时比较有局限性,当数据存储量非常小的时候,数组长度太长,会造成空间的浪费;当数据存储量非常大的时候,数组空间可能会不够,但是这种存储方式不能进行扩容。所以在实现顺序表时,我们通常使用的是动态顺序表。这样能够提高我们的空间利用率。

2、动态顺序表——使用动态开辟的数组进行存储元素。

//顺序表的动态存储
typedef int SLDatatype;
typedef struct SeqList
{
	SLDataType* Data; //定长数组
	int size;         //有效数据个数
	int capacity;     //空间容量的大小
}SeqList;

接口函数实现

顺序表的初始化

//初始化链表
void SLInit(SeqList* ps)
{
	assert(ps);   //判空,如果传入的空指针,后面对它进行解引用就会报错
	ps->data = NULL; //将data初始化为空指针
	ps->capacity = ps->size = 0;
}

现在顺序表的初始化完成了,接下来就是顺序表的增删查改了。

在实现顺序表增加元素的函数功能前,首先我们先实现一个检查顺序表是否已经存满。如果已经存满了,那么我们就需要对它进行扩容。

容量判断

//容量判断
void Check_Capacity(SeqList* ps)
{
	assert(ps);
	if (ps->capacity == ps->size) //判断顺序表中有效数据个数是否已经达到容量大小
	{
		int new_capacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;
        //如果容量为0的话,此时就是第一次向顺序表中添加元素,capacity就设为4
        //如果容量不为0,此时就是有效数据个数达到容量,就进行扩容,新容量设置为原容量的2倍
		SLDataType* tmp = (SLDataType*)realloc(ps->data, new_capacity * sizeof(SLDataType));
		if (tmp == NULL)  //如果扩容失败,就终止程序。
		{
			perror("ralloc fail");
			exit(-1);
		}
		ps->data = tmp;
		ps->capacity = new_capacity;
	}
}

这里扩容使用的是realloc函数,当我们进行第一次插入的时候,ps->data指针还是空指针,这时我们也可以使用realloc,realloc函数在使用的时候,如果传入的指针是空指针,它的作用就与malloc相同。 

 顺序表尾插

//顺序表尾插
void SL_PushBack(SL* ps, SLDataType x)
{
	assert(ps);
	Check_Capacity(ps);
	ps->data[ps->size] = x;
	ps->size++;
}

 顺序表尾删

//顺序表尾删
void SL_PopBack(SL* ps)
{
	assert(ps);
	assert(ps->size > 0); //如果顺序表中已经没有元素,那么就不用进行删除,所以
                          //这里需要检查顺序表中是否还有元素。
	ps->size--;
}

 无论是尾删还是头删,都要对顺序表进行检查表中是否还有元素。

顺序表头插

//顺序表头插
void SL_PushFront(SL* ps, SLDataType x)
{
	assert(ps);
	Check_Capacity(ps); //检查容量
    //将所有数据向后移动一位
	for (int i = ps->size - 1; i >= 0; i--)
	{
		ps->data[i + 1] = ps->data[i];
	}
	ps->data[0] = x;
	ps->size++;
}

头插时不仅要对容量进行检查,同时,我们也要将数据向后移动一位再进行插入操作,不然会造成数据丢失。

顺序表头删

//顺序表头删
void SL_PopFront(SL* ps)
{
	assert(ps);
    //如果顺序表中只有一个数据,那么直接将数据个数-1
    //如果对数据进行挪动,会造成越界
	if (ps->size == 1)
	{
		ps->size--;
		return;
	}
    如果数据个数不为1,就将数据中第2个到最后一个都往前移动一位
	for (int i = 1; i < ps->size; i++)
	{
		ps->data[i - 1] = ps->data[i];
	}
	ps->size--;
}

顺序表查找

//顺序表查找
int SL_Find(SeqList* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->data[i] == x)
		{
            //找到就返回下标
			return i;
		}
	}
    //找不到就返回-1
	return -1;
}

顺序表指定位置插入

//顺序表指定位置插入
void SL_Insert(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);
    //判定pos是否合法
	assert(pos <= ps->size);
	assert(pos >= 0);
	Check_Capacity(ps); //检查容量是否够用
    //将pos位置后的元素全部都向后移动一位
	for (int i = ps->size-1; i >= pos; i--)
	{
		ps->data[i + 1] = ps->data[i];
	}
	ps->data[pos] = x;
	ps->size++;
}

顺序表指定位置删除

//顺序表指定位置删除
void SL_Erase(SeqList* ps, int pos)
{
	assert(ps);
    //检查pos位置是否合法
	assert(pos >= 0);
	assert(pos < ps->size);
    //将pos位置后面的元素全都向前移动一位
	for (int i = pos; i < ps->size; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	ps->size--;
}

有了顺序表指定位置的插入和删除后,我们就可以对尾插尾删、头插头删进行改写:

//尾插
void SL_PushBack(SeqList* ps, SLDataType x)
{
	SL_Insert(ps, ps->size, x);
}

//尾删
void SL_PopBack(SeqList* ps)
{
	SL_Erase(ps, ps->size - 1);
}
//头插
void SL_PushFront(SeqList* ps, SLDataType x)
{
	SL_Insert(ps, 0, x);
}
//头删
void SL_PopFront(SeqList* ps)
{
	SL_Erase(ps,0);
}

打印顺序表

//打印顺序表
void SLPrint(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->data[i]);
	}
	printf("\n");
}

销毁顺序表

//销毁顺序表
void SL_Destroy(SeqList* ps)
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->capacity = ps->size = 0;
}

顺序表完整代码

SeqList.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* data;
	int size;
	int capacity;
}SeqList;

//初始化顺序表
void SLInit(SeqList* ps);

//删除顺序表
void SL_Destroy(SeqList* ps);

//打印顺序表
void SLPrint(SeqList* ps);

//检查容量
void Check_Capacity(SeqList* ps);

//尾插尾删
void SL_PushBack(SeqList* ps,SLDataType x);
void SL_PopBack(SeqList* ps);

//头插头删
void SL_PushFront(SeqList* ps, SLDataType x);
void SL_PopFront(SeqList* ps);

//顺序表查找
int SL_Find(SeqList* ps, SLDataType x);

//顺序表指定位置插入
void SL_Insert(SeqList* ps, int pos, SLDataType x);

//顺序表指定位置删除
void SL_Erase(SeqList* ps, int pos);

SeqList.c

#include "SeqList.h"

void SLInit(SeqList* ps)
{
	assert(ps);  
	ps->data = NULL; 
	ps->capacity = ps->size = 0;
}

void SL_Destroy(SeqList* ps)
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->capacity = ps->size = 0;
}

void SLPrint(SeqList* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->data[i]);
	}
	printf("\n");
}

void Check_Capacity(SeqList* ps)
{
	assert(ps);
	if (ps->capacity == ps->size) 
	{
		int new_capacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->data, new_capacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("ralloc fail");
			exit(-1);
		}
		ps->data = tmp;
		ps->capacity = new_capacity;
	}
}

void SL_PushBack(SeqList* ps, SLDataType x)
{
	//assert(ps);
	//Check_Capacity(ps);
	//ps->a[ps->size] = x;
	//ps->size++;
	SL_Insert(ps, ps->size, x);
}

void SL_PopBack(SeqList* ps)
{
	//assert(ps);
	//assert(ps->size > 0);
	//ps->size--;
	SL_Erase(ps, ps->size - 1);
}

void SL_PushFront(SeqList* ps, SLDataType x)
{
	//assert(ps);
	//Check_Capacity(ps);
	//for (int i = ps->size - 1; i >= 0; i--)
	//{
	//	ps->a[i + 1] = ps->a[i];
	//}
	//ps->a[0] = x;
	//ps->size++;
	SL_Insert(ps, 0, x);
}

void SL_PopFront(SeqList* ps)
{
	//assert(ps);
	//if (ps->size == 1)
	//{
	//	ps->size--;
	//	return;
	//}
	//for (int i = 1; i < ps->size; i++)
	//{
	//	ps->data[i - 1] = ps->data[i];
	//}
	//ps->size--;
	SL_Erase(ps,0);
}

int SL_Find(SeqList* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->data[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void SL_Insert(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos <= ps->size);
	assert(pos >= 0);
	Check_Capacity(ps);
	for (int i = ps->size-1; i >= pos; i--)
	{
		ps->data[i + 1] = ps->data[i];
	}
	ps->data[pos] = x;
	ps->size++;
}

void SL_Erase(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0);
	assert(pos < ps->size);
	for (int i = pos; i < ps->size; i++)
	{
		ps->data[i] = ps->data[i + 1];
	}
	ps->size--;
}

以上就是顺序表相关实现的全部内容了,希望能够帮到大家。文章来源地址https://www.toymoban.com/news/detail-846097.html

到了这里,关于【数据结构】C语言实现顺序表(超级详细)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构】顺序表---C语言版(数据结构开篇小菜,全网最详细!小白看一遍就学会!!!)

    停更了一个月限时返场啦😍从本篇文章开始就进入了我们数据结构的学习喽!本篇文章也是《数据结构与算法》 专栏的第一篇文章,本篇的内容是顺序表的学习,也是数据结构的开胃小菜,希望烙铁们可以理解消化哦🥰!!! 在我们学习 顺序表 之前呢,我们大家肯定会有

    2024年02月06日
    浏览(44)
  • 【数据结构】C语言实现顺序栈

    大家好,很高兴又和大家见面啦!!! 在上一个篇章中,我们介绍了栈的基本概念,以及栈中的重要术语。通过介绍我们知道了栈的本质也是一种线性表,只不过它是一种操作受限的线性表。因此栈的实现方式与线性表的实现实际上是大同小异的。下面我们就来介绍一下如何

    2024年01月19日
    浏览(40)
  • 顺序表—C语言实现数据结构

    本期带大家一起来用C语言代码实现顺序表🌈🌈🌈 顺序表是一段物理地址连续的存储单元,依次存储数据元素的线性结构。分为静态顺序表与动态顺序表。 🍊 🍋 🍒 静态顺序表 :使用定长数组用来存储数据 优点 :操作简单,代码实现容易 缺点 :定长数组很受限制,数

    2023年04月24日
    浏览(39)
  • 数据结构顺序表(C语言实现)

            从本章开始就是开始数据结构的开端,本章将会写出数据结构中的顺序表的代码实现,多会以注释的方法来描述一些细节(注释是我们程序员必须常用的工具)。         话不多说安全带系好,发车啦(建议电脑观看)。 附:红色,部分为重点部分;蓝颜色为需

    2024年02月10日
    浏览(49)
  • 【数据结构】C语言实现顺序表

    顺序表是用顺序存储方式存放的线性表(可以理解为数组的存储方式),表中的元素在内存中彼此相邻。 静态存储:在定义时就确定了顺序表的大小,并且之后顺序表的大小不会改变(即使之后空间不够用了,也无法增加) 动态存储:线性表的大小可以根据需要更改(顺序

    2024年02月08日
    浏览(40)
  • 【C语言数据结构】模拟·顺序表·总项目实现

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 我在上一篇博客中,

    2024年02月15日
    浏览(40)
  • 【数据结构初阶】二、 线性表里的顺序表(C语言实现顺序表)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】一. 复杂度讲解_高高的胖子的博客-CSDN博客  =======================================

    2024年02月08日
    浏览(42)
  • 【数据结构】线性表的顺序存储结构及实现——C语言版

    线性表的顺序存储结构称为 顺序表 ,其基本思想是 用一段地址连续的存储单元一次存储线性表的数据元素。 设顺序表的每个元素占用 c 个存储单元,则第 i 个元素的存储地址为: 所以, 只要确定了存储顺序表的起始地址(即基地址),计算任意一个元素的存储地址的时间

    2024年03月15日
    浏览(51)
  • 数据结构之顺序表的实现(C语言版)

         Hello, 大家好,我是一代,今天给大家带来有关顺序表的有关知识      所属专栏:数据结构      创作不易,望得到各位佬们的互三呦 1.首先在讲顺序表之前我们先来了解什么是数据结构 数据结构是由“数据”和“结构”两词组合⽽来。 什么是数据?常见的数值1、

    2024年04月25日
    浏览(47)
  • 【数据结构】详谈队列的顺序存储及C语言实现

    大家好,很高兴又和大家见面啦!!! 在上一篇内容中,我们在介绍完队列的基本概念、重要术语以及基本操作后,又回顾了一下数据结构的三要素——数据的逻辑结构、数据的存储结构以及数据的运算。 队列这种数据结构我们已经介绍了它的逻辑结构以及数据运算的定义

    2024年01月21日
    浏览(73)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包