注册 登录
编程论坛 → 数据结构与算法

C#数据结构 开一帖

寒风中的细雨 发布于 2012-04-18 17:52， 1550 次点击
此贴用于学习， 本人没有C#经验

所以希望加深数据结构的理解的同时去学习C#   
22 回复
#2
寒风中的细雨2012-04-19 22:08
程序代码：
/*

 * @文件名：Program.cs

 * @描  述：顺序表的基本操作

 */
using System;
public interface IListDS<T>
{
    void Clear();//清空操作
    bool IsEmpty();//判断线性表是否为空
    void Append(T nItem);//附加操作
    void Insert(T nItem, int nPos);//插入操作
    void Delete(int nPos);//删除操作
    T GetElem(int nPos);//取表元
    int Locate(T nValue);//按值查找
    void Print();//打印顺序表
}
public class SeqList<T>:IListDS<T>
{
    private int MAX_SIZE;//顺序表的容量
    private int m_Len;//元素的个数
    private T[] m_Data;//顺序表
    //构造函数
    public SeqList(int nSize)
    {
        m_Data = new T[nSize];
        MAX_SIZE = nSize;
        m_Len = 0;
    }
    //索引器
    public T this[int nIndex]
    {
        get { return m_Data[nIndex]; }
        set { m_Data[nIndex] = value; }
    }
    //容量属性
    public int MaxSize
    {
        get { return MAX_SIZE; }
        set { MAX_SIZE = value; }
    }
    //获取顺序表的长度
    public int GetLen
    {
        get { return m_Len; }
    }
    //清空顺序表
    public void Clear()
    {
        m_Len = 0;
    }
  
    //判断线性表是否为空
    public bool IsEmpty()
    {
        return m_Len == 0;
    }
    //附加操作
    public void Append(T nItem)
    {
        //添加到顺序表的末尾
        m_Data[m_Len++] = nItem;
    }
  
    //在指定的位置上进行插入操作
    public void Insert(T nItem, int nPos)
    {
        if (nPos < 1 || nPos > m_Len)
        {
            Console.WriteLine("\t插入的位置不正确！");
            Console.WriteLine();
        }
        for (int i = m_Len; i >= nPos; --i)
        {
            m_Data[i] = m_Data[i - 1];
        }
        m_Data[nPos - 1] = nItem;
        ++m_Len;
    }
  
    //在指定的位置进行删除操作
    public void Delete(int nPos)
    {
        if (nPos < 1 || nPos > m_Len)
        {
            Console.WriteLine("\t删除的位置不正确！");
            Console.WriteLine();
        }
        for (int i = nPos-1; i < m_Len; ++i)
        {
            m_Data[i] = m_Data[i + 1];
        }
        --m_Len;
    }
    //返回指定顺序表位置的值
    public T GetElem(int nPos)
    {
        if (nPos < 1 || nPos > m_Len)
        {
            Console.WriteLine("\t删除的位置不正确！");
            Console.WriteLine();
        }
        return m_Data[nPos-1];
    }
    //根据值查找元素的第一个位置
    public int Locate(T nValue)
    {
        for (int i = 0; i < m_Len; ++i)
        {
            if (nValue.Equals(m_Data[i]))
            {
                return i+1;
            }
        }
        return 0;
    }
    //输出顺序表的元素
    public void Print()
    {
        for (int i = 0; i < m_Len; ++i)
        {
            Console.Write("{0} ", m_Data[i]);
        }
        Console.WriteLine();
    }
}
public class App
{
    public static void Main()
    {
        SeqList<int> list = new SeqList<int>(10);

        Console.WriteLine("Print list: ");
        list.Print();

        Console.WriteLine("list maxsize is:{0}", list.MaxSize);
        Console.WriteLine();

        Console.WriteLine("Append 1 2 3");
        list.Append(1);
        list.Append(2);
        list.Append(3);
        Console.WriteLine("Print list: ");
        list.Print();
        Console.WriteLine();

        Console.WriteLine("At 1 position Insert 4");
        list.Insert(4, 1);
        Console.WriteLine("Print list: ");
        list.Print();
        Console.WriteLine();

        Console.Write("Get list length:");
        Console.WriteLine("{0} ", list.GetLen);
        Console.WriteLine();

        Console.WriteLine("Find 2's position:");
        Console.WriteLine("{0} ", list.Locate(2));
        Console.WriteLine();

        Console.WriteLine("Delete 2's position:");
        list.Delete(list.Locate(2));
        Console.WriteLine("Print list: ");
        list.Print();
        Console.WriteLine();
    }
}
#3
寒风中的细雨2012-04-19 22:09
回复 2楼 寒风中的细雨
终端交互不会
#4
寒风中的细雨2012-04-24 12:48
程序代码：
/**

 * @文件名：Program.cs

 * @作  者：寒风中的细雨

 * @时  间：2012/4/24/

 * @概  述：实现顺序表L，将其倒置

 */
using System;


//顺序表接口
interface ISeqList<T>
{
    int Append(T nData);//在顺序表的末尾添加
    int Insert(int Pos, T nData);//在指定的位置插入
    bool IsEmpty();//判断顺序表示是否为空
    bool IsFull();//判断顺序表示是否为满
    void Print();//打印表
    SeqList<T> Reverse();//倒置
}

//顺序表类
class SeqList<T> : ISeqList<T>
{
    int m_MAXSIZE;//顺序表的最大容量
    int m_Length;//顺序表中元素的个数
    T []m_Data;//存放数据的容器

    //支持下标操作
    T this[int nIndex]
    {
        get { return m_Data[nIndex]; }
        set { m_Data[nIndex] = value; }
    }

    //构造函数
    public SeqList(int nMAX_SIZE)
    {
        m_MAXSIZE = nMAX_SIZE;
        m_Length = 0;
        m_Data = new T[m_MAXSIZE];
    }

    //输出整个顺序表
    public void Print()
    {
        int i;

        for (i = 0; i < m_Length; ++i)
        {
            Console.Write("{0} ", m_Data[i]);
        }
    }

    //判断顺序表是否为空
    //返回值：空  true
    //        非空  false
    public bool IsEmpty()
    {
        return m_Length == 0;
    }

    //判断顺序表示是否为满
    //返回值：满 true
    //        非满  false
    public bool IsFull()
    {
        return m_Length == m_MAXSIZE;
    }

    //在顺序表的末尾添加元素
    //返回值：成功 0
    //        失败 非零
    public int Append(T nData)
    {
        if (IsFull())
        {
            Console.WriteLine("\t顺序表添加失败，没有足够的空间!");

            return -1;
        }

        m_Data[m_Length++] = nData;

        return 0;
    }

    //在顺序表指定的位置插入元素
    //返回值：成功 0
    //        失败 非零
    public int Insert(int Pos, T nData)
    {
        //判断Pos是否合法
        if (Pos < 1 || Pos > m_Length)
        {
            Console.WriteLine("\t顺序表插入失败，插入的位置不正确!");

            return -1;
        }

        if (IsFull())
        {
            Console.WriteLine("\t顺序表插入失败，没有足够的空间!");

            return -1;
        }

        int i;
        //移动一个单位
        for (i = m_Length; i >= Pos; --i)
        {
            m_Data[i] = m_Data[i - 1];
        }

        m_Data[i] = nData;
        ++m_Length;

        return 0;
    }

    //将顺序表逆置
    public SeqList<T> Reverse()
    {
        SeqList<T> temp = new SeqList<T>(this.m_MAXSIZE);

        int i;

        for (i = 0; i < this.m_Length; ++i)
        {
            if (temp.IsEmpty())
            {
                temp.Append(this.m_Data[i]);
            }
            else
            {
                temp.Insert(1, this.m_Data[i]);
            }
        }

        return temp;
    }

}

class App
{
    public static void Main()
    {
        SeqList<int> lst = new SeqList<int>(10);

        Console.Write("输出 lst 顺序表的初始化元素的状态( ");
        lst.Print();
        Console.WriteLine(").\n");
        for (int i = 1; i <= 10; ++i)
        {
            lst.Append(i);
        }
        Console.Write("输出 lst 顺序表添加10个元素的状态( ");
        lst.Print();
        Console.WriteLine(").\n");

        lst = lst.Reverse();
        Console.Write("输出 lst 顺序表逆置后的元素的状态( ");
        lst.Print();
        Console.WriteLine(").\n");

    }
}
#5
寒风中的细雨2012-04-25 10:30
程序代码：
/**

 * @文件名：Program.cs

 * @作  者：寒风中的细雨

 * @时  间：2012/4/25/

 * @概  述：实现有序顺序表La和Lb，合并成一个有序顺序表Lc

 */
using System;

//顺序表类
class SeqList
{
    private int m_MAXSIZE;//顺序表的最大容量
    private int m_Length;//顺序表中元素的个数
    private int []m_Data;//存放数据的容器

