Learn data structures and algorithms using Swift

• It mainly shares the data structure and sorting algorithm that we have learned recently
• The article covers only the function definitions implemented by code for each data structure
• Almost every data structure or algorithm involved is implemented in code
• GitHub code address: data structure and algorithm

The linear table

The list

• A linked list is a linear structure of chained storage where the memory addresses of all elements are not necessarily contiguous
• The following table shows the corresponding class names for the four linked lists and test items

class List<E: Comparable> {
    /** * clears all elements */
    func clear(a) {}

    /** * number of elements * @return */
    func size(a) -> Int{}/** * whether is empty * @return */
    func isEmpty(a) -> Bool{}/** * contains an element * @param element * @return */
    func contains(_ element: E) -> Bool{}/** * add element to end * @param element */
    func add(_ element: E) {}

    /** * get the element at index * @param index * @return */
    func get(_ index: Int) -> E? {}/** * replace the index element * @param index * @param element * @return the original element ֵ */
    func set(by index: Int.element: E) -> E? {}/** * Insert an element * @param index * @param element */
    func add(by index: Int.element: E) {}

    /** * remove the index element * @param index * @return */
    func remove(_ index: Int) -> E? {}/** * View the index of the element * @param Element * @return */
    func indexOf(_ element: E) -> Int{}}Copy the code

The stack

• A stack is a special kind of linear table that can only be operated on at one end
• The stack follows the Last in First out principle
• Statck

class Statck<E> {
    /// Number of elements
    func size(a) -> Int {}
    
    /// Is empty
    func isEmpty(a) -> Bool{}/ / / into the stack
    func push(_ element: E?). {}
    
    / / / out of the stack
    @discardableResult
    func pop(a) -> E? {}
    
    /// get the top element of the stack
    func peek(a) -> E? {}
    
    / / / empty
    func clear(a){}}Copy the code

The queue

• A queue is a special kind of linear table that can only operate at both ends
• Queues follow the last in, First out principle (single-ended queue), First in, First out
• The following table shows the corresponding class names for queues and test items

class Queue<E: Comparable> {
    /// Number of elements
    func size(a) -> Int {}
    
    /// Is empty
    func isEmpty(a) -> Bool {}
    
    /// Clear all elements
    func clear(a) {}
    
    / / / team
    func enQueue(_ element: E?). {}
    
    / / / out of the team
    func deQueue(a) -> E? {}
    
    /// get the header element of the queue
    func front(a) -> E? {}
    
    func string(a) -> String{}}Copy the code

Hash table

• Hash table also called hash table, childhood array storage (not just arrays)
• Use hash function to generate the index value corresponding to the key to store the value of the array index
• Two different keys may have the same index through a hash function, that is, hash conflict
• Common ways to resolve hash conflicts
  • Open addressing: probe other addresses according to certain rules until empty buckets are encountered
  • Rehash method: design multiple complex hash functions
  • Linked address method: test the use of this method in a project by linking the elements of the same index together in a linked list

class Map<K: Hashable.V: Comparable> {
    /// Number of elements
    func count(a) -> Int {}
    
    /// Is empty
    func isEmpty(a) -> Bool {}
    
    /// Clear all elements
    func clear(a) {}
    
    /// Add elements
    @discardableResult
    func put(key: K? .val: V?). -> V? {}
    
    /// Delete elements
    @discardableResult
    func remove(key: K) -> V? {}
    
    // query value by element
    func get(key: K) -> V? {}

    /// Whether to contain Key
    func containsKey(key: K) -> Bool {}
    
    /// Whether to include Value
    func containsValue(val: V) -> Bool {}

    / / / all the key
    func keys(a)- > [K] {}

    / / / all the value
    func values(a)- > [V] {}

    / / / traverse
    func traversal(visitor: ((K? .V?). - > ())){}}Copy the code

Binary tree

• A binary tree is a finite set of N (n>=0) nodes, which is either an empty set (called an empty binary tree) or consists of a root node and two disjoint left and right subtrees, called root nodes respectively

AVL tree and red-black tree are two balanced binary search trees

A collection of

In the test project, linked list, red-black tree and hash table were used to achieve three sets

class Set<E: Comparable & Hashable> {
    /// Number of elements
    func size(a) -> Int {}
    
    /// Is empty
    func isEmpty(a) -> Bool {}
    
    /// Clear all elements
    func clear(a) {}
    
    /// Whether to contain an element
    func contains(_ val: E) -> Bool {}
    
    /// Add elements
    func add(val: E) {}
    
    /// Delete elements
    @discardableResult
    func remove(val: E) -> E? {}
    
