Posted on 2007-03-29 17:02
dennis 閱讀(2001)
評論(1) 編輯 收藏 所屬分類:
C#歷程 、
數據結構與算法
??? 今天受一個帖子的刺激，再次復習起了數據結構與算法，那本《數據結構與算法（java版）》我還剩圖和高級排序的幾章沒看，工作上也沒我的事需要處理，就用C#重新寫了一遍鏈表結構，權作復習。
定義List接口：
???public??interface?List
????{
????????bool?IsEmpty();
????????void?Unshift(Object?obj);
????????Object?Shift();
????????void?Push(Object?obj);
????????Object?Pop();
????????bool?Contain(Object?obj);
????????void?Delete(Object?obj);
????????void?PrintAll();
????????Object?getHead();
????????Object?getTail();
??????? void Clear();
????}
實現單向鏈表：
?//單向鏈表
????public?class?SList:List
????{
????????private?SNode?head,?tail;
????????public?SList()
????????{
????????????this.head?=?this.tail?=?null;
????????}
????????public?bool?IsEmpty()
????????{
????????????return?head?==?null;
????????}
????????public?void?Unshift(Object?obj)
????????{
????????????head?=?new?SNode(obj,?head);
????????????if?(tail?==?null)
????????????????tail?=?head;
????????}
????????public?Object?Shift()
????????{
????????????if?(head?==?null)
????????????????throw?new?NullReferenceException();
????????????Object?value?=?head.value;
????????????if?(head?==?tail)
????????????????head?=?tail?=?null;
????????????else
????????????????head?=?head.next;
????????????return?value;
????????}
????????public?void?Push(Object?obj)
????????{
????????????if?(!IsEmpty())
????????????{
????????????????tail.next?=?new?SNode(obj);
????????????????tail?=?tail.next;
????????????}
????????????else
????????????????head?=?tail?=?new?SNode(obj);
????????}
????????public?Object?Pop()
????????{
????????????if?(head?==?null)
????????????????throw?new?NullReferenceException();
????????????Object?obj?=?tail.value;
????????????if?(head?==?tail)
????????????????head?=?tail?=?null;
????????????else
????????????{
????????????????//查找前驅節點
????????????????for?(SNode?temp?=?head;?temp.next?!=?null?&&?!temp.next.Equals(tail);?temp?=?temp.next)
????????????????????tail?=?temp;
????????????????tail.next?=?null;
????????????}
????????????return?obj;
????????}
????????public?void?PrintAll()
????????{
????????????string?result?=?"";
????????????for?(SNode?temp?=?head;?temp?!=?null;?temp?=?temp.next)
????????????????result?+=?"?"?+?temp.value.ToString();
????????????Console.WriteLine(result);
????????}
????????public?bool?Contain(Object?obj)
????????{
????????????if?(head?==?null)
????????????????return?false;
????????????else
????????????{
????????????????for?(SNode?temp?=?head;?temp?!=?null;?temp?=?temp.next)
????????????????{
????????????????????if?(temp.value.Equals(obj))
????????????????????????return?true;
????????????????}
????????????}
????????????return?false;
????????}
????????public?void?Delete(Object?obj)
????????{
????????????if?(!IsEmpty())
????????????{
????????????????if?(head?==?tail?&&?head.value.Equals(obj))
????????????????????head?=?tail?=?null;
????????????????else?if?(head.value.Equals(obj))
????????????????????head?=?head.next;
????????????????else
????????????????{
????????????????????//temp_prev為刪除值的前驅節點
????????????????????for?(SNode?temp_prev?=?head,?temp?=?head.next;?temp?!=?null;?temp_prev?=?temp_prev.next,?temp?=?temp.next)
????????????????????{
????????????????????????if?(temp.value.Equals(obj))
????????????????????????{
????????????????????????????temp_prev.next?=?temp.next;??//設置前驅節點的next為下個節點?
????????????????????????????if?(temp?==?tail)
???????????????????????????????tail?=?temp_prev;
????????????????????????????temp?=?null;
????????????????????????????break;
????????????????????????}
????????????????????}
????????????????}
????????????}
????????}
????????public??Object?getHead()
????????{
????????????return?this.head.value;
????????}
????????public?Object?getTail()
????????{
????????????return?this.tail.value;
????????}
? ? ? ? public void Clear()
??????? {
??????????? do
??????????? {
??????????????? Delete(head.value);
??????????? } while (!IsEmpty());
??????? }
????}
????class?SNode
????{
????????public?Object?value;
????????public?SNode?next;
????????public?SNode(Object?value,?SNode?next)
????????{
????????????this.value?=?value;
????????????this.next?=?next;
????????}
????????public?SNode(Object?value)
????????{
????????????this.value?=?value;
????????????this.next?=?null;
????????}
????}
實現雙向鏈表：
?//雙向鏈表
????public?class?LinkedList:List
????{
????????private?LinkedNode?head,?tail;
????????public?LinkedList()
????????{
????????????head?=?tail?=?null;
????????}
????????public?bool?IsEmpty()
????????{
????????????return?head?==?null;
????????}
????????public?void?Unshift(Object?obj)
????????{
????????????if?(IsEmpty())
????????????????head?=?tail?=?new?LinkedNode(obj);
????????????else
????????????{
????????????????head?=?new?LinkedNode(obj,?null,?head);
????????????????head.next.prev?=?head;
????????????}
????????}
????????public?Object?Shift()
????????{
????????????if?(IsEmpty())
????????????????throw?new?NullReferenceException();
????????????Object?obj?=?head.value;
????????????if?(head?==?tail)
????????????????head?=?tail?=?null;
????????????else
????????????{
????????????????head?=?head.next;
????????????????head.prev?=?null;
????????????}
????????????return?obj;
????????}
????????public?void?Push(Object?obj)
????????{
????????????if?(IsEmpty())
????????????????head?=?tail?=?new?LinkedNode(obj);
????????????else
????????????{
????????????????tail?=?new?LinkedNode(obj,?tail,?null);
????????????????tail.prev.next?=?tail;
????????????}
????????}
????????public?Object?Pop()
????????{
????????????if?(IsEmpty())
????????????????throw?new?NullReferenceException();
????????????Object?value?=?tail.value;
????????????if?(head?==?tail)
????????????????head?=?tail?=?null;
????????????else
????????????{
????????????????tail?=?tail.prev;
????????????????tail.next?=?null;
????????????}
????????????return?value;
????????}
????????public?bool?Contain(Object?obj)
????????{
????????????if?(IsEmpty())
????????????????return?false;
????????????else
????????????{
????????????????for?(LinkedNode?temp?=?head;?temp?!=?null;?temp?=?temp.next)
????????????????????if?(temp.value.Equals(obj))
????????????????????????return?true;
????????????}
????????????return?false;
????????}
????????public?void?Delete(Object?obj)
????????{
????????????if?(IsEmpty())
????????????????throw?new?NullReferenceException();
????????????if?(head?==?tail)
????????????????head?=?tail?=?null;
????????????else
????????????{
????????????????for?(LinkedNode?temp?=?head;?temp?!=?null;?temp?=?temp.next)
????????????????{
????????????????????if?(temp.value.Equals(obj))
????????????????????{
????????????????????????if?(temp.value.Equals(obj))
????????????????????????{
????????????????????????????if?(temp?==?tail)
????????????????????????????{
????????????????????????????????tail?=?tail.prev;
????????????????????????????????tail.next?=?null;
????????????????????????????????break;
????????????????????????????}
????????????????????????????else?if?(temp?==?head)
????????????????????????????{
????????????????????????????????head.next.prev?=?null;
????????????????????????????????head?=?head.next;
????????????????????????????}
????????????????????????????else
????????????????????????????????temp.prev.next?=?temp.next;
????????????????????????}
????????????????????}
????????????????}
????????????}
????????}
????????public?void?PrintAll()
????????{
????????????string?result?=?"";
????????????for(LinkedNode?temp=head;temp!=null;temp=temp.next)
????????????????result?+=?"?"?+?temp.value.ToString();
????????????Console.WriteLine(result);
????????}
????????public?Object?getHead()
????????{
????????????return?this.head.value;
????????}
????????public?Object?getTail()
????????{
????????????return?this.tail.value;
????????}
? ? ? ? public void Clear()
??????? {
??????????? do
??????????? {
??????????????? Delete(head.value);
??????????? } while (!IsEmpty());
??????? }
??? }
????class?LinkedNode
????{
????????public?Object?value;
????????public?LinkedNode?prev;
????????public?LinkedNode?next;
????????public?LinkedNode(Object?value,?LinkedNode?prev,?LinkedNode?next)
????????{
????????????this.value?=?value;
????????????this.next?=?next;
????????????this.prev?=?prev;
????????}
????????public?LinkedNode(Object?value)
????????{
????????????this.value?=?value;
????????}
????}