数据结构与算法(3)

Status ClearStack(SqStack *S)//栈的清空操作 {S->top=S->base; return OK; }

Status StackEmpty(SqStack S) {if(S.top==S.base)return TRUE; else

return FALSE; }

int StackLength(SqStack S) //计算堆栈大小 {int i; SElemType *p; i=0; p=S.top;

while(p!=S.base) {p++; i++;} return i; }

SElemType GetTop(SqStack S) return *(S.top-1); }

Status Push(SqStack *S,SElemType e) //将元素e压栈 {if(S->top - S->base>=S->stacksize)

{S->base=(SElemType *)realloc(S->base,(S->stacksize + STACKINCREMENT)*sizeof(SElemType)); if(!S->base)exit(OVERFLOW); S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT; }

*(S->top++)=e; return OK; }

Status Pop(SqStack *S,SElemType *e) //出栈操作，使用变量e接收出栈元素 {if(S->top==S->base)return ERROR; *e=*(--(S->top)); return OK; }

Status StackTraverse(SqStack S,Status (*visit)(SElemType *e))

//堆栈的遍历，其中visit函数需自行定义

{while (S.top>S.base) visit(--S.top); return OK; }

//取得栈顶元素

{if(S.top==S.base) return ERROR;

//判断栈是否为空

11

算法实验题3.1 车皮编序问题

? 问题描述：

在一个列车调度站中，1条轨道连接到1条侧轨处，形成一个铁路转轨栈。编号为1，2??，n的n个车皮从左侧入口依次进入转轨栈，由调度室安排车皮进出栈次序，并对车皮按其出栈次序重新编序a1，a2，??，an。

? 实验任务：

给定正整数n，计算左边轨道车皮编号依次为1，2，??，n时，右边轨道最多可以得到多少个不同的车皮编序方案。

? 数据输入：

由文件input.txt给出输入数据。第一行有1个正整数n，表示有n个车皮。 ? 结果输出：

将计算出的所有不同编序方案，以及不同的编序方案数输出到文件output.txt。文件的每行时一个编序方案，最后一行是编序方案数。

源程序如下： 1、 车皮编序.cpp

// 车皮编序问题.cpp : Defines the entry point for the console application. //

#include \typedef int SElemType; #include \#include \输入输出.h\//#include #include

void initer(int A[],int n)//初始化A { int i;

for(i=0;i

A[2*n-i-1]=1; }}

void adder(int A[],int n)//进位 { int i=n; if(n>=1) { A[i]++; if(A[i]==2) { A[i]%=2; adder(A,n-1); } }}

bool real(int A[],int n)//判断是否符合条件 { int i,count1=0,count2=0; for(i=0;i<2*n;i++) { if(A[i]==0) count1++; else

12

count2++; if(count2>count1) return false; }

if(count1==count2) return true; return false; }

bool breakdown(int A[],int n)//退出 { int i,j = 0;

for(i=0;i<2*n;i+=2)

{ if(A[i]==0&&A[i+1]==1) j++; }

if(j == n) return true; else return false; }

void main()

{ int n,i,e,k,t,count=0; int A[SIZE],out[SIZE]={0}; SqStack *S; n=load(); initer(A,n); InitStack(&S); t=0;

for(i=0;i<2*n;i++) { k=i+1;

if(A[i]==0) Push(S,k); else

{ Pop(S,&e); printf(\ out[t]=e; t++; } } printf(\ count++; save(out); while(n!=1)

{ adder(A,2*n-2); if(real(A,n)) { k=1; t=0;

for(i=0;i<2*n;i++) { if(A[i]==0)

13

{ Push(S,k); k++; } else

{ Pop(S,&e); printf(\ out[t]=e; t++; } } printf(\ count++; save(out); }

if(breakdown(A,n)) break; }

printf(\共有 %d 种情况\save(count); getchar();}

2、 输入输出.h #include #define SIZE 20 int load()

{ FILE *fp; int i; fp=fopen(\ fscanf(fp,\ fclose(fp); return i; }

void save(int m[]) { FILE *fp; int i; if((fp=fopen(\ { printf(\ return; } for(i=0;m[i]!=0;i++) fprintf(fp,\ fprintf(fp,\ fclose(fp); }

void save(int n) { FILE *fp; int i; if((fp=fopen(\

14

{ printf(\ return; }

fprintf(fp,\ fprintf(fp,\ fclose(fp);

}

3、 Input.txt

5 4、 Output.txt

5 4 3 2 1 4 5 3 2 1 4 3 5 2 1 4 3 2 5 1 4 3 2 1 5 3 5 4 2 1 3 4 5 2 1 3 4 2 5 1 3 4 2 1 5 3 2 5 4 1 3 2 4 5 1 3 2 4 1 5 3 2 1 5 4 3 2 1 4 5 2 5 4 3 1 2 4 5 3 1 2 4 3 5 1 2 4 3 1 5 2 3 5 4 1 2 3 4 5 1 2 3 4 1 5 2 3 1 5 4 2 3 1 4 5 2 1 5 4 3 2 1 4 5 3 2 1 4 3 5 2 1 3 5 4 2 1 3 4 5 1 5 4 3 2 1 4 5 3 2 1 4 3 5 2 1 4 3 2 5 1 3 5 4 2 1 3 4 5 2

15

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构与算法(3)在线全文阅读。