Shulou(Shulou.com)06/02 Report--

In this issue, the editor will bring you about how to analyze the python data structure. The article is rich in content and analyzes and narrates it from a professional point of view. I hope you can get something after reading this article.

Data structure is to design how the data is organized and stored in the computer.

For example, lists, collections, dictionaries, etc., are all data structures.

Program = data structure + algorithm

Stack

A Stack is a list of data sets that can only be inserted or deleted at one end

Features of stack: last-in, first-out (last-in, first-out)

Basic operation of the stack:

Stack (press stack): push

Out of stack: pop

Take the top of the stack: gettop, just take a look, do not remove the element

For the implementation of the stack in python, you can directly use the list:

Stack: append (obj)

Out of the stack: pop (), the last one without parameters

Take the top of the stack: list [- 1], and view the last element of the list

The time complexity of the operation of the above stack is O (1).

However, the list itself has no stack restrictions, and other methods supported by the list can still be used. For example, insert (index, obj) and pop (index) can insert or pull out elements anywhere in the list. But these operations are not stack operations, the time complexity is O (n).

Queue

A Queue is a collection of data that is only allowed to be inserted in one segment of the list and deleted at the other end.

Nature of queue: first-in, first-out (First-in, First-out)

There is also a two-way queue where both ends of the queue are allowed to enter and dequeue.

Queues cannot be implemented with lists. If implemented with a list, queuing can be an append operation. But out of the queue is pop (0), which pops up the first element, and then there is an empty position in front of the list, and all elements move forward. The time complexity of such an operation is O (n).

Queues can be implemented using the following modules:

From collections import deque

This queue supports two-way, allowing both sides to enter and leave the team. Method of operation:

Create a queue: queue = deque (), create an empty queue

Queue = deque (li), create the queue through a list

Join the team: append

Team out: popleft

The first member of the team: appendleft

At the end of the line: pop

Linked list

Each element is an object, and each object is called a node, containing a data field item and a pointer next to the next node. Through the connection between the nodes, it is finally connected into a linked list.

Definition of node:

Class Node (object): def _ _ init__ (self, item=None): self.item = item self.next = None

Insertion and deletion of nodes:

# cur_node is the current node # insert, insert node pp.next = cur_node.nextcur_node.naxt = p # delete after the current node, delete the node p behind the current node p = cur_node.nextcur_node.nxet = cur_node.next.nextdel p

The time complexity of inserting and deleting nodes in the linked list is O (1). But in the list it is O (n). This is the meaning of the linked list.

Establish a linked list

Head insertion, where each newly added element is inserted after the header element:

Def create_link_list_first (li): head = Node () for item in li: P = Node (item) p.next = head.next head.next = p return head

In tail interpolation, each newly added element is placed at the end of the linked list:

Def create_link_list_right (li): head = Node () r = head for item in li: P = Node (item) r.next = pr = p return head double linked list

A double-linked list is that each node has two pointers: one to the back node and one to the front node.

In the single linked list, the header node has no data field, the value is None, and the next of the tail node is None

In a double linked list, each node has a data office, and one of the pointers of the header and tail nodes is None.

Insert, delete and establish linked lists will not be expanded

List and linked list

The following is a comparison of the time complexity of the various basic operations of the two data structures:

Find by element: all O (n)

Search by subscript: list is O (1), linked list is O (n)

Insert element: list is O (n), linked list is O (1)

Delete element: list is O (n), linked list is O (1)

Collection and dictionary hash table lookup

Hash table (Hash Table, also known as hash table) is a linear table storage structure. By taking the associated word key of each object as an independent variable and the same hash function h (key), key is mapped to the subscript h (key), and the object is stored at this location.

There is no need to delve into this hash function h (k). Is to give a table key, after calculation can get a certain number (subscript).

For example: data set {1,6,7,9}, suppose there is a hash function: h (1) = 0, h (6) = 2, h (7) = 4, h (9) = 5, then the hash table is stored as [1, None, 6, None, 7, 9].

