C#单链表
一、首先写链表规范接口
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading.Tasks;
6
7 /// <summary>
8 /// 单链表规范
9 /// </summary>
10 /// <typeparam name="T">节点类型</typeparam>
11 public interface IList<T>
12 {
13 /// <summary>
14 /// 求链表长度
15 /// </summary>
16 /// <returns></returns>
17 int GetLength();
18
19 /// <summary>
20 /// 清空链表
21 /// </summary>
22 void Clear();
23
24 /// <summary>
25 /// 判空
26 /// </summary>
27 /// <returns></returns>
28 bool IsEmpty();
29
30 /// <summary>
31 /// 在表索引位置前面插入节点
32 /// </summary>
33 /// <param name="user">节点数据域</param>
34 /// <param name="i">索引</param>
35 void Insert(T user, int i);
36
37 /// <summary>
38 /// 根据索引查询节点
39 /// </summary>
40 /// <param name="i">索引</param>
41 /// <returns></returns>
42 T GetUserByIndex(int i);
43
44 /// <summary>
45 /// 根据节点查询索引
46 /// </summary>
47 /// <param name="value">节点</param>
48 /// <returns></returns>
49 int GetIndexByUser(T user);
50
51
52 ///// <summary>
53 ///// 添加节点
54 ///// </summary>
55 ///// <param name="item">节点数据域</param>
56 //void Append(T name);
57
58 /// <summary>
59 /// 删除索引位置的节点
60 /// </summary>
61 /// <param name="i">索引</param>
62 /// <returns></returns>
63 T Delete(int i);
64 }
二、写节点类
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading.Tasks;
6
7 /// <summary>
8 /// 节点类
9 /// </summary>
10 /// <typeparam name="T"></typeparam>
11 public class Node<T>
12 {
13 /// <summary>
14 /// 数据域
15 /// </summary>
16 private T data;
17
18 /// <summary>
19 /// 引用域
20 /// </summary>
21 private Node<T> next;
22
23 /// <summary>
24 /// 有数据构造器
25 /// </summary>
26 /// <param name="val"></param>
27 public Node(T val)
28 {
29 data = val;
30 }
31
32 /// <summary>
33 /// 无数据构造器
34 /// </summary>
35 public Node()
36 {
37 data = default(T);
38 next = null;
39 }
40
41 /// <summary>
42 /// 数据域属性
43 /// </summary>
44 public T Data
45 {
46 get
47 {
48 return data;
49 }
50 set
51 {
52 data = value;
53 }
54 }
55
56 /// <summary>
57 /// 引用域属性
58 /// </summary>
59 public Node<T> Next
60 {
61 get
62 {
63 return next;
64 }
65 set
66 {
67 next = value;
68 }
69 }
70 }
三、链表规范实现
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading.Tasks;
6
7 /// <summary>
8 /// 单链表规范实现
9 /// </summary>
10 /// <typeparam name="T">节点类型</typeparam>
11 public class LinkList<T> : IList<T>
12 {
13 private static LinkList<T> _instance = null;
14 public static LinkList<T> GetInstance()
15 {
16 if(null == _instance)
17 {
18 _instance = new LinkList<T>();
19 }
20 return _instance;
21 }
22 private Node<T> head;
23 /// <summary>
24 /// 单链表头节点属性
25 /// </summary>
26 public Node<T> Head
27 {
28 get
29 {
30 return head;
31 }
32 set
33 {
34 head = value;
35 }
36 }
37
38 /// <summary>
39 /// 构造器
40 /// </summary>
41 private LinkList()
42 {
43 head = null;
44 }
45
46 /// <summary>
47 /// 求单链表长度
48 /// </summary>
49 /// <returns></returns>
50 public int GetLength()
51 {
52 Node<T> p = head;
53 int len = 0;
54 while (p != null)
55 {
56 p = p.Next;
57 len++;
58 }
59 return len;
60 }
61
62 /// <summary>
63 /// 清空单链表
64 /// </summary>
65 public void Clear()
66 {
67 head = null;
68 }
69
70 /// <summary>
71 /// 判空
72 /// </summary>
73 /// <returns></returns>
74 public bool IsEmpty()
75 {
76 return head == null;
77 }
78
79 /// <summary>
80 /// 在表索引位置前面插入节点
81 /// </summary>
82 /// <param name="user">节点数据域</param>
83 /// <param name="i">索引</param>
84 public void Insert(T user, int i)
85 {
86 Console.WriteLine("插入位置" + i);
87 //if (IsEmpty())
88 //{
89 // Console.WriteLine("链表为空");
90 // Node<T> q = new Node<T>(user);
91 // head = q;
92 // return;
93 //}
94 if(i < 1)
95 {
96 Console.WriteLine("位置错误");
97 }
98 if (i == 1)
99 {
100 Node<T> q = new Node<T>(user);
101 if(head == null)
102 {
103 head = q;
104 }
105 else
106 {
107 q.Next = head;
108 head = q;
109 }
110 return;
111 }
112 Node<T> p = head;
113 Node<T> r = new Node<T>();
114 int j = 1;
115 while ( j < i)
116 {
117 r = p;
118 p = p.Next;
119 j++;
120 }
121 if (j == i)
122 {
123 Node<T> q = new Node<T>(user);
124 Node<T> m = r.Next;
125 r.Next = q;
126 q.Next = m;
127 }
128 }
129
130 /// <summary>
131 /// 根据索引查询节点
132 /// </summary>
133 /// <param name="i">索引</param>
134 /// <returns></returns>
135 public T GetUserByIndex(int i)
136 {
137 if (IsEmpty())
138 {
139 Console.WriteLine("空链表");
140 return default(T);
141 }
142
143 Node<T> p = new Node<T>();
144 p = head;
145 int j = 1;
146 while (p.Next != null && j < i)
147 {
148 p = p.Next;
149 j++;
150 }
151 if (j == i)
152 {
153 return p.Data;
154 }
155 else
156 {
157 Console.WriteLine("空位");
158 }
159 return default(T);
160
161 }
162
163 /// <summary>
164 /// 根据节点查询索引
165 /// </summary>
166 /// <param name="value">索引</param>
167 /// <returns></returns>
168 public int GetIndexByUser(T user)
169 {
170 if (IsEmpty())
171 {
172 Console.WriteLine("链表是空链表！");
173 return -1;
174 }
175 Node<T> p = new Node<T>();
176 p = head;
177 int i = 1;
178 while (((p != null) && (!p.Data.Equals(user))))
179 {
180 p = p.Next;
181 i++;
182 }
183 if (p == null)
184 {
185 Console.WriteLine("不存在这样的节点。");
186 return -1;
187 }
188 else
189 {
190 Console.WriteLine("找到了对应节点");
191 return i;
192 }
193 }
194
195 /// <summary>
196 /// 删除索引位置的节点
197 /// </summary>
198 /// <param name="i">索引</param>
199 /// <returns></returns>
200 public T Delete(int i)
201 {
202 if (IsEmpty() || i < 1)
203 {
204 Console.WriteLine("链表为空或者位置错误");
205 return default(T);
206 }
207 Node<T> q = new Node<T>();
208 if (i == 1)
209 {
210 q = head;
211 head = head.Next;
212 return q.Data;
213 }
214 Node<T> p = head;
215 int j = 1;
216 while (p.Next != null && j < i)
217 {
218 q = p;
219 p = p.Next;
220 j++;
221 }
222 if (j == i)
223 {
224 q.Next = p.Next;
225 return p.Data;
226 }
227 else
228 {
229 Console.WriteLine("位置不正确");
230 return default(T);
231 }
232 }
233
234 ///// <summary>
235 ///// 向表尾添加元素
236 ///// </summary>
237 ///// <param name="data">节点数据域</param>
238 //public void Append(T data)
239 //{
240 // Node<T> q = new Node<T>(data);
241 // Node<T> p = new Node<T>();
242 // if (head == null)
243 // {
244 // head = q;
245 // return;
246 // }
247 // p = head;
248 // while (p.Next != null)
249 // {
250 // p = p.Next;
251 // }
252 // p.Next = q;
253 //}
254
255 ///// <summary>
256 ///// 在单链表第i个位置后面插入一个值为item的节点
257 ///// </summary>
258 ///// <param name="data"></param>
259 ///// <param name="i"></param>
260 //public void InsertPost(T data, int i)
261 //{
262 // if (IsEmpty() || i < 1)
263 // {
264 // Console.WriteLine("链表为空或者位置错误");
265 // return;
266 // }
267 // if (i == 1)
268 // {
269 // Node<T> q = new Node<T>(data);
270 // q.Next = head.Next;
271 // head.Next = q;
272 // return;
273 // }
274 // Node<T> p = head;
275 // Node<T> r = new Node<T>();
276 // int j = 1;
277 // while (p.Next != null && j <= i)
278 // {
279 // r = p;
280 // p = p.Next;
281 // j++;
282 // }
283 // if (j == i + 1)
284 // {
285 // Node<T> q = new Node<T>(data);
286 // Node<T> m = r.Next;
287 // r.Next = q;
288 // q.Next = m;
289 // }
290 // else
291 // {
292 // Console.WriteLine("插入位置过大，error");
293 // }
294 //}
295
296
297
298
299
300 }
到此链表就写完啦,要使用它只需要
/*获取链表单例对象*/
LinkList<T> link = LinkList<T>.GetInstance();
如此就可以获取到链表对象了.
下面来个应用,写个排行榜吧.
一、写个用户实体类
1 /// <summary>
2 /// 用户实体类
3 /// </summary>
4 public class User
5 {
6 public string name;
7 public float time;
8
9 public User(string name, float time)
10 {
11 this.name = name;
12 this.time = time;
13 }
14 }
二、写个排名功能类(这里包含遍历和按序插入)
1 using System;
2 /// <summary>
3 /// 包含遍历与按序插入
4 /// </summary>
5 public static class ShowRank
6 {
7 /// <summary>
8 /// 遍历
9 /// </summary>
10 /// <param name="link">单链表对象</param>
11 public static void Put(LinkList<User> link)
12 {
13 Node<User> n = link.Head;
14 while (n != null)
15 {
16 Console.WriteLine(link.GetIndexByUser(n.Data) + " " + n.Data.name + " " + n.Data.time);
17 n = n.Next;
18 }
19 }
20
21 /// <summary>
22 /// 用户按成绩序插入排行榜(不会重复)
23 /// </summary>
24 /// <param name="link">单链表对象</param>
25 /// <param name="user">用户对象</param>
26 public static void CalculatePosition(LinkList<User> link, User user)
27 {
28 link.Delete(link.GetIndexByUser(user));
29 int i = 1;
30 while (true)
31 {
32
33 if (link.GetUserByIndex(i) == null)
34 {
35 link.Insert(user, i);
36 Console.WriteLine("表长" + link.GetLength() + "\n");
37 break;
38 }
39
40
41 if (user.time <= link.GetUserByIndex(i).time)
42 {
43 link.Insert(user, i);
44 Console.WriteLine("表长" + link.GetLength() + "\n");
45 break;
46 }
47 else
48 {
49 i++;
50 }
51
52 }
53 }
54 }
到此排行功能就写完啦,测试一下.
写个测试类:
1 using System;
2
3 class Test
4 {
5 static void Main(string[] args)
6 {
7 User wanglei = new User("WangLei", 30.57f);
8 User xiaoma = new User("XiaoMa", 30.58f);
9 User liming = new User("LiMing", 31.62f);
10 User chengliang = new User("ChengLiang", 32.67f);
11 User liuxing = new User("LiuXing", 35.31f);
12
13 LinkList<User> link = LinkList<User>.GetInstance();
14
15 ShowRank.CalculatePosition(link, liuxing);
16 ShowRank.CalculatePosition(link, wanglei);
17 ShowRank.CalculatePosition(link, liming);
18 ShowRank.CalculatePosition(link, chengliang);
19 ShowRank.CalculatePosition(link, xiaoma);
20
21 liming.time = 31.0f;
22 ShowRank.CalculatePosition(link, liming);
23
24 ShowRank.Put(link);
25 Console.WriteLine();
26 Console.WriteLine(xiaoma.name + "的Rank是 : " + link.GetIndexByUser(xiaoma));
27 Console.WriteLine(liuxing.name + "的Rank是 : " + link.GetIndexByUser(liuxing));
28 Console.WriteLine(wanglei.name + "的Rank是 : " + link.GetIndexByUser(wanglei));
29 Console.WriteLine(chengliang.name + "的Rank是 : " + link.GetIndexByUser(chengliang));
30 Console.WriteLine(liming.name + "的Rank是 : " + link.GetIndexByUser(liming));
31
32 Console.WriteLine("\n删除了: " + link.Delete(link.GetIndexByUser(xiaoma)).name);
33 Console.WriteLine("删除了: " + link.Delete(link.GetIndexByUser(liuxing)).name);
34 Console.WriteLine("删除了: " + link.Delete(link.GetIndexByUser(wanglei)).name);
35 Console.WriteLine("删除了: " + link.Delete(link.GetIndexByUser(chengliang)).name);
36 // Console.WriteLine("删除了: " + link.Delete(link.GetIndexByUser(liming)).name);
37
38 Console.WriteLine();
39 ShowRank.Put(link);
40
41 Console.WriteLine("表长" + link.GetLength() + "\n");
42
43 Console.ReadKey();
44 }
45 }
结果看看:
是不是很棒呢?嗯?是不是?
版权声明：本文为LeaMeaWarn原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。