纯净、安全、绿色的下载网站

首页

当前位置:首页IT学院IT技术

C语言数据结构顺序表 C语言编程简单却重要的数据结构顺序表全面讲解

高邮吴少   2021-10-22 我要评论
想了解C语言编程简单却重要的数据结构顺序表全面讲解的相关内容吗高邮吴少在本文为您仔细讲解C语言数据结构顺序表的相关知识和一些Code实例欢迎阅读和指正我们先划重点:C语言编程,C语言数据结构顺序表下面大家一起来学习吧

前言

本文主要介绍顺序表的定义和常见静态顺序表的用法

一、线性表定义

线性表(line list)是n个具有相同特性的数据元素的有限序列线性表是一种在实际中广泛使用的数据结构常见的线性表有:顺序表、链表、栈、队列、字符串
线性表在逻辑上是线性结构也就是说是连续的一条直线但在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储

二、顺序表实现

1概念及结构

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

顺序表一般可表示为:

1.静态顺序表:使用定长数组存储
2.动态顺序表:使用动态开辟的数组存储

我们以简单的静态顺序表进行引例(与动态顺序表接口函数思想是一样的)
代码如下(示例):

#define N 10//这里定义宏是为了方便将来如果需要更改空间的大小而代码中用到的10过于多要更改多次宏定义直接改N大小即可
typedef int SQDataType;//这里顺序表10个空间都是int型如果将来要改变类型可以在这里把int改为所需类型
struct SeqList//单个数据直接定义变量多个数据定义结构体
{
	SQDataType a[N];//顺序表有10个空间可进行存储
	int size;//顺序表存了几个数据(有10个空间不一定就存10个数据)
};

ps:顺序表的一些要求:
1.连续的物理空间存储-用的是数组
2.数据必须是从头开始依次存储

2静态顺序表

2.1实现顺序表接口第一步要对顺序表进行初始化

代码如下(示例):

#include<stdio.h>
#include<string.h>//memset函数头文件
//增删查改等接口函数
void SeqListInit(struct SeqList *ps)
{
	memset(ps->a, 0, sizeof(SQDataType)*N);//memset是一个初始化函数
	//sl.a表示按字节初始化
	//0表示初始化为0
	//sizeof(SQDataType)表示数组内每个元素大小(之前定义了SQDataType=int)N表示数组内共有N个元素两者相乘是数组大小
	ps->size = 0;
}
void TestSeqList1()
{
	struct SeqList sl;//sl是实参上面的ps是形参,为了实参和形参可以相互影响这里用的是传址调用
	SeqListInit(&sl);
}
int main()
{
	TestSeqList1();
	return 0;
}
//ps:如果这里你觉得写struct SeqList sl烦你可以这样改进代码(这里和2.1代码对应)
//typedef struct SeqList//单个数据直接定义变量多个数据定义结构体
//{
//	SQDataType a[N];//顺序表有10个空间可进行存储
//	int size;//顺序表存了几个数据(有10个空间不一定就存10个数据)
//}SL;
//这样结构体类型就可以直接写成SL

2.2对顺序表的增删查改的接口函数(以尾插为例)

void SeqListPushBack(struct SeqList *ps, SQDataType x)//尾插
{
	if (ps->size >= N)
	{
		printf("SeqList is full");//防止你尾插太多已经大于了顺序表最大容量
		return;
	}
	ps->a[ps->size] = x;
	ps->size++;//存储的数据多了一个size加1个
}

乍一看代码比较晦涩难懂我们用图来理解一下这个代码:

在这里插入图片描述

(图片来自比特就业课)

图示顺序表有7个空间我们放了5个数据现在要在尾部插入一个数据该数据下标是5而ps->size=5(结构体指针相关知识见笔者结构体文章)所以a[5]也就是a[ps->size]恰好是尾部后一个元素这里的5改成其他数也是同样的道理

ps->a[ps->size]=x也就是对尾部后一个元素赋值

ps->size++是表示顺序表存储的数据又多了一个(原本认定顺序表存储5个数据你现在添加了一个认定存储几个数据也要再加1个)
而你在尾插的过程中可能插入数据多了甚至多于数组最大容量这肯定会有问题所以我们用了一个if进行判断一下

到这里大家可能就会发现了在使用静态链表有两个不方便的地方:
1.数组给的空间小了可能不够用
2.数组给的空间大了可能浪费空间

3动态顺序表

3.1动态顺序表初始化

代码如下(示例):

