研究数据如何在程序中进行组织的一种方法 数据和数据之间一般存在着某种特定关系

集合关系

数据元素之间唯一的关系就是同属于一个集合 无序且唯一

线性结构关系

数据元素之间有着一对一的关系

树形结构关系

数据元素之间有着一对多的关系

图状结构关系

数据元素之间有着多对多的关系

C# 开发过程中常用的数据结构

数组Array 动态数组 ArrayList 泛型List 双向链表LinkedList 栈Stack 队列Queue 字典Dicitionary

线性表

由相同数据类型的元素所结构成的有限序列

1. 顺序表：将线性表中的节点按照逻辑顺序一次存放在一组地址的存储单元中 Array
2. 链表：
   • 单向链表：链表的链接方向是单向的，对链表的访问需要通过顺序从头开始
   • 环形链表：尾巴节点指向头节点 形成一个环 从环表的任何节点出来 都能找到其他节点
   • 双向链表：每个节点都有两个指针，分别指向直接前驱和直接后驱

双向链表代码

using UnityEngine;

namespace 数据结构
{
    public class ListNode
    {
        public int Value;
        public ListNode Before;
        public ListNode Next;

        public ListNode(int newValue)
        {
            Value = newValue;
        }
    }

    // 双向链表类
    public class LinkList
    {
        private ListNode _headNode;
        private ListNode _tailNode;

        private int _listCount;

        private ListNode _current;

        public LinkList()
        {
            _listCount = 0;
            _headNode = null;
            _tailNode = null;
        }

        public LinkList MoveFirst()
        {
            _current = _headNode;
            return this;
        }

        public LinkList MoveLast()
        {
            _current = _tailNode;
            return this;
        }

        // 移动到下一项
        public LinkList MoveNext()
        {
            if (_current.Next != null)
            {
                _current = _current.Next;
            }

            return this;
        }

        public bool IsNull()
        {
            return _headNode == null;
        }

        // 追加节点
        public LinkList Append(int data)
        {
            ListNode newNode = new ListNode(data);
            if (IsNull())
            {
                _headNode = newNode;
                _tailNode = newNode;
            }
            else
            {
                _tailNode.Next = newNode;
                newNode.Before = _tailNode;
                _tailNode = newNode;
            }

            _current = newNode;
            _listCount++;
            return this;
        }

        public void Delete()
        {
            if (IsNull())
                return;
            if (_current == _headNode)
            {
                _headNode = _headNode.Next;
                _current = _headNode;
                _current.Before = null;
                _listCount--;
                return;
            }

            if (_current == _tailNode)
            {
                _tailNode = _tailNode.Before;
                _current = _tailNode;
                _current.Next = null;
                _listCount--;
                return;
            }

            _current.Before.Next = _current.Next;
            _current.Next.Before = _current.Before;
            _current = _current.Before;
            _listCount--;
        }

        public void Show(bool forward)
        {
            if (forward)
            {
                ListNode temp = _headNode;
                while (temp != null)
                {
                    Debug.Log(temp.Value);
                    temp = temp.Next;
                }
            }
            else
            {
                ListNode temp = _tailNode;
                while (temp != null)
                {
                    Debug.Log(temp.Value);
                    temp = temp.Before;
                }
            }
            
        }

        public void Insert(int data)
        {
            ListNode newNode = new ListNode(data);
            if (IsNull())
            {
               Append(data);
               return;
            }

            if (_headNode == _current)
            {
                _headNode = newNode;
                _current.Before = _headNode;
                _headNode.Next = _current;
                _current = _headNode;
                _listCount++;
                return;
            }

            newNode.Before = _current.Before;
            newNode.Next = _current;
            _current.Before.Next = newNode;
            _current.Before = newNode;
            _current = newNode;
            _listCount++;
        }
    }
}
------------------------------------------------------------------------
using System;
using UnityEngine;

namespace 数据结构
{
    public class Test : MonoBehaviour
    {
        private void Start()
        {
            LinkList link = new LinkList();
            link.Append(1);
            link.Append(2);
            link.Append(3);
            link.Append(4);
            link.Append(5);
            link.Append(6);
            link.MoveFirst();
            link.Insert(9999);
            link.MoveNext().Insert(232323);
            link.Delete();
            link.Show(true);
        }
    }
}

栈的实现

在表的尾端进行操作的线性表

using UnityEngine;

namespace 数据结构
{
    public class StackData
    {
        public StackData Next;
        public object Data;

        public StackData(object data, StackData next)
        {
            Data = data;
            Next = next;
        }
    }

    public class MyStack
    {
        private StackData _top; // 栈顶

        // 入栈
        public void Push(object data)
        {
            _top = new StackData(data, _top);
        }

        // 出栈
        public object Pop()
        {
            if (_top == null)
                return null;
            object data = _top.Data;
            _top = _top.Next;
            return data;
        }
    }
}

using UnityEngine;

namespace 数据结构
{
    public class Test : MonoBehaviour
    {
        private void Start()
        {
            MyStack myStack = new MyStack();
            myStack.Push(1);
            myStack.Push(2);
            myStack.Push(3);
            myStack.Push(4);
            myStack.Push(5);
            myStack.Push(6);
            print(myStack.Pop());
            print(myStack.Pop());
            print(myStack.Pop());
            print(myStack.Pop());
            print(myStack.Pop());
            print(myStack.Pop());
        }
    }
}

队列原则：插入操作在表尾执行 其他操作在表头执行

namespace 数据结构
{
    public class QueueData
    {
        public object Data;
        public QueueData Next;

        public QueueData(object data)
        {
            Data = data;
        }
    }

    public class MyQueue
    {
        private QueueData _top;
        private QueueData _bottom;

        public void EnQueue(object data)
        {
            QueueData queue = new QueueData(data);
            if (_bottom == null)
            {
                _bottom = queue;
                _top = _bottom;
            }
            else
            {
                _top.Next = queue;
                _top = queue;
            }
        }

        public object DeQueue()
        {
            object data = _bottom.Data;
            _bottom = _bottom.Next;
            return data;
        }
    }
}

二叉树

每个节点最多有两个子数的树结构（左子树Leftsubtree 右子树rightsubtree）