    public int Data
    {
        get { return m_MAXSIZE; }
    }

    //支持下标操作
    int this[int nIndex]
    {
        get { return m_Data[nIndex]; }
        set { m_Data[nIndex] = value; }
    }

    //构造函数
    public SeqList(int nMAX_SIZE)
    {
        m_MAXSIZE = nMAX_SIZE;
        m_Length = 0;
        m_Data = new int[m_MAXSIZE];
    }

    //输出整个顺序表
    public void Print()
    {
        int i;
        for (i = 0; i < m_Length; ++i)
        {
            Console.Write("{0} ", m_Data[i]);
        }
    }

    //判断顺序表是否为空
    //返回值：空  true
    //        非空  false
    public bool IsEmpty()
    {
        return m_Length == 0;
    }

    //判断顺序表示是否为满
    //返回值：满 true
    //        非满  false
    public bool IsFull()
    {
        return m_Length == m_MAXSIZE;
    }

    //在顺序表的末尾添加元素
    //返回值：成功 0
    //        失败 非零
    public int Append(int nData)
    {
        if (IsFull())
        {
            Console.WriteLine("\t顺序表添加失败，没有足够的空间!");
            return -1;
        }
        m_Data[m_Length++] = nData;

        return 0;
    }

    //顺序表与nRight顺序表进行合并
    //bFlag  false  降序
    //       true   升序
    //返回新的顺序表
    public SeqList Merge(SeqList nRight, bool nFlag)
    {
        nRight.Sort(nFlag);
        Sort(nFlag);
        int i, j;

        SeqList Lc = new SeqList(m_Length + nRight.m_Length);
        for (i = 0, j = 0; i < m_Length && j < nRight.m_Length; )
        {
            if (nFlag )
            {//升序
                if (m_Data[i] < nRight[j])
                {
                    Lc.Append(m_Data[i]);
                    ++i;
                }
                else
                {
                    Lc.Append(nRight[j]);
                    ++j;
                }
            }
            else
            {//降序
                if (m_Data[i] < nRight[j])
                {
                    Lc.Append(nRight[j]);
                    ++j;
                }
                else
                {
                    Lc.Append(m_Data[i]);
                    ++i;
                }
            }
        }

        while (i != m_Length)
        {
            Lc.Append(m_Data[i]);
            ++i;
        }

        while (j != nRight.m_Length)
        {
            Lc.Append(nRight[j]);
            ++j;
        }

        return Lc;
    }

    ////排序
    //bFlag  false  降序
    //       true   升序
    //返回排序后的顺序表
    public void Sort(bool bFlag)
    {
        int i, j;
        //冒泡排序
        for (i = 0; i < m_Length; ++i)
        {
            for (j = 0; j < m_Length-i-1; ++j)
            {
                if (m_Data[j+1] < m_Data[j])
                {//升序
                    int nTmp = m_Data[j];
                    m_Data[j] = m_Data[j+1];
                    m_Data[j+1] = nTmp;
                }
            }
        }

        if (bFlag == false)
        {//降序
            for (i = 0, j = m_Length - 1; i != j; ++i, --j)
            {
                m_Data[i] += m_Data[j];
                m_Data[j] = m_Data[i] - m_Data[j];
                m_Data[i] = m_Data[i] - m_Data[j];
            }
        }
    }
}

class App
{
    public static void Main()
    {
        SeqList Lst = new SeqList(7);
        SeqList Tst = new SeqList(5);

        Console.Write("输出 Lst 顺序表的初始化元素的状态( ");
        Lst.Print();
        Console.WriteLine(").");

        Console.Write("输出 Tst 顺序表的初始化元素的状态( ");
        Tst.Print();
        Console.WriteLine(").");

        Console.WriteLine("输入Lst的{0}个元素", Lst.Data);
        for (int i = 1; i <= Lst.Data; ++i)
        {
            int j;
            j = Int32.Parse(Console.ReadLine());
            Lst.Append(j);
        }
        Console.Write("输出 Lst 顺序表的初始化元素的状态( ");
        Lst.Print();
        Console.WriteLine(").");

        Console.WriteLine("输入Tst的{0}个元素", Tst.Data);
        for (int i = 1; i <= Tst.Data; ++i)
        {
            int j;
            j = Int32.Parse(Console.ReadLine());
            Tst.Append(j);
        }
        Console.Write("输出 Tst 顺序表的初始化元素的状态( ");
        Tst.Print();
        Console.WriteLine(").");

        Console.Write("输出 Lst 顺序表升序的元素的状态( ");
        Lst.Sort(true);
        Lst.Print();
        Console.WriteLine(").");

        Console.Write("输出 Tst 顺序表降序的元素的状态( ");
        Tst.Sort(false);
        Tst.Print();
        Console.WriteLine(").");

        Console.Write("输出升序合并 Tst 和 Lst 顺序表( ");
        SeqList Lc = Tst.Merge(Lst, true);
        Lc.Print();
        Console.WriteLine(").");
    }
}
#6
寒风中的细雨2012-04-26 11:31
程序代码：
/**

 * @文件名：Program.cs

 * @作  者：寒风中的细雨

 * @时  间：2012/4/26/

 * @概  述：单链表的基本操作

 */
using System;

class CNode<T>
{
    private T m_Data;//数据域
    private CNode<T> m_Next;//指向后继

    //默认构造函数
    public CNode()
    {
        m_Data = default(T);
        m_Next = null;
    }

    //带参构造函数
    public CNode(T nData, CNode<T> nNext)
    {
        m_Data = nData;
        m_Next = nNext;
    }

    //数据域属性操作
    public T Data
    {
        get { return m_Data; }
        set { m_Data = value; }
    }

    //后继域属性操作
    public CNode<T> Next
    {
        get { return m_Next; }
        set { m_Next = value; }
    }
}

interface IList<T>
{
    int GetLength();//获取链表的长度
    void Clear();//清空链表
    bool IsEmpty();//判断链表是否为空
    void Append(T nData);//在链表的末尾添加元素
    void Insert(int nPos, T nData);//在指定位置插入元素
    void Delete(int nPos);//指定要删除元素的位置
    T GetElem(int nPos);//获取指定位置的值
    int GetIndex(T nData);//查找指定值在链表中的位置
    void Print();//打印链表
}

//单链表类
class LinkList<T>:IList<T>
{
    private CNode<T> m_Head;

    //构造函数
    public LinkList()
    {
        //带上头结点
        m_Head = new CNode<T>();
        Console.WriteLine("\t启动单链表......");
    }

    ////获取链表的长度
    //返回值  链表的长度
    public int GetLength()
    {
        CNode<T> nTmp = m_Head.Next;
        int i = 0;
        while (null != nTmp)
        {
            ++i;
            nTmp = nTmp.Next;
        }

        return i;
    }
  
    //清空链表
    public void Clear()
    {
        m_Head.Next = null;//垃圾回收
    }

    //判断链表是否为空
    //返回值：空-true
    //        非空-false
    public bool IsEmpty()
    {
        return null == m_Head.Next;
    }

    //在链表的末尾添加元素
    public void Append(T nData)
    {
        CNode<T> nTmp = m_Head;

        while (null != nTmp.Next)
        {
            nTmp = nTmp.Next;
        }
        nTmp.Next = new CNode<T>(nData, nTmp.Next);
    }

    //在指定位置插入元素
    public void Insert(int nPos, T nData)
    {
        if (nPos > GetLength() || nPos < 1)
        {
            Console.WriteLine("\t元素插入的位置不正确!");
        }

        CNode<T> nTmp = m_Head;

        while (0 != --nPos)
        {
            nTmp = nTmp.Next;
        }

        nTmp.Next = new CNode<T>(nData, nTmp.Next);
    }

    //指定要删除元素的位置
    public void Delete(int nPos)
    {
        if (nPos > GetLength() || nPos < 1)
        {
            Console.WriteLine("\t指定删除的元素位置不正确!");
            return;
        }

        CNode<T> nTmp = m_Head;

        while (0 != --nPos)
        {
            nTmp = nTmp.Next;
        }

        nTmp.Next = nTmp.Next.Next;
    }

    //获取指定位置的值
    public T GetElem(int nPos)
    {
        if (nPos > GetLength() || nPos < 1)
        {
            Console.WriteLine("\t指定查询元素位置不正确!");
            return default(T);
        }

        CNode<T> nTmp = m_Head.Next;

        while (0 != --nPos)
        {
            nTmp = nTmp.Next;
        }

        return nTmp.Data;
    }

    //查找指定值在链表中的位置
    public int GetIndex(T nData)
    {
        int i = 1;
        CNode<T> nTmp = m_Head.Next;

        while (null != nTmp && !nTmp.Data.Equals(nData))
        {
            ++i;
            nTmp = nTmp.Next;
        }

        if (null == nTmp)
        {//不存在要查找的元素
            return -1;
        }

        return i;
    }

