class SingleNode(object):
""" Single node """
def __init__(self, item):
# item Storing data elements
self.item = item
# next Is the identity of the next node ( The pointer )
self.next = None
class SingleLinkList(object):
""" Single chain list """
# Empty single linked list self.__head = None
# Non empty single linked list self.__head = node
def __init__(self, node=None):
self.__head = node
def is_empty(self):
""" Judge whether the list is empty """
if self.__head == None:
return True
else:
return False
# return self.__head == None
def length(self):
""" Chain length """
# In the case of an empty linked list
# cur The cursor Point to the head node Used to traverse the
cur = self.__head # None
count = 0
while cur != None:
count += 1
# Move the cursor back one bit
cur = cur.next
return count
def travel(self):
""" Traverse the entire list """
cur = self.__head
while cur != None:
# Data in node
print(cur.item, end=' ')
cur = cur.next
print("")
def append(self, item):
""" Add elements at the end of the list """
# item The specific data you want to insert
node = SingleNode(item)
# Consider the empty linked list
if self.is_empty():
self.__head = node
else:
cur = self.__head # None node
# AttributeError: 'NoneType' object has no attribute 'next'
while cur.next != None:
# Find the last node
cur = cur.next
cur.next = node
def add(self, item):
""" Add elements to the head of the linked list """
# item The specific data you want to insert
node = SingleNode(item)
# The link area of the new node next Point to the head node
node.next = self.__head
# Point the head of the linked list to the new node
self.__head = node
def insert(self, pos, item): # insert(2,100) insert(-1,100) insert(10,100)
""" Add elements at specified locations """
# item The specific data you want to insert
# Head insertion
if pos <= 0:
self.add(item)
# Tail insertion
elif pos > self.length()-1:
self.append(item)
else:
# Insert... At specified location
node = SingleNode(item)
pre = self.__head
count = 0
while count < (pos - 1):
count += 1
pre = pre.next
node.next = pre.next
pre.next = node
def remove(self, item):
""" Delete node """
# remove(100) [100,200,100] Delete one 100
cur = self.__head # Empty list None
pre = None
while cur != None:
# The specified element was found
if cur.item == item:
# Delete first element
if cur == self.__head:
self.__head = cur.next
else:
# Delete
pre.next = cur.next
break
else:
# Keep moving
pre = cur
cur = cur.next
def search(self, item):
""" Find if the node exists """
cur = self.__head
while cur != None:
if cur.item == item:
return True
else:
# Let the cursor continue execution
cur = cur.next
return False
s = SingleLinkList()
""" test result """
print(s.is_empty()) # Whether the single linked list is empty
print(s.length()) # The length of a single list
# Add five data to the end of the single linked list
s.append(10)
s.append(23)
s.append(13)
s.append(5)
s.append(34)
print(s.is_empty())
print(s.length())
s.travel() # Traversing a single linked list
# Insert data into the specified location
s.insert(-1, 6)
s.insert(10, 77)
s.insert(2, 11)
s.insert(1, 33)
s.travel()
print(s.search(77)) # Find data 77 Is it in a single linked list
s.remove(33) # Delete data 33
s.travel() # Traverse the single linked list again
One way circular list
class Node(object):
""" node """
def __init__(self, item):
# item Storing data elements
self.item = item
# next Is the identity of the next node ( The pointer )
self.next = None
class SinCycLinkList(object):
""" Single circular list """
# Empty single linked list self.__head = None
# Non empty single linked list node.next = node
def __init__(self, node=None):
self.__head = None
if node:
node.next = node
def is_empty(self):
""" Judge whether the list is empty """
if self.__head == None:
return True
else:
return False
def length(self):
""" Return the length of the list """
# In the case of an empty linked list
if self.is_empty():
return 0
# cur The cursor Point to the head node Used to traverse the
cur = self.__head # None
# is object == Is the value equal
count = 1
while cur.next != self.__head:
count += 1
# Move the cursor back one bit
cur = cur.next
return count
def travel(self):
""" Traverse """
# Empty list
if self.is_empty():
return None
cur = self.__head
while cur.next != self.__head:
# Data in node
print(cur.item, end=' ')
cur = cur.next
# When you exit the loop ,cur Point to the tail node , But the tail node is not printed
print(cur.item)
def add(self, item):
""" Add elements to the head of the linked list """
# item The specific data you want to insert
node = Node(item)
# Empty list
if self.is_empty():
self.__head = node
node.next = self.__head
else:
cur = self.__head # None
while cur.next != self.__head:
cur = cur.next
# Find the tail node
# The added node points to the original head node
node.next = self.__head
# __head Point to node
self.__head = node
# The tail node points to the new node
cur.next = node
def append(self, item):
""" Add elements at the end of the list """
node = Node(item)
# Empty list
if self.is_empty():
self.__head = node
node.next = self.__head
else:
cur = self.__head
while cur.next != self.__head:
cur = cur.next
# Find the tail node
# Point the tail node to node
cur.next = node
# take node Point to __head
node.next = self.__head
def insert(self, pos, item):
""" Add elements at specified locations """
# Head insertion
if pos <= 0:
self.add(item)
# Tail insertion
elif pos > self.length() - 1:
self.append(item)
else:
# Insert... At specified location
node = Node(item)
cur = self.__head
count = 0
while count < (pos - 1):
count += 1
cur = cur.next
node.next = cur.next
cur.next = node
def search(self, item):
""" Find if the node exists """
if self.is_empty():
return False
cur = self.__head
while cur.next != self.__head:
if cur.item == item:
return True
else:
# Let the cursor continue execution
cur = cur.next
# Loop exit cur Point to the tail node
if cur.item == item:
return True
return False
def remove(self, item):
""" Delete node """
# Empty list
if self.is_empty():
return
cur = self.__head
pre = None
# The element of the head node is the element to be deleted
if cur.item == item:
# There is more than one node in the linked list
if cur.next != self.__head:
while cur.next != self.__head:
cur = cur.next
# The loop ends cur Point to the tail node
cur.next = self.__head.next
self.__head = cur.next
else:
self.__head = None
# The first node is not to be deleted
else:
while cur.next != self.__head:
if cur.item == item:
# Delete
pre.next = cur.next
return
else:
# The cursor continues down
pre = cur
cur = cur.next
if cur.item == item:
pre.next = cur.next
s = SinCycLinkList()
""" test result """
print(s.is_empty()) # Judge whether it is an empty list
print(s.length()) # Judge the length of the linked list
s.add(1) # Add data to the header
s.add(2)
s.add(3)
s.add(4)
s.append(6) # Add data to the tail
s.append(8)
s.travel() # Traversing a one-way circular list
s.insert(2, 7) # Insert data in the specified location
s.insert(2, 7)
s.travel() # Traversing a one-way circular list
s.remove(6) # Delete data
s.remove(7)
s.travel() # Traverse... Again
Double linked list
class Node(object):
""" node """
def __init__(self, item):
# item Storing data elements
self.item = item
# next Is the identity of the next node
self.next = None
# perv Is the representation of the previous node
self.prev = None
class DoubleLinkList(object):
""" Double linked list """
def __init__(self, node=None):
self.__head = node
def is_empty(self):
""" Judge whether the list is empty """
if self.__head == None:
return True
else:
return False
def length(self):
""" Return the length of the list """
# In the case of an empty linked list
if self.is_empty():
return 0
# cur The cursor Point to the head node Used to traverse the
cur = self.__head
# is object == Is the value equal
count = 0
while cur != None:
count += 1
# Move the cursor back one bit
cur = cur.next
return count
def travel(self):
""" Traverse """
# Empty list
if self.is_empty():
return None
cur = self.__head
while cur != None:
# Data in node
print(cur.item, end=' ')
cur = cur.next
print("")
# When you exit the loop ,cur Point to None
def add(self, item):
""" Add elements to the head of the linked list """
# item The specific data you want to insert
node = Node(item)
if self.is_empty():
self.__head = node
else:
# take node Of next Point to __head The head node of
node.next = self.__head
# take __head Of the head node prev Point to node
self.__head.prev = node
# take __head Point to node
self.__head = node
def append(self, item):
""" Add elements at the end of the list """
# item The specific data you want to insert
node = Node(item)
# Consider the empty linked list
if self.is_empty():
self.__head = node
else:
cur = self.__head # None node
while cur.next != None:
# Find the last node
cur = cur.next
# After the end of the cycle ,cur Point to the tail node
cur.next = node
node.prev = cur
def insert(self, pos, item): # insert(2,100) insert(-1,100) insert(10,100)
""" Add elements at specified locations """
# item The specific data you want to insert
# Head insertion
if pos <= 0:
self.add(item)
# Tail insertion
elif pos > self.length()-1:
self.append(item)
else:
# Insert... At specified location
node = Node(item)
cur = self.__head
count = 0
while count < (pos - 1):
count += 1
cur = cur.next
# The loop ends , Find the previous node at the insertion location
# take node Of prev Point to cur
node.prev =cur
# take node Of next Point to cur Next node of
node.next = cur.next
# take cur The next node of prev Point to node
cur.next.prev = node
# take cur Of next Point to node
cur.next = node
def search(self, item):
""" Find if the node exists """
cur = self.__head
while cur != None:
if cur.item == item:
return True
else:
# Let the cursor continue execution
cur = cur.next
return False
def remove(self, item):
""" Delete node """
# remove(100) [100,200,100] Delete one 100
if self.is_empty():
return
else:
cur = self.__head # Empty list None
# If the element of the first node is the element to be deleted
if cur.item == item:
print(1)
# If the linked list has only one node
if cur.next == None:
self.__head = None
else:
cur.next.prev = None
self.__head = cur.next
return
while cur != None:
if cur.item == item:
print(2)
cur.prev.next = cur.next
if cur.next:
cur.next.prev = cur.prev
break
cur = cur.next
d = DoubleLinkList()
""" test result """
print(d.is_empty())
print(d.length())
d.add(1)
d.add(2)
d.add(3)
d.append(4)
d.append(10)
d.travel()
d.insert(-1, 0)
d.insert(-5, 0)
d.travel()
Stack
class Stack(object):
""" Use list to realize stack """
def __init__(self):
self.__items = []
def is_empty(self):
""" Judge whether the stack is empty """
if self.__items == []:
return True
else:
return False
# return self.__items == []
def push(self, item):
""" Add a new element item To the top of the stack """
self.__items.append(item)
# self.__items.insert(0, item)
def pop(self):
""" Pop up top element """
return self.__items.pop()
def peek(self):
""" Back to top of stack element """
if self.is_empty():
return None
else:
return self.__items[-1]
# return self.__items[len(self.__items)-1]
def size(self):
""" Returns the number of stack elements """
return len(self.__items)
def travel(self):
""" Traverse """
print(self.__items)
# for item in self.__items:
# print(item)
s = Stack()
""" test result """
print(s.is_empty())
s.push(1)
s.push(2)
s.push(3)
s.pop() # Pop up the top of the stack item 3
s.travel()
print(s.size())
print(s.is_empty())
print(s.peek()) # Back to the top of the stack item Instead of popping up
s.travel()
queue
class Queue(object):
def __init__(self):
self.__items = []
def enqueue(self, item):
self.__items.append(item)
def dequeue(self):
""" Delete an element from the head of the queue :return: Queue header element """
return self.__items.pop(0)
def is_empty(self):
""" Determine whether a queue is empty :return: True or False """
return self.__items == []
def size(self):
return len(self.__items)
def travel(self):
""" Traverse """
# print(self.__items)
for item in self.__items:
print(item, end=' ')
print('')
q = Queue()
""" test result """
print(q.is_empty())
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.travel()
q.dequeue() # Team leader item Out of the team
q.travel() # Traverse... Again
Bubble sort
def bu_sort(lis):
n = len(lis)
for j in range(n-1):
for i in range(0, n-1-j):
if lis[i] > lis[i + 1]:
lis[i], lis[i + 1] = lis[i + 1], lis[i]
Selection sort
""" First, find the smallest element in the unlisted sequence Put it at the beginning of the arranged sequence Then continue to look for the smallest element in the unlined sequence Add to the end of the ordered sequence And so on , Until all the elements are sorted . """
def selection_sort(lis):
n = len(lis)
for i in range(n-1):
# Record the location of the minimum
min_index = i
# from min_index Find the minimum value from the position to the end Find the subscript of the minimum
for j in range(min_index, n):
if lis[j] < lis[min_index]: # lis[1] < lis[0] 26 < 54 min_index = 1
min_index = j
lis[i], lis[min_index] = lis[min_index], lis[i]
Insertion sort
""" First, divide the data in the array into two intervals Sorted and unsorted intervals The initial ordered interval has only one element Is the first element of the array The core idea of insertion sorting is to take the elements in the unordered interval Find a suitable insertion position in the sorted interval and insert it into And ensure that the sorted interval data is always in order Repeat the process , Until the element in the unordered interval is empty , The algorithm ends """
def insert_sort(lis):
n = len(lis)
# From the second position , That is, the subscript is 1 Insert forward at the beginning of
for i in range(1, n):
# From i Elements Compare forward If it's smaller than the previous element In exchange for
for j in range(i, 0, -1):
if lis[j] < lis[j - 1]:
lis[j], lis[j - 1] = lis[j - 1], lis[j]
Shell Sort
def shell_sort(lis):
n = len(lis)
gap = n//2 # python2 python3 There is a difference
while gap > 0:
for i in range(gap, n):
while i >= gap and lis[i-gap] > lis[i]:
lis[i-gap], lis[i] = lis[i], lis[i-gap]
i -= gap
gap = gap//2
Quick sort
def quick_sort(lis, start, end):
if start >= end:
return
mid = lis[start]
low = start
high = end
# Loop exit low = high
while low < high:
while low < high and lis[high] >= mid:
high -= 1
lis[low] = lis[high]
while low < high and lis[low] < mid:
low += 1
lis[high] = lis[low]
lis[low] = mid
quick_sort(lis, start, low-1)
quick_sort(lis, low+1, end)
lis = [9, 21, 43, 27, 67, 31, 49, 55, 20]
quick_sort(lis, 0, len(lis)-1)
Merge sort
""" Combine two ordered arrays after decomposing the array to the smallest The basic idea is to compare the first two arrays Take the first one who is small , After taking the corresponding pointer, move it back one bit Then compare , Until an array is empty , Finally, copy the rest of another array . """
def merge_sort(lis):
if len(lis) <= 1:
return lis
# Dichotomy
mid_index = len(lis) // 2
left_lis = merge_sort(lis[:mid_index])
right_lis = merge_sort(lis[mid_index:])
l_index = 0
r_index = 0
result = []
while l_index < len(left_lis) and r_index < len(right_lis):
if left_lis[l_index] < right_lis[r_index]:
result.append(left_lis[l_index])
l_index += 1
else:
result.append(right_lis[r_index])
r_index += 1
result += left_lis[l_index:]
result += right_lis[r_index:]
return result # Return to the sorted list
lis = [14, 26, 63, 17, 77, 31, 44, 55, 20]
s = merge_sort(lis)
