mobile wallpaper 1mobile wallpaper 2mobile wallpaper 3mobile wallpaper 4mobile wallpaper 5mobile wallpaper 6
Profile Image of the Author
超級の新人
Announcement
私のブログにご訪問いただき、ありがとうございます！
标签
2187 字
11 分钟
线性结构笔记
2026-01-14
算法
算法

栈抽象数据类型及python实现#

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


    def isEmpty(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)

栈的应用#

括号匹配#

def parChecker(symbolString):
    s = Stack()
    balanced = True //括号是否平衡
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in "([{":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                top = s.pop
                if not matches(top,symbol):
                    balanced = False
        index = index + 1


    if balanced and s.isEmpty():
        return True
    else:
        return False


def matchs(open,close):
    open = "([{"
    closers = ")]}"
    return open.index(open) == closers.index(close)

如果是(那么入栈，如果是)那么栈中的(出栈

若(多了则不为空；若)多了则不平衡

最后检验栈是否为空或不平衡进行判断括号是否匹配

进制转换#

十进制转换成二进制

def divideBy2(decNumber):
    remstack = Stack()


    while decNumber > 0;
        rem = decNumber % 2
        remstack.push(rem) //把余数入栈
        decNumber = decNumber // 2


    binString = ""
    while not remstack.isEmpty(): //把每个余数出栈
        binString = binString + str(remstack.pop())


    return binString

十进制转换成十六进制以下任何进制

def baseConverter(decNumber,base):
    digits = "0123456789ABCDEF"


    remstack = Stack()


    while decNumber > 0;
        rem = decNumber % base
        remstack.push(rem) //把余数入栈
        decNumber = decNumber // base


    newString = ""
    while not remstack.isEmpty(): //把每个余数出栈
        newString = newString + digits[remstack.pop()]


    return newString

表达式转换#

为了解决A+B*C的混淆，人们引入了操作符优先级的概念，同时引入了括号来表示强制优先级(A+B)*C

但是计算机处理这种操作符优先级会很麻烦，因此引入了全括号中缀表达式

之后可以扩展为前缀和后缀表达式 转换方法如下 后缀 前缀

在中缀表达式转换为后缀形式的处理过程 中，操作符比操作数要晚输出

所以在扫描到对应的第二个操作数之前，需要把 操作符先保存起来

在从左到右扫描逐个字符扫描中缀表达式的过程中，采用一个栈来暂存未处理的操作符

这样，栈顶的操作符就是最近暂存进去的 ，当遇到一个新的操作符，就需要跟栈顶 的操作符比较下优先级，再行处理。

流程：
从左到右扫描中缀表达式单词列表
如果单词是操作数，则直接添加到后缀表达式列表的末尾
如果单词是左括号“(”，则压入opstack栈顶
如果单词是右括号“)”，则反复弹出opstack栈顶
操作符，加入到输出列表末尾，直到碰到左括号
如果单词是操作符“*/+-”，则压入opstack栈顶
• 但在压入之前，要比较其与栈顶操作符的优先级
• 如果栈顶的高于或等于它，就要反复弹出栈顶操作符，加入到输出列表末尾
• 直到栈顶的操作符优先级低于它
  • ❖中缀表达式单词列表扫描结束后，把opstack栈中的所有剩余操作符依次弹出，添加到输出列表末尾
  • ❖把输出列表再用join方法合并成后缀表达式字符串，算法结束。

代码

后缀表达式求值

  • ❖ 创建空栈operandStack用于暂存操作数

  • ❖ 将后缀表达式用split方法解析为单词（token）的列表 ❖ 从左到右扫描单词列表

      如果单词是一个操作数，将单词转换为整数int，压入operandStack栈顶
      如果单词是一个操作符（*/+-），就开始求值，从栈顶弹出2个操作数，先弹出的是右操作数，后弹出的是左操作数，计算后将值重新压入栈顶

  • ❖ 单词列表扫描结束后，表达式的值就在栈顶

  • ❖ 弹出栈顶的值，返回。 流程图 代码

队列抽象数据类型及python实现#

将List首端作为Queue的尾端

将List末端作为Queue的首端

class Queue:
    def _init_(self):
        self.items = []


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


    def enqueue(self,item):
        self.items.insert(0,item)
    //enqueue()复杂度为O(n)


    def dequeue(self):
        return self.items.pop()
    //dequeue()复杂度为O(1)


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

若首尾倒过来的实现，复杂度也倒过来

队列的应用#

热土豆问题(约瑟夫问题)#

击鼓传花的土豆版本

传烫手的热土豆，在鼓声停的时候，手里有土豆的小孩要出列 代码

双端队列抽象数据类型及python实现#

class Deque:
    def _init_(self):
        self.items = []


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


    def addFront(self,item):
        self.items.append(item)


    def addRear(self,item):
        self.items.insert(0,item)


    def removeFront(self):
        return self.items.pop()


    def removeRear(self):
        return self.items.pop(0)


    // addRear/removeRear操作复杂度为O(n)
    // addFront/removeFront操作复杂度为O(1)


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

双端队列的应用#

回文词问题#

先将需要判定的词从队尾加入deque

再从两端同时移除字符判定是否相同，直到deque中剩下0个或1个字符

def palchecker(aString):
    chardeque = Deque()


    for ch in aString:
        chardeque.addRear(ch)


    stillEqual = True


    while chardeque.size() > 1 and stillEqual:
        first = chardeque.removeFront()
        last = chardeque.removeRear()
        if first != last:
            stillEqual = False


    return stillEqual

无序表抽象数据类型及python实现#

无序表（Unordered List）是一种数据项按照相对位置存放的数据集，其中数据项只按照存放位置来索引（如第1个、第2个、最后一个等），而不考虑数据项之间的大小顺序关系。

特点： 数据项的存放位置可以不连续，通过节点之间的链接指向来保持前后相对位置。

无序表的链表实现#

节点是链表实现的最基本元素，每个节点包含：

  • 数据项本身（data）
  • 指向下一个节点的引用（next）
class Node:
    def __init__(self, initdata):
        self.data = initdata
        self.next = None


    def getData(self):
        return self.data


    def getNext(self):
        return self.next


    def setData(self, newdata):
        self.data = newdata


    def setNext(self, newnext):
        self.next = newnext

注意： next为None表示没有下一个节点，这是链表末尾的标志。

无序表通过head属性保存对第一个节点的引用，空表的head为None。

class UnorderedList:
    def __init__(self):
        self.head = None

抽象数据类型操作

基本操作

  • List()：创建一个空列表
  • isEmpty()：返回列表是否为空
  • size()：返回列表包含的数据项数量
  • add(item)：添加数据项到列表
  • remove(item)：从列表中移除数据项
  • search(item)：查找数据项，返回布尔值
  • append(item)：添加数据项到表末尾
  • index(item)：返回数据项在表中的位置
  • insert(pos, item)：将数据项插入到指定位置
  • pop()：从列表末尾移除数据项
  • pop(pos)：移除指定位置的数据项

部分方法实现

isEmpty() - 判断空表

def isEmpty(self):
    return self.head == None

add() - 添加数据项（表头插入）

设计思路： 新数据项添加到表头位置最快捷，因为访问整条链都必须从head开始。

def add(self, item):
    temp = Node(item)
    temp.setNext(self.head)  # 新节点指向原来的第一个节点
    self.head = temp          # head指向新节点

注意： 链接次序很重要！必须先让新节点指向原head，再修改head指向新节点。

size() - 统计数据项数量

def size(self):
    current = self.head
    count = 0
    while current != None:
        count = count + 1
        current = current.getNext()
    return count

search() - 查找数据项

def search(self, item):
    current = self.head
    found = False
    while current != None and not found:
        if current.getData() == item:
            found = True
        else:
            current = current.getNext()
    return found

remove() - 删除数据项

设计思路： 需要同时维护current（当前节点）和previous（前一个节点）两个引用，因为删除需要将前一个节点的next指向current的下一个节点。

def remove(self, item):
    current = self.head
    previous = None
    found = False


    # 查找item
    while not found:
        if current.getData() == item:
            found = True
        else:
            previous = current
            current = current.getNext()


    # 删除操作：区分两种情况
    if previous == None:  # 删除的是首节点
        self.head = current.getNext()
    else:  # 删除的是中间节点
        previous.setNext(current.getNext())

两种删除情况：

  • current是首节点：直接修改head指向下一个节点
  • current是中间节点：修改previous的next指向current的下一个节点

有序表抽象数据类型及python实现#

有序表的链表实现#

有序表(OrderList)的实现和无序表类似，都以链表形式来实现

大部分方法的实现(如：isEmpty、size、remove)也相同，主要不同的地方是search方法和add方法

以下是这两个方法的实现

search方法

def search(self,item):
   current = self.head
   found = False
   stop = False


   while current != None and not found and not stop:
       if current.getData() == item:
           found = True
       else:
           if current.getData() > item:
   //减少操作次数，若比当前数据还大，但是未找到则直接停止
               stop = True
           else:
               current = current.getNext()


   return found

add方法

def add(self,item):
    current = self.head
    previous = None
    stop = False


    while current != None and not stop:
        if current.getData() > item: //发现插入位置
            stop = True
        else:
            previous = current
            current = current.getNext()


    temp = Node(item)
    if previous == None: //插入到表头
        temp.setNext(self.head)
        self.head = temp
    else:  //插入到表中
        temp.setNext(current)
        previous.setNext(temp)

链表复杂度分析

分享

如果这篇文章对你有帮助，欢迎分享给更多人！

线性结构笔记
https://chaojixin.ren/posts/线性结构笔记/
作者
超級の新人
发布于
2026-01-14
许可协议
CC BY-NC-SA 4.0

部分信息可能已经过时

递归学习笔记
变位词问题的解法及其时间复杂度分析
辽ICP备2026000942号
© 2026 超級の新人. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 7.6.5
封面
Sample Song
Sample Artist
封面
Sample Song
Sample Artist
0:00 / 0:00