python基础--数据结构

原创

ypoint

修改于 2019-08-19 17:16:41

8920

修改于 2019-08-19 17:16:41

数据结构

python 提供了很多现成的数据结构类型,系统定义好的称为内置数据结构,比如:列表(list),元组(tuple),字典(dict),还有部分pythoh系统中没有直接定义,需要我们自己去定义实现的数据结构,称为python的扩展数据结构,比如,栈,队列等.

线性表

在程序中需要将一组数据元素作为整体进行管理和使用,要创建这种元素组，用变量记录它们，传进传出函数等。一组数据中包含的元素个数可能发生变化（可以增加或删除元素）。

对于这种需求，最简单的解决方案便是将这样一组元素看成一个序列，用元素在序列里的位置和顺序，表示实际应用中的某种有意义的信息，或者表示数据之间的某种关系。

这样的一组序列元素的组织形式，我们可以将其抽象为线性表。一个线性表是某类元素的一个集合，还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一，在实际程序中应用非常广泛，它还经常被用作更复杂的数据结构的实现基础。

根据线性表的实际存储方式，分为两种实现模型：

顺序表，将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。

链表，将元素存放在通过链接构造起来的一系列存储块中。

线性表---顺序表形式

元素内置顺序表

图a 表示的是顺序表的基本形式，

数据元素本身连续存储 (内存地址由系统连续分配)
内存空间存储的是数据元素本身 (元素内置)
每个元素所占的存储单元大小固定相同 (元素数据类型一致)
元素的下标是其逻辑地址 (index)
而元素存储的物理地址（实际内存地址）可以通过存储区的起始地址Loc (e0)加上逻辑地址（第i个元素）与存储单元大小（c）的乘积计算而得，即：

Loc(ei) = Loc(e0) + c*i

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

元素外置顺序表

如果元素的大小不统一 (数据类型不一致,如,整型,字符串,...混合)
顺序表中各单元位置保存对应元素的地址信息（即只存实际元素的内存链接地址）。
元素的下标是其逻辑地址 (index)
由于每个链接所需的存储量相同，通过上述公式，可以计算出元素链接的存储位置，而后顺着链接找到实际存储的数据元素。注意，图b中的c不再是数据元素的大小，而是存储一个链接地址所需的存储量，这个量通常很小。

图b这样的顺序表也被称为对实际数据的索引，这是最简单的索引结构。

线性表---顺序表结构与实现

完整的顺序表结构包含2个部分,

数据集合的描述信息部分
- 元素存储去的容量大小
- 实际存储的元素个数
数据元素存储区部分

顺序表的两种基本实现方式

存储表信息区与元素存储区以连续内存地址的方式安排在一块存储区里
一体式结构整体性强，易于管理。
但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了
若想修改元素的存储去,就必须整个顺序表(存储表信息区+存储区)整体迁移,重新向内存申请新的空间.每次修改都重复以上操作

信息区与元素存储区分离
信息区除了保存存储区容量和数据元素实际存储量外,还存储了元素存储区的内存地址
若想跟换数据区,只需将信息区中元素存储区的内存地址更新即可
修改不影响数组的地址,该顺序表对象不变

元素存储区扩充

采用分离式结构的顺序表，若将数据区更换为存储空间更大的区域，则可以在不改变表对象的前提下对其数据存储区进行了扩充，所有使用这个表的地方都不必修改。只要程序的运行环境（计算机系统）还有空闲存储，这种表结构就不会因为满了而导致操作无法进行。人们把采用这种技术实现的顺序表称为动态顺序表，因为其容量可以在使用中动态变化。

扩充的两种策略

每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置，这种策略可称为线性增长
- 特点：节省空间，但是扩充操作频繁，操作次数多。
每次扩充容量加倍，如每次扩充增加一倍存储空间。
- 特点：减少了扩充操作的执行次数，但可能会浪费空间资源。以空间换时间，推荐的方式。

顺序表的操作

增加元素

如图所示，为顺序表增加新元素111的三种方式

a. 尾端加入元素，时间复杂度为O(1)

b. 非保序的加入元素（不常见），时间复杂度为O(1)

插入元素到指定位置,将原来指定位置的元素放到最后'

c. 保序的元素加入，时间复杂度为O(n)

插入元素到指定位置,其余元素往后退格,腾出空位,考虑最坏情况插入位置为0,所以时间复杂度为O(n)

删除元素

a. 删除表尾元素，时间复杂度为O(1)

b. 非保序的元素删除（不常见），时间复杂度为O(1)

删除指定位置的元素,将表尾的元素放入该空余位置上

c. 保序的元素删除，时间复杂度为O(n)

删除指定位置的元素, 往后的元素均往前挪,直至表结构连续不断为止,考虑最坏情况删除位置为0,所以时间复杂度为O(n)

python中的顺序表

python 的基本类型 list tuple 均为顺序表结构,

tuple 为不可变类型,即不可变的顺序表,其余与list相似

python中 list 的基本实现

list 特点:

list 可以存储不同类型的数据元素(即元素外置)
新增,修改和删除元素,表序不变(即保序)
扩展表容量时, 表对象的id地址并没有发生改变(即分离式)

总结:

