算法基础_Third_Chapter

链表

1、单向链表

1.1、单向链表的操作

链表节点：

1.2、单链表定义和方法实现

class Node(): #定义结点，结点包括数值域和地址域 def __init__(self,elem): self.elem = elem self.next = None class SingleLinkList(): #创建单链表 def __init__(self,node=None): self.__head = node # 初始化头结点，默认为None，空对象 def is_empty(self): return self.__head == None # 头结点为None，即不指向任何元素，指向空对象，即无元素 def length(self): #cur为游标，遍历整个列表 cur = self.__head #cur为游标，指向self.head所指向的对象地址即头结点 count = 0 while cur != None: count += 1 #指向下一个结点(cur.next所指向对象即下个结点，# cur即指向下个结点) cur = cur.next return count # 判断下个结点是否存在，例只有如一个结点，则cur指向该头结点，count+1=1,count_next=None def travel(self): cur = self.__head while cur != None: print(cur.elem,end=" ") cur = cur.next # cur从头结点开始，一直到None之前的结点为止 def add(self,item): #首位插入元素 node = Node(item) #Node初始化，创建结点 node.next = self.__head #node.next指向头结点的地址 self.__head = node #头结点指向现在的首位结点 #Note:不能破坏单链表的后边的连接性，例如头结点指向新结点，新结点再指向原来的头结点，指针会找不到位置 def append(self,item): #最后添加元素 node = Node(item) if self.is_empty(): #若为空，则头结点指向现在结点即可 self.__head=node else: cur = self.__head #cur游标指向头结点 while cur.next !=None: #cur.next！=None,说明后边还有结点 cur = cur.next cur.next = node # cur = cur.next，cur指向下个结点（cur.next对象是下个结点，下个结点地址赋给cur），当到了最后一个退出循环，最后一个节点cur.next指向新结点 def insert(self,pos,item): if pos < 0: self.add(item) elif pos>(self.length()-1): self.append(item) else: pre = self.__head # pre同指针，相当于cur前一个，因为从pos位置前一个插入 count = 0 while count < (pos-1): # 指针挪一次，count+1，同步的，因此不能小于等于，等于的话会进入pos位置 count += 1 pre = pre.next #当循环退出后pre指向pos-1位置 node = Node(item) #仍然创建结点 node.next = pre.next #node.next指向原pos位置结点 pre.next = node # 原pos-1位置结点的指针区域pre.next指向现在结点node # def remove(self,item): # node = Node(item) # if self.search(item): # cur = self.__head # count = 0 # while cur != None: # if cur.elem == item: # break # cur = cur.next # count+=1 # if count==self.length()-1: # pre = self.__head # for pos in range(count-1): # pre = pre.next # pre.next = cur.next #pre=cur.next，pre没被替代？？？ # pre = None # else: # pre = self.__head # for pos in range(count-1): # pre = pre.next # pre.next = cur.next #pre=cur.next，pre没被替代？？？ # # pre = cur.next # else: # print("异常") def remove(self, item): node = Node(item) cur = self.__head pre = None while cur!=None: if cur.elem == item: #判断此节点是否是头结点 if pre == None: self.__head=cur.next else: pre.next = cur.next break else: pre = cur cur = cur.next def search(self,item): node = Node(item) cur = self.__head while cur!=None: if cur.elem == item: #此处用item，node中self.elem属性 return True else: cur = cur.next return False if __name__ == "__main__": ll = SingleLinkList() print(ll.is_empty()) print(ll.length()) ll.append(1) print(ll.is_empty()) print(ll.length()) ll.append(2) ll.add(8) ll.append(3) ll.append(4) ll.append(5) ll.append(6) ll.insert(3,6) ll.insert(100,23) ll.travel() # print(ll.search(2)) ll.remove(6) ll.travel()

1.3 链表与顺序表的对比

顺序表存取元素可通过访问地址一次定位（内存连续），发生动态改变，存储区需要改变，当存储量庞大无足够内存空间则无法解决。 链表的内存空间分散，利用空间增大，但是因为存储数值域和指针域，内存消耗增加，存取元素需用指针从前向后遍历。 时间复杂度：链表用于遍历，顺序表用于数据搬迁。

