C#_数据结构--数据表(顺序表,链表,栈,队列)

 

常见的线性表:

     1.顺序表          List<>       表中元素有索引和固定连续的顺序, 方便元素遍历和查找

     2.链表              需要自己构建, 有固定的链接,没有索引      方便元素插入和删除

     3.栈                 Stack<T>    类似于一个桶,后进入的元素先出去         FILO

     4.队列             Queue<>     类似于一个通道,先进入的元素先出去     FIFO 

     5.字典             Dictionary<> 键值对组合 键是唯一的 值与键一一对应  Key-->Value 

 

   一. 顺序表的数据结构  (代码实现)  1 class MySeqList<T>

 {  3         private T[] _Ts;       // 顺序表基于一个数组
        private int _flag;    //实际存在的成员个数  5 

        //构造函数 给封装变量赋予初始值
        public MySeqList(int Max)  9  {  10             _Ts = new T[Max];   //定义顺序表容量
            _flag = 0;  12  }  13         //构造函数 重载
        public MySeqList()  15  {  16             _Ts = new T[10];  17             _flag = 0;  18  }  19 
        //得到顺序表实有长度
        public int Count()  22  {  23             return _flag;  24  }  25    

        //从表尾加入元素
        public void Add(T Item) {  29             if (_flag>=_Ts.Length)  30  {  31                 Console.WriteLine("out of length");  32                 return;  33  }  34             _Ts[_flag] = Item;  35             _flag++;  36  }  37 
        //删除元素
        public int Remove(T Item) {  40             int returnValue = -1;  41             for (int i = 0; i < _flag; i++)  42  {  43                 if (_Ts[i].Equals(Item))  44  {  45                     returnValue = i;  46  RemoveAt(i);  47                     break;  48  }  49  }  50             return returnValue;  51  }  52 

        //按照索引号删除对应元素
        public void RemoveAt(int Index)  56  {  57             if (Index<0||Index>=_flag)  58  {  59                 Console.WriteLine("out of range");  60  }  61             for (int i = Index; i < _flag; i++)  62  {  63                 _Ts[i] = _Ts[i + 1];  64  }  65             _flag--;  66 
 }  68 

        //找到对应元素的索引号
        public int IndexOf(T Item) {  72             for (int i = 0; i < _flag; i++)  73  {  74                 if (_Ts[i].Equals(Item))  75  {  76                     return i;  77  }  78  }  79             return -1;  80  }  81 

        //按索引号插入元素到指定位置
        public void Insert(int Index,T Item) {  85             if (Index>_flag)  86  {  87                 Console.WriteLine("out of range");  88                 return;  89  }  90             if (_flag>=_Ts.Length)  91  {  92                 Console.WriteLine("out of length");  93                 return;  94  }  95             for (int i = _flag; i >Index; i--)  96  {  97                 _Ts[i] = _Ts[i - 1];  98  }  99             _Ts[Index] = Item; 100             _flag++; 101  } 102 

        //展示所有元素
        public void ShowItem(Action<T> act) { 106             for (int i = 0; i < _flag; i++) 107  { 108  act(_Ts[i]); 109               // Console.WriteLine(_Ts[i]); 110               //当类型为system库中已经规定的类型(如 int,string等)时,可以启用 否则需使用委托
 } 112  } 

 //翻转 (倒置)
        public void Reverse() { 3             for (int i = 0; i < _flag/2; i++) 4  { 5                 T temp=_Ts[i]; 6                 _Ts[i]=_Ts[_flag-i-1]; 7                 _Ts[_flag - i - 1] = temp; 8  } 9         }

    }

 二. 链表  (代码实现)

       首先需要定义一个Node类,去作为链表的单个节点元素    

