Data Structures and Algorithms College Didn’t Understand Come
Data StructuresHow do college students learn data structures? Five Chakra Charts
Data structures are the way computers store and organize data. A data structure is a collection of data elements that have one or more specific relationships with each other. Often, a carefully chosen data structure can lead to greater operational or storage efficiency.
In Data Structures and Algorithms, there are some students who can’t figure out the relationship between data, data objects, data elements, and data items. By drawing a diagram to run through:
Three elements of data
Three elements of data structure are divided into: logical structure, storage structure, and operation of data. Logical structure is divided into linear and nonlinear structure; storage structure is divided into sequential storage, chained storage, indexed storage, hash storage: data operations include the definition and implementation.
Steps to learn data structure
Single linked table (with head node, without head node) design and implementation (add, delete, change, check), double linked table design and implementation
Stack design and implementation (arrays and chained lists), queue design and implementation (arrays and chained lists)
Two and two tree concepts to learn, two and two trees, the preorder, middle order, the back order of traversal of the recursive, non-recursive implementation. Hierarchical traversal
Tree design and implementation (insertion and deletion)
Heap (priority queuing, heap sort)
AVL (balanced) tree design and implementation (four kinds of spin to understand the implementation)
Stretching tree, red-black tree principle concepts to understand
B, B + principle concepts to understand
Huffman Tree Principle Concepts Understanding (greedy strategy)
Hashing (hash table) principle concepts understanding (several ways to resolve hash conflicts)
Annotation sets/disjoint sets (optimization and path compression)
Graph theoretic topological sorting
Graph theoretic dfs depth-first traversal, bfs breadth-first traversal
Shortest Path Diikstra algorithm, Floyd algorithm, spfa algorithm
Minimum spanning tree prim algorithm, kruskal algorithm
Other data structures line segment trees, suffix arrays, and so on
Classical algorithms step by step
Recursive algorithms (factorial, Fibonacci, Hannota problems)
Partitioning algorithms ( fast sort, subsumption sort, find the nearest pair of points, etc.)
Greedy algorithm (used more, interval selection problem, interval coverage problem)
Common dynamic programming (LCS (longest common subsequence) LIS (longest ascending subsequence) knapsack problem and so on
Backtracking algorithms (the classic eight queens problem, the whole arrangement of problems)
Bitwise operation Frequently asked questions (refer to sword offer and LeetCode problems)
Fast power algorithms (fast power multiplication, matrix fast power)
String matching algorithms such as kmp
Everything else number theory algorithms (Euclid, Extended Euclid, China’s Remainder Theorem, etc.)
Illustration: Data Structures and Algorithms of the Dictionary Tree
Dictionary Tree (Trie Tree) This data structure is not very common but very good <typoid=”typo-32 “data-origin=”and “ignoretag=”true”> and</typo> a data structure, the blogger that is! recent period of time to do a few byte questions to understand the dictionary tree this data structure. And will be their own learning content to share with you.
First of all, what is a dictionary tree (Trie tree)? As the name suggests, is the target in the query, like a dictionary, in accordance with certain criteria and steps in order to access the nodes of the tree, to give a simple example, the English dictionary to look up the word “He”, then the first step you must be in accordance with the order of a-z to find the first letter of the first letter of the h, and then according to the same order to find the e. The blogger is to introduce the dictionary tree is similar to the structure of such a dictionary.
The process of searching for a word is to keep searching for a string of characters with the same prefix as the word you are searching for until you reach the last letter of the word you are searching for. Therefore, the dictionary tree is also called prefixTree.
Take hell, hi, new, nop as an example to build a dictionary tree, the construction is as follows
Based on the above you can get the structural properties of the dictionary tree
Based on the above three points to construct a dictionary tree.
The construction of a dictionary tree is in fact relatively simple and not very different from the construction of a normal tree. Next, we will analyze and explain the insertion, deletion, and query operations of the dictionary tree.
When there is no dictionary tree, we need to construct a dictionary tree first.
To insert hell as an example:
Then insert the word hit, the process is as follows, check = > exists then visit / does not exist then create a new node and then visit = > until the word to be inserted to reach the last character.
The insertion operation of a dictionary tree is relatively simple and does not require much sorting.
As mentioned above, according to certain criteria for querying the target string, each node stores a character, the root node to reach the child node path composed of the string that corresponds to the node, then query the target string in accordance with the root node step by step to access the corresponding character of the node, in fact, is to match the process of the string prefix.
The following figure, in the dictionary tree, query “hell”,
[Image upload failed… (image-f028c4-1611057619223)]
If you look up no in that dictionary
Deletion is a bit more complicated than insertion and querying, but it’s also very simple, and deletion assumes that the word already exists in the dictionary tree.
The operation of deleting a node in the dictionary tree takes into account whether the last character of the target string is a leaf node in the tree.
Because a word may be a prefix of another word, if it is not a leaf node, we just need to clear the word flag bit of the word without deleting the whole “branch”.
For example, if you want to delete the word “no”
For example, if you want to delete the word “hell”, it’s the same as the first deletion, except that you start at the last node, the ‘l’ node, which is a leaf node, and work your way up.
For example, if you want to delete the word “hi”, then it is the same as the first two deletions, you visit the leaf node ‘i’, delete the leaf node, and go up to ‘h’, and since ‘h’ is still not a leaf node after ‘i’ is deleted, you don’t continue deleting nodes.
For example, if you want to delete “nop”, similar to the previous ones, you first visit the leaf node ‘p’ and delete it, then you move up and find that ‘o’ is a leaf node, however, ‘o’ has a word marker bit, so you don’t continue deleting here.
With the above several deletion operations, we get the criteria for deletion:
Knowing so much about the various operations of the dictionary tree, I believe that you have a rough understanding of the use of the dictionary tree, the dictionary tree’s biggest role is to be used to == a variety of string matches==, prefix matching (fuzzy search), string lookup (dictionary), and so on.
The blogger only typed out the four keywords “trickle down”, and the search list returned a number of options led by trickle down
As the name implies, it’s a simple dictionary, with not many examples.
The construction of a dictionary tree makes inserting and searching for strings efficient by utilizing the idea of space for time and common prefixes for strings to reduce inefficient string comparison operations. The time complexity of insertion or search is O(n), n is the length of the string.
Of course, the dictionary tree has its drawbacks, when the inserted word does not have a lot of common prefixes, the construction of the dictionary tree becomes very complex and inefficient.
The dictionary tree is not very difficult, but it is a very useful data structure, which is very helpful for solving some problems related to string matching and public prefixes.
Of course, we also said that the dictionary tree has its own drawbacks, due to the use of space for time, if you encountered a bunch of words with very few public prefixes for the construction of the dictionary tree, the space requirements appear to be very large.
Level Exam Public Foundation Exam Analysis of Data Structures and Algorithms (3)
Exam 3 Definition of Data Structures
A data structure (datastructure) is a collection of data elements that have one or more specific relationships with each other, i.e., the form of organization of data.
Data structure, as a computer discipline, mainly studies and discusses the following three aspects:
(l) the logical relationships inherent in the data elements in the data collection, i.e., the logical structure of the data;
(2) in the processing of the data elements, the data elements in the computer storage relationship, i.e., the storage structure of the data;
(3) The operations performed on various data structures.
The day of the discussion of the above issues is to improve the efficiency of data processing, the so-called improve the efficiency of data processing has two aspects:
(l) improve the speed of data processing;
(2) try to save the data processing process in the process of occupying the computer storage space.
Data (data): a symbolic representation of something objective, in computer science it is a general term for all symbols that can be entered into a computer and processed by a computer program.
Data elements (dataelement): is the basic unit of data, in the computer program is usually considered and processed as a whole.
Data object (dataobject): a collection of data elements of the same nature, a subset of data.
In general, in a collection of data elements with the same characteristics, there is a certain relationship (i.e., continuity) between the individual data elements, this relationship reflects the collection of data elements inherent in a structure. In the field of data processing, this inherent relationship between data elements is usually described simply by the front and back pieces relationship (or direct predecessor and direct successor relationship).
The front and back piece relationship is a basic relationship between data elements, but the actual meaning expressed by the front and back piece relationship varies with the specific object. In general, any relationship between data elements can be described by the front and back pieces of the relationship.
1 Logical structure of data
A data structure is a representation of a collection of data elements that reflects the relationships between data elements. More generally, a data structure is a collection of data elements with a structure. By structure, we actually mean the relationships between data elements.
A data structure should contain both of the following information:
(1) information that represents the data elements;
(2) information that represents the back-and-forth relationships between the data elements.
Selected MSOffice Exams for March 2018 Computer Level 2 Exam: Data Structures and Algorithms
Selected MSOffice Exams for March 2018 Computer Level 2 Exam: Data Structures and Algorithms
Data Structures and Algorithms
1. Basic Concept of Algorithms
(1) Concepts : An algorithm is a clear set of instructions for solving a problem.
(2) 4 basic characteristics: feasibility, certainty, infinity, and having enough intelligence.
(3) Two basic elements: operations and manipulations on data objects, and the control structure of the algorithm (the order of operations and manipulations).
(4) The basic methods of design: enumeration, induction, recursion, recursion, halving recursion techniques and backtracking.
2. Complexity of Algorithms
(1) Time complexity of an algorithm: the amount of computational effort required to execute the algorithm.
(2) Space complexity of an algorithm: the memory space required to execute the algorithm.
1.2 Basic Concepts of Data Structures
A data structure refers to a collection of interrelated data elements, i.e., the organization of data. The logical structure reflects the logical relationship between the data elements; the storage structure for the logical structure of the data in the computer storage space in the form of storage, sequential storage, chained storage, indexed storage and hash storage in four ways.
Data structure according to the complexity of the relationship between the elements before and after the pieces can be divided into:
(1) linear structure: there is only one root node, and each node has at most one direct predecessor and one direct successor of the non-empty data structure.
(2) Nonlinear structure: a data structure that does not satisfy the linear structure.
1.3 Linear Tables and Their Sequential Storage Structures
1. Basic Concepts of Linear Tables
Linear structures are also known as linear tables, and linear tables are one of the simplest and most commonly used data structures.
2. Sequential Storage Structure of Linear Tables
– The storage space occupied by the elements must be consecutive.
-Elements are stored in logical order in the storage space.
3. Insertion Operations in Linear Tables
The steps to insert a new element before the ith element are as follows:
Step 1: Move the original nth node to the ith node back by one element position in order.
Step 2: Place the new node at the ith position.
Step 3: Fix the number of nodes in the linear table.
In the worst case, where the inserted element is at the first position, all elements in the linear table need to be moved.
4. Deletion operations on linear tables
The steps to delete the element at the ith position are as follows:
Step 1: Move the n-i elements after the ith element, excluding the ith element, forward by one position in order;
Step 2: Correct the number of nodes in the linear table.
1.4 Stacks and Queues
1. Stacks and their basic operations
(1) Basic concepts: Stacks are a special kind of linear table, whose insertion and deletion operations are carried out only at one end of the linear table, which is also known as “first-in-first-out” or ” last-in-first-out” table. LIFO” table.
– Top of stack: the end that allows insertions and deletions.
– Bottom of the stack: the other end of the top of the stack.
– Empty stack: a stack with no elements in it.
-The top element of the stack is the last to be inserted and the earliest to be deleted.
-The bottom element of the stack is the element that was first inserted and last deleted.
– The stack has memory.
– In a sequential storage structure, stack insertion and deletion operations do not move other data elements in the table.
-Top-of-stack pointer top dynamically reflects changes in the elements of the stack
(3) Sequential storage and operations: entry operation, exit operation and read top-of-stack operation.
2. Queue and its basic operations
(1) Basic concepts: queue is a linear table that allows insertion at one end and deletion at the other, also known as “first-in-first-out” linear table.
-Tail: The end of the queue where insertions are allowed, with the tail pointer pointing to the last element of the queue.
– Head: The end that allows deletions, with the head pointer pointing to the previous position of the head element.
(2) Circular queues and their operations.
The so-called circular queue is the last position of the queue storage space around to the first position, forming a logical circular space.
The entry operation is the addition of a new element to the end of the circular queue.
When the circular queue is not empty (s = 1) and the pointer to the end of the queue is equal to the pointer to the head of the queue, the circular queue is full, and the queuing operation can not be carried out, which is called “overflow”.
Unqueueing refers to exiting an element at the head of a circular queue and assigning it to a specified variable. The head pointer is first rounded up to one, and then the element pointed to by the head pointer is assigned to the specified variable. When the circular queue is empty (s=0), you can’t back out of the queue, which is called “underflow”.
1.5 Linear Chained Tables
A chained table is said to be single or linear if it contains only one pointer field for the address of the next element.
In chained storage, each node is required to consist of two parts: one part is used to store the data element values, called the data domain; the other part is used to store pointers, called the pointer domain. Where pointers are used to point to the previous or next node of that node (i.e., antecedent or consequent).
1.6 Tree and Binary Tree
1. Basic Concepts of Tree
A tree is a simple nonlinear structure, where there is one and only one node with no predecessor, called the root, and the rest of the nodes are grouped into m finite sets of disjoint sets T1, T2, …. T}mm, each of which is a tree, and T1, T2, …, T}mm are subtrees of the root node.
– Parent node: each node has only one antecedent, and there is only one node without antecedent, called the root node of the tree (referred to as the root of the tree).
– Child nodes: each ~ node can be followed by more than one antecedent, nodes without antecedents are called leaf nodes.
– Tree degree: the maximum degree of all nodes.
– Tree depth: the maximum level of the tree.
2. Definition of a binary tree and its basic properties
(1) Definition of a binary tree: a binary tree is a nonlinear structure, is a finite set of nodes, the set is empty (the empty binary tree) or consists of a root node and two non-intersecting left and right binary subtrees. They can be categorized as full binary trees and complete binary trees, where a full binary tree must be a complete binary tree, but a complete binary tree is not necessarily a full binary tree. A binary tree has the following two characteristics:
– A binary tree can be empty, an empty binary tree has no nodes, and a non-empty binary tree has one and only one root node;
– Each node can have up to two subtrees, called the left subtree and the right subtree.