数据结构Python版--线性结构_python 线性结构

线性数据结构

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

栈

有序集合，添加操作和移除操作总发生在同一端。栈中的元素离底端越近，代表其在栈中的时间越长，最先添加的元素最先被移除，排序原则为先进后出。栈中元素的插入和移除的顺序相反。
栈抽象数据类型是由下面的结构和操作定义：
stack():创建一个空栈，不需要参数，且会返回一个空栈。
push(item):将一个元素添加到栈的顶端，需要一个参数item，没有返回值。
pop():将栈顶端的元素移除，不需要参数但会返回顶端的元素，并修改栈中的内容。
peek():返回栈顶的元素，但是不移除该元素。
isEmpty():检查是否为空，它不需要参数，会返回一个布尔值。
size():返回栈中元素的数目，不需要参数，会返回一个整数。

# 列表的尾部入栈
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)
# 另一种实现方式 列表的头部入栈
class StackTwo:
    def __init__(self):
        self.items = []

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

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

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

    def peek(self):
        return self.items[0]

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

# 创建空栈
s = Stack()
# 判空
s.isEmpty()
# 入栈
s.push(4)
s.push(5)

# 出栈
s.pop()

# 栈的大小
print(s.size())
# 栈中的元素
print(s.items)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

匹配括号

每一左括号都有一个与之对应的右括号对应，并且括号对有正确的嵌套关系。编写一个算法：从左到右读取一个括号，判断其中的括号是否匹配。最右边的无匹配左括号必须与接下来遇到的第一个右括号相匹配，并且第一个位置的左括号可能要等到处理至最后一个位置的右括号时才能完成匹配。相匹配的右括号与左括号出现的顺序相反。
由一个空栈开始，如果遇到左括号就入栈，如果遇到右括号就出栈，如果栈中的所有左括号都能遇到与之匹配的右括号，则括号串就是匹配的，如果栈中有任何一个左括号找不到与之匹配的右括号，则不匹配。在处理完匹配的括号串之后，栈应该是空的。

# 匹配括号算法
def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString
        if symbol == "(":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()
        index = index +1
    if balanced and s.isEmpty():
        return True
    else:
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 扩展到匹配符号
# 匹配符号算法
def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString
        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 matches(open,close):
    opens = "([{"
    closes = ")]} "
     # 在两个列表中括号的位置是否一样
    return opens.index(open) == closes.index(close)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

进制转换问题

除以2算法假设待处理的整数大于0，它用一个简单的玄幻不停的将10进制除以2，并且记录余数，第一次除以2的结果能够用于区分偶数和奇数，如果是偶数则为0 。

# 除以2算法
def divideBy2(decNumber):
    restack = Stack()

    while decNumber >0:
        rem = decNumber % 2
        restack.push(rem)
        decNumber = decNumber //2

    binString = ""
    while restack.isEmpty():
        binString = binString + str(restack.pop())
    return binString
1
2
3
4
5
6
7
8
9
10
11
12
13

可以将上述算法扩展成一个十进制数以及希望转换成的进制基数，除以2变成除以基数。但是当基数超过10之后就会遇到问题，不能再直接使用余数。

前序、中序和后序表达式

运算符出现在两个操作数的中间，称为中序表达式。
计算机徐娅明确的知道以何种顺序进行计算，杜绝歧义的方法是完全括号表达式。这种表达式对每一个运算符都要添加一对括号，由括号决定运算顺序，没有任何歧义。
前序表达式要求所有的运算符出现它所作用的两个操作数之前，后序表达式则相反。前序和后续表达式不需要括号，运算顺序完全由运算符的位置确定。

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

