资讯专栏INFORMATION COLUMN

数据结构——顺序表的实现

happen / 714人阅读

摘要:线性表是一种在实际中广泛使用的数据结构,常见的线性表顺序表链表栈队列字符串线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。


一、什么是线性表?

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

二、什么是顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为:
1.静态顺序表:就是存储空间固定,如果空间被数据放满了,此时就不能再插入数据了

2.动态顺序表:存储空间不固定,可以增容

三、顺序表的实现

1.顺序表的接口

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

代码如下:

//顺序表中存储的数据类型为进行重命名//为什么要重命名?//因为如果以后想将存储数据的内容改为char或者double等其他类型的话,只需在这里该一次就可以,在之前的栈和队列我们已经说过了,下次就不说了---^_^//而不必代码中的每一处都改,减少了不必要的麻烦,提高了代码的可读性typedef int SQDataType;typedef struct SeqList{	SQDataType* a;//指向顺序表的指针	int capacity;//顺序表的容量	int size;//实际在顺序表中已经存储数据的个数}SL;//顺序表的初始化void SeqListInit(SL* ps);////检查容量是否已满void SeqListCheckCapacity(SL* ps);////打印顺序表中的数据void SeqListPrint(SL* ps);////尾插void SeqListPushBack(SL* ps, SQDataType x);////尾删void SeqListPopBack(SL* ps);////头插void SeqListPushFront(SL* ps, SQDataType x);//头删void SeqListPopFront(SL* ps);//顺序表的摧毁void SeqListDestory(SL* ps);////随机插入void SeqListInsert(SL* ps, size_t pos, SQDataType x);//随机删除void SeqListErase(SL* ps, size_t pos);//在顺便表中找出一次出现x的下标,如果没有就返回-1int SeqListFind(SL* ps, SQDataType x);//修改下标为pos的值void SeqListModify(SL* ps, size_t pos, SQDataType x);

2.每个接口的实现

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

//顺序表的打印void SeqListPrint(SL* ps){	assert(ps && ps->a);//断言ps是否合法(是否为NULL)并且断言ps->a(指向顺序表的指针)是否合法	for (int i = 0; i < ps->size; i++)//从下标为0处开始打印数据,直到下标为size-1(最后一个数据)处为止	{		printf("%d ",ps->a[i]);	}	printf("/n");}//顺序表的摧毁void SeqListDestory(SL* ps){    assert(ps && ps->a);	free(ps->a);	ps->a = NULL;//释放后要将指针置NULL,防止被误操作(对已经被释放的空间操作)	ps->capacity = ps->size = 0;//空间已经被释放了,所以capacity和size也要置0}//顺序表的初始化void SeqListInit(SL* ps){	assert(ps);	ps->a = NULL;	ps->capacity = ps->size = 0;}//检查容量是否已满void SeqListCheckCapacity(SL* ps)//下面的头插,尾插等都需要调这个接口来检查是否需要扩容{	assert(ps);	if (ps->capacity == ps->size)//当capacity和size相等时需要扩容,此时有两种情况	{		int NewCapacity = ps->capacity == 0 ? 4 : 2*ps->capacity;//当capacity为0时,表示此时是指针a指向的是NULL,直接给4个容量。	    //当capacity不为0时,直接扩容原来的两倍		SQDataType* tmp = (SQDataType*)realloc(ps->a, NewCapacity*sizeof(SQDataType));//扩容		//这里用一个类型为SQDataType*的指针接受realloc的返回值,如果不这么做可能造成内存泄漏,因为如果扩容失败,realloc将返回NULL		//类似于ps->a=NULL,这样就会导致指针a也为NULL,原来a指向的空间就无法找到		if (!tmp)//如果tmp为NULL,表示扩容失败,给出提示信息,异常终止程序->exit(-1)		{			printf("relloc fail/n");			exit(-1);		}		else		{			ps->a = tmp;//成功的话就将tmp赋给a			ps->capacity = NewCapacity;//容量也进行更新		}	}}//尾插void SeqListPushBack(SL* ps,SQDataType x){	assert(ps);	SeqListCheckCapacity(ps);//先检查容量是否满了,满了就进行扩容	ps->a[ps->size++] = x;//因为前面已经检查了capacity,所以直接插入数据	//这里也等价于ps->a[ps->size] = x;	//           ps->size++;}//尾删void SeqListPopBack(SL* ps){	assert(ps && ps->a);	assert(ps->size > 0);//断言顺序表中是否有数据,如果有才进行Pop,所有的Pop接口都需要这么做	ps->size--;//不必担心顺序表里的数据,因为在下一次尾插或者头插时,会将后面的数据覆盖}//头插void SeqListPushFront(SL* ps, SQDataType x){	assert(ps);	SeqListCheckCapacity(ps);	int end = ps->size - 1;//end就表示最后一个元素的下标位置	while (end >= 0)//因为是头插,所以需要从前往后挪动数据,下面的头删,和随机删除,随机插入都需要挪动数据	{		ps->a[end + 1] = ps->a[end];		end--;	}	ps->a[0] = x;//数据挪动完成,第一个位置就相当于空,所以就可以用来存储x	ps->size++;}//头删void SeqListPopFront(SL* ps){	assert(ps && ps->a);	assert(ps->size > 0);	int begin = 1;	while (begin < ps->size)//这里依然是挪动数据,不过与前面不同的是,这里是从后往前挪动数据	{		ps->a[begin - 1] = ps->a[begin];//每次都将后一个数据挪到前一个位置		begin++;	}	ps->size--;}//在顺便表中找出一次出现x的下标,如果没有就返回-1int SeqListFind(SL* ps, SQDataType x){	assert(ps && ps->a);	for (int i = 0; i < ps->size; i++)//从下标为0开始遍历整个顺序表	{		if (ps->a[i] == x)		{			return i;//如果找到了与x相等的数,就返回这个数的下标,不过这里只能返回第一个			         //换句话说,如果顺序表出现了多个与x相等的值,只返回第一个与x相等的数的下标,因为我们是从下标为0开始找的		}	}	return -1;//如果找不到,就返回1,至于为什么返回1,众所周知,数组的下标不可能为负数,也可以返回其他负数,所以负数代表没找到}//在pos的位置插入void SeqListInsert(SL* ps, size_t pos, SQDataType x)//size_t pos表示想插入的下标位置{	assert(ps && ps->a);	assert(pos >= 0 && pos <= ps->size);//这里与前面的有所不同,主要是需要判断pos(下标位置)是否合法	SeqListCheckCapacity(ps);	size_t end = ps->size - 1;	while (end >= pos)	{		ps->a[end + 1] = ps->a[end];//依旧是挪动数据,从前往后挪		end--;	}	ps->a[pos] = x;//挪动完后,pos的位置相当于空,此时就用来存放x	ps->size++;}//删除pos位置的值void SeqListErase(SL* ps, size_t pos){	assert(ps && ps->a);	assert(pos >= 0 && pos < ps->size);//与前面的SeqListInsert是一样的原因	int begin = pos + 1;	while (begin < ps->size)	{		ps->a[begin - 1] = ps->a[begin];//从后往前挪动数据		begin++;	}	ps->size--;}//修改pos位置的值void SeqListModify(SL* ps, size_t pos, SQDataType x){	assert(ps && ps->a);	assert(pos >= 0 && pos < ps->size);//修改数据也要判断pos是否合法	ps->a[pos] = x;//将位置为pos的数据修改为x}

