用C#学习数据结构之链表

单链表的定义

　　链表是用一组任意的存储单元来存储线性表中的数据元素（这组存储单元可以是连续的，也可以是不连续的）。那么，怎么表示两个数据元素逻辑上的相邻关系呢？即如何表示数据元素之间的线性关系呢？为此，在存储数据元素时，除了存储数据元素本身的信息外，还要存储与它相邻的数据元素的存储地址信息。这两部分信息组成该数据元素的存储映像(Image)，称为结点(Node)。把存储据元素本身信息的域叫结点的数据域(Data Domain)，把存储与它相邻的数据元素的存储地址信息的域叫结点的引用域(Reference Domain)。因此，线性表通过每个结点的引用域形成了一根“链条”，这就是“链表”名称的由来。
如果结点的引用域只存储该结点直接后继结点的存储地址，则该链表叫单链表(Singly Linked List)。把该引用域叫next。单链表结点的结构如图所示，图中data表示结点的数据域。

单链表的结点结构

单链表结点类的实现

 1 public class Node<T>
 2     {
 3         private T data; //数据域
 4         private Node<T> next; //引用域
 5         //构造器
 6         public Node(T val, Node<T> p)
 7         {
 8             data = val;
 9             next = p;
10         }
11         //构造器
12         public Node(Node<T> p)
13         {
14             next = p;
15         }
16         //构造器
17         public Node(T val)
18         {
19             data = val;
20             next = null;
21         }
22         //构造器
23         public Node()
24         {
25             data = default(T);
26             next = null;
27         }
28 
29         //数据域属性
30         public T Data
31         {
32             get
33             {
34                 return data;
35             }
36             set
37             {
38                 data = value;
39             }
40         }
41         //引用域属性
42         public Node<T> Next
43         {
44             get
45             {
46                 return next;
47             }
48             set
49             {
50                 next = value;
51             }
52         }
53     }

链式存储结构

通常，我们把链表画成用箭头相连接的结点的序列，结点间的箭头表示引用域中存储的地址

单链表类LinkList<T>的实现说明如下所示

  1 public class LinkList<T> : IListDS<T>
  2     {
  3         private Node<T> head; //单链表的头引用
  4         //头引用属性
  5         public Node<T> Head
  6         {
  7             get
  8             {
  9                 return head;
 10             }
 11             set
 12             {
 13                 head = value;
 14             }
 15         }
 16         //构造器
 17         public LinkList()
 18         {
 19             head = null;
 20         }
 21         //求单链表的长度
 22         public int GetLength()
 23         {
 24             Node<T> p = head;
 25             int len = 0;
 26             while (p != null)
 27             {
 28                 ++len;
 29                 p = p.Next;
 30             }
 31             return len;
 32         }
 33 
 34         //清空单链表
 35         public void Clear()
 36         {
 37             head = null;
 38         }
 39         //判断单链表是否为空
 40         public bool IsEmpty()
 41         {
 42             if (head == null)
 43             {
 44                 return true;
 45             }
 46             else
 47             {
 48                 return false;
 49             }
 50         }
 51         //在单链表的末尾添加新元素
 52         public void Append(T item)
 53         {
 54             Node<T> q = new Node<T>(item);
 55             Node<T> p = new Node<T>();
 56             if (head == null)
 57             {
 58                 head = q;
 59                 return;
 60             }
 61             p = head;
 62             while (p.Next != null)
 63             {
 64                 p = p.Next;
 65             }
 66             p.Next = q;
 67         }
 68         //在单链表的第i个结点的位置前插入一个值为item的结点
 69         public void Insert(T item, int i)
 70         {
 71             if (IsEmpty() || i < 1)
 72             {
 73                 Console.WriteLine("List is empty or Position is error!");
 74                 return;
 75             }
 76             if (i == 1)
 77             {
 78                 Node<T> q = new Node<T>(item);
 79                 q.Next = head;
 80                 head = q;
 81                 return;
 82             }
 83             Node<T> p = head;
 84             Node<T> r = new Node<T>();
 85             int j = 1;
 86             while (p.Next != null && j < i)
 87             {
 88                 r = p;
 89                 p = p.Next;
 90                 ++j;
 91             }
 92             if (j == i)
 93             {
 94                 Node<T> q = new Node<T>(item);
 95                 q.Next = p;
 96                 r.Next = q;
 97             }
 98         }
 99         //在单链表的第i个结点的位置后插入一个值为item的结点
100         public void InsertPost(T item, int i)
101         {
102             if (IsEmpty() || i < 1)
103             {
104                 Console.WriteLine("List is empty or Position is error!");
105                 return;
106             }
107             if (i == 1)
108             {
109                 Node<T> q = new Node<T>(item);
110                 q.Next = head.Next;
111                 head.Next = q;
112                 return;
113             }
114             Node<T> p = head;
115             int j = 1;
116             while (p != null && j < i)
117             {
118                 p = p.Next;
119                 ++j;
120             }
121             if (j == i)
122             {
123                 Node<T> q = new Node<T>(item);
124                 q.Next = p.Next;
125                 p.Next = q;
126             }
127         }
128         //删除单链表的第i个结点
129         public T Delete(int i)
130         {
131             if (IsEmpty() || i < 0)
132             {
133                 Console.WriteLine("Link is empty or Position is error!");
134                 return default(T);
135             }
136             Node<T> q = new Node<T>();
137             if (i == 1)
138             {
139                 q = head;
140                 head = head.Next;
141                 return q.Data;
142             }
143             Node<T> p = head;
144             int j = 1;
145             while (p.Next != null && j < i)
146             {
147                 ++j;
148                 q = p;
149                 p = p.Next;
150             }
151             if (j == i)
152             {
153                 q.Next = p.Next;
154                 return p.Data;
155             }
156             else
157             {
158                 Console.WriteLine("The ith node is not exist!");
159                 return default(T);
160             }
161         }
162         //获得单链表的第i个数据元素
163         public T GetElem(int i)
164         {
165             if (IsEmpty())
166             {
167                 Console.WriteLine("List is empty!");
168                 return default(T);
169             }
170             Node<T> p = new Node<T>();
171             p = head;
172             int j = 1;
173             while (p.Next != null && j < i)
174             {
175                 ++j;
176                 p = p.Next;
177             }
178             if (j == i)
179             {
180                 return p.Data;
181             }
182             else
183             {
184                 Console.WriteLine("The ith node is not exist!");
185                 return default(T);
186             }
187         }
188 
189         //在单链表中查找值为value的结点
190         public int Locate(T value)
191         {
192             if (IsEmpty())
193             {
194                 Console.WriteLine("List is Empty!");
195                 return -1;
196             }
197             Node<T> p = new Node<T>();
198             p = head;
199             int i = 1;
200             while (!p.Data.Equals(value) && p.Next != null)
201             {
202                 p = p.Next;
203                 ++i;
204             }
205             return i;
206         }
207     }