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
}
新闻热点
疑难解答
