顺序表是在计算机内存中用一组地址连续的存储单元依次存储数据元素的线性结构。简单，就不做过多说明了。
单向链表是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。在我设计的单向链表类（LinkList类）中，是以LNode类的一个对象来实现链表头。对链表的操作，都将链表头送入LinkList类。因此LinkList类中所有方法都是静态的。而对一个表的传输只需要传递表头就可以了。
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
至于循环单向链表和循环双向链表都是之需要把尾元素指向首元素，在以上2个类实现的基础上再实现也不难。
暂时只写了单向链表类与双向链表节点类，其他的以后有时间慢慢搞了。。。
作者：长沙理工大学 02级 张宇洋
最后修改日期：2006-01-25
1
/* 说明：
2
* 双向链表的实现很简单，只是需要在结构中再加上个 public LNode Prev;
3 * 循环链表把最后一个元素的指向第一个元素就好了。可以重新设计一个循环链表头，记录尾对象
4 * C# 中并不是没指针，不过用了指针其实违背了 C# 的设计初衷，所以程序中并不存在指针
5 * 关于这个结构是什么样子，可以在运行程序后，从局部变量窗口中查看 L 的的变化
6 * 从降低算法的复杂度考虑，才会简写了 NextElem() 函数，要不别的函数能方便的从基函数得到扩展
7
*/
8
9using System;
10
11namespace GyAngle.ZhangYuYang.LinearList
12{
13 //Compare() 是数据元素判定函数
14 public delegate bool CompareLNode(LNode obj1,LNode obj2);
15 //Visit() 是元素依次访问的函数
16 public delegate bool VisitLNode(int i,LNode obj);
17
18
/*============================================================
19 数据存储结构的定义
20
============================================================*/
21
22 //线性表的单链表储存结构以及头结构
23 public sealed class LNode
24 {
25 public object Data; //保存数据
26 public LNode Next; //保存下一元素对象的引用
27
28 public LNode(){}
29
30 public LNode(object obj)
31 {
32 this.Data=obj;
33 }
34
35 public override string ToString()
36 {
37 return this.Data.ToString ();
38 }
39
40 //返回指定对象
41 public LNode this[int i]
42 {
43 get
44 {
45 return LinkList.GetElem(this,i);
46 }
47 }
48 }
49
50
51 //线性表的双向链表储存结构
52 public sealed class DuLNode
53 {
54 public DuLNode Prev; //保存上一元素对象的引用
55 public object Data; //保存数据
56 public DuLNode Next; //保存下一元素对象的引用
57
58 public DuLNode(){}
59
60 public DuLNode(object obj)
61 {
62 this.Data=obj;
63 }
64
65 public override string ToString()
66 {
67 return this.Data.ToString ();
68 }
69 }
70
71
72 /============================================================
73 对应结构的操作
74 ============================================================*/
75
76 //对线性表的单链表的基本操作
77 public sealed class LinkList
78 {
79
80 //构造函数
81 private LinkList(){}
82
83 //构造一个空的线性表，并且返回这个表的表头
84 public static LNode InitList()
85 {
86 return new LNode(0); //链性线性表元素头，并且在 Data 字段中记录下元素数目（这个是个优化）
87 }
88
89
90 //销毁线性表
91 public static void DestroyList(ref LNode L)
92 {
93 L=null;
94 }
95
96
97 //将表设置为空表
98 public static void ClearList(ref LNode L)
99 {
100 L.Data=0;
101 L.Next=null;
102 }
103
104
105 //若 L 表为空表，则返回 True ,或则返回 False
106 public static bool ListEmpty(ref LNode L)
107 {
108 if(0==(int)L.Data)return true;else return false;
109 }
110
111
112 //返回 L 中数据元素个数
113 public static int ListLength(LNode L)
114 {
115 return (int)L.Data;
116 }
117
118
119 //返回链性线性表中的一个指定值
120 public static LNode GetElem(LNode L,int p)
121 {
122 if(p>ListLength(L)||p<0)throw new ArgumentOutOfRangeException("p","指向了不存在的对象。"+"p="+p);
123 LNode obj=L;
124 for(int i=0;i<p;i++)
125 {
126 obj=NextElem(obj);
127 }
128 return obj;
129 }
130
131
132 //返回 L 中第一个与 e 满足关系 func() 的数据元素的位序，若这样的元素不存在，则返回 0
133 public static int LocateElem(LNode L,LNode e,CompareLNode func)
134 {
135 int i=0;
136 LNode obj=L;
137 for(i=0;i<ListLength(L);i++)
138 {
139 obj=NextElem(obj);
140 if(true==func(obj,e))
141 {
142 return i+1;
143 }
144 }
145 return 0;
146 }
147
148 /*============================================================
149 按道理说，这2个函数要求应该更严格些，实现起来并不难，不过这样更简便点，而且够用了
150 NextElem() 函数完整版以给出，不过那样的话 LocateElem() 函数的使用又会不方便
151 ============================================================*/
152 //若元素 cur_e 是 L 的数据元素，且不是第一个，则返回它的前驱，否则返回 null
153 public static LNode PriorElem(LNode L,LNode cur_e)
154 {
155 int i=LocateElem(L,cur_e,new CompareLNode(CompareElement));
156 if(2>i)
157 {
158 return null;
159 }
160 return GetElem(L,i-1);
161 }
162
163
164 /*若元素 cur_e 是 L 的数据元素，且不是最后一个，则返回它的后继，否则返回 null
165 public static LNode NextElem(LNode L,LNode cur_e)
166 {
167 int i=LocateElem(L,cur_e);
168 if(0==i||ListLength(L)==i)
169 {
170 return null;
171 }
172 return cur_e.Next;
173 }*/
174
175
176 /*返回元素 cur_e 的下一个元素，简单版 NextElem 函数。*/
177 public static LNode NextElem(LNode cur_e)
178 {
179 return cur_e.Next;
180 }
181
182
183 //在L中的第 p 个元素处插入新元素 e
184 public static void ListInsert(LNode L,int p,object e)
185 {
186 if(p>ListLength(L)||p<0)throw new ArgumentOutOfRangeException("p","指向了一个不存在的位置。"+"p="+p);
187 LNode NewElement=new LNode(e);
188 LNode obj=GetElem(L,p);
189 NewElement.Next=obj.Next;
190 obj.Next=NewElement;
191 L.Data=(int)L.Data+1;
192 }
193
194
195 //删除 L 的第 p 个元素
196 public static void ListDelete(LNode L,int p)
197 {
198 if(p>ListLength(L)||p<1)throw new ArgumentOutOfRangeException("p","指向了不存在的对象。"+"p="+p);
199 LNode obj=GetElem(L,p-1);
200 obj.Next=(obj.Next).Next;
201 L.Data=(int)L.Data-1;
202 }
203
204
205 //依次对 L 的每一个元素调用函数 func() 。一旦 func() 失败，则操作失败
206 public static bool ListTraverse(LNode L,VisitLNode func)
207 {
208 LNode obj=L;
209 for(int i=0;i<ListLength(L);i++)
210 {
211 obj=obj.Next;
212 if(false==func(i,obj))return false;
213 }
214 return true;
215 }
216
217
218 //类内部默认的用于定位函数的 func()
219 static bool CompareElement(LNode obj1,LNode obj2)
220 {
221 if(obj1.Data.ToString()==obj2.Data.ToString())return true;else return false;
222 }
223
224
225 }
226
227
228
229
230
231
232
233}
/* 说明：
2
* 双向链表的实现很简单，只是需要在结构中再加上个 public LNode Prev;3
* 循环链表把最后一个元素的指向第一个元素就好了。可以重新设计一个循环链表头，记录尾对象4
* C# 中并不是没指针，不过用了指针其实违背了 C# 的设计初衷，所以程序中并不存在指针5
* 关于这个结构是什么样子，可以在运行程序后，从局部变量窗口中查看 L 的的变化6
* 从降低算法的复杂度考虑，才会简写了 NextElem() 函数，要不别的函数能方便的从基函数得到扩展7
*/8
9
using System;10
11
namespace GyAngle.ZhangYuYang.LinearList12
{
13
//Compare() 是数据元素判定函数14
public delegate bool CompareLNode(LNode obj1,LNode obj2);15
//Visit() 是元素依次访问的函数16
public delegate bool VisitLNode(int i,LNode obj);17
18
/*============================================================
19
数据存储结构的定义20
============================================================*/21
22
//线性表的单链表储存结构以及头结构23
public sealed class LNode24
{25
public object Data; //保存数据26
public LNode Next; //保存下一元素对象的引用27
28
public LNode(){}29
30
public LNode(object obj)31
{32
this.Data=obj;33
}34
35
public override string ToString()36
{37
return this.Data.ToString ();38
}39
40
//返回指定对象41
public LNode this[int i]42
{43
get44
{45
return LinkList.GetElem(this,i);46
}47
}48
}49
50
51
//线性表的双向链表储存结构52
public sealed class DuLNode53
{54
public DuLNode Prev; //保存上一元素对象的引用55
public object Data; //保存数据56
public DuLNode Next; //保存下一元素对象的引用57
58
public DuLNode(){}59
60
public DuLNode(object obj)61
{62
this.Data=obj;63
}64
65
public override string ToString()66
{67
return this.Data.ToString ();68
}69
}70
71
72
/============================================================73
对应结构的操作74
============================================================*/75
76
//对线性表的单链表的基本操作77
public sealed class LinkList78
{79
80
//构造函数81
private LinkList(){}82
83
//构造一个空的线性表，并且返回这个表的表头84
public static LNode InitList()85
{86
return new LNode(0); //链性线性表元素头，并且在 Data 字段中记录下元素数目（这个是个优化）87
}88
89
90
//销毁线性表91
public static void DestroyList(ref LNode L)92
{93
L=null;94
}95
96
97
//将表设置为空表98
public static void ClearList(ref LNode L)99
{100
L.Data=0;101
L.Next=null;102
}103
104
105
//若 L 表为空表，则返回 True ,或则返回 False106
public static bool ListEmpty(ref LNode L)107
{108
if(0==(int)L.Data)return true;else return false;109
}110
111
112
//返回 L 中数据元素个数113
public static int ListLength(LNode L)114
{115
return (int)L.Data;116
}117
118
119
//返回链性线性表中的一个指定值120
public static LNode GetElem(LNode L,int p)121
{122
if(p>ListLength(L)||p<0)throw new ArgumentOutOfRangeException("p","指向了不存在的对象。"+"p="+p);123
LNode obj=L;124
for(int i=0;i<p;i++)125
{126
obj=NextElem(obj);127
}128
return obj;129
}130
131
132
//返回 L 中第一个与 e 满足关系 func() 的数据元素的位序，若这样的元素不存在，则返回 0133
public static int LocateElem(LNode L,LNode e,CompareLNode func)134
{135
int i=0;136
LNode obj=L;137
for(i=0;i<ListLength(L);i++)138
{139
obj=NextElem(obj);140
if(true==func(obj,e))141
{142
return i+1;143
}144
}145
return 0;146
}147
148
/*============================================================149
按道理说，这2个函数要求应该更严格些，实现起来并不难，不过这样更简便点，而且够用了150
NextElem() 函数完整版以给出，不过那样的话 LocateElem() 函数的使用又会不方便151
============================================================*/152
//若元素 cur_e 是 L 的数据元素，且不是第一个，则返回它的前驱，否则返回 null153
public static LNode PriorElem(LNode L,LNode cur_e)154
{155
int i=LocateElem(L,cur_e,new CompareLNode(CompareElement));156
if(2>i)157
{158
return null;159
}160
return GetElem(L,i-1);161
}162
163
164
/*若元素 cur_e 是 L 的数据元素，且不是最后一个，则返回它的后继，否则返回 null165
public static LNode NextElem(LNode L,LNode cur_e)166
{167
int i=LocateElem(L,cur_e);168
if(0==i||ListLength(L)==i)169
{170
return null;171
}172
return cur_e.Next;173
}*/174
175
176
/*返回元素 cur_e 的下一个元素，简单版 NextElem 函数。*/177
public static LNode NextElem(LNode cur_e)178
{179
return cur_e.Next;180
}181
182
183
//在L中的第 p 个元素处插入新元素 e184
public static void ListInsert(LNode L,int p,object e)185
{186
if(p>ListLength(L)||p<0)throw new ArgumentOutOfRangeException("p","指向了一个不存在的位置。"+"p="+p);187
LNode NewElement=new LNode(e);188
LNode obj=GetElem(L,p);189
NewElement.Next=obj.Next;190
obj.Next=NewElement;191
L.Data=(int)L.Data+1;192
}193
194
195
//删除 L 的第 p 个元素196
public static void ListDelete(LNode L,int p)197
{198
if(p>ListLength(L)||p<1)throw new ArgumentOutOfRangeException("p","指向了不存在的对象。"+"p="+p);199
LNode obj=GetElem(L,p-1);200
obj.Next=(obj.Next).Next;201
L.Data=(int)L.Data-1;202
}203
204
205
//依次对 L 的每一个元素调用函数 func() 。一旦 func() 失败，则操作失败206
public static bool ListTraverse(LNode L,VisitLNode func)207
{208
LNode obj=L;209
for(int i=0;i<ListLength(L);i++)210
{211
obj=obj.Next;212
if(false==func(i,obj))return false;213
}214
return true;215
}216
217
218
//类内部默认的用于定位函数的 func()219
static bool CompareElement(LNode obj1,LNode obj2)220
{221
if(obj1.Data.ToString()==obj2.Data.ToString())return true;else return false;222
}223
224
225
}226
227
228
229
230
231
232
233
}