当前位置 : 主页 > 编程语言 > c语言 >

数据结构入门(C语言版)线性表中顺序表介绍及接口实现

来源:互联网 收集:自由互联 发布时间:2023-09-07
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 (导航) 数据结构入门之线性表 C语言的学习结束,就该入门数据结构了呦 不论在程序员的工作上,还是在学习或

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

(导航)


数据结构入门之线性表

C语言的学习结束,就该入门数据结构了呦

不论在程序员的工作上,还是在学习或是考研上,数据结构都是一门非常重要且值得我们一直研究探索的学科,可以说数据结构和算法就是编程的核心。OK,接下来我们来到数据结构的入门第一步就是学习线性表,接下来由作者来详细介绍数据结构第一章线性表。


一、线性表

1、什么是线性表?

维基百科:线性表(英语:Linear List)是由n(n≥0)个数据元素(结点)a[0],a[1],a[2]…,a[n-1]组成的有限序列。

你可以理解为零个或多个数据元素的有限序列。

线性表的数据集合为{a1,a2,…,an},其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

在较复杂的线性表中,一个数据元素可以由若干个数据项组成。

2、线性表的存储结构

线性表的可按照顺序存储结构形成顺序表,或者按照链式结构形成链式表。 这里我们先介绍顺序表

二、顺序表

1、 顺序表基本概念

定义:用一组地址连续的存储单元依次存储线性表的数据元素,这种存储结构的线性表称为顺序表。

特征:逻辑上相邻的数据元素,物理次序也是相邻的。

优缺点:

①随机访问:只要确定好了存储线性表的起始位置,线性表中任一数据元素都可以随机存取(数据读写所需的时间与存储位置无关)。在O(1)的时间内找到第 i 个元素。代码上以数组 (序号读取地址) 的方式实现。

②存储密度高:每个节点只存储数据元素。

③静态拓展容量不方便,动态拓展容量易造成空间浪费。

④插入、删除数据不方便,需要移动大量数据。

2、静态顺序表结构体定义

#define N 100
typedef int SeqDataType;
typedef struct Seqlist
{
	SeqDataType a[N];//定值数组
	int size;//表示数组中存储了多少个数据
}SeqList;

静态特点:如果满了就不让插入 缺点:给多少空间不确定 给小了不够用,给大了浪费 一般不推荐,在现实中运用少,但适合初学者练习顺序表的建立

3、动态顺序表结构体定义

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

动态特点:将静态的定值数组改为了可以接收动态开辟内存地址的指针,且增加了一个变量capacity表示容量。 我们这里使用动态顺序表结构体来定义接口函数

三、顺序表接口实现

1、头文件的结构体建立和接口函数声明

typedef int SeqDataType;
typedef struct SeqList
{
	SeqDataType* a;
	int size;      
	int capacity;
}SeqList;
void SeqListInit(SeqList* pq);//初始化
void SeqListCheckCapacity(SeqList* ps);//检查扩容
void SeqListPushBack(SeqList* pq, SeqDataType x);//尾插
void SeqListPushFront(SeqList* pq, SeqDataType x);//头插
void SeqListPopBack(SeqList* pq);//尾删
void SeqListPopFront(SeqList* pq);//头删
int SeqListFind(SeqList* pq, SeqDataType x);//查找
void SeqListInsert(SeqList* pq, int pos, SeqDataType x);//任意位置插入
void SeqListErase(SeqList* pq, int pos);//任意位置删除
void SeqListModify(SeqList* pq, int pos, SeqDataType x);//修改
void SeqListPrint(SeqList* pq);//打印
void SeqListDestory(SeqList* pq);//销毁

2、接口函数代码实现

A、初始化接口函数

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

初始化即将指针置空,长度容量初始化为0。

B、检查扩容接口函数

void SeqCheckCapacity(SeqList* pq)
{
	// 满了,需要增容
	if (pq->size == pq->capacity)
	{
		int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2;
		SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType)*newcapacity);
		if (newA == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		pq->a = newA;
		pq->capacity = newcapacity;
	}
}

