任务

链表的实现任务

实现目标：（1）实现一个链表

　　　　　（2）链表可以增，删，改，查；

　　　　　（3）可以输出信息；

实现过程：

（1）创建一个新的类，包含一个内部类作为链表的结点框架；

（2）创建构造函数，分别是一个参数的构造函数与无参数的构造函数；

（3）实现增功能，允许按照下标添加；

（4）实现查询功能，按照下标查询，按照给出元素查询；

（5）实现删除功能，按照下标删除某个元素，按照给出元素删除，删除所有元素；

（7）实现修改功能，按照下标修改，按照给出元素修改；

（8）实现输出函数；

重点：

（1）内部类的构建

 1 /// <summary>
 2         /// 内部类，作为链表的结点使用
 3         /// </summary>
 4         private class Node
 5         {
 6             //定义一个泛型的字段存储数据
 7             public E e;
 8             //定义链表的下一个结点指针
 9             public Node next;
10             /// <summary>
11             /// 可以传入数据和一个结点指针的构造函数
12             /// </summary>
13             /// <param name="e"></param>
14             /// <param name="next"></param>
15             public Node(E e,Node next)
16             {
17                 this.e = e;
18                 this.next = next;
19             }
20             /// <summary>
21             /// 可以创建作为尾部的结点的构造函数
22             /// </summary>
23             /// <param name="e"></param>
24             public Node(E e)
25             {
26                 this.e = e;
27                 this.next = null;
28             }
29             /// <summary>
30             /// 打印该结点则返回该结点的E型数据
31             /// </summary>
32             /// <returns></returns>
33             public override string ToString()
34             {
35                 return e.ToString();
36             }
37         }

该内部类支撑整个链表的运作。

（2）链表中各结点的衔接 细节需要注意

