2-线性结构

线性结构的概念

  • 线性结构是一种有序数据项的集合，可以有零个或多个数据项，其中每个数据项都有唯一的前驱和后继，除了第一个没有前驱，最后一个没有后继

  • 线性表包括列表，栈，队列等不同的抽象数据结构，不同的线性表主要体现在于对于数据项的增删改查的方式以及性能差异

三种主要线性数据结构类型

列表-LIST

  • python中包含了一个内建的列表类型，是基于数组进行实现的，但其实还有几种不同的实现方法,下面主要介绍两种经典的实现（数组和链表）

顺序存储（数组实现）

  • 底层物理结构是数组，而数组用一段连续的内存存放，所以在内存中数据项是相互挨在一起的，只要知道了此列表在内存地址中的起始位置，就能通关偏移量的大小定位到其他数据项的位置，基于索引

数组两大特点

  • 支持随机访问
  • 存储在一块连续的内存上

你所要了解的数组操作

增加数组大小
  1. 创建一个新的，更大的数组（申请更大的内存空间）
  2. 将原数据复制到新的数组中（这样新数组就有更大的空间容纳数据项）
  3. 将指向就数组的变量重新指向新数组，旧数组的内存则被回收
减小数组的大小
  1. 创建一个更小的数组
  2. 将原数组内容复制到新数组
  3. 将新数组设置为新的数组对象
数组中插入一项
  1. 先检查数组大小是否够用，不够用先申请空间
  2. 从数组最后一项的位置开始直到要插入数据项的索引位置，将每个数据项都往后移动一个位置
  3. 这样就会在目标位置空出一个位置给新的数据项插入
数组中删除一项
  1. 先将目标索引位置的数据项从数组中移除
  2. 将索引位置之后的所有数组向前移动一位

时间复杂度

# O(1)
搜索第i项/替换第i项/从末尾追加/从末尾删除/
# O(n)
从第i个位置插入/删除/增加数组容量/减小数组容量

链式存储（链表实现）

特点

  • 由于数组结构的列表对于删除和插入的性能不是很好，所以构造了以链表作为底层结构的实现
  • 链表结构和数组结构的不同主要体现在每个数据项不光含有数据信息，还另外维护了一个指针元素，这两部分合起来称之为一个节点。而链表实现的基本元素就是节点，单链表的节点包含两个部分，数据项的引用以及到下一个节点的引用
  • 链表结构中，对于单纯的数据项，在内存中的相对位置没有规则，但是可以通过每个节点中指针信息指向下一个数据项在内存中的位置，这样就形成链条一样的形状，故称之为链表结构

构建节点类

# 构建节点类
class Node:
  def __init__(self, data, next=None):
    self.data = data
    self.next = next
# 一般来讲，初始化次类会创建一个空链接或是新的Node对象

生成链表

head = None
for i in range(n):
  head = Node(i, head)
# 假设n=3，生成的链表是这个样子的：2->1->0->None，此时head=Node(2,指向数据项为1的节点)
# 你会发现，数据项的遍历和节点生成以相反的方式呈现（当然，这只是一种生成链表的方式，也可以通过程序设计，保证数据项和节点生成的一致性）

链表操作(代码实现)

遍历
# 正确的做法一般来讲，会构建一个新的变量，初始化为链表的head指针，用指针去遍历整个链表
temp = head
while temp !=None:
  temp = temp.next

# 错误的遍历方法，因为head在变化，最后的结果就是，head是None，前面的节点全都删除了
while head !=None:
  head = head.next
搜索目标值
# 构建一个新的变量，初始化为链表的head指针，通过遍历搜索目标值
temp = head
while temp != None and temp.data != target_data:
  probe = probe.next
if probe != None:
  print("success to find")
 else:
  print("fail to find")
替换第i项位置的数据
temp = head
# 假设替换索引为5的节点
index = 5
# 要么遍历到链表结尾，链表长度不够，结束循环，要么找到链表要替换的位置，结束循环
while temp != None and index > 0:
  temp = temp.next
  index -= 1
if temp == None:
  print("fail to replace")
else:
  temp.data = target
