数据结构与算法(4)

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

算法实验题3.2 单柱汉诺塔问题

? 问题描述：

在一个塔座上有一叠大小不等的n个圆盘，各圆盘从小到大编号为1，2??，n。初始时，这些圆盘自下而上散乱地叠在一起。现要求按照以下的翻转规则，经若干次翻转，将塔座上的这一叠圆盘排好序，即按照自底向上，从大到小的顺序叠置。

翻转规则：每次可以将最顶上的若干圆盘翻转，即按其相反的次序叠置。 ? 实验任务：

对于给定的大小不等的n个圆盘的初始状态，用翻转运算将n个圆盘排序。 ? 数据输入：

由文件input.txt给出输入数据。第一行是给定的圆盘自顶向下的初始状态。 ? 结果输出：

将排序所用的翻转运算依次输出到文件output.txt。输出翻转运算flip(i)时，只要输出数字i即可，相邻数字用空格分隔。

源程序如下：

1、 单柱汉诺塔.cpp #include\#include #include #include\输入输出.h\typedef int SElemType; #include\ //加载堆栈操作的头文件 #define SIZE 10 int len,count=0; SqStack *S;

void display(int a[]) //打印每次排序后的序列情况 { for(int t=0;t

void Flip(int n,int A[]) //利用栈将若干圆盘翻转，使较大者在下 { int i; printf(\翻转 H[%d] 以前的圆盘: \ for(i=0;i<=n;i++) Push(S,A[i]); for(i=0;i<=n;i++) Pop(S,&A[i]); display(A); save(len-n+1);

16

count++; }

void main()

{ int H[SIZE]; int i,j,max,k; InitStack(&S); printf(\汉诺塔原始状态：\ len=load(H); printf(\翻转过程如下：\\n\ for(j=len-1;j>0;j--) { max=H[0];k=0; for(i=1;i<=j;i++) //查找最大的圆盘 { if(max

//如果圆盘在中间区域，先将其翻转至最上方，再进行所有圆盘翻转，将其翻转至最下方

} printf(\一共进行了%d次翻转\\n\ DestroyStack(S); getchar(); }

2、 输入输出.h #include int load(int a[]) { FILE *fp; int i,n; fp=fopen(\ fscanf(fp,\ for(i=0;i

17

}

{ printf(\ return; }

fprintf(fp,\fclose(fp);

3、 Input.txt

6

8 4 6 7 5 2 4、 Output.txt

2 5 3 6 4 5 6

算法实验题3.3 多栈模拟问题

? 问题描述：

设当前系统中有多个栈在工作，多栈模拟问题要求模拟当前系统中各栈的工作状态。 ? 实验任务：

对于给定的栈操作，模拟系统中各栈的工作状态。 ? 数据输入：

由文件input.txt给出输入数据。第1行是正整数n，表示有n个栈操作。接下来的n行，每行给出一个栈操作指令。指令“PUSH A B”表示将正整数B加入到编号为A的栈顶，指令“POP A”表示输出编号为A的栈顶元素。

? 结果输出：

将输入数据中POP指令的输出结果依次输出到文件output.txt。当编号为A的栈为空时，栈操作指令“POP A”输出0。

源程序如下： 1、 多栈模拟.cpp

// 多线模拟.cpp : 定义控制台应用程序的入口点。 //

#include \#include \#include \#include \输入输出.h\#include \typedef struct list {int id; int data;

struct list * next; }Node;

//定义工作链表 typedef Node * link; link head,tail=NULL; int count,L=0;

void Insert(int m,int n)

18

{ link ptr,q; if(head==NULL)

{ head=(link)malloc(sizeof(Node)); head->next=NULL; head->id=m; head->data=n; } else

{ ptr=head; q=(link)malloc(sizeof(Node)); q->id=m; q->data=n; q->next=ptr; head=q;

}}//通过插入结点建立链表 int delete_node(int n) { link q,ptr=head; if(head->id==n)

{ printf(\堆栈ID：%d 弹出 值：%d\\n\ head=head->next; return ptr->data; free(ptr);

}//如果待出栈结点是第一个结点，将头指针后移 else

{ while((ptr->id!=n)&&ptr->next!=NULL) { q=ptr; ptr=ptr->next; if(ptr->id==n) { printf(\堆栈ID：%d 弹出 值：%d\\n\ q->next=ptr->next; return ptr->data; free(ptr); } }}

return 0;

}//如果待出栈的结点位于链表中间，查找之，找到后将其删除 void display() { link p=head;

printf(\当前堆栈工作状态为：\\n\ while(p)

{ printf(\堆栈ID：%d,值：%d\\n\ p=p->next; }}

//打印当前堆栈工作状态

19

void main() { FILE *fp; char a[SIZE]; int out[SIZE]; int i=0,k,num;

fp=fopen(\ fscanf(fp,\

printf(\系统中一共有%d个栈在工作\\n\while(!feof(fp)) { fscanf(fp,\ if(strcmp(a,\ { printf(\ fscanf(fp,\ Insert(k,num); display(); }

if(strcmp(a,\ { fscanf(fp,\ printf(\ i=delete_node(k); save(i); display();

}}//按行读取输入文件，通过字符串比较确定堆栈操作，调用相应函数 fclose(fp); getchar(); }

2、 输入输出.h

#include #define SIZE 50 void save(int m) { FILE *fp;

if((fp=fopen(\ { printf(\ return; }

fprintf(fp,\ fclose(fp); } 3、 Input.txt

7

push 1 100 push 1 200 push 2 300 push 3 400

20

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