开发一种将任意中序表达式转换成后续表达式的算法。后序表达式中相对位置保持不变只有运算符改变了位置，中序运算符中的顺序和后序表达的相反。当遇到左括号时，需要将其保存，表示接下来会遇到高优先级的运算符，那么这个运算符需要等到对应的右括号出现才能确定其位置，当右括号出现时，便可以将运算符从栈中取出来。
1.创建一个用于保存运算符栈，以及一个用于保存结果的空列表。
2.使用字符串方法将输入的中序表达式转换成一个列表
3.从左向右扫描这个标记
如果标记时操作数，将其添加到结尾列表的末尾，如果时左括号，将其压入栈中，如果是右括号，反复从栈中移除元素，直到移除对应的左括号，将从栈中取出的每一个运算符都添加到结果列表的末尾。如果是运算符，将其压入栈中，但是需要从栈中取出优先级更高或相同的运算符，并将它们添加到结果列表的末尾，保证栈顶的操作符的优先级是低于它的。
4.当处理完输入表达式以后，检查栈，将其中所有残留的运算符全部都添加到结果列表的末尾。

# 中序转换成后序
import string
def infixToPostfix(infixexpr):
    # 保存运算符的优先级，把每一个运算符都映射称为一个整数，通过比较整数来确定优先级
    prec ={}
    prec["*"] = 3
    prec["/"] = 3
    prec["-"] = 2
    prec["+"] = 2
    prec["("] = 1

    opStack = Stack()
    postfixList = []

    tokenList = infixexpr.split()

    for token in tokenList:
        # 获取所有ascii码中的大写英文字母
        # 直接将字母添加到列表中
        if token in string.ascii_uppercase:
            postfixList.append(token)
        # 直接压入左括号
        elif token == '(':
            opStack.push(token)
        # 如果遇到右括号
        elif token == ')':
            # 依次输出运算符
            topToken = opStack.pop()
            while topToken != '(':
                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)

print(infixToPostfix("( A + B ) * ( C + D )"))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

计算后序表达式，栈是合适的数据结构，当扫描后序表达式时，需要保存操作数，而不是运算符。当遇到一个运算符时，需要用离它最近的两个操作数来计算。

假设后序表达式是一个以空格分隔的标记串，结果是一个整数：
1.创建一个空栈
2.使用字符串方法将输入的后序表达式转换成一个列表
3.从左向右扫描这个标记列表
如果标记是操作数，将其转换成整数压入栈中，如果标记是运算符，从栈中取出两个操作数，进行相应的算术运算，然后将结果压入栈中，当处理完输入表达式时，栈中的值就是结果，将其从栈中返回。

# 计算后序表达式
def postfixEval(postfixExpr):
    operandStack = Stack()
    
    tokenList = postfixExpr.split()
    
    for token in tokenList:
        
        if token in "0123456789":
            operandStack.push(int(token))
        else:
            operand2 = operandStack.pop()
            operand1 = operandStack.pop()
            result = doMath(token,operand1,operand2)
            operandStack.push(result)
    return operandStack.pop()
def doMath(op,op1,op2):
    if op == "*":
        return op1*op2
    elif op == "/":
        return op1/op2
    elif op == "+":
        return op1+op2
    else:
        return op1- op2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

队列

队列也是线性数据结构。
队列是有序集合，添加操作发生在尾部，移除操作则发生在头部。新元素从尾部进入队列，然后一直向前移动到头部，知道成为下一个被移除的元素，先进先出原则。
Queue()：创建一个空队列，不需要参数，返回一个空队列。
enqueue(item)：在尾部添加一个元素，它需要一个元素作为参数，不返回任何值。
dequeue():从队列的头部移除一个元素，它不需要参数，且会返回一个元素，并且修改队列的内容。
isEmpty():检查队列是否为空，不需要参数，返回一个布尔值。
size():返回队列中元素的数目，不需要参数，返回一个整数。

