编程社团活动课教案.docx
《编程社团活动课教案.docx》由会员分享，可在线阅读，更多相关《编程社团活动课教案.docx（38页珍藏版）》请在冰点文库上搜索。
编程社团活动课教案
第一课进制转换
教学目标
1.让学生掌握二进制、八进制、十进制、十六进制转换的方法；
2.让学生理解进制转换的原理；
3.会使用转换方法解决问题。
重点：
进制转换方法
难点：
对进制概念的理解
教学过程
一、进制的概念
（一）进制
进制也就是进位计数制，是人为定义的带进位的计数方法（有不带进位的计数方法，比如原始的结绳计数法，唱票时常用的“正”字计数法，以及类似的tallymark计数）。
对于任何一种进制---X进制，就表示每一位置上的数运算时都是逢X进一位。
十进制是逢十进一，十六进制是逢十六进一，二进制就是逢二进一，以此类推，x进制就是逢x进位。
二进制只有0，1两个数字；八进制有0，1，2，3，4，5，6，7共八个数字；十进制有0，1，2，3，4，5，6，7，8，9共十个数字；十六进制有0，1，2，3，4，5，6，7，8，9，A，B，C，D，E，F共十六个数字，期中A代表11，B代表12，……，依此类推，F代表15。
计算机存储数据采用的是二进制。
（二）进制数的书写
1.二进制数的书写通常在数的右下方注上基数2，或加后面加B表示。
如二进制数101书写时可写作（101）B或（101）2。
2.八进制用下标8或数据后面加O（英语大写字母O）表示。
如八进制数36书写时可写作（36）O或（36）8。
3.十六进制数通常在表示时用尾部标志H或下标16以示区别。
例如：
十六进制数4AC8可写成（4AC8）H或写成（4AC8）16。
二、进制转换
进制转换就是将一个某种进制的数转换成另外一种进制的数，比如把一个二进制的数转换成十进制，把一个十进制的数转换成二进制、八进制等。
（一）二进制与十进制之间的转换
1.十进制转二进制
方法：
十进制数除2倒取余法，即十进制数除2，余数为权位上的数，得到的商值继续除，直到商为0为止，然后从最后一个余数写到第一个余数。
2.二进制转十进制
方法：
把二进制数按权展开、相加即得十进制数。
（二）二进制与八进制之间的转换
1.二进制数与八进制数的关系（用三位二进制表示一个八进制数）
八进制
二进制
三位二进制按权展开相加
0
000
0*22+0*21+0*20=0
1
001
0*22+0*21+1*20=1
2
010
0*22+1*21+0*20=2
3
011
0*22+1*21+1*20=3
4
100
1*22+0*21+0*20=4
5
101
1*22+0*21+1*20=5
6
110
1*22+1*21+0*20=6
7
111
1*22+1*21+1*20=7
2.八进制转二进制
方法一：
八进制数每一位通过除2倒取余法，得到3位二进制数（不足补0），从左到右读出。
方法二：
对每个八进制数表示为1个3位二进制数，去掉最左边的0，从左到右读出。
3.二进制转八进制数
方法：
从右向左每3位二进制数（不足时补零）转成1个八进制数。
（三）二进制与十六进制之间的转换
1.二进制数与十六进制数的关系（用四位二进制表示一个十六进制数）
八进制
二进制
四位二进制按权展开相加
0
0000
0*23+0*22+0*21+0*20=0
1
0001
0*23+0*22+0*21+1*20=1
2
0010
0*23+0*22+1*21+0*20=2
3
0011
0*23+0*22+1*21+1*20=3
4
0100
0*23+1*22+0*21+0*20=4
5
0101
0*23+1*22+0*21+1*20=5
6
0110
0*23+1*22+1*21+0*20=6
7
0111
0*23+1*22+1*21+1*20=7
8
1000
1*23+1*22+1*21+0*20=8
9
1001
1*23+1*22+1*21+0*20=9
A
1010
1*23+0*22+1*21+0*20=10
B
1011
1*23+0*22+1*21+1*20=11
C
1100
1*23+1*22+0*21+0*20=12
D
1101
1*23+1*22+0*21+1*20=13
E
1110
1*23+1*22+1*21+0*20=14
F
1111
1*23+1*22+1*21+1*20=15
2.十六进制转二进制
方法一：
十六进制数每一位通过除2倒取余法，得到4位二进制数（不足补0），从左到右读出。
方法二：
对每个十六进制数表示为1个4位二进制数，去掉最左边的0，从左到右读出。
3.二进制转十六进制
方法为：
与二进制转八进制方法近似，八进制是取三合一，十六进制是取四合一。
（注意事项，4位二进制转成十六进制是从右到左开始转换，不足时补0）。
（四）十进制与八进制与十六进制之间的转换
1.十进制转八进制或者十六进制
第一：
间接法—把十进制转成二进制，然后再由二进制转成八进制或者十六进制。
第二：
直接法—把十进制转八进制或者十六进制按照除8或者16取余，直到商为0为止。
（具体用法如下图）
2.八进制或者十六进制转成十进制
方法为：
把八进制、十六进制数按权展开、相加即得十进制数。
（具体用法如下图）
3.十六进制与八进制之间的转换
八进制与十六进制之间的转换有两种方法
第一种：
它们之间的转换可以先转成二进制然后再相互转换。
第二种：
它们之间的转换可以先转成十进制然后再相互转换。
三、带有小数点的进制转换
（一）十进制小数→R进制小数
乘R取整顺序法：
乘基数取整，连续乘以基数，并取其整数，直到积为零或达到所要求的精度时，将所得整数正序排列即可。
（二）二进制小数→八进制
方法：
小数部分从左向右三位并一位。
（三）二进制小数→八进制
方法：
小数部分从左向右四位并一位。
第二课原码、反码、补码
教学目标
1.让学生掌握原码、反码、补码的概念；
2.会进行原码、反码、补码间的计算。
重点：
原码、反码、补码的计算
难点：
对原码、反码、补码的理解
教学过程
一、机器数和真值
1.机器数
一个数在计算机中的二进制表示形式,叫做这个数的机器数。
机器数是带符号的，在计算机用一个数的最高位存放符号,正数为0,负数为1.
比如，十进制中的数+3，计算机字长为8位，转换成二进制就是00000011。
如果是-3，就是10000011。
那么，这里的00000011和10000011就是机器数。
2.真值
因为第一位是符号位，所以机器数的形式值就不等于真正的数值。
例如上面的有符号数10000011，其最高位1代表负，其真正数值是-3而不是形式值131（10000011转换成十进制等于131）。
所以，为区别起见，将带符号位的机器数对应的真正数值称为机器数的真值。
例：
00000001的真值=+0000001=+1，10000001的真值=–0000001=–1
二、原码、反码、补码的基础概念和计算方法
对于一个数,计算机要使用一定的编码方式进行存储。
原码、反码、补码是机器存储一个具体数字的编码方式。
1.原码
原码就是符号位加上真值的绝对值,即用第一位表示符号,其余位表示值。
比如如果是8位二进制：
[+1]原 =00000001
[-1]原 =10000001
第一位是符号位，因为第一位是符号位,所以8位二进制数的取值范围就是:
[11111111,01111111]
即[-127,127]
原码是人脑最容易理解和计算的表示方式。
2.反码
反码的表示方法是：
正数的反码是其本身
负数的反码是在其原码的基础上,符号位不变，其余各个位取反。
[+1]=[00000001]原 =[00000001]反
[-1]=[10000001]原 =[11111110]反
可见如果一个反码表示的是负数,人脑无法直观的看出来它的数值，通常要将其转换成原码再计算。
3.补码
补码的表示方法是:
正数的补码就是其本身
负数的补码是在其原码的基础上,符号位不变,其余各位取反,最后+1。
（即在反码的基础上+1）
[+1]=[00000001]原 =[00000001]反 =[00000001]补
[-1]=[10000001]原 =[11111110]反 =[11111111]补
对于负数,补码表示方式也是人脑无法直观看出其数值的，通常也需要转换成原码在计算其数值。
第三课栈
教学目标
1.让学生掌握栈的概念及栈的基本操作；
2.能对顺序栈、链栈进行操作。
重点：
顺序栈、链栈的基本操作
难点：
链钱的操作
教学过程
一、什么是栈？
栈，汉语解释为存储货物或供旅客住宿的地方,可引申为仓库、中转站，入到计算机领域里，就是指数据暂时存储的地方。
定义：
只允许在表尾进行插入和删除操作的线性表。
所以首先栈是一种线性表，其次栈限定只能在某一端进行插入和删除操作。
二、常见的两种栈及其操作
（一）顺序栈
采用顺序存储结构的栈。
几个定义：
栈顶（Top）：
允许进行插入删除操作的一端，也即是箱子的顶部；
栈底（Bottom）：
固定并且不允许进行插入和删除操作的一端，也就是箱子的底部；
空栈：
不含有任何元素的空表；
进栈（PUSH）：
向一个栈插入新元素，又称作入栈或压栈；
出栈（POP）：
从一个栈删除元素，又称作或退栈。
栈的操作特性可以概括为后进先出，因此栈也称为先进后出表。
如把A……Z按顺序放入一个栈中，A最先被放入，它是栈底元素，Z最后被放入，它是栈顶元素，当出栈时，因为只能在栈顶进行插入和删除操作，所以进最先出栈是的Z。
栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。
（二）链式栈
采用链式存储的栈称为链式栈（链栈），链栈的优点是便于多个栈共享存储空间和提高其效率，而且不存在栈满上溢的情况。
链栈通常采用单链表实现，并规定其所有操作都是在单链表的表头进行的。
这里规定链栈没有头结点，head指向栈顶元素。
链栈示意图
链表的头部作为栈顶，意味着：
在实现数据“入栈”操作时，需要将数据从链表的头部插入；
在实现数据“出栈”操作时，需要删除链表头部的首元节点；
因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表。
（一）链栈元素入栈
例如，将元素1、2、3、4依次入栈，等价于将各元素采用头插法依次添加到链表中，每个数据元素的添加过程如图所示：
链栈元素依次入栈过程示意图
（二）链栈元素出栈
例如，在上图所示的链栈中，若要将元素3出栈，根据"先进后出"的原则，要先将元素4出栈，也就是从链表中摘除，然后元素3才能出栈，整个操作过程如图所示：
链栈元素出栈示意图
（三）基本算法
1．进栈（PUSH）算法
①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；
②置TOP=TOP+1（栈指针加1，指向进栈地址）；
③S（TOP）=X，结束（X为新进栈的元素）；
2.退栈（POP）算法
①若TOP≤0，则给出下溢信息，作出错处理（退栈前先检查是否已为空栈，空则下溢；不空则作②）；
②X=S（TOP），（退栈后的元素赋给X）：
③TOP=TOP-1，结束（栈指针减1，指向栈顶）。
三、典型练习题
1.设链表不带头结点，且所有操作均在表头进行，则下列最不适合作为链栈的链表是（C）。
A．只有表头结点指针，没有表尾指针的双向循环链表
B．只有表尾结点指针，没有表头指针的双向循环链表
C．只有表头结点指针，没有表尾指针的单向循环链表
D．只有表尾结点指针，没有表头指针的单向循环链表
解析：
对于双向训练链表，不管是表头指针还是表尾指针，都可以很方便地找到表头节点，方便在表头做插入或删除操作。
单向循环链表通过尾指针可以很方便地找到表头节点，但通过头指针找尾节点需要遍历一次链表。
对于C，插入和删除节点后，找尾节点需要花费O（n）的时间。
2.向一个栈顶指针为top的链栈中插入一个x结点，则执行（ C）。
A.top->next=x B.x->next=top->next;top->next=x
C.x->next=top;top=x D.x->next=top,top=top->next
解析：
链栈釆用不带头结点的单链表表示时，进栈橾作在首部插入一个结点x（即x->next=top），插入完后需将top指向该插入的结点X。
3.链栈执行Pop操作，并将出栈的元素存在x中应该执行（D）。
A.x=top;top=top->next B.x=top->data
C.top=top->next;x=top->data D.x=top->data;top=top->next
解析：
这里假设栈顶指针指向的是栈顶元素，所以选D；而A中首先将top指针赋给了x，错误；B中没有修改top指针的值；C为top指针指向栈顶元素的上一个元素时的答案。
4.若一个栈的输入序列是1,2，3,…,n，输出序列的第一个元素是n，则第i个输出元素是（D）。
A.不确定 B.n-i C.n-i-1 D.n-i+1
解析：
第n个元素先出栈，说明前n-1个元素都已经按顺序入栈，由“先进后出”的特点可知，此时的输出序列一定是输入序列的逆序，故答案选D。
5.一个栈的输入序列为1,2,3,…,n,输出序列的第一个元素是i，则第j个输出元素是（D）。
A,i-j-1 B.i-j C.j-i+1 D.不确定
解析：
当第i个元素第一个出栈时，则i之前的元素可以依次排在i之后出栈，但剩余的元素可以在此时进栈并且也会排在i之前的元素出栈，所以，第j个出栈的元素是不确定的。
6.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为 p1 ， p2 ， p3 ，…， pn ，若p2=3，则p3为可能取值的个数是（C）。
A.n-3 B.n-2 C.n-1 D.无法确定
解析：
显然，3之后的4,5,…,n都是P3可取的数。
P1可是3之前入栈的数（1、2），也可以是4,：
（1）当P1=1时，P3可取2；
（2）当P1=2时，P3可取1；
（3）当P1=4时，P3可取除1、3、4之外的所有数。
所以P3可能的取值个数为n-1。
7.设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。
试设计算法判断该链表的前n个字符是否中心对称。
例如xyx、xyyx都是中心对称。
使用栈来判断链表中的数据是否中心对称。
将链表的前一半元素依次进栈。
在处理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两个元素比较，若相等，则将链表中下一个元素与栈中再弹出的元素比较，直至链表到尾。
这时若栈是空栈，则得出链表中心对称的结论；否则，当链表中的一个元素与栈中弹出元素不等时，结论为链表非中心对称，结束算法的执行。
intdc（LinkListL,intn）{
chars[n/2];//字符栈
inti=1;//记结点个数
P=L->next;//是链表的工作指针，指向待处理的当前元素
for{i=0;is[i]=p->data;
p=p->next;
}
i--;//恢复最后的i值
if（n%2==1）//若n是奇数，后移过中心结点
p=p->next;
while（p!
=NULL&&s[i]==p->data）{//检测是否中心对称
i--;
p=p->next;
}
if（i==-1）//桟为空栈
return1;//链表中心对称
else
return0;//链表不中心对称
}
算法先将“链表的前一半”元素（字符）进栈。
当n为偶数时，前一半和后一半的个数相同；当n为奇数时，链表中心结点字符不必比较，移动链表指针到下一字符开始比较。
比较过程中遇到不相等时，立即退出while循环，不再进行比较。
第四课队列
教学目标
1.让学生掌握队例的概念及队列的基本操作；
2.理解链式队列的入队、出队操作。
重点：
链式队列的基本操作
难点：
链式队列
教学过程
一、什么是队列？
队列，和栈一样，也是一种对数据的“存”和“取”有严格要求的线性存储结构。
与栈结构不同的是，队列的两端都“开口”，要求数据只能从一端进，从另一端出，如图所示：
队列存储结构
通常，称进数据的一端为“队尾”，出数据的一端为“队头”，数据元素进队列的过程称为“入队”，出队列的过程称为“出队”。
不仅如此，队列中数据的进出要遵循“先进先出”的原则，即最先进队列的数据元素，同样要最先出队列。
拿上图中的队列来说，从数据在队列中的存储状态可以分析出，元素1最先进队，其次是元素2，最后是元素3。
此时如果将元素3出队，根据队列"先进先出"的特点，元素1要先出队列，元素2再出队列，最后才轮到元素3出队列。
栈和队列不要混淆，栈结构是一端封口，特点是“先进后出”；而队列的两端全是开口，特点是“先进先出”。
因此，数据从表的一端进，从另一端出，且遵循“先进先出”原则的线性存储结构就是队列。
队列存储结构的实现有以下两种方式：
顺序队列：
在顺序表的基础上实现的队列结构；
链队列：
在链表的基础上实现的队列结构；
两者的区别仅是顺序表和链表的区别，即在实际的物理空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。
实际生活中，队列的应用随处可见，比如排队买XXX、医院的挂号系统等，采用的都是队列的结构。
拿排队买票来说，所有的人排成一队，先到者排的就靠前，后到者只能从队尾排队等待，队中的每个人都必须等到自己前面的所有人全部买票成功并从队头出队后，才轮到自己买票。
这就不是典型的队列结构吗？
二、顺序队列简单实现
由于顺序队列的底层使用的是数组，因此需预先申请一块足够大的内存空间初始化顺序队列。
除此之外，为了满足顺序队列中数据从队尾进，队头出且先进先出的要求，我们还需要定义两个指针（top和rear）分别用于指向顺序队列中的队头元素和队尾元素，如图所示：
顺序队列实现示意图
由于顺序队列初始状态没有存储任何元素，因此top指针和rear指针重合，且由于顺序队列底层实现靠的是数组，因此top和rear实际上是两个变量，它的值分别是队头元素和队尾元素所在数组位置的下标。
在图1的基础上，当有数据元素进队列时，对应的实现操作是将其存储在指针rear指向的数组位置，然后rear+1；当需要队头元素出队时，仅需做top+1操作。
例如，在上图基础上将{1,2,3,4}用顺序队列存储的实现操作如图所示：
数据进顺序队列的过程实现示意图
在上图基础上，顺序队列中数据出队列的实现过程如图所示：
数据出顺序队列的过程示意图
三、链式队列及基本操作
链式队列，简称“链队列”，即使用链表实现的队列存储结构。
链式队列的实现思想同顺序队列类似，只需创建两个指针（命名为top和rear）分别指向链表中队列的队头元素和队尾元素，如图所示:
链式队列的初始状态
上图所示为链式队列的初始状态，此时队列中没有存储任何数据元素，因此top和rear指针都同时指向头节点。
（一）链式队列数据入队
链式队列中，当有新的数据元素入队，只需进行以下3步操作：
a）将该数据元素用节点包裹，例如新节点名称为elem；
b）与rear指针指向的节点建立逻辑关系，即执行rear->next=elem；
c）最后移动rear指针指向该新节点，即rear=elem；
由此，新节点就入队成功了。
例如，在上图的基础上，我们依次将{1,2,3}依次入队，各个数据元素入队的过程如图所示:
{1,2,3}入链式队列
（二）链式队列数据出队
当链式队列中，有数据元素需要出队时，按照“先进先出”的原则，只需将存储该数据的节点以及它之前入队的元素节点按照原则依次出队即可。
这里，我们先学习如何将队头元素出队。
链式队列中队头元素出队，需要做以下3步操作：
a）通过top指针直接找到队头节点，创建一个新指针p指向此即将出队的节点；
b）将p节点（即要出队的队头节点）从链表中摘除；
c）释放节点p，回收其所占的内存空间；
例如，在图2b）的基础上，我们将元素1和2出队，则操作过程如图所示：
链式队列中数据元素出队
第五课前缀、中缀、后缀表达式
教学目标
1.让学生掌握前缀、中缀、后缀表达式的概念；
2.会进行前缀、中缀、后缀表达式间的转换。
重点：
前缀、中缀、后缀表达式间的转换
难点：
前缀、中缀、后缀表达式间的转换
教学过程
一、什么是表达式？
表达式，是由数字、算符、数字分组符号（括号）、自由变量和约束变量等以能求得数值的有意义排列方法所得的组合。
可分为算术表达式和逻辑表达式。
算术表达式是最常用的表达式，又称为数值表达式。
它是通过算术运算符来进行运算的数学公式。
如1+2，（3+4）*6
表达式计算（expressionevaluation）是程序设计语言编译中的一个最基本问题，也是早期计算机语言研究的一项重要成果，它使得高级语言程序员可以使用与数学形式相一致的方式书写表达式。
二、什么是前缀、中缀、后缀表达式？
它们都是对表达式的记法，因此也被称为前缀记法、中缀记法和后缀记法。
它们之间的区别在于运算符相对于操作数的位置不同：
前缀表达式的运算符位于与其相关的操作数之前；中缀和后缀同理。
例如：
（3+4）×5-6中缀表达式
-×+3456 前缀表达式
34+5×6- 后缀表达式
（一）中缀表达式（中缀记法）
中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。
一般我们接触比较熟悉的是中缀表达式。
中缀表达式是常见的运算表达式，如（3+4）×5-6。
中缀表达式在我们日常生活中应用最为广泛，也最符合人的计算思维。
虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。
对计算机来说，计算前缀或后缀表达式的值非常简单。
（二）前缀表达式（波兰式）
1.前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前。
例如：
中缀表达式（2+3）×4-5，采用前缀表达式为：
-×+2345
2.前缀表达式运算
前缀表达式的计算机求值：
从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素op次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。
例如前缀表达式“-×+3456”：
（1）从右至左扫描，将6、5、4、3压入堆栈；
（2）
升级会员 