任务
链表的实现任务
实现目标：（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 }
View Code
该内部类支撑整个链表的运作。
（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 }
View Code