Microsoft PowerPoint - Ch3 [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - Ch3 [兼容模式]"

纳接冉
5 years ago
Views:

1 Ch.3 栈和队列栈定义和运算栈仅在表的一端插删的线性表插入进 ( 入 ) 栈删除出 ( 退 ) 栈栈顶插删的一端栈底另一端结构特征 -- 后进先出修改原则 : 退栈者总是最近入栈者服务原则 : 后来者先服务 (LIFO 表 ) 例 : 入栈出栈 a n a 2 a 栈 Note: 后入栈者先出栈, 但不排除后者未进栈, 先入栈者先出栈 an,, a2, a1 基本运算 :1 判栈空 2 入栈 3 出栈 4 判栈满 5 读栈顶 6 置空栈顺序栈底相对固定可设在向量的任一端 Top 指针为下标类型 ( 整型量 ) #define StackSize 100 DataType data[stacksize]; int top; SeqStack; 顺序栈设栈底在向量低端 data[0], 则 : 入栈 :top+1 出栈 :top-1 栈空 :top<0 栈满 :top=stacksize-1 上溢 : 满时入栈下溢 : 空时出栈顺序栈 Note:top 指针不是指物理地址, 与 C 的指针变量含义不同可理解为相对地址, 是指示元素的所在位置 6 1

2 3.1.1 顺序栈顺序栈实现初始化 ( 置空栈 ) void InitStack(SeqStack *S) { S->top=-1; 判栈空 int StacEmpty(SeqStack *S) { // 亦可用非指针类型 return S->top<0; 判栈满 int StackFull (SeqStack *S) { return S->top==StackSize-1; 7 入栈 void Push(SeqStack *S, DataType x) { if ( StackFull(S) ) Error( overflow );// 上溢, 退出运行 S->data[++S->top]=x; // 指针先加 1, 后 x 入栈出栈 DataType Pop(SeqStack *S) { if ( StackEmpty(S) ) Error( UnderFlow ); // 下溢 return S->data[S->top--]; // 返回栈顶后指针减 1 读栈顶链栈只在表头操作, 故头指针即为 top, 无需头结点定义 typedef struct snode { DataType data; struct snode *next; StackNode; StackNode *top; LinkStack; 链栈动态分配结点, 无需考虑上溢链栈 void InitStack(LinkStack *S) { S->top=NULL; int StackEmpty (LinkStack *S) { return S->top==NULL; void Push(LinkStack *S, DataType x) { StackNode *p=(stacknode*) malloc (sizeof(stacknode)); p->data=x; p->next=s->top; s->top=p; 链栈 DataType Pop(LinkStack *S) { DataType x; StackNode *p=s->top; // 保存栈顶指针 if ( StackEmpty(S) ) Error ( underflow ); // 下溢 x=p->data; // 保存栈顶数据 S->top=p->next; // 将栈顶结点从链头摘下 free(p); // 释放原栈顶结点空间 return x; EX.3.6,3.17, 队列 1. 定义队列 : 运算受限的线性表, 一端插入 ( 队尾 ), 另一端删除 ( 队头 ) 结构特征先进先出, 先来先服务,FIFO 表例子 : 排队现象操作入队 ( 插入 ) 序列 : 出队 ( 删除 ) 序列 :

2. 顺序队列队列的顺序存储结构空队列 :front = rear; 初值为 0 入队 : 插入 rear 位置, 然后加 1 出队 : 删去 front 所指元素, 然后加 1 头指针 front 指向实际队头元素尾指针 rear 指向实际队尾元素的下一个位置上溢 : 队满时入队下溢 : 队空是出队 ( 不一定是错误, 可能是转移控制条件 ) 伪上溢 : 队非满但不能插入原因

0:i++; // i 为 front 或 rear 可用模运算简化 : i=(i+1)%queuesize; 循环队列实用顺序队列多为循环队列 15 边界问题队满和队空时,front=rear, 如何区分?

3 2. 顺序队列队列的顺序存储结构空队列 :front = rear; 初值为 0 入队 : 插入 rear 位置, 然后加 1 出队 : 删去 front 所指元素, 然后加 1 头指针 front 指向实际队头元素尾指针 rear 指向实际队尾元素的下一个位置上溢 : 队满时入队下溢 : 队空是出队 ( 不一定是错误, 可能是转移控制条件 ) 伪上溢 : 队非满但不能插入原因 :f,r 只增不减例如 : 入, 出, 入, 出, 尽管任一时刻, 队中最多只有 1 个元素, 但无论事先定义多大的空间, 均会产生指针越界怎样消除伪上溢? 重复利用已删除的结点空间, 将向量视为首尾相接的环这种用循环向量实现的队列称为循环队列 f,r 在循环意义下的加 1 动作 : 越界时, 令其指向下界 0 i = (i+1==queuesize)? 0:i++; // i 为 front 或 rear 可用模运算简化 : i=(i+1)%queuesize; 循环队列实用顺序队列多为循环队列 15 边界问题队满和队空时,front=rear, 如何区分? 解决方法 : 1 设一布尔量以示区分 2 留一个结点不用约定入队前, 测试尾指针 +1 ( 循环定义下 ) 是否等于头指针若相等则为满 3 使用 1 个计数器, 记录队列长度 ( 用此法 ) 定义 #define QueueSize 100 int front; int rear; int count; DataType data [QueueSize]; CirQueue; 16 操作实现置空队 void InitQueue (CirQueue *Q) { Q->front = Q->rear = 0; Q->count = 0; // 队空判队空 int QueueEmpty (CirQueue *Q) { return Q->count == 0; 判队满 int QueueFull (CirQueue *Q) { return Q->count ==QueueSize; 17 入队 void EnQueue (CirQueue *Q, DataType x) { if (QueueFull (Q) ) Error( overflow ); // 上溢 Q->count++; Q->data [Q->rear] = x; // 插入 Q->rear = (Q->rear+1)%QueueSize; // 尾指针加 1 出队 DataType DeQueue (CirQueue *Q) { if (QueueEmpty (Q) ) Error ( underflow ); // 下溢, 不一定是错 temp = Q->data[Q->front]; Q->count--; Q->front= (Q->front+1)%QueueSize; // 头指针加 1 return temp; 18 3

4 3. 链队列仅限于在表头和尾插删的单链表 typedef struct qnode{ DataType data; struct qnode *next; QNode; QNode *front; QNode *rear; LinkQueue; LinkQueue Q; a1 不带头节点 : an 19 void InitQueue (LinkQueue *Q) { Q->front = Q->rear = NULL; // 若有头结点则不同 int QEmpty (LinkQueue *Q) { // 无上溢, 故不判满队 return Q->front == NULL; // 头尾指针均为空, 有头结点时 f = r void EnQueue (LinkQueue *Q, DataType x) { QNode *p = (QNode *) malloc( sizeof(qnode) ); p->data = x; p->next = NULL; // 新结点作为新的队尾 if ( QEmpty(Q) ) // 若有头结点无需判此项 Q->front = Q->rear = p; // *p 插入空队 else { // 插入非空队尾, 有无头结点均要做此项 Q->rear->next = p; // *p 链到原尾结点之后 Q->rear = p; // 指向新尾 *p 链队列 DataType DeQueue (LinkQueue *Q) { if ( QEmpty(Q) ) Error ( underflow ); // 下溢 p = Q->front; // 指向队头 x = p->data; Q->front = p->next; // 队头摘下 if (Q->rear == p) // 原队中只有一个结点, 删去后队变空 Q->rear = NULL; free (p) ; return x; 3.3 栈和队列的应用 1. 数据转换问题 : 一非负十进制整数 N B 进制整数例 :28 10 = = = = 规律 : (3.1) 其中 b i 表示 B 进制数的第 i 位数字十进制数 N 可用位 B 进制数表示为 Ex 栈的应用如何确定 b j? 令, 则 (3.1) 式为 : 例如 : (3.2) 该式整除 B, 则余数为 b 0, 商为括号内的和式故 (3.2) 式可表达为 : N = ( N/B ) B + N%B // / 为整除算法思想 1 模除求余数 : N%B b 0 2 整除求商 :N/B, 令其为新 N, 重复 1 求 b 1, 反复至某 N 为 0 时结束上述过程依次求出的 B 进制各位为 ( 从低位至高位 ): b 0,b 1,, b j, 用栈保存, 退栈输出 b j,b j-1,, b 0 即为所求

5 实现 typedef int DataType; void MultiBaseOutput (int N, int B) { // N 为非负十进制整数, B 为基 int i; SeqStack S; // 顺序栈 S InitStack( &S ); // 置空栈 while (N) { // 从右向左产生 b i, i=0,1,, j Push( &S, N%B); // 将 b i 入栈 N=N/B; while(!stackempty(&s) ) { // 栈 S 非空 i = Pop(&S); printf( %d,i); 时间复杂度 :O(log B N ) 25 递归是一种强有力的数学工具, 可使问题的描述和求解变得简洁与清晰递归若一函数过程或数据结构定义的内部又直接或间接使用了定义本身, 则称它们是递归的, 或递归定义的 26 例 :Bakus-Naur Form (BNF) 巴科式范式早期定义 Algol 60 语法 1 直接递归 < 标识符 > ::= < 字母 > < 标识符 >< 字母 > < 标识符 >< 数字 > < 字母 > ::= a b y z < 数字 > ::= 递归算法设计 ( 分治法 ) 分解求解组合 step1: 将原问题分解为一个或多个规模更小, 但与问题特性类似的子问题 ( 递归步骤 ) // 解子问题为调用语句 step2: 确定一个或多个无须分解, 可直接求解的最小子问题 ( 终结条件 )// 归纳基础非终结符终结符可选分隔符由此定义的标识符是由字母打头的字母数字串 2 简接递归 < 表达式 > ::= < 项 > + < 项 > < 项 > - < 项 > < 项 > < 项 > ::= < 因子 > * < 因子 > < 因子 > / < 因子 > < 因子 > < 因子 > ::= (< 表达式 >) < 字母 > < 数字 > 合法的表达式 :A+5,B*C+D,(A+B*C)/D 27 例 1: // 递归终结条件 // 递归步骤 (n-1)! 的规模比 n! 小 1 28 int F (int n) { // 设 n 为非负整数 if (n==0) return 1; else return n*f(n-1) ; 至少有一个直接求解的最小子问题, 保证递归终止, 否则无限循环分解为一个子问题, 若 F(n) 是解 n!, 则 F(n-1) 可解 (n-1)! 29 有些问题表面上不是递归定义的, 但可通过分析, 抽象出递归的定义例 2: 写一个就地生成 n 个元素 a 1,a 2,,a n 全排列 (n!) 的算法, 要求算法终止时保持 a 1,a 2,,a n 原状解 : 设 A[0..n-1] 基类型为 char, 就地不允许使用 A 以外的数组 1 生成 a 1, a 2,, a n 全排列 n 个子问题求 n-1 个元素的全排列 + n th 个元素 1 st 子问题 a 1, a 2,, a n-1 a n // 2 nd 子问题 a 1,, a n-2, a n a n-1 //A[n-1] A[n] 3 rd 子问题 a 1,, a n, a n-1 a n-2 //A[n-2] A[n] n th 子问题 a n,a 2, a n-1 a 1 //A[1] A[n] 2 递归终结分支当 n=1 时, 一个元素全排列只有一种, 即为本身实际上无须进一步递归, 可直接打印输出 A 30 5

.n] 原状 //endfor //endif 时间 : 例 3:n 阶 Hanoi 塔问题将 X 上的圆盘移到 Z 上, 要求按同样次序排列, 且满足 : 1. 每次只能移动一片 2. 圆盘可插在 X,Y,Z 任一塔座上 3. 任一时刻大盘不能压在小盘上所以实验时,n 不能太大 31 32 1 分解设 n>1 原问题 : 将 n 片从 X 移到 Z,Y 为辅助塔, 可分解为 : I.

6 3 算法 : 以 A[0..7] 为例 void permute (char A[ ], int n) { // 外部调用时令 n=7 if (n==0) print (A); // 打印 A[0..n] else { Permute(A,n-1); // 求 A[0..n-1] 的全部排列 1 st 子问题不用交换 for (i=n-1; i>0; i--) { Swap(A[i], A[n]); // 交换 a i 和 a n 内容, 说明为引用 Permute(A,n-1); // 求 A[0..n-1] 全排列 Swap(A[i],A[n]); // 交换, 恢复 A[0..n] 原状 //endfor //endif 时间 : 例 3:n 阶 Hanoi 塔问题将 X 上的圆盘移到 Z 上, 要求按同样次序排列, 且满足 : 1. 每次只能移动一片 2. 圆盘可插在 X,Y,Z 任一塔座上 3. 任一时刻大盘不能压在小盘上所以实验时,n 不能太大分解设 n>1 原问题 : 将 n 片从 X 移到 Z,Y 为辅助塔, 可分解为 : I. 将上面 n-1 个盘从 X 移至 Y,Z 为辅助盘 II. 将 n th 片从 X 移至 Z III. 将 Y 上 n-1 个盘子移至 Z,X 为辅助盘 2 终结条件 n = 1 时, 直接将编号为 1 的盘子从 X 移到 Z void Hanoi (int n, char x, char y, char z ) { // n 个盘子从 X 移至 Z,Y 为辅助 if ( n==1 ) move(x,1,z); // 将 1 号盘子从 X 移至 Z, 打印 else { Hanoi (n-1,x,z,y); // 源 X, 辅 Z, 目 Y move (x,n,z); Hanoi (n-1,y,x,z); // 源 Y, 辅 X, 目 Z // 子问题特征属性与原 // 问题相同规模小 1, 参 // 数不同递归的内部实现 1 调用调用一个函数时, 系统将为调用者构造一个活动记录, 并将其压入栈的顶, 然后将程序控制权转移到被调用函数若被调用函数有局部变量, 则在栈顶也要为其分配空间, 形成一个活动结构实际上所有的递归或非递归函数都是这样实现的活动结构 : 局部变量活动记录 : 参数表的内容为实参返址为函数调用语句的下一指令的位置递归的内部实现 2 返回当被调用函数执行完毕时, 系统将活动结构退栈, 并根据退栈返回地址将程序控制权转移给调用者继续执行例 : F(4) 为例 Ret L1 void main(void) { int n; Ret L1: 赋值语句的地址 Ret L2: 计算乘法的地址 n = F(4); // 调用引起压栈为简单起见, 假设局部变量不入栈改写 : int F (int n) { Ret L2 int temp; if (n==0) return 1; // 返回语句引起退栈 else { // 调用 F(n-1) 引起入栈 temp = n*f(n-1); return temp; // 退栈递归的内部实现 * 执行返回指令 Ret L2: temp=1*1; // 从 F(0) 返回 0! = 1 是递归终结条件, 故执行 F(0) 引起返回 (return 1) 退栈, 返回到 F(1) 的 Ret L2 处, 继续执行 temp = 1*1; 按着执行 return temp 又引起退栈, 返回到 F(2) 的 Ret L2 处, 执行 temp = 2*1, 36 6

7 4. 递归算法的正确性初学者很难相信递归程序的正确性原因 : 一个函数尚未完成 ( 即对本函数的正确性还未确信 ) 时又调用了自身, 故对递归函数正确性缺乏信心例 : 非递归函数或过程假设 Q 正确的情况下, 证明了 P 正确, 则一旦证明了被调过程 Q 是正确的, 我们就对 P 的正确性深信不疑! 由于 P Q 各自独立, 独立于 P 来证明 Q 的正确性很容易, 这大概是对自己写非递归程序较有信心的缘故 4. 递归算法的正确性若 P 是递归过程, 则不可能独立于 P 来证明被调过程 ( 亦自身 ) 是否正确因此, 我们只能假设过程 P 内部所有递归的调用是正确的 ( 不考虑其内部实现细节 ), 才能由此证明 P 的正确性其理论依据是数学归纳法 : (1) 证明参数满足递归终结条件时函数或过程正确 ( 相当于归纳基础 ) (2) 假设过程函数内部的所有递归调用语句正确 ( 相当于归纳假设 ), 由此证明过程正确或函数是正确的 ( 相当于归纳步骤 ) Note: 函数内的递归调用语句的参数应比函数本身的参数更接近递归终结条件参数, 这样才能确保递归是可终止的上机题 : 调试跟踪 : 全排列和 Hanoi 塔队列的应用例 : 周末舞会, 男女各排成一队, 跳舞时, 依次从男女队的头上各出一人配成舞伴, 若两队人数不同, 较长的队中未配对者等下一轮舞曲 char name[20]; char sex; // M 男,F 女 Person; typedef person DataType; // 将队列定义中的数据类型改为 Person void DancePartners(Person dancer[ ], int num){ int i; Person P; CirQueue Mdancers, Fdancers; InitQueue(&Mdancers); // 男士队列 InitQueue(&Fdancers); 队列的应用 for( i=0; i<num; i++ ) {//num 个男女依其性别入队 P = dancer[ i ]; if (P.sex == M ) EnQueue (&Mdancers, P); // 入男队 else EnQueue (&Fdancers, P); // 入女队 printf ( The dancing partners are:\n\n ); while (!QueueEmpty(&Fdancers) &&!QueueEmpty(&Mdancers)) { // 男女队列均非空 P=DeQueue(&Fdancers); // 女士出队 printf( %s, P.name); // 女士姓名 P=DeQueue(&Mdancers); // 男士出队 printf( %s\n, P.name); 队列的应用 if (!QueueEmpty(&Fdancers)) { // 女队非空, 输出剩余人数及队头者名字 printf( \n There are %d women waiting for the next round.\n, Fdancers.count);// count 是队列属性, 长度 P=QueueFront(&Fdancers); // 取队头 printf ( %s will be the first to get a partner.\n, P.name); else{ // 男队类型处理时间复杂度 :O(n) 42 7

Microsoft PowerPoint - DS_Ch4_EN [兼容模式]

Microsoft PowerPoint - DS_Ch4_EN [兼容模式] Data Structure Ch.4 Recursion Dr. He Emil Huang School of Computer Science and Technology Soochow University 苏州大学计算机科学与技术学院网络工程系本章 ppt 与教材对应情况本章涉及所有内容涵盖了教材以下章节 Chapter 5 ( 递归,Recursion) Question: 递归与数据结构课程体系的关系?