文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

C语言深入浅出讲解顺序表的实现

2024-04-02 19:55

关注

今天起开始编写数据结构中的各种数据结构及算法的实现,说到顺序表,我们首先得了解下线性表。

1.线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。

线性表的存储

2.顺序表

2.1 概念及结构

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

1.静态顺序表:使用定长数组存储。

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

//顺序表的静态存储 
#define N 100
struct SeqList
{
	int a[N];//定长存储
	int size;//有效数据的个数
};
//顺序表的动态存储
typedef struct SeqList
{
	SeqDataType* a;//指向动态开辟的数组
	int size;	  //有效数据个数
	int capacity; //容量
}SeqList;

顺序表本质上是数组,在数组上增加了两个要求:

1.插入数据的过程中,可以动态增长

2.并且要求里面存储的数据必须是从左往右,是连续的

顺序表的缺陷

1.动态增容有性能消耗

2.头部插入数据时,需要挪动数据

2.2 提供接口

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小,所以下面我们来实现动态顺序表。

首先在头文件<SeqList.h>中提供接口:

typedef int SeqDataType; //需要插入什么类型的数据,就改成对应类型

typedef struct SeqList
{
	SeqDataType* a;//指向动态开辟的数组
	int size;	  //有效数据个数
	int capacity; //容量
}SeqList;

//内存中管理数据结构 提供增删查改的接口
//顺序表初始化
void SeqListInit(SeqList* pq);
//顺序表销毁
void SeqListDestory(SeqList* pq);
//顺序表打印
void SeqListPrint(SeqList* pq);//打印数组
//检查空间,如果满了,进行增容
void SeqCheckCapacity(SeqList* pq)
//顺序表尾插
void SeqListPushBack(SeqList* pq, SeqDataType x);
//顺序表头插
void SeqListPushFront(SeqList* pq, SeqDataType x);
//顺序表尾删
void SeqListPopBack(SeqList* pq);
//顺序表头删
void SeqListPopFront(SeqList* pq);
//顺序表查找x
int SeqListFind(SeqList* pq, SeqDataType x);//查找 查到返回下标,没查到返回-1
//顺序表在指定位置插入数据
void SeqListInsert(SeqList* pq, int pos, SeqDataType x);//在下标pos位置处插入数据
//顺序表在指定位置删除数据
void SeqListErase(SeqList* pq, int pos);//把下标为pos位置处的数据删除
//顺序表在指定位置替换数据
void SeqListModify(SeqList* pq, int pos, SeqDataType x);//把小标为pos位置的值改为x

2.3 接口实现

在源文件SeqList.c中实现接口功能

(1)顺序表初始化

void SeqListInit(SeqList* pq)
{
	assert(pq != NULL);//或者 assert(pq); 断言 防止传入空指针
	pq->a = NULL;
	pq->size = 0;
	pq->capacity = 0;
}

(2)顺序表销毁

void SeqListDestory(SeqList* pq)
{
	assert(pq);
	free(pq->a);
	pq->a = NULL;
	pq->size = 0;
	pq->capacity = 0;
}

(3)顺序表打印

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

(4)检查空间,如果满了,进行增容

//检查是否需要扩容
void SeqCheckCapacity(SeqList* pq)
{
	//满了,需要增容
	if (pq->size == pq->capacity)
	{
		int newcapacity = (pq->capacity == 0 ? 4 : pq->capacity * 2);

		//realloc接收的地址如果为空,将像malloc一样,开辟一块新空间
		SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType) * newcapacity);//realloc返回 开辟的新空间的地址
		if (newA == NULL)
		{
			printf("realloc fail\n");
			exit(-1);//失败了就退出
		}
		pq->a = newA;
		pq->capacity = newcapacity;
	}
}

(5)顺序表尾插

void SeqListPushBack(SeqList* pq, SeqDataType x)//尾插
{
	assert(pq);

	SeqCheckCapacity(pq);

	pq->a[pq->size] = x;
	pq->size++;
}

(6)顺序表头插

void SeqListPushFront(SeqList* pq, SeqDataType x)
{
	assert(pq);

	SeqCheckCapacity(pq);

	int end = pq->size - 1;
	while (end >= 0)
	{
		pq->a[end + 1] = pq->a[end];
		end--;
	}
	pq->a[0] = x;
	pq->size++;
}

(7)顺序表尾删

void SeqListPopBack(SeqList* pq)
{
	assert(pq);
	assert(pq->size > 0);
	pq->size--;
}

(8)顺序表头删

void SeqListPopFront(SeqList* pq)
{
	assert(pq);
	assert(pq->size > 0);

	int begin = 0;
	while (begin < pq->size - 1)
	{
		pq->a[begin] = pq->a[begin + 1];
		begin++;
	}
	pq->size--;
}

(9)顺序表查找x

int SeqListFind(SeqList* pq, SeqDataType x)
{
	assert(pq);
	for (int i = 0; i < pq->size; ++i)
	{
		if (pq->a[i] == x)
		{
			return x;
		}
	}
	return -1;//没找到
}

(10)顺序表在指定位置插入数据

void SeqListInsert(SeqList* pq, int pos, SeqDataType x){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->assert(pq);assert(pos >= 0 && pos < pq->size);SeqCheckCapacity(pq);//检查是否需要扩容int end = pq->size - 1;while (end >= pos){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->pq->a[end + 1] = pq->a[end];end--;}pq->a[pos] = x;pq->size++;}void SeqListInsert(SeqList* pq, int pos, SeqDataType x)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);

	SeqCheckCapacity(pq);//检查是否需要扩容

	int end = pq->size - 1;
	while (end >= pos)
	{
		pq->a[end + 1] = pq->a[end];
		end--;
	}
	pq->a[pos] = x;
	pq->size++;
}

(11)顺序表在指定位置删除数据

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

(12)顺序表在指定位置替换数据

void SeqListModify(SeqList* pq, int pos, SeqDataType x)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);

	pq->a[pos] = x;
}

主函数的设计大家可以自由发挥,做个简单的测试功能调用函数或是创建菜单栏实现交互都可以。我水平有限,请朋友们谅解!写的不好的地方还请大佬们指出。

下期预告——单链表

到此这篇关于C语言深入浅出讲解顺序表的实现的文章就介绍到这了,更多相关C语言 顺序表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