class Queue:
    def __init__(self):
        self.items = []
    # 判空
    def isEmpty(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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

传土豆

该程序接受一个名字列表和一个用于计数的常量num,并且返回最后一个人的名字。假设握着土豆的孩子位于队列的头部，在模拟传土豆的过程中，程序将这个孩子的名字移除队列。在出列和入列num次之后，此时位于 队列头部的孩子出局，新一轮的游戏开始，如此反复，直到队列中只剩下一个名字（队列的大小为1）.

# 传土豆程序
def hotPotato(namelist,num):
# 创建一个空队列
    simqueue = Queue()
    # 将姓名列表入队列
    for name in namelist:
        simqueue.enqueue(name)
# 只要大于1游戏继续
    while simqueue.size()>1:
        for i in range(num):
        # 将出队列的姓名添加在队列的尾部
            simqueue.enqueue(simqueue.dequeue())
# 要出队列的姓名
        simqueue.dequeue()
# 最后的姓名
    return simqueue.dequeue()

# 调用函数
print(hotPotato(['bill','david','susan','jane','kent','brand'],7))

运行结果
susan
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

打印任务

模拟打印任务队列，向共享打印机发送打印请求，这些任务被存放在一个队列中，并且按照先到先得的顺序执行。这样的设置会导致很多问题，最重要的是，打印机能否处理一定量的工作，如果不能，学生可能会由于等待过长时间而错过要上的课程。在任何给定的一个小时内，实验室都有约10个学生，它们在这一个小时内最多打印2次，并且打印页数从1到20不等，实验室的打印机每分钟只能打印10张，可以将打印机质量调高，这样打印机没分证打印5张，应该如何设置打印速度呢？
概率学知识：学生打印的文章可能有1~ 20页，如果各页数出现的概率相等，那么打印任务的实际时长就可以通过1~20的一个随机数来模拟。如果实验室有10个学生，并且在一个小时内每个人都打印两次，那么每小时平均就有20个打印任务。在任意一秒，创建一个打印任务的概率是多少？

通过1~180的一个随机数来模拟每秒内产生打印任务的概率。随机数正好是180，那么认为有一个有一个任务被创建，可能会出现多个任务连接被创建的情况，也可能很长一段时间都没有任务。这是模拟的本质，希望在常用参数已知的情况下尽可能的准确的模拟。
主要步骤：
1.创建一个打印任务队列，每一个任务到来时都会有一个时间戳。
2.针对每一秒，执行：
（1）是否有新创建的打印任务，如果是，以currentSecond作为时间戳并将该任务加入到队列中，
（2）如果打印机空闲，并且有正在等待执行的任务，则：
从队列中取出第一个任务并提交给打印机；
用currentSecond减去该任务的时间戳，以此计算其等待时间；
将该任务的等待时间存入一个列表，以备后用；
根据该任务的页数，计算执行时间；
（3）打印机进行一秒的打印，并从该任务的执行时间中减去一秒
（4）如果打印任务执行完毕，或者说任务需要的时间减为0，则说明打印机回到空闲状态。
3.模拟完成之后，根据等待时间列表中的值计算平均等待时间。

'''
printer类需要检查当前是否有待完成的任务，如果有，那么打印机就处于工作状态
并且其工作所需要的时间可以通过要打印的页数来计算
构造方法会初始化打印速度，即每分钟打印多少页
tick方法会减量计时，并且在执行完任务之后将打印机设置成空闲状态
'''
class Printer:
    def __init__(self,ppm):
        # 每分钟打印几页
        self.pagerate = ppm
        # 当前任务
        self.currentTask = None
        # 执行时间
        self.timeRemaining = 0
   # 打印机执行时间
    def tick(self):
        # 正在执行任务
        if self.currentTask != None:
            # 执行时间-1
            self.timeRemaining = self.timeRemaining -1
            # 任务执行完毕
            if self.timeRemaining <= 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


'''
代表单个打印任务，当任务被创建时，随机数生成器会随机提供页数，取值范围是1-20
每个任务都需要保存一个时间戳，用于计算等待时间
这个时间戳代表任务被创建并放入打印任务队列的时间
waitTime方法可以获得任务在队列中等待的时间
'''
import random
class Task:
    def __init__(self,time):
        # 创建任务的时间戳
        self.timestamp = time
        # 打印任务的页数
        self.pages = random.randrange(1,21)

    def getStamp(self):
        return self.timestamp

    def getPages(self):
        return self.pages

    def waitTime(self,currenttime):
        return currenttime - self.timestamp

'''
printQueue对象是队列抽象数据类型的实例
布尔辅助函数newPrintTask判断是否有新创建的打印任务
使用random模块中的randrange函数来生成随机数：平均180秒就有一个打印任务
该模拟程序允许设置总时间和打印机没分钟打印多少页
'''

# 每180秒一个任务
def newPrintTask():
    num = random.randrange(1,181)
    if num == 180:
        return True
    else:
        return False


def simulation(numSeconds,pagesPerMinute):


    # 创建打印机
    labprinter = Printer(pagesPerMinute)
    # 创建任务对垒
    printQueue = Queue()
    # 等待时间列表
    waitingtimes = []

     # 对于每一秒
    for currentSecond in range(numSeconds):
        # 创建新的任务
        if newPrintTask():
            task = Task(currentSecond)
            # 新到的任务加入队列
            printQueue.enqueue(task)
        # 如果打印机空闲以及任务队列非空
        if (not labprinter.busy()) and (not printQueue.isEmpty()):
            # 新的任务出队列
            nexttask = printQueue.dequeue()
            # 将新任务的等待时间加入到等待时间列表
            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()))


