数据结构和算法——线性表

顺序存储结构

Array

引用类型（托管堆）
初始化时需要设置默认值

实现自己的ArrayList

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 
  6 namespace ConsoleAppMyArrayList
  7 {
  8     public class MyArrayList
  9     {
 10         //容量
 11         private const int _defaultCapacity = 4;
 12         //存放数组元素
 13         private object[] _items;
 14         //数组大小
 15         private int _size;
 16         //元素个数为0的数组状态
 17         private static readonly object[] emptyArray = new object[0];
 18 
 19         public MyArrayList()
 20         {
 21             this._items = emptyArray;
 22         }
 23 
 24         public MyArrayList( int capacity)
 25         {
 26             if (capacity<0)
 27             {
 28                 throw new ArgumentOutOfRangeException(nameof(capacity),"ArrayList的容量不可为负数！");
 29             }
 30             this._items = new object[capacity];
 31         }
 32 
 33         //索引器
 34         public virtual object this[int index]
 35         {
 36             get 
 37             {
 38                 if (index<0||index>=this._size)
 39                 {
 40                     throw new ArgumentOutOfRangeException(nameof(index),"索引超出范围！");
 41                 }
 42                 return this._items[index];
 43             }
 44 
 45             set 
 46             {
 47                 if (index < 0 || index >= this._size)
 48                 {
 49                     throw new ArgumentOutOfRangeException(nameof(index), "索引超出范围！");
 50                 }
 51                 this._items[index] = value;
 52             }
 53 
 54         }
 55 
 56         //当前数组元素个数
 57         public virtual int Count
 58         {
 59             get {return this._size ;}
 60         }
 61 
 62         //数组的容量
 63         public virtual int Capacity
 64         {
 65             get { return this._items.Length; }
 66             set 
 67             {
 68                 if (value!=this._items.Length)
 69                 {
 70                     if (value<this._size)
 71                     {
 72                         throw new ArgumentOutOfRangeException(nameof(value),"容量太小");
 73                     }
 74                     if (value > 0)
 75                     {//开辟新内存空间存储元素
 76                         object[] dest = new object[value];
 77                         if (this._size > 0)
 78                         {//搬动元素
 79                             Array.Copy(this._items, 0, dest, 0, this._size);
 80                         }
 81                         this._items = dest;
 82                     }
 83                     else//数组最小的空间为4
 84                     {
 85                         this._items=new object[_defaultCapacity]; 
 86                     } 
 87                 }
 88             }
 89         }
 90 
 91         //元素的添加
 92         public virtual int Add(object value)
 93         {//当空间已满
 94             if (this._size==this._items.Length)
 95             {
 96                 this.EnsureCapacity(this._size+1);
 97             }
 98             this._items[this._size] = value;
 99             return this._size++;
100         }
101 
102         //扩容
103         private void EnsureCapacity(int p)
104         {
105             if (this._items.Length<p)
106             {//空间加倍
107                 int num = (this._items.Length == 0) ? _defaultCapacity : (this._items.Length * 2);
108                 if (num < p)
109                 {
110                     num = p;
111                 }
112                 this.Capacity = num;
113             } 
114         }
115 
116         //指定位置插入元素
117         public virtual void Insert( int index,object value)
118         {
119             if (index<0||index>this._size)
120             {
121                 throw new ArgumentOutOfRangeException(nameof(index),"索引超出范围！");
122             }
123             if (this._size==this._items.Length)
124             {
125                 this.EnsureCapacity(this._size + 1);
126             }
127             if (index<this._size)
128             {
129                 Array.Copy(this._items, index, this._items, index + 1, this._size - index);
130             }
131             this._items[index] = value;
132             this._size++;
133         } 
134 
135         //移除指定索引的元素
136         public virtual void Remove(int index)
137         {
138             if (index < 0 || index > this._size)
139             {
140                 throw new ArgumentOutOfRangeException(nameof(index), "索引超出范围！");
141             }
142             this._size--;
143             if (index<this._size)
144             {
145                 Array.Copy(this._items,index+1,this._items,index,this._size-index);
146             }
147             this._items[this._size]=null; 
148         }
149 
150         //裁剪空间
151         public virtual void TrimToSize()
152         {
153             this.Capacity = this._size;
154         }
155     }
156 }

链式存储结构

链表

单向链表

循环链表

实现自己的循环链表

  1 using System;
  2 
  3 namespace ConsoleAppLinked
  4 {
  5     class CirculLinkedList
  6     {
  7         //元素个数
  8         private int count;
  9 
 10         //尾指针
 11         private Node tail;
 12 
 13         //当前节点的前节点
 14         private Node CurrPrev;
 15 
 16 
 17         //增加元素
 18         public void Add(object value)
 19         {
 20             Node newNode = new Node(value);
 21             if (tail==null)
 22             {//链表为空
 23                 tail = newNode;
 24                 tail.next = newNode;
 25                 CurrPrev = newNode;
 26             }
 27             else
 28             {//链表不为空，把元素增加到链表结尾
 29                 newNode.next = tail.next;
 30                 tail.next = newNode;
 31 
 32                 if (CurrPrev==tail)
 33                 {
 34                     CurrPrev = newNode;
 35                 }
 36                 tail = newNode;
 37             }
 38             count++;
 39         }
 40 
 41         //删除当前元素
 42         public void RemoveCurrNode()
 43         {
 44             //为null代表为空表
 45             if (tail == null) 
 46             {
 47                 throw new NullReferenceException("集合中没有任何元素！");
 48             }
 49             else if (count==1)
 50             {
 51                 tail = null;
 52                 CurrPrev = null;
 53             }
 54             else
 55             {
 56                 if (CurrPrev.next==tail)
 57                 {
 58                     tail = CurrPrev;
 59                 }
 60                 CurrPrev.next = CurrPrev.next.next;
 61             }
 62             count--;
 63         }
 64 
 65         //当前节点移动步数
 66         public void Move(int step)
 67         {
 68             if (step<0)
 69             {
 70                 throw new ArgumentOutOfRangeException("step", "移动步数不可为负数！");
 71             }
 72             if (tail==null)
 73             {
 74                 throw new NullReferenceException("链表为空！");
 75             }
 76             for (int i = 0; i < step; i++)
 77             {
 78                 CurrPrev = CurrPrev.next;
 79             }
 80         }
 81 
 82         //获得当前节点
 83         public object Current
 84         {
 85             get {return CurrPrev.next.item ;}
 86         }
 87 
 88         public override string ToString()
 89         {
 90             if (tail==null)
 91             {
 92                 return string.Empty;
 93             }
 94             string s = "";
 95             Node temp = tail.next;
 96             for (int i = 0; i < count; i++)
 97             {
 98                 s += temp.ToString() + "    ";
 99                 temp = temp.next;
100             }
101             return s;
102         }
103 
104 
105         public int Count
106         {
107             get {return count ;}
108         }
109 
110         private   class Node
111         {
112             public Node(object  value)
113             {
114                 item = value;
115             }
116             //放置数据
117             public object item;
118             public CirculLinkedList.Node next;
119             public override string ToString()
120             {
121                 return item.ToString();
122             }
123         }
124     }
125 }

双向链表

数据结构和算法——线性表

顺序存储结构

Array

链式存储结构

链表

单向链表

循环链表

双向链表