下面我们将用画图的方式来分析头插、头删、尾插、尾删等接口:

3.测试程序

代码如下:

void test(){	SL s;	SeqListInit(&s);	SeqListPushBack(&s, 1);	SeqListPushBack(&s, 2);	SeqListPushBack(&s, 3);	SeqListPrint(&s);	SeqListPopBack(&s);	SeqListPrint(&s);	SeqListPushFront(&s, 4);	SeqListPushFront(&s, 5);	SeqListPrint(&s);	SeqListInsert(&s, 2, 7);	SeqListPrint(&s);	SeqListErase(&s, 2);	SeqListPrint(&s);	SeqListDestory(&s);}int main(){	test();	return 0;}




总结

经过对顺序表的实现,我们知道了各个接口的原理,同时发现顺序表的头插、头删、随机插入,随机删除相对于尾插和尾删都十分麻烦,原因在于我们必须要挪动数据,而且需要十分小心的控制插入或删除的边界,否则会导致插入的数据把原始数据覆盖等一系列问题。但对于链表,我们不需要这么麻烦,我们只需要改变指针的指向即可,对于链表的实现,我们下期再说。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/123300.html

相关文章

  • 数据结构》第二章 | 线性表 知识梳理(应对期末考)

    文章目录 一、线性表的定义和特点及案例引入1.线性表的定义和特点2.案例引入(1) 一元多项式的运算(2) 稀疏多项式的运算(3) 图书信息管理...

    ChanceWong 评论0 收藏0
  • 数据结构--顺序表的c语言实现(超详细注释/实验报告)

    ... 数据结构顺序表的c语言实现(超详细注释/实验报告) 知识小回顾 线性表是一种最基本、最常用的数据结构,它有两种存储结构——顺序表和链表。顺序表是由地址连...

    Fourierr 评论0 收藏0
  • 数据结构之线性表

    ...,还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一,在实际程序中应用非常广泛,它还经常被用作更复杂的数据结构实现基础。 根据线性表的实际存储方式,分为两种实现模型: 顺序表,将元素顺序地存...

    leoperfect 评论0 收藏0
  • 数据结构与算法的Python实现(二)——线性表之顺序

    ...组元素的序列的抽象,就是线性表,简称表,是很多复杂数据结构实现基础,在Python中,list和tuple就可以看作是线性表的实现。 一、线性表的性质和ADT (一)几个基本概念1.线性表是一组有穷元素(元素可以是任何类型的数...

    TerryCai 评论0 收藏0
  • 数据结构 | 数组模拟实现顺序

    ...有相同特性的数据元素的有限序列,这是我们广泛使用的数据结构。 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。 ...

    OldPanda 评论0 收藏0
  • 数据结构 | 数组模拟实现顺序

    ...有相同特性的数据元素的有限序列,这是我们广泛使用的数据结构。 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。 ...

    tolerious 评论0 收藏0

发表评论

0条评论

阅读需要支付1元查看
<