    /// get all elements
    func lists(a)- > [E] {}}Copy the code

Binary heap

A heap is a kind of tree-like data structure, and a binary heap is just one of them

• Many fork heap
• The index of
• The binomial heap
• .

In the test project, the maximum heap and minimum heap are realized by binary heap

class AbstractHeap<E: Comparable> {
    // the number of elements
    func count(a) -> Int {}
    
    /// Is empty
    func isEmpty(a) -> Bool {}
    
    / / / empty
    func clear(a){}/// Add elements
    func add(val: E){}/// Add elements to the array
    func addAll(vals: [E]){}/// get the top of the heap element
    func top(a) -> E? {}
    
    /// delete the heaptop element
    func remove(a) -> E? {}
    
    // insert a new element while removing the top element of the heap
    func replace(val: E) -> E? {}}Copy the code

Check and set

• A parallel lookup set is also called a disjoint set. It has two core operations: lookup and merge
• Find: Finds the set in which the element is located
• Merge: To combine the set of two elements into a set

class UnionFind {
    // find the set (root node) that V belongs to
    func find(v: Int) -> Int {}
    
    // merge the set of v1 and v2
    func union(v1: Int.v2: Int){}// check whether v1 and v2 belong to the same set
    func isSame(v1: Int.v2: Int) -> Bool{}}Copy the code

figure

• A graph consists of vertices and edges. It is divided into directed graph and undirected graph.ListGraph
• ListGraphInherited fromGraph

class Graph<V: Comparable & Hashable.E: Comparable & Hashable> {
    
    /// The number of edges
    func edgesSize(a) -> Int {}
    
    /// Number of vertices
    func verticesSize(a) -> Int {}
    
    /// add vertices
    func addVertex(val: V) {}
    
    / / / add edge
    func addEdge(from: V.to: V) {}
    
    // add edges (with weights)
    func addEdge(from: V.to: V.weight: Double?). {}
    
    /// delete vertices
    func removeVertex(val: V) {}
    
    / / / remove edge
    func removeEdge(from: V.to: V) {}
    
    Our lines can be customized according to our requirements. //
    func breadthFirstSearch(begin: V? .visitor: ((V) - > ())) {}
    
    // Depth First Search (non-recursive)
    func depthFirstSearch(begin: V? .visitor: ((V) - > ())) {}
    
    /// Depth First Search
    func depthFirstSearchCircle(begin: V? .visitor: ((V) - > ())) {}
    

    /* * topology sort * AOV network traversal, all AOV activities into a sequence */
    func topologicalSort(a)- > [V] {}

    /* * Minimum spanning tree * Minimum weight spanning tree, minimum support tree * Of all spanning trees, the one with the least weight * prim algorithm */
    func mstPrim(a) -> HashSet<EdgeInfo<V.E> >? {}/* * Minimum spanning tree * Minimum weight spanning tree, minimum support tree * Of all spanning trees, the one with the least weight * prim algorithm */
    func mstKruskal(a) -> HashSet<EdgeInfo<V.E> >? {}/* * Directed graph * Shortest path from a point (least weight) * return weight */
    func shortestPath(_ begin: V) -> HashMap<V.Double>? {}
    
    /* * Dijkstra: single-source shortest path algorithm, used to calculate the shortest path from one vertex to all other vertices * does not support negative weight edges */
    func dijkstraShortPath(_ begin: V) -> HashMap<V.PathInfo<V.E> >? {}/* * bellmanFord: single-source shortest path algorithm, used to calculate the shortest path from one vertex to all other vertices * supports negative weight edges * supports detection of negative weight rings */
    func bellmanFordShortPath(_ begin: V) -> HashMap<V.PathInfo<V.E> >? {}/* * Floyd: multisource shortest path algorithm, used to calculate the shortest path of any two vertices * supports negative weight edges */
    func floydShortPath(a) -> HashMap<V.HashMap<V.PathInfo<V.E> > >? {}/// Outputs a string
    func printString(a){}}Copy the code

The sorting

/// quicksort
let arr = [126.69.593.23.6.89.54.8]
let quick = QuickSorted<Int> ()print(quick.sorted(by: arr))

/ / / bucket sort
let sort = BucketSorted(a)let array = [0.34.0.47.0.29.0.84.0.45.0.38.0.35.0.76]
print(sort.sorted(by: array))
Copy the code

conclusion

• Data structure part in addition to the hop table and string other basic implementation
• In addition to sorting, the algorithm part has not been learned
• This part of the study is over for the time being, and then I have to prepare for the exam in November
• GitHub code address: data structure and algorithm