完整代码：

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Threading.Tasks;
  6 
  7 namespace DataStructrue
  8 {
  9     class LinkedList1<E>
 10     {
 11         /// <summary>
 12         /// 内部类，作为链表的结点使用
 13         /// </summary>
 14         private class Node
 15         {
 16             //定义一个泛型的字段存储数据
 17             public E e;
 18             //定义链表的下一个结点指针
 19             public Node next;
 20             /// <summary>
 21             /// 可以传入数据和一个结点指针的构造函数
 22             /// </summary>
 23             /// <param name="e"></param>
 24             /// <param name="next"></param>
 25             public Node(E e,Node next)
 26             {
 27                 this.e = e;
 28                 this.next = next;
 29             }
 30             /// <summary>
 31             /// 可以创建作为尾部的结点的构造函数
 32             /// </summary>
 33             /// <param name="e"></param>
 34             public Node(E e)
 35             {
 36                 this.e = e;
 37                 this.next = null;
 38             }
 39             /// <summary>
 40             /// 打印该结点则返回该结点的E型数据
 41             /// </summary>
 42             /// <returns></returns>
 43             public override string ToString()
 44             {
 45                 return e.ToString();
 46             }
 47         }
 48         //头结点
 49         private Node head;
 50         //结点个数;
 51         private int N;
 52         /// <summary>
 53         /// 无参构造函数
 54         /// </summary>
 55         public LinkedList1()
 56         {
 57             head = null;
 58             N = 0;
 59         }
 60         //链表长度
 61         public int Count { get { return N; } }
 62         //链表是否为空
 63         public bool IsEmpty { get { return N==0; } }
 64         /// <summary>
 65         /// 添加结点
 66         /// </summary>
 67         /// <param name="index"></param>
 68         /// <param name="e"></param>
 69         public void Add(int index,E e)
 70         {
 71             if (index<0 || index>N)
 72             {
 73                 throw new ArgumentException("非法索引");
 74             }
 75             if (index == 0)
 76             {
 77                 ////为什么不直接赋值null而是赋值head;
 78                 //Node node = new(e);
 79                 //node.next = head;
 80                 //head = node;
 81                 ////等价于↓
 82                 head = new(e, head);
 83             }
 84             else
 85             {
 86                 Node pre = head;
 87                 //按照0为起点开始数，并非从1开始数
 88                 for (int i = 0; i < index - 1; i++)
 89                 {
 90                     pre = pre.next;
 91                 }
 92                 //Node node = new(e);
 93                 //node.next = pre.next;
 94                 //pre.next = node;
 95                 ////等价于↓
 96                 pre.next = new(e, pre.next);
 97             }
 98             N++;
 99         }
100         //头部添加结点
101         public void AddFirst(E e)
102         {
103             Add(0, e);
104         }
105         //尾部添加结点
106         public void AddLast(E e)
107         {
108             Add(N,e);
109         }
110         /// <summary>
111         /// 按照下标删除结点
112         /// </summary>
113         /// <param name="index"></param>
114         /// <returns></returns>
115         public E RemoveAt(int index)
116         {
117             if (index < 0 || index >= N)
118             {
119                 throw new ArgumentException("非法索引");
120             }
121             Node pre = head;
122             for (int i = 0; i < index-1; i++)
123             {
124                 pre = pre.next;
125             }
126             Node rm = new(pre.next.e,null);
127             pre.next = pre.next.next;
128             N--;
129             return rm.e;
130         }
131         /// <summary>
132         /// 按照元素删除结点
133         /// </summary>
134         /// <param name="e"></param>
135         public void Remove(E e)
136         {
137             if (head ==null)
138             {
139                 return;
140             }
141             Node cur = head;
142             Node pre = null;
143             while (cur!=null)
144             {
145                 if (cur.e.Equals(e))
146                 {
147                     break;
148                 }
149                 pre = cur;
150                 cur = cur.next;
151             }
152             if (pre==null)
153             {
154                 head = head.next;
155                 N--;
156             }
157             else if(cur!=null)
158             {
159                 pre.next = cur.next;
160                 N--;
161             }
162             ////也可这样实现↓
163             //Node cur = head.next;
164             //Node pre = head;
165             //for (int i = 0; i < N-1; i++)
166             //{
167             //    if (pre.e.Equals(e))
168             //    {
169             //        head = head.next;
170             //        break;
171             //    }
172             //    else if(cur.e.Equals(e))
173             //    {
174             //        pre.next = cur.next;
175             //        break;
176             //    }
177             //    pre = cur;
178             //    cur = cur.next;
179             //}
180         }
181         /// <summary>
182         /// 修改结点数据
183         /// </summary>
184         /// <param name="index"></param>
185         /// <param name="e"></param>
186         public void Set(int index,E e)
187         {
188             if (index < 0 || index >= N)
189             {
190                 throw new ArgumentException("非法索引");
191             }
192             Node cur = head;
193             for (int i = 0; i < index; i++)
194             {
195                 cur = cur.next;
196             }
197             cur.e = e;
198         }
199         /// <summary>
200         /// 获取结点数据
201         /// </summary>
202         /// <param name="index"></param>
203         /// <returns></returns>
204         public E Get(int index)
205         {
206             if (index < 0 || index >= N)
207             {
208                 throw new ArgumentException("非法索引");
209             }
210             Node cur = head;
211             for (int i = 0; i < index; i++)
212             {
213                 cur = cur.next;
214             }
215             return cur.e;
216         }
217         /// <summary>
218         /// 打印输出结点，也可以直接重写ToString方法实现
219         /// </summary>
220         public void Print()
221         {
222             Node pri = head;
223             for (int i = 0; i < N; i++)
224             {
225                 Console.Write(pri+" ");
226                 pri = pri.next;
227             }
228             Console.WriteLine();
229         }
230         /// <summary>
231         /// 重写ToString方法，打印输出链表
232         /// </summary>
233         /// <returns></returns>
234         public override string ToString()
235         {
236             StringBuilder res = new();
237             Node cur = head;
238             while (cur !=null)
239             {
240                 res.Append(cur + "->");
241                 cur = cur.next;
242             }
243             res.Append("Null\n");
244             return res.ToString();
245         }
246     }
247 }