    //打印链表
    public void Print()
    {
        CNode<T> nTmp = m_Head.Next;

        while (null != nTmp)
        {
            Console.Write("{0} ", nTmp.Data);
            nTmp = nTmp.Next;
        }
    }
}

class App
{
    public static void Main()
    {
        int i=0;
        LinkList<int> Lst = new LinkList<int>();

        while (-1 != i)
        {
            choice(ref i);
            run(Lst, i);
        }
    }

    static void run(LinkList<int> Lst, int i)
    {
        switch (i)
        {
            case 1://输出单链表.
                {
                    Console.Write("输出单链表的元素( ");
                    Lst.Print();
                    Console.WriteLine(").");
                }
                break;
            case 2://链表末尾添加元素.
                {
                    Console.Write("输入添加的元素值：");
                    int j = int.Parse(Console.ReadLine());
                    Lst.Append(j);
                }
                break;
            case 3://指定位置插入元素.
                {
                    Console.Write("输入添加的元素位置：");
                    int j = int.Parse(Console.ReadLine());
                    Console.Write("输入添加的元素值：");
                    int k = int.Parse(Console.ReadLine());
                    Lst.Insert(j, k);
                }
                break;
            case 4://指定位置删除元素.
                {
                    Console.Write("输入删除元素的位置：");
                    int j = int.Parse(Console.ReadLine());
                    Lst.Delete(j);
                }
                break;
            case 5://指定值查询元素下标.
                {
                    Console.Write("输入查询下标元素的值：");
                    int j = int.Parse(Console.ReadLine());
                    Console.WriteLine("下标为{0}", Lst.GetIndex(j));
                }
                break;
            case 6://指定位置查询元素值.
                {
                    Console.Write("输入查询值元素的下标：");
                    int j = int.Parse(Console.ReadLine());
                    Console.WriteLine("元素的值为{0}", Lst.GetElem(j));
                }
                break;
            case 7://清空链表.
                {
                    Console.WriteLine("清空链表");
                    Lst.Clear();
                }
                break;
            default:
                break;
        }
    }

    static void choice(ref int i)
    {
        Console.WriteLine("\n\t根据下面提示信息选择操作.");
        Console.WriteLine("\"1\"：输出单链表.");
        Console.WriteLine("\"2\"：链表末尾添加元素.");
        Console.WriteLine("\"3\"：指定位置插入元素.");
        Console.WriteLine("\"4\"：指定位置删除元素.");
        Console.WriteLine("\"5\"：指定值查询元素下标.");
        Console.WriteLine("\"6\"：指定位置查询元素值.");
        Console.WriteLine("\"7\"：清空链表.");
        Console.WriteLine("\"-1\"：退出链表操作.");

        i = Int16.Parse(Console.ReadLine());
    }
}
#7
寒风中的细雨2012-04-27 07:51
程序代码：
/**

 * @文件名：Program.cs

 * @作  者：寒风中的细雨

 * @时  间：2012/4/27/

 * @概  述：带头结点的单链表的逆置

 */
using System;

class CNode<T>
{
    private T m_Data;//数据域
    private CNode<T> m_Next;//指向后继

    //默认构造函数
    public CNode()
    {
        m_Data = default(T);
        m_Next = null;
    }

    //带参构造函数
    public CNode(T nData, CNode<T> nNext)
    {
        m_Data = nData;
        m_Next = nNext;
    }

    //数据域属性操作
    public T Data
    {
        get { return m_Data; }
        set { m_Data = value; }
    }

    //后继域属性操作
    public CNode<T> Next
    {
        get { return m_Next; }
        set { m_Next = value; }
    }
}

interface IList<T>
{
    int GetLength();//获取链表结点个数
    void Append(T nData);//在链表的末尾添加元素
    void Insert(int nPos, T nData);//在指定位置插入元素
    void Print();//打印链表
    LinkList<T> Reverse();//逆置
}

//单链表类
class LinkList<T>:IList<T>
{
    private CNode<T> m_Head;

    //构造函数
    public LinkList()
    {
        //带上头结点
        m_Head = new CNode<T>();
    }

    ////获取链表的长度
    //返回值  链表的长度
    public int GetLength()
    {
        CNode<T> nTmp = m_Head.Next;
        int i = 0;

        while (null != nTmp)
        {
            ++i;
            nTmp = nTmp.Next;
        }
        return i;
    }

    //在链表的末尾添加元素
    public void Append(T nData)
    {
        CNode<T> nTmp = m_Head;

        while (null != nTmp.Next)
        {
            nTmp = nTmp.Next;
        }
        nTmp.Next = new CNode<T>(nData, nTmp.Next);
    }

    //在指定位置插入元素
    public void Insert(int nPos, T nData)
    {
        if (nPos > GetLength() || nPos < 1)
        {
            Console.WriteLine("\t元素插入的位置不正确!");
        }

        CNode<T> nTmp = m_Head;

        while (0 != --nPos)
        {
            nTmp = nTmp.Next;
        }
        nTmp.Next = new CNode<T>(nData, nTmp.Next);
    }

    //打印链表
    public void Print()
    {
        CNode<T> nTmp = m_Head.Next;

        while (null != nTmp)
        {
            Console.Write("{0} ", nTmp.Data);
            nTmp = nTmp.Next;
        }
    }

    //逆置
    //返回逆置后的链表
    public LinkList<T> Reverse()
    {
        LinkList<T> Lc = new LinkList<T>();
        CNode<T> nTmp = m_Head.Next;

        while (null != nTmp)
        {
            if (Lc.GetLength() == 0)
            {
                Lc.Append(nTmp.Data);
            }
            else
            {
                Lc.Insert(1, nTmp.Data);
            }
            nTmp = nTmp.Next;
        }

        return Lc;
    }
}

class App
{
    public static void Main()
    {
        LinkList<int> Lst = new LinkList<int>();
        int i;

        do
        {
            Console.Write("输入你要输入的元素个数:");
            i = int.Parse(Console.ReadLine());
        }
        while (i <= 0);

        while (0 != i--)
        {
            int j = int.Parse(Console.ReadLine());
            Lst.Append(j);
        }
        Console.Write("输出单链表 Lst 中的所有元素( ");
        Lst.Print();
        Console.WriteLine(").");

        //逆置
        Lst = Lst.Reverse();
        Console.Write("输出逆置后单链表 Lst 中的所有元素( ");
        Lst.Print();
        Console.WriteLine(").");
    }
}
#8
寒风中的细雨2012-04-30 10:03
程序代码：
/**

 * @文件名：Program.cs

 * @作  者：寒风中的细雨

 * @时  间：2012/4/28/

 * @概  述：单链表a和b,数据按升序排列，将量表合并

 */
using System;

class CNode<T>
{
    private T m_Data;//数据域
    private CNode<T> m_Next;//指向后继

    //默认构造函数
    public CNode()
    {
        m_Data = default(T);
        m_Next = null;
    }

    //带参构造函数
    public CNode(T nData, CNode<T> nNext)
    {
        m_Data = nData;
        m_Next = nNext;
    }

    //数据域属性操作
    public T Data
    {
        get { return m_Data; }
        set { m_Data = value; }
    }

    //后继域属性操作
    public CNode<T> Next
    {
        get { return m_Next; }
        set { m_Next = value; }
    }
}

interface IList<T>
{
    int GetLength();//获取链表结点个数
    void Append(T nData);//在链表的末尾添加元素
    void Insert(int nPos, T nData);//在指定位置插入元素
    void Print();//打印链表
    LinkList<T> Reverse();//逆置
}

//单链表类
class LinkList<T>:IList<T>
{
    private CNode<T> m_Head;

    //获取头结点
    public CNode<T> Head
    {
        get { return m_Head; }
        set { m_Head = value; }
    }
    //构造函数
    public LinkList()
    {
        //带上头结点
        m_Head = new CNode<T>();
    }
    ////获取链表的长度
    //返回值  链表的长度
    public int GetLength()
    {
        CNode<T> nTmp = m_Head.Next;
        int i = 0;
        while (null != nTmp)
        {
            ++i;
            nTmp = nTmp.Next;
        }
        return i;
    }
    //在链表的末尾添加元素
    public void Append(T nData)
    {
        CNode<T> nTmp = m_Head;
        while (null != nTmp.Next)
        {
            nTmp = nTmp.Next;
        }
        nTmp.Next = new CNode<T>(nData, nTmp.Next);
    }
    //在指定位置插入元素
    public void Insert(int nPos, T nData)
    {
        if (nPos > GetLength() || nPos < 1)
        {
            Console.WriteLine("\t元素插入的位置不正确!");
        }
        CNode<T> nTmp = m_Head;
        while (0 != --nPos)
        {
            nTmp = nTmp.Next;
        }
        nTmp.Next = new CNode<T>(nData, nTmp.Next);
    }
    //打印链表
    public void Print()
    {
        CNode<T> nTmp = m_Head.Next;
        while (null != nTmp)
        {
            Console.Write("{0} ", nTmp.Data);
            nTmp = nTmp.Next;
        }
    }
    //逆置
    //返回逆置后的链表
    public LinkList<T> Reverse()
    {
        LinkList<T> Lc = new LinkList<T>();
        CNode<T> nTmp = m_Head.Next;
        while (null != nTmp)
        {
            if (Lc.GetLength() == 0)
            {
                Lc.Append(nTmp.Data);
            }
            else
            {
                Lc.Insert(1, nTmp.Data);
            }
            nTmp = nTmp.Next;
        }
        return Lc;
    }
}