在任意索引位置插入节点
# 两种情况，要么索引大于链表长度，那么插在最后，要么索引小于链表，插入索引位置
if head is None or index < 0:
  head= Node(new_data, head)
else:
  temp = head
  # index > 1是为了放置新节点在（index-1）到index之间
  if temp.next != None and index > 1:
    temp = temp.next
    index -= 1
  temp.next = Node(new_data, temp.next)
在任意位置删除节点
# 这里只考虑索引小于链表长度
temp = head
index = 5
while temp.next.next != None and index > 1:
  temp = temp.next
  index -= 1
temp.next = temp.next.next

时间复杂度

# O(1)
从开始处插入节点/从开始处删除节点
# O(n)
在第i个位置访问/替换(平均情况),在第i个位置插入/删除(平均情况)

列表接口

  • 一般列表这种结构，都会提供如下几个接口
add(data)               # 添加数据项
insert(index, data)     # 插入数据项到索引位置
replace(index, data)    # 将索引位置的数据项替换
pop(index)              # 将索引位置的数据项弹出列表
remove(data)            # 删除某个数据项

栈-STACK

特点

  • 栈结构也可以通过数组或者链表结构设计实现

  • 数据项的加入和移除都限制在一端，这个端点一般称之为栈顶

  • 后进先出的结构特点（LIFO），越早进入栈结构的数据越晚离开栈

生活中的例子（加深理解）

  • 一摞盘子，想取的话只能先取最上面的一个，然后下一个，依次类推，但如果想放新的盘子上去，也只能将新盘子放在所有盘子的最上面，然后再摞一个，以此类推。这个（顶端）用来拿或者取盘子的位置，抽象出来一个概念，称之为栈顶。盘子最下面不参与任何的操作，称之为栈底。

经典应用

  • 编译器基本功能中的对于各种括号（"(){}[]"）的正确匹配
  • 回溯算法
  • 管理计算机内存支持函数和方法的调用
  • 中缀表达式转换为后缀表达式；计算后缀表达式
    • 利用运算符优先级的思想（转换）
      1. 如果遇到操作数，我们就直接将其输出
      2. 如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。
      3. 如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。
      4. 如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "
      5. 如果我们读到了输入的末尾，则将栈中所有元素依次弹出

部分应用代码实现

# 我们这里简单的用python内置列表作为基础结构实现栈结构
class Stack:
    """利用列表（底层为数组）构建栈的抽象结构"""
    def __init__(self):
        self._items = []

    def size(self):
        return len(self._items)

    def push(self, item):
        self._items.append(item)

    def pop(self):
        return self._items.pop()

    def is_empty(self):
        return len(self._items) == 0

    def peek(self):
        return self._items[len(self._items) - 1]
#######################################################################

# 中缀转后缀表达式
def infix_to_suffix(expressions):
    """当前约定中缀表达式是以空格进行分割, exp: a + b * c"""
    s = Stack()
    exp_list = expressions.split(" ")
    # 存放操作数
    num_list = []
    # 自定义优先级，"("的存在是为了有多重括号存在时，保证所有的+-*/都可以顺利入栈
    priority_dic = {"(": 1, "+": 2, "-": 2, "*": 3, "/": 3}
    for token in exp_list:
        if token not in "+-*/()":
            num_list.append(int(token))
        elif token == "(":
            s.push(token)
        elif token == ")":
            while s.peek() != "(":
                num_list.append(s.pop())
            # 将"("弹出
            s.pop()
        else:
            while s.size() > 0 and priority_dic.get(token) <= priority_dic.get(s.peek()):
                num_list.append(s.pop())
            s.push(token)
    # 检查栈中是否还有操作符存在，有的话，依依弹出即可
    while not s.is_empty():
        num_list.append(s.pop())
    return "".join([str(i) for i in num_list])


# 计算后缀
def calc_suffix(expression):
    s = Stack()
    for token in expression:
        if token in "0123456789":
            s.push(int(token))
        else:
            # 要考虑到减法和除法顺序不能颠倒的问题
            num_first = s.pop()
            num_second = s.pop()
            tmp_result = convert_to_math(token, num_first, num_second)
            s.push(tmp_result)
    return s.pop()


