数据结构 实验报告-2

第一题 列车厢调动：

一、实验内容：

有三条平行的列车轨道（1、2、3）以及1-3和2-3两段连接轨道。现有一列车厢停在1号轨道上，请利用两条连接轨道以及3号轨道，将车厢按照要求的顺序转移到2号轨道。

二、实验目的：

掌握栈的基本操作，入栈和出栈，能够应用栈来解决问题；

三、程序清单：

▶

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 26
 
enum solution {
    one_two,
    three_two,
    one_three
};
 
typedef struct {
    char base[MAXSIZE];
    int top;
    int zhaisize;
}*zhai, ZHAI;
 
zhai initStack() {
    zhai s = (zhai)malloc(sizeof(ZHAI));
    s->top = 0;
    s->zhaisize = MAXSIZE;
    return s;
}
 
void push(zhai s, char e) {
    s->base[s->top++] = e;
}
 
char pop(zhai s) {
    char e = s->base[--s->top];
    return e;
}
 
char getTop(zhai s) {
    return s->base[s->top - 1];
}
 
int empty(zhai s) {
    if (s->top == 0) {
        return 1;
    }
    else {
        return 0;
    }
}
 
int main() {
    char a[MAXSIZE + 1];
    char b[MAXSIZE + 1];
    int mid[100];
    zhai s1 = initStack();
    zhai s2 = initStack();
    zhai s3 = initStack();
 
    scanf("%s", a);
    int len1 = strlen(a);
    for (int i = len1 - 1; i >= 0; i--) {
        push(s1, a[i]);
    }
     
    scanf("%s", b);
    int len2 = strlen(b);
    for (int i = len2 - 1; i >= 0; i--) {
        push(s2, b[i]);
    }
     
    int cnt = 0;
    int flag = 1;
    while (!empty(s2)) {
         
        if (!empty(s1) && getTop(s1) == getTop(s2)) {
            pop(s1);
            pop(s2);
            mid[cnt++] = one_two;
        }
         
        else if (!empty(s3) && getTop(s3) == getTop(s2)) {
            pop(s3);
            pop(s2);
            mid[cnt++] = three_two;
        }
         
        else if (empty(s1)) {
            flag = 0;
            break;
        }
         
        else {
            push(s3, pop(s1));
            mid[cnt++] = one_three;
        }
         
    }
    if (flag == 0) {
        printf("Are you kidding me?");
    }
    else {
        for (int i = 0; i < cnt; i++) {
            if (mid[i] == one_two) printf("1->2\n");
            if (mid[i] == three_two) printf("3->2\n");
            if (mid[i] == one_three) printf("1->3\n");
        }
    }
     
    return 0;
}

四、调试步骤：

1. 输入题中的测试数据；
2. 检查程序输出与预期输出的差距，分析错误在程序的哪个部分；
3. 更改程序，再次测试，直到程序输出符合预期；

第二题 银行业务队列简单模拟：

一、实验内容：

设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。

二、实验目的：

掌握栈的基本操作，入栈和出栈，能够应用栈来解决问题；

三、程序清单：

▶

Code

#include <stdio.h>
#include<string.h>
#include <stdlib.h>
 
struct Quene
{
    int node[1001];
    int size;
    int front;
    int rear;
};
typedef struct Quene qe;
qe A, B;
void gen()
{
    int all;
    int n;
    scanf("%d", &all);
    A.front = 0;
    A.rear = 0;
    A.size = 0;
 
    B.front = 0;
    B.rear = 0;
    B.size = 0;
    int i;
    for (i = 0; i < all; i++)
    {
        scanf("%d", &n);
        if (n % 2 == 0)
        {
            B.node[B.rear] = n;
            B.rear++;
            B.size++;
        }
        else
        {
            A.node[A.rear] = n;
            A.rear++;
            A.size++;
        }
    }
}
int top_a1 = 1, top_a2 = 1, top_b = 1;
int top;
qe Pop(qe q)
{
     
    if (q.size > 0)
    {
        top = q.node[q.front];
        q.size--;
        q.front++;
    }
    else
    {
        top = -1;
    }
 
    return q;
}
 
 
int main()
{
    int a1 = 1, a2 = 1, b = 1;
    int tag = 0;
    gen();
    while (a1 > 0 || a2 > 0 || b > 0)
    {
        A = Pop(A);
        a1 = top;
        if (top > 0)
        {
            if (tag)
            {
                printf(" ");
            }
            printf("%d", top);
            tag = 1;
        }
 
        A = Pop(A);
        a2 = top;
        if (top > 0)
        {
            if (tag)
            {
                printf(" ");
            }
            printf("%d", top);
            tag = 1;
        }
        B = Pop(B);
        b = top;
        if (top > 0)
        {
            if (tag)
            {
                printf(" ");
            }
            printf("%d", top);
            tag = 1;
        }
 
    }
    return 0;
}

四、调试步骤：

1. 输入题中的测试数据；
2. 检查程序输出与预期输出的差距，分析错误在程序的哪个部分；
3. 更改程序，再次测试，直到程序输出符合预期；