在这里作者用了一个三目操作符判定空间如果为空则增加4个整形空间,若满则以2倍增容,这样不容易造成空间浪费,当然,随着数组长度越来越大,你会发现浪费依然存在且越来越大,实际上这也就是我们在前面提到的线性表的缺点,这是不可避免的,在后面我们学到的链表就很好的弥补了这个缺陷。

C、尾部插入接口函数

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

	SeqCheckCapacity(pq);

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

尾插在顺序表中是最好实现的,直接增加一位插入即可。

D、头部插入接口函数

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++;
}

在顺序表中,头插相对于尾插来说就不是那么简单了,这里主要是让顺序表整体向后移动,再在头部插入数据。

E、尾部删除接口函数

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

	--pq->size;
}

尾删直接进行--size操作即可,没必要对最后一个元素进行置空,再进行尾插时同样会覆盖

F、头部删除接口函数

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--;
}

头删的实现就是将除第一位之后的元素整体向前挪动覆盖。

在这里做一个小小的总结,我们会发现不论是头插还是头删,无论在时间上,还是代码量上都比尾插和尾删浪费更多,动一位影响整体,在链表中,同样也很好的弥补了这一点。

G、查找接口函数

int SeqListFind(SeqList* pq, SeqDataType x)
{
	assert(pq);

	for (int i = 0; i < pq->size; ++i)
	{
		if (pq->a[i] == x)
		{
			return i;
		}
	}

	return -1;
}

查找的实现即为遍历顺序表,比较查找是否有我们想要的元素 没有:返回-1 有:返回该元素的下标(如果有多个符合要查找的元素,则返回优先找到的元素的下标)

H、任意位置插入接口函数

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++;
}

任意位置插入代码实现,即为将从顺序表中要插入的位置开始,往后原有的元素整体往后移动一位,腾出空位来插入要插入的元素;此函数可以很好的替代前面的头插和尾插。 头插

void SeqListPushFront(SeqList* pq, SeqDataType x)
{
	SeqListInsert(pq, 0, x);
}

尾插

void SeqListPushBack(SeqList* pq, SeqDataType x)
{
	SeqListInsert(pq, pq->size, x);
}

I、任意位置删除接口函数

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--;
}

任意位置删除代码实现,和任意位置插入函数同理,即为将从顺序表中要删除的位置开始,往后原有的元素整体向前移动一位,直接覆盖要删除的元素;此函数可以很好的替代前面的头删和尾删。 头删

void SeqListPopFront(SeqList* pq)
{
	SeqListErase(pq, 0);
}

尾删

void SeqListPopBack(SeqList* pq)
{
	SeqListErase(pq, pq->size - 1);
}

J、修改接口函数

void SeqListModify(SeqList* pq, int pos, SeqDataType x)
{
	assert(pq);
	assert(pos >= 0 && pos < pq->size);//断言是否在有效范围内

	pq->a[pos] = x;
}

对某个元素的修改,可以对其所在下标进行访问再进行覆盖修改

K、打印顺序表接口函数

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

遍历顺序表逐个打印即可,与打印数组类似。

L、销毁顺序表接口函数

void SeqListDestory(SeqList* pq)
{
	assert(pq);

	free(pq->a);
	pq->a = NULL;
	pq->capacity = pq->size = 0;
}

与初始化类似,但在这我们需要先free空间(对应relloc),再进行初始化操作,即可销毁顺序表。

四、总结

总的来说,结合头删尾删的小总结,包括中间插入和删除操作,我们不难看出,这些操作效率都很低,且在增容内存分配上,存在空间浪费,有一定缺陷,但在元素的访问上,可以做到随机访问,通过下标直接访问元素,这是顺序表的优点。

这就是数据结构线性表之顺序表的主要知识点,感谢你的阅读,让我有更新的动力,下一期我们讲链表中的单链表!!!

制作不易,如有不正之处,敬请指出,感谢来访,一键三连,蟹蟹你呦!!! 如有兴趣还可以关注我的csdn博客:小谢爱学C语言

上一篇:包的介绍
下一篇:没有了
网友评论