devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】C# 实现常用数据结构总结_c#数据结构

作者：我家自动化 | 2024-05-30 07:12:35

赞

踩

c#数据结构

文章目录


在这里插入图片描述

前言

大家好，这是自己整理的C#常见数据结构笔记，方便自己学习的同时分享出来，感谢支持。
声明：因为C#作为一门面向对象的编程语言， 其实大多数的像array，linklist，queue，stack等的数据结构微软的开发团队已经帮我们封装好了，所以在这里直接用这些东西显得没什么意义，所以本章从其它角度出发，用泛型实现数组，用数组实现栈，队列等这样以此类推， 欢迎学习交流！

线性结构

线性结构是有序的数据元素的集合，存在着一对一的关系。常用的线性结构有：线性表，栈，队列，双队列，串(一维数组)。

1. 数组（Array）

一组具有同一属性的数据就称为数组（array），数组是有序数据的集合，其中各数据的排列时有一定的规律的，我们用一个数组名和下标来唯一的确定数组中的元素。
在这里插入图片描述

  • 优点：
    • 按照索引查询元素速度很快。
    • 按照索引遍历数组很方便。
  • 缺点：
    • 声明数组时大小必须确定，且大小不能改变。
    • 添加和删除元素的速度很慢，因为需要移动其它元素。
    • 数组只能存储一种数据类型。
  • 使用场景：
    • 频繁查询，很少增加和删除的场景。

1.1 代码实现:

// 简单实现数组，数组涉及的应用方法很多
// 这里只实现增删功能, 其它方法逻辑差不多 
public class MyArray<T>
{
    private T[] myArray;
    private int arraysize;
    
    public int Count
    {
        get
        {
            return arraysize;
        }
    }

    // 属性或索引器必须至少有一个访问器
    public T This[int index]
    {
        get
        {
            return myArray[index];
        }
        set
        {
            myArray[index] = value;
        }
    }

    public MyArray()
    {
        arraysize = 0;      // 初始化数组大小
        myArray = new T[arraysize];
    }

    
    public T GetValue(int index)
    {
        return myArray[index];
    }

    // 向数组添加新元素 
    public void Add(T data)
    {
        if (data == null)    // 元素为空的清空 
        {
            return;
        }

        T[] array = new T[arraysize + 1];       //申请一块新的内存
        for (int i = 0; i < myArray.Length; i++)
        {
            array[i] = myArray[i];      // 先把之前的元素添加进来 
        }
        array[arraysize] = data;
        myArray = null;
        myArray = array;
        arraysize++;
        array = null;           // 释放原来的array内存 

    }

    // 按照索引删除数据 
    public void RemoveAt(int index)
    {
        if (index < 0 && index > arraysize)
        {
            return;
        }

        for (int i = index; i < arraysize - 1; i++)
        {
            myArray[i] = myArray[i + 1];
        }
        
        myArray[arraysize - 1] = default(T);
        arraysize--;
    }

    // 指定元素删除 
    public void Remove(T n)
    {
        for (int i = 0; i < myArray.Length; i++)
        {
            if (myArray[i].Equals(n))
            {
                RemoveAt(i);
            }
        }
    }
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90

2. 链表（Linked List）

链表是一种数据元素按照链式存储结构进行存储的数据结构，在每一个节点里存到下一个节点的地址，这种存储结构具有在物理上存在非连续的特点， 链表分为单向链表，双向链表以及循环链表。
在这里插入图片描述

  • 优点：
    • 只需要修改指针，不会有大量元素移动，所以插入和删除元素的速度快。
  • 缺点：
    • 每一次查找都是从头节点开始逐个遍历，所以查找元素速度很慢。
  • 适用场景：
    • 少查询，需要频繁插入或删除的情况。

2.1 代码实现：

单线链表：

public interface ILinkList
{
    bool IsEmpty();
    void Unshift(Object obj);
    Object Shift();
    void Push(Object obj);
    Object Pop();
    bool Contain(Object obj);
    void Delete(Object obj);
    void PrintAll();
    Object GetHead();
    Object GetTail();
    void Clear();
}

class LinkListNode
{
    public Object value;
    public LinkListNode next;

