数据结构之线性表
线性表学习笔记,python语言描述-2019-1-14
线性表简介
在程序中,经常需要将一组(通常是同为某个类型的)数据元素作为整体管理和使用,需要创建这种元素组,用变量记录它们,传进传出函数等。一组数据中包含的元素个数可能发生变化(可以增加或删除元素)。
对于这种需求,最简单的解决方案便是将这样一组元素看成一个序列,用元素在序列里的位置和顺序,表示实际应用中的某种有意义的信息,或者表示数据之间的某种关系。
这样的一组序列元素的组织形式,我们可以将其抽象为线性表。一个线性表是某类元素的一个集合,还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一,在实际程序中应用非常广泛,它还经常被用作更复杂的数据结构的实现基础。
根据线性表的实际存储方式,分为两种实现模型:
顺序表
,将元素顺序地存放在一块连续的存储区里,元素间的顺序关系由它们的存储顺序自然表示。链表
,将元素存放在通过链接构造起来的一系列存储块中。
顺序表
2.1、顺序表的基本形式
图a表示的是顺序表的基本形式,数据元素本身连续存储,每个元素所占的存储单元大小固定相同,元素的下标是其逻辑地址,而元素存储的物理地址(实际内存地址)可以通过存储区的起始地址Loc (e0)加上逻辑地址(第i个元素)与存储单元大小(c)的乘积计算而得,即:
Loc(ei) = Loc(e0) + c*i
故,访问指定元素时无需从头遍历,通过计算便可获得对应地址,其时间复杂度为O(1)。
如果元素的大小不统一,则须采用图b的元素外置的形式,将实际数据元素另行存储,而顺序表中各单元位置保存对应元素的地址信息(即链接)。由于每个链接所需的存储量相同,通过上述公式,可以计算出元素链接的存储位置,而后顺着链接找到实际存储的数据元素。注意,图b中的c不再是数据元素的大小,而是存储一个链接地址所需的存储量,这个量通常很小。
图b这样的顺序表也被称为对实际数据的索引,这是最简单的索引结构。
2.2、顺序表的基本实现
顺序表的基本实现方式:表中元素顺序存放在一片足够大的连续存储区里,首元素存入存储区的开始位置,其余元素依次顺序存放。元素之间的逻辑顺序关系通过元素在存储区的物理地址表示。
顺序表最常见的一种基本实现方式是一个表里保存的元素类型相同,因此存储每个表元素所需的存储量相同,可以在表里等距安排相同大小的存储位置。如下图,一个顺序表,存放的元素是整型的数据类型,整型在32位的操作系统中,一个整型数字占用内存的空间大小是4Byte,因此,内存中连续存放几个整型数字,每个存放元素的空间的地址值之间是等距。其中Li变量指向的通常是顺序表的表头元素的地址值,也就是0x23。
链表之单链表
线性表的定义,它是一些元素的序列,维持着元素之间的一种线性关系。实现线性表的基本需要是:
- 能够找到表中的首元素
- 从表中的任一元素出发,都能找到它的下一个元素
实现它除了连续存储的顺序表之外,链表也能做到。
链表是用链接关系显示表示元素之间的顺序关系,基本实现方式如下:
- 把表中的元素分别存储在一批独立的存储块里
- 保证从组成表结构中的任一结点可找到与其相关的下一个结点
- 在前一结点用链接的方式显示地记录与下一结点的关联。
单链表
单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。
- 表元素域elem用来存放具体的数据。
- 链接域next用来存放下一个节点的位置(python中的标识)
- 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点。
而表示一条链表的结束,只需要将最后一个结点的链接域设置为None。
节点的实现
一个链表的最基本组成是一个结点,一个结点的实现如下:
class SingleNode(object): """单链表的结点""" def __init__(self,item): # _item存放数据元素 self.item = item # _next是下一个节点的标识 self.next = None
单链表的操作
- is_empty() 链表是否为空
- length() 链表长度
- travel() 遍历整个链表
- add(item) 链表头部添加元素
- append(item) 链表尾部添加元素
- insert(pos, item) 指定位置添加元素
- remove(item) 删除节点
- search(item) 查找节点是否存在
python中单链表的实现
class SingleLinkList(object): """单链表""" def __init__(self): self._head = None def is_empty(self): """判断链表是否为空""" return self._head == None def length(self): """链表长度""" # cur初始时指向头节点 cur = self._head count = 0 # 尾节点指向None,当未到达尾部时 while cur != None: count += 1 # 将cur后移一个节点 cur = cur.next return count def travel(self): """遍历链表""" cur = self._head while cur != None: print cur.item, cur = cur.next print ""