typedef int SQDataType;
struct SeqList
{
	SQDataType*a;
	int size;//有效数据个数
	int capacity;//容量
};
//由于没有数组a了所以顺序表初始化也要改一下
void SeqListInit(struct SeqList *ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

在这里插入图片描述

(图片来自比特就业课)

3.2动态顺序表-尾插

代码如下(示例):

void SeqListPushBack(struct SeqList *ps, SQDataType x)
{	
	if (ps->size == ps->capacity)//原先空间满了无法进行尾插了需要进行扩容(扩容一般扩2倍)
	{
		int newcapacity = ps->capacity==0?4:ps->capacity*2;//这个4是可以换其他数的
		//这里是防止原来的容量是0扩容后的倍数仍然是0
		SQDataType*tmp = (SQDataType*)realloc(ps->a, newcapacity* sizeof(SQDataType));
		if (tmp == NULL)//防止扩容失败也就是没有剩余空间供它使用了
		{
			printf("realloc is fail\n");
			exit(-1);//退出运行
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
	ps->a[ps->size] = x;
	ps->size++;//存储的数据多了一个size加1个
}

我们在扩容时是用一个扩容一个吗?这样太浪费时间一般是扩容所需要的空间的两倍realloc函数可对指针指向的空间进行扩大或缩小感兴趣的同学自行了解这里不作深究

3.3动态顺序表-头插

了解过尾插这里讲头插也很容易理解就是在最前面插入一个内容如何操作呢?把已有的内容全部向后移动一位然后最前面会空出一个空间然后你放入内容
代码如下(示例):

void SeqListPushFront(struct SeqList *ps, SQDataType x)
{
//原先空间满了需要进行扩容
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity==0?4:ps->capacity*2;
		//这里是防止原来的容量是0扩容后的倍数仍然是0
		SQDataType*tmp = (SQDataType*)realloc(ps->a, newcapacity* sizeof(SQDataType));
		if (tmp == NULL)//防止扩容失败也就是没有剩余空间供它使用了
		{
			printf("realloc is fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
	int end = ps->size - 1;//确定最后一个内容下标
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];//以此把原先的内容往后挪一位
		--end;
	}
	ps->a[0] = x;//把需要插入的内容放在最开始的空间
	ps->size++;
}

这里需要注意的是头插和尾插都面临一个空间已经满的情况如果满了都需要扩容这个不要忘记如果你嫌麻烦每次都要写扩容你可以写一个扩容函数用的时候调用一下即可

3.4动态顺序表-尾删

代码如下(示例):

void SeqListPopBack(struct SeqList *ps)
{
	assert(ps->size > 0);
	//要进行删除首先要有东西可删
	//这里会进行断言如果没有东西删会报错
	ps->size--;
}

这里为什么size- -即可完成尾部数据的删除?解释是这样的size- -后电脑认为的有效数据就少了一个不管你那个数据还在不在电脑已经认为它不再是一个所需的数据了使用顺序表时不会对无效数据进行考虑

3.5动态顺序表-头删

头删也就是把最前面的数据删除其他数据下标依次减1即可
代码如下(示例):

void SeqListPopFront(struct SeqList *ps)
{
	assert(ps->size > 0);
	int start = 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		++start;
	}
	ps->size--;
}

3.6动态顺序表-任意位置插入数据

我们以下面这个顺序表举例

在这里插入图片描述

我们要在1和2中间插一个数据怎么办?0和1不变2和3分别向后移
但是考虑到其他的顺序表假设它原来的数据已经占满了所有空间你再插是不是有可能空间不够还有一点虽说是任意位置插入数据你能不能在顺序表尾部插入?非法访问了属于是考虑上面几点我们有下面的代码

void SeqListInsert(struct SeqList *ps, int pos, SQDataType x)
//pos表示插入位置的下标
{
	assert(pos < ps->size);//防止在尾部插入构成非法访问
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

3.7动态顺序表-任意位置删除数据

我们仍以下面的图举例要将2删除怎么办?把3往前挪一位即可

在这里插入图片描述

void SeqListErase(struct SeqList *ps, int pos)
{
	assert(pos < ps->size);
	int start =pos + 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	ps->size--;
}

结束

ps:上述的所有删除都是删除数据空间是不删除的


相关文章

猜您喜欢

  • @RequestBody注解只能注入对象和map 基于@RequestBody注解只能注入对象和map的解决

    想了解基于@RequestBody注解只能注入对象和map的解决的相关内容吗WoddenFish在本文为您仔细讲解@RequestBody注解只能注入对象和map的相关知识和一些Code实例欢迎阅读和指正我们先划重点:@RequestBody注解,注入对象,注入map下面大家一起来学习吧..
  • python递归函数 python基础之递归函数

    想了解python基础之递归函数的相关内容吗qianqqqq_lu在本文为您仔细讲解python递归函数的相关知识和一些Code实例欢迎阅读和指正我们先划重点:python基础,python递归函数下面大家一起来学习吧..

网友评论

Copyright 2022 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 联系我们