数据结构-顺序表详解(含完整代码)

这篇具有很好参考价值的文章主要介绍了数据结构-顺序表详解(含完整代码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


数据结构-顺序表详解(含完整代码)

1.线性表的顺序存储结构

1.1定义

指用一段地址连续的存储单元依次存储线性表的数据元素。
数据结构-顺序表详解(含完整代码)
该图片来源于《大话数据结构》—作者程杰

1.2 数据长度和线性表长度的区别

数据长度: 是存放线性表的存储空间的长度,存储分配后这个量一般是不变的。
线性表长度: 线性表长度是线性表数据元素的个数,会随着插入和删除操作的进行,这个量也会发生改变。

1.3顺序存储的结构代码

#define MAXSIZE 20  /*存储空间初始分配量*/
typedef int ElemType;   /*ElemType的类型根据实际情况而定*/
//存储
typedef struct
{
	ElemType data[MAXSIZE];            /*数组存储数据元素,最大值为MAXSIZE*/
	int length;                        /*线性表当前长度*/
}SqList;

1.4顺序表中基本操作的实现

1.4.1自定义变量

为了方便读者对后续代码的理解,我将我自定义的一些变量放在该部分的开头

#define OK 1
#define ERROR 0
#define MAXSIZE 20  /*存储空间初始分配量*/
typedef int ElemType;   /*ElemType的类型根据实际情况而定*/
typedef int Status;

1.4.2 初始化

顺序表初始化操作就是构造一个空的顺序表。

代码如下:

//初始化操作

void InitList(SqList* L)
{
	int i = 0;
	for (i = 0;i < MAXSIZE;i++)
	{
		L->data[i] = 0;
	}
	L->length = 0;
}

1.4.3 查找

两种不同的查找

1.顺序表按数据值查找,返回位序:
【算法步骤】
①从第一个元素起,依次将其值和e相比较,若找到与e相等的元素L.elem[i],则查找成功,返回该元素序号i+1。
②若查遍整个顺序表都没有找到,则查找失败,返回0。

【算法描述】【伪代码】

//顺序表按数据值查找,返回位序
Status LocateElem(SqList L, ElemType e)
{//在顺序表中查找值为e的数据元素,返回其序号
	int i = 0;
	for (i = 0;i < L.length;i++)
	{
		if (L.data[i] == e)
			return i + 1;          //查找成功
	}
	return 0;                   //查找失败
}

【算法分析】
最好的情况:查找1次
最坏的情况:查找n次
平均情况:(1+n)/2次
时间复杂度为:O(n)

2.获得元素操作,顺序表按位序查找,返回数据值
【算法步骤】
①判断指定的位置序号i值是否合理(i>=1&&i<=L.length)以及顺序表是否可查找,若不合理,返回ERROR。
②获得合理位序的数据值,返回OK。

【算法描述】【伪代码】

//获得元素操作,顺序表按位序查找,获得数据值
Status GetElem(SqList L, int i, ElemType* e)
{
	if (L.length == 0 || i<1 || i>L.length)
	{
		return ERROR;
	}
	*e = L.data[i-1];
	return OK;
}

【算法分析】
时间复杂度为:O(1)

1.4.4 插入

【算法步骤】
①判断插入位置i是否合法(i>=1&&i<=L.length+1),若不合法返回ERROR。
②判断顺序表的存储空间是否已满,若满则返回ERROR。
③将第n个至第i个位置的元素依次向后移动一个位置,空出第i个位置(i=n+1时无需移动)。
④将要插入的新元素e放入第i个位置。
⑤表长加1。

【算法描述】【伪代码】

//插入操作
Status ListInsert(SqList* L, int i, ElemType e)
{
	int j;
	if (L->length == MAXSIZE)      /*顺序表已满*/
		return ERROR; 
	if (i<1 || i>L->length+1)
		return ERROR;              /*当i不在范围内*/
	if (i >= 1 && i <= L->length)   /*写这个条件便于理解*/
	{
		for (j = L->length - 1;j >= i - 1;j--)     
		{
			L->data[j + 1] = L->data[j];    /*将插入位置及之后的元素后移一位*/
		}
	}
	L->data[i - 1] = e;         /*将新元素插入*/
	L->length++;                /*表长加1*/
	return OK;
}

【算法分析】

当在顺序表中某个位置插入一个数据元素时,其主要时间耗在数据元素移动上,而移动元素的个数(n-i)取决于插入元素的位置。

最好的情况:插入到表尾,移动0次
最坏的情况:插入到表头,移动n次
平均情况:n/2次
时间复杂度:O(n)

1.4.5 删除

【算法步骤】
①判断删除位置是否合法(i>=1&&i<=n),若不合法则返回ERROR。
②将第i+1个至第n个元素依次向前移动一个位置(i=n时无需移动)
③表长减1

【算法描述】【伪代码】

//删除操作
Status ListDelete(SqList* L, int i, ElemType* e)
{
	int j;
	if (L->length == 0)
		return ERROR;      /*线性表为空*/
	if (i<1 || i>L->length)
		return ERROR;         /*删除位置不正确*/
	*e = L->data[i - 1];
	if (i >= 1 && i <= L->length)
	{
		for (j = i ;j < L->length;j++)
		{
			L->data[j - 1] = L->data[j];    /*将删除位置后继元素前移*/
		}
	}
	L->length--;        //线性表减1
	return OK;
}

【算法分析】

当要删除顺序表中某个位置的元素,其主要时间耗在数据元素的移动上,而移动的个数(n-i)取决于要删除的位置。

最好的情况:删除顺序表中最后一个元素,移动0次
最坏的请况:删除顺序表中第一个元素,移动n-1次
平均情况:移动(n-1)/2
时间复杂度:O(n)

1.4.6 打印

直接【伪代码】

//打印操作
void print(SqList L)
{
	int i = 0;
	for (i = 0;i < L.length;i++)
		printf("%d ", L.data[i]);
	printf("\n");
}

1.5完整代码实现(结合完整代码再看模块理解更快)

//顺序表的整体实现
#define OK 1
#define ERROR 0
#define MAXSIZE 20  /*存储空间初始分配量*/
typedef int ElemType;   /*ElemType的类型根据实际情况而定*/
typedef int Status;

//存储
typedef struct
{
	ElemType data[MAXSIZE];            /*数组存储数据元素,最大值为MAXSIZE*/
	int length;                        /*线性表当前长度*/
}SqList;

//初始化操作

void InitList(SqList* L)
{
	int i = 0;
	for (i = 0;i < MAXSIZE;i++)
	{
		L->data[i] = 0;
	}
	L->length = 0;
}


//顺序表按数据值查找,返回位序
Status LocateElem(SqList L, ElemType e)
{//在顺序表中查找值为e的数据元素,返回其序号
	int i = 0;
	for (i = 0;i < L.length;i++)
	{
		if (L.data[i] == e)
			return i + 1;          //查找成功
	}
	return 0;                   //查找失败
}

//获得元素操作,顺序表按位序查找,获得数据值
Status GetElem(SqList L, int i, ElemType* e)
{
	if (L.length == 0 || i<1 || i>L.length)
	{
		return ERROR;
	}
	*e = L.data[i-1];
	return OK;
}

//插入操作
Status ListInsert(SqList* L, int i, ElemType e)
{
	int j;
	if (L->length == MAXSIZE)      /*顺序表已满*/
		return ERROR; 
	if (i<1 || i>L->length+1)
		return ERROR;              /*当i不在范围内*/
	if (i >= 1 && i <= L->length)
	{
		for (j = L->length - 1;j >= i - 1;j--)     /*将要插入位置后数据元素向后移一位*/
		{
			L->data[j + 1] = L->data[j];
		}
	}
	L->data[i - 1] = e;         /*将新元素插入*/
	L->length++;                /*表长加1*/
	return OK;
}


//删除操作
Status ListDelete(SqList* L, int i, ElemType* e)
{
	int j;
	if (L->length == 0)
		return ERROR;      /*线性表为空*/
	if (i<1 || i>L->length)
		return ERROR;         /*删除位置不正确*/
	*e = L->data[i - 1];
	if (i >= 1 && i <= L->length)
	{
		for (j = i ;j < L->length;j++)
		{
			L->data[j - 1] = L->data[j];    /*将删除位置后继元素前移*/
		}
	}
	L->length--;        //线性表减1
	return OK;
}

//打印操作
void print(SqList L)
{
	int i = 0;
	for (i = 0;i < L.length;i++)
		printf("%d ", L.data[i]);
	printf("\n");
}

int main()
{
	SqList L;    //声明一些顺序表
	InitList(&L);
	//插入一些元素
	ListInsert(&L, 1, 2);
	ListInsert(&L, 1, 3);
	ListInsert(&L, 1, 4);
	print(L);
	int e = 0;      //将需要的元素带回
	if (ListDelete(&L, 3, &e))
		printf("已删除第3个元素,第三个元素为%d\n", e);
	else
		printf("位序不合法,删除失败\n");
	print(L);
	//按位查找
	if (GetElem(L, 2, &e))
	{
		printf("查找成功,第2个元素为%d\n", e);
	}
	else
	{
		printf("位序不合法,查找失败!\n");
	}
	//按值查找
	if (LocateElem(L, 1))
	{
		printf("查找成功,第2个元素为%d\n", LocateElem(L, 1));
	}
	else
	{
		printf("查找失败,该顺序表不存在该值!\n");
	}
	return 0;
}

数据结构-顺序表详解(含完整代码)

1.6顺序表的优缺点

1.6.1 优点

顺序表可以随机存取表中任意元素,其存储位置可用一个简单、直观的公式来表示。

1.6.2 缺点

在做插入和删除操作时,需要移动大量元素。另外数组有长度相对固定的静态特性,当表中元素个数较多且变化较大时,操作过程相对复杂,必然导致存储空间的浪费。
数据结构-顺序表详解(含完整代码)文章来源地址https://www.toymoban.com/news/detail-402453.html

到了这里,关于数据结构-顺序表详解(含完整代码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构之队列(顺序队和链队)(C语言附完整代码)

    队列简称队,它是一种 操作受限的线性表 ,其限制为仅允许在表的一端进行插入操作,而在表的另一端进行删除操作。把 进行插入的一端称为队尾 ,把 进行删除的一端称为队头或队首 。向队列中插入新元素称为 进队或入队 ,从队列中删除元素称为 出队或离队 。由于队列

    2024年02月06日
    浏览(43)
  • 『初阶数据结构 • C语言』⑧ - 动态顺序表详解(附完整源码)

    本章内容 写在前面 1.静态与动态是指什么? 2.动态顺序表结构的定义 3.动态顺序表的函数接口实现 4.动态顺序表的问题及思考 5.关于顺序表的OJ题 6.OJ答案及解析 1.移除元素 2.删除有序数组中的重复项 ​3.合并两个有序数组 7.动态顺序表完整源码 1.SeqList.h 2.SeqList.c     上一章

    2024年02月16日
    浏览(43)
  • 『初阶数据结构 • C语言』⑦ - 静态顺序表详解(附完整源码)

    本章内容 1.什么是线性表 2.什么是顺序表  3.静态顺序表结构的定义 4.静态顺序表的函数接口实现 5.静态顺序表的问题及思考     线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、

    2024年02月15日
    浏览(44)
  • 【数据结构】——线性表(顺序表加链表),万字解读(加链表oj详解)

    前言 由于之前存在过对两者的区别考虑,所以把他们放在一起来说,更加容易区别和理解 对于有关线性表的概念这里就不展示了,这里主要是介绍线性表里面的这两个结构的知识点 一.顺序表 1.顺序表介绍 顺序表的存储结构和逻辑结构都是相邻的, 这里如果我们把a1的地址

    2024年03月22日
    浏览(86)
  • 【数据结构】顺序表的实现及基本操作完整代码(C语言实现)

    顺序表:逻辑上相邻的数据元素,其物理次序也是相邻的 这里之所以要把int分别创建新名字为SqlElemType和Status,是因为实际应用时数据的类型不一定是int型,这样设置方便修改元素类型,提高代码适用性。 LocateElem的时间复杂度为O(n) InsertSq的时间复杂度为O(n) DeleteSq的时间

    2024年04月12日
    浏览(48)
  • 数据结构-线性表的顺序表基本操作代码实现(超级详细清晰 C++实现)

    顺序表是用一段 物理地址连续的存储单元 依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表: 可动态增长的数组,要求数据是连续存储的 特点: 随机访问 顺序既可以 静态分配 ,也可以 动态分配 。在静态分配时,由于数组

    2024年02月07日
    浏览(54)
  • 数据结构进阶篇 之 【二叉树顺序存储(堆)】的整体实现讲解(赋完整实现代码)

    做人要谦虚,多听听别人的意见,然后记录下来,看看谁对你有意见 3.1 向下调整算法 AdJustDown 3.2 向上调整算法 AdJustUP 3.3 堆的创建 3.3.1 向上建堆 3.3.2 向下建堆 3.3.3 堆的初始化与销毁 3.3.4 堆的插入(压栈) 3.3.5 取堆顶的数据 3.3.6 堆的删除 3.3.7 堆的数据个数 3.3.8 堆的判空

    2024年04月17日
    浏览(72)
  • 数据结构:线性表————顺序表的实现、项目和OJ题目(手把手教你写代码)

    🌈 个人主页: 小新_- 🎈个人座右铭:“成功者不是从不失败的人,而是从不放弃的人!”🎈 🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝 🏆所属专栏:  话说那些与C++的爱恨情仇   欢迎订阅,持续更新中~~~                                           ✨让小新带着你

    2024年04月16日
    浏览(100)
  • 【数据结构】顺序表的动态分配(步骤代码详解)

    🎈个人主页:豌豆射手^ 🎉欢迎 👍点赞✍评论⭐收藏 🤗收录专栏:数据结构 🤝希望本文对您有所裨益,如有不足之处,欢迎在评论区提出指正,让我们共同学习、交流进步! 在计算机科学中,数据结构是组织和存储数据的方式,它决定了数据如何被存储、检索和操作。

    2024年04月12日
    浏览(63)
  • 数据结构:线性表顺序存储结构———顺序表

    目录 顺序表的定义 初始化线性表 销毁线性表 求线性表的长度 判断是否为空表 插入数据元素 逻辑序号与物理序号的区别 删除数据元素 输出线性表  按序号求线性表中的元素 按元素值查找 整体上创建顺序表 顺序表实验 线性表的顺序存储是把线性表中的所有元素按照其逻辑

    2024年02月03日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包