首页 > 代码库 > 第三章解决堆栈的编程问题

第三章解决堆栈的编程问题

第三章      解决堆栈的编程问题

堆栈是一种特殊的线性表,是一种只允许在表的一端进行插入或删除操作的线性表。

堆栈的主要特点是后进先出

用一片连续的存储空间来存储栈中的元素,这样的栈称为顺序栈

用链式存储结构存储的栈称为链栈

汉诺塔问题

         汉诺塔问题来自一个古老的传说:在世界刚刚被创建的时候有一座砖石宝塔(A),其上有64个金蝶。所有按从大到小的顺序从塔底堆放至塔顶。紧挨着这座塔有两个砖石塔(BC)。从世界创始之日起,婆罗门的牧师们就一直在试图把A塔上的碟子移动到B上去,其间借助于C的帮助。由于碟子非常重,因此,每次只能移动一个碟子。另外,任何时候都不能把一个碟子放在比它小的碟子上面。按照这个传说,当牧师们完成所有的任务之后,世界末日也就到了。

         在汉诺塔问题中,已知n个碟子和3座塔。初始时所有的碟子按从大到小的次序从塔A的底部堆放至顶部,现在需要把碟子都移动到B塔,每次移动一个碟子,而且任何时候都不能把大碟子放到小碟子上面。

         【基本要求】

(1)      编写一个算法实现将A塔上的碟子移动到B塔上,大碟子在下,小碟子在上。

(2)      将移动的过程显示出来

思路:

         wKiom1QdSrLwFtDQAAD-R53j8M8491.jpg

由上可知,要想把n个碟子从A移动到目标塔(不妨设为B),则需要将n-1个碟子移动到缓冲塔(C),然后将最大的碟子放到B

         再往前迭代,即以A为缓冲塔,只需将n-2个碟子移动到B,然后将次大的移动到C

         ……

         直到最后只需移动一个碟子到指定的塔。

汉诺塔碟子的移动次数为:2n-1

C#代码实现如下:

1)  封装栈结点:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace LinkStack

{

    class StackNode<T>

    {

        private T data;

        privateStackNode<T> next;

        public StackNode()

        {

            data = http://www.mamicode.com/default(T);

            next = null;

        }

        public StackNode(Tval)

        {

            data = http://www.mamicode.com/val;

            next = null;

        }

        public StackNode(Tval, StackNode<T> p)

        {

            data = http://www.mamicode.com/val;

            next = p;

        }

        public T Data

        {

            get

            {

                return data;

            }

            set

            {

                data = http://www.mamicode.com/value;

            }

        }

        publicStackNode<T> Next

        {

            get

            {

                return next;

            }

            set

            {

                next = value;

            }

        }

    }

}

2)  栈操作接口:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace LinkStack

{

    interface IStack<T>

    {

        void Push(T item);//压栈

        T Pop();//出栈

        bool isEmpty();

        void Clear();

    }

}

3)  链栈封装:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace LinkStack

{

    classLStack<T>:IStack<T>

    {

        privateStackNode<T> top;

        private int count;

        private string name =string.Empty;

 

        public int Count

        {

            get { returncount; }

 

        }

 

        public string Name

        {

            get { return name;}

            set { name =value; }

        }

        public LStack()

        {

            top = null;

            count = 0;

        }

        public LStack(stringname)

        {

            this.name = name;

            top = null;

            count = 0;

        }

        public void Push(Titem)

        {

            StackNode<T> tnode = newStackNode<T>(item);

            if (top == null)

            {

                top = tnode;

            }

            else

            {

                tnode.Next =top;

                top = tnode;

            }

            count++;

        }

 

        public T Pop()

        {

            if (top == null&& count == 0)

            {

                throw newException("栈为空!");

            }

            StackNode<T>tnode = top;

            top = top.Next;

            count--;

            return tnode.Data;

        }

 

        public bool isEmpty()

        {

            if (top == null&& count == 0)

            {

                return true;

            }

            return false;

        }

 

        public void Clear()

        {

            top = null;

            count = 0;

        }

    }

}

4)  算法实现:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace LinkStack

{

    class Program

    {

        /// <summary>

        /// 解决汉诺塔问题

        /// </summary>

        /// <paramname="args"></param>

        static voidMain(string[] args)

        {

            //三根塔柱

            LStack<int>tln_A =new LStack<int>("A");

            LStack<int>tln_B = new LStack<int>("B");

            LStack<int>tln_C = new LStack<int>("C");

           Console.WriteLine("请输入汉诺塔中上碟子的个数");

            string nstr =Console.ReadLine();

            int n;

            if(!int.TryParse(nstr, out n))

            {

               Console.WriteLine("请输入有效的整数!");

            }

            for (int i = n;i>=1; i--)

            {

                tln_A.Push(i);

            }

            MoveTa(n, tln_B,tln_A, tln_C);

           Console.WriteLine("B塔元素依次为:");

            for (int i = 0; i< n;i++ )

            {

               Console.Write(tln_B.Pop() + "   ");

            }

            Console.ReadKey();

        }

        static void MoveTa(intn, LStack<int> desT, LStack<int> srcT,LStack<int> bufT)

        {

            if (n == 1)

            {

                int t =srcT.Pop();

                desT.Push(t);

                string str="将金碟"+t+"从塔" + srcT.Name + "移动到" +desT.Name;

               Console.WriteLine(str);

            }

            else

            {

                MoveTa(n - 1,bufT,srcT,desT);

                //移动最大的金蝶

                int t =srcT.Pop();

                desT.Push(t);

                string str ="将金碟" + t + "从塔" + srcT.Name + "移动到" +desT.Name;

               Console.WriteLine(str);

                MoveTa(n - 1,desT, bufT, srcT);

            }

        }

    }

}


本文出自 “虎哥的博客” 博客,请务必保留此出处http://7613577.blog.51cto.com/7603577/1555563

第三章解决堆栈的编程问题