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
}