In this way, when you need to find the location of element 6, the subscript (h (6) = 2) of the element can be obtained through the hash function h (6). Therefore, there is no need to traverse, go directly to the position of 2 to confirm whether there is a changed element. This is the time complexity of an O (1).

Hash conflict: because the subscript range of the hash table is limited, the value of the element key is nearly infinite. So it is possible that two keywords get the same value after being calculated by the hash function. Two elements are mapped to a single subscript, which results in a hash conflict.

The solution to the hash conflict:

Zipper method: connect all conflicting elements with a linked list at the subscript

Open addressing method: create a hash conflict function and get a new address through the hash conflict function.

The set in python is to confirm whether there is a value or not after passing the subscript of the element through the hash function. If it does not exist, it is not in the set. If there is a value, see if it is the same (there may be a Huaxi conflict), and if it is in the subscript or in the linked list, then the element is in the collection.

Dictionaries in python

A hash table is used to store the dictionary, and the key of the dictionary is mapped to a subscript through a hash function. The value can then be stored in the subscript corresponding to key.

In the case of a small number of key-value pairs in the dictionary, there is almost no hash conflict. At this point, the time complexity of finding an element is O (1).

Maze problem

You can use a two-dimensional list to represent the maze. Each element in the list is a grid in a maze, either a path (which can be represented by 0) or a wall (for example, represented by 1). Each node has four directions. An algorithm is given and a path from the starting point to the end point is given.

Maze = [1Perry 1reparte1], [1jort0jort0magor0jor0jor0jor0], [1pyrrine 1pjor1], [1pjor0pence0parention0partemo 0reparent1], [1pjori0re0partem1], [1pjor0re0paren1], [1pyrum 1pence1]

Probing in four directions can be carried out on the nodes (x, y) of a maze. Iterate through the following list to complete the exploration in four directions:

Dirs = [lambda x, y: (x + 1, y), lambda x, y: (x-1, y), lambda x, y: (x, y + 1), lambda x, y: (x, y-1)]

Idea: start from one node, find the next point that can go, and when you can't find a point that can go, go back to the last point to see if there is a point that can go in other directions.

Method: create an empty stack and first put the entry node into the stack. Loop when the stack is not empty. Get the element at the top of the stack and find the next walkable node. If you can't find the walkable node, the current location is a dead end and backtrack (that is, the current position is out of the stack to see if there are any other nodes to go). Nodes that have passed before can be marked-1 to prevent them from going up again.

Queue implementation

Idea: start with one node and look for all the points below where you can continue to go. Then keep looking until you find an exit. For example, many people explore the maze together, encounter a fork in the road, break up the team and continue to explore each fork.

Method: create an empty queue and put the starting position in the queue. Loop when the queue is not empty. Get out of the team once and see the nodes of the team. If it's an exit, then you'll find an exit. Otherwise, find out the walkable squares among the four adjacent squares of the queue nodes, and all these nodes join the queue. Repeat the above steps.

According to the above method, we can finally find the end point. But there is no output path from the start to the end. Each element that joins the team must be associated with the previous element that made him join the team. In this way, a path from the end to the starting point can be deduced backwards.

This is what I thought, and this path can be stored in a chain table. The head of the chain table is the end position and the end of the chain table is the starting point. Each element in the queue is also inserted into the linked list by head insertion, so that the previous element is associated. It seems that you don't have to worry about the fork in the road.

There is no bifurcation in the direction from the end to the starting point.

Depth first and breadth first

There are two search methods: depth first and breadth first.

The implementation of the stack is the depth-first approach.

The implementation of queues is the breadth-first approach.

In general, the implementation of depth first is related to the stack. The breadth-first implementation is related to queues.

The above is the editor for you to share how to analyze the python data structure, if you happen to have similar doubts, you might as well refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.