程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> 關於C# >> 數據結構(C#):單鏈表

數據結構(C#):單鏈表

編輯:關於C#

與順序表相比,鏈表有自己的特點:插入、刪除操作無需移動元素;能夠高效實現動態內存分配;但 不能按節點索引快速定位到節點;由於需要記錄指針域,系統開銷較大。

本篇介紹單鏈表的實現,使用上一篇定義的接口。

代碼:

/*
* File   :  SingleLinkedList.cs
* Author  :  Zhenxing Zhou
* Date   :  2008-12-06
* Blog   :  http://www.xianfen.net/
*/
using System;
using System.Collections;
using System.Collections.Generic;

namespace Xianfen.Net.DataStructure
{
   // 定義節點
   internal class SingleLinkedListNode<T>
   {
     private T m_Value;
     private SingleLinkedListNode<T> m_Next;

     public T Value
     {
       get { return m_Value; }
       set { m_Value = value; }
     }

     public SingleLinkedListNode<T> Next
     {
       get { return m_Next; }
       set { m_Next = value; }
     }

     public SingleLinkedListNode()
     {
       m_Next = null;
     }

     public SingleLinkedListNode(T t)
       : this()
     {
       Value = t;
     }
   }

   // 實現單鏈表
   public class SingleLinkedList<T> : ILinearList<T>
   {
     private int m_Count;
     private SingleLinkedListNode<T> m_Head;

     public SingleLinkedList()
     {
       m_Count = 0;
       m_Head = new SingleLinkedListNode<T>();
     }

     public SingleLinkedList(T t)
       : this()
     {
       m_Count = 1;
       m_Head.Next = new SingleLinkedListNode<T>(t);
     }

     public bool IsEmpty
     {
       get { return m_Count == 0; }
     }

     public int Count
     {
       get { return m_Count; }
     }

     public void Add(T t)
     {
       InsertAt(t, this.Count);
     }

     public void AddHead(T t)
     {
       InsertAt(t, 0);
     }

     public void AddTail(T t)
     {
       Add(t);
     }

     public void InsertAt(T t, int pos)
     {
       if (pos > this.Count || pos < 0)
       {
         throw new IndexOutOfRangeException("pos");
       }

       if (m_Count == int.MaxValue)
       {
         throw new ArithmeticException();
       }

       SingleLinkedListNode<T> currentNode = m_Head;

       while (pos-- > 0)
       {
         currentNode = currentNode.Next;
       }

       SingleLinkedListNode<T> tempNode = new SingleLinkedListNode<T> (t);

       tempNode.Next = currentNode.Next;
       currentNode.Next = tempNode;
       m_Count++;
     }

     public void RemoveTail()
     {
       RemoveAt(this.Count - 1);
     }

     public void RemoveHead()
     {
       RemoveAt(0);
     }

     public void RemoveAt(int pos)
     {
       if (pos >= Count || pos < 0)
       {
         throw new IndexOutOfRangeException("pos");
       }

       SingleLinkedListNode<T> currentNode = m_Head;

       while (pos-- > 0)
       {
         currentNode = currentNode.Next;
       }

       currentNode.Next = currentNode.Next.Next;
       m_Count--;
     }

     public void RemoveAll()
     {
       m_Head.Next = null;
       m_Count = 0;
     }

     public void Clear()
     {
       RemoveAll();
     }

     public T GetHead()
     {
       return GetAt(0);
     }

     public T GetTail()
     {
       return GetAt(this.Count - 1);
     }

     public T GetAt(int pos)
     {
       return GetNodeAt(pos).Value;
     }

     private SingleLinkedListNode<T> GetNodeAt(int pos)
     {
       if (pos >= Count || pos < 0)
       {
         throw new IndexOutOfRangeException("pos");
       }

       SingleLinkedListNode<T> currentNode = m_Head;

       while (pos-- > 0)
       {
         currentNode = currentNode.Next;
       }

       return currentNode.Next;
     }

     public void SetAt(int pos, T t)
     {
       GetNodeAt(pos).Value = t;
     }

     public int Find(T t)
     {
       SingleLinkedListNode<T> node = m_Head;
       int pos = 0;

       while ((node = node.Next) != null)
       {
         if (node.Value.Equals(t))
         {
           return pos;
         }

         pos++;
       }

       return -1;
     }

     public IEnumerator<T> GetEnumerator()
     {
       SingleLinkedListNode<T> node = m_Head;

       while ((node = node.Next) != null)
       {
         yield return node.Value;
       }
     }

     IEnumerator IEnumerable.GetEnumerator()
     {
       return GetEnumerator();
     }
   }
}

如果發現BUG請留言指出,下一篇介紹雙鏈表的實現。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved