前言
最近开始学数据结构，打算用python作为语言，看的书是米勒和戴维的《Python数据结构与算法分析》。目前大三，希望能一个月速成，奥利给！！注意到课本中的练习题没有参考答案，我自己写了一份放到这上面，更详细，完整的代码在我的github：https://github.com/Yunzz-goon/PythonForDataStructure
欢迎大家一起交流！！！
——————————————————————————
第二章讲的是时间复杂度，因为很多地方需要plot，我打算先埋个伏笔，等到自己的matlibplot博客开始了再穿插到那边。Anyway，第三章讲了几种数据结构：栈，队列，双端队列，链表。整体看下来觉得原理不难，难的是怎么coding出这些实例（如打印机那一块我看得头疼）。
一、课后习题
由于时间有限，我只做了部分较容易的习题。
- 问题13: 要我们把节点个数储存在表头中，可以通过增删操作的时候不断修改表头数据来实现，增删包括add，remove，pop等。
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
class UnorderedList:
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def add(self,item,count):
temp = Node(item)
temp.setNext(self.head)
self.head = temp
count = count+1
return count
def count2head(self,count):
self.head.setData(count)
def length(self):
return self.head.getData()
"""
方法：确认元素item是否在链表中
Input：元素
Output：布尔值
"""
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
"""
方法：移除某个链表中的item,且不假设这个元素一定在链表中（比课本中的情况更加general）
Input：item
Output：None；但是链表改变
"""
def remove(self,item):
current = self.head
previous = None
found = False
while not found and current != None:
if current == None:
print('Error!!!Item is not in List!!!')
else:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
self.head.setData(self.head.getData()-1)
mylist = UnorderedList()
countt=0
countt=mylist.add(31,countt)
countt=mylist.add(77,countt)
countt=mylist.add(17,countt)
countt=mylist.add(93,countt)
countt=mylist.add(26,countt)
countt=mylist.add(54,countt)
print(countt)
mylist.count2head(countt)
mylist.remove(93)
print(mylist.search(93))
print(mylist.length())
- 问题14: 在问题13中已经给出。
- 问题16: 要我们把Unorderlist类中的元素（即列表）打印出来
"""
类：节点-----包含了修改和访问数据的方法，以及指向下一个节点的引用
Input：节点初始值
Output：一个节点
"""
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
"""
类：无序列表（特殊的链表）
"""
class UnorderedList:
def __init__(self):
self.head = None
def __str__(self):
current = self.head
ss=""
while current != None:
s = str(current.getData())
current=current.getNext()
ss=ss+s+","
return ss
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 += 1
current = current.getNext()
return count
"""
方法：确认元素item是否在链表中
Input：元素
Output：布尔值
"""
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
"""
方法：移除某个链表中的item,假设这个元素一定在链表中
Input：item
Output：None；但是链表改变
"""
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 = UnorderedList()
mylist.add(31)
mylist.add(77)
mylist.add(17)
mylist.add(93)
mylist.add(26)
mylist.add(54)
print(mylist.__str__())
- 问题18: 实现无序列表的方法：append，index，pop，insert
"""
类：节点-----包含了修改和访问数据的方法，以及指向下一个节点的引用
Input：节点初始值
Output：一个节点
"""
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
"""
类：无序列表（特殊的链表）
"""
class UnorderedList:
def __init__(self):
self.head = None
def __str__(self):
current = self.head
ss=""
while current != None:
s = str(current.getData())
current=current.getNext()
ss=ss+s+","
return ss
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 += 1
current = current.getNext()
return count
"""
方法：确认元素item是否在链表中
Input：元素
Output：布尔值
"""
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
"""
方法：移除某个链表中的item,假设这个元素一定在链表中
Input：item
Output：None；但是链表改变
"""
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())
def append(self,item):
current = self.head
previous = None
while current != None:
previous = current
current = current.getNext()
previous.setNext(Node(item))
def insert(self, pos, item):
current = self.head
for indexx in range(0,pos-1):
current = current.getNext()
temp = Node(item)
temp.setNext(current.getNext())
current.setNext(temp)
def index(self,item):
positionn = -1
current = self.head
while current.getData() != item:
current = current.getNext()
positionn = positionn+1
return positionn
def pop(self):
current = self.head
previous = None
while current.getNext() != None:
previous = current
current = current.getNext()
previous.setNext(None)
return current.getData
def pop2(self,pos):
current = self.head
for indexx in range(0,pos):
current = current.getNext()
Next=current.getNext()
current.setNext = (current.getNext()).getNext()
Next.setNext(None)
mylist = UnorderedList()
mylist.add(31)
mylist.add(77)
mylist.add(17)
mylist.add(93)
mylist.add(26)
mylist.add(54)
print(mylist.length())
print(mylist.search(93))
mylist.remove(93)
print(mylist.search(93))
print(mylist.length())
mylist.append(11)
print(mylist.length())
mylist.insert(2,4)
print(mylist.length())
mylist = UnorderedList()
mylist.add(31)
mylist.add(77)
mylist.add(17)
mylist.add(93)
mylist.add(26)
mylist.add(54)
mylist.index(17)
print(mylist.length())
mylist.pop()
print(mylist.length())
mylist.pop2(2)
print(mylist.length())
print(mylist.search(77))
- 问题22: 使用链表实现栈
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
"""
类：用链表创建栈（包含了栈的所有运算）
Input：none
Output：一个栈（列表）
假设列表的头部是栈的顶端
"""
class Stack:
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 pop(self):
current = self.head
previous = None
while current.getNext() != None:
previous = current
current = current.getNext()
previous.setNext(None)
return current.getData
def peek(self):
current = self.head
previous = None
while current.getNext() != None:
previous = current
current = current.getNext()
return current
def length(self):
current = self.head
count = 0
while current != None:
count += 1
current = current.getNext()
return count
if __name__=="__main__":
s=Stack()
print(s.isEmpty())
s.add(4)
print(s.__str__())
s.add('dog')
s.add('True')
print(s.__str__())
print(s.length())
print(s.isEmpty())
s.add(8.4)
print(s.__str__())
print(s.pop())
print(s.__str__())
问题23，24: 与22非常类似，可参考https://blog.csdn.net/zyzzzz222/article/details/118914199?spm=1001.2014.3001.5502 中的队列和双端队友的类的定义方式。
|