线性链表存储结构
㈠ 数据结构线性表的单链表存储结构
线性表是一种数据元素有序的逻辑结构,通常采用顺序存储结构和链式存储结构。线性表采用顺序存储结构时,有利用线性表长度的计算、线性表数据元素的存取和数据元素的遍历,同时也从物理结构上反映了线性表数据元素的逻辑结构,有点类似于c语言中的数组,但是采用顺序存储结构时,插入和删除数据元素时,要移动较多的数据元素;采用链表结构存储的线性表,克服了插入和删除数据元素时要移动较多元素的缺点,其只要寻找到需要插入和删除的数据元素处,处理相应的指针就可以实现数据元素的插入和删除,同时也和顺序存储的线性表一样方便遍历,但是其不利于计算线性表的长度,线性表的链表存储结构有以下几种常见类型:采用带头指针和头结点的单链表、采用仅带头指针的单链表、带头指针和头结点的循环链表、带头指针和尾结点的循环链表、双向链表等形式。在实际应用中,结合顺序表易于计算表长和链表易于插入和删除的特点,实际一般采用两者结合的一种单链表,其链表类型为带有头指针(含头结点)和尾指针,以及含有线性表长度的分量,在一元多项式的运算中采用的就是这种链式存储结构。此外,还有一种一般应用于无指针的高级语言中的静态单链表的存储结构。
㈡ 线性表的存储结构
你好像把数据的逻辑结构与存储结构搞混淆了。
数据的逻辑结构包括线性结构、树、图、集合这四种,在线性结构里面又有线性表、栈、队列等等。
而数据的存储结构只有两种:顺序存储结构和链式存储结构,这两种存储结构,前面一个是利用数据元素在存储器中的相对位置表示其逻辑结构,另外一个是用指针来表示其逻辑关系。
结论:
线性结构的数据在存储结构方面,既可能是顺序存储,也可能是链式存储。
线性表是线性结构,也是顺序存储结构。
㈢ 线性表的顺序存储结构是一种什么
线性表的链式存储结构是一种顺序存储的存储结构。
线性表的链式存储结构中的每一个存储结点不仅含有一个数据元素,还包括指针,每一个指针指向一个与本结点有逻辑关系的结点,此类存储方式属于顺序存储;线性表是最基本、最简单、也是最常用的一种数据结构。线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。
简介
我们说“线性”和“非线性”,只在逻辑层次上讨论,而不考虑存储层次,所以双向链表和循环链表依旧是线性表。
在数据结构逻辑层次上细分,线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”,可以自由的删除或添加结点。受限线性表主要包括栈和队列,受限表示对结点的操作受限制。
㈣ 线性表的链式存储结构是什么样的存储结构
顺序存储结构的地址在内存中是连续的所以可以通过计算地址实现随机存取,而链式存储结构的存储地址不一定连续,只能通过第个结点的指针顺序存取;
所以选b,即只能按顺序存储
㈤ 线性表两种 存储结构各自的优缺点有哪些
线性表的链式存储结构:
优点:
插入和删除不需要移动插入时只需要对插入位置后的一个元素进行操作,不需要大量的移动元素。空间有效利用高。
缺点:
大量访问操作时不如顺序存储结构,因为每次都需要从头开始遍历整个线性表直到找到相应的元素为止。
线性表的顺序存储结构:
优点:
可随机存取表中任一元素。因为有下标可以操作可以快速的定位到指定位置的元素,但是不知道位置的话也需要顺序遍历。
缺点:
插入或删除操作时,需大量移动元素。合适在很少进行插入和删除运算的情况下。
(5)线性链表存储结构扩展阅读:
线性表的特征
集合中必存在唯一的一个“第一元素”。
集合中必存在唯一的一个 “最后元素” 。
除最后一个元素之外,均有唯一的后继(后件)。
除第一个元素之外,均有唯一的前驱(前件)。
线性表的基本操作
MakeEmpty(L) 这是一个将L变为空表的方法。
Length(L) 返回表L的长度,即表中元素个数。
Get(L,i) 这是一个函数,函数值为L中位置i处的元素(1≤i≤n)。
Prior(L,i) 取i的前驱元素。
Next(L,i) 取i的后继元素。
Locate(L,x) 这是一个函数,函数值为元素x在L中的位置。
Insert(L,i,x)在表L的位置i处插入元素x,将原占据位置i的元素及后面的元素都向后推一个位置。
Delete(L,p) 从表L中删除位置p处的元素。
IsEmpty(L) 如果表L为空表(长度为0)则返回true,否则返回false。
Clear(L)清除所有元素。
Init(L)同第一个,初始化线性表为空。
Traverse(L)遍历输出所有元素。
Find(L,x)查找并返回元素。
Update(L,x)修改元素。
Sort(L)对所有元素重新按给定的条件排序。
strstr(string1,string2)用于字符数组的求string1中出现string2的首地址。
参考资料来源:网络-线性表
㈥ 线性表链式存储结构的优点和缺点有什么
一、线性表链式存储结构的优点:
1、均匀性:虽然不同数据表的数据元素可以是各种各样的,但对于同一线性表的各数据元素必定具有相同的数据类型和长度。对于线性链表,可以从头指针开始,沿各结点的指针扫描到链表中的所有结点。
2、有序性:各数据元素在线性表中的位置只取决于它们的序号,数据元素之前的相对位置是线性的,即存在唯一的第一个和最后一个的数据元素,除了第一个和最后一个外,其它元素前面均只有一个数据元素(直接前驱)和后面均只有一个数据元素(直接后继)。
二、线性表链式存储结构的缺点:
线性表链式存储结构不要求逻辑上相邻的元素在物理位置上是相邻,因此,它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点。
(6)线性链表存储结构扩展阅读:
线性表链式存储结构的其他介绍:
一般在计算机的硬盘中,文件都是链式存储的。我们知道,多个扇区组成一个簇,簇是计算机存储数据的基本单位。
而一个文件是存储在多个在空间上也许并不相连的簇中的,这就是链式存储。但是为了能够读取出这个文件,计算机会在该文件第一部分的尾部写上第二部分所在的簇号。
另一部分的尾部又写上第三部分,以此类推,最后一部分写上一段代码,表示这是该文件的最后一部分。值得一提的是,高簇号在后。(如代码所示的1234实为簇3412)文件所占簇可认为是随机分配的。
㈦ 线性表存储结构有哪几种
线性表存储结构有2种,分别是顺序存储和链性存储结构。
数据元素之间的关系有两种不同的表示方法:顺序映象和非顺序映象,并由此得到两种不同的存储结构:顺序存储结构和链式存储结构。数据的存储结构是指数据的逻辑结构在计算机中的表示。
在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。
链接存储结构是在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。
顺序存储结构是存储结构类型中的一种,该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元中,结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构,通常顺序存储结构是借助于计算机程序设计语言(例如c/c++)的数组来描述的。
㈧ 线性表链式存储结构是什么
线性表是一种逻辑结构,它有两种存储方式,顺序存储和链式存储。
顺序存储对应的是顺序表,链式存储对应的有单链表,双链表,循环链表以及静态链表。
其中,线性表的链式存储又称为单链表。
注:双链表、循环链表等都是由单链表演化而来。
单链表:一个后继指针,一个头结点和头指针。每一个结点是存储下一个结点的存储位置,因此最后一个结点存储null,也就是空值。
双链表:双链表结点中有两个指针,prior和next,即有前驱指针和后继指针,分别指向前驱和后继结点。
循环链表:循环链表和单链表的区别在于最后一个结点的指针不是null(回到单链表的知识去看一下吧),而是指向头结点,从而整个链表成为了一个环。
循环双链表:循环双链表中头结点的指针prior指针还要指向表尾结点。
注:在循环双链表L中,当循环双链表为空表时,其头结点的prior域和next域都等于L。
静态链表:静态链表是借助数组来描述线性表的链式存储结构。结点有data域和指针域next。按照我的理解:其实静态链表和单链表在结构上差不太多,但是静态链表又和顺序表很像,可以把静态链表看作是单链表和顺序表的结合吧。
链式存储结构就这几种了。