阅读裘宗燕老师的《数据结构与算法:python语言描述》的课件所记笔记

一、计算机内存结构

1.内存结构模型

  • 内存是线性排列的一批存储单元,单元有唯一编号,称为单元地址
  • 单元地址从0开始连续排列,可用地址是一个连续整数区
  • 对内存单元的访问都是通过单元地址进行
  • 基于地址访问单元是O(1)操作,与单元位置或内存大小无关

2.内存和对象存储

  • 程序运行中建立/存在的每个对象都要占用一块内存
    • 建立的每个对象都有唯一标识,在其存续期间保持不变,这是一个基本原则
    • 知道一个对象的位置就能访问它,访问操作在常量时间完成
  • 如果一个组合对象包含一组元素,在一块存储区连续存储,每个元素的存储量相同,基于存储区位置和编号访问元素是O(1)操作
    • 设存储区起始位置是p,每个元素占用a个内存单元,若第一个元素编号为0
    • 要访问编号为k的元素,其位置为
      $$loc = p + k*a$$
    • 计算元素位置所用时间与元素编号无关,也与组合对象的元素个数无关,连续存储可以O(1)时间访问

3.变量和对象

  • 变量也在内存安排位置,每个变量占用若干存储单元
  • 程序运行中总能找到根据作用域可见的那些变量,取得或修改其值
  • python里通过初始化给变量约束一个值(对象),就是把该对象的标识(内存位置)保存在变量里

4.表示及其设计

  • 假设要给变量s赋值一个字符串,系统需要:
    • 找一块足够大的内存快,把字符串的内容复制进去
    • 把内存地址信息存入变量s
  • 上述做法有所欠缺
    • 内存单元里存储的都是二进制编码,仅从单元里存储的内容无法判断这一字符串到哪里结束
    • 需要有一种安排(约定)。由于字符串可以有任意长度,一种可能安排是在相应存储块的开始记录字符串长度
  • 程序中生成和处理的对象都要以某种方式保存,因此要设计好它们的存储方式,这种方式及其效果称为该对象的'表示'
  • python系统的实现基于一套精心设计的链接结构

二、线性表

  • 程序里经常需要将一组元素作为整体管理和使用
    • 元素个数可能变化
    • 可能需要把这样一组元素看成一个序列,元素在序列里的位置和顺序可能表示实际应用中某种意义的信息或关系
    • 这样一组元素的抽象就是线性表(简称表)。
    • 线性表是一种元素集合,其中记录着元素间的一种顺序关系

1.概念和术语

  • 抽象讨论线性表时,考虑一个基本元素集合E={$e0,...,e{N-1}$},其中的元素可能是某个类型的成员
  • 表是元素的有穷序列,有0个或多个元素
    • 元素的位置称为其下标,下标从0开始编号
    • 表中元素的个数称为表的长度,长度为0的表是空表
    • 元素间基本关系是下一个关系:$<e_0,e_1>,<e_1,e2>,...,<e{n-2},e_{n-1}>$,这是一种顺序关系(线性关系)
  • 线性表是一种线性结构。在一个非空线性表里:
    • 存在唯一的‘首元素’,唯一的‘尾元素’
    • 除首元素外,表中每个元素有且只有一个前驱元素
    • 除尾元素外,表中每个元素有且只有一个后驱元素
  • 从实际角度看,线性表是一种组织数据元素的结果。作为一种抽象的数据结构,需要从两个角度考虑
    • 从实现角度需要考虑两个问题:
      • 如何把该结构内部的数据组织好
      • 如何提供一套有用而且必要的操作,并有效实现这些操作
    • 从使用者角度,需要考虑该结构提供了哪些操作,如何有效使用以解决自己的问题。
  • 上述两种角度既有统一又有分工。情况与函数的定义与使用类似
    • 数据结构的表示完全是内部的东西,外面看不到。但它会对这一数据结构上各种操作的实现和性质产生重要影响
    • 对复杂的数据结构,由于存在多种可能表示,设计时需要考虑的因素很多

