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 list	The name of the class
Singly linked list	SingleLinkList
Two-way linked list	DoubleLinkList
Unidirectional cyclic linked lists	CircleSingleLineList
Bidirectional circular linked lists	CircleDoubleLinkList

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

The queue	The name of the class
Single-ended queue	SingleQueue
deque	SingleDeque
Single-ended loop queue	CircleQueue
Double-ended circular queue	CircleDeque

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

Binary tree	The name of the class
Binary tree	BinaryTree
Binary search tree	BinarySearchTree

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

Balanced binary search tree	The name of the class
Binary equilibrium tree	BinaryBalanceTree
Binary balanced search tree	BinaryBalanceSearchTree
Red and black tree	RedBlackTree

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

A collection of	The name of the class
A collection of bidirectional linked lists	ListSet
Red black tree collection	TreeSet
A collection of hash tables	HashSet

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

Binary heap	The name of the class
Binary heap	BinaryHeap
The maximum heap	MinHeap
The minimum heap	MaxHeap

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

Check and set	The name of the class
Quick Find	UnionFind_QF
Quick Union	UnionFind_QU
QU is optimized based on size	UnionFind_QU_Size
QU is optimized based on size	UnionFind_QU_Size
QU is optimized based on Rank	UnionFind_QU_Rank
QU Rank based optimization, path compression	UnionFind_QU_Rank_PC
QU Rank based optimization, path splitting	UnionFind_QU_Rank_PS
QU Rank based optimization, path half	UnionFind_QU_Rank_PH
Generic and look up sets	GenericUnionFind

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

The sorting	The name of the class
Bubble sort	BubbleSorted2
Selection sort	SelectedSorted
Insertion sort	InsertionSorted1
Merge sort	MergeSort
Hill sorting	ShellSort
Quick sort	QuickSorted
Heap sort	HeapSorted
Count sorting	CountingSorted
Radix sort	RadixSorted
Bucket sort	BucketSorted

/// 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

---