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

数据结构习题练习

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

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

  • Pn(x) =
    • 1, n = 0
    • 2x, n= 1
    • 2xPn-1(x) – 2(n-1)Pn-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;
}

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注