2、双向链表

2.1 双向链表的结构

2.2 双向链表的操作

class Node(): def __init__(self,item): self.elem = item self.next = None self.prev = None class DoubleLinklist(): def __init__(self, node=None): self.__head = node def is_empty(self): return self.__head == None def length(self): cur = self.__head count = 0 while cur != None: count += 1 cur = cur.next return count def travel(self): cur = self.__head while cur != None: print(cur.elem, end=" ") cur = cur.next def add(self, item): node = Node(item) node.next = self.__head self.__head = node if node.next: node.next.prev = node def append(self, item): node = Node(item) if self.is_empty(): self.__head = node else: cur = self.__head while cur.next != None: cur = cur.next cur.next = node node.prev = cur def insert(self, pos, item): if pos < 0: self.add(item) elif pos > (self.length() - 1): self.append(item) else: cur = self.__head count = 0 while count < pos: count += 1 cur = cur.next node = Node(item) node.next = cur node.prev = cur.prev cur.prev.next = node cur.prev = node def remove(self, item): node = Node(item) cur = self.__head while cur != None: if cur.elem == item: if cur == self.__head: self.__head = cur.next if cur.next != None: cur.next.prev = None else: cur.prev.next = cur.next if cur.next: cur.next.prev = cur.prev break else: cur = cur.next def search(self, item): node = Node(item) cur = self.__head while cur != None: if cur.elem == item: return True else: cur = cur.next return False if __name__ == "__main__": dll = DoubleLinklist() dll.append(1) dll.append(2) dll.append(5) dll.append(6) dll.insert(3,3) dll.travel() print() dll.remove(3) dll.travel()

2.3 单向循环列表

class Node(): def __init__(self,elem): self.elem = elem self.next = None class SingleLinkList(): def __init__(self,node=None): self.__head = node if node: node.next = node def is_empty(self): return self.__head == None def length(self): cur = self.__head if self.is_empty(): return 0 else: count = 1 while cur.next != self.__head: count += 1 cur = cur.next return count def travel(self): cur = self.__head if self.is_empty(): return else: while cur.next != self.__head : print(cur.elem,end=" ") cur = cur.next #尾结点未打印 print(cur.elem) def add(self,item): node = Node(item) if self.is_empty(): self.__head = node node.next = node else: cur = self.__head while cur.next != self.__head: cur = cur.next node.next = self.__head self.head = node cur.next = node def append(self,item): node = Node(item) if self.is_empty(): self.__head=node node.next = node else: cur = self.__head while cur.next != self.__head: cur = cur.next cur.next = node node.next = self.__head def insert(self,pos,item): if pos < 0: self.add(item) elif pos>(self.length()-1): self.append(item) else: pre = self.__head count = 0 while count < (pos-1): count += 1 pre = pre.next node = Node(item) node.next = pre.next pre.next = node def remove(self, item): cur = self.__head pre = None if self.is_empty(): return else: while cur.next!=self.__head: if cur.elem == item: if cur == self.__head: rear = self.__head while rear.next != self.__head: rear = rear.next self.__head = cur.next rear.next = self.__head else: pre.next = cur.next return else: pre = cur cur = cur.next if cur.elem == item: if cur == self.__head: self.__head = None else: pre.next = cur.next def search(self,item): if self.is_empty(): return False else: cur = self.__head while cur.next != self.__head: if cur.elem == item: return True else: cur = cur.next if cur.elem == item: return True return False if __name__ == "__main__": ll = SingleLinkList() # print(ll.is_empty()) # print(ll.length()) ll.append(1) # print(ll.is_empty()) # print(ll.length()) ll.append(2) ll.add(1) ll.append(3) ll.append(4) ll.insert(3,6) ll.insert(100,23) # print(ll.search(2)) ll.remove(6) print() ll.travel() ll.remove(23) ll.travel() ll.remove(1) ll.travel()