using System;
using ZH.DataFrame.AbstractData;
namespace ZH.DataFrame.BasicData.ChainTable
{
Node 單鏈表#region Node 單鏈表
/**//// <summary>
/// 單鏈表
/// </summary>
public class Node
{
public object item;
public Node next;
private Node head;
private int index;
構造函數#region 構造函數
public Node()
{
head=new Node("head");
index=0;
}
public Node(object v)
{
item=v;next=null;
}
/**//// <summary>
/// 可以自定義開始頭節點
/// </summary>
public void headNode()
{
head=new Node("head");
index=0;
}
#endregion
插入#region 插入
/**//// <summary>
/// 從後面插入
/// </summary>
/// <param name="ob">要插入的數據</param>
public void insertNode(object ob)//從後面插入
{
Node x=head;
Node t=new Node(ob);
for(int i=0;i<index;i++)
x=x.next;
t.next=x.next;
x.next=t;
index=index+1;
}
/**//// <summary>
/// 指定插入(插入指定參數的下面)l從0開始插入第一個的前面
/// </summary>
/// <param name="ob">要插入的數據</param>
/// <param name="l">要插入的數據的位置</param>
/// <returns>true為插入成功，反之失敗</returns>
public bool insertNode(object ob,int l)//指定插入(插入指定參數的下面)l從0開始插入第一個的前面
{
if((l>=0)&&(l<=index))
{
Node x=head;
for(int i=0;i<l;i++)
x=x.next;
Node t=new Node(ob);
t.next=x.next;
x.next=t;
index=index+1;
return true;
}
else
{
return false;
}
}
#endregion
刪除#region 刪除
/**//// <summary>
/// 刪除最後一個
/// </summary>
public void delNode()//刪除最後一個
{
Node x=head;
for(int i=0;i<index-1;i++)
x=x.next;
x.next=x.next.next;
index=index-1;
}
/**//// <summary>
/// 指定刪除(l從1開始)
/// </summary>
/// <param name="l">指定刪除位置</param>
/// <returns>true刪除成功，反之失敗</returns>
public bool delNode(int l)//指定刪除l從1開始
{
if((l>0)&&(l<=index))
{
Node x=head;
for(int i=0;i<l-1;i++)
x=x.next;
x.next=x.next.next;
index=index-1;
return true;
}
else
{
return false;
}
}
/**//// <summary>
/// 查找刪除
/// </summary>
/// <param name="ob">輸入要刪除的輸入</param>
/// <returns>true刪除成功，反之失敗</returns>
public bool delNode(object ob)//查找刪除
{
Node x=head;
Node t;
bool b=false;
for(int i=0;i<index;i++)
{
t=x.next;
if(t.item==ob)
{
x.next=x.next.next;
index=index-1;
b=true;
}
x=x.next;
}
return b;
}
#endregion
上下移動#region 上下移動
/**//// <summary>
/// 上移動
/// </summary>
/// <param name="l">指定要移動的位置</param>
public void Upnode(int l)
{
if((l>1)&&(l<=index))
{
object o=this.showNode(l-1);
this.delNode(l-1);
this.insertNode(o,l-1);
}
}
/**//// <summary>
/// 下移動
/// </summary>
/// <param name="l">指定要移動的位置</param>
public void Downnode(int l)
{
if((l>0) && (l<index))
{
object o=this.showNode(l);
this.delNode(l);
this.insertNode(o,l);
}
}
#endregion
排序 和反鏈#region 排序 和反鏈
/**//// <summary>
/// 排序
/// </summary>
/// <param name="b">true（正）從小到大，false（反）</param>
public void compositorNode(bool b)//排序true（正）從小到大，false（反）
{
if(b==true)
{
for(int i=1;i<index;i++)
for(int j=1;j<index-i+1;j++)
if(this.CharNode(j)>this.CharNode(j+1))
this.Downnode(j);
}
else
{
for(int i=1;i<index;i++)
for(int j=1;j<index-i+1;j++)
if(this.CharNode(j)<this.CharNode(j+1))
this.Downnode(j);
}
}
private char CharNode(int l)
{
string s=this.showNode(l).ToString();
char[] c=s.ToCharArray();
return c[0];
}
/**//// <summary>
/// 反鏈
/// </summary>
public void rollbackNode()//反鏈(其實是反鏈head後的)
{
Node t,y,r=null;
y=head.next;
while(y!=null)
{
t=y.next;y.next=r;r=y;y=t;
}
head.next=r;//把head鏈上最後一個
}
#endregion
顯示節點和接點數#region 顯示節點和接點數
/**//// <summary>
/// 返回節點數方法
/// </summary>
/// <returns>節點數</returns>
public int showNodenum()
{
return index;
}
/**//// <summary>
/// 顯示指定數據
/// </summary>
/// <param name="l">指定位置</param>
/// <returns>返回數據</returns>
public object showNode(int l)//顯示指定l從1開始
{
if((l<=index)&&(l>0))
{
Node x=head;
for(int i=0;i<l;i++)
{
x=x.next;
}
return x.item;
}
else
{
return head.item;
}
}
/**//// <summary>
/// 顯示所有
/// </summary>
/// <returns>返回一個ObQueue對象</returns>
public ObQueue showAllNode()//顯示所有
{
ObQueue oq=new ObQueue();
Node x=head;
for(int i=0;i<index;i++)
{
x=x.next;
oq.qput(x.item);
}
return oq;
}
#endregion
}
#endregion
循環鏈表#region 循環鏈表
/**//// <summary>
/// 循環鏈表
/// </summary>
public class CircularList
{
public class Node
{
public object val;
public Node next;
public Node(object v)
{
val=v;
}
}
public Node next(Node x)
{
return x.next;
}
public object val(Node x)
{
return x.val;
}
/**//// <summary>
/// 插入
/// </summary>
/// <param name="x"></param>
/// <param name="v"></param>
/// <returns></returns>
public Node insert(Node x,object v)
{
Node t=new Node(v);
if(x==null)t.next=t;
else{t.next=x.next;x.next=t;}
return t;
}
/**//// <summary>
/// 移除
/// </summary>
/// <param name="x"></param>
public void remove(Node x)
{
x.next=x.next.next;
}
}
#endregion
間接用循環鏈表解決，約瑟芬問題#region 間接用循環鏈表解決，約瑟芬問題
/**//// <summary>
/// 間接用循環鏈表解決，約瑟芬問題
/// </summary>
public class Josephuses
{
public static object GetJosephuses(object[] item,int M)
{
int N=item.Length;
CircularList L=new CircularList();
CircularList.Node x=null;
for(int i=1;i<=N;i++)
{
x=L.insert(x,item[i-1]);
}
while(x!=L.next(x))
{
for(int i=1;i<M;i++)
{
x=L.next(x);
}
L.remove(x);
}
return L.val(x);
}
}
#endregion
循環鏈表列子（約瑟芬問題）#region 循環鏈表列子（約瑟芬問題）
/**//// <summary>
/// 循環鏈表列子（約瑟芬問題）
/// </summary>
public class Josephus
{
public static object GetJosephus(object[] item,int M)
{
object[] o=item;
int N=o.Length;
Node t=new Node(o[0]);
Node x=t;
for(int i=1;i<N;i++)
{
x=(x.next=new Node(o[i]));
}
x.next=t;
while(x!=x.next)
{
for(int i=1;i<M;i++)x=x.next;
x.next=x.next.next;
}
return x.item;
}
}
#endregion
}