class App
{
    public static void Main()
    {
        LinkList<int> aLst = new LinkList<int>();
        LinkList<int> bLst = new LinkList<int>();
        int i;

        do
        {
            Console.Write("输入你要输入的aLst元素个数:");
            i = int.Parse(Console.ReadLine());
        }
        while (i <= 0);
        while (0 != i--)
        {
            int j = int.Parse(Console.ReadLine());
            aLst.Append(j);
        }
        Console.Write("输出单链表 aLst 中的所有元素( ");
        aLst.Print();
        Console.WriteLine(").");

        do
        {
            Console.Write("输入你要输入的bLst元素个数:");
            i = int.Parse(Console.ReadLine());
        }
        while (i <= 0);
        while (0 != i--)
        {
            int j = int.Parse(Console.ReadLine());
            bLst.Append(j);
        }
        Console.Write("输出单链表 bLst 中的所有元素( ");
        bLst.Print();
        Console.WriteLine(").");

        LinkList<int> cLst = Merge(aLst, bLst, true);
      
        Console.Write("输出升序合并后单链表 cLst 中的所有元素( ");
        cLst.Print();
        Console.WriteLine(").");
    }
    //排序
    // nFlag true 升序
    //       fase 降序
    static void Sort(LinkList<int> nList, bool nFlag)
    {
        int Length = nList.GetLength();
        if (Length <= 0)
        {
            return;
        }
        //冒泡升序
        while (0 != --Length)
        {
            CNode<int> node = nList.Head;
            int i = Length;
            while (null!=node && 0!=i--)
            {
                if (node.Next.Data > node.Next.Next.Data)
                {
                    CNode<int> tmp = node.Next.Next;
                    node.Next.Next = tmp.Next;
                    tmp.Next = node.Next;
                    node.Next = tmp;
                }
                node = node.Next;
            }
        }
        if (false == nFlag)
        {
            nList = nList.Reverse();
        }
    }
    //合并aList 和 bList 表
    static LinkList<int> Merge(LinkList<int> aList, LinkList<int> bList, bool nFlag)
    {
        Sort(aList, nFlag);
        Sort(bList, nFlag);
        CNode<int> Ta = aList.Head.Next;
        CNode<int> Tb = bList.Head.Next;
        LinkList<int> cList = new LinkList<int>();
        while (null != Ta && null != Tb)
        {
            if (Ta.Data > Tb.Data)
            {
                cList.Append(Tb.Data);
                Tb = Tb.Next;
            }
            else
            {
                cList.Append(Ta.Data);
                Ta = Ta.Next;
            }
        }
        while (null != Ta)
        {
            cList.Append(Ta.Data);
            Ta = Ta.Next;
        }
        while (null != Tb)
        {
            cList.Append(Tb.Data);
            Tb = Tb.Next;
        }
        return cList;
    }
}

输入你要输入的aLst元素个数:5
12
3
6
90
10
输出单链表 aLst 中的所有元素( 12 3 6 90 10 ).
输入你要输入的bLst元素个数:3
34
9
23
输出单链表 bLst 中的所有元素( 34 9 23 ).
输出升序合并后单链表 cLst 中的所有元素( 3 6 9 10 12 23 34 90 ).
请按任意键继续. . .
#9
寒风中的细雨2012-05-04 09:58
程序代码：
/**

 * @文件名：Program.cs

 * @作  者：寒风中的细雨

 * @时  间：2012/4/29/

 * @概  述：单循环链表实现约瑟夫环

 */
using System;

class CNode<T>
{
    private T m_Data;//数据域
    private CNode<T> m_Next;//指向后继

    //默认构造函数
    public CNode()
    {
        m_Data = default(T);
        m_Next = null;
    }

    //带参构造函数
    public CNode(T nData, CNode<T> nNext)
    {
        m_Data = nData;
        m_Next = nNext;
    }

    //数据域属性操作
    public T Data
    {
        get { return m_Data; }
        set { m_Data = value; }
    }

    //后继域属性操作
    public CNode<T> Next
    {
        get { return m_Next; }
        set { m_Next = value; }
    }
}

interface IList<T>
{
    int GetLength();//获取链表结点个数
    void Append(T nData);//在链表的末尾添加元素
    void Print();//打印链表
    void Delete(int Pos);//删除
}

//单链表类
class CLinkList<T>:IList<T>
{
    private CNode<T> m_Head;

    //获取头结点
    public CNode<T> Head
    {
        get { return m_Head; }
        set { m_Head = value; }
    }

    //构造函数
    public CLinkList()
    {
        //不带头结点
        m_Head = null;
    }

    ////获取链表的长度
    //返回值  链表的长度
    public int GetLength()
    {
        if (null == m_Head)
        {
            return 0;
        }
        CNode<T> nTmp = m_Head.Next;
        int i = 1;
        while (nTmp != m_Head)
        {
            ++i;
            nTmp = nTmp.Next;
        }
        return i;
    }

    //在链表的末尾添加元素
    public void Append(T nData)
    {
        int nLen = GetLength();
        if (0 == nLen)
        {
            m_Head = new CNode<T>(nData, null);
            m_Head.Next = m_Head;
            return;
        }
        CNode<T> nTmp = m_Head;
        while (0 != --nLen)
        {
            nTmp = nTmp.Next;
        }
        nTmp.Next = new CNode<T>(nData, nTmp.Next);
    }

    //打印链表
    public void Print()
    {
        int nLen = GetLength();
        if (0 == nLen)
        {
            return;
        }
        CNode<T> nTmp = m_Head;
        Console.Write("{0} ", nTmp.Data);
        nTmp = nTmp.Next;
        while (nTmp != m_Head)
        {
            Console.Write("{0} ", nTmp.Data);
            nTmp = nTmp.Next;
        }
    }
    //删除指定位置
    public void Delete(int Pos)
    {
        int i = GetLength();
        if (i == 1)
        {//长度只有1
            Console.Write("{0} ", m_Head.Data);
            m_Head = null;
            return;
        }
      
        //长度大于1
        if (1 == Pos)
        {
            Console.Write("{0} ", m_Head.Data);
            CNode<T> nTmp = m_Head;
            while (m_Head != nTmp.Next)
            {
                nTmp = nTmp.Next;
            }
            nTmp.Next = m_Head = m_Head.Next;
        }
        else
        {
            CNode<T> nTmp = m_Head;
            --Pos;
            while (0 != --Pos)
            {
                nTmp = nTmp.Next;
            }
            Console.Write("{0} ", nTmp.Next.Data);
            nTmp.Next = nTmp.Next.Next;
        }
    }
}

class App
{
    public static void Main()
    {
        CLinkList<int> CList = new CLinkList<int>();
        Console.Write("输入元素个数：");
        int i = int.Parse(Console.ReadLine());
        for (int j = 1; j <= i; ++j)
        {
            CList.Append(j);
        }
        Console.Write("输出 CList 中的元素( ");
        CList.Print();
        Console.WriteLine(").");
        Console.Write("起始位置：");
        int nStart = int.Parse(Console.ReadLine());
        Console.Write("间隔：");
        int nOffset = int.Parse(Console.ReadLine());

        while (0 != CList.GetLength())
        {
            nStart = (nStart-1) % CList.GetLength() + 1;
            CList.Delete(nStart);
            nStart += nOffset;
        }
        Console.WriteLine();
    }
}

输入元素个数：10
输出 CList 中的元素( 1 2 3 4 5 6 7 8 9 10 ).
起始位置：1
间隔：2
1 4 7 10 5 9 6 3 8 2
请按任意键继续. . .
#10
寒风中的细雨2012-05-04 10:46
程序代码：
/**

 * @文件名：Program.cs

 * @作  者：寒风中的细雨

 * @时  间：2012/4/30/

 * @概  述：双循环链表实现约瑟夫环

 */
using System;

class CNode<T>
{
    private T m_Data;//数据域
    private CNode<T> m_Next;//指向后继
    private CNode<T> m_Prev;//指向前驱

    //默认构造函数
    public CNode()
    {
        m_Data = default(T);
        m_Prev = m_Next = null;
    }

