资讯专栏INFORMATION COLUMN

数据结构学习笔记--顺序表

haoguo / 1016人阅读

摘要:优点实现方便,只需要会用数组就能够写出简单的静态顺序表。缺点相较于顺序表更难实现,有一定的使用门槛。顺序表实现顺序表结构静态顺序表结构由于静态顺序表不是本篇文章的主要内容所以只是稍微提及一下结构。

1.顺序表概念

顺序表是用以一段物理地址连续的存储单眼依次存储数据元素的线性结构,一般情况采用数组存储。在数组上完成数据的增删查改。顺序表一般分为静态顺序表和动态顺序表,这里主要讲如何实现动态顺序表。


2.顺序表分类

顺序表一般可以分为:静态顺序表动态顺序表

2.1静态顺序表

静态顺序表:通过定长的数组存储。

优点:实现方便,只需要会用数组就能够写出简单的静态顺序表。

缺点:不够灵活,开辟的数组如果过大荣以浪费大量的空间,而开辟的数组过小也容易导致数据不够存放,适用于能预先知道所需空间,而且不用对内容频繁改动的情况(但实际上从实现角度来看,其实动态通讯录也没有麻烦太多,所以一般都是使用动态顺序表)

2.2动态顺序表

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

优点:泛用性好,能够适用于各种不同的环境,并且能根据所需存储内容多少,动态的分配空间,更加的灵活,且不容易存在空间浪费的情况,一般都是需要多少空间就能那多少空间用。

缺点:相较于顺序表更难实现,有一定的使用门槛。


3.顺序表实现

3.1顺序表结构

3.1.1静态顺序表结构

由于静态顺序表不是本篇文章的主要内容所以只是稍微提及一下结构。

#typedef SLDataType int#define N 10typedef struct SeqList{    SLDataType arr[N];    int size;}SeqList;

SeqList顺序表的英文缩写,本文提到的所有SeqList均为顺序表的意思

SLData Type顺序表中要存放的数据类型,只需要改动typedef int SLDataType后面的内容就能改变所需要存放的数据类型,这里假定我们需要存放的是int类型的数据

N所开辟数组大小

arr[N] 为顺序表开辟的数组空间

size顺序表已经使用的空间长度

3.2动态顺序表结构

typedef int SLDataType    typedef struct SeqList{	SLData Type* a;	int size;	int capacity;}SeqList;

SeqList顺序表的英文缩写,本文提到的所有SeqList均为顺序表的意思

SLData Type顺序表中要存放的数据类型,只需要改动 typedef int SLDataType 后面的内容就能改变所需要存放的数据类型,这里假定我们需要存放的是int类型的数据

size已用空间的大小

capacity剩余空间的大小

3.3动态顺序表功能实现

文件:"SeqList.c"

3.3.1顺序表初始化

void SeqListInit(SeqList* ps)					//顺序表初始化{	assert(ps);	ps->a = NULL;	//初始指针指空	ps->size = 0;	//初始已用容量为零	ps->capacity = 0;	//初始可用容量为零}

3.3.2顺序表空间检查

