武汉理工大学-信息工程学院-数据结构c1第一章-新

2020/11/121C语言程序设计教程2020/11/122关于本课程的教学安排本课程的教学目的：通过对C语言的学习，掌握使用计算机编程语言解决实际问题的基本理论、方法、技巧、以及常用的算法。本课程的教学安排：理论教学38学时，实验教学22学时。参考书：《C语言程序设计》谭浩强著《ThinkinginC++》机械工业出版社《ComputerConcepts》4thedtion机械工业出版社2020/11/123Let’scontinueourClanguagejourney!2020/11/124ThestrategyoflearningCisastep-by-stepapproach,firstlayingasoundfoundationonprogrammingconcepts,flowofcontrol,andfunctions.ThefundamentalsofCprogrammingisasteppingstonethatwillprepareyoutoembarkonthejourneyoflearningC++andJAVA.2020/11/125YouwillbegintolearnhowtowritesimpleCprogramswithprimitivedatatypes,controlstatements,functions,andarrays.ProgrammingExercisesattheendofeachchapterprovideyouwithopportunitiestoapplytheskillsonyourown.2020/11/126Thetrickoflearningprogrammingispractice,practice,andpractice.2020/11/127第一章C语言程序设计基础知识1.1概述1.1.1信息的表示1.数制十进制：日常使用的数制。二进制、八进制、十六进制：计算机中使用的数制。2020/11/128不同数制间的转换：二、八、十六进制转换成十进制的方法是--------按位权法展开。例：二进制转换成八、十六进制的方法是--------分组法（三位、四位一组）。例：八、十六进制转换成二进制的方法是--------直接法（直接将八、十六进制数字符号转换成二进制数字符号）。例：十进制转换成二、八、十六进制间的方法是--------整数部分除法取余，小数部分乘法取整。例：(101.01)2=1×22+0×21+1×20+0×2-1+1×2-2=(5.25)10↑小数点位置(1a.2)16=1×161+10×160+2×16-1=(26.125)10↑小数点位置(1010111.011)2=(001010111.011)2=(127.3)8(1010111.011)2=(01010111.0110)2=(57.6)16转换时应注意：分别对整数和小数部分进行分组。整数部分：从小数点开始，向左三位（四位）一组，不够三位（四位）时，高位充零。小数部分：从小数点开始，向右三位（四位）一组，不够三位（四位）时，低位充零。最后将各组数据转换成相应数制的符号即可。(a5)16=(10100101)2建议：二、八、十六进制间的转换应利用二进制作为过渡，这样做来得简单。例：求(a5)16的八进制表示。(a5)16=(10100101)2=(010100101)2=(245)80.125×2=0.25….0最高位2020/11/129(28.125)10对应的二进制数是(11100.001)2。整数部分：28小数部分：0.125余数整数2…….0最低位14282…….072…….132…….11最高位0.125×2=0.25….0最高位0.25×2=0.5….00.5×2=1.0….1最低位2020/11/1210数据数值数据：二进制非数值数据：编码定点法浮点法西文：ASCII,BCD汉字：国标码图形有符定点无符定点2.数据的编码通常在计算机中用8个、16个、32个….等固定个数的二进制位来表示某一个数据。计算机中常见的数据分为两种即数值数据和非数值数据。2020/11/1211数值型数据：通常在计算机中用8个、16个、32个二进制位来表示数值型数据。小数点的位置总是隐含的，以节省空间。但小数点的位置可以是固定的或可变的。前者称为定点数，后者称为浮点数。(1)定点数（在计算机中整数是按定点数格式存放的）定点数分为:有符定点数（signed)无符定点数(unsigned)。⑵浮点数（在计算机中小数是按浮点数格式存放的）2020/11/1212有符定点整数dsdndn-1dn-2……..d1↑↑符号位数值部分小数点无符定点整数dndn-1dn-2…………..d1↑数值部分小数点2020/11/1213⑵浮点数（在计算机中小数是按浮点数格式存放的）浮点数格式如下：Jsjnjn-1….j2j1dsdmdm-1…….…..d2d1↑↑阶符阶码数符尾数2020/11/1214字符型数据：常用的英文编码有ASCII码、BCD码ASCII码ASCII码是英文AmericanStandardCodeforInformationInterchange（美国信息交换标准编码）的缩写。该编码已经国际标准化组织所采纳。目前国际上流行的是ASCII编码的七位版本，即用一个字节的低七位表示一个字符，高位充零。七个二进制位可表示128种状态，故可用来表示128个不同的字符，在ASCII编码的七位版本中表示的33个通用控制字符、95个可打印显示的字符（其中10个数字、52个大小写英文字母、33个标点符号和运算符号）。ASCII编码表（见附录I）2020/11/1215字符型数据：常用的中文编码有国家标准汉字编码(GB码)GB2312-80（国家标准汉字编码）是常用的汉字编码标准，它收录了6763个常用汉字。国标码使用连续的两个字节（十六位二进制位）表示一个汉字。根据这些汉字使用频率的高低，分成两部分：一级汉字共3755个，即最常用的汉字。二级汉字共3008个，为次常用的汉字。GB2312-80还收录了一些数字符号、图形符号、外文字母等。2020/11/1216数值数据的编码方法：前面讨论的是数值数据在计算机中的存放格式，下面讨论对数值数据进行编码的方法。①原码表示法：(假定用八个二进制位表示）a=+51(a)2=(+00110011)2则[a]原=00110011a=-127(a)2=(-01111111)2则[a]原=11111111原码表示法在八个二进制位中的表示范围：-127≤a≤+127[+0]原=00000000[-0]原=10000000要点：最高位作为符号位，若正数，则最高位是0，若负数，则最高位是1。2020/11/1217②反码表示法：(假定用八个二进制位表示）通过一个二进制整数的原码得到所谓反码：当a为正数时，[a]原=[a]反,当a为负数时，则保持[a]原的符号位不变，其余各个二进制位逐位取反，即0变1，1变0。如：a=+51[a]原=00110011则[a]反=[a]原=00110011a=-51[a]原=10110011则[a]反=11001100反码表示法在八个二进制位中的表示范围：-127≤a≤+127[+0]反=00000000[-0]反=11111111要点：由原码得到反码。若正数，则反码与原码相同，若负数，则最高位不变，其余逐位取反。2020/11/1218③补码表示法：(假定用八个二进制位表示）通过一个二进制整数的反码得到所谓补码：当a≥0时，[a]补=[a]反,当a＜0时，则[a]补=[a]反+1，如：a=+51[a]原=00110011则[a]补=[a]反=[a]原=00110011a=-51[a]原=10110011[a]反=11001100则[a]补=[a]反+1=11001101补码表示法在八个二进制位中的表示范围：-128≤a≤+127[+0]补=00000000[-128]补=10000000要点：由反码得到补码。若正数，则反码与补码相同，若负数，则补码等于反码加1。在补码表示法中，0的表示是唯一的，而最小值可达-128。2020/11/1219在上述介绍当中我们是以八位二进制位为例，同样，我们可以将其推广到十六位，三十二位等二进制位中去，需要注意的是数值范围将发生变化。思考：以上介绍的原码、反码、补码都是有符定点整数的编码方式，若以八位二进制位表示无符定点整数，则其范围是0到255。在TurboC中：有符整数是按有符定点整数格式的补码表示的，无符整数是按无符定点整数格式表示的。2020/11/1220补码的加、减法补码的加法公式是：[a]补+[b]补=[a+b]补补码的减法公式是：[a-b]补=[a]补-[b]补=[a]补+[-b]补例1.1：a=[11]10=[00001011]原，b=[5]10=[00000101]原,求a+b。因为[a]补=00001011,[b]补=00000101补码→[a+b]补=[00010000]补[a+b]反=[00010000]反[a+b]原=[00010000]原=[16]100001000000000101000010112020/11/1221一、负整数的原码与补码的快速转换：⒈从左到右；⒉见0不变、见第一个1也不变；⒊其余位依次取反；⒋最高位不变二、整数的原、反、补码相同。2020/11/1222例1.2：-a=[-11]10=[10001011]原，b=[5]10=[00000101]原，求b-a。因为[-a]补=11110101,[b]补=00000101补码→[b-a]补=[b]补+[-a]补=[11111010]补[b-a]反=[11111001]反[b-a]原=[10000110]原=[-6]101111101011110101000001012020/11/1223关于字符编码方法：要注意ASCII码和国标码应用对象的不同，ASCII码用来对英文字符编码而国标码用来对汉字进行编码。ASCII码使用一个字节（八位二进制位），国标码使用两个字节（十六位二进制位）。GB2312-80规定了用连续的两个字节来表示一个汉字，并且只用各个字节的低7位，最高位未定义。这样以来就有可能与ASCII码字符产生冲突，就单个字节来说，两种编码方式都只用到字节的低七位，ASCII码规定高位充零，而国标码对高位未定义，因此，对单个字节而言，不能确定它到底是一个ASCII码字符还是一个汉字的一部分（低字节或高字节）。于是有很多为了解决这类问题的方案应运而生，变形国标码就是其中之一，并且得到了广泛的应用。它的主要特点是将国标码编码的各个字节的最高位置1，以达到区别于ASCII编码的目的。2020/11/1224如何理解存储在计算机中的信息计算机中各种信息都是以二进制形式存在，有的是数值，有的是ASCII码字符，有的是汉字，如何区分它们呢？这实际上取决于我们（或者程序）按照何种规则判读它们，例如：对于机器内存中连续两个字节，它们的低七位内容分别为0110000和0100001，如果它们的最高位均为1，则表示汉字“啊”，如果均为0则表示为两个ASCII码字符“0”和“！”。当然，我们还可根据不同的数值编码规则将它们判读成不同的数值。2020/11/12251.1.2计算机系统的基本组成一个完整的计算机系统是由硬件系统和软件系统两大部分组成。硬件系统：是构成计算机系统的各种物理设备的总称，是计算机系统的物质基础，它由运算器、控制器、存储器、输入设备和输出设备组成；软件系统：是为运行、管理和维护计算机而编制的程序和各种文档的总和。2020/11/1226计算机系统硬件系统软件系统主机外设系统软件应用软件中央处理器（CPU）内存储器运算器（ALU）控制器（CU）只读存储器（ROM）随机存储器（RAM）外部存储器(辅助存储器）输入设备输出设备操作系统编译系统数据库管理系统实用程序专用应用软件通用应用软件图1-42020/