第5章 堆栈.ppt

继续 入：581742 出： H1 H2 H3 3 6 9 2：次序不对，23，2?H1 2 4：次序不对，42，46，4?H2 4 7：次序不对，72，74，79?H3 7 * 继续 入：581 出： H1 H2 H3 3 6 9 2 4 7 1：次序对?出轨 1 H1：2?出轨，3?出轨 2 3 8：次序不对，?H1 8 H2：4?出轨 4 * 继续 入：5 出： H1 H2 H3 6 9 7 1 2 3 4 8 5：次序对?出轨 5 H2：6?出轨 6 H3：7?出轨 7 H1：8?出轨 8 H3：9?出轨，OK! 9 * 重排算法 缓冲轨后进先出，用堆栈保存车厢号 考虑在出轨顺序，必须栈底大，栈顶小 依次检查入轨车厢编号 如果≠出轨所需要的下一车厢，?缓冲轨 依次检查缓冲轨，若新来的栈顶，入栈 如果=出轨所需要的下一车厢，?出轨 缓冲轨中车厢可能满足出轨需要，检查缓冲轨栈顶车厢，如有可能，出栈，?出轨，不是一次，要反复做，直至栈中无满足出轨需要的车厢 * 重排程序 bool Railroad(int p[], int n, int k) {// k track rearrangement of car order p[1:n]. // Return true if successful, false if impossible. // Throw NoMem exception if inadequate space. // create stacks for holding tracks LinkedStackint *H; H = new LinkedStackint [k + 1]; int NowOut = 1; // next car to output int minH = n+1; // smallest car in a track int minS; // track with car minH k=? 为什么不是Stack？ * 重排程序（续） // rearrange cars for (int i = 1; i = n; i++) if (p[i] == NowOut) // send straight out { cout “Move car ” p[i] “ from input to output”; cout endl; NowOut++; while (minH == NowOut) { Output(minH, minS, H, k, n); NowOut++; } } * 重排程序（续） else {// put car p[i] in a holding track if (!Hold(p[i], minH, minS, H, k, n)) return false;} return true; } * Output：缓冲铁轨?出轨 void Output(int minH, int minS, LinkedStackint H[], int k, int n) {// Move from hold to output and update minH and minS. int c; // car index // delete smallest car minH from stack minS H[minS].Pop(c); cout Move car minH from holding track “ minS to output endl; * Output：缓冲铁轨?出轨 // find new minH and minS // by checking top of all stacks minH = n + 2; for (int i = 1; i = k; i++) if (!H[i].IsEmpty() (c = H[i].Top()) minH) { minH = c; minS = i;} } * Hold：入轨?缓冲铁轨 bool Hold(int c, int minH, int minS, LinkedStackint H[]