python 中list 的实现是一种,分离式元素外置的保序动态顺序表,,
基于下标（位置）的高效元素访问和更新，时间复杂度应该是O(1),
允许任意加入元素，而且在不断加入元素的过程中，表对象的标识（函数id得到的值）不变。

线性表--链表

单向链表

单向链表的节点包含:

表元素域 (数据存储)
下一个节点链接域 (下一个节点的内存地址)

单向链表的结构:

单链表的地址是首结点的内存地址
每个节点链接域均为下一节点的地址
末节点的链接域为结束符 T倒置

单向链表的实现:

节点实现

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) 查找节点是否存在

单链表的实现

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 ""

头部添加元素

    def add(self, item):
        """头部添加元素"""
        # 先创建一个保存item值的节点
        node = SingleNode(item)
        # 将新节点的链接域next指向头节点，即_head指向的位置
        node.next = self.__head
        # 将链表的头_head指向新节点
        self.__head = node

尾部添加元素

    def append(self, item):
        """尾部添加元素"""
        node = SingleNode(item)
        # 先判断链表是否为空，若是空链表，则将_head指向新节点
        if self.is_empty():
            self.__head = node
        # 若不为空，则找到尾部，将尾节点的next指向新节点
        else:
            cur = self.__head
            while cur.next != None:
                cur = cur.next
            cur.next = node

指定位置插入元素

    def insert(self, pos, item):
        """指定位置添加元素"""
        # 若指定位置pos为第一个元素之前，则执行头部插入
        if pos <= 0:
            self.add(item)
        # 若指定位置超过链表尾部，则执行尾部插入
        elif pos > (self.length()-1):
            self.append(item)
        # 找到指定位置
        else:
            node = SingleNode(item)
            count = 0
            # pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置
            pre = self.__head
            while count < (pos-1):
                count += 1
                pre = pre.next
            # 先将新节点node的next指向插入位置的节点
            node.next = pre.next
            # 将插入位置的前一个节点的next指向新节点
            pre.next = node

删除节点

    def remove(self,item):
        """删除节点"""
        cur = self.__head
        pre = None
        while cur != None:
            # 找到了指定元素
            if cur.item == item:
                # 如果第一个就是删除的节点
                if not pre:
                    # 将头指针指向头节点的后一个节点
                    self.__head = cur.next
                else:
                    # 将删除位置前一个节点的next指向删除位置的后一个节点
                    pre.next = cur.next
                break
            else:
                # 继续按链表后移节点
                pre = cur
                cur = cur.next

单向循环链表

单向循环链表,是单向表的变形, 尾元素的链接域修改为指向链表的 头节点

双向链表

双向链表节点:

上一个节点的链接域
表元素域 (数据存储)
下一个节点链接域 (下一个结点的内存地址)
结点为第一个节点时，上链接域指向空值
结点为最后一个节点时, 下链接域指向空值

指定位置插入节点

删除节点

栈(stack)

栈,也可以称为堆栈,是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。

由于栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

栈结构实现

栈可以用顺序表实现，也可以用链表实现。

栈的操作

Stack() 创建一个新的空栈
push(item) 添加一个新的元素item到栈顶
pop() 弹出栈顶元素
peek() 返回栈顶元素
is_empty() 判断栈是否为空
size() 返回栈的元素个数

class Stack(object):
    """栈"""
    def __init__(self):
         self.items = []

    def is_empty(self):
        """判断是否为空"""
        return self.items == []

    def push(self, item):
        """加入元素"""
        self.items.append(item)

    def pop(self):
        """弹出元素"""
        return self.items.pop()

    def peek(self):
        """返回栈顶元素"""
        return self.items[len(self.items)-1]

    def size(self):
        """返回栈的大小"""
        return len(self.items)

队列Queue

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

队列的实现

同栈一样，队列也可以用顺序表或者链表实现。

操作

Queue() 创建一个空的队列
enqueue(item) 往队列中添加一个item元素
dequeue() 从队列头部删除一个元素
is_empty() 判断一个队列是否为空
size() 返回队列的大小

class Queue(object):
    """队列"""
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def enqueue(self, item):
        """进队列"""
        self.items.insert(0,item)

    def dequeue(self):
        """出队列"""
        return self.items.pop()

    def size(self):
        """返回大小"""
        return len(self.items)

双端队列(deque)

双端队列（deque，全名double-ended queue），是一种具有队列和栈的性质的数据结构。

双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。双端队列可以在队列任意一端入队和出队。

操作

Deque() 创建一个空的双端队列
add_front(item) 从队头加入一个item元素
add_rear(item) 从队尾加入一个item元素
remove_front() 从队头删除一个item元素
remove_rear() 从队尾删除一个item元素
is_empty() 判断双端队列是否为空
size() 返回队列的大小

class Deque(object):
    """双端队列"""
    def __init__(self):
        self.items = []

    def is_empty(self):
        """判断队列是否为空"""
        return self.items == []

    def add_front(self, item):
        """在队头添加元素"""
        self.items.insert(0,item)

    def add_rear(self, item):
        """在队尾添加元素"""
        self.items.append(item)

    def remove_front(self):
        """从队头删除元素"""
        return self.items.pop(0)

    def remove_rear(self):
        """从队尾删除元素"""
        return self.items.pop()

    def size(self):
            """返回队列大小""" 
        return len(self.items)

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法