用栈实现N全排列的代码和实验报告.doc

-管理信息系统作业
第2次作业
第2组成员

序号
学号
姓名
任务
成绩
备注
7
201217010102
何偲
程序设计
99

8
201217010103
何玲玲
程序设计
99

9
201217010104
黄春媛
程序设计、完成实验报告
100
组长
10
201217010105
靳梦迪
程序设计
99

一、小组问题
1.对于本实验中栈顶元素可不可再变大的程序不会写。
2.程序语法没有错但输出结果不对，找不出错误，不会调试。
二、小组建议
1.希望老师在我们绞尽脑筋都还没有解决问题的时候给我们提示一下，帮助我们转换思维，从而解决问题。
2. 写出来的程序没有语法错误，但得出的结果也不对，但是不会调试，希望下次上课老师可以能用多讲解如何调试程序。
三、小组总结
拿到题目后，我们说了自己的理解，还提出了自己不懂的的部分来讨论，争取每一个组员能够对题目的做法有所了解。分析了题目我们就知道要创造哪几个类，由于可以用课堂上的代码，省去很多功夫，但是算法的逻辑太复杂，我们认真地研究好久后都没做出来，然后去请教了黄万艮老师，把思路想清，但是还是有一些判断条件不懂怎么写，后来老师在班群发的提示研究了许久终于弄出来了。
这次的实验作业使我们更加熟练地操作和编写程序，每一次的作业都让我们学到不少的东西，也让我们知道自己的弱点所在，从而通过平时的练习来补自己的不足之处 。
五、实验
1.实验目的
熟悉栈的ADT以及它的方法实现，学会用栈的方法去解决一些问题。
2.实验要求
求n个元素的所有排列，要求：使用栈。
例如n=3时得：123、132、213、231、312、321
3.算法设计
public void pailie(int n)
{
ArrayStack stack=new ArrayStack();
for(int a=1;a<=n;a++)
stack.push(a);
System.out.println(stack.toString());
boolean back=false;
while(!stack.isEmpty()&&!back)
{
int i=stack.pop();
for(;i<n;i++)
if(!stack.find(i+1))
{
stack.push(i+1);
for(int j=1;j<n+1;j++)
{
if(!stack.find(j)){ stack.push(j);}
}
System.out.println(stack.toString());
back=false;break;
}
} }
4.软件结构

5.程序清单
1.StackADT:
import java.util.EmptyStackException;
public interface StackADT {
public int size();
public boolean isEmpty();
public void push(int n);
public int pop()throws EmptyStackException;
public int peek();
public String toString();
}
2.ArrayStack:
import java.util.EmptyStackException;
public class ArrayStack implements StackADT{
private Object[] stack;
public int top ;
private final int DEFAULT_CAPACITY=20;
public ArrayStack(){stack=new Object [DEFAULT_CAPACITY];top=-1; }
public ArrayStack(int size){stack =new Object [size];top=-1; }
public int size(){return top+1;}
public boolean isEmpty(){ return top==-1;}
public void push(int n)
{
if(top+1==stack.length) expandCapacity();
stack[++top]=n;
}
private void expandCapacity()
{
Object[] newstack=new Object[stack.length*2+1];
for(int i=0;i<top;i++)
newstack[i]=stack[i];
stack=newstack;
}
public int pop()throws EmptyStackException
{
if(top==-1)throw new EmptyStackException();
return (Integer)stack[top--];
}
public int peek(){ return (Integer) stack[top];}
public String toString()
{
String string="";
for(int i=0;i<=top;i++)
string=string+stack[i].toString();
return string;
}
public boolean find(int k)
{
boolean result=false;
for(int i=0;i<=top;i++)
{
if(k== (Integer)stack[i]){ result=true;break;}
}
return result;
}
}
3.Expression:
public class Expression
{
public void pailie(int n)
{

ArrayStack stack=new ArrayStack();
for(int a=1;a<=n;a++)
stack.push(a);
System.out.println(stack.toString());
boolean back=false;
while(!stack.isEmpty()&&!back)
{
int i=stack.pop();
for(;i<n;i++)
if(!stack.find(i+1))
{
stack.push(i+1);

for(int j=1;j<n+1;j++)
{
if(!stack.find(j)){ stack.push(j);}

}
System.out.println(stack.toString());

back=false;break;
}

}
}
}
4.TEST:
import java.util.Scanner;

public class TEST {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
System.out.println("please input an integer:");
int n=input.nextInt();
System.out.println("当n="+n+"时,所有排列如下:");

Expression e=new Expression();
e.pailie(n);
}
}

6.测试数据
please input an integer:
(1) 1
(2) 2
(3) 3
(4) 4

7.测试报告
1.当n=1：

2.当n=2：

3.当n=3：

4.当n=4：

8