public class Node<T>
 {  3         public T Data;       //节点的值
        public Node<T> Next;  //节点的下一个节点地址
        public Node() {  6             Data=default(T);  7             Next = null;  8  }  9         public Node(T data) 10  { 11             Data = data; 12             Next = null; 13  } 14     }

        然后去写链表的结构

 class LinkList<T>
 {  3         private Node<T> _head;  // 定义一个Node类型 作为链表的引出项
        private int _count;     //表中元素个数  5 
        //构造函数
        public LinkList() {  8             _count = 0;  9             _head = new Node<T>();  10  }  11 
        //获取长度
        public int length() {  14             return _count;  15  }  16 
        //添加节点
        public void Addnode(Node<T> newNode) {  19             Node<T> temp = _head;  20             while (temp.Next!=null)  21  {  22                 temp = temp.Next;  23  }  24             temp.Next = newNode;  25             _count++;  26  }  27 
        //插入节点
        public void Insert(int index,Node<T> newNode) {  30             if (index<0||index>_count)  31  {  32                 Console.WriteLine("Can not do this method");  33  }  34             Node<T> temp = _head;  35             for (int i = 0; i < index; i++)  36  {  37                 temp = temp.Next;  38  }  39             newNode.Next = temp.Next;  40             temp.Next = newNode;  41             _count++;  42  }  43 
        //查找元素位置
        public int IndexOf(Node<T> Item)  46  {  47             Node<T> temp = _head;  48             for (int i = 0; i < _count; i++)  49  {  50                 temp = temp.Next;  51                 if (temp.Data.Equals(Item.Data))  52  {  53                     return i;  54  }  55  }  56             return -1;  57  }  58 

        //按索引移除节点
        public T RemoveAt(int index) {  62 
            if (index<0||index>=_count)  64  {  65                 Console.WriteLine("out of range");  66                 return default(T);  67  }  68             Node<T> temp = _head;  69             for (int i = 0; i < index; i++)  70  {  71                 temp = temp.Next;  72  }  73             Node<T> getNode = temp.Next;  74             temp.Next = temp.Next.Next;  75             getNode.Next = null;  76             _count++;  77             return getNode.Data;  78  }  79        

        //展示所有元素
        public void ShowItem(Action<T> act) {  83             if (_count==0)  84  {  85                 Console.WriteLine("empty!");  86                 return;  87  }  88             Node<T> temp=_head;  89             for (int i = 0; i < _count; i++)  90  {  91                 temp = temp.Next;  92  act(temp.Data);  93  }  94  }  95 
        //展示所有元素 重载
        public void ShowItem()  98  {  99             if (_count == 0) 100  { 101                 Console.WriteLine("empty!"); 102                 return; 103  } 104             Node<T> temp = _head; 105             for (int i = 0; i < _count; i++) 106  { 107                 temp = temp.Next; 108  Console.WriteLine(temp.Data); 109  } 110         }
     拓展操作 :

//根据节点数据删除元素
         public int Romove(Node<T> Item)  3  {  4             int index = -1;  5             Node<T> temp = _head;  6             
            for (int i = 0; i < _count; i++)  8  {  9                 temp = temp.Next; 10                 if (temp.Data.Equals(Item.Data)) 11  { 12  RemoveAt(i); 13                     return index = i; 14  } 15  } 16             return index; 17  } 18        
         //数据类型为<T>的情况 移除最小值 注:只有数值类型可以进行此操作 如int,float,double.....
         public T RemoveMin(Func<Node<T>, Node<T>, bool> _func) 21  { 22             Node<T> delPreMin, delMin, preMin, Min; 23             delMin = Min = _head.Next; 24             delPreMin = preMin = _head; 25             while (Min!=null) 26  { 27                 if (_func(delMin,Min)) 28  { 29                     delMin = Min; 30                     delPreMin = preMin; 31                     
                    break; 33  } 34                 Min = Min.Next; 35                 preMin = preMin.Next; 36  } 37             delPreMin.Next = delPreMin.Next.Next; 38             delMin.Next = null; 39             _count--; 40             return delMin.Data; 41  } 42        
         //颠倒元素
         public void Reverse() { 45              Node<T> temA,temB; 46              temB = _head.Next; 47              _head.Next = null; 48              while (temB!=null) 49  { 50                  temA = temB.Next; 51                  temB.Next = _head.Next; 52                  _head.Next = temB; 53                  temB = temA; 54  } 55          }

         }

三. 栈和队列都是受限的线性表

     栈常用的方法:

             Stack<type> sta=new Stack<type>();      定义一个栈

             sta .pop           出栈(移除并返回栈顶元素)

             sat .push          进栈,压栈

             sat .peek          获取栈顶元素,但不将其移除

             sta.ToArray        转化为数组( type[] Its=sta.toArray(); 注意 Its[0]为栈顶元素,栈顺序为先进后出 )

      队列常用方法:

            Queue<type> que=new Queue<type>();        定义一个队列      

            que.Dequeue         出队(移除并返回队首元素)  

            que.Enqueue        入队

            que.Peek            获取队首元素(不移除)

            que.ToArray         转化为数组 ( type[] Its=que.toArray(); 注意 Its[0]为队首元素,队列顺序为先进先出 )

四.字典

     key;Value

      用于信息持久化存储