线性表的链式存储——单链表

时间:2023-02-22 19:52:41
线性表的链式存储——单链表线性表的链式存储——单链表
  1         public interface IListliner<T>
  2     {
  3         T GetElement(int i);
  4         void Insert(T t, int i);
  5         void Add(T t);
  6         void Delete(int i);
  7         //获取线性表长度
  8         int GetLength();
  9         bool IsEmpty();
 10         int LocationElement(T t);
 11         void Clear();
 12         void Reverse();
 13     }
 14     /// <summary>
 15     /// 链表节点类型
 16     /// </summary>
 17     /// <typeparam name="T"></typeparam>
 18     class Node<T>
 19     {
 20         /// <summary>
 21         /// 数据
 22         /// </summary>
 23         private T tdata;
 24         public T Data
 25         {
 26             get { return this.tdata; }
 27             set { this.tdata = value; }
 28         }
 29         /// <summary>
 30         /// 节点位置
 31         /// </summary>
 32         private Node<T> nNext;
 33         public Node<T> Next
 34         {
 35             get { return this.nNext; }
 36             set { this.nNext = value; }
 37         }
 38         public Node()
 39         {
 40             this.tdata = default(T);
 41             this.nNext = null;
 42         }
 43         public Node(T t)
 44         {
 45             this.tdata = t;
 46             this.nNext = null;
 47         }
 48         public Node(T t, Node<T> node)
 49         {
 50             this.tdata = t;
 51             this.nNext = node;
 52         }
 53     }
 54     /// <summary>
 55     /// 表示链表添加元素的位置:头部和尾部
 56     /// </summary>
 57     enum AddPosition
 58     {
 59         Head,
 60         Tail
 61     }
 62 
 63     /// <summary>
 64     /// 单链表类
 65     /// </summary>
 66     /// <typeparam name="T"></typeparam>
 67     class Linkedlist<T> : IListliner<T>
 68     {
 69         //链表头部
 70         private Node<T> tHead;
 71         public Node<T> Head
 72         {
 73             get { return this.tHead; }
 74             set { this.tHead = value; }
 75         }
 76         public Linkedlist()
 77         {
 78             this.tHead = null;
 79         }
 80         public Linkedlist(Node<T> node)
 81         {
 82             this.tHead = node;
 83         }
 84 
 85         public T GetElement(int i)
 86         {
 87             throw new NotImplementedException();
 88         }
 89         /// <summary>
 90         /// i最小从1开始
 91         /// </summary>
 92         /// <param name="t"></param>
 93         /// <param name="i"></param>
 94         public void Insert(T t, int i)
 95         {
 96             Node<T> insertNode = new Node<T>(t, null);//实例化添加的node;
 97             if(this.Head==null||i==1)
 98             {
 99                 this.Head = insertNode;
100             }
101             if(i<1|| i>this.GetLength()||(tHead==null&&i==1))
102             {
103                 Console.WriteLine("There are no elements in this linked list!");
104                 return;  
105             }
106             int j = 1;
107             Node<T> node = tHead;
108             Node<T> nodeTmp;
109             while(node !=null &&j <i)
110             {
111                 node = node.Next;
112                 j++;
113             }
114             nodeTmp = node.Next;
115             node.Next = insertNode;
116             insertNode.Next = nodeTmp;//待插入的node插入后,其后继node为原来链表的第i+1个node 
117         }
118         /// <summary>
119         /// 添加元素。选择添加位置
120         /// </summary>
121         /// <param name="t"></param>
122         /// <param name="p"></param>
123         public void Add(T t, AddPosition p)
124         {
125             if (p == AddPosition.Tail)
126             {
127                 Add(t);//尾部添加
128             }
129             else
130             {
131                 Node<T> node = Head;
132                 Node<T> tmp = new Node<T>(t);
133                 if (node == null)
134                 {
135                     Head = node;
136                 }
137                 else
138                 {
139                     tmp.Next = node;
140                     Head = tmp;
141                 }
142             }
143         }
144         /// <summary>
145         /// 添加到尾部
146         /// </summary>
147         /// <param name="t"></param>
148         public void Add(T t)
149         {
150             Node<T> LastNode=new Node<T>(t,null);
151             if(tHead==null)
152             {
153                 tHead = LastNode;
154             }
155             else
156             {
157                 Node<T> node = tHead;
158                 while(node.Next!=null)
159                 {
160                     node = node.Next;
161                 }
162                 node.Next = LastNode;
163             }
164         }
165 
166         public void Delete(int i)
167         {
168             if(i<1||i>GetLength())
169             {
170                 Console.WriteLine("Location Error");
171                 return;
172             }
173             else
174             {
175                 if (i == 1)
176                 {
177                     Node<T> node = tHead;
178                     tHead = node.Next;
179                 }
180                 else
181                 {
182                     Node<T> node = tHead;
183                     int j = 1;
184                     while(j<i)
185                     {
186                         node = node.Next;
187                         j++;
188                     }
189                     node.Next=node.Next.Next;
190                 }
191             }
192         }
193 
194         public int GetLength()
195         {
196             Node<T> node = new Node<T>();
197             int count = 0;
198             node = Head;
199             while (node != null)
200             {
201                 count++;
202                 node = node.Next;
203             }
204             return count;
205         }
206         public T GetElement(int i)
207         { 
208         if(i<1||i>GetLength())
209         {
210             Console.WriteLine("Location error");
211             return default(T);
212         }
213         else
214         {
215             if(i==1)
216             {
217                 return tHead.Data;
218             }
219             else
220             {
221                 Node<T> node = tHead;
222                 int j = 1;
223                 while (j < i)
224                 {
225                     node = node.Next;
226                     j++;
227                 }
228                 return node.Data;
229             }
230         }
231         }
232 
233         public bool IsEmpty()
234         {
235             return tHead == null;
236         }
237 
238         public int LocationElement(T t)
239         {
240             if(tHead==null)
241             {
242                 Console.WriteLine("there is no element in the list");
243                 return -1;
244             }
245             Node<T> node = tHead;
246             int i = 0;
247             while(node!=null)
248             {
249                 i++;
250                 if (node.Data.Equals(t))
251                 {
252                     return i;
253                 }
254                 node = node.Next;
255             }
256             Console.WriteLine("no found");
257             return -1;
258         }
259 
260         /// <summary>
261         /// thead设为null后,则所有后继结点由于失去引用
262         /// </summary>
263         public void Clear()
264         {
265             tHead = null;
266         }
267 
268         public void Reverse()
269         {
270             if(tHead==null)
271             {
272                 Console.WriteLine("There is no element in the list");
273             }
274             else
275             {
276                 Node<T> node = tHead;
277                 if (node.Next == null) { }
278                 else
279                 {
280                     Node<T> node1 = node.Next;
281                     Node<T> node2;
282                     while (node != null)
283                     {
284                         node2 = node.Next.Next;
285                         node.Next = node2;//可以发现node始终未变,始终是原来的那个头节点  
286                         node1.Next = this.tHead;
287                         this.tHead = node1;
288                         node1 = node2;
289                     }
290                 }
291             }
292         }
293     }
View Code