第二次上机总结之运行时间

第二次上机总结之运行时间

第二次上机总结：

关于不同种方法的用时：我测试了下代码运行时间

均为试验8个元素的全排列的时间

递归实现：

#include

#include

using namespace std;

int n = 0;

void swap(int *a, int *b)

{

int m;

m = *a;

*a = *b;

*b = m;

}

void perm(int list[], int k, int m)

{

int i;

if(k > m)

{

for(i = 0; i <= m; i++)

printf("%d ", list[i]);

printf("\n");

n++;

}

else

{

for(i = k; i <= m; i++)

{

swap(&list[k], &list[i]); //在i=0时;i=1,2,……m

perm(list, k + 1, m); //k=0,1,……，m

swap(&list[k], &list[i]); //i=1,2,……，m

}

}

}

int main()

{

time_t begin,end;

begin=clock();

//code

printf("给定n个元素：");

int m;

scanf("%d",&m);

int list[100];

int i;

printf("输入元素：");

for(i=0;i

scanf("%d",&list[i]);

printf("输出%d的全排列:\n",m);

perm(list,0,m-1);

printf("total:%d\n", n);

end=clock();

cout<<"runtime: "<

}

字典序排序：

next_permutation：

用栈方法：此为同学写的用动态栈的方法，特此测试一下。

#include

#include

#include

using namespace std;

using namespace std;

typedef int ElemType;

#define NUM 30

typedef struct{

ElemType e[NUM];

}array;

array w,v; //用两个数组存储原数组及做一次变换后的数组

int n; //元素个数n

typedef struct node{

array data;

struct node *next;

}stack;

int push(stack *S,array x){

stack *p;

p=(stack *)malloc(sizeof(stack));

if(!p) return 0;

p->data=x;

p->next=S->next;

S->next=p;

return 1;

}

int pop(stack *S,array *e){

if(S->next==NULL) return 0;

stack *p;

p=S->next;

*e=p->data;

S->next=p->next;

free(p);

return 1;

}

int InitStack(stack **S){

*S=(stack *)malloc(sizeof(stack));

if(*S==NULL) return 0;

(*S)->next=NULL;

return 1;

}

int emptystack(stack *S){

if(S->next==NULL) return 1;

else return 0;

}

void list(stack *S){

stack *p;

p=S->next;

while(p!=NULL){

for(int i=0;i

cout<data.e[i]<<" ";

cout<

p=p->next;

}

}

void creat(){

int i;

cout<<"请输入元素个数：";

cin>>n;

cout<<"请输入元素：";

for(i=0;i

cin>>w.e[i];

}

}

void copy(array &b,array &c){

for(int i=0;i

c.e[i]=b.e[i];

}

}

void tran(array &b,int p,int q){ //做变换交换b[p]与b[q]

ElemType k;

k=b.e[p];

b.e[p]=b.e[q];

b.e[q]=k;

}

int s; //用s记录下最后使用的栈

stack *S[2]; //使用两个栈

stack p[2];

void qpl(){ //全排列算法

int i;

S[0]=&p[0];

InitStack(&S[0]);

S[1]=&p[1];

InitStack(&S[1]);

push(S[s],w);

for(i=1;i

copy(w,v);

tran(v,0,i);

push(S[s],v);

}

int t;

for(i=1;i

while(!emptystack(S[s])){

pop(S[s],&w);

t=(s==1)?0:1;

push(S[t],w);

for(int j=i+1;j

copy(w,v);

tran(v,i,j);

push(S[t],v);

}

}

s=t;

}

}

void print(){ //输出

cout<<"**********全排列结果**********"<

list(S[s]);

}

int main()

{

time_t begin,end;

begin=clock();

//code

creat();

qpl();

print();

end=clock();

cout<<"runtime: "<

}

由截图结果可看出：

四种方法的用时比较结果为：用栈方法（59.218s）<递归实现（44.031s）<字典序排序（37.093s）（20.531s）