The Best Object-Oriented Programming Tutorials on the Net for Getting Started: 45 Python Implementations of Common Data Structures - Chain Tables, Trees, Hash Tables, Graphs, and Heaps
Abstracts:
A data structure is a way of organizing and storing data in computer science that determines how data is accessed and how efficiently it can be manipulated, and the choice and implementation of a data structure is critical to the performance and design of a program. This article focuses on how to implement common data structures using the Python language and built-in libraries.
Link to original article:
FreakStudio's Blog
Past Recommendations:
You're learning embedded and you don't know how to be object oriented?
The Best Object-Oriented Programming Tutorials on the Web for Getting Started: 00 Introduction to Object-Oriented Design Methods
The network's most suitable for the introduction of object-oriented programming tutorials: 01 Basic Concepts of Object-Oriented Programming
The Best Object-Oriented Programming Tutorials for Getting Started on the Web: 02 Python Implementations of Classes and Objects - Creating Classes with Python
The Best Object-Oriented Programming Tutorials for Getting Started on the Web: 03 Python Implementations of Classes and Objects - Adding Attributes to Custom Classes
The Best Object-Oriented Programming Tutorial on the Net for Getting Started: 04 Python Implementation of Classes and Objects - Adding Methods to Custom Classes
The Best Object-Oriented Programming Tutorial on the Net for Getting Started: 05 Python Implementation of Classes and Objects - PyCharm Code Tags
The best object-oriented programming tutorials on the net for getting started: 06 Python implementation of classes and objects - data encapsulation of custom classes
The best object-oriented programming tutorial on the net for getting started: 07 Python implementation of classes and objects - type annotations
The best object-oriented programming tutorials on the net for getting started: 08 Python implementations of classes and objects - @property decorator
The best object-oriented programming tutorials on the net for getting started: 09 Python implementation of classes and objects - the relationship between classes
The Best Object-Oriented Programming Tutorials on the Net for Getting Started: 10 Python Implementations of Classes and Objects - Class Inheritance and Richter's Replacement Principle
The best object-oriented programming tutorials on the net for getting started: 11 Python implementation of classes and objects - subclasses call parent class methods
The network's most suitable for the introduction of object-oriented programming tutorials: 12 classes and objects of the Python implementation - Python using the logging module to output the program running logs
The network's most suitable for the introduction of object-oriented programming tutorials: 13 classes and objects of the Python implementation - visual reading code artifacts Sourcetrail's installation use
The Best Object-Oriented Programming Tutorials on the Web for Getting Started: The Best Object-Oriented Programming Tutorials on the Web for Getting Started: 14 Python Implementations of Classes and Objects - Static Methods and Class Methods for Classes
The Best Object-Oriented Programming Tutorials on the Net for Getting Started: 15 Python Implementations of Classes and Objects - __slots__ Magic Methods
The Best Object-Oriented Programming Tutorials on the Net for Getting Started: 16 Python Implementations of Classes and Objects - Polymorphism, Method Overriding, and the Principle of Open-Close
The Best Object-Oriented Programming Tutorials for Getting Started on the Web: 17 Python Implementations of Classes and Objects - Duck Types and "file-like objects"
The network's most suitable for the introduction of object-oriented programming tutorials: 18 classes and objects Python implementation - multiple inheritance and PyQtGraph serial data plotting graphs
The Best Object-Oriented Programming Tutorials on the Web for Getting Started: 19 Python Implementations of Classes and Objects - Using PyCharm to Automatically Generate File Annotations and Function Annotations
The best object-oriented programming tutorials on the web for getting started: 20 Python implementation of classes and objects - Combinatorial relationship implementation and CSV file saving
The best introductory object-oriented programming tutorials on the net: 21 Python implementation of classes and objects - Organization of multiple files: module module and package package
The Best Object-Oriented Programming Tutorials on the Net for Getting Started: 22 Python Implementations of Classes and Objects - Exceptions and Syntax Errors
The Best Object-Oriented Programming Tutorials on the Net for Getting Started: 23 Python Implementation of Classes and Objects - Throwing Exceptions
The Best Object-Oriented Programming Tutorials on the Web for Getting Started: 24 Python Implementations of Classes and Objects - Exception Catching and Handling
The best object-oriented programming tutorials on the web for getting started: 25 Python implementation of classes and objects - Python to determine the type of input data
The Best Object-Oriented Programming Tutorials on the Net for Getting Started: 26 Python Implementations of Classes and Objects - Context Managers and with Statements
The best introductory object-oriented programming tutorials on the web: 27 Python implementation of classes and objects - Exception hierarchy and custom exception class implementation in Python
The best object-oriented programming tutorials on the net for getting started: 28 Python implementations of classes and objects - Python programming principles, philosophies and norms in a big summary
The Best Object-Oriented Programming Tutorials on the Net for Getting Started: 29 Python Implementations of Classes and Objects - Assertions and Defensive Programming and Use of the help Function
The Best Object-Oriented Programming Tutorials for Getting Started on the Web: 30 Python's Built-In Data Types - the root class of object
The Best Object-Oriented Programming Tutorials on the Web for Getting Started: 31 Python's Built-In Data Types - Object Object and Type Type
The Best Object-Oriented Programming Tutorials on the Web for Getting Started: 32 Python's Built-in Data Types - Class Class and Instance Instance
The Best Object-Oriented Programming Tutorials for Getting Started on the Web: 33 Python's Built-In Data Types - The Relationship Between the Object Object and the Type Type
The Best Object-Oriented Programming Tutorials on the Web for Getting Started: 34 Python's Built-In Data Types - Python's Common Compound Data Types: Tuples and Named Tuples
The Best Object-Oriented Programming Tutorials on the Net for Getting Started: 35 Python's Built-In Data Types - Document Strings and the __doc__ Attribute
The Best Object-Oriented Programming Tutorials on the Web for Getting Started: 36 Python's Built-In Data Types - Dictionaries
The Best Object-Oriented Programming Tutorials on the Net for Getting Started: 37 Python's Common Composite Data Types - Lists and List Derivatives
The Best Object-Oriented Programming Tutorials on the Net for Getting Started: 38 Python's Common Composite Data Types - Using Lists to Implement Stacks, Queues, and Double-Ended Queues
The Best Object-Oriented Programming Tutorials on the Web for Getting Started: 39 Python Common Composite Data Types - Collections
The Best Object-Oriented Programming Tutorials on the Net for Getting Started: 40 Python's Common Compound Data Types - Enumeration and Use of the enum Module
The Best Object-Oriented Programming Tutorials on the Net for Getting Started: 41 Python's Common Composite Data Types - Queues (FIFO, LIFO, Priority Queue, Double-Ended Queue, and Ring Queue)
The best introductory object-oriented programming tutorials on the web: 42 Python commonly used composite data types-collections container data type
The Best Object-Oriented Programming Tutorials on the Web for Getting Started: 43 Python's Common Composite Data Types - Extended Built-In Data Types
The Best Object-Oriented Programming Tutorial on the Net for Getting Started: 44 Python Built-In Functions and Magic Methods - Magic Methods for Rewriting Built-In Types
More highlights to watch:
Accelerating Your Python: A Quick Guide to Python Parallel Computing
Understanding CM3 MCU Debugging Principles in One Article
Liver half a month, embedded technology stack summary out of the big
The "Secrets of the Martial Arts" of the Computer Competition
A MicroPython open source project collection: awesome-micropython, including all aspects of Micropython tool library
Avnet ZUBoard 1CG Development Board - A New Choice for Deep Learning
SenseCraft Deploys Models to Grove Vision AI V2 Image Processing Module
Documentation and code acquisition:
The following link can be accessed to download the document:
/leezisheng/Doc
This document mainly introduces how to use Python for object-oriented programming, which requires readers to have a basic understanding of Python syntax and microcontroller development. Compared with other blogs or books that explain Python object-oriented programming, this document is more detailed and focuses on embedded host computer applications, with common serial port data sending and receiving, data processing, and dynamic graph drawing as application examples for the host computer and the lower computer, and using Sourcetrail code software to visualize and read the code for readers' easy understanding.
The link to get the relevant sample code is below:/leezisheng/Python-OOP-Demo
main body (of a book)
Data Structure Basics
In fact, the queues, lists, sets, dictionaries, etc. mentioned earlier are all part of data structures. Data structure, as a kind of code structure, its core purpose is to store and organize data in an orderly manner, thus simplifying the process of modifying, navigating and accessing information. It not only determines how data is collected, what functions are implemented, and the interrelationships between data, but also plays an indispensable role in various areas of computer science and programming, such as operating systems, front-end development, and machine learning. Data structures are key building blocks for efficient and realistic problem solving. Each data structure has its own unique application scenarios and tasks.
Data structures can be divided into two main categories: logical and physical structures:
- Logical structure: A data organization that refers to the logical relationships between data elements that focus on the relative position of the elements, independent of where the data is actually stored in the computer.
In the classification of logical structures, they can be categorized into linear and nonlinear structures:
- Physical structure: Also known as storage structure, it describes the specific form in which the logical structure of data is realized in the computer storage space. The logical structure of data can usually be mapped to a variety of physical structures. Physical structure is a specific means to realize the logical relationship between data elements. A logical structure can be transformed into multiple physical structures according to actual needs. Common physical structures are:
- ① Sequential storage, which is characterized by the sequential order in which elements are stored in memory; the elements of a linear table are stored through a set of contiguous storage units.
- ② Chained storage, in which the stored elements in memory do not have to be consecutive and each element node contains data elements and pointer information to neighboring elements.
- ③ Indexed storage, in addition to storing node information, identifies the memory address of a node by means of an additional index table, which consists of multiple index entries.
- ④ Hash storage, also known as Hash storage, in which the storage address of a node is directly determined by the keycode value of the node.
Next, we'll outline how to use object-oriented programming thinking and Python's built-in data types to implement other data structures.Note that this part is not the focus of this book, so here is just a superficial talk about data structures, which realize the code is mainly to help readers understand rather than practical applications.
Python Implementation of Chained Tables
A chained table is a non-contiguous, non-sequential storage structure on physical storage units, a linear table consisting of many data items of the same data type arranged in a particular order. A chain table has a series of nodes, the so-called nodes are each element in the chain table, each node contains two data, one is the data field (value) that stores the element, the other is the pointer field that stores the address of the next node.
The first node in a linked table is called the head node, and the last node is called the tail node, where the next pointer to the tail node is null. a linked table can be either singly or doubly linked, depending on whether each node has only one pointer to the next node, or whether it also has a pointer to the previous node. You can think of a linked table as a chain; individual links have only one connection to neighboring links, but all links together form a larger structure.
class Node:
def __init__(self, dataval=None):
= dataval
= None
class SLinkedList:
def __init__(self):
= None
list1 = SLinkedList()
= Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
_# Link first Node to second node_
= e2
_# Link second Node to third node_
= e3
Chained lists have the following advantages: new elements can be inserted and deleted more efficiently, they are easier to reorganize than arrays, and advanced data structures (such as graphs or trees) are based on chained lists. The disadvantages are: pointer storage at each data point increases memory usage and you must always traverse the chained table from the head node in order to find a specific element.
Python Implementation Tree
Trees are another relationship-based data structure, specialized for representing hierarchies. Like chained lists, they are populated with Node objects, which contain a data value and one or more pointers that define their relationship to the immediate node. Every tree has a root node from which all other nodes branch. The root node contains pointers to all the elements directly below it, which are called its children. These child nodes can have their own child nodes. Any node on the same level is called a sibling node. Nodes with no connected children are called leaf nodes.
We usually use binary trees the most, and the most common application of binary trees is binary search trees. A binary search tree excels at searching large collections of data because the time complexity depends on the depth of the tree rather than the number of nodes. A binary tree has the following characteristics:
- The left subtree contains only nodes with elements smaller than the root.
- The right subtree contains only nodes with elements greater than the root.
- The left and right subtrees must also be binary search trees. They must follow the above rules with the "root" of the tree.
- There can be no duplicate nodes, i.e. no two nodes can have the same value.
lass Node:
def __init__(self, data):
= None
= None
= data
def insert(self, data):
_# Compare the new value with the parent node_
if :
if data < :
if is None:
= Node(data)
else:
(data)
elif data > :
if is None:
= Node(data)
else:
(data)
else:
= data
_# Print the tree_
def PrintTree(self):
if :
()
print( ),
if :
()
_# Use the insert method to add nodes_
root = Node(12)
(6)
(14)
(3)
()
The tree structure's search efficiency is ideal for storing hierarchical data (e.g., file locations, etc.), but only for sorted lists; unsorted data degrades to a linear search.
Python implementation of hash tables
Also known as a hash table, a hash table is a complex data structure capable of storing large amounts of information and retrieving specific elements efficiently. This structure stores data consisting of keys (key) and values (value), which are stored in memory storage locations that are directly accessed based on the key.
Each input key goes through a hash function that converts it from its initial form to an integer value called a hash. The hash function must always produce the same hash from the same input, must be computed quickly, and produces a fixed-length value.Python includes a built-in hash() function that speeds up implementation. The table then uses hashing to find the general location of the desired value (called a storage bucket). The program then only needs to search for the desired value in this subgroup, rather than having to search the entire data pool. In addition to this general framework, hash tables can be very different depending on the application. Some may allow keys from different data types, while others may have different setup buckets or different hash functions.
Here is an example of a hash table in Python code.
import pprint
class Hashtable:
def __init__(self, elements):
self.bucket_size = len(elements)
= [[] for i in range(self.bucket_size)]
self._assign_buckets(elements)
def _assign_buckets(self, elements):
for key, value in elements: _#calculates the hash of each key_
hashed_value = hash(key)
index = hashed_value % self.bucket_size _# positions the element in the bucket using hash_
[index].append((key, value)) _#adds a tuple in the bucket_
def get_value(self, input_key):
hashed_value = hash(input_key)
index = hashed_value % self.bucket_size
bucket = [index]
for key, value in bucket:
if key == input_key:
return(value)
return None
def __str__(self):
return () _# pformat returns a printable representation of the object_
if __name__ == "__main__":
capitals = [
('France', 'Paris'),
('United States', 'Washington .'),
('Italy', 'Rome'),
('Canada', 'Ottawa')
]
hashtable = Hashtable(capitals)
print(hashtable)
print(f"The capital of Italy is {hashtable.get_value('Italy')}"
Hash tables, which can hide any form of key as an integer index, are very effective for large dataset searches and are often used in large databases used for frequent queries or in systems that retrieve based on keywords.
Python Implementation Diagram
A graph is a data structure used to represent the visualization of relationships between data vertices (nodes of the graph). The links that connect vertices together are called edges. Edges define which vertices are connected, but do not specify the flow between them. Each vertex is connected to other vertices, and these connections are kept as a comma-separated list of vertices. There is also a special type of graph called a directed graph, which defines the direction of a relationship, similar to a chained list. Directed graphs are helpful when modeling one-way relationships or flowchart-like structures.
In Python, graphs are best implemented using a dictionary, with the name of each vertex as the key and the list of edges as the value.
_# Create the dictionary with graph elements_
graph = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
_# Print the graph _
print(graph)
Graphs have more complex and efficient algorithms for storing data, such as adjacency matrices, adjacency tables, cross-chained lists, adjacency multitables, edge set arrays, and other storage structures. The common graph traversal algorithms are breadth-first and depth-first algorithms. It is suitable for modeling networks or network-like structures and can quickly convey visual information through code, but it is difficult to understand vertex links in large graphs at the same time parsing data from the graph is time expensive.
Python implements the heap
The heap is a special kind of graph tree structure. It is used to implement "priority queues" (priority queues), priority queues are a data structure, you can freely add data, but when you take out the data from the smallest value to take out in order. In the tree structure of the heap, the vertices are called "nodes" (node), and data is stored in these nodes. A tree structure is a heap if it satisfies the following two characteristics:
- A heap is a complete binary tree (a complete binary tree is one in which the number of nodes in all but the last layer is full).
- The value of each node in the heap must be greater than or equal to or less than the value of each node in its subtree.
We can use the heapq module to implement a minimal heap suitable for use with Python's lists:
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data
heap = []
print('random :', data)
print()
for n in data:
print('add {:>3}:'.format(n))
(heap, n)
show_tree(heap)
There are two functions in there that need attention:
-
(heap, item): Pushes the value item to the heap, leaving the heap unchanged. -
heapq_showtree.show_tree(heap): Used to show the tree structure.