    //带参构造函数
    public CNode(T nData, CNode<T> nNext, CNode<T> nPrev)
    {
        m_Data = nData;
        m_Next = nNext;//后继赋值给后继
        m_Prev = nPrev;//前驱赋值给前驱
    }

    //数据域属性操作
    public T Data
    {
        get { return m_Data; }
        set { m_Data = value; }
    }

    //后继域属性操作
    public CNode<T> Next
    {
        get { return m_Next; }
        set { m_Next = value; }
    }

    //前驱域属性操作
    public CNode<T> Prev
    {
        get { return m_Prev; }
        set { m_Prev = value; }
    }
}

interface IList<T>
{
    int GetLength();//获取链表结点个数
    void Append(T nData);//在链表的末尾添加元素
    void Print();//打印链表
    void Delete(int Pos);//删除
}

//单链表类
class CLinkList<T>:IList<T>
{
    private CNode<T> m_Head;

    //获取头结点
    public CNode<T> Head
    {
        get { return m_Head; }
        set { m_Head = value; }
    }

    //构造函数
    public CLinkList()
    {
        //不带头结点
        m_Head = null;
    }

    ////获取链表的长度
    //返回值  链表的长度
    public int GetLength()
    {
        if (null == m_Head)
        {
            return 0;
        }
        CNode<T> nTmp = m_Head.Next;
        int i = 1;
        while (nTmp != m_Head)
        {
            ++i;
            nTmp = nTmp.Next;
        }
        return i;
    }

    //在链表的末尾添加元素
    public void Append(T nData)
    {
        int nLen = GetLength();
        if (0 == nLen)
        {
            m_Head = new CNode<T>(nData, null, null);
            m_Head.Prev = m_Head.Next = m_Head;
            return;
        }
        CNode<T> nPrev = m_Head.Prev;
        nPrev.Next = m_Head.Prev = new CNode<T>(nData, m_Head, nPrev);
    }

    //打印链表
    public void Print()
    {
        int nLen = GetLength();
        if (0 == nLen)
        {
            return;
        }
        CNode<T> nTmp = m_Head;
        Console.Write("{0} ", nTmp.Data);
        nTmp = nTmp.Next;
        while (nTmp != m_Head)
        {
            Console.Write("{0} ", nTmp.Data);
            nTmp = nTmp.Next;
        }
    }

    //删除指定位置
    public void Delete(int Pos)
    {
        int i = GetLength();
        if (i == 1)
        {//长度只有1
            Console.Write("{0} ", m_Head.Data);
            m_Head = null;
            return;
        }
        CNode<T> nPrev;
        CNode<T> nNext;
        //长度大于1
        if (1 == Pos)
        {
            Console.Write("{0} ", m_Head.Data);
            nPrev = m_Head.Prev;
            nNext = m_Head.Next;
            m_Head = nNext;
        }
        else
        {
            CNode<T> nTmp = m_Head;
            while (0 != --Pos)
            {
                nTmp = nTmp.Next;
            }
            Console.Write("{0} ", nTmp.Data);
            nPrev = nTmp.Prev;
            nNext = nTmp.Next;
        }
        nPrev.Next = nNext;
        nNext.Prev = nPrev;
    }
}

class App
{
    public static void Main()
    {
        CLinkList<int> CList = new CLinkList<int>();
        Console.Write("输入元素个数：");
        int i = int.Parse(Console.ReadLine());
        for (int j = 1; j <= i; ++j)
        {
            CList.Append(j);
        }
        Console.Write("输出 CList 中的元素( ");
        CList.Print();
        Console.WriteLine(").");

        Console.Write("起始位置：");
        int nStart = int.Parse(Console.ReadLine());
        Console.Write("间隔：");
        int nOffset = int.Parse(Console.ReadLine());

        while (0 != CList.GetLength())
        {
            nStart = (nStart-1) % CList.GetLength() + 1;
            CList.Delete(nStart);
            nStart += nOffset;
        }
        Console.WriteLine();
    }
}

输入元素个数：10
输出 CList 中的元素( 1 2 3 4 5 6 7 8 9 10 ).
起始位置：3
间隔：3
3 7 1 6 2 9 8 10 5 4
请按任意键继续. . .
#11
寒风中的细雨2012-05-11 08:25
程序代码：
/**

 * @文件名：Program.cs

 * @作  者：寒风中的细雨

 * @时  间：2012/5/11/

 * @概  述：使用顺序链表实现进制转换

 */
using System;

public interface IStack<T>
{
    int GetLength();//求栈的长度
    bool IsEmpty();//判断栈是否为空
    void Clear();//清空栈操作
    void Push(T nItem);//入栈
    void Pop();//出栈
    T GetTop();//取栈顶元素
}
//顺序栈
public class SeqStack<T> : IStack<T>
{
    private int m_MaxSize;//顺序栈的容量
    private T[] m_Data; //数组
    private int m_Top;//指示顺序栈的栈顶

    //索引器
    public T this[int nIndex]
    {
        get { return m_Data[nIndex];}
        set { m_Data[nIndex] = value; }
    }
    //容量属性
    public int MaxSize
    {
        get { return m_MaxSize; }
        set { m_MaxSize = value; }
    }
    //构造器
    public SeqStack(int nSize)
    {
        m_Data = new T[nSize];
        m_MaxSize = nSize;
        m_Top = -1;
    }
    //求栈的长度
    public int GetLength()
    {
        return (m_Top + 1);
    }
    //判断栈是否为空
    public bool IsEmpty()
    {
        return (-1 == m_Top);
    }
    //判断栈是否为满
    public bool IsFull()
    {
        return (m_MaxSize - 1 == m_Top);
    }
    //清空栈操作
    public void Clear()
    {
        m_Top = -1;
    }
    //进栈
    public void Push(T nItem)
    {
        if (IsFull())
        {
            Console.WriteLine("压栈失败，栈满...");
            return;
        }
        m_Data[++m_Top] = nItem;
    }
    //出栈
    public void Pop()
    {
        if (IsEmpty())
        {
            Console.WriteLine("出栈失败，栈空...");
            return;
        }
        --m_Top;
    }
    //取栈顶元素
    public T GetTop()
    {
        return m_Data[m_Top];
    }
}

public class SamplesArrayList
{
    static SeqStack<int> stack = new SeqStack<int>(80);

    public static void Main()
    {
        int N;//要转换的进制
        int getConsoleInput;//

        Console.Write("输入要变换的数字(十进制)：");
        getConsoleInput = int.Parse(Console.ReadLine());
        Console.Write("输入要转换的进制：");
        N = int.Parse(Console.ReadLine());

        Conversion(getConsoleInput, N);

        Console.Write("转换成"+N+"进制后的结果：");
        while (!stack.IsEmpty())
        {
            if (stack.GetTop() >= 10)
            {
                Console.Write((char)(87 + stack.GetTop()));
            }
            else
            {
                Console.Write(stack.GetTop());
            }
            stack.Pop();
        }
        Console.WriteLine();
    }

    public static void Conversion(int a, int b)
    {
        do
        {
            stack.Push(a%b);
            a = a / b;
        } while (0 != a);
    }
}

输入要变换的数字(十进制)：250
输入要转换的进制：16
转换成16进制后的结果：fa
请按任意键继续. . .
#12
寒风中的细雨2012-05-12 07:45
程序代码：
/**

 * @文件名：Program.cs

 * @作  者：寒风中的细雨

 * @时  间：2012/5/12/

 * @概  述：使用链栈实现进制转换

 */
using System;

public interface IStack<T>
{
    int GetLength();//求栈的长度
    bool IsEmpty();//判断栈是否为空
    void Clear();//清空栈操作
    void Push(T nItem);//入栈
    void Pop();//出栈
    T GetTop();//取栈顶元素
}

//结点
class Node<T>
{
    private T m_Data;
    private Node<T> m_Next;

    //m_Next属性
    public Node<T> Next
    {
        get { return m_Next; }
        set { m_Next = value; }
    }
    //m_Data属性
    public T Data
    {
        get { return m_Data; }
        set { m_Data = value; }
    }
    //构造函数
    public Node(T nData, Node<T> nNext)
    {
        m_Data = nData;
        m_Next = nNext;
    }
    public Node()
    {
        m_Data = default(T);
        m_Next = null;
    }
}

//链栈
public class LinkStack<T> : IStack<T>
{
    private Node<T> m_Top;
    private int m_Length;