void CheckSeqList(SeqList* ps){		assert(ps);	int new_capacity = ps->capacity;	SLDataType* new_a = NULL;	//开辟两个临时变量以防止开辟失败影响原空间内容	if (ps->size == ps->capacity)    //如果已用空间与可用空间相等就开辟空间	{		(new_capacity == 0) ? (new_capacity = 4) : (new_capacity = 2 * new_capacity);		//当首次开辟直接开辟四个空间,否则开辟原空间的两倍		new_a = (SLDataType*)realloc(ps->a, new_capacity * sizeof(SLDataType));		//开辟原来空间的两倍		if (new_a == NULL)		{			printf("开辟空间失败");			exit(-1);		}		//new_a是空指针表示开辟失败		else		{			ps->capacity = new_capacity;			ps->a = new_a;		}        //开辟成功将空间和空间长度给SeqList	}	}

3.3.3顺序表销毁

void SeqListDestory(SeqList* ps)				//顺序表销毁{	assert(ps);	free(ps->a);	//释放开辟的空间	ps->a = NULL;	//指针指空	ps->size = 0;	//已用空间置零	ps->capacity = 0;	//可用空间置零}

3.3.4打印顺序表

void SeqListPrint(SeqList* ps)                 //顺序表打印{	assert(ps);	for (int i = 0; i < ps->size; i++)	{		printf("%d ", ps->a[i]);	}	printf("/n");	//将顺序表的内容依次打印}

3.3.5顺序表头部插入数据

void SeqListPushFront(SeqList* ps, SLDataType x)		//顺序表头插{	assert(ps);	CheckSeqList(ps);	//检查顺序表是否已满	for (int i = ps->size -1 ; i >=0 ; i--)	{		ps->a[i+1] = ps->a[i];	}    //从后到前一次往后放一位	ps->a[0] = x;	//第一位为插入内容	ps->size++;	//已用空间+1}

3.3.6顺序表尾部插入数据

void SeqListPushBack(SeqList* ps, SLDataType x)			//顺序表尾插{	assert(ps);	CheckSeqList(ps);    //检查顺序表是否已满	ps->a[ps->size] = x;	//在顺序表最后放入x	ps->size++;	//顺序表已用空间+1}

3.3.7顺序表头部删除数据

void SeqListPopFront(SeqList* ps)					//顺序表头删{	assert(ps);	for (int i = 0; i < ps->size -1; i++)	{		ps->a[i] = ps->a[i + 1];	}	//将顺序表依次往前移	ps->size--;	//顺序表可用空间-1}

3.3.8顺序表尾部删除数据

void SeqListPopBack(SeqList* ps)					//顺序表尾删{	assert(ps);	ps->size--;	//顺序表可用空间-1}

3.3.9顺序表按值查找

int SeqListFind(const SeqList* ps, SLDataType x)			//顺序表按值查找{	assert(ps);	for (int i = 0; i < ps->size; i++)	{		if (ps->a[i] == x)		{			return i;											//依次与x匹配,找到返回所在位置		}	}	return -1;											//找不到返回-1}

3.3.10顺序表按位插入

void SeqListInsert(SeqList* ps, int pos, SLDataType x)       //顺序表位插{	assert(ps);	CheckSeqList(ps);	//检查顺序表是否已满	if (pos > ps->size)	{		printf("超出可检测范围");		exit(-1);	}	//要插入位置是否为合格	for (int i = ps->size - 1; i >= pos - 1; i--)	{		ps->a[i + 1] = ps->a[i];	}	//从后到前依次往后移一位	ps->a[pos - 1] = x;	//第pos-1位为插入内容	ps->size++;	//已用空间+1}

3.3.11顺序表按位删除

void SeqListErase(SeqList* ps, int pos)		//顺序表位删	{	assert(ps);	if (pos > ps->size)	{		printf("超出可检测范围");		exit(-1);	}	//要删除位置是否为合格为止	for (int i = pos - 1; i < ps->size - 1; i++)	{		ps->a[i] = ps->a[i+1];	}	//从前向后依次往前移一位	ps->size--;	//已用空间-1}

3.4顺序表头文件

文件:"SeqList.h"

#pragma once                                           //防止重复定义typedef int SLDataType;                                #include#include#include                                     //头文件,其他文件只用包含该文件typedef struct SeqList                                 //顺序表结构{	SLDataType *a;	int size;	int capacity;}SeqList;void SeqListInit(SeqList* ps);							//顺序表初始	void SeqListDestory(SeqList* ps);						//顺序表销毁	void SeqListPrint(SeqList* ps);							//顺序表打印	void SeqListPushFront(SeqList* ps, SLDataType x);		//顺序表头插	void SeqListPushBack(SeqList* ps, SLDataType x);		//顺序表尾插	void SeqListPopFront(SeqList* ps);						//顺序表头删	void SeqListPopBack(SeqList* ps);						//顺序表头删void SeqListInsert(SeqList* ps, int pos, SLDataType x); //顺序表位插	void SeqListErase(SeqList* ps, int pos);				//顺序表位删	void CheckSeqList(SeqList* ps);							//检查表容量	int SeqListFind(const SeqList* ps, SLDataType x);		//顺序表查找	

3.5顺序表功能测试

文件:"test.c"

#include"SeqList.h"int main(){	SeqList seqlist;	SeqListInit(&seqlist);						//初始化顺序表--通过	SeqListPushFront(&seqlist, 3);			SeqListPushFront(&seqlist, 2);	SeqListPushFront(&seqlist, 1);	SeqListPushFront(&seqlist, 0);	SeqListPrint(&seqlist);						//头插测试--通过	SeqListPushBack(&seqlist, 4);	SeqListPushBack(&seqlist, 5);	SeqListPushBack(&seqlist, 6);	SeqListPushBack(&seqlist, 7);	SeqListPrint(&seqlist);						//尾插测试--通过	SeqListPopFront(&seqlist);	SeqListPopFront(&seqlist);	SeqListPrint(&seqlist);						//头删测试--通过	SeqListPopBack(&seqlist);	SeqListPopBack(&seqlist);	SeqListPrint(&seqlist);						//尾插测试--通过	printf("%d ", SeqListFind(&seqlist, 1));	printf("%d /n", SeqListFind(&seqlist, 4));		SeqListPrint(&seqlist);						//查找测试--通过	SeqListInsert(&seqlist, 3, 0);	SeqListInsert(&seqlist, 5, 0);						SeqListPrint(&seqlist);						//位插测试--通过			SeqListErase(&seqlist, 3);	SeqListErase(&seqlist, 4);	SeqListPrint(&seqlist);						//位删测试--通过			SeqListDestory(&seqlist);					//销毁顺序表--通过	return 0;}

✨写在最后

⏱笔记时间:2021_09_25

?代码:Gitee:朱雯睿 (zhu-wenrui) - Gitee.com

               Github:https://github.com/Zero0Tw0

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

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

相关文章

  • [学习笔记-Java集合-5]Map - LinkedHashMap源码分析

    摘要:源码解析属性双向链表头节点双向链表尾节点是否按访问顺序排序双向链表的头节点,旧数据存在头节点。双向链表的尾节点,新数据存在尾节点。内部类位于中位于中存储节点,继承自的类,用于单链表存储于桶中,和用于双向链表存储所有元素。 简介 LinkedHashMap内部维护了一个双向链表,能保证元素按插入的顺序访问,也能以访问顺序访问,可以用来实现LRU缓存策略。 LinkedHashMap可以看...

    Lowky 评论0 收藏0
  • LRU算法 :学习笔记

    摘要:算法学习笔记是什么即最近最少使用,是一种缓存算法页面置换算法。理想的算法读写是时间复杂度应该都为。通过查找对应的节点,将其移动至头部并返回。 LRU算法 :学习笔记 LRU是什么 LRU(Least Recently Used)即最近最少使用,是一种缓存算法(页面置换算法)。我们知道,缓存通常是具有固定大小的,他应该只保存那些常常被用到的数据,而数据如何更新则是通过缓存算法实现,LRU...

    Sanchi 评论0 收藏0
  • MySQL学习笔记

    摘要:学习要点数据库设计规范数据库命名规范名称必须使用小写字母并用下划线分隔数据库名表名字段名名称禁止使用的保留关键字关键字使用来代表不是关键名称要见名知意,长度推荐不超过个字符内临时表必须以为前缀并且以日期为后缀备份表必须以为前缀并且以日期为后 MySQL 学习要点 showImg(https://segmentfault.com/img/bVPlN0?w=725&h=497); 数据库设...

    kgbook 评论0 收藏0
  • MySQL学习笔记之索引

    摘要:哈希索引哈希索引基于哈希索引实现,只有精确匹配所有所有列的查询才有效。哈希索引只支持等值比较查询。如果哈希冲突很多的话,一些索引维护代价也会很高。因为这些限制哈希索引只适用于某些特定的场合。建立聚簇索引的方式对主键建立聚簇索引。 索引是存储引擎用于快速找到记录的一种数据结构。 索引对于良好的性能非常关键。尤其是当表中的数据量越来越大时,索引对性能的影响愈发重要。在数据量较小且负载较低时...

    fou7 评论0 收藏0
  • CSS学习笔记(四) CSS优先级

    摘要:为了解决冲突,确定哪条规则胜出并最终被应用,提供了三种机制继承层叠和特指。整个检查更新过程结束后,再将每个标签以最终设定的样式显示出来。层叠规则四顺序决定权重。规则三设定的样式胜过继承的样式,此时不用考虑特指度即显式设定优先。 为了解决冲突,确定哪条规则胜出并最终被应用,CSS提供了三种机制:继承、层叠和特指。 1.继承 CSS 中的祖先元素会向后代传递一样东西:CSS属性...

    高胜山 评论0 收藏0

发表评论

0条评论

haoguo

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<