Python数据结构与算法分析

第三章   基本数据结构

3.1 何谓线性数据结构

  栈、队列、双端队列和列表都是有序的数据集合，其元素的顺序取决于添加顺序或移除顺序。一旦某个元素被添加进来，它与前后元素的相对位置将保持不变。这样的数据集合经常被称为线性数据结构。

3.2 栈

 栈有时也被称作“下推栈”。它是有序集合，添加操作和移除操作总发生在同一端，即“顶端”，另一端则被称为“底端”。(只能由一端进出，后进先出(LIFO))

3.2.1

 栈是元素的有序集合，添加操作与移除操作都发生在其顶端。栈的操作顺序是 LIFO，它支持以下操作。

• Stack() 创建一个空栈。它不需要参数，且会返回一个空栈
• push(item) 将一个元素添加到栈的顶端。它需要一个参数 item，且无返回值
• pop() 将栈顶端的元素移除。它不需要参数，但会返回顶端的元素，并且修改栈的内容
• peek() 返回栈顶端的元素，但是并不移除该元素。它不需要参数，也不会修改栈的内容
• isEmpty() 检查栈是否为空。它不需要参数，且会返回一个布尔值
• size() 返回栈中元素的数目。它不需要参数，且会返回一个整数

3.2.2 用Python 实现栈

1.栈的实现

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)

if __name__ == '__main__':
    s = Stack()
    #print(s.isEmpty()) #True
    s.push(4)
    s.push('dog')

    #print(s.peek())  # dog
    s.push(True)
    #print(s.size())  # 3

    #print(s.isEmpty())  #False

    s.push(8.4)
    print(s.pop())  #8.4
    print(s.pop())  #True

    print(s.size()) #2 [4,'dog']

2.栈的另一种实现

 也可以选择将列表的头部作为栈的顶端。不过在这种情况下，便无法直接使用 pop 方法和 append 方法，而必须要用 pop 方法和 insert 方法显式地访问下标为 0 的元素，即列表中的第 1 个元素。insert()可以在栈的任何位置插入新元素，但需要指定新元素的索引和值。

def push(self,item):#在栈中索引为0的位置上添加新元素 即栈头
   self.items.insert(0,item)

3.2.3 匹配括号

 匹配括号是指每一个左括号都有与之对应的一个右括号，并且括号对有正确的嵌套关系。

• (()()()())

• (((())))

• (()((())()))

 我们需要编写一个算法，它从左到右读取一个括号串，然后判断其中的括号是否匹配。为了解决这个问题，需要注意到一个重要现象。当从左到右处理括号时，最右边的无匹配左括号必须与接下来遇到的第一个右括号相匹配。并且，在第一个位置的左括号可能要等到处理至最后一个位置的右括号时才能完成匹配。相匹配的右括号与左括号出现的顺序相反。

 思路：由一个空栈开始，从左往右依次处理括号。如果遇到左括号，便通过 push 操作将其加入栈中，以此表示稍后需要有一个与之匹配的右括号。反之，如果遇到右括号，就调用pop 操作与右括号匹配成功的左括号弹出。只要栈中的所有左括号都能遇到与之匹配的右括号，那么整个括号串就是匹配的；如果栈中有任何一个左括号找不到与之匹配的右括号，则括号串就是不匹配的。在处理完匹配的括号串之后，栈应该是空的。

def perChecker(symbolString):
    s = Stack() #借用Stack 类定义的方法
    balance  = True
    index = 0
    while index < len(symbolString) and balance: #遍历栈
        symbol = symbolString[index]  #获取下标对应的值
        if symbol == "(":
            s.push(symbol)    #为左括号 入栈
        else:
            if s.isEmpty():
                balance = False #保证栈不为空
            else:
                symbol.pop()    #为右括号 顶部右括号出栈

        index += 1    #索引值+1
    if balance and s.isEmpty():
        return True
    else:
        return False

 处理多种符号，方括号[和]用于列表；花括号{和}用于字典；括号(和)用于元组和算术表达式。只要保证左右符号匹配，就可以混用这些符号。当每一个左符号都将被压入栈中，以待之后出现对应的右符号。唯一的区别在于，当出现右符号时，必须检测其类型是否与栈顶的左符号类型相匹配。如果两个符号不匹配，那么整个符号串也就不匹配。

def matches(left, right):
    l = "([{"
    r = ")]}"

    return  l.index(left) == r.index(right) #匹配括号