    //构造器
    public LinkStack()
    {
        m_Length = 0;
        m_Top = null;
    }
    //求栈的长度
    public int GetLength()
    {
        return m_Length;
    }
    //判断栈是否为空
    public bool IsEmpty()
    {
        return (null == m_Top);
    }
    //清空栈操作
    public void Clear()
    {
        m_Top = null;
    }
    //进栈
    public void Push(T nItem)
    {
        if (IsEmpty())
        {
            m_Top = new Node<T>(nItem, null);
            ++m_Length;
            return;
        }
        m_Top = new Node<T>(nItem, m_Top);
        ++m_Length;
    }
    //出栈
    public void Pop()
    {
        if (IsEmpty())
        {
            Console.WriteLine("出栈失败，栈空...");
            return;
        }
        m_Top = m_Top.Next;
        --m_Length;
    }
    //取栈顶元素
    public T GetTop()
    {
        return m_Top.Data;
    }
}

public class SamplesArrayList
{
    static LinkStack<int> stack = new LinkStack<int>();

    public static void Main()
    {
        int N;//要转换的进制
        int getConsoleInput;//

        Console.Write("输入要变换的数字(十进制)：");
        getConsoleInput = int.Parse(Console.ReadLine());
        Console.Write("输入要转换的进制：");
        N = int.Parse(Console.ReadLine());

        Conversion(getConsoleInput, N);

        Console.Write("转换成"+N+"进制后的结果：");
        while (!stack.IsEmpty())
        {
            if (stack.GetTop() >= 10)
            {
                Console.Write((char)(87 + stack.GetTop()));
            }
            else
            {
                Console.Write(stack.GetTop());
            }
            stack.Pop();
        }
        Console.WriteLine();
    }

    public static void Conversion(int a, int b)
    {
        do
        {
            stack.Push(a%b);
            a = a / b;
        } while (0 != a);
    }
}

输入要变换的数字(十进制)：10
输入要转换的进制：8
转换成8进制后的结果：12
请按任意键继续. . .
#13
寒风中的细雨2012-05-13 10:10
程序代码：
/**

 * @文件名：Program.cs

 * @作  者：寒风中的细雨

 * @时  间：2012/5/13/

 * @概  述：使用栈实现 括号匹配的检验 其中括号只有[ ] ( ) 字符组成

 */
using System;

//此处省略掉栈的实现环节

public class App
{
    static LinkStack<char> stack = new LinkStack<char>();
    static string nStr;
    public enum Opr{OPR_IN, OPR_OUT}

    public static void Main()
    {
        Console.Write("输入要检验的括号字符串：");
        nStr = Console.ReadLine();
        if (Compare())
        {
            Console.WriteLine("结果：匹配成功！");
        }
        else
        {
            Console.WriteLine("结果：匹配失败！");
        }
    }

    //检验成功返回true  否则返回false
    public static bool Compare()
    {
        for (int i = 0; i < nStr.Length; ++i)
        {
            switch (GetOpr(nStr[i]))
            {
                case Opr.OPR_IN:
                    stack.Push(nStr[i]);
                    break;
                case Opr.OPR_OUT:
                    if (stack.GetTop() == '[' && nStr[i] == ']' ||
                        stack.GetTop() == '(' && nStr[i] == ')')
                    {
                        stack.Pop();
                    }
                    else
                    {
                        return false;
                    }
                    break;
                default: return false;
            }
        }
        return stack.IsEmpty();
    }

    //获取字符应该执行的操作
    public static Opr GetOpr(char c)
    {
        if ('[' == c || '(' == c)
        {//进栈操作
            return Opr.OPR_IN;
        }
        //出栈操作
        return Opr.OPR_OUT;
    }
}


输入要检验的括号字符串：[]([])[()]()
结果：匹配成功！
请按任意键继续. . .

输入要检验的括号字符串：(()]
结果：匹配失败！
请按任意键继续. . .
#14
寒风中的细雨2012-05-13 11:53
程序代码：
/**

 * @文件名：Program.cs

 * @作  者：寒风中的细雨

 * @时  间：2012/5/13/

 * @概  述：使用栈实现 行编辑器

 */
using System;

//此处省略掉栈的实现环节

public class App
{
    static LinkStack<char> stack = new LinkStack<char>();
    static string nStr;

    public static void Main()
    {
        Console.Write("输入要字符串：");
        nStr = Console.ReadLine();
        LineEditor();
        Console.Write("得到的最终字符串为：");
        PrintResult();
        Console.WriteLine();
    }
    /**
     * 功  能：在字符中 ‘#’为退格 ‘@’为删除该行中的内容
     */
    public static void LineEditor()
    {
        foreach(char i in nStr)
        {
            if (i == '#')
            {
                stack.Pop();
            }
            else if (i == '@')
            {
                stack.Clear();
            }
            else
            {
                stack.Push(i);
            }
        }
    }
    //
    public static void PrintResult()
    {
        if (!stack.IsEmpty())
        {
            char i = stack.GetTop();
            stack.Pop();
            PrintResult();
            Console.Write(i);  
        }
    }
}

输入要字符串：whli##ilr#e(s#*s)
得到的最终字符串为：while(*s)
请按任意键继续. . .

输入要字符串：outcha@putchar(*s=#++);
得到的最终字符串为：putchar(*s++);
请按任意键继续. . .


[ 本帖最后由 寒风中的细雨 于 2012-5-13 12:41 编辑 ]
#15
寒风中的细雨2012-05-14 11:29
程序代码：
/**

 * @文件名：App.cs

 * @作  者：寒风中的细雨

 * @时  间：2012/5/14/

 * @概  述：使用栈实现 迷宫

 */
using System;

enum Dir
{
    EAST,//东
    WEST,//西
    SOUTH,//南
    NORTH,//北
    END
}

class Pos//坐标
{
    int m_Row;//行号
    int m_Col;//列号
    Dir m_Dir;//方向
    public Pos(int nRow, int nCol, Dir nDir)
    {
        m_Row = nRow;
        m_Col = nCol;
        m_Dir = nDir;
    }
    public int Row
    {
        get { return m_Row; }
        set { m_Row = value; }
    }
    public int Col
    {
        get { return m_Col; }
        set { m_Col = value; }
    }
    public Dir Dir
    {
        get { return m_Dir; }
        set { m_Dir = value; }
    }
    public bool Equal(Pos obj)
    {
        return m_Col == obj.m_Col && m_Row == obj.m_Row;
    }
}

class App
{
    static int[,] map =//迷宫地图
    {  //0  1  2  3  4  5  6  7  8  9
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},//0
        {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},//1
        {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},//2
        {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},//3
        {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},//4
        {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},//5
        {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},//6
        {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},//7
        {1, 1, 0, 0, 0, 0, 0, 0, 0, 1},//8
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},//9
    };
    static LinkStack<Pos> stack = new LinkStack<Pos>();

    static void Main(string[] args)
    {
        Pos startPos = new Pos(1, 1, Dir.EAST);//起点
        Pos endPos = new Pos(8, 8, Dir.EAST);//终点

        stack.Push(startPos);//压入起点
        map[startPos.Row, startPos.Col] = 1;

        MazePath(endPos);//

        Console.WriteLine("下面为行走轨迹...");
        PrintTrace();
    }

    //走迷宫
    static void MazePath(Pos endPos)
    {
        while (!stack.IsEmpty() && !stack.GetTop().Equal(endPos))
        {
            Pos tmpPos = stack.GetTop();

            switch (tmpPos.Dir)
            {
            case Dir.EAST://东
                tmpPos.Dir = Dir.SOUTH;//修改方向
                if (0 == map[tmpPos.Row, tmpPos.Col + 1])
                {
                    stack.Push(new Pos(tmpPos.Row, tmpPos.Col+1, Dir.EAST));
                    map[tmpPos.Row, tmpPos.Col + 1] = 1;
                }
                break;
            case Dir.SOUTH://南
                tmpPos.Dir = Dir.WEST;//修改方向
                if (0 == map[tmpPos.Row+1, tmpPos.Col])
                {
                    stack.Push(new Pos(tmpPos.Row + 1, tmpPos.Col, Dir.EAST));
                    map[tmpPos.Row + 1, tmpPos.Col] = 1;
                }
                break;
            case Dir.WEST://西
                tmpPos.Dir = Dir.NORTH;//修改方向
                if (0 == map[tmpPos.Row, tmpPos.Col-1])
                {
                    stack.Push(new Pos(tmpPos.Row, tmpPos.Col - 1, Dir.EAST));
                    map[tmpPos.Row, tmpPos.Col - 1] = 1;
                }
                break;
            case Dir.NORTH://北
                tmpPos.Dir = Dir.END;//修改方向
                if (0 == map[tmpPos.Row-1, tmpPos.Col])
                {
                    stack.Push(new Pos(tmpPos.Row-1, tmpPos.Col, Dir.EAST));
                    map[tmpPos.Row - 1, tmpPos.Col] = 1;
                }
                break;
            case Dir.END://出栈
                stack.Pop();
                break;
            default:
                break;
            }
        }
    }

    //输出行走轨迹
    static void PrintTrace()
    {
        if (!stack.IsEmpty())
        {
            Pos tmpPos = stack.GetTop();
            stack.Pop();
            PrintTrace();
            Console.WriteLine("("+tmpPos.Row+", "+tmpPos.Col+")");
        }
    }
}
#16
寒风中的细雨2012-05-14 11:30
程序代码：
/**

 * @文件名：App.cs

 * @作  者：寒风中的细雨

 * @时  间：2012/5/14/

 * @概  述：使用栈实现 中缀表达式转为后缀表达式

 *          支持一位整数的操作数

 */
