黑马程序员技术交流社区

标题: 【郑州校区】 python数据结构与算法（6） [打印本页]

---

作者: 谷粒姐姐    时间: 2018-11-28 09:57
标题: 【郑州校区】 python数据结构与算法（6）
Python中的顺序表
Python中的list和tuple两种类型采⽤了顺序表的实现技术，具有前⾯讨论的顺 序表的所有性质。
tuple是不可变类型，即不变的顺序表，因此不⽀持改变其内部状态的任何操 作，⽽其他⽅⾯，则与list的性质类似。
list的基本实现技术
Python标准类型list就是⼀种元素个数可变的线性表，可以加⼊和删除元素， 并在各种操作中维持已有元素的顺序（即保序），⽽且还具有以下⾏为特 征：
基于下标（位置）的⾼效元素访问和更新，时间复杂度应该是O(1)；
为满⾜该特征，应该采⽤顺序表技术，表中元素保存在⼀块连续的存储 区中。
允许任意加⼊元素，⽽且在不断加⼊元素的过程中，表对象的标识（函 数id得到的值）不变。
为满⾜该特征，就必须能更换元素存储区，并且为保证更换存储区时list 对象的标识id不变，只能采⽤分离式实现技术。
在Python的官⽅实现中，list就是⼀种采⽤分离式技术实现的动态顺序表。这 就是为什么⽤list.append(x)        （或        list.insert(len(list),        x)，即尾部插⼊）⽐在指 定位置插⼊元素效率⾼的原因。
在Python的官⽅实现中，list实现采⽤了如下的策略：
       

[AppleScript] 纯文本查看 复制代码

/*        This        over-allocates        proportional        to        the        list        size,        mak ing        room                                        *        for        additional        growth.                The        over-allocation        is        mild,        b ut        is                                        *        enough        to        give        linear-time        amortized        behavior        over        a        l ong                                        *        sequence        of        appends()        in        the        presence        of        a        poorly-perf orming                                        *        system        realloc().                                        *        The        growth        pattern        is:                0,        4,        8,        16,        25,        35,        46,        58,        7 2,        88,        ...                                        */                                new_allocated        =        (newsize        >>        3)        +        (newsize        <        9        ?        3        :        6);

                                /*        check        for        integer        overflow        */                                if        (new_allocated        >        PY_SIZE_MAX        -        newsize)        {                                                                PyErr_NoMemory();                                                                return        -1;                                }        else        {                                                                new_allocated        +=        newsize;                                }

链表
为什么需要链表
顺序表的构建需要预先知道数据⼤⼩来申请连续的存储空间，⽽在进⾏扩充 时⼜需要进⾏数据的搬迁，所以使⽤起来并不是很灵活。
链表结构可以充分利⽤计算机内存空间，实现灵活的内存动态管理。
链表的定义
链表（Linked        list）是⼀种常⻅的基础数据结构，是⼀种线性表，但是不像顺 序表⼀样连续存储数据，⽽是在每⼀个节点（数据存储单元）⾥存放下⼀个 节点的位置信息（即地址）。


单向链表
单向链表也叫单链表，是链表中最简单的⼀种形式，它的每个节点包含两个 域，⼀个信息域（元素域）和⼀个链接域。这个链接指向链表中的下⼀个节 点，⽽最后⼀个节点的链接域则指向⼀个空值。


表元素域elem⽤来存放具体的数据。 链接域next⽤来存放下⼀个节点的位置（python中的标识） 变量p指向链表的头节点（⾸节点）的位置，从p出发能找到表中的任意 节点。
节点实现

[AppleScript] 纯文本查看 复制代码

class        SingleNode(object):                                """单链表的结点"""                                def        __init__(self,item):                                                                #        item存放数据元素                                                                self.item        =        item                                                                #        next是下⼀个节点的标识                                                                self.next        =        None

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2