编程知识 cdmana.com

To be a programmer, you need to know 8 common data structures, remember!

source | http://suo.im/6oo92L

 

8 Common data structures

Data structure is a special way to organize and store data , It enables us to operate on the stored data more efficiently . Data structure is widely used in computer science and software engineering .

 

Almost all developed programs or software systems use data structures . Besides , Data structure is the foundation of computer science and software engineering . When it comes to software engineering interviews , This is a key theme . therefore , As a developer , We must have a good understanding of the data structure .

In this paper , I will briefly explain what every programmer must know 8 Common data structures .

C/C++ Learning skirt of 【 712   two eight four   Seven Zero Five  】, Whether you are Xiaobai or an advanced person , If you want to change your career or join it, you can learn about it and learn from it together ! There are development tools in the skirt , A lot of dry goods and technical information sharing !

 

1. Array

Arrays are fixed size structures , Can hold items of the same data type . It can be an array of integers , Array of floating-point numbers , String array or even array array ( For example, a two-dimensional array ). Array indexed , This means random access .

Fig 1. Visualization of basic Terminology of Arrays

 

Array operations

· Traverse : Traverse all elements and print .

· Insert : Insert one or more elements into the array .

· Delete : Remove elements from array

· Search for : Search for elements in an array . You can search for elements by their value or index

· to update : Update the value of an existing element at the given index

Application of array

· Used as the basis for building other data structures , For example, array list , Pile up , Hashtable , Vectors and matrices .

· For different sorting algorithms , For example, insert sort , Quick sort , Bubble sort and merge sort .

2. Linked list

A list is a sequential structure , It consists of a sequence of linked linear sequential items . therefore , You have to access the data in sequence , And no random access . Link lists provide a simple and flexible representation of dynamic sets .

Let's consider the following terms about linked lists . You can refer to the figure 2 To get a clear idea .

· The elements in the list are called nodes .

· Each node contains a key and a point to its successor ( be called next) The pointer to .

· be known as head The attribute of points to the first element of the list of links .

· The last element of the list is called the tail .

Fig 2. Visualization of basic Terminology of Linked Lists

Here are the various types of lists available .

· Single chain list — You can only traverse items in a positive direction .

· Double linked list - You can traverse items in both forward and backward directions . The node consists of an additional pointer called the previous one , Point to the previous node .

· Loop link list — Link list , The last pointer of the head points to the tail , The next pointer to the tail points to the head .


 

List operation

· Search for : Through a simple linear search, find the key in a given list as k The first element of , And return a pointer to the element

· Insert : Insert a key in the list of links . Insertion can be done by 3 Do it in different ways ; Insert... At the beginning of the list , Insert... At the end of the list , Then insert... In the middle of the list .

· Delete : Remove elements from the given list x. You cannot delete a node step by step . Delete by 3 Do it in different ways ; Remove... From the beginning of the list , Delete... From the end of the list , Then delete... From the middle of the list .

The application of linked list

· For symbol table management in compiler design .

· For in use Alt Tab( Use circular list to realize ) Switch between programs .

3. Stack

Stack is a kind of LIFO( Last in, first out - The last placed element can be accessed first ) structure , This structure can be found in many programming languages . This structure is called " Stack ", Because it's like a real world stack - The stack of plates .

Image Source: pixabay

Stack operation

Here's what you can do on the stack 2 A basic operation . Please refer to the picture 3, To better understand stack operations .

· Push push : Insert an element at the top of the stack .

· Pop eject : Delete the top element and return .

Fig 3. Visualization of basic Operations of Stacks

Besides , The following additional functions are provided for the stack , To check its condition .

· Peep peep : Returns the top element of the stack without deleting it .

· isEmpty: Check if the stack is empty .

· isFull: Check if the stack is full .

Application of stack

· For expression evaluation ( for example : Shunting yard algorithm used to analyze and evaluate mathematical expressions ).

· Used to implement function calls in recursive programming .

4. queue

A queue is a kind of FIFO( fifo - First placed elements can be accessed first ) structure , This structure can be found in many programming languages . This structure is called " queue ", Because it's like a real-world queue - People are waiting in line .

Image Source: pixabay

 

Queue operation

Here's what you can do on a queue 2 A basic operation . Please refer to the picture 4, To better understand stack operations .

· Enter the team : Insert the element at the end of the queue .

· Out of the team : Remove elements from the beginning of the queue .

Fig 4. Visualization of Basic Operations of Queues

Application of queues

· For managing threads in multithreading .

· Used to implement queuing system ( for example : Priority queue ).

5. Hashtable

A hash table is a data structure , Used to store values with keys associated with each key . Besides , If we know the key associated with the value , Then it effectively supports searching . therefore , Whatever the size of the data , Insert and search are very effective .

When stored in a table , Direct addressing uses a one-to-one mapping between values and keys . however , When there are a lot of key value pairs , There are problems with this method . The table will have a lot of records , And it's huge , Consider the available memory on a typical computer , The table may be impractical or even impossible to store . To avoid this problem , We use hash tables . A detailed introduction to hash table can be found in python Introduction and advanced official account collection algorithm ebook

hash function

Called hash function (h) The special function of is used to overcome the above problems in direct addressing .