using System;

class App
{
    static int[,] op_pri = //运算符为左结合 所以栈里面的优先级大于栈外的
    {//  +, -, *, /, #, (, )
        {2, 2, 4, 4, 0, 6, 1},//out
        {3, 3, 5, 5, 0, 1, 'X'}//in
    };
    static LinkStack<char> optr = new LinkStack<char>();//操作符
    static LinkStack<char> opnd = new LinkStack<char>();//操作数

    static void Main(string[] args)
    {
        string nStr;
        Console.Write("输入表达式:");
        nStr = Console.ReadLine();
        nStr += '#';
        optr.Push('#');
        EvaluateExpression(nStr);
        Console.WriteLine("结果为:");
        Print();
    }

    static void EvaluateExpression(string nStr)
    {
        for (int i=0; i<nStr.Length;)
        {
            if (-1 == GetIndex(nStr[i]))
            {
                opnd.Push(nStr[i]);
                ++i;
            }
            else
            {
                i = DoOptr(nStr[i], i);
            }
        }
    }

    static int DoOptr(char nChar, int i)
    {
        int nIn = GetIndex(optr.GetTop());
        int nOut = GetIndex(nChar);
        if (op_pri[0, nOut] > op_pri[1, nIn])
        {//进栈
            optr.Push(nChar);
            return i + 1;
        }
        else if (op_pri[0, nOut] < op_pri[1, nIn])
        {//出栈
            opnd.Push(optr.GetTop());
            optr.Pop();
            return i;
        }
        else
        {
            optr.Pop();
            return i + 1;
        }
    }

    static void Print()
    {
        if (!opnd.IsEmpty())
        {
            char nChar = opnd.GetTop();
            opnd.Pop();
            Print();
            Console.Write(nChar);
        }
    }

    //获取字符在数组中对应的下标志
    static int GetIndex(char nChar)
    {
        switch (nChar)
        {
            case '+':
                return 0;
                break;
            case '-':
                return 1;
                break;
            case '*':
                return 2;
                break;
            case '/':
                return 3;
                break;
            case '#':
                return 4;
                break;
            case '(':
                return 5;
                break;
            case ')':
                return 6;
                break;
            default:
                return -1;
                break;
        }
    }
}

输入表达式:4+2*3-9/5
结果为:
423*+95/-请按任意键继续. . .
#17
寒风中的细雨2012-05-14 15:24
程序代码：
/**

 * @文件名：App.cs

 * @作  者：寒风中的细雨

 * @时  间：2012/5/14/

 * @概  述：使用栈实现  字符“ABCD”的全排

 */
using System;
class Node
{
    private int m_PosSwap;
    private string m_Data;
    public Node(int nPos, string nData)
    {
        m_Data = nData;
        m_PosSwap = nPos;
    }
    public int GetPos
    {
        get { return m_PosSwap; }
        set { m_PosSwap = value; }
    }
    public string Data
    {
        get { return m_Data; }
        set { m_Data = value; }
    }
}
class App
{
    //要进行全排的字符串
    static string m_Str = "ABCD";
    static LinkStack<Node> stack = new LinkStack<Node>();

    static void Main(string[] args)
    {
        stack.Push(new Node(-1, m_Str));//初始化栈
        DoAllSort();//进行全排
    }

    static void DoAllSort()
    {
        while (!stack.IsEmpty())
        {
            Node tmpNode = stack.GetTop();
            stack.Pop();
            string nStr = tmpNode.Data;//当前处理的字符串
            int nStartPos = tmpNode.GetPos+1;//字符交换的起始位置
            char[] m_Array = new char[nStr.Length];
            nStr.CopyTo(0, m_Array, 0, nStr.Length);
            for (int i = nStartPos; i < nStr.Length; ++i)
            {
                //交换字符串的位置
                CharSwap(ref m_Array[i], ref m_Array[nStartPos]);
                stack.Push(new Node(nStartPos, new string(m_Array)));
                CharSwap(ref m_Array[i], ref m_Array[nStartPos]);
            }
            PrintArrange();
        }
    }

    static void CharSwap(ref char c, ref char b)
    {
        char tmp = c;
        c = b;
        b = tmp;
    }

    static void PrintArrange()
    {
        while (!stack.IsEmpty())
        {
            Node tmpNode = stack.GetTop();
            if (tmpNode.GetPos + 1 == tmpNode.Data.Length)
            {
                foreach (char i in tmpNode.Data)
                {
                    Console.Write("{0} ", i);
                }
                Console.WriteLine();
                stack.Pop();//出栈
            }
            else
            {
                break;
            }
        }
    }
}

D A B C
D A C B
D C A B
D C B A
D B A C
D B C A
C D B A
C D A B
C A D B
C A B D
C B D A
C B A D
B D A C
B D C A
B C D A
B C A D
B A D C
B A C D
A D B C
A D C B
A C D B
A C B D
A B D C
A B C D
请按任意键继续. . .
#18
寒风中的细雨2012-05-14 15:31
回复 17楼 寒风中的细雨
因为对象指示器属性为只读， 中间只好转向到字符数组中去交换字符操作

因为不熟悉C#中字符串 和 字符数组   感觉和c++中的有很大的差别  用起来有点费神

因此代码看起来很臃肿...    留待后面再改进吧
#19
BlueGuy2012-05-14 17:45
以下是引用寒风中的细雨在2012-5-14 15:31:39的发言：

因为对象指示器属性为只读， 中间只好转向到字符数组中去交换字符操作

因为不熟悉C#中字符串 和 字符数组   感觉和c++中的有很大的差别  用起来有点费神

因此代码看起来很臃肿...    留待后面再改进吧
你在作茧自缚， 知道吗？
#20
寒风中的细雨2012-05-14 18:41
回复 19楼 BlueGuy
写的不好的地方，  是希望路过的前辈可以加以改正。

你突然蹦出这么句话  我表示很茫然。
#21
寒风中的细雨2012-05-16 13:12
程序代码：
/**

 * @文件名：Program.cs

 * @作  者：寒风中的细雨

 * @时  间：2012/5/16/

 * @概  述：栈的基本操作, 队列的基本操作

 */
using System;

public interface IStack<T>
{
    int GetLength();//求栈的长度
    bool IsEmpty();//判断栈是否为空
    void Clear();//清空栈操作
    void Push(T nItem);//入栈
    void Pop();//出栈
    T GetTop();//取栈顶元素
}
public interface IQueue<T>
{
    int GetLength();//求队列的长度
    bool IsEmpty();//判断队列是否为空
    void Clear();//清空队列
    void In(T nItem);//入队
    void Out();//出队
    T GetFront();//取对头元素
}
//结点
class Node<T>
{
    private T m_Data;
    private Node<T> m_Next;
    //m_Next属性
    public Node<T> Next
    {
        get { return m_Next; }
        set { m_Next = value; }
    }
    //m_Data属性
    public T Data
    {
        get { return m_Data; }
        set { m_Data = value; }
    }
    //构造函数
    public Node(T nData, Node<T> nNext)
    {
        m_Data = nData;
        m_Next = nNext;
    }
    public Node()
    {
        m_Data = default(T);
        m_Next = null;
    }
}
//链栈
public class LinkStack<T>:IStack<T>
{
    private Node<T> m_Top;
    private int m_Length;
    //构造器
    public LinkStack()
    {
        m_Length = 0;
        m_Top = null;
    }
    //求栈的长度
    public int GetLength()
    {
        return m_Length;
    }
    //判断栈是否为空
    public bool IsEmpty()
    {
        return (null == m_Top);
    }
    //清空栈操作
    public void Clear()
    {
        m_Top = null;
    }
    //进栈
    public void Push(T nItem)
    {
        if (IsEmpty())
        {
            m_Top = new Node<T>(nItem, null);
            ++m_Length;
            return;
        }
        m_Top = new Node<T>(nItem, m_Top);
        ++m_Length;
    }
    //出栈
    public void Pop()
    {
        if (IsEmpty())
        {
            Console.WriteLine("出栈失败，栈空...");
            return;
        }
        m_Top = m_Top.Next;
        --m_Length;
    }
    //取栈顶元素
    public T GetTop()
    {
        return m_Top.Data;
    }
}
//队列
public class LinkQueue<T>:IQueue<T>
{
    private Node<T> m_Rear;//队尾
    private Node<T> m_Front;//对头
    private int m_Length;//队长度
    //构造函数
    public LinkQueue()
    {
        m_Length = 0;
        m_Front = m_Rear = null;
    }
    //求队列的长度
    public int GetLength()
    {
        return m_Length;
    }
    //判断队列是否为空
    public bool IsEmpty()
    {
        return 0 == m_Length;
    }
    //清空队列
    public void Clear()
    {
        m_Length = 0;
        m_Front = m_Rear = null;
    }
    //入队
    public void In(T nItem)
    {
        if (this.IsEmpty())
        {
            m_Front = m_Rear = new Node<T>(nItem, null);
        }
        else
        {
            m_Rear.Next = new Node<T>(nItem, null);
            m_Rear = m_Rear.Next;
        }
        ++m_Length;
    }
    //出队
    public void Out()
    {
        if (this.IsEmpty())
        {
            Console.WriteLine("队列为空...");
            return;
        }
        if (m_Length > 1)
        {
            m_Front = m_Front.Next;
        }
        else
        {
            m_Front = m_Rear = null;
        }
        --m_Length;
    }
    //取对头元素
    public T GetFront()
    {
        return m_Front.Data;
    }
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**

