家装企业网站系统下载,寿光网站制作,多用户商城系统哪个公司的好,网站开发服务内容原文出处:数据结构和算法之线性结构 关注码农爱刷题#xff0c;看更多技术文章#xff01;#xff01;#xff01; 线性结构是一种逻辑结构#xff0c;是我们编程开发工作应用最广泛的数据结构之一。线性结构是包含n个相同性质数据元素的有限序列。它的基本特征是看更多技术文章 线性结构是一种逻辑结构是我们编程开发工作应用最广泛的数据结构之一。线性结构是包含n个相同性质数据元素的有限序列。它的基本特征是在数据元素的非空有限集中 1存在唯一的“最后的元素”。 2存在唯一的“第一个元素”。 3除最后的元素之外其它数据元素均有唯一的“直接后继”。 4除第一个元素之外其它数据元素均有唯一的“直接前驱”。 在实际的应用中产生的典型线性结构有以下几种线性表、栈、队列。 1如果允许在序列任意位置进行操作这种线性结构称为线性表。 2如果只允许在序列末端进行操作这种线性结构称为栈。 3如果只允许在序列两端进行操作这种线性结构称为队列。 从三者的概念上可以看出栈和队列是线性表的特定场景实现。
一、线性表 线性表本质上还是一种抽象的逻辑概念是线性结构逻辑概念的细分。线性表根据存储结构实现方式不同可分为顺序表和链表。 1. 顺序表 顺序表是采用顺序存储结构实现的线性表一组地址连续的存储单元依次存放线性表的数据元素即以存储位置相邻表示位序相继的两个元素之间的前驱和后继关系从而使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表具有以下典型特征 数组符合顺序表的特征是典型的、具体的顺序表结构的应用和实现。数组继承了顺序表的特征会为存储的元素都分配一个下标索引此下标是一个自增连续的访问数组中的元素通过下标进行访问数组下标从0开始访问至数组长度-1结束。同时数组作为一种基础且常见的数据结构既频繁应用在各类算法之中也可用于实现各种复杂数据结构。数组访问元素的时间复杂度为O(1)增删元素的时间复杂度为O(n)。 在C和JAVA语言中数组大小是固定的保留了数组随机访问查询效率高的优点避免了插入删除低的劣势。顺序表和数组虽然查询效率高但是增删效率低下显然不能满足广泛使用的需求于是一种能快速在任意位置插入和删除元素的线性表链表应运而出。 2.链表 链表是采用链式存储结构实现的线性表和顺序表采用地址连续的存储单元不同链表是通过一组任意的存储单元来存储线性表中的数据元素具有以下特征 链表根据指针域指向不同可分为单向链表、双向链表和循环链表循环链表又分循环单向链表和循环双向链表具体定义如下 其中单向链表和数组一样是一种基础且常见的数据结构常用于实现其他复杂数据结构。它具备链表的基本特征插入和删除结点的时间复杂度为O(1)查找结点时间复杂度为O(n)寻找直接后继结点的时间复杂度为O(1)其他链表都是在单向链表基础上变化。
二、栈 正如前文所说栈是线性表的特殊实现仅能在线性表的一端操作栈顶允许操作栈底不允许操作。栈的特点是先进后出从栈顶放入元素的操作叫入栈压栈取出元素叫出栈弹栈 入栈操作如下图 出栈操作如下图 正如线性表可以采用顺序存储结构和链式存储结构实现栈作为线性表的特例自然也可以使用前述两种存储结构表示 使用顺序存储结构的栈称之为顺序栈或栈表使用链式存储的栈称之为链栈。 栈的入栈出栈操作时间复杂度为O(1)空间复杂栈的空间复杂度取决于栈中存储的数据量。如果栈中存储的数据量与输入数据的大小成正比那么空间复杂度为O(n)其中n为输入数据的大小。例如在实现深度优先搜索DFS算法时如果使用栈来保存搜索路径那么空间复杂度将与输入图的大小相关可能达到O(n)。然而如果栈的使用是固定的不随输入数据的大小变化那么空间复杂度为O(1)。例如在实现一些固定的数据结构操作时如简单的算术运算空间复杂度可以视为常数因为无论输入数据多大所需的空间是固定的。
三、队列 队列与栈一样也是一种线性表其限制是仅允许在表的一端进行插入而在表的另一端进行删除。队列的特点是先进先出从一端放入元素的操作称为入队取出元素为出队其操作如下图 队列根据存储结构表示不同也可以分为顺序队列和链式队列还有双端队列其中链式队列就是通过单向链表实现的双端队列可以通过双向链表实现。列入队和出队时间复杂度通常为O(1)空间复杂度为O(1)。 在具体的编程语言中大多是采用数组和链表取实现更复杂的数据结构。例如Java通过动态数组实现了ArrayList因为是用数组实现其存储结构就是顺序存储的因而具有顺序表的特征插入删除效率低查询元素效率高但又不完全等同顺序表因为它的空间是可以动态扩容的Stack类则是通过具有线程安全的动态数组Vector实现的具备栈先进后出的特征同时又具备线程安全性。LinkedList底层则是通过双向链表实现的具有链表插入删除元素效率高、结点查询效率低的特征。而Java的Queue实现方式有多种其中之一就是使用双向链表的实现LinkedList类来完成而Deque接口是Queue接口的一个扩展提供了在队列两端操作的方法Deque接口的实现类包括ArrayDeque和LinkedList因而LinkedList还可以用于双端队列的实现。 码农爱刷题
为计算机编程爱好者和从业人士提供技术总结和分享 为前行者蓄力为后来者探路
9篇原创内容