    public LinkListNode(Object value, LinkListNode next)
    {
        this.value = value;
        this.next = next;
    }

    public LinkListNode(Object value)
    {
        this.value = value;
        this.next = null;
    }
}

// 实现单向链表为例子
public class OneWayList : ILinkList
{
    private LinkListNode head, tail;

    public OneWayList()
    {
        this.head = this.tail = null;
    }

    // 判断是否为空  
    public bool IsEmpty()
    {
        return head == null;
    }

    public void Unshift(Object obj)
    {
        head = new LinkListNode(obj, head);
        if (tail == null)
            tail = head;
    }

    public Object Shift()
    {
        if (head == null)
            throw new NullReferenceException();
        Object value = head.value;
        if (head == tail)
            head = tail = null;
        else
            head = head.next;
        return value;
    }

    public void Push(Object obj)
    {
        if (!IsEmpty())
        {
            tail.next = new LinkListNode(obj);
            tail = tail.next;
        }
        else
            head = tail = new LinkListNode(obj);
    }

    public Object Pop()
    {
        if (head == null)
            throw new NullReferenceException();
        Object obj = tail.value;
        if (head == tail)
            head = tail = null;
        else
        {
            // 查找前驱节点
            for (LinkListNode temp = head; temp.next != null && !temp.next.Equals(tail); temp = temp.next)
                tail = temp;
            tail.next = null;
        }
        return obj;
    }

    public void PrintAll()
    {
        string result = "";
        for (LinkListNode temp = head; temp != null; temp = temp.next)
            result += "   " + temp.value.ToString();
        Console.WriteLine(result);
    }

    public bool Contain(Object obj)
    {
        if (head == null)
            return false;
        else
        {
            for (LinkListNode temp = head; temp != null; temp = temp.next)
            {
                if (temp.value.Equals(obj))
                    return true;
            }
        }
        return false;
    }

    public void Delete(Object obj)
    {
        if (!IsEmpty())
        {
            if (head == tail && head.value.Equals(obj))
                head = tail = null;
            else if (head.value.Equals(obj))
                head = head.next;
            else
            {
                // temp_prev为删除值的前驱节点
                for (LinkListNode temp_prev = head, temp = head.next; temp != null; temp_prev = temp_prev.next, temp = temp.next)
                {
                    if (temp.value.Equals(obj))
                    {
                        temp_prev.next = temp.next;   // 设置前驱节点的next为下个节点 
                        if (temp == tail)
                            tail = temp_prev;
                        temp = null;
                        break;
                    }
                }
            }
        }
    }

    public Object GetHead()
    {
        return this.head.value;
    }

    public Object GetTail()
    {
        return this.tail.value;
    }

