第4章+栈、队列和递归

1、数据结构数据结构C+实现实现缪淮扣缪淮扣 沈沈 俊俊 顾训穰顾训穰上海大学上海大学 计算机工程与科学学院计算机工程与科学学院20142014年年6 6月月第第4 4章章栈、队列和递归栈、队列和递归4.1 栈4.2 队 列 4.3 递 归 只可在表头位置插入和删除的线性结构不是一种数据结构，而是一种有效的算法设计方法 只可在表尾位置插入、在表头位置删除的线性结构 第第4 4章章 栈、队列和递归栈、队列和递归（stackstack）是限定仅在表尾一端进行插入或删除操作）是限定仅在表尾一端进行插入或删除操作的特殊线性表。的特殊线性表。对于栈来说对于栈来说, , 允许进行插入或删除操作的一端称为允许进

2、行插入或删除操作的一端称为（toptop）, ,而另一端称为而另一端称为（bottombottom）。）。不含元素栈称为不含元素栈称为向栈中插入一个新元素称为向栈中插入一个新元素称为或或从栈中删除一个元素称为从栈中删除一个元素称为或或。栈又称为栈又称为（Last In First OutLast In First Out，LIFOLIFO）的线）的线性表。性表。4.1 4.1 栈栈图图4.1 栈的结构示意图栈的结构示意图 ana2a1进栈出栈栈顶栈底进栈出栈(a) 栈的示意图(b) 铁路调序栈的表示栈的实例栈的实例 日常生活中的叠碗日常生活中的叠碗栈栈 结结 构构 示示 例例【例例】 很窄的死

3、胡同，每次只能容许一人进出很窄的死胡同，每次只能容许一人进出.【例例】 给枪的弹匣装子弹。给枪的弹匣装子弹。【例例】 桌上的一摞书，假定每次取书只取最上面的一桌上的一摞书，假定每次取书只取最上面的一本，放书必须放在最上面。本，放书必须放在最上面。1 1、初始化初始化2 2、求长度求长度3 3、取栈顶元素取栈顶元素4 4、入栈入栈5 5、出栈出栈6 6、判断栈是否为空栈判断栈是否为空栈7 7、清空栈清空栈栈栈的的基本操作基本操作1 1、栈的顺序存储、栈的顺序存储2 2、栈的链式存储、栈的链式存储3 3、栈的两种存储结构的比较、栈的两种存储结构的比较栈的存储结构栈的存储结构图4-2 栈的顺序存储结

4、构及其操作过程【例例】 假设顺序栈为假设顺序栈为(A,B,C,D,E,F)，栈中最多能存储，栈中最多能存储6个元个元素。请给出入栈和出栈时，其栈顶指针素。请给出入栈和出栈时，其栈顶指针top和栈的变化情况。和栈的变化情况。 (a)空栈toptoptoptoptopAFEDCBEDCACABBA (b)A入栈 (c)BCDEF入栈 (d)F出栈 (e)ED出栈templateclass SeqStack protected: int top;/ 栈顶指针栈顶指针 int maxSize;/ 栈最大容量栈最大容量 ElemType *elems;/ 元素存储空间元素存储空间栈的顺序存储结构栈的顺序

5、存储结构v 顺序栈的栈底在数组的底端，S-elems0表示栈底元素；v S-top=-1 表示栈空；v S-top=MAXSIZE-1 表示栈满；v 入栈时，首先将S-top加1，用以指示新的栈顶位置，再把元素放到这个位置上。v 出栈时，首先取出栈顶元素，再将S-top减1，使栈顶指针指示新的栈顶元素。v 栈满时入栈会“”，栈空时出栈会“”。顺序顺序栈栈S S的规定的规定public:SeqStack(int size = DEFAULT_SIZE);virtual SeqStack();int GetLength() const;bool IsEmpty() const;void Clear

6、();Status Push(const ElemType e);Status Top(ElemType &e) const;Status Pop(ElemType &e); ;栈的顺序存储结构栈的顺序存储结构templateSeqStack:SeqStack(int size)/ 操作结果：构造一个最大容量为操作结果：构造一个最大容量为size的空栈的空栈maxSize = size;if (elems != NULL) delete elems;elems = new ElemTypemaxSize;top = -1;顺序栈的构造函数顺序栈的构造函数size-1templateSeqSta