def perChecker(symbolString):
    s = Stack()
    balance  = True
    index = 0
    while index < len(symbolString) and balance: #遍历栈
        symbol = symbolString[index]  #获取下标对应的值
        if symbol == "( [ {":
            s.push(symbol)    #为左括号 入栈
        else:
            if s.isEmpty():
                balance = False #保证栈不为空
            else:
                top = s.pop()    #为右括号 顶部右括号出栈
                if not s.matches(top,symbol):
                    balance = False

        index += 1    #索引值+1
    if balance and s.isEmpty():
        return True
    else:
        return False

3.2.4 将十进制数转换成二进制数

 整数是常见的数据项，它们在计算机程序中无处不在。我们在数学课上学习过整数，并且会用十进制或者以 10 为基来表示它们。

233(10) = 11101001 (2)

1.整数值转换成二进制数:除以2

    def divideBy2(self,decNumber): #divideBy2 函数接受一个十进制数作为参数，然后不停地将其除以 2。

        remstack = Stack()

        while decNumber > 0:
            rem = decNumber % 2 #取余运算符% 求得余数rem
            remstack.push(rem) #将求得的余数rem压入栈
            decNumber = decNumber // 2

        bingString = " " #创建一个空串
        while not  remstack.isEmpty():
            bingString = bingString + str(remstack.pop()) #从栈中被逐个取出，并添加到数字串的最右边

        return  bingString

if __name__ == '__main__':
    s =  Stack()
    print(s.divideBy2(233))

2.二进制对其他进制的转换

233(10) = 351 (8)

233(10) = E9 (16)

 思路：可以将 divideBy2 函数修改成接受一个十进制数以及希望转换的进制基数，“除以 2”则变 成“除以基数”。

    def baseConverter(self,decNumber,base):#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()]  #从栈中被逐个取出，并添加到数字串的最右边 digits[remstack.pop()]取出下标对应的元素
        return newString
if __name__ == '__main__':

     s =  Stack()
     print(s.baseConverter(233,16))

3.2.5 前序、中序和后序表达式

 A + B * C 可以被重写为前序表达式+ A * B C。乘号出现在 B 和 C 之前，代表着它的优先级高于加号。加号出现在 A 和乘法结果之前.

 A + B * C 对应的后序表达式是 A B C * +。运算顺序仍然得以正确保留，这是由于乘号紧跟 B 和 C 出现，意味着它的优先级比加号更高。

 前序表达式和后序表达式的运算顺序完全由运算符的位置决定。

1.从中序向前序和后序转换

• 中序转前序：向左移动运算符

• 中序转后序：向右移动运算符

 若要将任意复杂的中序表达式转换成前序表达式或后序表达式，可以先将其写作完全 括号表达式，然后将括号内的运算符移到左括号处（前序表达式）或者右括号处（后序表达式）。

• 假设中序表达式是一个以空格分隔的标记串。其中，运算符标记有*、/、+和−，括号标记有(和)，操作数标记有 A、B、C 等。下面的步骤会生成一个后序标记串。

  • (1) 创建用于保存运算符的空栈 opstack，以及一个用于保存结果的空列表。

  • (2) 使用字符串方法 split 将输入的中序表达式转换成一个列表。

  • (3) 从左往右扫描这个标记列表。

    • 如果标记是操作数，将其添加到结果列表的末尾。
    • 如果标记是左括号，将其压入 opstack 栈中。
    • 如果标记是右括号，反复从 opstack 栈中移除元素，直到移除对应的左括号。将从栈中取出的每一个运算符都添加到结果列表的末尾。
    • 如果标记是运算符，将其压入 opstack 栈中。但是，在这之前，需要先从栈中取出优先级更高或相同的运算符，并将它们添加到结果列表的末尾。

  • (4) 当处理完输入表达式以后，检查 opstack。将其中所有残留的运算符全部添加到结果列表的末尾。

 思路：使用名为 prec 的字典来保存运算符的优先级值。该字典把每一个运算符都映射成一个整数。通过比较对应的整数，可以确定运算符的优先级（' * /'=3；'+ -' =2、'('=1）。左括号的优先级值最小。导入 string 模块，它包含一系列预定义变量。本例使用一个包含所有大写字母的字符串（string.ascii_uppercase）来代表所有可能出现的操作数。

