妹妹我初学数据结构。刚学栈,用栈将 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("输入的不合法,请重新输入: ");
}
}
}