2.数据结构的操作

  • 作为一种包含元素的数据结构,需要提供一些“标准”操作
    • 创建和销毁
    • 判断是否空。如果容量有限,还需判断是否满
    • 向结构中加入元素或从中删除
    • 访问结构里的元素
  • 不同的编程语言可能影响需要实现的操作
    • 由于python能自动回收不用的对象,因此不需要销毁结构的操作
  • 除上述共性操作外,具体数据结构还需要一些特殊操作
    • 集合数据结构需要支持各种集合运算(求并集,交集等)
    • 图数据结构要提供判断结点是否相邻的操作(两点间是否有边)
  • 从作用看,数据结构的操作分为三类:
    • 构造操作
    • 访问操作
    • 变动操作
  • 从支持操作类型的角度看,数据结构可分为两类:
    • 不变数据结构,如python中的tuple和frozenset
    • 变动数据结构,如python中的list,dict,set

3.线性表的操作

  • 假设为表数据结构取一个类型名List。为简洁严格地表示操作的对象和结果,下面介绍一种数学表达形式:
    opname:T1 T2 -> ResT
    其中opname表示操作名,T1
    T2表示有两个参数,类型分别为T1和T2,ResT表示操作的结果类型。
    用()表示没有参数或者操作不返回任何结果
a.创建和销毁,判断空和满
newList:   () -> List           # 创建一个空表
deList:    () -> ()             # 销毁表
emptyList: List -> bool         # 表空?
fullList:  List -> bool         # 表满?
b.元素加入
prepend:  List * Data -> List         # 首端加入
append:   List * Data -> List         # 尾端加入
insert:   List * int * Data -> List   # 定位加入,加入表中特定位置,原处及其后面的元素后移
c.删除元素
delFront:   List -> List            # 删除首元素
delEnd:     List -> List            # 删除末元素
delete:     List * int -> List      # 定位删除
delElem:    List * Data -> List     # 删除一个Data
delAllElem: List * Data -> List     # 删除所有Data
d.访问元素
getElem: List * int -> Data
e.其它操作
length:   List -> integer           # 表中元素个数
locate:   List * Data -> integer    # 元素在表中第一次出现的位置,没有返回特殊值
sortList: List -> List              # 按上升序重新排列
  • 表内容变化的操作有两种考虑
    • 总构造一个新表作为操作的结果。语义清晰,适合不变的表
    • 按操作的需要直接修改作为参数的表。效率可能更高

4.表数据结构实现模型

  • 考虑因素
    • 计算机内存的特点,保存元素和元素顺序信息的需要
    • 重要操作的效率。最频繁的操作通常是:定位访问,元素加入,元素删除,元素遍历
  • 元素遍历就是依次访问表里的所有元素
    • 操作效率与元素个数有关
    • 遍历所有元素的操作,希望其复杂性不超过O(n)
  • 加入、删除、访问元素的操作效率与表的实现结构有关
  • 两种基本实现模型
    • 顺序表,将表元素顺序存放在一大块连续的存储区,元素顺序有自然的表示
    • 链接表,将表元素存放在通过链接构造起来的一系列存储块里

三、顺序表模型

  • 基本实现方式
    • 元素顺序存放在一块足够大的连续存储区。表中首元素存入存储区开始位置,其余元素依次顺序存放
    • 通过元素在存储区的‘物理位置’表示元素之间的逻辑顺序关系
  • 一般情况是表元素所需存储量相同,因此顺序表中任一元素的位置都可简单计算出来,存取操作在O(1)时间内完成
  • 若元素的情况复杂,大小不一,或者还有复杂的内部结构,可以采用链接方式

1.顺序表

  • 表的一个重要性质即加入和删除元素,决定表的长度在存续期间可能变化
    • 存储块一旦分配,大小固定
    • 建立时按确定元素个数分配存储,适合创建不变表。要考虑变动的表,应区分元素个数和存储区容量
  • 解决方法:分配足以容纳所需元素的存储块,可以有一些空位
    • 应约定元素的存放方式,通常连续存放在存储区的前面一段
    • 为保证正确操作,需要记录块大小和现有元素个数