def infixToPostfix(self,infixexpr):
        prec = {}
        prec["*"] = 3
        prec["/"] = 3
        prec["+"] = 2
        prec["-"] = 2
        prec["("] = 1

        opStack = Stack()

        postfixList = [] #结果列表

        tokenList = infixexpr.split()  #把输入的公式切分存储在tokenList

        for token in  tokenList:  
            if token in string.ascii_uppercase: #包含所有大写字母的字符串
                postfixList.append(token) #标记是操作数（ABCD...），将其添加到结果列表

            elif token == "(":
                opStack.push(token)  #遇到‘(‘压栈
            elif token == ")":
                topToken = opStack.pop()   #遇到“）”，“（” 出栈
                while topToken != "(":  #如果不是右括号 把 tokenList剩下的元素都压入栈中
                    postfixList.append(topToken)
                    topToken = opStack.pop()

            else:
                while (not opStack.isEmpty() and prec[opStack.peek()]>=prec[token]): #标记是运算符,检查栈中是否有优先级更高或相同的运算符，
                                                                                     # 有，出栈，无，入栈
                     postfixList.append(opStack.pop())#添加到结果列表的末尾
                opStack.push(token) #否则出栈

        while not opStack.isEmpty():
            postfixList.append(opStack.pop())

        return " ".join(postfixList)
    
if __name__ == '__main__':

     s =  Stack()
#print(s.baseConverter(233,16))
     print(s.infixToPostfix("( A + B ) * ( C + D )"))

2.计算后序表达式 例子：4 5 6 * +

例子：7 8 + 3 2 + /

• 假设后序表达式是一个以空格分隔的标记串。其中，运算符标记有*、/、+和−，操作数标记是一位的整数值。结果是一个整数

  • (1) 创建空栈 operandStack。

  • (2) 使用字符串方法 split 将输入的后序表达式转换成一个列表。

  • (3) 从左往右扫描这个标记列表。

    • 如果标记是操作数，将其转换成整数并且压入 operandStack 栈中。
    • 如果标记是运算符，从 operandStack 栈中取出两个操作数。第一次取出右操作数，第二次取出左操作数。进行相应的算术运算，然后将运算结果压入 operandStack 栈中。

  • 当处理完输入表达式时，栈中的值就是结果。将其从栈中返回。

    #计算后序表达式


    def postfixEval(self,postfixExpr):

        oprandStank = Stack()  #(1) 创建空栈 operandStack。

        tokenList = postfixExpr.split()  #(2) 使用字符串方法 split 将输入的后序表达式转换成一个列表。

        for token in tokenList:  #(3) 从左往右扫描这个标记列表。
            if token in "0123456789":
                oprandStank.push(token)   #3.1 如果标记是操作数，将其转换成整数并且压入 operandStack 栈中。

            else:           #如果标记是运算符，从 operandStack 栈中取出两个操作数。
                            # 第一次取出右操作数，第二次取出左操作数。
                            # 进行相应的算术运算然后将运算结果压入 operandStack 栈中。

                operand2 = oprandStank.pop()
                operand1 = oprandStank.pop()
                results = oprandStank.doMath(token,operand1,operand2)
                oprandStank.push(results)
        return oprandStank.pop()

    def doMath(self, op, op1, op2):  # doMath 函数
        if op == "*":
            return int(op1) * int(op2)
        elif op == "/":
            return int(op1) / int(op2)
        elif op == "+":
            return int(op1) + int(op2)
        else:
            return int(op1) - int(op2)



if __name__ == '__main__':

     s =  Stack()
    #print(s.baseConverter(233,16))
     # print(s.infixToPostfix("( A + B ) * ( C + D )"))
     print(s.postfixEval("7 8 + 3 2 + /"))

3.3 队列 （FIFO（先进先出）

3.3.1 列表的数据类型

• Queue()创建一个空队列。它不需要参数，且会返回一个空队列。
• enqueue(item)在队列的尾部添加一个元素。它需要一个元素作为参数，不返回任何值。
• dequeue()从队列的头部移除一个元素。它不需要参数，且会返回一个元素，并修改队列内容。
• isEmpty()检查队列是否为空。它不需要参数，且会返回一个布尔值。
• size()返回队列中元素的数目。它不需要参数，且会返回一个整数。

3.3.2 用 Python 实现队列

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

    def isEmpty(self):
        self.items == [] #检查队列是否为空

    def enquene(self,item):
        return  self.items.insert(0,item) #在队列的尾部添加一个元素。

    def dequene(self):
        return self.items.pop() #删除头部元素

    def size(self):
        return len(self.items)#返回队列中元素的数目

