数据结构教案第三章.docx
- 文档编号:12824684
- 上传时间:2023-06-08
- 格式:DOCX
- 页数:12
- 大小:19.84KB
数据结构教案第三章.docx
《数据结构教案第三章.docx》由会员分享,可在线阅读,更多相关《数据结构教案第三章.docx(12页珍藏版)》请在冰点文库上搜索。
数据结构教案第三章
课程名称
数据结构
教学对象
新华软工
教材
数据结构(C语言)
授课内容
第三章栈和队列
课时
3
教学目的
与要求
本章主要介绍栈和队列的定义,它们的特点,算法实现
重点、难点
重点:
栈和队列的定义和特性、它们的基本操作、存储结构
难点:
队列的顺序存储结构
课型
电脑+理论
教学方法
投影、讨论、板书
教学过程
设计
(包括讲授知识、演示内容及案例、提问及学生演示内容)
任务一、栈
前言:
(用时15分钟)
从数据结构角度看,栈和队列也是线性表,其特殊性在于栈和队列的基本操作是线性表的子集,它们是操作受限的线性表,即可称限定性的数据结构
一、什么是栈(用时35分钟)
栈是限定仅能在表尾一端进行插入、删除操作的线性表
栈的特点:
后进先出
第一个进栈的元素在栈底,
最后一个进栈的元素在栈顶,
第一个出栈的元素为栈顶元素,
最后一个出栈的元素为栈底元素
安徽新华电脑专修学院课堂教学教案
(电脑应用课使用)
教
学
过
程
设
计
(续表)
二栈的基本操作(用时20分钟)
1) 构造一个空栈S;
2)进栈操作Push
3)出栈操作Pop
4)取栈顶元素top
任务二、栈存储
1、栈的顺序存储结构(用时40分钟)
#defineMAX50
intstack[MAX];
inttop=0;
1)进栈操作
viodPush(intx)
{if(top>=MAX)printf(“overflow”);
else{stack[top]=x;top++;}
}
2)出栈操作
intpop()
{if(top==0){printf(“underflow”);return(NULL);}
top--;return(stack[top]);
}
2、栈的链式存储和实现(用时40分钟)
(1)进栈算法
NODE*top;
Voidpush(intx)
{NODE*p=(NODE*)malloc(sizeof(NODE);
p->data=x;
p->link=top;
top=p;
}
教
学
过
程
设
计
(续表)
(2)出栈算法
NODE*pop();
{NODE*p;
if(top==NULL)return(NULL);
p=top;
top=p->link;
return(p);
}
复习思考题
作业
上机任务
案例分析:
死胡同案例分析
参考文献
《数据结构》(C语言版)扬振生中国科学技术大学出版社
课后记
(或归纳小结)
栈是限定仅能在表尾一端进行插入、删除操作的线性表;栈的元素具有后进先出的特点;栈顶元素的位置由一个称为栈顶指针的变量指示,进栈、出栈操作要修改栈顶指针
课程名称
数据结构
教学对象
新华软工
教材
数据结构(C语言)
授课内容
第三章栈和队列
课时
3
教学目的
与要求
本章主要介绍栈和队列的定义,它们的特点,算法实现
重点、难点
重点:
栈和队列的定义和特性、它们的基本操作、存储结构
难点:
队列的顺序存储结构
课型
电脑+理论
教学方法
投影、讨论、板书
教学过程
设计
(包括讲授知识、演示内容及案例、提问及学生演示内容)
任务三、栈的应用举例
例1数制转换(用时50分钟)
对于输入的任意一个非负十进制数,显示输出与其等值的八进制数
数制转换方法
N=(Ndiv8)10⨯8+Nmod8
N:
十进制数,div:
整除运算,mod:
求余运算;
(1348)10=2⨯83+5⨯82+0⨯8+4=(2504)8
N1348168212
Ndiv81682120
Nmod84052
安徽新华电脑专修学院课堂教学教案
(电脑应用课使用)
教
学
过
程
设
计
(续表)
voidconversion()
{InitStack(s);//建空栈
scanf(“%d”,&x);//输入一个非负十进制整数
while(x!
=0){//x不等于零循环
push(s,x%8);//x/8第一个余数进栈
x=x/8;//整除运算
}
while(!
StackEmpty(s))//输出存放在栈中的八制数位
{x=pop(s);
printf(“%d”,x);
}
}
例2表达式求值(用时100分钟)
1)问题的提出
设计一个小计算器:
对键入的表达式进行求值。
2)表达式的构成操作数+运算符+界符(如括号)
3)表达式的求值:
例5+6⨯(1+2)-4
按照四则运算法则,上述表达式的计算过程为:
5+6⨯(1+2)-4=5+6⨯3-4=5+18-4=23-4=19
4)算符优先关系表
表达式中任何相邻运算符c1、c2的优先关系有:
c1 c1的优先级低于c2 c1=c2: c1的优先级等于c2 c1>c2: c1的优先级高于c2 5)算符优先算法 5+4⨯(1+2)-6 从左向右扫描表达式: 遇操作数——保存; 遇运算符号cj——与前面的刚扫描过的运算符ci比较 若ci 。 ) 若ci>cj则说明ci是已扫描的运算符中优先级最高者,可进行运算; 若ci=cj则ci为(,cj为),说明括号内的式子已计算完,需要消去括号; 教 学 过 程 设 计 (续表) 算符比较算法 CharPrecede(charc1,charc2) {intc_temp1,c_temp2; switch(c1) {case‘*‘: case‘/‘: c_temp1=4;break; case‘+‘: case‘-‘: c_temp1=2;break; ......} switch(c2) {case‘*‘: case‘/‘: c_temp2=3;break; case‘+‘: case‘-‘: c_temp2=1;break; ......} if(c_temp1 if(c_temp1=c_temp2)return(‘=‘); if(c_temp1>c_temp2)return(‘>‘); } 在算符优先算法中,建立了两个工作栈。 一个是OPTR栈,用以保存运算符一个是OPND栈,用以保存操作数或运算结果。 intexpress() {//运算数栈,OP为运算符集合。 InitStack(OPTR);Push(OPTR,‘#‘); InitStack(OPND);w=getchar(); While(w! =‘#’||GetTop(OPTR)! =‘#’) {if(! In(w,OP)){Push(OPND,w);w=getchar();}//不是运算符则进栈 else//In(w,OP)判断c是否是运算符的函数 switch(Precede(GetTop(OPTR),w){ case‘<‘: //新输入的算符w优先级高,w进栈 Push(OPTR,w);w=getchar();break; case‘=‘: //去括号并接收下一字符 x=Pop(OPTR);w=getchar();break; case‘>’: //新输入的算符c优先级低,即栈顶算符优先权高, //出栈并将运算结果入栈OPND op=Pop(OPTR); b=Pop(OPND);a=Pop(OPND); Push(OPND,Operate(a,op,b)); break;} }returnGetTop(OPND); } 复习思考题 作业 上机任务 案例分析: 例1数制转换 例2表达式求值 参考文献 《数据结构》(C语言版)扬振生中国科学技术大学出版社 课后记 (或归纳小结) 本章主要介绍的栈的特性,来说明两个例子 课程名称 数据结构 教学对象 新华软工 教材 数据结构(C语言) 授课内容 第三章栈和队列 课时 3 教学目的 与要求 本章主要介绍栈和队列的定义,它们的特点,算法实现 重点、难点 重点: 栈和队列的定义和特性、它们的基本操作、存储结构 难点: 队列的顺序存储结构 课型 电脑+理论 教学方法 投影、讨论、板书 教学过程 设计 (包括讲授知识、演示内容及案例、提问及学生演示内容) 任务四、队列的概念 一、什么是队列(用时30分钟) 队列是限定仅能在表头进行删除,表尾进行插入的线性表 队列的特点: 先进先出 第一个入队的元素在队头,最后一个入队的元素在队尾, 第一个出队的元素为队头元素,最后一个出队的元素为队尾元素 二队列的基本操作(用时20分钟) 1)初始化操作 2)销毁操作 3)置空操作 4)判空操作 5)取队头元素操作 6)入队操作 7)出队操作 安徽新华电脑专修学院课堂教学教案 (电脑应用课使用) 教 学 过 程 设 计 (续表) 任务五: 队列的存储 一、队列的顺序存储: (用时40分钟) #defineMAX50/*数据结构定义*/ intqueue[MAX];intfront=-1;rear=-1; intinsert_queue(intx)/*入队列*/ {if(rear==MAX-1)return(0); rear++; queue[rear]=x;return (1); } intdel_queue()/*出队列*/ {if(rear==front)return(0); front++;return(queue[front]); } 当rear==front相等时,队列有可能是空的也有可能满的,所以就不能有任何二义性,到底是满的,还是空的,所以必须想办法处理,出现一种循环列 二循环队列的基本操作算法(用时20分钟) 有两种方法: 1)另设一个标志位以区分队空、队满。 2)少用一个存储单元,队满条件: front=rear+1; 1、初始化操作 功能: 建一个空队列Q;算法: Intqueue[MAX]; Intfront,rear; intInitQueue_Sq(){ //构造一个空队列Q front=0;rear=0; Return (1)} 2、入队操作功能: 将元素x插入队尾 教 学 过 程 设 计 (续表) intinsert_queue(intx)/*入队列*/ {if((rear+1)%MAX==front)return(0); queue[rear]=x; rear=(rear+1)%MAX;return (1); } 3、出队操作功能: 删除队头元素; intdel_queue()/*出队列*/ {intx; if(rear==front)return(0); x=queue[front]; front=(front+1)%MAX; return(x); } 三、链队列——队列的链式存储结构和实现(用时40分钟) structnode//链队列结点的类型定义 {intdata; structnode*link; };typedefstructnodeNODE NODE*front,*rear; 1、队列入列运算 Voidaddqlink(intx) {NODE*p; p=(NODE*)malloc(sizeof(NODE)); p->data=x;p->link=NULL; rear->link=p;rear=p; } 2、队列出列运算 intcount() {inti=0;NODE*p; if(front==rear)return(0); for(p=front->link;p! =NULL;p=p->link)i++; return (1); } 复习思考题 作业 上机任务 案例分析: 1)解决计算机主机与外设不匹配的问题; 2)解决由于多用户引起的资源竞争问题; 3)离散事件的模拟----模拟实际应用中的各种排队现象; 4)用于处理程序中具有先进先出特征的过程; 参考文献 《数据结构》(C语言版)扬振生中国科学技术大学出版社 课后记 (或归纳小结) 队列是限定仅能在表尾一端进行插入,表头一端删除操作的线性表; 队列中的元素具有先进先出的特点; 队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示, 入队操作要修改队尾指针,出队操作要修改队头指针;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 教案 第三