2.实现和操作

  • 元素存储区的大小决定了表的容量,个数记录与实际元素个数保持一致,元素变化时需要维护这一记录
  • 访问第i个元素时通过计算位置直接找到。复杂性O(1)
  • 判断空满只需对比元素个数记录是否等于容量个数,复杂性O(1)
  • 创建空表是分配一块存储,记录容量并设置元素计数为0。建立新表后应立即设置这两个记录域,保证合法状态
  • 只要掌握着元素存储区开始位置,各种访问操作都很容易实现
  • 遍历操作:
    • 遍历过程用一个整数变量记录遍历达到的位置
    • 通过存储区开始位置和上述变量的值,O(1)时间可算出相应元素的位置
    • 找下一元素的更新操作就是加一,前一元素就是减一
  • 访问给定下标i的元素
    • 需判断i值是否在表当时的合法元素范围内
    • 不在范围内是非法访问,合法时从给定位置取得元素的值
  • 查找给定元素d的位置(第一次出现),通常循环,将d与表里的元素逐个比较,找到返回元素下标,否则返回一个特殊值
  • 尾端加入与删除都是O(1)操作
    • 加入需先判断表是否满,将新数据存入,同时元素计数加一
    • 删除只需把元素计数减一
  • 首端加入与定位删除需要移动元素,比较复杂,需要O(n)操作
a.实现
  • 模型应包括两部分内容
    • 一个元素存储区,存放表中的实际元素
    • 若干单元,存放一个表的全局信息(容量,表元素个数)
  • 一个数据结构应该具有一个对象的整体形态。对顺序表,就是把上述两块信息组织关联起来
  • 一块存储连续存放这两部分信息称为一体式实现;用两块存储区,通过链接关联,称为分离式实现

3.python的list

  • list是一种线性结构,可看作线性表的一种实现
    • 基于下标(位置)的元素访问和更新操作,复杂性为O(1)
    • 允许任意加入元素,而且维持表对象标识不变(id())
  • list实现约束和解决方案
    • 要求O(1)的元素访问并维持元素的顺序,只能采用连续表技术,元素保存在一块连续存储区
    • 要能容纳任意多个元素,必须在元素个数将要超出存储区容量时换一块更大的存储区。要想在替换存储时id不变,只能采用分离式实现
  • list里元素越多,换一次存储区的代价也越高
    • 要想平均结果较好,随着表长度增加,换存储区的频率应降低
    • 一种可能做法:每次换存储区,容量加倍
  • 一次高开销操作后,保证有很多次低开销操作,称为分期付款式的常量复杂性
  • python中list采用上述设计,因此lst.insert(len(lst), x)比一般位置加入的效率高,等价写法lst.append(x),如何使,应优先使用
a.list的操作
  • 实际实现策略
    • 建立空list时分配可以容纳8个元素的存储区
    • 元素区满时换一块4倍大的存储区;但在表已经比较大时就会改变策略,加倍换存储区的规模
    • 效果:尾端加入平均复杂性为O(1)
  • 其它操作的性质由连续表的实现方式确定
    • 所有序列的共性操作,复杂性由操作中需要考察的元素个数确定,其中len()是O(1)操作
    • 元素访问和赋值,尾端加入和尾端(切片)删除是O(1)操作
    • 一般元素加入,切片替换,切片删除,表拼接(extend)等都是O(1)操作。pop操作默认情况是尾端删除返回,为O(1)。
  • 特殊操作
    • list仅有的特殊方法是sort,对表中元素进行排序。最好的排序算法复杂性是O(nlogn)
    • lst.reverse()修改lst,将其元素倒置。如下实现,假设元素存储区的域名为elements,复杂性O(n)
      def reverse(self):
      e = self.elements
      i = 0, j = len(e)-1
      for i < j:
      e[i], e[j] = e[j], e[i]
      i, j = i+1, j-1

思考

  • 1.数据结构是一种结合数据在内存中的存储方式(连续存储或分散存储)与实际应用的抽象化数据组织方式
  • 2.下标有时等效于数据在内存中的位置,即存储地址。访问数据只能通过存储地址访问
  • 3.数据通过预先组织形成一种关联性,然后存入内存,该关联性体现在从内存中取出数据
最后由 oucb 编辑于2016年05月03日 16:53