学步园

接口：（同顺序表中的接口）

public interface IListDS<T><br /> {<br /> int GetLength(); //求长度<br /> void Clear(); //清空操作<br /> bool IsEmpty(); //判断线性表是否为空<br /> void Append(T item); //附加操作<br /> void Insert(T item,int i); //插入操作<br /> T Delete(int i); //删除操作<br /> T GetElem(int i); //取表元<br /> int Locate(T value); //按值查找<br /> void Reverse();<br /> }

单链表定义：

//结点<br /> public class Node<T><br /> {<br /> private T data; //数据域<br /> private Node<T> next; //引用域<br /> //构造器<br /> public Node(T val,Node<T> p)<br /> {<br /> data=val;<br /> next=p;<br /> }<br /> //构造器<br /> public Node(T val)<br /> {<br /> data=val;<br /> next=null;<br /> }<br /> //构造器<br /> public Node(Node<T> p)<br /> {<br /> next=p;<br /> }<br /> //构造器<br /> public Node()<br /> {<br /> data=default(T);<br /> next=null;<br /> }<br /> //获取或设置数据域属性<br /> public T Data<br /> {<br /> get<br /> {<br /> return data;<br /> }<br /> set<br /> {<br /> data=value;<br /> }<br /> }<br /> //获取或设置引用域属性<br /> public Node<T> Next<br /> {<br /> get<br /> {<br /> return next;<br /> }<br /> set<br /> {<br /> next=value;<br /> }<br /> }<br /> }<br /> //单链表<br /> public class LinkList<T>:IListDS<T><br /> {<br /> //构造器<br /> public LinkList()<br /> {<br /> head=null;<br /> }<br /> private Node<T> head; //单链表的头引用<br /> //头引用属性<br /> public Node<T> Head<br /> {<br /> get<br /> {<br /> return head;<br /> }<br /> set<br /> {<br /> head=value;<br /> }<br /> }<br /> //求单链表的长度<br /> public int GetLength()<br /> {<br /> Node<T> p=head;<br /> int len=0;<br /> while(p!=null)<br /> {<br /> ++len;<br /> p=p.Next;<br /> }<br /> return len;<br /> }<br /> //清空单链表<br /> public void Clear()<br /> {<br /> head=null;<br /> }<br /> //判断单链表是否为空<br /> public bool IsEmpty()<br /> {<br /> if(head==null)<br /> {<br /> return true;<br /> }<br /> else<br /> {<br /> return false;<br /> }<br /> }</p> <p> //在单链表的末尾添加新元素<br /> public void Append(T item)<br /> {<br /> Node<T> q=new Node<T>(item);<br /> Node<T> p=new Node<T>();</p> <p> if(head==null)<br /> {<br /> head=q;<br /> return;<br /> }<br /> p=head;<br /> //找到最后一个结点的位置<br /> while(p!=null)<br /> {<br /> p=p.Next;<br /> }<br /> p.Next=q;<br /> }<br /> //在单链表的第i个结点的位置 前 出入一个值为item的结点<br /> public void Insert(T item,int i)<br /> {<br /> Node<T> q=new Node<T>(item);<br /> Node<T> p=new Node<T>();<br /> if(IsEmpty()||i<1)<br /> {<br /> Console.WriteLine("LinkList is empty or Position is error");<br /> return;<br /> }<br /> //插入在链表的头节点处<br /> if(i==1)<br /> {<br /> q.Next=head;<br /> head=q;<br /> return;<br /> }<br /> p=head;<br /> int j=1;<br /> Node<T> r=new Node<T>();<br /> while(p.Next!=null&&j<i)<br /> {<br /> r=p;<br /> p=p.Next;<br /> ++j;<br /> }<br /> if(j==i)<br /> {<br /> q.Next=p;<br /> r.Next=q;<br /> }<br /> }<br /> //在单链表的第i个结点的位置 后 插入一个值为item的结点<br /> public void InsertPost(T item,int i)<br /> {<br /> if(IsEmpty()||i<1)<br /> {<br /> Console.WriteLine("LinkList is empty or Position is error");<br /> return;<br /> }<br /> Node<T> q=new Node<T>(item);<br /> Node<T> p=new Node<T>();<br /> int j=1;<br /> p=head;<br /> while(p!=null&&j<i)<br /> {<br /> p=p.Next;<br /> j++;<br /> }<br /> if(j==i)<br /> {<br /> q.Next=p.Next;<br /> p.Next=q;<br /> }<br /> }</p> <p> //删除单链表的第i个结点<br /> public T Delete(int i)<br /> {<br /> if(IsEmpty()||i<1)<br /> {<br /> Console.WriteLine("Link is empty or Position is error.");<br /> return default(T);<br /> }<br /> Node<T> q=new Node<T>();<br /> if(i==1)<br /> {<br /> q=head;<br /> head=head.Next;<br /> return q.Data;<br /> }<br /> Node<T> p=new Node<T>();<br /> p=head;<br /> int j=1;<br /> while(p.Next!=null&&j<i)<br /> {<br /> q=p;<br /> p=p.Next;<br /> j++;<br /> }<br /> if(j==i)<br /> {<br /> q.Next=p.Next;<br /> return p.Data;<br /> }<br /> else<br /> {<br /> Console.WriteLine("The ith node is not exist!");<br /> return default(T);<br /> }<br /> }<br /> //获得单链表的第i个数据元素<br /> public T GetElem(int i)<br /> {<br /> if(IsEmpty())<br /> {<br /> Console.WriteLine("List is empty!");<br /> return default(T);<br /> }<br /> Node<T> p=new Node<T>();<br /> p=head;<br /> int j=1;<br /> while(p.Next!=null&&j<i)<br /> {<br /> p=p.Next;<br /> j++;<br /> }<br /> if(j==i)<br /> {<br /> return p.Data;<br /> }<br /> else<br /> {<br /> Console.WriteLine("The ith mode is not exist!");<br /> return default(T);<br /> }<br /> }<br /> //在单链表中查找值为value的结点<br /> public int Locate(T value)<br /> {<br /> if(IsEmpty())<br /> {<br /> Console.WriteLine("List is empty!");<br /> }<br /> Node<T> p=new Node<T>();<br /> p=head;<br /> int j=1;<br /> while(!p.Data.Equals(value)&&p.Next!=null)<br /> {<br /> p=p.Next;<br /> j++;<br /> }<br /> return j;<br /> }<br /> //单链表倒置<br /> public void Reverse()<br /> {<br /> Node<T> p=head.Next;<br /> Node<T> q=new Node<T>();<br /> head.Next=null;</p> <p> while(p!=null)<br /> {<br /> q=p;<br /> p=p.Next;<br /> q.Next=head.Next;//考虑插入操作<br /> head.Next=q;<br /> }<br /> }<br /> }

应用实例

//在单链表的头部插入结点 建立 单链表<br /> LinkList<int> CreateListHead()<br /> {<br /> //创建一个链表<br /> LinkList<int> L=new LinkList<int>();<br /> int d;<br /> //输入一个数据<br /> d=Int32.Parse(Console.ReadLine());</p> <p> //用-1作为输入数据的结束标志<br /> while(d!=-1)<br /> {<br /> Node<int> p=new Node<int>(d);<br /> p.Next=L.Head;<br /> L.Head=p;<br /> d=Int32.Parse(Console.ReadLine());<br /> }<br /> return L;<br /> }<br /> //在单链表的尾部插入结点 建立 单链表<br /> LinkList<int> CreateListTail()<br /> {<br /> LinkList<int> L=new LinkList<int>();<br /> Node<int> p=new Node<int>();<br /> p=L.Head;<br /> int d=Int32.Parse(Console.ReadLine());<br /> while(d!=-1)<br /> {<br /> Node<int> q=new Node<int>(d);<br /> if(p==null)<br /> {<br /> L.Head=q;<br /> }<br /> else<br /> {<br /> p.Next=q;<br /> }<br /> p=q;<br /> d=Int32.Parse(Console.ReadLine());<br /> }<br /> if(p!=null)<br /> {<br /> p.Next=null;<br /> }<br /> return L;<br /> }<br /> //将两表合并成一表<br /> public LinkList<int> Merge(LinkList<int> Ha,LinkList<int>Hb)<br /> {<br /> LinkList<int> Lc=new LinkList<int>();<br /> Node<int> p=Ha.Next;<br /> Node<int> q=Hb.Next;<br /> Node<int> s=Node<int>();<br /> Lc=Ha;<br /> Lc.Next=null;<br /> while(p!=null&&q!=null)<br /> {<br /> if(p.Data<q.Data)<br /> {<br /> s=p;<br /> p=p.Next;<br /> }<br /> else<br /> {<br /> s=q;<br /> q=q.Next;<br /> }<br /> Lc.Append(s);<br /> }</p> <p> if(p==null)<br /> {<br /> p=q;<br /> }<br /> while(p!=null)<br /> {<br /> s=p;<br /> p=p.Next;<br /> Lc.Append(s);<br /> }<br /> return Lc;</p> <p> }</p> <p> //把结点插入到链表Hc头部合并Ha和Hb的<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span><br /> public LinkList<int> Merge(LinkList<int> Ha,LinkList<int> Hb)<br /> {<br /> LinkList<int> Hc=new LinkList<int>();<br /> Node<int> p=Ha.Next;<br /> Node<int> q=Hb.Next;<br /> Node<int> s=Node<int>();<br /> Hc=Ha;<br /> Hc.Next=null;<br /> while(p!=null&&q!=null)<br /> {<br /> if(p.Data<q.Data)<br /> {<br /> s=p;<br /> p=p.Next;<br /> }<br /> else<br /> {<br /> s=q;<br /> q=q.Next;<br /> }<br /> s.Next=Hc.Next;<br /> Hc.Next=s;<br /> }<br /> if(p==null)<br /> {<br /> p=q;<br /> }<br /> while(p!=null)<br /> {<br /> s=p;<br /> p=p.Next;<br /> s.Next=Hc.Next;<br /> Hc.Next=s;<br /> }<br /> return Hc;<br /> }<br /> //已知一个存储整数的单链表Ha,试构造单链表Hb，要求单链表Hb中只包含<br /> //单链表Ha中所有值不相同的结点<br /> public LinkList<int> Purge(LinkList<int> Ha)<br /> {<br /> LinkList<int> Hb=new LinkList<int>();<br /> Node<int> p=Ha.Next;<br /> Node<int> q=new Node<int>();<br /> Node<int> s=new Node<int>();<br /> //将Ha的第一个元素作为Hb的第一个元素<br /> s=p;<br /> p=p.Next;<br /> s.Next=null;<br /> Hb.Next=s;<br /> while(p!=null)<br /> {<br /> s=p;<br /> p=p.Next;<br /> q=Hb.Next;<br /> while(q!=null&&q.Data!=s.Data)<br /> {<br /> q=q.Next;<br /> }<br /> if(q==null)<br /> {<br /> //插入元素结点<br /> s.Next=Hb.Next;<br /> Hb.Next=s;<br /> }<br /> }<br /> }