    public void Clear()
    {
        do
        {
            Delete(head.value);
        } while (!IsEmpty());
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164

双向链表：

public interface ILinkList
{
    bool IsEmpty();
    void Unshift(Object obj);
    Object Shift();
    void Push(Object obj);
    Object Pop();
    bool Contain(Object obj);
    void Delete(Object obj);
    void PrintAll();
    Object GetHead();
    Object GetTail();
    void Clear();
}

class LinkedNode
{
    public Object value;
    public LinkedNode prev;
    public LinkedNode next;

    public LinkedNode(Object value, LinkedNode prev, LinkedNode next)
    {
        this.value = value;
        this.next = next;
        this.prev = prev;
    }
    
    public LinkedNode(Object value)
    {
        this.value = value;
    }
}


// 双向链表
public class DoubleLinkelist : ILinkList
{
    private LinkedNode head, tail;

    public DoubleLinkelist()
    {
        head = tail = null;
    }

    public bool IsEmpty()
    {
        return head == null;
    }

    public void Unshift(Object obj)
    {
        if (IsEmpty())
            head = tail = new LinkedNode(obj);
        else
        {
            head = new LinkedNode(obj, null, head);
            head.next.prev = head;
        }
    }

    public Object Shift()
    {
        if (IsEmpty())
            throw new NullReferenceException();
        Object obj = head.value;
        if (head == tail)
            head = tail = null;
        else
        {
            head = head.next;
            head.prev = null;
        }
        return obj;
    }

    public void Push(Object obj)
    {
        if (IsEmpty())
            head = tail = new LinkedNode(obj);
        else
        {
            tail = new LinkedNode(obj, tail, null);
            tail.prev.next = tail;
        }
    }

    public Object Pop()
    {
        if (IsEmpty())
            throw new NullReferenceException();
        Object value = tail.value;
        if (head == tail)
            head = tail = null;
        else
        {
            tail = tail.prev;
            tail.next = null;
        }
        return value;
    }

    public bool Contain(Object obj)
    {
        if (IsEmpty())
            return false;
        else
        {
            for (LinkedNode temp = head; temp != null; temp = temp.next)
                if (temp.value.Equals(obj))
                    return true;
        }
        return false;
    }

    public void Delete(Object obj)
    {
        if (IsEmpty())
            throw new NullReferenceException();
        if (head == tail)
            head = tail = null;
        else
        {
            for (LinkedNode temp = head; temp != null; temp = temp.next)
            {
                if (temp.value.Equals(obj))
                {
                    if (temp.value.Equals(obj))
                    {
                        if (temp == tail)
                        {
                            tail = tail.prev;
                            tail.next = null;
                            break;
                        }
                        else if (temp == head)
                        {
                            head.next.prev = null;
                            head = head.next;
                        }

                        else
                            temp.prev.next = temp.next;
                    }
                }
            }
        }
    }

    public void PrintAll()
    {
        string result = "";
        for (LinkedNode temp = head; temp != null; temp = temp.next)
            result += "   " + temp.value.ToString();
        Console.WriteLine(result);
    }

    public Object GetHead()
    {
        return this.head.value;
    }

    public Object GetTail()
    {
        return this.tail.value;
    }

    public void Clear()
    {
        do
        {
            Delete(head.value);
        } while (!IsEmpty());
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176

3. 栈（Stack）

栈是限定仅在表尾进行插入或删除操作的一种特殊的线性表。因此，对栈来说，表尾端有特殊含义，称为栈顶（top）， 表头端成为栈底（bottom），栈的修改是按后进先出的原则进行的。 不含元素的空表成为空栈。
在这里插入图片描述

  • 优点：
    • 存取速度比堆要快，仅次于直接位于CPU中的寄存器。
    • 栈中的数据可以共享。
  • 缺点：
    • 存在栈中的数据大小与生存期必须是确定的，缺乏灵活性。
  • 使用场景：
    • 实现递归，表达式求值，括号匹配和浏览器的前进和后退功能等。

3.1 代码实现：

// 链表实现
public class MyLinkedStack<T>
{
    public LinkedNode<T> bottom;    // 栈底
    public LinkedNode<T> top;       // 栈顶 
    private int count = 0;
    public int Count => count;

    public MyLinkedStack()
    {
        bottom = new LinkedNode<T>();
        top = bottom;
    }

    // 推入栈元素 
    public void Push(T value)
    {
        LinkedNode<T> node = new LinkedNode<T>(value);
        node.Next = top;
        top = node;
        count++;
    }

    // 删除并抛出 
    public T Pop()
    {
        if (top == bottom)
            throw new Exception("Stack is empty");      // 空栈
        T value = top.Value;
        top = top.Next;
        count--;
        return value;
    }

    // 输出栈元素 
    public T Pull()
    {
        if (top == bottom)
            throw new Exception("Stack is empty");      // 空栈 
        return top.Value;
    }
}

public class LinkedNode<T>
{
    public T Value { get; set; }
    public LinkedNode<T> Next { get; set; }
    public LinkedNode() { }
    public LinkedNode(T value) => Value = value;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
// 数组实现 
public class MyStack<T>
{
    private T[] items;
    private int top;
    private int count;
    public int Count => count;
    public int Capacity => items == null ? 0 : items.Length;

    public MyStack(int capacity = 10)
    {
        items = new T[capacity + 1];
        top = 0;
        count = 0;
    }

    // 推入栈元素 
    public void Push(T item)
    {
        if (count == Capacity)
            Expansion();
        items[top] = item;
        count++;
        top++;
    }

    // 删除并抛出 
    public T Pop()
    {
        if (count == 0)
            throw new Exception("Stack is empty");
        top--;
        T value = items[top];
        count--;
        return value;
    }

    // 取出栈元素 
    public T Pull()
    {
        if (count == 0)
            throw new Exception("Stack is empty");
        return items[top - 1];
    }

    // 扩容 
    private void Expansion()
    {
        int newCapacity = Capacity * 2;
        T[] newItems = new T[newCapacity];

        for (int i = 0; i < top; i++)
            newItems[i] = items[i];
        items = newItems;
    }
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

4. 队列（Queue）

队列也是一种特殊的线性表，只在表头（也称为队头）进行删除操作，只在表尾（也称为队尾）进行插入操作。由于队列的修改是按先进先出的原则，所以队列又称为先进先出（First In First Out）表，简称FIFO表。
在这里插入图片描述

  • 优点：
    • 提供先进先出的存储方式，添加速度快，允许重复。
    • 队列中的数据可以共享。
  • 缺点：
    • 只能在一头添加，另一头获取，存取其他元素速度会很慢。
  • 使用场景：
    • 多线程阻塞时经常使用队列来解决。
    • 模拟生活中的排队场景。

4.1 代码实现：

// 链表实现队列
public class LinkedQueue<T>
{
    public LinkedNode<T> front;
    public LinkedNode<T> rear;
    private int count;
    public int Count => count;

    public LinkedQueue()
    {
        count = 0;
    }

    // 加入队列元素 
    public void Enqueue(T value)
    {
        LinkedNode<T> node = new LinkedNode<T>(value);
        if (front == null)
        {
            front = node;
            rear = front;
        }
        else
        {
            rear.Next = node;
            rear = node;
        }
        count++;
    }

    // 取出队列元素并删除 
    public T Dequeue()
    {
        if (front == null)
            throw new Exception("Queue is empty");      // 空队列 
        T value = front.Value;
        front = front.Next;
        count--;
        return value;
    }

    // 取出队列元素 
    public T Pull()
    {
        if (front == null)
            throw new Exception("Queue is empty");      // 空队列 
        return front.Value;
    }
}

// 链表节点 
public class LinkedNode<T>
{
    public T Value { get; set; }
    public LinkedNode<T> Next { get; set; }

    public LinkedNode() { }
    public LinkedNode(T value) => Value = value;
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
// 数组实现队列 
public class MyQueue<T>
{
    private T[] items;
    public int front;
    public int rear;
    private int count;
    public int Count => count;
    public int Capacity => items == null ? 0 : items.Length;

    public MyQueue(int capacity = 10)
    {
        items = new T[capacity];
        front = 0;
        rear = 0;
        count = 0;
    }

    // 加入队列元素 
    public void Enqueue(T item)
    {
        if (count >= Capacity)
            Expansion();
        items[rear] = item;
        rear = (rear + 1) % Capacity;
        count++;
    }

    // 取出队列元素 
    public T Dequeue()
    {
        if (count == 0)
            throw new Exception("The queue is empty");     // 空队列 
        T value = items[front];
        count--;
        front = (front + 1) % Capacity;
        return value;
    }

    // 查看队列元素 
    public T Pull()
    {
        if (count == 0)
            throw new Exception("Queue is empty");      // 空队列  
        return items[front];
    }

    // 扩容 
    private void Expansion()
    {
        int newCapacity = Capacity * 2;
        T[] newItems = new T[newCapacity];
        for (int i = front; i < count; i++)
            newItems[i - front] = items[i % Capacity];
        items = newItems;
        front = 0;
        rear = count;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59

5. 哈希表（Hash）

哈希表（Hash table，也叫散列表），是一种有限连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录。通常散列表的存储空间是一个一维数组，散列地址是数组的下标。
在这里插入图片描述

  • 优点：
    • 如果关键字已知则存取速度极快，支持高效的数据插入、删除和查找操作。
  • 缺点：
    • 不支持快速顺序遍历散列表中的数据。
  • 使用场景：
    • 哈希表适用于那种查找性能要求高，数据元素之间无逻辑关系要求的情况，同时哈希表在海量数据处理中有着广泛应用。

5.1 代码实现:

using System;
using UnityEngine;     

public class MyHashTable
{
    // 初始化哈希表
    int[] hashTable;

    // 创建哈希表
    public void CreateHashTable(int[] intArray)
    {
        hashTable = new int[intArray.Length];
        for (int i = 0; i < intArray.Length; i++)
        {
            Insert(intArray[i]);
        }
    }

    public void ShowData()
    {
        Debug.Log("展示哈希表中的数据：" + String.Join(",", hashTable));
    }

    /// <summary>
    /// 插入
    /// </summary>
    /// <param name="value">待插入值</param>
    public void Insert(int value)
    {
        // 哈希函数，除留余数法
        int hashAddress = Hash(value);
        // 如果不为0，则说明发生冲突
        while (hashTable[hashAddress] != 0)
        {
            // 利用开放定址的线性探测法解决冲突
            hashAddress = (++hashAddress) % hashTable.Length;
        }
        // 将待插入值存入字典中
        hashTable[hashAddress] = value;
    }

    /// <summary>
    /// 哈希表查找
    /// </summary>
    /// <param name="value">待查找的值</param>
    /// <returns>对应的下标</returns>
    public int Search(int value)
    {
        int hashAddress = Hash(value);
        // 冲突发生
        while (hashTable[hashAddress] != value)
        {
            // 利用开放定址的线性探测法解决冲突
            hashAddress = (++hashAddress) % hashTable.Length;
            // 查找到了开放单元或者循环回到原点，表示查找失败
            if (hashTable[hashAddress] == 0 || hashAddress == Hash(value)) { return -1; }
        }
        // 查找成功，返回值的下标
        return hashAddress;
    }

    /// <summary>
    /// 哈希函数（除留余数法）
    /// </summary>
    /// <param name="value"></param>
    /// <returns>返回数据的位置</returns>
    private int Hash(int value)
    {
        return value % hashTable.Length;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71

非线性结构

非线性结构每个元素可能与零个或者多个数据元素有着联系。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。

1. 树（Tree）

树结构是一类重要的非线性数据结构。树是以分支关系定义的层级结构，作为一种树状的数据结构，其数据节点之间的关系也如大树一样，将有限个节点根据不同层次关系进行排列，从而形成数据与数据之间的父子关系。
在这里插入图片描述

  • 优点：
    • 常用的树有二叉树，红黑树等，在树总是平衡的情况下，查找，插入，删除元素都很快。
  • 缺点：
    • 例如红黑树，2-3-4树，B+树等一些复杂的树功能算法实现难度较大。
  • 使用场景：
    • 文件系统的目录结构
    • MySQL数据库索引
    • 数据文件的压缩技术
    • 深度优先搜索算法是一种用于遍历或搜索树或图的算法。

1.1 代码实现：

// 以实现简单二叉树为例子 
class BinaryTree<TKey, TValue> where TKey : IComparable
{
    public TKey Key { get; set; }           // 键
    public TValue Value { get; set; }       // 值 

    BinaryTree<TKey, TValue> Left { get; set; }     // 左分支 
    BinaryTree<TKey, TValue> Right { get; set; }    // 右分支 

    // 构造函数初始化 
    public BinaryTree(TKey key, TValue value)
    {
        this.Key = key;
        this.Value = value;
    }

    //  查找功能 
    public TValue Search(TKey key)
    {
        int ret = key.CompareTo(this.Key);

        if (ret == 0)
        {
            return Value;
        }
        else
        {
            var subTree = ret < 0 ? Left : Right;
            if (subTree == null)
            {
                throw new KeyNotFoundException();
            }
            else
            {
                return subTree.Search(key);
            }
        }
    }

    // 插入功能
    public void Insert(TKey key, TValue value)
    {
        int ret = key.CompareTo(this.Key);

        if (ret == 0)
        {
            this.Value = value;
        }
        else
        {
            var subTree = ret < 0 ? Left : Right;
            if (subTree == null)
            {
                subTree = new BinaryTree<TKey, TValue>(key, value);
                if (ret < 0)
                    Left = subTree;
                else
                    Right = subTree;
            }
            else
            {
                subTree.Insert(key, value);
            }
        }
    }

    // 二叉排序树性的遍历 
    public void Visit(Action<TKey, TValue> visitor)
    {
        if (Left != null)
        {
            Left.Visit(visitor);
        }

        visitor(Key, Value);

        if (Right != null)
        {
            Right.Visit(visitor);
        }
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82

2. 堆（Heap）

当一棵优先级树是近似满二叉树时，称其为堆和偏序树。极小化优先数相应的堆称为极小化堆；极大化优先级树相应的堆称为极大化堆。
在这里插入图片描述

  • 优点：
    • 堆是一颗完全二叉树
    • 可以动态地分配内存大小
  • 缺点：
    • 要在运行时动态分配内存，存取速度较慢。
  • 使用场景：
    • 需要求一段序列的中位数时
    • 按照某种优先级来的优先级队列， 通常就是用堆来实现
    • 找出数组中的最大的前K个数，或者最小的前K个数，使用大顶堆或者小顶堆来完成。

2.1 代码实现：

// 小根堆的实现
public class BinaryHeap<T>
{
    //默认容量为6
    private const int DEFAULT_CAPACITY = 6;
    private int mCount;
    private T[] mItems;
    private Comparer<T> mComparer;

    public BinaryHeap() : this(DEFAULT_CAPACITY) { }

    public BinaryHeap(int capacity)
    {
        if (capacity < 0)
        {
            throw new IndexOutOfRangeException();
        }
        mItems = new T[capacity];
        mComparer = Comparer<T>.Default;
    }

    // 增加元素到堆，并从后往前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点
    public bool Enqueue(T value)
    {
        if (mCount == mItems.Length)
        {
            ResizeItemStore(mItems.Length * 2);
        }

        mItems[mCount++] = value;
        int position = BubbleUp(mCount - 1);

        return (position == 0);
    }

    // 取出堆的最小值
    public T Dequeue()
    {
        return Dequeue(true);
    }

    private T Dequeue(bool shrink)
    {
        if (mCount == 0)
        {
            throw new InvalidOperationException();
        }
        T result = mItems[0];
        if (mCount == 1)
        {
            mCount = 0;
            mItems[0] = default(T);
        }
        else
        {
            --mCount;
            //取序列最后的元素放在堆顶
            mItems[0] = mItems[mCount];
            mItems[mCount] = default(T);
            // 维护堆的结构
            BubbleDown();
        }
        if (shrink)
        {
            ShrinkStore();
        }
        return result;
    }

    private void ShrinkStore()
    {
        // 如果容量不足一半以上，默认容量会下降。
        if (mItems.Length > DEFAULT_CAPACITY && mCount < (mItems.Length >> 1))
        {
            int newSize = Math.Max(
                DEFAULT_CAPACITY, (((mCount / DEFAULT_CAPACITY) + 1) * DEFAULT_CAPACITY));

            ResizeItemStore(newSize);
        }
    }

    private void ResizeItemStore(int newSize)
    {
        if (mCount < newSize || DEFAULT_CAPACITY <= newSize)
        {
            return;
        }

        T[] temp = new T[newSize];
        Array.Copy(mItems, 0, temp, 0, mCount);
        mItems = temp;
    }

    public void Clear()
    {
        mCount = 0;
        mItems = new T[DEFAULT_CAPACITY];
    }

    // 从前往后依次对各结点为根的子树进行筛选，使之成为堆，直到序列最后的节点
    private void BubbleDown()
    {
        int parent = 0;
        int leftChild = (parent * 2) + 1;
        while (leftChild < mCount)
        {
            // 找到子节点中较小的那个
            int rightChild = leftChild + 1;
            int bestChild = (rightChild < mCount && mComparer.Compare(mItems[rightChild], mItems[leftChild]) < 0) ?
                rightChild : leftChild;
            if (mComparer.Compare(mItems[bestChild], mItems[parent]) < 0)
            {
                // 如果子节点小于父节点, 交换子节点和父节点
                T temp = mItems[parent];
                mItems[parent] = mItems[bestChild];
                mItems[bestChild] = temp;
                parent = bestChild;
                leftChild = (parent * 2) + 1;
            }
            else
            {
                break;
            }
        }
    }

    // 从后往前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点
    private int BubbleUp(int startIndex)
    {
        while (startIndex > 0)
        {
            int parent = (startIndex - 1) / 2;
            //如果子节点小于父节点，交换子节点和父节点
            if (mComparer.Compare(mItems[startIndex], mItems[parent]) < 0)
            {
                T temp = mItems[startIndex];
                mItems[startIndex] = mItems[parent];
                mItems[parent] = temp;
            }
            else
            {
                break;
            }
            startIndex = parent;
        }
        return startIndex;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148

3. 图（Graph）

图（Graph）G由V和E两个集合组成，记为G=（V, E）。其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集合，这些顶点偶对称为边。通常，也将图G的顶点集合和边集合分别为V（G）和E（G）。E（G）可以是空集，此时图G中只有顶点而没有边。
在这里插入图片描述

  • 优点：
    • 简单直观，可以快速查到一个顶点和另一顶点之间的关联关系。
  • 缺点：
    • 占用空间大，如果一个图有1000个顶点，其中只有10个顶点之间有关联（这种情况叫作稀疏图），却不得不建立一个1000X1000的二维数组。
  • 使用场景：
    • 图的应用十分广泛，可以用来模拟生活中的社交关系， 网址安全，设备安全，知识图谱等。

3.1 代码实现：

public class Vertex
{
    public string Data;
    public bool IsVisited;
    
    public Vertex(string Vertexdata)
    {
        Data = Vertexdata;
    }
}

// 图的简单实现 
public class Graph
{
    //图中所能包含的点上限
    private const int Number = 10;

    //顶点数组
    private Vertex[] vertiexes;

    //邻接矩阵
    public int[,] adjmatrix;

    //统计当前图中有几个点
    int numVerts = 0;

    //初始化图
    public Graph()
    {
        //初始化邻接矩阵和顶点数组
        adjmatrix = new Int32[Number, Number];
        vertiexes = new Vertex[Number];
        //将代表邻接矩阵的表全初始化为0
        for (int i = 0; i < Number; i++)
        {
            for (int j = 0; j < Number; j++)
            {
                adjmatrix[i, j] = 0;
            }
        }
    }

    //向图中添加节点
    public void AddVertex(String v)
    {
        vertiexes[numVerts] = new Vertex(v);
        numVerts++;
    }

    //向图中添加有向边
    public void AddEdge(int vertex1, int vertex2)
    {
        adjmatrix[vertex1, vertex2] = 1;
        //adjmatrix[vertex2, vertex1] = 1;
    }

    //显示点
    public void DisplayVert(int vertexPosition)
    {
        Console.WriteLine(vertiexes[vertexPosition] + " ");
    }
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62

注意

本章部分图文内容来源于网站和书籍资料提供, 自己整理收集,方便学习参考,版权属于原作者。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/645794
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号