if __name__ == '__main__':
     q = Queue()
     q.enquene('dog')
     q.enquene(4)
     q.enquene("True")
     #print(q.size())
     q.dequene()
     print(q.size())

3.3.3 模拟：传土豆

 儿童游戏：传土豆。在这个游戏中，孩子们围成一圈，并依次尽可能快地传递一个土豆，在某个时刻，大家停止传递，此时手里有土豆的孩子就得退出游戏。重复上述过程，直到只剩下一个孩子。

 我们使用队列来模拟一个环，假设握着土豆的孩子位于队列的头部。在模拟传土豆的过程中，程序将这个孩子的名字移出队列，然后立刻将其插入队列的尾部。随后，这个孩子会一直等待，直到再次到达队列的头部。在出列和入列 num 次之后，此时位于队列头部的孩子出局，新一轮游戏开始。如此反复，直到队列中只剩下一个名字（队列的大小为 1）。

    def hotPotato(self,namelist,num): #输入名字列表和传递限制次数
        simqueue = Queue() #建立一个空队列

        for name in namelist :
            simqueue.enquene(name) #把名字入对

        while simqueue.size() > 1: #队列大于1 循环7次
            for i in range(num):
                simqueue.enquene(simqueue.dequene())    #7次内 把出队的元素插入尾部
            simqueue.dequene()  #7次后，头部元素出队

        return simqueue.dequene() #<= 1 队列元素直接出队


if __name__ == '__main__':
      q = Queue()
      print(q.hotPotato(["Bill", "David", "Susan", "Jane", "Kent", "Brad"],7))

3.3.4 模拟：打印任务

例子：一个实验室，在任意的一个小时内，大约有10名学生在场，这一小时中，每人会发起2次左右的打印，每次1～20页。以草稿模式打印的话，每分钟10页，以正常模式打印的话，打印质量好，但速度下降为每分钟5页。 怎么设定打印机的模式， 让大家都不会等太久的前提下尽量提高打印质量？

 我们以学生、打印任务和打印机构建对象。当学生提交打印任务时，我们需要将它们加入等待列表中，该列表是打印机上的打印任务队列。当打印机执行完一个任务后，它会检查该队列，看看其中是否还有需要处理的任务。

 如果实验室里有 10 个学生，并且在一小时内每个人都打印两次，那么每小时平均就有 20 个打印任务。在任意一秒，创建一个打印任务的概率是多少？回答这个问题需要考虑任务与时间的比值。每小时 20 个任务相当于每 180 秒 1 个任务。可以通过 1~180 的一个随机数来模拟每秒内产生打印任务的概率。如果随机数正好是 180，那么就认为有一个打印任务被创建。

1.主要步骤

• 创建一个打印任务队列。每一个任务到来时都会有一个时间戳。一开始，队列是空的。

• 针对每一秒（currentSecond），执行以下操作。

  • 是否有新创建的打印任务？如果是，以 currentSecond 作为其时间戳并将该任务加入到队列中。

  • 如果打印机空闲，并且有正在等待执行的任务，执行以下操作：

    • 从队列中取出第一个任务并提交给打印机；
    • 用 currentSecond 减去该任务的时间戳，以此计算其等待时间；
    • 将该任务的等待时间存入一个列表，以备后用；
    • 根据该任务的页数，计算执行时间。

  • 打印机进行一秒的打印，同时从该任务的执行时间中减去一秒.

  • 如果打印任务执行完毕，或者说任务需要的时间减为 0，则说明打印机回到空闲状态。

• (3) 当模拟完成之后，根据等待时间列表中的值计算平均等待时间。

2.Python 实现

 我们创建 3 个类：Printer、Task 和 PrintQueue。它们分别模拟打印机、打印任务和队列。

 Printer 类需要检查当前是否有待完成的任务。如果有，那么打印机就处于工作状态，并且其工作所需的时间可以通过要打印的页数来计算。其构造方法会初始化打印速度，即每分钟打印多少页。tick 方法会减量计时，并且在执行完任务之后将打印机设置成空闲状态。

import random
import math

