数据结构习题练习（六）-栈与队列两题(C)

数据结构习题练习

这篇虽然少，但至少栈与队列都囊括了。

以栈实现递归函数的非递归计算

• P_n(x) =
  • 1, n = 0
  • 2x, n= 1
  • 2xP_n-1(x) - 2(n-1)P_n-2(x), n>1
• 这里的栈用来存放每次计算中n的值。

int getPn(int x, int n) {
    if (n == 0) return 1;
    else if (n == 1) return 2 * x;
    typedef struct stack {
        int* data;
        int top;
    }stack;
    stack s;
    s.data = malloc(sizeof(int) * (n + 1));
    s.top = 0;
    int pos, pn1, pn2;
    pn1 = 2 * x;
    pn2 = 1;
    for (pos = n; pos > 1; pos--) {
        s.data[s.top] = pos;
        s.top += 1;
    }
    while (s.top > 0) {
        s.top -= 1;
        //printf("2 * %d * %d - 2 * (%d - 1) * %d\n", x, pn1, s.data[s.top], pn2);
        s.data[s.top] = 2 * x * pn1 - 2 * (s.data[s.top] - 1) * pn2;
        pn2 = pn1;
        pn1 = s.data[s.top];
    }
    return s.data[s.top];
}

渡口管理模拟-船能上10辆车，同类车先来先上，客车优先货车，每上4辆客车可上1辆货车，客车不足4辆可上货车。

//测试主函数
int main(){
    int pos;
    int vehicle[] = { 11, 21, 31, 41, 51, 61, 12, 22, 32, 71, 81, 91 };
    int vehicle2[] = { 11, 21, 31, 41, 51, 61, 12, 22, 32, 42, 52, 62 };
    int vehicle3[] = { 11, 21, 31, 41, 51 };
    int vehicle4[] = { 12, 22, 32, 42, 11 };
    // int* orderInShip = ferrySimulation(vehicle1, 12);
    // int* orderInShip = ferrySimulation(vehicle2, 12);
    //int* orderInShip = ferrySimulation(vehicle3, 5);
    int* orderInShip = ferrySimulation(vehicle4, 5);
    for (pos = 1; pos < orderInShip[0]; pos++) {
        printf("%d ", orderInShip[pos]);
    }
    system("PAUSE");
    return 0;
}

int* ferrySimulation(int* vehicleOrder, int vehicleNum) {
    //vehicleOrder中的元素表示车牌号，客车尾号为1，货车尾号为2，vehicleNum表车辆数目。
    //返回orderInShip数组，[0]存放车辆数目，[1~10]存放车牌号。
    typedef struct queue {
        int* order;
        int front;
        int rear;
    }queue;
    queue car, truck;
    car.order = malloc(sizeof(int) * vehicleNum);
    car.front = car.rear = 0;
    truck.order = malloc(sizeof(int) * vehicleNum);
    truck.front = truck.rear = 0;
    int pos, pos2;
    int* orderInShip = malloc(sizeof(int) * 11);
    for (pos = 0; pos < vehicleNum; pos++) {
        if (vehicleOrder[pos] % 10 == 1) {
            car.order[car.rear] = vehicleOrder[pos];
            car.rear += 1;
        }
        else if (vehicleOrder[pos] % 10 == 2) {
            truck.order[truck.rear] = vehicleOrder[pos];
            truck.rear += 1;
        }
    }
    for (pos = 1; pos < 11;) {
        for (pos2 = 0; pos2 < 4 && pos < 11; pos2++) {
            if (car.front == car.rear) break;
            orderInShip[pos] = car.order[car.front];
            car.front += 1;
            pos++;
        }
        if (truck.front == truck.rear && car.front == car.rear) break;
        if (truck.front == truck.rear) continue;
        orderInShip[pos] = truck.order[truck.front];
        truck.front += 1;
        pos++;
    }
    orderInShip[0] = pos;
    return orderInShip;
}