Basic data structure
1. Linear structure
-
Definition of linear structure: linear structure is a set of ordered data items, in which each data item has a unique precursor and successor
Except for the first one, there is no precursor, and the last one has no successor
When a new data item is added to the data set, it will only be added to the data set with this property before or after the original data item, which is called linear structure -
Linear structure always has two ends. In different cases, the names of the two ends are also different
Left and right ends, front and rear ends, top and bottom ends -
The address at both ends is not the key. The key difference between different linear structures lies in the way data items are increased or decreased (some structures only allow data items to be added from one end, while others allow data items to be removed from both ends)
-
The four simplest but powerful structures: Stack, Queue, Deque and List
What these data sets have in common is that there is only a sequential relationship between data items, which is a linear structure
1. Stack abstract data type and Python implementation
- Stack: an ordered collection of data items. In the stack, the addition and removal of data items occur only at the same end. This end is called the "top" of the stack, and the other end is called the "bottom base" of the stack
- Stack: last in first out (LIFO). The closer the data item is to the bottom of the stack, the longer it will stay in the stack
- Stack characteristics: reverse order
The order of entering and leaving the stack is exactly the opposite
We have encountered this feature of reverse access order in some computer operations
Browser Back back"Button, first back Is the most recently visited web page Word Yes“ Undo" Button. The most recent operation is cancelled first
- Stack operation in python
Stack(): Create an empty stack without any data items push(item): take item Added to the top of the stack, no return value pop(): The data item at the top of the stack is removed and returned, and the stack is modified peek(): " Peep "stack top data item, return the data item at the top of the stack but do not remove it, and the stack will not be modified isEmpty(): Returns whether the stack is empty size(): Returns how many data items are in the stack
Implementing ADT Stack with Python
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(0, item)
def pop(self):
return self.items. pop(0)
def peek(self):
return self.items[0]
def size(self) :
return len(self.items )
Another implementation of ADT Stack
❖ different implementation schemes maintain the stability of ADT interface, but the performance is different. The complexity of push/pop is O(n) for the version at the top and end of the stack (upper), while the complexity of push/pop is O(1) for the implementation at the top and end of the stack (lower)
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 )
- Application of stack
- Simple bracket matching
Scan the bracket string from left to right. The newly opened left bracket should match the first encountered right bracket. In this way, the first left bracket (first opened) should match the last right bracket (last encountered). This identification of reverse order is just in line with the characteristics of the stack - Convert decimal to binary
Binary conversion adopts the "divide by 2 for remainder" algorithm. Divide integers by 2 continuously, and the remainder obtained each time is the binary bits from low to high. In the "divide by 2" process, the remainder obtained is in the order from low to high, while the output is from high to low, so a stack is required to reverse the order
2. Queue abstract data type and Python implementation
- Queue is an ordered data set, which is characterized in that the addition of new data items always occurs at one end (usually referred to as the "tail rear" end) and the removal of existing data items always occurs at the other end (usually referred to as the "front" end)
When the data item is added to the queue, it first appears at the end of the queue. With the removal of the data item at the head of the queue, it gradually approaches the head of the queue - The principle of this order arrangement is called (FIFO: first in first out) first in first out or "first come first served"
- The abstract data type Queue is defined by the following operations:
Queue(): Create an empty queue object with a return value of Queue Object; enqueue(item): Add data item item Added to the end of the queue, no return value; dequeue(): Remove the data item from the queue head, the return value is the queue head data item, and the queue is modified; isEmpty(): Test whether the queue is empty, and the return value is Boolean size(): Returns the number of data items in the queue.
Python implements ADT Queue
# List is used to hold the data items of the Queue
# Take the first end of the List as the end of the queue, and the end of the List as the first end of the queue
# enqueue() complexity is O(n),dequeue() complexity is O(1)
#The complexity of the implementation is reversed
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)
3. Double ended queue abstract data type and Python implementation
- Deque is an ordered data set, which is similar to a queue. Its two ends can be called "head" and "tail", but data items in deque can be added from the head of the queue or from the tail of the queue; data items can also be removed from both ends. In a sense, deque integrates the capabilities of stack and queue
- However, double ended queues do not have inherent LIFO or FIFO characteristics
- deque defined actions
Deque(): Create an empty double ended queue addFront(item): take item Join the team leader addRear(item): take item Join the tail of the team removeFront(): Remove the data item from the queue leader, and the return value is the removed data item removeRear(): Remove the data item from the end of the queue, and the return value is the removed data item isEmpty(): return deque Is it empty size(): return deque Number of data items contained in
Python implements ADT Deque
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)
4. List
- A dset in which data items are stored in relative positions
1. Abstract data type: unordered table List
- Operation of unordered List
List(): Create an empty list
add(item): Add a data item to the list, assuming item It didn't exist in the list
remove(item): Remove from list item，The list has been modified, item It should have existed in the table
search(item): Find in list item，Returns a Boolean value
isEmpty(): Returns whether the list is empty
size(): Returns how many data items the list contains
append(item): Add a data item to the end of the table, assuming item It didn't exist in the list
index(item): Returns the position of the data item in the table
insert(pos,item): Insert data item into location pos，hypothesis item It didn't exist in the list,
At the same time, the original list has enough data items to make item Occupy position pos
pop(): Remove data items from the end of the list, assuming that the original list has at least 1 data item
pop(pos): Remove at pos Assuming that the original list exists pos
2. Use linked list to realize unordered list
- In order to realize the data structure of unordered table, the scheme of linked table can be adopted.
- Although the list data structure requires to maintain the front and rear relative positions of data items, the maintenance of this front and rear position does not require the data items to be stored in a continuous storage space in turn
- The most basic element of the linked list implementation is the Node. Each Node must contain at least two information: the data item itself and the reference information pointing to the next Node
Note that there is no next node when next is None, which is very important - Linked list implementation: 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 setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
# You can link nodes to build data sets to implement unordered tables
"""The first and last nodes of the linked list are the most important if you want to access the linked list
All nodes must be traversed along the link from the first node"""
"""Therefore, the unordered table must have reference information to the first node
Set up a property head，Save a reference to an empty table for the first node head by None"""
class UnorderedList:
def __init__(self):
self.head = None
#With the addition of data items, the head of the unordered table always points to the first node in the chain
"""Unordered table mylist The object itself does not contain data items
(Data item (in node)
Which contains head Only for the first node Node Reference to"""
# Implementation of isEmpty add size search remove method
class UnorderedList:
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 size(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
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())
3. Abstract data type: ordered table OrderedList
- An ordered table is a data item whose position in the list is determined according to its comparable properties (such as integer size and alphabet order)
- The smaller the data item, the closer it is to the head of the list, and the closer it is to the front
- Operations defined by OrderedList
OrderedList(): Create an empty ordered table add(item): Add a data item to the table and keep the overall order. This item did not exist remove(item): Remove a data item from the ordered table. This item should exist and the ordered table is modified search(item): Find the data item in the ordered table and return whether it exists isEmpty(): Empty table size(): Returns the number of data items in the table index(item): Returns the position of the data item in the table. This item should exist pop(): Remove and return the last item in the ordered table. There should be at least one item in the table pop(pos): Remove and return the data item at the specified location in the ordered table, which should exist
- Implementation of ordered table OrderedList
# It is also realized by linked list method
# Node definitions are the same
# OrderedList also sets a head to save the reference to the header of the linked list
"""about isEmpty/size/remove These methods have nothing to do with the order of nodes, so their implementation is consistent with UnorderedList It's the same.
search/add Methods need to be modified"""
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 orderedList:
def __init__(self):
self.head = 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)
def size(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
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
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())
4. Algorithm analysis of linked list implementation
- The analysis of the complexity of the linked list mainly depends on whether the corresponding method involves the traversal of the linked list
- For a linked list with n nodes
isEmpty is O(1), because you only need to check whether the head is None
size is O(n), because there is no other way to know the number of nodes except to traverse to the end of the table
search/remove and the add method of the ordered table are O(n), because it involves the traversal of the linked list. According to the probability, the average number of operations is n/2
The add method of the unordered table is O(1), because it only needs to be inserted into the header - The List implemented by the linked List has different time complexity from the List data type built in Python in the implementation of some of the same methods
- This is mainly because Python's built-in list data type is implemented based on sequential storage and optimized