# 辅助函数，每两个弹出元素的计算结果
def convert_to_math(token, num1, num2):
    if token == "*":
        return num1 * num2
    elif token == "/":
        return num2 / num1
    elif token == "-":
        return num2 - num1
    elif token == "+":
        return num1 + num2

# 测试数据
convert_ret = infix_to_suffix("3 + 5 * 2 - 5 * ( 3 + 2 )")
calcu_ret = calc_suffix(convert_ret)
print(calcu_ret)
####################################################################

# 10进制转换为2/8/16进制的字符串格式
def to_str(n, base):
    :param n: 十进制数
    :param base: 想要转换的进制
    :return: 
    if n < base:
        return str(n)
    elif 2 <= base <= 10:
        return to_str(n // base, base) + str((n % base))
    else:
        convert_string = "0123456789abcdef"
        return to_str(n // base, base) + convert_string[(n % base)]

ret = to_str(541, 2)
print(ret)

队列-QUEUE

特点

  • 队列也可以由数组或是链表结构设计实现，数组的实现（循环数组的方法）要难于链表，但是性能更优

  • 队列是一种有次序的数据集合，表现为向队列中添加数据时，永远在尾端添加，而移除数据则永远从队首删除

  • 先进先出的结构特点（FIFO），越早进入栈结构的数据越早离开栈

生活中的例子（加深理解）

  • 排队买票，一般情况下，你应该从买票队伍的最后一个位置进入列队
  • 一台打印机面向多个用户或是程序的情况

经典应用

  • 模拟打印机处理多任务
  • 模拟道路交通，超市结账排队情况等
  • CPU访问
    • 多个进程访问同一个CPU，新进程会被添加到队列，这个队列就是等待CPU使用的进程

部分应用代码实现

约瑟夫/热土豆理论

# 热土豆问题：几个小朋友，围成一圈，用一个热土豆（或别的什么东西），数一个数就抛给下一个人，每数到3，手上有土豆的人就站出来，然后继续，问哪个位置的人最后剩下？

# 利用内置数据类型列表构建队列数据结构
class Queue():
    def __init__(self):
        self._items = []

    def size(self):
        return len(self._items)

    def enqueue(self, data):
        self._items.insert(0, data)

    def dequeue(self):
        return self._items.pop()

    def is_empty(self):
        return len(self._items) == 0

# 热土豆问题逻辑代码
def hot_potato(lists, num):
    q = Queue()
    # 按人名将数据项入队
    for person in lists:
        q.enqueue(person)
    # 直到只剩下一个人，游戏结束
    while q.size() > 1:
        for i in range(num):
            q.enqueue(q.dequeue())
        q.dequeue()
    # 将最后剩下的人返回
    return q.dequeue()

# 模拟热土豆的实例，参数分表代表参加游戏的人名以及土豆每传递几次就出队一个人
last_person = hot_potato(["A", "B", "C", "D", "E", "F", "G", "H", "I", "L", "M", "N", "O"], 3)
print(last_person)

生产者消费者模型

import threading
import queue
 
 
def producer():
    """
    模拟生产者
    :return:
    """
    for i in range(10):
        print("生产包子%s" %i)
        q.put("包子 %s" % i)
 
    print("开始等待所有的包子被取走...")
    q.join()  # 等待这个包子队列被消费完毕
    print("所有的包子被取完了...")
 
 
def consumer(n):
    """
    模拟消费者
    :return:
    """
    while q.qsize() > 0:
        print("%s 取到" % n, q.get())
        q.task_done()  # 每取一个包子，便告知队列这个任务执行完了
 
q = queue.Queue()
 
p = threading.Thread(target=producer,)
p.start()
 
c1 = consumer("xiaochen")
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,968评论 6赞 482
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,601评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 153,220评论 0赞 344
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,416评论 1赞 279
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,425评论 5赞 374
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,144评论 1赞 285
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,432评论 3赞 401
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,088评论 0赞 261
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,586评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,028评论 2赞 325
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,137评论 1赞 334
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,783评论 4赞 324
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,343评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,333评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,559评论 1赞 262
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,595评论 2赞 355
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,901评论 2赞 345