 * @文件名：App.cs

 * @作  者：寒风中的细雨

 * @时  间：2012/5/16/

 * @概  述：树的基本操作 模拟递归实现

 */
using System;

//二叉数的结点结构
class BinaryTreeNode<T>
{
    private int m_Num;//后序遍历时候使用
    private T m_Data;
    private BinaryTreeNode<T> m_Lchild;
    private BinaryTreeNode<T> m_Rchild;

    //构造函数
    public BinaryTreeNode(T nData, BinaryTreeNode<T> nLchild,
        BinaryTreeNode<T> nRchild)
    {
        m_Data = nData;
        m_Lchild = nLchild;
        m_Rchild = nRchild;
        m_Num = 0;
    }

    //属性域
    public T Data
    {
        get { return m_Data; }
        set { m_Data = value; }
    }
    public BinaryTreeNode<T> Lchild
    {
        get { return m_Lchild; }
        set { m_Lchild = value; }
    }
    public BinaryTreeNode<T> Rchild
    {
        get { return m_Rchild; }
        set { m_Rchild = value; }
    }
    public int Num
    {
        get { return m_Num; }
        set { m_Num = value; }
    }
}

//二叉树类
class BinaryTree
{
    private BinaryTreeNode<char> m_Head;

    //属性域
    public BinaryTreeNode<char> Head
    {
        get { return m_Head; }
        set { m_Head = value; }
    }

    //构造函数
    public BinaryTree()
    {
        m_Head = null;
    }
      
    //建树 利用字符串ABC@@D@@E@F@@  先序字符串
    public void CreatTreeByString(string nStr)
    {
        LinkStack<BinaryTreeNode<char>> stack = new LinkStack<BinaryTreeNode<char>>();
        int i = 0;
        BinaryTreeNode<char> tmp = null;

        do
        {
            while (nStr[i] != '@')
            {//左孩子
                if (m_Head == null)
                {
                    m_Head = new BinaryTreeNode<char>(nStr[i], null, null);
                    stack.Push(m_Head);
                }
                else
                {
                    tmp = new BinaryTreeNode<char>(nStr[i], null, null);
                    stack.GetTop().Lchild = tmp;
                    stack.Push(tmp);
                }
                ++i;
            }
           
            stack.GetTop().Lchild = null;
            tmp = stack.GetTop();
            stack.Pop();

            ++i;
            if (nStr[i] == '@')
            {//第二个 进行出栈
                tmp.Rchild = null;
                if (stack.IsEmpty())
                {
                    break;
                }
                tmp = stack.GetTop();
                stack.Pop();
                ++i;
                if (nStr[i] == '@')
                {
                    tmp.Rchild = null;
                    ++i;
                    continue;
                }
            }
   
            BinaryTreeNode<char> tmp1 = null;
            tmp1 = new BinaryTreeNode<char>(nStr[i], null, null);
            tmp.Rchild = tmp1;
            stack.Push(tmp1);
            ++i;
        } while (!stack.IsEmpty());
    }

    //先序遍历
    public void PreOrderTraverse()
    {
        LinkStack<BinaryTreeNode<char>> stack = new LinkStack<BinaryTreeNode<char>>();

        if (m_Head == null)
        {
            Console.WriteLine("为空树...");
            return;
        }

        BinaryTreeNode<char> tmp = m_Head;
        do
        {
            while (tmp != null)
            {
                Console.Write("{0} ", tmp.Data);
                stack.Push(tmp);
                tmp = tmp.Lchild;
            }

            tmp = stack.GetTop();
            stack.Pop();
            tmp = tmp.Rchild;
        } while (!stack.IsEmpty() || null !=tmp);
        Console.WriteLine();
    }

    //中序遍历
    public void InOrderTraverse()
    {
        LinkStack<BinaryTreeNode<char>> stack = new LinkStack<BinaryTreeNode<char>>();

        if (m_Head == null)
        {
            Console.WriteLine("为空树...");
            return;
        }

        BinaryTreeNode<char> tmp = m_Head;
        do
        {
            while (tmp != null)
            {
                stack.Push(tmp);
                tmp = tmp.Lchild;
            }

            tmp = stack.GetTop();
            Console.Write("{0} ", tmp.Data);
            stack.Pop();
            tmp = tmp.Rchild;
        } while (!stack.IsEmpty() || null != tmp);
        Console.WriteLine();
    }
   
    //后序遍历
    public void PostOrderTraverse()
    {
        LinkStack<BinaryTreeNode<char>> stack = new LinkStack<BinaryTreeNode<char>>();
        if (m_Head == null)
        {
            Console.WriteLine("为空树...");
            return;
        }
        BinaryTreeNode<char> tmp = m_Head;

        do
        {
            while (tmp != null)
            {
                stack.Push(tmp);
                tmp = tmp.Lchild;
            }

            tmp = stack.GetTop();
            tmp.Num += 1;

            while (!stack.IsEmpty() && stack.GetTop().Num == 2)
            {
                Console.Write("{0} ", stack.GetTop().Data);
                stack.Pop();
                if (!stack.IsEmpty())
                {
                    stack.GetTop().Num += 1;
                }
            }
            if (!stack.IsEmpty())
            {
                tmp = stack.GetTop().Rchild;
            }

        } while (!stack.IsEmpty());
        Console.WriteLine();
    }

    //层序遍历
    public void LevelOrderTraverse()
    {
        LinkQueue<BinaryTreeNode<char>> queue = new LinkQueue<BinaryTreeNode<char>>();

        if (m_Head == null)
        {
            Console.WriteLine("为空树...");
            return;
        }

        BinaryTreeNode<char> tmp = m_Head;
        queue.In(tmp);

        do
        {
            tmp = queue.GetFront();
            Console.Write("{0} ", tmp.Data);
            queue.Out();

            if (tmp.Lchild != null)
            {
                queue.In(tmp.Lchild);
            }
            if (tmp.Rchild != null)
            {
                queue.In(tmp.Rchild);
            }
        } while (!queue.IsEmpty());
        Console.WriteLine();
    }
}

class App
{
    static void Main(string[] args)
    {
        BinaryTree Tree = new BinaryTree();

        Tree.CreatTreeByString("AB@D@@EF@@@");
        Console.WriteLine("先序遍历");
        Tree.PreOrderTraverse();
        Console.WriteLine("中序遍历");
        Tree.InOrderTraverse();
        Console.WriteLine("后序遍历");
        Tree.PostOrderTraverse();
        Console.WriteLine("层序遍历");
        Tree.LevelOrderTraverse();

        Console.WriteLine();

        BinaryTree tree = new BinaryTree();

        tree.CreatTreeByString("ABC@@D@@E@F@@");
        Console.WriteLine("先序遍历");
        tree.PreOrderTraverse();
        Console.WriteLine("中序遍历");
        tree.InOrderTraverse();
        Console.WriteLine("后序遍历");
        tree.PostOrderTraverse();
        Console.WriteLine("层序遍历");
        tree.LevelOrderTraverse();
    }
}

先序遍历
A B D E F
中序遍历
B D A F E
后序遍历
D B F E A
层序遍历
A B E D F

先序遍历
A B C D E F
中序遍历
C B D A E F
后序遍历
C D B F E A
层序遍历
A B E C D F
请按任意键继续. . .
#22
孀倪2012-09-12 17:08
我没学过c#，可是我看着这代码 我就第一感觉认为是c++。
咋一看，这两者好像没什么区别，都是面向对象的，可是本质上到底区别在哪 版主，我只知道c#做图形界面做的很好。其他就不知道了。
版主能否给我详细的解答解答。谢谢！
#23
lisong6192013-03-31 18:36
啊，啊啊啊啊，跪谢LZ啊。。。。。千难万险才找到一个啊
1
©2025, BCCN.NET
电脑版