数据结构线性表简介

本文主要是介绍数据结构线性表简介，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

.线性表
线性表：零个或者多个数据元素的有限序列。性质：数据元素可以为空数据元素有限数据元素之间的逻辑结构为线性结构，也就是一对一的关系数据元素类型相同举个例子：白羊 -> 金牛 -> 双子 -> 巨蟹 -> 狮子 -> 处女 -> 天秤 -> 射手 -> 摩羯 -> 水平 -> 双鱼线性表的抽象数据类型：ADT 线性表（List）Data 线性表的数据对象集合为{a1, a2, …, an}，每一个元素的类型都是DataType。其中，除第一个元素a1外，每一个元素有且仅有一个直接前驱元素，除了最后一个元素an外，每一个元素有且仅有一个直接后续元素。数据元素之间的关系是一对一的关系。Operation count：线性表元素个数。 first：头指针。 last：尾指针。 isEmpty()：若线性表为空，返回true，否则返回false。 remove()：将线性表清空 node(i)：将线性表中的第i个位置的元素返回。 insert(data,i)：在线性表中的第i个位置插入新数据data。EndADT线性表根据在计算机的储存方式可以分为两种：顺序线性表链式线性表顺序线性表顺序线性表：使用一段连续的地址存储单元放置线性表的数据元素。举个例子：数组。顺序线性表的优缺点：优点：- 可以快速获取下标的数据元素，时间复杂度为O(1)- 逻辑关系是一对一的关系，连续存储单元足以储存，不需要增加额外的存储空间缺点：- 插入和删除操作需要移动大量的元素，时间复杂度为O(n)- 线性表的存储空间大小难以确定，并且不好扩展- 造成存储空间碎片链式线性表链式线性表：线性表的数据元素可以存储在随意的存储单元，每一个节点不仅仅包括数据元素还有一个指向下一个节点的指针（基本的单链表）。链式（单链表）和顺序线性表优缺点对比：存储分配方式：- 顺序 -> 一段地址连续的存储空间- 链式 -> 任意地址存储空间时间性能：- 查找 顺序 -> O(1) 链式 -> O(n)- 插入和删除 顺序 -> O(n) 链式 -> 寻找相应的节点，时间复杂度为O(n)，然后，插入和删除为O(1)空间性能：- 顺序 -> 需要提前分配存储空间，分配大了，浪费空间，分配小了，容易发生上溢- 链式 -> 不需要提前分配空间，只要有存储空间分配就行，数据元素个数只受可分配存储空间大小的限制总结：（1）若线性表需要频繁查找，很少进行插入和删除操作时，使用顺序存储结构；反之，使用链式存储结构。（2）如果提前知道线性表需要的存储空间，可以使用顺序结构；如果不知道线性表中的数据元素变化有多大，即不确定需要多大的存储空间，则使用链式存储结构。链式线性表的基本分类：单向链表静态链表 -> 使用顺序结构实现链式线性表双向链表 -> 每个节点除了数据元素，还包含一个指向上一个节点的指针和一个指向下一个节点的指针循环链表

这篇关于数据结构线性表简介的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！