算法与数据结构讲义第3章新1.ppt

3.1.1栈的定义 栈（stack）是限定在表的同一端进行插入或删除操作的线性表。 进行插入或删除操作的一端称为栈顶(top)，另一端称为栈底(bottom)。 当表中没有元素时称为空栈 3.1.1栈的定义 例： 火车调度，如进栈的车厢序列为1、2、3,则可能的出栈序列有哪些？ 若进栈序列123456,能否得到435612和135426? 栈一个最重要的应用就是实现函数的递归调用. 3.4 队列 3.4 队列 3.4 队列 3.4 队列 3.4 队列 3.4 队列 2．递归设计 1）将问题用递归的方式描述（定义） 2）根据问题的递归描述（定义）编写递归算法 ?问题的递归描述（定义）包括两项： 基本项（终止项）：描述递归终止时问题的求解； 递归项：将问题分解为与原问题性质相同，但规模较小的问题； 例 n!的递归定义 基本项： n!=1 当 n=0 递归项： n!=n (n-1)!? 当 n 0 用(n-1)!定义n! 我们看一下n=3 阶乘函数fact(n)的执行过程 Main( ) { int n=3,y; L y= fact(n); } 调用 调用 调用 int fact (n) { If（n=1） return（1）； Else L1 return（n*fact (n-1)）； } n=3 int fact (int n) { If（n=1） return（1）； Else L2 return（n*fact (n-1)）； } n=2 int fact (int n) { If（n=1） return（1）； Else L3 return（n*fact (n-1)）； } n=1 L 3 L1 1 L1 2 返 回 1 返回2 返 回 6 1 n*fact (n-1) n*fact (n-1) fact(n) 返回地址 实参n 注意递归调用中 栈的变化 3 栈与递归的执行过程 3.4.1 队列的定义 一 什么是队列 队列是限定仅能在表头进行删除，表尾进行插入的线性表 （a1, a2, ... , ai -1, ai , ai+1, …, an ） 插入 删除 3.4.1 队列的定义 一 什么是队列 a1 a2 a3 an 入队列 队头 队尾 队 列 的 示 意 图 队列的特点 先进先出 3.4.1 队列的定义 二 队列的基本操作 1）初始化操作,InitQueue(Q); 2）判空操作,QueueEmpty(Q); 3）取队头元素操作,getHead(Q); 4）入队操作,EnQueue(Q,e) ; 5）出队操作,DeQueue(Q); 3.4.2 链队列 typedef struct QNode{ ElemType data; struct QNode *next; }QNode,*QueuePtr; ; 图3.10 链队列示意图 Q.front ∧ 　 Q.rear typedef struct { // 链队列类型 QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针 } LinkQueue; a1 ∧ an … Q.front Q.rear Q.front Q.rear ∧ 空队列 Status InitQueue (LinkQueue Q) { // 构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit (OVERFLOW); //存储分配失败 Q.front-next = NULL; return OK; } Status EnQueue (LinkQueue Q, QElemType e) { // 插入元素e为Q的新的队尾元素 p = (QueuePtr) malloc (sizeof (QNode));