常用的线性结构有线性表、栈、队列、循环队列、数组。线性表中包括顺序表、链表等,其中,栈和队列只是属于逻辑上的概念,实际中不存在,仅仅是一种思想,一种理念;线性表则是在内存中数据的一种组织、存储的方式。
(1)顺序表
顺序表将元素一个接一个地存入一组连续的存储单元中,在内存物理上是连续的,如图6.36所示。
图6.36 顺序存储
顺序表存储密度较大,节省空间;但需要事先确定容量,在时间性能方面,读运算较快,时间复杂度为O(1);查找运算为O(n/2),和链表一样;插入运算和删除运算如果要操作中间一个元素,比如3,那么就需要把3后面的元素全部进行移动,因此时间复杂度相对链表要大一些,插入时间复杂度最好为O(0)或最坏为O(n);删除时间复杂度为O[(n-1)/2]。
(2)链表
链表拥有很多节点,每个节点前半部分是数据域,后半部分是指针域,指针域指针指向下一个结点;链表可分为单链表、循环链表和双链表。
①单链表
单链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映像)﹢指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据,如图6.37所示。
图6.37 单链表存储(www.daowen.com)
如图6.37所示,单链表的上一个结点指针指向下一个结点,最后一个结点的指针域为null。
②循环链表
循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头节点,整个链表形成一个环,如图6.38所示。
图6.38 循环链表存储
如图6.38所示,循环链表与单链表唯一不同之处是,循环链表的最后一个结点指针不为空,而是指向头节点。节点的插入和删除和单链表非常相似,就不再示范了。
③双链表
双链链表也称双向表,是链表的一种,它的每个数据节点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表,如图6.39所示。
图6.39 双链表存储
如图6.39所示,双链表拥有一前一后两个指针域,从两个不同的方向把链表连接起来,如此一来,从两个不同的方向形成了两条链,因此成为双链表。因此,双链表的灵活度要大于单链表。
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。