浏览量: 58 次浏览

数据结构之顺序表与链表

2020年1月19日 0 作者 Nie Hen

下面分别介绍 顺序表、链表 的结构与实现

顺序表

基本形式

enter description here
1. 如果元素的大小是一致的采用图a的形式,也是顺序表的基本形式
数据元素本身连续存储,每个元素所占的存储单元大小固定相同,元素的下标是其逻辑地址,而元素存储的物理地址(实际内存地址)可以通过存储区的起始地址Loc (e0)加上逻辑地址(第i个元素)与存储单元大小(c)的乘积计算而得
! Loc(ei) = Loc(e0) + c*i

故,访问指定元素时无需从头遍历,通过计算便可获得对应地址,其时间复杂度为O(1)。

  1. 如果元素的大小不一致,则须采用图b的元素外置的形式
    将实际数据元素另行存储,而顺序表中各单元位置保存对应元素的地址信息(即链接)。由于每个链接所需的存储量相同,通过上述公式,可以计算出元素链接的存储位置,而后顺着链接找到实际存储的数据元素。

注意,图b中的c不再是数据元素的大小,而是存储一个链接地址所需的存储量,这个量通常很小。

数据大小
  1. 1位(bit) = 1位二进制数
  2. 1字节(Byte) = 8位(bit)
  3. 1千字节(KB,Kilobyte)=1024字节(2的10次方字节)(1KB=1024B)
  4. 1兆字节(MB,Megabyte)=1024千字节(2的20次方字节)(1MB=1024KB)
  5. 1吉字节(GB,Gigabyte)=1024兆字节(2的30次方字节)(1GB=1024MB)
  6. 1千吉字节(TB,Terabyte)=1024吉字节(2的40次方字节)(1TB=1024GB)
      
    > 一个ASCII码就是一个字节
    一个英文字母(不分大小写)占一个字节的空间
    一个中文汉字占两个字节的空间  

c语言中
int 字节4 数值范围:-2147483648~+2147483647 有效数位 10
float 字节4 数值范围 -3.4×10^-38~3.4×10^38 有效数位 6~7
double 字节8 数值范围 -1.7×10^-308~1.7×10^308 有效数位 6~7

python 中
int从技术上讲具有有限的大小,但是如果计算结果超过该大小,Python将自动使用任意精度的long代替。这些仅受可用内存的限制。
float是IEEE 64位二进制浮点数。许多其他语言会称其为double。
double和char在Python中不存在。 Python只有一种内置的浮点数据类型,即float。单字符字符串用于表示字符。
  

结构与实现

enter description here

一个顺序表的完整信息包括两部分,一部分是表中的元素集合,另一部分是为实现正确操作而需记录的信息,即有关表的整体情况的信息。
这部分信息主要包括元素存储区的容量当前表中已有的元素个数两项。

顺序表的两种实现方式
enter description here
1. 图a为一体式结构,存储表信息的单元与元素存储区以连续的方式安排在一块存储区里,两部分数据的整体形成一个完整的顺序表对象。

一体式结构整体性强,易于管理。但是由于数据元素存储区域是表对象的一部分,顺序表创建后,元素存储区就固定了。

  1. 图b为分离式结构,表对象里只保存与整个表有关的信息(即容量和元素个数),实际数据元素存放在另一个独立的元素存储区里,通过链接与基本表对象关联。

分离式结构若想更换数据区,只需将表信息区中的数据区链接地址更新即可,而该顺序表对象不变

python中的顺序表

Python中的list和tuple两种类型采用了顺序表的实现技术

list就是一种采用分离式技术实现的动态顺序表。

list实现采用了如下的策略:
1. 在建立空表(或者很小的表)时,系统分配一块能容纳8个元素的存储区;
2. 在执行插入操作(insert或append)时,如果元素存储区满就换一块4倍大的存储区。
3. 如果此时的表已经很大(目前的阀值为50000),则改变策略,采用加一倍的方法。(引入这种改变策略的方式,是为了避免出现过多空闲的存储位置)

顺序表的不足

顺序表的构建需要预先知道数据大小来申请连续的存储空间,而在进行扩充时又需要进行数据的搬迁,所以使用起来并不是很灵活。

链表

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是不像顺序表一样连续存储数据,而是在每一个节点(数据存储单元)里存放下一个节点的位置信息(即地址)。

enter description here

单向链表

单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。

enter description here

  • 表元素域elem用来存放具体的数据。
  • 链接域next用来存放下一个节点的位置(python中的标识)
  • 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点。

单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点。

enter description here

双向链表

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空值。

enter description here

顺序表与链表的比较

链表失去了顺序表随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大,但对存储空间的使用要相对灵活。

链表与顺序表的各种操作复杂度如下所示:
enter description here

链表和顺序表在插入和删除时进行的是完全不同的操作。

  • 链表的主要耗时操作是遍历查找,删除和插入操作本身的复杂度是O(1)。
  • 顺序表查找很快,主要耗时的操作是拷贝覆盖。