class Printer:  #Printer 类 检查当前是否有待完成的任务
    def __init__(self,ppm): #初始化页数，当前是否有任务 打印时间
        self.pagerate = ppm
        self.currentTask = None
        self.timeRemaining = 0

    def tick(self):
        if self.currentTask != None:
            self.timeRemaining =self.timeRemaining - 1  #以一秒的速度  打印机的打印速度自己指定 打印工作开始则开始倒计时
            if self.timeRemaining <=0 : #到0时，则说明该任务打印完毕，打印机为空闲状态
                self.currentTask = None

    def busy(self):                   #当前有任务则处于工作时间，无，则空闲时间
        if self.currentTask != None:
            return True
        else:
            return False
    def startNext(self,newtask):
        self.currentTask = newtask
        self.timeRemaining = newtask.getPages()*60/self.pagerate #打印机的每一页打印所需要的时间=打印速度/页数

    def newPrinter(self):
        num = random.randrange(1,181)
        if num == 180:
            return True
        else:
            return False


class Task: #用于计算打印任务再队列等待时间
    def __init__(self,time):
        self.timestamp = time
        self.page =random.randrange(1,21) #20页

    def getStamp(self):
        return self.timestamp  #入队时间

    def getPages(self):
        return self.page

    def waitTime(self,currenttime):#再队列中等待的时间
        return currenttime - self.timestamp  #开始打印时间-入对的时间


    def simulation(self,numSeconds,pagesPerMinute): #设置总时间，和打印机每分钟打印多少页

        labprinter = Printer(pagesPerMinute)  #连接打印机 Printer(pagesPerMinute) self.timeRemaining = 0 传入打印机中每分钟打印多少页
        printQueue = Queue() #建立一个空队列
        waitingtimes = [] #等待时间

        for currentSecond in range(numSeconds):#在总时间内
            if newPrinter():
                task = Task(currentSecond)
                printQueue.enquene(task) #添加任务

            if (not labprinter.busy()) and (not printQueue.isEmpty()):#打印机空闲却打印队列不为空
                nexttask =printQueue.dequene()  #弹出首部打印任务生成新任务
                waitingtimes.append(nexttask.waitTime(currentSecond)) #该任务的等待时间 入时间列表
                labprinter.startNext(nexttask) #返回该任务打印时间

            labprinter.tick()#启动打印机

        averageWait = sum(waitingtimes)/len(waitingtimes)
        print("Average Wait %6.2f secs %3d tasks remaining." %(averageWait,printQueue.size()))

def newPrinter():
    num = random.randrange(1, 181)
    if num == 180:
     return True
    else:
     return False

3.4 双端队列

3.4.1 何为双端队列

 双端队列是与队列类似的有序集合。它有一前、一后两端，元素在其中保持自己的位置。与队列不同的是，双端队列对在哪一端添加和移除元素没有任何限制。新元素既可以被添加到前端，也可以被添加到后端。同理，已有的元素也能从任意一端移除。某种意义上，双端队列是栈和队列的结合。

3.5.2 双端队列抽象数据结构

• Deque() 创建一个空的双端队列。它不需要参数，且会返回一个空的双端队列。
• addFront(item) 将一个元素添加到双端队列的前端。它接受一个元素作为参数，没有返回值。
• addRear(item) 将一个元素添加到双端队列的后端。它接受一个元素作为参数，没有返回值。
• removeFront()从双端队列的前端移除一个元素。它不需要参数，且会返回一个元素，并修改双端队列的内容。
• removeRear() 从双端队列的后端移除一个元素。它不需要参数，且会返回一个元素，并修改双端队列的内容。
• isEmpty() 检查双端队列是否为空。它不需要参数，且会返回一个布尔值。
• size() 返回双端队列中元素的数目。它不需要参数，且会返回一个整数。

3.4.3 用Python实现双端队列

class Deque: def init(self): #创建一个空的双端队列 self.items = []

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

def size(self):       #返回双端队列中元素的数目 有返回
    return len(self.items)

3.4.4 回文检测器

 回文是指从前往后读和从后往前读都一样的字符串，例如 radar、toot，以及 madam。

 该问题的解决方案是使用一个双端队列来存储字符串中的字符。按从左往右的顺序将字符串中的字符添加到双端队列的后端。此时，该双端队列类似于一个普通的队列。然而，可以利用双端队列的双重性，其前端是字符串的第一个字符，后端是字符串的最后一个字符。

 由于可以从前后两端移除元素，因此我们能够比较两个元素，并且只有在二者相等时才继续。如果一直匹配第一个和最后一个元素，最终会处理完所有的字符（如果字符数是偶数），或者剩下只有一个元素的双端队列（如果字符数是奇数）。任意一种结果都表明输入字符串是回文。

