次小课汉字存储与算法设计.ppt

1,第3次小课 汉字存储与算法设计,实验目的： 掌握汉字的机内存储规律，完成指定问题的算法设计。,2,一.汉字存储的机内码,1.汉字编码 （1）国家标准 GB2312 一个汉字和 4 个十进数字对应 前两个称为区号 194 后两个称为位号 194 极限编码8836个，其中已定义 6763个 汉字 分为 一级 3755个 二级 3008个 682个 非汉字图形字符,3,（2）输入码 在通用的键盘上输入汉字 主要种类: 字根代码 典型代表：“五笔字型” 输入法 输入速度快， 要专门学习 拼音 易掌握，但同音字多，输入较慢 改进的方法从字词的上下关联入手， 尽量减少击键次数，提高输入速度 典型代表：“搜狗” 输入法 等,4,2.汉字机内码 如何存储用输入码形式输入计算机内的汉字好呢?把输入编码字符串原封不动地存放是不合适的。同一个汉字在不同的输入法中有不同的编码，但编码长度绝大多数超过2个字节。而且同一种输入法里，不同汉字的编码长度也不一定相同。这样就给汉字的存储和处理带来麻烦。因此有必要对输入的汉字进行转换，变成统一的一种机内存储形式，这就是 汉字的内部码。,5,虽然汉字内部码没有统一的标准格式，但使用的形式只有几种。最常用的一种内部码 格式是： (1)一个汉字的内码占据两个字节。 (2)每个字节中使用标志位来表示这是个汉字字节还是个ASCIl码字符字节；汉字的第一个字节的标志位为“1”，第二个字节的标志位可以是“1”也可以是“0”；ASCIl码字符的标志位为“0”。 (3)汉字的第一个字节中除标志位外的其余7位内容是：汉字的GB2312码区号+32；第二个字节标志位外的其余7位内容是：汉字的GB2312码位号+32(见图5-13)。,6,这种方案实现的前提是：系统使用7单位的ASCIl码表示字符每个字符编码用一个字节存储，这样就有一个“空闲”位可以用作汉字或者字符的标志位。那么，为什么汉字内码不直接用国标码的区号和位号来表示，而要作一个加32的位移呢?这是种以防万一的考虑。区、位号的取值范围是l94，加上32后，码值在33126之间。这样就避过ASCIl码的控制字符区间。万一系统没有汉字处理能力，把汉字内码字节的右7位当作字符处理，也只是错为可印出字符，引起混乱的程度也许不那么严重。,7,例：已知“广东”这两个汉字的内部码为：B9E3和B6AB，请问它们的区位码分别是什么？ 解：首先看“广”字，每个字节的最高位变为0后则为(39)H和(63) H 每个字节减去32后则为(19)H和(43) H 转换成十进制就是25和67，他就是“广”字的区码和位码，所以“广”字的区位码就是：2567 同理，“东” 字的区位码是：2211,8,验证：首先用记事本写入两个字“广东”，然后再用16进制编辑器打开这个文本文件，可以看到“广东”两个字的机内码是B9E3和B6AB。 然后，再用区位码输入法输入： 2567和2211就可以在文本编辑器中看到“广东”两个汉字。,9,算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。 一个算法应该具有以下五个重要的特征： 1、有穷性： 一个算法必须保证执行有限步之后结束； 2、确切性： 算法的每一步骤必须有确切的定义； 3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件； 4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 5、可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。,二.算法,10,算法表示手段,1、流程图符号,起 / 始,动作,条件,算法的起点和终点,循环条件,循环条件,基本符号：,表示意义：,数据/数据的输入输出动作,处理动作,（逻辑）判断,流线、（动作）控制流方向,循环、上/下界,11,一、流程图符号(续),基本符号：,表示意义：,特定处理：另外再详细表示的操作,准备(动作),符,(流程的接点)连接符,注解,12,并行符号和并行动作示例,13,2、操作表示 原则：具体或笼统的程度和算法的描述目标相一致 例：1.把S中的元素按升序排列 (很笼统） 2.交换变量a和b的值 （较具体） 面向高级程序设计的操作表示建议： 1） 输入/输出操作 （不指向介质和设备） 输入：变量(名) 输出： 2）赋值操作（处理） 变量(名) 或 变量(名) ,14,3）对文本的操作（处理） 打开/关闭文件 读，写，重写，删除一个记录 4）判断,操作涉及的数据表示方式：常量、变量、函数、表达式, 描述格式是不严格的。,15,算法示例,1、顺序结构的算法设计 要点： （1）把处理过程转化为一个依次逐步执行的操作序列 （2）操作步之间的先后关系 一般：输入变换处理输出 （3）算法操作序列和计算机执行序列一致，注意对数据对象的修改序列，保证结果正确。 如： T+BT T+1A 不等同 T+1A T+BT,16,例1.计算圆的周长和面积,开始,结束,2* 3.14 * 2 L,3.14 * 2*2S,输出：L，S,开始,结束,输入：R,2*3.14*R L 3.14 * R*RS,输出：“周长=”，L “面积=”，S,算法1 只能计算一个圆(R=2),算法2 计算任意圆,17,2、分支结构的算法设计 p215,例1. 求解Ax + Bx + C=0,由判断的取值,决定执行两个处理序列中的一个。,开始,B*B -4*A*CW,SQRT(W)W,(-B+W)/（2*A）x1 (-B -W)/（2*A）x2,结束,SQRT( ) 是个函数,18,3、重复结构,1.单重循环结构,开始,结束,i是个计数器,例1： 在500个输入数中挑选最大者。,19,【例】将两个变量a和b的值互换的程序。 main() int a=2,b=5,c; c=a; a=b; b=c; printf(“%d %dn“,a,b); 如果只允许定义：a，b两个变量，这个程序该如何修改。,20,求出100以内的所有素数： main() int i,j,k; for (i=2;i=100;i+) k=1; for ( ) if (i % j=0) ; if (k=1) printf(“%d “,i); ,21,打印汉字字库： main() int i,j; char c1,c2; for (i=1;i=94;i+) printf(“nn第%d区：nn“,i); c1=i+32+128; for (j=1;j=94;j+) c2=j+32+128; printf(“%c%c “,c1,c2); getch(); ,22,数据的栈结构 数据入栈顺序：A B C D E 执行的操作是：push、push、pop、push、 pop、pop、push、push、pop、pop 则出栈顺序为：,B C A E D,23,请运用前面讲过的知识求出“华软”这两个汉字的机内码和区