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;

        構(gòu)造函數(shù)#region 構(gòu)造函數(shù)
        public node()
        {
            head=new node("head");
            index=0;       
        }
        public node(object v)
        {
            item=v;next=null;
        }
        /**//// <summary>
        /// 可以自定義開(kāi)始頭節(jié)點(diǎn)
        /// </summary>
        public void headnode()
        {
           head=new node("head");
           index=0;
        }
        #endregion

        插入#region 插入
        /**//// <summary>
        /// 從后面插入
        /// </summary>
        /// <param name="ob">要插入的數(shù)據(jù)</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>
        /// 指定插入(插入指定參數(shù)的下面)l從0開(kāi)始插入第一個(gè)的前面
        /// </summary>
        /// <param name="ob">要插入的數(shù)據(jù)</param>
        /// <param name="l">要插入的數(shù)據(jù)的位置</param>
        /// <returns>true為插入成功，反之失敗</returns>
        public bool insertnode(object ob,int l)//指定插入(插入指定參數(shù)的下面)l從0開(kāi)始插入第一個(gè)的前面
        {
            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>
        /// 刪除最后一個(gè)
        /// </summary>
        public void delnode()//刪除最后一個(gè)
        {
            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開(kāi)始)
        /// </summary>
        /// <param name="l">指定刪除位置</param>
        /// <returns>true刪除成功，反之失敗</returns>
        public bool delnode(int l)//指定刪除l從1開(kāi)始
        {
            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">輸入要?jiǎng)h除的輸入</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

        上下移動(dòng)#region 上下移動(dòng)
        /**//// <summary>
        /// 上移動(dòng)
        /// </summary>
        /// <param name="l">指定要移動(dòng)的位置</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>
        /// 下移動(dòng)
        /// </summary>
        /// <param name="l">指定要移動(dòng)的位置</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()//反鏈(其實(shí)是反鏈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鏈上最后一個(gè)

        }
        #endregion

        顯示節(jié)點(diǎn)和接點(diǎn)數(shù)#region 顯示節(jié)點(diǎn)和接點(diǎn)數(shù)
        /**//// <summary>
        /// 返回節(jié)點(diǎn)數(shù)方法
        /// </summary>
        /// <returns>節(jié)點(diǎn)數(shù)</returns>
        public int shownodenum()
        {
            return index;
        }
        /**//// <summary>
        /// 顯示指定數(shù)據(jù)
        /// </summary>
        /// <param name="l">指定位置</param>
        /// <returns>返回?cái)?shù)據(jù)</returns>
        public object shownode(int l)//顯示指定l從1開(kāi)始
        {
            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>返回一個(gè)obqueue對(duì)象</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

    循環(huán)鏈表#region 循環(huán)鏈表
    /**//// <summary>
    /// 循環(huán)鏈表
    /// </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

    間接用循環(huán)鏈表解決，約瑟芬問(wèn)題#region 間接用循環(huán)鏈表解決，約瑟芬問(wèn)題
    /**//// <summary>
    /// 間接用循環(huán)鏈表解決，約瑟芬問(wèn)題
    /// </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

    循環(huán)鏈表列子（約瑟芬問(wèn)題）#region 循環(huán)鏈表列子（約瑟芬問(wèn)題）
    /**//// <summary>
    /// 循環(huán)鏈表列子（約瑟芬問(wèn)題）
    /// </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

}