3.4.4.1 用Python实现回文检测器

    def palchcker(self,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



if __name__ == '__main__':
      d = Deque()
      print(d.palchcker("toot"))
      print(d.palchcker("lasjigh"))

3.5 列表

 列表是元素的集合，其中每一个元素都有一个相对于其他元素的位置。更具体地说，这种列表称为无序列表。可以认为列表有第一个元素、第二个元素、第三个元素，等等；也可以称第一个元素为列表的起点，称最后一个元素为列表的终点。

3.5.1 无序列表抽象数据类型

• List() 创建一个空列表。它不需要参数，且会返回一个空列表。
• add(item) 假设元素 item 之前不在列表中，并向其中添加 item。它接受一个元素作为参数，无返回值。
• remove(item) 假设元素 item 已经在列表中，并从其中移除 item。它接受一个元素作为参数，并且修改列表。
• search(item) 在列表中搜索元素 item。它接受一个元素作为参数，并且返回布尔值。
• isEmpty() 检查列表是否为空。它不需要参数，并且返回布尔值。
• length() 返回列表中元素的个数。它不需要参数，并且返回一个整数。
• append(item) 假设元素 item 之前不在列表中，并在列表的最后位置添加 item。它接受一个元素作为参数，无返回值。
• index(item) 假设元素 item 已经在列表中，并返回该元素在列表中的位置。它接受一个元素作为参数，并且返回该元素的下标。
• insert(pos, item) 假设元素 item 之前不在列表中，同时假设 pos 是合理的值，并在位置 pos 处添加元素 item。它接受两个参数，无返回值。
• pop() 假设列表不为空，并移除列表中的最后一个元素。它不需要参数，且会返回一个元素。
• pop(pos) 假设在指定位置 pos 存在元素，并移除该位置上的元素。它接受位置参数，且会返回一个元素。

3.5.1.1 实现无序列表：链表

 无序列表需要维持元素之间的相对位置，但是并不需要在连续的内存空间中维护这些位置信息。如果可以为每一个元素维护一份信息，即下一个元素的位置，那么这些元素的相对位置就能通过指向下一个元素的链接来表示。链表第一个元素的引用被称作头。最后一个元素需要知道自己没有下一个元素。

1. Node类

 节点（node） 是构建链表的基本数据结构。每一个节点对象都必须持有至少两份信息。首先，节点必须包含列表元素，我们称之为节点的数据变量。其次，节点必须保存指向下一个节点的引用。

 指向 None 的引用代表着后面没有元素。注意，Node 的构造方法将 next 的初始值设为 None。由于这有时被称为“将节点接地”，因此我们使用接地符号来代表指向 None 的引用。

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

2.UnorderedList 类

 无序列表（unordered list）是基于节点集合来构建的，每一个节点都通过显式的引用指向下一个节点。只要知道第一个节点的位置（第一个节点包含第一个元素），其后的每一个元素都能通过下一个引用找到。因此，UnorderedList 类必须包含指向第一个节点的引用。

 最开始构建列表时，其中没有元素。赋值语句 mylist = UnorderedList()将创建如下图所示的链表。与在 Node 类中一样，特殊引用值 None 用于表明列表的头部没有指向任何节点。

 isEmpty 方法检查列表的头部是否为指向 None 的引用。(检查链表是否为空)

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

 列表的头部指向包含列表第一个元素的节点。这个节点包含指向下一个节点（元素）的引用，依此类推。非常重要的一点是，列表类本身并不包含任何节点对象，而只有指向整个链表结构中第一个节点的引用。

  add方法列表中的每一个元素都必须被存放在一个节点对象中。创建一个新节点，并且将元素作为其数据。

def add(self,item):
    temp = None(item) #创建链表 输入数字
    temp.setNext(self.head)  #将原来的头指为尾部
    self.head = item #更新头部元素

 length方法需要遍历链表并且记录访问过多少个节点。

def length(self):
    current  = self.head #定位当前链表头部位置
    count = 0 #起初长度为0
    while current != None:
        count = count+1 #长度加一
        current = current.getNext() #只想下一个元素只到链表尾部

    return count

 search方法，在 length 方法中相似，遍历从列表的头部开始。我们使用布尔型变量 found 来标记是否找到所需的元素。由于一开始时并未找到该元素，因此先将 found 初始化为 False。考虑是否到达列表末尾，也考虑了是否已经找到目标元素。只要还有未访问的节点并且还没有找到目标元素，就继续检查 下一个节点。若当前节点元素为目标元素，将found设为True。

以查找17为例子，

 remove 方法，遍历列表并查找要移除的元素。一旦找到该元素（假设元素在列表中），就必须将其移除。从一个指向列表头节点的外部引用开始，遍历整个列表，直到遇到需要移除的元素。由于假设目标元素已经在列表中，因此我们知道循环会在 current 抵达 None 之前结束。当 found 被设为 True 时，current 将指向需要移除的节点。在遍历链表时使用两个外部引用。current 与之前一样，标记在链表中的当前位置。新的引用 previous 总是指向 current 上一次访问的节点。这样一来，当current 指向需要被移除的节点时，previous 就刚好指向真正需要修改的节点。

删除头节点：

def remove(self,item):#输入移除元素
    current = self.head #定位头部
    previous  = None #初始化前一个位置为空
    found = False
    while not found:
        if current.getData == item:
            found = True
        else:
            previous = current #previous指向current 即更新current后的前一个元素
            current = current.getNext() #current指向下一个值

    if previous == None:#如果移除元素为头部
        self.head = current.getNext() #链表的头节点被修改成指向当前头节点的下一节点

    else:
        previous.setNext(current.getNext()) #previous 指向了 next 引用需要被修改的节点。

3.5.2 有序列表抽象数据类型

 在有序列表中，元素的相对位置取决于它们的基本特征。它们通常以升序或者降序排列，并且我们假设元素之间能进行有意义的比较。有序列表的众多操作与无序列表的相同。

 如果前文中的整数列表是以升序排列的有序列表，那么它会被写作17, 26, 31, 54, 77, 93。由于 17 是最小的元素，因此它就成了列表的第一个元素。同理，由于 93 是最大的元素，因此它在列表的最后一个位置。

3.5.2.1 无序列表抽象数据类型

• OrderedList() 创建一个空列表。它不需要参数，且会返回一个空列表。
• add(item) 假设元素 item 之前不在列表中，并向其中添加 item。同时保持整个列表的顺序。它接受一个元素作为参数，无返回值。
• remove(item) 假设元素 item 已经在列表中，并从其中移除 item。它接受一个元素作为参数，并且修改列表。
• search(item) 在列表中搜索元素 item。它接受一个元素作为参数，并且返回布尔值。
• isEmpty() 检查列表是否为空。它不需要参数，并且返回布尔值。
• length() 返回列表中元素的个数。它不需要参数，并且返回一个整数。
• index(item) 假设元素 item 已经在列表中，并返回该元素在列表中的位置。它接受一个元素作为参数，并且返回该元素的下标。
• pop() 假设列表不为空，并移除列表中的最后一个元素。它不需要参数，且会返回一个元素。
• pop(pos) 假设在指定位置 pos 存在元素，并移除该位置上的元素。它接受位置参数，且会返回一个元素。

3.5.2.2 实现有序列表

 在实现有序列表时必须记住，元素的相对位置取决于它们的基本特征。

 OrderedList类的构造方法与 UnorderedList 类的相同。head 引用指向 None，代表这是一个空列表。

class OrderedList:
    def __init__(self):
        self.head = 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

1. search 方法

 在有序列表中搜索45的情况。从列表的头节点开始遍历，首先比较 45 和 17,由于 17 不是要查找的元素，因此移向下一个节点，即 26。它也不是要找的元素，所以继续向前比较 31 和之后的 54。由于 54 不是要查找的元素，因此在无序列表中，我们会继续搜索。但是，在有序列表中不必这么做。一旦节点中的值比正在查找的值更大，搜索就立刻结束并返回 False。这是因为，要查找的元素不可能存在于链表后序的节点中。

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
                stop = True
            else:
                current = current.getNext() #否则查找下一个节点

    return found

2. add 方法

 假设要向有序列表 17, 26, 54, 77, 93 中添加 31。add 方法必须确定新元素的位置在 26 和 54之间。需要遍历链表来查找新元素的插入位置。当访问完所有节点（current 是 None）或者当前值大于要添加的元素时，就找到了插入位置。

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)#前元素的下一个元素为目标元素