In a direct interview , With a key k The value of is stored in the slot k in . Use hash function , We can calculate the table that each value points to ( slot ) The index of . The value computed by the hash function of a given key is called the hash value , It represents the index of the table to which the value is mapped .

· h: hash function

· k: The key whose hash value should be determined

· m: The size of the hash table ( Number of slots available ). One is not close to 2 The prime of the exact power of is m A good choice for .

Fig 5. Representation of a Hash Function

 

· 1→1→1

· 5→5→5

· 23→23→3

· 63→63→3

From the last two examples given above , We can see , When the hash function generates the same index for multiple keys , There will be conflict . We can choose the appropriate hash function h And uses technologies such as linking and open addressing to resolve conflicts .

Application of hash table

· For database indexing .

· Used to implement associative arrays .

· Used to implement " Set up " data structure .

6. Trees

A tree is a hierarchy , Data is organized hierarchically and linked together . This structure is different from the link list , And in the list of links , Projects are linked in linear order .

In the past few decades , Various types of trees have been developed , To suit certain applications and meet certain limitations . Some examples are binary search trees ,B Trees , Red and black trees , Unfold the tree ,AVL Trees and n Metatree .

Binary search tree

seeing the name of a thing one thinks of its function , Binary search tree (BST) It's a binary tree , The data is organized in a hierarchical structure . This data structure stores values in sort order , We will study these values in detail in this course .

Each node in the binary search tree contains the following attributes .

· key: Values stored in nodes .

· left: A pointer to the left child .

· Right : A pointer to the right child .

· p: A pointer to the parent node .

Binary search trees have unique properties , It can be distinguished from other trees . This property is called binary-search-tree attribute .

Make x Search for a node in the binary tree .

· If y yes x A node in the left subtree , be y.key≤x.key

· If y yes x The nodes in the right subtree of , be y.key≥x.key

Fig 6. Visualization of Basic Terminology of Trees.

The application of tree

· Binary tree : For implementing expression parsers and expression solvers .

· Binary search tree : Used in many search applications that continuously input and output data .

· Pile up : from JVM(Java virtual machine ) Used to store Java object .

· Trap: For wireless networks .

7. Pile up

Heap is a special case of binary tree , Where the values of the parent and its children are compared , And arrange them accordingly .

Let's see how to represent a heap . The heap can be represented by trees and arrays . chart 7 and 8 Shows how we use binary trees and arrays to represent binary heaps .

Fig 7. Binary Tree Representation of a Heap

 

Fig 8. Array Representation of a Heap

 

Piles can have 2 Types .

· The smallest pile - The parent key is less than or equal to the child key . This is called min-heap attribute . The root will contain the minimum value of the heap .

· The maximum number of piles - The parent key is greater than or equal to the child key . This is called max-heap attribute . The root will contain the maximum value of the heap .

Application of heap

· Used to implement priority queues , Because priority values can be sorted according to heap properties .

· Can be in O(log n) Use heap to implement queue function in time .

· Used to find... In a given array k Minimum ( Or maximum ) Value .

· For heap sort algorithm .

8. chart

A graph consists of a finite set of vertices or nodes and a set of edges connecting these vertices .

The order of a graph is the number of vertices in the graph . The size of a graph is the number of sides in the graph .

If two nodes are connected to each other through the same side , They are called adjacent nodes .

Directed graph

If graphics G All edges of have directions indicating what is the starting vertex and what is the ending vertex , It is called a directed graph .

We said (u,v) From the top u To enter or leave a vertex u, Then incident or enter the vertex v.

Self ring : From the vertex to its edge .

Undirected graph

If the figure G All the edges of are directionless , It is called undirected graph . It can travel between two vertices in two ways .

If the vertex is not connected to any other node in the graph , The vertex is called an isolated .

Fig 9. Visualization of Terminology of Graphs

The application of graph

· For social media networks . Every user is a vertex , And an edge is created when the user connects .

· Web pages and links used to represent search engines . Web pages on the Internet are linked to each other through hyperlinks . Every page is a vertex , The hyperlink between two pages is one side . be used for Google Page rank in .

· Used to represent GPS Location and route in . Position is the vertex , The route connecting the location is the side . Used to calculate the shortest path between two positions .

reference

[1] Introduction to the algorithm , The third edition , author : Thomas ·H· Komen (Thomas H. Cormen), Charles ·E· Rayson (Charles E. Leiserson), Ronald ·L· Livingster (Ronald L. Rivest) And Clifford · Stan (Clifford Stein).

[2] come from Wikipedia List of data structures for

( This article is translated from Vijini Mallawaarachchi The article 《8 Common Data Structures every Programmer must know》, Reference resources :https://towardsdatascience.com/8-common-data-structures-every-programmer-must-know-171acf6a1a42)

 

If you are right about C/C++ Interested in , Want to learn programming , Xiaobian recommends one C/C++ Technology exchange group 【 Click to enter 】!

It's about : Introduction to programming 、 Game programming 、 Network programming 、Windows Programming 、Linux Programming 、Qt Interface development 、 Hackers and so on ......

版权声明
本文为[Three ah three water]所创,转载请带上原文链接,感谢

Scroll to Top