C#實現(xiàn)單鏈表(線性表)完整實例
更新時間：2016年06月29日 14:42:34 作者：叢曉男
這篇文章主要介紹了C#實現(xiàn)單鏈表(線性表)的方法,結(jié)合完整實例形式分析了單鏈表的原理、實現(xiàn)方法與相關(guān)注意事項,需要的朋友可以參考下
本文實例講述了C#實現(xiàn)單鏈表(線性表)的方法。分享給大家供大家參考，具體如下：
順序表由連續(xù)內(nèi)存構(gòu)成，鏈表則不同。順序表的優(yōu)勢在于查找，鏈表的優(yōu)勢在于插入元素等操作。順序表的例子：http://www.dbjr.com.cn/article/87605.htm
要注意的是，單鏈表的Add（）方法最好不要頻繁調(diào)用，尤其是鏈表長度較長的時候，因為每次Add，都會從頭節(jié)點(diǎn)到尾節(jié)點(diǎn)進(jìn)行遍歷，這個缺點(diǎn)的優(yōu)化方法是將節(jié)點(diǎn)添加到頭部，但順序是顛倒的。
所以，在下面的例子中，執(zhí)行Purge（清洗重復(fù)元素）的時候，沒有使用Add（）方法去添加元素，而是定義一個節(jié)點(diǎn)，讓它始終指向目標(biāo)單鏈表的最后一個節(jié)點(diǎn)，這樣就不用每次都從頭到尾遍歷。
此外，鏈表還可以做成循環(huán)鏈表，即最后一個結(jié)點(diǎn)的next屬性等于head，主要操作與單鏈表相似，判斷最后一個結(jié)點(diǎn)，不是等于null，而是等于head
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LinearList
{
//定義線性表的行為，可供順序表類和單鏈表類繼承
public interface IListDS<T>
{
int GetLength();
void Insert(T item, int i);
void Add(T item);
bool IsEmpty();
T GetElement(int i);
void Delete(int i);
void Clear();
int LocateElement(T item);
void Reverse();
}
//鏈表節(jié)點(diǎn)類
class Node<T>
{
private T tData;
private Node<T> nNext;
public T Data
{
get { return this.tData; }
set { this.tData = value; }
}
public Node<T> Next
{
get { return this.nNext; }
set { this.nNext = value; }
}
public Node()
{
this.tData = default(T);
this.nNext = null;
}
public Node(T t)
{
this.tData = t;
this.nNext = null;
}
public Node(T t,Node<T> node)
{
this.tData = t;
this.nNext = node;
}
}
//該枚舉表示單鏈表Add元素的位置，分頭部和尾部兩種
enum AddPosition {Head,Tail};
//單鏈表類
class LinkedList<T>:IListDS<T>
{
private Node<T> tHead;//單鏈表的表頭
public Node<T> Head
{
get { return this.tHead; }
set { this.tHead = value; }
}
public LinkedList()
{
this.tHead = null;
}
public LinkedList(Node<T> node)
{
this.tHead = node;
}
public void Add(T item,AddPosition p)//選擇添加位置
{
if (p == AddPosition.Tail)
{
this.Add(item);//默認(rèn)添加在末尾
}
else//從頭部添加會節(jié)省查找的開銷，時間復(fù)雜度為O(1)不必每次都循環(huán)到尾部，這恰好是順序表的優(yōu)點(diǎn)
{
Node<T> node = this.Head;
Node<T> nodeTmp = new Node<T>(item);
if (node == null)
{
this.Head = nodeTmp;
}
else
{
nodeTmp.Next = node;
this.tHead = nodeTmp;
}
}
}
#region IListDS<T> 成員
public int GetLength()
{
Node<T> node = new Node<T>();
int count = 0;
node = this.tHead;
while (node != null)
{
count++;
node = node.Next;
}
return count;
}
public void Insert(T item, int i)//i最小從1開始
{
Node<T> insertNode = new Node<T>(item, null);//實例化待添加的Node
if (this.tHead == null && i == 1)
{
this.tHead = insertNode;
return;
}
if (i < 1 || i > this.GetLength() || (this.tHead == null && i != 1))
{
Console.WriteLine("There are no elements in this linked list!");
return;
}
int j = 1;
Node<T> node = this.tHead;
Node<T> nodeTmp;
while (node != null && j < i)//循環(huán)結(jié)束時，保證node為第i個node
{
node = node.Next;
j++;
}
nodeTmp = node.Next;//原來的單鏈表的第i+1個node
node.Next = insertNode;//第i個node后的node修改為待插入的node
insertNode.Next = nodeTmp;//待插入的node插入后，其后繼node為原來鏈表的第i+1個node
}
public void Add(T item)//添加至尾部，時間復(fù)雜度為O(n)，如果添加至頭部，則會節(jié)省循環(huán)的開銷
{
Node<T> LastNode = new Node<T>(item, null);//實例化待添加的Node
if (this.tHead == null)
{
this.tHead = LastNode;
}
else
{
Node<T> node = this.tHead;
while (node.Next != null)
{
node = node.Next;
}
node.Next = LastNode;
}
}
public bool IsEmpty()
{
return this.tHead == null;
}
public T GetElement(int i)//設(shè)i最小從1開始
{
if (i < 1 || i > this.GetLength())
{
Console.WriteLine("The location is not right!");
return default(T);
}
else
{
if (i == 1)
{
return this.tHead.Data;
}
else
{
Node<T> node = this.tHead;
int j = 1;
while (j < i)
{
node = node.Next;
j++;
}
return node.Data;
}
}
}
public void Delete(int i)//設(shè)i最小從1開始
{
if (i < 1 || i > this.GetLength())
{
Console.WriteLine("The location is not right!");
}
else
{
if (i == 1)
{
Node<T> node = this.tHead;
this.tHead = node.Next;
}
else
{
Node<T> node = this.tHead;
int j = 1;
while (j < i-1)
{
node = node.Next;
j++;
}
node.Next = node.Next.Next;
}
}
}
public void Clear()
{
this.tHead = null;//講thead設(shè)為null后，則所有后繼結(jié)點(diǎn)由于失去引用，等待GC自動回收
}
public int LocateElement(T item)//返回值最小從1開始
{
if (this.tHead == null)
{
Console.WriteLine("There are no elements in this linked list!");
return -1;
}
Node<T> node = this.tHead;
int i = 0;
while (node != null)
{
i++;
if (node.Data.Equals(item))//如果Data是自定義類型，則其Equals函數(shù)必須override
{
return i;
}
node = node.Next;
}
Console.WriteLine("No found!");
return -1;
}
public void Reverse()
{
if (this.tHead == null)
{
Console.WriteLine("There are no elements in this linked list!");
}
else
{
Node<T> node = this.tHead;
if (node.Next == null)//如果只有頭節(jié)點(diǎn)，則不作任何改動
{
}
else
{
Node<T> node1 = node.Next;
Node<T> node2;
while (node1 != null)
{
node2 = node.Next.Next;
node.Next = node2;//可以發(fā)現(xiàn)node始終未變，始終是原來的那個頭節(jié)點(diǎn)
node1.Next = this.tHead;
this.tHead = node1;
node1 = node2;
}
}
}
}
#endregion
}
class Program
{
static void Main(string[] args)
{
/*測試單鏈表的清空
lList.Clear();
Node<int> n = new Node<int>();
n = lList.Head;
while (n != null)
{
Console.WriteLine(n.Data);
n = n.Next;
}
Console.ReadLine();
*/
/*測試單鏈表返回元素個數(shù)
LinkedList<int> lList = new LinkedList<int>();
lList.Add(3);
Console.WriteLine(lList.GetLength());
Console.ReadLine();
*/
/*測試單鏈表插入
LinkedList<int> lList = new LinkedList<int>();
lList.Insert(0,1);
lList.Add(1);
lList.Add(2);
lList.Add(3);
lList.Add(4);
lList.Insert(99,3);
Node<int> n = new Node<int>();
n = lList.Head;
while (n != null)
{
Console.WriteLine(n.Data);
n = n.Next;
}
Console.ReadLine();
*/
/*測試單鏈表獲取某位置的值
LinkedList<int> lList = new LinkedList<int>();
lList.Add(1);
lList.Add(2);
lList.Add(3);
lList.Add(4);
Console.WriteLine(lList.GetElement(1));
Console.ReadLine();
*/
/*測試單鏈表刪除某位置的值
LinkedList<int> lList = new LinkedList<int>();
lList.Add(1);
lList.Add(2);
lList.Add(3);
lList.Add(4);
Node<int> n = new Node<int>();
n = lList.Head;
while (n != null)
{
Console.WriteLine(n.Data);
n = n.Next;
}
Console.ReadLine();
lList.Delete(2);
Node<int> m = new Node<int>();
m = lList.Head;
while (m != null)
{
Console.WriteLine(m.Data);
m = m.Next;
}
Console.ReadLine();
*/
/*測試單鏈表按值查找元素位置
LinkedList<int> lList = new LinkedList<int>();
lList.Add(1);
lList.Add(2);
lList.Add(3);
lList.Add(4);
Console.WriteLine(lList.LocateElement(3));
Console.ReadLine();
*/
/*測試單鏈表Reverse操作（逆序）
LinkedList<int> lList = new LinkedList<int>();
lList.Add(1);
lList.Add(2);
lList.Add(3);
lList.Add(4);
lList.Add(5);
Node<int> m = new Node<int>();
m = lList.Head;
while (m != null)
{
Console.WriteLine(m.Data);
m = m.Next;
}
Console.ReadLine();
lList.Reverse();
Node<int> n = new Node<int>();
n = lList.Head;
while (n != null)
{
Console.WriteLine(n.Data);
n = n.Next;
}
Console.ReadLine();
*/
/*測試單鏈表從頭部添加元素
LinkedList<int> lList = new LinkedList<int>();
lList.Add(1,AddPosition.Head);
lList.Add(2, AddPosition.Head);
lList.Add(3, AddPosition.Head);
lList.Add(4, AddPosition.Head);
lList.Add(5, AddPosition.Head);
Node<int> m = new Node<int>();
m = lList.Head;
while (m != null)
{
Console.WriteLine(m.Data);
m = m.Next;
}
Console.ReadLine();
*/
/*測試對單鏈表清除重復(fù)元素操作（返回另一鏈表）。這個例子中避免使用Add（）方法，因為每個Add（）都要從頭到尾進(jìn)行遍歷，不適用Add（）方法
就要求對目標(biāo)鏈表的最后一個元素實時保存。另一種避免的方法在于從頭部Add，但這樣的最終結(jié)果為倒序
LinkedList<int> lList = new LinkedList<int>();//原鏈表
LinkedList<int> lList2 = new LinkedList<int>();//保存結(jié)果的鏈表
lList.Add(1);
lList.Add(2);
lList.Add(1);
lList.Add(3);
lList.Add(3);
lList.Add(4);
lList.Add(5);
Node<int> m = new Node<int>();
m = lList.Head;
while (m != null)
{
Console.WriteLine(m.Data);
m = m.Next;
}
Console.ReadLine();
Node<int> node1 = lList.Head;//標(biāo)識原鏈表的當(dāng)前要參與比較大小的元素，即可能放入鏈表2中的元素
Node<int> node2;//標(biāo)識結(jié)果單鏈表的最后一個元素，避免使用Add函數(shù)造成多次遍歷
Node<int> node3;//對node1的后繼進(jìn)行暫時保存，并最終付給node1
node3 = node1.Next;
lList2.Head = node1;//鏈表1的頭結(jié)點(diǎn)肯定要加入鏈表2
node2 = lList2.Head;//node2表示鏈表2的最后一個元素，此時最后一個元素為頭結(jié)點(diǎn)
node2.Next = null;//由于是把node1賦給了鏈表2的頭結(jié)點(diǎn)，必須把它的后續(xù)結(jié)點(diǎn)設(shè)為null，否則會一起帶過來
node1 = node3;//如果沒有node3暫存node1的后繼，對lList2.Head后繼賦為null的就會同時修改node1的后繼，因為兩者指向同一塊內(nèi)存
while (node1 != null)
{
//在iList2中比較大小
Node<int> tmp = lList2.Head;
if (node1.Data.Equals(tmp.Data))
{
node1 = node1.Next;
continue;//若相等，則node1向后移一位，重新計算
}
else
{
Node<int> tmp2 = tmp;
tmp = tmp.Next;//tmp標(biāo)識鏈表2的用于循環(huán)的節(jié)點(diǎn)，與node比較
if (tmp == null)//當(dāng)鏈表2中現(xiàn)有元素與node1都不相等時
{
node3 = node1.Next;
node2.Next = node1;
node2 = node1;
node2.Next = null;
node1 = node3;
continue;
}
while (tmp != null)//tmp不為null時，一直循環(huán)到它為null
{
if (node1.Data.Equals(tmp.Data))
{
node1 = node1.Next;
}
else
{
tmp2 = tmp;
tmp = tmp.Next;
if (tmp == null)
{
node3 = node1.Next;
node2.Next = node1;
node2 = node1;
node2.Next = null;
node1 = node3;
}
}
}
}
}
//輸出清除重復(fù)處理后的數(shù)組
Node<int> n = new Node<int>();
n = lList2.Head;
while (n!= null)
{
Console.WriteLine(n.Data);
n = n.Next;
}
Console.ReadLine();
*/
}
}
}
更多關(guān)于C#相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《C#數(shù)據(jù)結(jié)構(gòu)與算法教程》、《C#遍歷算法與技巧總結(jié)》、《C#程序設(shè)計之線程使用技巧總結(jié)》、《C#操作Excel技巧總結(jié)》、《C#中XML文件操作技巧匯總》、《C#常見控件用法教程》、《WinForm控件用法總結(jié)》、《C#數(shù)組操作技巧總結(jié)》及《C#面向?qū)ο蟪绦蛟O(shè)計入門教程》
希望本文所述對大家C#程序設(shè)計有所幫助。
您可能感興趣的文章:
相關(guān)文章
C#實現(xiàn)Oracle批量寫入數(shù)據(jù)的方法詳解
往數(shù)據(jù)庫批量寫入數(shù)據(jù)，這個功能使用頻率相對還是比較高的，特別是在做一些導(dǎo)入等功能的時候。本文為大家介紹了C#實現(xiàn)Oracle批量寫入數(shù)據(jù)的方法，需要的可以參考一下2022-11-11
這篇文章主要為大家詳細(xì)介紹了Unity Shader實現(xiàn)3D翻頁效果，Plane實現(xiàn)翻頁效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07
這篇文章主要介紹了C#將Json解析成DateTable的方法,涉及相關(guān)格式轉(zhuǎn)換的操作技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-01-01
Unity Shader實現(xiàn)動態(tài)過場切換圖片效果
這篇文章主要為大家詳細(xì)介紹了Unity Shader實現(xiàn)動態(tài)過場切換圖片效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07
C#實現(xiàn)判斷當(dāng)前操作用戶管理角色的方法
這篇文章主要介紹了C#實現(xiàn)判斷當(dāng)前操作用戶管理角色的方法,涉及C#針對系統(tǒng)用戶判斷的相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-08-08
一般大家經(jīng)常會用PPT遙控翻頁筆來遙控幻燈片，本文確為大家介紹了使用C#制作一個遙控幻燈片,感興趣的朋友可以參考下2015-07-07
這篇文章主要為大家詳細(xì)介紹了unity實現(xiàn)鼠標(biāo)拖住3D物體，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-07-07
C#中使用JSON.NET實現(xiàn)JSON、XML相互轉(zhuǎn)換
這篇文章主要介紹了C#中使用JSON.NET實現(xiàn)JSON、XML相互轉(zhuǎn)換的相關(guān)代碼及示例,需要的朋友可以參考下2015-11-11
這篇文章主要介紹了C#判斷一個矩陣是否為對稱矩陣及反稱矩陣的方法,涉及C#矩陣遍歷及檢查等相關(guān)運(yùn)算技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-08-08
Unity實現(xiàn)鼠標(biāo)或者手指點(diǎn)擊模型播放動畫
這篇文章主要為大家詳細(xì)介紹了Unity實現(xiàn)鼠標(biāo)或者手指點(diǎn)擊模型播放動畫，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-01-01