'''
每次模拟的结果不一定相同，60分钟内每分钟打印5页，进行10次这样的模拟
'''
for i in range(10):
    simulation(3600,5)
print("--------")
'''
改成没分钟10页，模拟10次，加快打印速度，一个小时内可以完成更多的任务
'''
for i in range(10):
    simulation(3600,10)

运行结果：
average wait 187.82 secs   2 tasks remaining
average wait 235.67 secs   2 tasks remaining
average wait  91.39 secs   0 tasks remaining
average wait 210.94 secs   0 tasks remaining
average wait  48.24 secs   0 tasks remaining
average wait 127.94 secs   0 tasks remaining
average wait 288.74 secs   0 tasks remaining
average wait 294.70 secs   0 tasks remaining
average wait 112.71 secs   1 tasks remaining
average wait  43.58 secs   1 tasks remaining
--------
average wait  35.18 secs   0 tasks remaining
average wait  18.95 secs   0 tasks remaining
average wait  31.69 secs   0 tasks remaining
average wait  45.33 secs   0 tasks remaining
average wait  22.27 secs   0 tasks remaining
average wait  40.91 secs   0 tasks remaining
average wait   6.06 secs   0 tasks remaining
average wait   5.32 secs   0 tasks remaining
average wait   9.94 secs   0 tasks remaining
average wait  73.03 secs   0 tasks remaining
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

双端队列

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

双端队列有栈和队列的很多特性，但是它不要求按照这两种数据结构分别规定的LIFO原则和FIFO原则操作元素，具体的排序原则取决于使用者。
Deque()：创建一个空的双端队列，不需要参数，返回一个空的双端队列
addFront(item):将一个元素添加到双端队列的前端，它接受一个元素作为参数，没有返回值。
addRear(item)：将一个元素添加到双端队列的后端，它接受一个元素作为参数，没有返回值。
removeFront():从双端队列的前端移除一个元素，不需要参数，返回一个元素，并修改双端队列的内容。
removeRear():从双端队列的后端移除一个元素，不需要参数，返回一个元素，并修改双端队列的内容。
isEmpty():检查双端队列是否为空，返回一个布尔值
size():返回双端队列中元素的数目，不需要参数，但会一个整数

# 双端队列
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)
    def size(self):
        return len(self.items)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

回文检测器

回文是指从前往后读和从后往前读都一样的字符串。
使用一个双端队列来存储字符串中的字符，按从左往右将字符串中的字符添加到双端队列的后端。此时，该双端队列类似于一个普通的队列。利用双端队列的双重性，其前端是字符串的第一个字符，后端是字符串的最后一个字符。

从前后两端移除元素，比较两个元素，并且只有在二者相等的时候才继续。如果一直匹配第一个和最后一个元素，最终会处理完所有的字符，或者剩下只有一个元素的双端队列。

# 回文检测器
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

print(palchecker('toot'))
print(palchecker('lsdkjfskf'))
print(palchecker('radar'))

运行结果：
True
False
True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

列表

列表是元素的集合，其中每一个元素都有一个相对于其他元素的位置。这种列表称为无序列表。

无序列表

List()：创建一个空列表，不需要参数，返回一个空列表
add(item)：假设元素item之前不在列表中，并向其添加item,它接受一个元素作为参数，无返回值。
remove(item)：假设元素item已经在列表中，并从中移除item。它接受一个元素作为参数，并且修改列表。
search(item)：在列表中搜索元素item，它接受一个元素作为参数，并且返回布尔值。
isEmpty()：检查列表是否为空，不需要参数，返回一个布尔值。
length()：返回列表中元素的个数。
append(item)：假设元素不在列表中，在列表的最后位置添加item.接受一个元素作为参数，无返回值。
index(item)：假设元素item已在列表中，并返回该元素在列表中的位置。接受一个元素作为参数，并返回该元素的下标。
insert(pos,item):假设元素不在列表中，同时pos是合理的值，并在pos位置处添加item元素。它接受两个参数，无返回值。
pop():列表不为空，移除列表的最后一个元素，不需要参数，返回一个元素
pop(pos):假设指定位置pos存在元素，移除该位置上的元素，接受位置参数且返回一个元素。
为了实现无序列表，构建链表。无序列表需要维护元素之间的相对位置，但是并不需要在连续的内存空间中维护这些位置信息。

必须指明列表中第一个元素的位置。一旦直到第一个元素的位置，就能根据其中的链接信息访问第二个元素，接着访问第三个元素。指向链表第一个元素的引用被称为投，最后一个元素需要直到自己没有下一个元素。
节点是构建链表的基本数据机构，每一个节点对象都必须持有至少两份信息。节点必须包含列表元素，称之为节点的数据变量，节点必须保存指向下一个节点的引用。构建节点时，需要为其提供初始值。

# Node类
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 setDat(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

'''
无序列表是基于节点集合来创建的，每一个节点都通过显示的引用指向下一个节点
只要知道第一个节点的位置，其后的每一个元素都能通过下一个引用找到
必须包含指向第一个节点的引用
特殊引用值None用于表明列表的头部没有指向任何节点

列表是无序的，新元素相对于已有元素的位置不重要
新的元素可以在任意的位置，将新元素放在最简便的位置是最合理的选择
把新元素放在列表的第一个元素，并把已有的元素链接到该元素的后面
'''
class UnorderesList:
    def __init__(self):
        self.head = None

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

    def add(self,item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

    '''
    遍历是系统的访问每一个节点，用一个外部引用从列表的头节点开始访问
    随着访问每一个节点，将这个外部引用通过遍历下一个引用来指向下一个节点
    '''

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

        return count

    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总是指向current上一次访问的节点
    如果移除的元素恰好是链表的第一个元素，修改链表的头节点
    '''
    def remove(self,item):
        current = self.head
        previous = None
        found = False
        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())
    
myList = UnorderesList()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

有序列表

在有序列表中，元素的相对位置取决于它们的基本特征，通常以升序或降序排雷，并且假设元素之间能进行有意义的比较。
orderList():创建一个空有序列表，不需要参数，会返回一个空列表
add(item):假设item之间不在列表中，向其添加item,同时保证整个列表的顺序。
remove(item):假设item已经在列表中，从其中移除item，接受一个元素作为参数，并且修改列表
search(item):在列表中搜索item,接受一个元素作为参数，并且返回布尔值
isEmpty()：检查列表是否为空，不需要参数，返回布尔值
length()：返回列表中元素的个数，不需要参数，返回一个整数值
index(item)：假设item已在列表中，返回该元素在列表中的位置，接受一个元素作为参数，返回该元素的下标。
pop()假设不为空，移除列表中的最后一个元素
pop(pos):假设指定位置pos存在元素，移除该位置上的元素，接受位置参数返回一个元素。

# 有序列表
class OrderedList:
    def __init__(self):
        self.head = None

    '''
    isEmpty和Length仅与列表中的节点数目有关，与实际的元素值没有关系
    有序和无序的实现是一样的
    需要找到目标元素并且通过更改链接来移除节点，remove()方法也是一样的
    '''
    # 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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44