7、ck:SeqStack()/ 操作结果：销毁栈操作结果：销毁栈delete elems;顺序栈的析构函数顺序栈的析构函数sizen-1template int SeqStack:GetLength() const/ 操作结果：返回栈中元素个数操作结果：返回栈中元素个数return top+1;求顺序栈的长度求顺序栈的长度templatebool SeqStack:IsEmpty() const/ 操作结果：如栈为空，则返回操作结果：如栈为空，则返回true，否则返回，否则返回falsereturn top = -1;判断顺序栈是否为空判断顺序栈是否为空templatevoid SeqStack

8、:Clear()top = -1;清空顺序栈清空顺序栈templateStatus SeqStack:Push(const ElemType e)if (top = maxSize - 1) / 栈已满栈已满return OVER_FLOW;else elems+top = e; / 将元素将元素e追加到栈顶追加到栈顶 return SUCCESS; / 操作成功操作成功入栈入栈templateStatus SeqStack:Top(ElemType &e) constif (IsEmpty() / 栈空栈空return UNDER_FLOW;else e = elemstop;/ 用用e返回

9、栈顶元素返回栈顶元素return SUCCESS; / 栈非空栈非空,操作成功操作成功取栈顶元素取栈顶元素templateStatus SeqStack:Pop(ElemType &e)if (IsEmpty() / 栈空栈空return UNDER_FLOW;else e = elemstop-; / 用用e返回栈顶元素返回栈顶元素return SUCCESS; / 操作成功操作成功出栈出栈template void SqStack:Traverse(void (*Visit)(const ElemType &) constfor (int i = top; i =0 ; i-)(*Visi

10、t)(elemsi);遍历顺序栈遍历顺序栈栈的顺序存储结构是一种静态的存储结构，栈中元素的栈的顺序存储结构是一种静态的存储结构，栈中元素的多少受到多少受到MAXSIZEMAXSIZE的限制，空间太大会造成存储空间的浪费，的限制，空间太大会造成存储空间的浪费，为解决这个问题，同时建立多个顺序栈，以实现存储空间的为解决这个问题，同时建立多个顺序栈，以实现存储空间的共享，这样就可以相互调节余缺，既能高效地节约存储空间，共享，这样就可以相互调节余缺，既能高效地节约存储空间，又能降低上溢的发生概率。又能降低上溢的发生概率。为两个栈申请一个共享的一维数组空间，将两个栈的栈为两个栈申请一个共享的一维数组空间

11、，将两个栈的栈底分别放在一维数组的两端，分别是底分别放在一维数组的两端，分别是-1-1和和m m。 由于两个栈顶由于两个栈顶动态变化，这样可以形成互补，使得每个栈可用的最大空间动态变化，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。由此可见，两栈共享比两个栈分别与实际使用的需求有关。由此可见，两栈共享比两个栈分别申请申请M/2M/2的空间利用率高。的空间利用率高。两个顺序栈共享一个数组的存储空间两个顺序栈共享一个数组的存储空间图4.5 共享栈示意图栈空的条件：栈空的条件：top1 = -1，top2=m栈满的条件：栈满的条件：top1 + 1 =top2两个顺序栈共享一个数组

12、的存储空间两个顺序栈共享一个数组的存储空间u用不带头结点的单链表表示栈。用不带头结点的单链表表示栈。utoptop是栈顶指针，指向链栈的栈顶结点；是栈顶指针，指向链栈的栈顶结点；utop=NULL top=NULL 表示栈空；表示栈空；u若链栈非空，则若链栈非空，则toptop是指向链表的第一个结点是指向链表的第一个结点( (栈顶栈顶结点结点) )的指针。的指针。u栈顶结点是最后一个入栈的元素，而栈底结点是最栈顶结点是最后一个入栈的元素，而栈底结点是最先入栈的元素。先入栈的元素。栈的链式存储结构栈的链式存储结构图4.4 栈的链接存储结构及其操作过程链栈链栈存储的示例存储的示例#include

13、node.h/ 结点类结点类 templateclass LinkStack protected:Node *top;/ 栈顶指针栈顶指针链式栈的类链式栈的类模板模板定义定义链式栈的类链式栈的类模板模板定义定义public:LinkStack();virtual LinkStack();int GetLength() const;bool IsEmpty() const;void Clear();Status Push(const ElemType e);Status Top(ElemType &e) const;Status Pop(ElemType &e);templateLinkStac

14、k:LinkStack()top = NULL;链序栈的构造函数链序栈的构造函数templateLinkStack:LinkStack()Clear();链序栈的析构函数链序栈的析构函数template int LinkStack:GetLength() const/ 操作结果：返回栈中元素个数int count = 0;/ 计数器 Node *p; for (p = top; p != NULL; p = p-next)count+;/ 统计链栈中结点数return count;求求链式链式栈的长度栈的长度templatebool LinkStack:IsEmpty() constretur

15、n top = NULL;判断判断链式链式栈是否为空栈是否为空templatevoid LinkStack:Clear()/ 操作结果：清空栈Node *p; while (top != NULL) p = top;top = top-next;delete p;清空清空链式链式栈栈templateStatus LinkStack:Push(const ElemType item)Node *p = new Node(item, top);if (p = NULL) / 系统内存耗尽return OVER_FLOW;else / 操作成功top = p;return SUCCESS;入栈入栈t

16、emplateStatus LinkStack:Top(ElemType &e) constif(IsEmpty()/ 栈空return UNDER_FLOW;else e = top-data;/ 用e返回栈顶元素return SUCCESS;取栈顶元素取栈顶元素templateStatus LinkStack:Pop(ElemType &e)if (IsEmpty() / 栈空return UNDER_FLOW;else / 操作成功Node *p = top;/ 保留原栈顶e = top-data;/ 用e返回栈顶元素top = top-next;/ 修改栈顶delete p;/ 删除原

17、栈顶结点 return SUCCESS;出栈出栈template void LinkStack:Traverse(void (*Visit)(const ElemType &) const/ 从栈顶到栈底依次对栈的每个元素调用函数(*visit)访问 Node *p;for (p = top; p != NULL; p = p-next)(*Visit)(p-data); 遍历遍历链式链式栈栈u中缀表达式中缀表达式 (32 26) * 5 + 28 / 4 u后后缀表达式缀表达式（逆波兰式逆波兰式） 32 26 5 * 28 4 / + u前缀表达式为：前缀表达式为： + * 32 26 5

18、/ 28 4栈的应用表达式求值后后缀表达式缀表达式的计算的计算后后缀表达式缀表达式的的计算计算bool IsOperator(char ch)bool IsOperator(char ch) if (ch = # | ch = ( | ch = | ch = if (ch = # | ch = ( | ch = | ch = * * | ch = / | ch = / | | ch = + | ch= - | ch = )ch = + | ch= - | ch = ) return true; return true; else else return return false;false;

19、;后后缀表达式缀表达式的的计算计算void PostfixExpressionCalculationvoid PostfixExpressionCalculation() () LinkStack LinkStack opndopnd; ; char char chch; ; double double operand, first, secondoperand, first, second; ; cout cout cin.putback(ch); cin operandoperand; opnd.Push(operand); opnd.Push(operand); else else if

20、 (!IsOperator(ch) | ch = ( | ch =) if (!IsOperator(ch) | ch = ( | ch =) throw throw Error(Error(表达式中有非法符号表达式中有非法符号!); !); 后后缀表达式缀表达式的的计算计算 else else / ch/ ch为操作符为操作符 if if (opnd.Pop(second) = UNDER_FLOW) (opnd.Pop(second) = UNDER_FLOW) throw throw Error(Error(缺少操作数缺少操作数!);!); if if (opnd.Pop(first)

21、= UNDER_FLOW(opnd.Pop(first) = UNDER_FLOW) ) throw throw Error(Error(缺少操作数缺少操作数!);!); opnd.Push(Operate(first opnd.Push(Operate(first, ch, second, ch, second);); ch=GetChar(); ch=GetChar(); if (opnd.Pop(operand) = UNDER_FLOW if (opnd.Pop(operand) = UNDER_FLOW) ) throw Error(throw Error(缺少操作数缺少操作数!);

22、!); if if (!opnd.IsEmpty(!opnd.IsEmpty() () throw Error(throw Error(缺少操作符缺少操作符!);!); cout cout 表达式结果为：表达式结果为： operand endl operand (2)(2)(1)(1)(1)(2)(2)-(2)(2)(1)(1)(1)(2)(2)*(2)(2)(2)(2)(1)(2)(2)(2)(2)(2)(2)(1)(2)(2)(2)(2)(2)(2)(1)(2)(2)(1)(1)(1)(1)(1)(2)(2)(2)(2)(2)(-1) (2)(2)#(1)(1)(1)(1)(1)(1) (

23、-1) =(3)op1：栈顶符op2：扫描符 判断两个相邻算符的优先级判断两个相邻算符的优先级int OperPrior(char op1, char op2int OperPrior(char op1, char op2) ) int prior int prior; ; switch switch (op1) (op1) case + : case + : case - : if (op2 = + | op2 = - | op2 = ) | op2 = case - : if (op2 = + | op2 = - | op2 = ) | op2 = #) prior=2#) prior=2

24、; ; else else prior=1;prior=1; break break; ; case case * * : : case / : case / : case : if (op2 = | op2 = case : if (op2 = | op2 = () () prior=1;prior=1; else else prior=2;prior=2; break;break;判断两个相邻算符的优先级判断两个相邻算符的优先级 case ( : if (op2 = ) prior=0; case ( : if (op2 = ) prior=0; else if (op2 = #) pri

25、or=-1; else if (op2 = #) prior=-1; else prior=1; else prior=1; break; break; case ) : if (op2 = () prior=-1; case ) : if (op2 = () prior=-1; else prior=2; else prior=2; break; break; case # : if (op2 = ) prior=-1; case # : if (op2 = ) prior=-1; else if (op2 = #) prior=3; else if (op2 = #) prior=3; e

26、lse prior=1; else prior=1; break; break; return prior; return prior; 中缀式转换为后缀式的算法中缀式转换为后缀式的算法1、操作符栈初始化，“#”入栈，扫描表达式首字符ch。2、重复执行以下步骤，直到ch=“#”=栈顶操作符op。 情况一：ch是数字或“.”，则说明读入的是操作数。 情况二：ch不属于情况一，也不是操作符。 情况三：ch不属于上面二种情况，则说明ch是操作符。l 若ch是“(”，并且前一项是“)”或操作数。l 若op的优先级高于ch的优先级。l 若op与ch之间不存在优先关系。l 若op的优先级和ch的优先级相等

27、。直接输出操作数直接输出操作数。非法表达式非法表达式。中缀式转换为后缀式的算法中缀式转换为后缀式的算法情况三：l 若ch是“(”，并且前一项是“)”或操作数。非法表达式l 若op的优先级高于ch的优先级。 若operCount2:非法表达式, 否则op出栈输出,比较新栈顶与ch, 直到op优先级不高于ch。l 若op与ch之间不存在优先关系: 非法表达式。l 若op的优先级和ch的优先级相等，说明op为“(”，ch为“)”。op出栈，读入下一个字符。中缀式转换为后缀式的算法中缀式转换为后缀式的算法void InfixInToPostfix() LinkStack optr; char ch;

28、char priorChar; char op=#; double operand; int operandCount=0; optr.Push(#); priorChar=#; cout operand; cout operand ; operandCount+; priorChar=0; ch=GetChar(); else if (!IsOperator(ch) throw Error(表达式中有非法符号!); / 抛出异常 else / ch为操作符 if (ch = ( & (priorChar = 0 | priorChar = ) throw Error(前缺少操作符!); wh

29、ile (OperPrior(op, ch) = 2) if (operandCount 2) throw Error(缺少操作数!); operandCount-; optr.Pop(op); cout op ; if (optr.Top(op) = UNDER_FLOW) throw Error(缺少操作符!); 中缀式转换为后缀式的算法中缀式转换为后缀式的算法 switch (OperPrior(op, ch) case -1 : throw Error(括号不匹配!); case 0 : optr.Pop(op); if (optr.Top(op) = UNDER_FLOW) thro

30、w Error(缺少操作符!); priorChar=ch; ch=GetChar(); break; case 1 : optr.Push(ch); op=ch; priorChar=ch; ch=GetChar(); break; if (operandCount != 1) throw Error(缺少操作数!); cout rearfrontMAXSIZErearfront如何解决如何解决“假溢出假溢出”问题？问题？移动元素，使移动元素，使front=0front=0。效率低效率低循环队列循环队列同栈类似，顺序队列也有上溢和下溢现象同栈类似，顺序队列也有上溢和下溢现象： 当队空时，再进

31、行出队就会产生当队空时，再进行出队就会产生“下溢下溢”； 当队满时，再进行入队就会产生当队满时，再进行入队就会产生“上溢上溢”； 此外，顺序队列还存在此外，顺序队列还存在“假上溢假上溢”现象，即现象，即rear=MAXSIZErear=MAXSIZE并且并且front0front0时。时。 将整个数组空间变成一个首尾相接的圆环，即将整个数组空间变成一个首尾相接的圆环，即把把elems 0放放在在elems MAXSIZE-1之后，我们称这种数组为之后，我们称这种数组为。用。用循环数组表示的队列称为循环数组表示的队列称为。循环队列循环队列01234567frontrear空队列空队列012345

32、67A,B,C,D,E,F,G,H 进进队队frontCrearDEFG HAB图4-7 循环队列的队空和队满01234567front01234567front01234567frontrearAABCrearrear空队列空队列A 进进队队B, C 进进队队0123456701234567A 退退队队B 退退队队01234567D,E,F,G,H, I 进进队队frontBCrearAfrontBCrearfrontCrearDEFG HI队满的条件：队空的条件：(rear+1)%maxsize=frontrear=front循环队列循环队列队列的三种状态队列的三种状态( (设置一个空闲单

33、元不用设置一个空闲单元不用) )： 队满的条件队满的条件: : (rear+1)%MAXSIZE = front(rear+1)%MAXSIZE = front； 队空的条件队空的条件: rear = front: rear = front； 其它为一般情况（非空、非满）其它为一般情况（非空、非满）templateclass SeqQueue protected:int front, rear;/ 队头队尾指针 int maxSize; / 队列容量 ElemType *elems; / 元素存储空间循环队列循环队列的类的类模板模板定义定义public:SeqQueue(int size =

34、DEFAULT_SIZE);virtual SeqQueue();int GetLength() const;bool IsEmpty() const;void Clear();Status DelQueue(ElemType &e);Status GetHead(ElemType &e) constStatus EnQueue(const ElemType e); ;循环队列循环队列的类的类模板模板定义定义templateSeqQueue:SeqQueue(int size)maxSize = size; if (elems != NULL) delete elems; elems = ne

35、w ElemTypemaxSize;rear = front = 0; 循环循环队列的构造函数队列的构造函数size00template SeqQueue:SeqQueue()delete elems;循环循环队列的析构函数队列的析构函数templateint SeqQueue:GetLength() constreturn (rear - front + maxSize) % maxSize;求求循环队列的循环队列的长度长度templatebool SeqQueue:IsEmpty() const return rear = front;判断判断循环循环队列是否为队列是否为空空templat

36、evoid SeqQueue:Clear() rear = front = 0;清清空循环空循环队列队列templateStatus SeqQueue:EnQueue(const ElemType e)if (rear + 1) % maxSize = front)return OVER_FLOW;elseelemsrear = e;rear = (rear + 1) % maxSize;return SUCCESS;入队入队templateStatus SeqQueue:GetHead(ElemType &e) constif (!Empty() e = elemsfront;return

37、SUCCESS;elsereturn UNDER_FLOW;取取队头队头元素元素templateStatus SeqQueue:DelQueue(ElemType &e)if (!IsEmpty() e = elemsfront;front = (front + 1) % maxSize;return SUCCESS;else return UNDER_FLOW;出出队队template void SeqQueue:Traverse(void (*Visit)(const ElemType &) constfor (int i = front; i != rear; i = (i + 1) %

38、 maxSize)(*Visit)(elemsi);遍历遍历循环循环队列队列templateclass SeqQueue protected:int front, length;/ 队头队尾指针 int maxSize; / 队列容量 ElemType *elems; / 元素存储空间顺序顺序队列的另一种队列的另一种定义定义队列的链接存储结构是用一个单链表存放队列元素的。队列的链接存储结构称为。由于队列只允许在表尾进行插入操作、在表头进行删除操作，因此，链队需设置两个指针：队头指针front和队尾指针rear，分别指向单链表的第一个结点(表的头结点)和最后一个结点(队尾结点)。链链式式队列队列

39、图4.8 带头结点的链接队列的结构示意图templateclass LinkQueue protected:Node *front, *rear; / 队头队尾指指链式队列链式队列的类的类模板模板定义定义public:public:LinkQueue();virtual LinkQueue();int GetLength() const;bool IsEmpty() const;void Clear();Status DelQueue(ElemType &e); Status GetHead(ElemType &e) const;Status EnQueue(const ElemType e)

40、; ;链式队列链式队列的类的类模板模板定义定义templateLinkQueue:LinkQueue()rear = front = new Node;链链式式队列队列的构造的构造函数函数templateLinkQueue:LinkQueue()Clear(); delete front; 链式队列链式队列的的析构函数析构函数templateint LinkQueue:GetLength() constint count = 0; Node *p;for (p = front-next; p != NULL; p = p-next)count+; return count;求求链式队列链式队列

41、的长度的长度templatebool LinkQueue:IsEmpty() constreturn rear = front;判断判断链式队列链式队列是否为空是否为空templatevoid LinkQueue:Clear() Node *p = front-next;while (p != NULL)front-next = p-next;delete p; p = front-next;rear = front;清空清空链式队列链式队列templateStatus LinkQueue:EnQueue(const ElemType e)Node *p; p = new Node(e); i

42、f (p) rear-next = p;rear = rear-next; return SUCCESS; else return OVER_FLOW; 入队入队templateStatus LinkQueue:GetHead(ElemType &e) constif (!IsEmpty() e = front-next-data; return SUCCESS;elsereturn UNDER_FLOW;取队头元素取队头元素templateStatus LinkQueue:DelQueue(ElemType &e)if (!IsEmpty() Node *p = front-next; e

43、= p-data;front-next = p-next; if (rear = p)rear = front; delete p; return SUCCESS;else return UNDER_FLOW;出队出队template void LinkQueue:Traverse(void (*Visit)(const ElemType &) const Node *p; for (p = front-next; p != NULL; p = p-next)(*Visit)(p-data);遍历遍历链链式式队列队列templateclass LinkQueue protected:Node

44、*front, *rear; / 队头队尾指指链式队列的变化链式队列的变化1 1templateclass LinkQueue protected:Node *rear; / 队尾指指链式队列的变化链式队列的变化2 2车厢调度车厢调度一个由一个由2 2条平行铁轨组成铁路调度系统条平行铁轨组成铁路调度系统下下图所示。其中辅助铁轨图所示。其中辅助铁轨用于对车厢次序进行调整，它在主铁轨中间，把主铁轨分成左、用于对车厢次序进行调整，它在主铁轨中间，把主铁轨分成左、右两部分。主铁轨左边的车厢可以直接开到主铁轨右边；也可以右两部分。主铁轨左边的车厢可以直接开到主铁轨右边；也可以从主铁轨左边进入辅助铁轨；辅

45、助铁轨上的车厢只可以进入主铁从主铁轨左边进入辅助铁轨；辅助铁轨上的车厢只可以进入主铁轨右边轨右边。队列的应用队列的应用车厢调度车厢调度现在现在有有n n节火车车厢，编号为节火车车厢，编号为1 1、2 2、n n，在主铁轨的左边依次，在主铁轨的左边依次排列，要求通过这个调度系统，在主铁轨的右按规定的编号次序排列，要求通过这个调度系统，在主铁轨的右按规定的编号次序出站（例如：有出站（例如：有5 5节车厢以节车厢以1 1、2 2、3 3、4 4、5 5的顺序依次进入，要求的顺序依次进入，要求以以3 3、4 4、1 1、5 5、2 2的顺序出站）。的顺序出站）。队列的应用队列的应用1 1数据结构选择数

46、据结构选择由于由于n n节车厢在主铁轨左边按节车厢在主铁轨左边按1 1、2 2、n n的顺序排列，所以可以的顺序排列，所以可以简单的用一个计数器表示；简单的用一个计数器表示；n n节车厢在主铁轨右边的出站顺序可节车厢在主铁轨右边的出站顺序可以用一个线性表表示，也可以依次输入，在此通过循环依次从输以用一个线性表表示，也可以依次输入，在此通过循环依次从输入流获得。在这个调度系统中主要考虑辅轨道的实现。由于辅轨入流获得。在这个调度系统中主要考虑辅轨道的实现。由于辅轨道具有道具有FIFOFIFO特征，所以可以用一个队列进行模拟。特征，所以可以用一个队列进行模拟。队列的应用队列的应用2 2算法思想算法思

47、想设置一个主循环按车厢在主轨道右边的出站顺序依次读入设置一个主循环按车厢在主轨道右边的出站顺序依次读入当前要出站的车厢号当前要出站的车厢号d d，对当前出站的车厢号，对当前出站的车厢号d d进行执行如进行执行如下步骤下步骤：队列的应用队列的应用int main(void) LinkQueue qa; int n, x, d, No; cout n; No = 1; cout 输入 n 节车厢的出站顺序：; for (int i = 1; i d; if (qa.GetHead(x) = SUCCESS & x = d) cout 第 x 号车厢从辅轨道进入主轨道右边. endl; qa.Del

48、Queue(x); 车厢调度车厢调度车厢调度车厢调度else if (No = d) while (No = n & No d) cout 第 No 号从主轨道左边进入辅轨道. endl; qa.EnQueue(No+); if (No = d) cout 第 No 号从主轨道左边进入主轨道右边. endl; No+; else break;if (qa.IsEmpty() cout 调度完成. endl;else cout “调度无法完成.” 0 n=0 n=0是递归终止条件，n0时实现递归调用。单链表的递归定义：(1) 单个结点，其指针域next为NULL，是一个单链表；(2) 一个结点，

49、其指针域next指向一个单链表单链表，整个仍是一个单链表。 递归函数定义如下：float fact(int n ) if (n0) printf(输入数据错误!); else if n=0 then return(1.0); else return(n*fact(n-1)； main ( ) float y= fact(3); printf(nt输出3的阶乘:%d, y);调用递归函数的主程序：问题的解法是递归的问题的解法是递归的【例例】汉诺塔问题汉诺塔问题 设有3根标号为A、B、C的针，在A针上穿有n个盘子，一个比一个小。要求把A针上的盘子借助B针全部移到C针上。移动规则：（1）一次只能移动

50、一个盘子；（2）移动过程中大盘子不能放在小盘子上面。问题的解法是递归的若n = 1，则将盘子直接从A针移到C针。否则：Setp1 用C针过渡，将A针上的(n-1)个盘子移到B针上；Step2 将A针上最后一个盘子直接移到C针上；Step3 用A针做过渡，将B针上的(n-1)个盘子移到C针上。图4-14 汉诺塔问题的求解 # include void Hanoi (int n, char A, char B, char C) /把n 个盘子从A针借助B针移到C针上 if (n = 1 ) /递归出口，一个盘子直接移动 coutMoveAtoCendl; else Hanoi (n-1, A, C

51、, B); /将上面n-1个盘子移到B针上 coutMoveAtoCendl; /最后一个移到C针 Hanoi (n-1, B,A,C); /将B针上的n-1个盘子移到C针上 汉诺塔问题的求解汉诺塔问题的求解# include # include iostream.hvoid Hanoi (int n, char A, char B, char C) void Hanoi (int n, char A, char B, char C) / /把把n n 个盘子从个盘子从A A针借助针借助B B针移到针移到C C针上针上 if if (n = 1 ) /(n = 1 ) /递归出口，一个盘子直接

52、移动递归出口，一个盘子直接移动 cout coutMoveAtoCendl;MoveAtoCendl; else else Hanoi Hanoi (n-1, A, C, B); (n-1, A, C, B); cout coutMoveAtoCendlMoveAtoCendl; ; Hanoi Hanoi (n-1, B, A, C(n-1, B, A, C); ); 递归过程与递归工作栈递归过程与递归工作栈一般情况，对一个非递归函数的调用，在函数调用前要保存以下一般情况，对一个非递归函数的调用，在函数调用前要保存以下三方面的信息：三方面的信息：（1 1）返回地址。）返回地址。（2 2）本函

53、数调用时，与形参结合的实参值。包括函数名和函数）本函数调用时，与形参结合的实参值。包括函数名和函数参数。参数。（3 3）本函数的局部变量值。）本函数的局部变量值。时当时当0n)!1n(n0n1!nfact(3)递归调用流程变化示意图 递归调用变化情况示意图递归调用变化情况示意图 递归调用递归调用调用返回调用返回递归过程与递归工作栈递归过程与递归工作栈时当时当0n)!1n(n0n1!n递归过程与递归工作栈递归过程与递归工作栈fact: 函数名函数名n: 参数参数x, y: 局部变量局部变量 *：值未知：值未知消除递归消除递归递归的优缺点：u分而治之(复杂问题分解为简单问题来求解)u描述自然、易理解u时间效率比较差 用循环结构来替代递归用栈来模拟系统运行时的栈尾递归和单向递归的消除是指在递归算法的函数中，递归调用语句只有一个，而且是处在函数的最后。 是指递归函数中虽然有不止一个的递归调用语句，但各递归调用语句的参数只和主调用函数有关，相互之间参数无关，并且这些递归调用语句都处在算法的最后。 用循环结构来替代递归尾递归的消除尾递归的消除float f(int n ) if (n0) printf(输入数据错误输入数据错误!); else if n=0 then return(1.0) ; else return(n*f(