欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构中的线性表(线性数据)

程序员文章站 2022-06-01 20:20:22
...

看了大话数据结构的线性表这一章,我同事在旁边弱弱的说了一句“这么基础的东西啊,看它干嘛。。。”
好吧承认我很弱。。。所以我要温故而知新。
大话数据结构其实很不错,将的非常的详细,及时对于这方面的知识你已经了解了,也不防看看。(至于原因吗,你打游戏也很无聊,不如看看有助于睡眠,而且睡觉前的记忆力很猛的,睡着后大脑活动率降低,你学习的知识不容易被覆盖,个人推测。。)
1。线性表的定义
线性表(Lsit):零个或多个数据元素的有限序列
首先它是一个序列,也就是说,元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最以后一个元素无后继,其他每个元素都有且一个前驱和后继。
2。线性表的顺序存储结构
线性表的顺序存储结构,指的是用一段地址连续的 存储单元依次存储线性表的数据元素。
说白了就是在内存中找了一块地方,通过占位的形式,吧一定内存空间给占了。然后把相同数据类型的元素依次存放在这个空地中。
如果我就占了5个地方,去了4个人 。这样剩余了一个空位。
如果我占了5个地方,去了6个人。这就装不下了。
所以顺序存储结构需要的三个属性:
(1)存储空间的起始位置:数组data 他的存储位置就是存储空间的存储位置。
(2)线性表的最大存储容量: 数组长度 MaxSize
(3)线性表的当前长度: length
优点
无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
可以快速的存取表中的任一位置的元素
缺点
插入和删除操作需要移动大量的元素
当线性表长度变化较大时,难以确定存储空间的容量。
造成存储空间的“碎片”
3。线性表的链式存储结构
顺序存储结构缺点是插入删除需要移动大量的元素,这显然非常耗时,所以链式存储就出现并解决这一难题。
线性表的链式存储结构的特点是用一组任意任意的存储单元存储线性表的数据元素。这租存储单元可以是连续的,也可以是不连续的。这就意味着,这些数据元素可以存在内存未被占用的任意位置。
以前的顺序结构中,每个元素只需要存储数据元素信息可以了,现在链式结构中,除了要存储数据元素信息外,还要存储它的后继元素的存储地址。
单链表结构 与 顺序储存结构优缺点
简单的对单链表结构和顺序存储结构做对比
1。存储分配方式
(1)顺序存储结构用一段连续存储单位一次存储线性表的数据元素
(2)单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素
2。时间性能
(1)查找
顺序存储结构 O(1)
单链表 O(n)
(2)插入和删除
顺序存储计日工需要平均一定表长度的一半元素 时间O(n)
单链表在线出某位置的指针后。插入删除时间仅为 O(1)
(3)空间性能
顺序存储结构需要预分配存储空间,分大了,浪费,分小了容易发生上溢
单链表不需要分配存储空间,只要有就可分配,元素个数也不受限制
通过上面的对比,可以得出一些结论
1.若线性包需要频繁的查找,很少进行插入和删除操作时,宜采用顺序存储结构
若需要频繁的插入和删除,宜采用单链表结构。
2.当线性表中的元素个数变化较大或根本就不知道有多大时,最好用单链表结构,这样可以不需要考虑储存空间大小的问题。而如果事先知道线性表的大致长度,这种用顺序存储结构效率会高很多。
4。循环链表
循环表与单链表的差别在于循环的判断条件上。循环表把最后一个元素的指针放到了第一个元素里。
合并两个循环表,A B ,A表的最后元素指定针指向B表单的第一个元素,B表的最后一个元素的指针指向A表的第一个元素上。
5。双向链表
是在单链表的每个节点中,在设置一个指向前驱的指针域。所以在双向链表中的节点都有两个指针域,一个指向直接后续,一个指向直接前驱。
插入操作是个比较容易弄混的地方。A元素 C元素 将B元素插入到他们中间
先将A元素赋值给 B的前驱。
再将C元素赋值给B的后继。
在将B元素赋值个C的前驱。
在将B元素赋值给A的后继。
删除简单了 删除B元素
将A元素赋值给C元素的前驱。
将C元素赋值给A元素的后继。


线性表

线性表     
顺序存储结构
链式存储结构:     单链表       静态链表       循环链表      双向链表