| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 770 人关注过本帖
标题:妹妹我初学数据结构。刚学栈,用栈将 n 全排列.这里是我的代码,可是就是运 ...
只看楼主 加入收藏
冰冰酱
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2014-4-22
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:5 
妹妹我初学数据结构。刚学栈,用栈将 n 全排列.这里是我的代码,可是就是运行不出结果,哪个大神给我看看,万分感谢。
妹妹我初学数据结构。刚学栈,用栈将n全排列.这里是我的代码,可是就是运行不出结果,哪个大神给我看看,万分感谢。
(一)
public interface nStackADT {
    public void initial(int n);
    public  boolean stackfull(int n);
    public  void stackprint(int n) ;
    public void stackoutfile(int n) ;
    public void stackback();
    public void stackadd(int n) ;
    public void stackmov(int n) ;
    public void stackfun(int n) ;

}

(二)
import java.util.EmptyStackException;
import java.security.PrivilegedExceptionAction;
public class nStack implements nStackADT {

    private int stack[];
    private int top=-1;
    private int a[], b[], c[];//分别表示当前数的值,改变后的值,及改变的次数.
    private final int DEFUALT_CAPACITY = 20;

    /**********************
     * 对栈进行初始化.
     **********************/
    public void initial(int n) {
        //int i=0;
        for (int i = 0; i < n; i++){
            stack[++top] = i; // 第一次初始化的值.
            a[i] = b[i] = i; // 初始值相同.
            c[i] = 0; // 0表示尚未改变过.
        }
    }
   

    /***********************************************
     * 判断栈是否已满,在本程序中,此函数实际上是多余的.
     ***********************************************/
    public boolean stackfull(int n) {
        if (top + 1 == n)
            return true;
        else
            return false;
    }

    /**********************************
     * 当经过一次退栈后,当前栈顶是top,则top+1到n-1 中并没有填充数字,此函数的作用就是为后面 的栈中重新入栈. 并且此处是有规律的入栈.
     **********************************/
    public void stackadd(int n) {

        int j;
        int k, flag; // j,k是控制变量,flag是标志变量.
        while (1 + top < n) // 一直循环到最后.
        {
            /************************
             * 此段的作用是使当前填充的值与前面的都不相同. 用for循环控制.
             ************************/
            for (j = 0; j < n; j++) {
                flag = 0;
                for (k = 0; k <= top; k++) {
                    if (j == stack[k]) // 若与某一个栈相同,则重新对j赋值.
                    {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0) // 当flag为0时,表示赋值成功.
                {
                    stack[++top] = j; // 当此值赋到栈中.
                    a[top] = b[top] = j;// 同时重新定义当前值,并使其相等.相当于又初始化.
                    c[top] = 0;// 把值的改变次数定义为0.
                    break;
                }
            }
        }
    }

    /********************
     * 打印栈中的数值. 此处是输出到屏幕上.
     ********************/
    public void stackprint(int n) {
        int i = 0;
        for (i = 0; i < n; i++)
            System.out.print(+stack[i]);
        System.out.println();
    }
   
   
    public void stackback() {
        --top;
    }


    /*********************************
     * 本程序的核心所在. 算法是若退栈到当前值,则改变当前值. 使当前栈值b[top]=(b[top]+1)%n;
     *********************************/
    public void stackmov(int n) {
        int flag, i;
        while (true) {
            b[top] = (b[top] + 1) % n; // 此处比较好理解,即循环.
            c[top]++; // 记录值的变化.
            flag = 0; // 0表示赋值成功,1表示要赋的值已被占用.
            for (i = 0; i < top; i++) {
                if (b[top] == stack[i]) // 要赋的值已存在.
                {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1) // 若赋值失败则进行下一轮的赋值.
                continue;
            if ((a[top] == b[top]) || flag == 0) // 结果是要么赋值成功,要么回到原来的值.
                break;
        }
        if (flag == 0 && (a[top] != b[top])) // 当赋值成功.
        {
            stack[top] = b[top]; // 将值赋进栈中.
            stackadd(n); // 对该栈后面的值进行填充.
        } else
            // 当回到原来的位置,要退栈.
            stackback();
    }

    /**********************************
    *此处是接口函数.
    **********************************/
    public void stackfun(int n)
    {
        
        initial(n);    //初始化.
        if(stackfull(n))   //初始化后本身就是一个成功的排列,打印出来.
        {
            stackprint(n);
            
        }

        while(true)   //一直循环下去,直到退无可退.
        {
            /*********************************
            *这是本程序中最关键的一条指令.
            *此处的退栈仅且只能在值尚未发生变化的情况下退栈.
            *若没有c[top]!=0,当退到任一个栈时,他们的初始状态都是a[top]==b[top]
            *若是(a[top]==b[top])&&c[top]!=0表明当前栈已是退无可退.
            *此处有个关键时,第一轮开始的时候并没有执行该指令,当栈顶值循环一轮后
            *使c[top]!=0后才开始执行的,要特别注意这个地方.
            *********************************/
            if((a[top]==b[top])&&c[top]!=0)  
                stackback();
            stackmov(n);     //退完栈后要补齐后面的.
            if(stackfull(n))
            {
                stackprint(n);
            
            }

            if(top==-1)     //结束的条件,退无可退.
                break;
        }
        
    }


    public void stackoutfile(int n) {
        // TODO Auto-generated method stub
        
    }

}

(三)
import java.util.Scanner;

public class test {
    public static void main(String[] args) {
   
        Scanner s=new Scanner(System.in);  
        System.out.println("请输入一个整数:");  
        int n=s.nextInt();   
            nStack stack=new nStack();
        while(true)
        {      
        
            if(n>0)
            {
                System.out.println(n+"的排列如下:\n");
                stack.stackfun(n);
                System.out.println();
                System.out.println("请输入一个数字: ");
            }
            else
                System.out.print("输入的不合法,请重新输入: ");
        }
    }
   
   
   
}







搜索更多相关主题的帖子: interface initial public import 
2014-04-22 17:24
黄昏的王座
Rank: 2
来 自:安徽亳州
等 级:论坛游民
帖 子:38
专家分:65
注 册:2011-10-5
收藏
得分:10 
...
你栈里面的数组没有进行空间分配。会出现nullpoint错误。。。

2014-04-23 12:25
黄昏的王座
Rank: 2
来 自:安徽亳州
等 级:论坛游民
帖 子:38
专家分:65
注 册:2011-10-5
收藏
得分:0 
你在初始化的时候给他们分配一下空间就可以了。。。
图片附件: 游客没有浏览图片的权限,请 登录注册

2014-04-23 12:28
xl881221
Rank: 3Rank: 3
等 级:论坛游侠
威 望:2
帖 子:30
专家分:177
注 册:2014-3-23
收藏
得分:10 
initial(int n)初始化的时候加上
        stack=new int[n];
        a=new int[n];
        b=new int[n];
        c=new int[n];
class test里的while(true)去掉,不去的话,我运行是无限循环
2014-04-23 13:49
冰冰酱
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2014-4-22
收藏
得分:0 
回复 3 楼 黄昏的王座
谢谢,可以啦~~\(≧▽≦)/~啦啦啦
2014-04-23 22:19
冰冰酱
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2014-4-22
收藏
得分:0 
回复 4 楼 xl881221
O(∩_∩)O谢谢,可以~\(≧▽≦)/~啦啦啦
2014-04-23 22:19
快速回复:妹妹我初学数据结构。刚学栈,用栈将 n 全排列.这里是我的代码,可是就 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.029354 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved