数据结构chapter1概论14级

1、P1C语言程序设计授课教师：张惕远Email： 遵循ISO/IEC 14882:2003C+标准P2第1章 概 论1.1 C语言背景知识1.2 C语言的发展及特点1.3 C语言程序的书写格式和结构特点1.4 C语言的基本语法单位1.5 简单的输入与输出1.6 运行C程序的一般步骤 2022/9/13P31.1 C语言背景知识1、何为程序设计？C语言有何用？2、计算机的数和编码系统：3、计算机的基本原理4、程序设计语言2022/9/13P4(1.1)1何为程序设计？C语言有何用？程序设计是一个完整的过程，包含：需求分析、总体设计、详细(功能模块)设计、代码编写、调试、用例测试和源代码维护。程序设

2、计的目标就是生成能够可靠执行且满足用户需求功能的可执行应用程序。源代码（又叫源程序）是用程序设计语言写成的，本身无法运行于操作系统C+、C是广泛使用的程序设计语言。2022/9/13P5(1.1)1何为程序设计？C语言有何用？(续)C是结构化的程序设计语言，适合于系统级程序开发，最大代码量1w行左右C+是面向对象（ Object-oriented ）的程序设计语言，适合于大规模级别的应用开发，是当今软件行业首选的程序设计语言之一学习C/C+的好处:了解一门行业推崇的程序设计语言；了解面向对象的软件工程系统设计概念。C 是C+的子集，C+包含过程性语言部分和面向对象语言部分，C就是过程性语言部分

3、。2022/9/13P6(1.1)2、计算机的数和编码系统：(1)二进制人们最习惯和熟悉的计数和运算方式是十进制，即逢十进一。而计算机内数是以 二进制 0 和 1 来表示的。故存在现实与计算机中数表示方式的转换。同十进制数一样在计算机内部二进制数也有多位构成，彼此之间逢二进一，如同十进制数字的每一位都有一个权值（同样的1在不同数位上的取值），二进制数也是如此。可略2022/9/13P7(1.1)2、计算机的数和编码系统(cont.)例1：二进制位： b7 b6 b5 b4 b3 b2 b1 b0 0 1 0 1 1 1 1 0 权 值： 27 26 25 24 23 22 21 20 转换成1

4、0进制数 = b727 + b626 + b525 + b424 + b323 + b222 + b121 + b020 = 027 + 126 + 025 + 124 + 123 + 122 + 121 + 020 = 64 + 16 + 8 + 4 + 2 = 942022/9/13P8(1.1)2、计算机的数和编码系统(cont.) 把二进制数转换成十进制数的方法（称为二翻十运算）dec = bn12n1 + bn-22n-2 + .+ b12 + b0 式中，bn1、bn-2、.、b1、b0均为二进制数（二进制码元）。 若二进制数的位数为n(如8位)，n个bits可表示2n个不同的数，

5、无符号数数值范围是0 2n 1，如0 28 1 = 255，即所表示最大数值255的二进制码，其8个bits都是1。2022/9/13P9(1.1)2、计算机的数和编码系统(cont.) 位数越多表示数的动态范围越大，且最大数值再加1则n位都变成0，并向(n+1)位进位，称为“溢出”，这就是说n位二进制数已装满了，则溢出一个2n 数值后，再从零开始计数。 十六进制和八进制数：由于二进制数较长，阅读和书写困难，且容易出错，而且4位二进制数可以用一位十六进制数来表示，3位二进制数对应一位八进制数，它们之间具有直接的、唯一的对应关系如下表所示2022/9/13P10(1.1)2、计算机的数和编码系统

6、(cont.) 十进制 二进制 十六进制 八进制 0 0000 0 0 1 0001 1 1 2 0010 2 2 3 0011 3 3 4 0100 4 4 5 0101 5 5 6 0110 6 6 7 0111 7 7 8 1000 8 10 9 1001 9 11 10 1010 A 12 11 1011 B 13 12 1100 C 14 13 1101 D 15 14 1110 E 16 15 1111 F 172022/9/13P11(1.1)2、计算机的数和编码系统(cont.) 从表中可知，二进制数和十六进制数之间的转换非常简捷方便，即4位二进制数可以用一位十六进制数来表示。

7、例如：94 = 0101,1110 = 5E（H）其中，H是Hexadecimal（十六进制的）第1个字母，在计算机的教材中用以表明十六进制数。但在代码中常写成0X5E. 十六进制数转换成十进制数：为了简便，我们讨论4位十六进制数的转换情况，（因为我们通常用4位16进制数表示段内偏移地址码）dec=hex3163+hex2162+hex116+hex0例如：0 x80AF= 8163+ 0162+A16+F = 32768+0+160+15 = 32943 八进制类推2022/9/13P12(1.1)2、计算机的数和编码系统(cont.)（3）二进制数的原码、反码和补码：以上的整数都是无符号整

8、数，考虑带符号的整数在计算机内如何表示呢 正号和负号如何表示通常取一个二进制数的最高位为符号位，1表示负号，0表示正号。例如，一个8bits二进制数的最高位是b7，其后7个bits是它的数值，一个16bits二进制数的最高位是b15，其后15bits是它的数值。这种表示法叫原码反码：正数的反码和原码相同；负数的反码是对原码符号后面二进制码各位取反(即将“0”变为“1”，“1”变为“0”)。？2022/9/13P13(50)10的八位二进制原码为(00110010)原(50)10的八位二进制原码为(10110010)原(156)10的十六位二进制原码为 (0000000010011100)原(1

9、56)10的十六位二进制原码为 (1000000010011100)原(1.1)2、计算机的数和编码系统(cont.)为什么要用16位二进制码来表示？2022/9/13P14(1.1)2、计算机的数和编码系统(cont.)(50)10的八位二进制原码为(00110010)原(50)10的八位二进制原码为(10110010)原(50)10的八位二进制反码为(00110010)反(50)10的八位二进制反码为(11001101)反50+（-50）= ？2022/9/13P15(1.1)2、计算机的数和编码系统(cont.)在计算机中，数的处理和存储形式既不是原码也不是反码，而是数的二进制补码！规则

10、：正数的补码和原码相同；负数的补码是在该数的反码的最低位加1。求负运算变补运算，即：求出负号后面数的码按位取反1，如果负号后面的数还是负数，则递归地求出该负号后面的数的码按位取反+1。减法运算用加法来实现（补码相加）。参与运算的所有数都以补码形式表示。在内存中以补码来保存。2022/9/13P16(1.1)2、计算机的数和编码系统(cont.)(50)10的八位二进制原码为(00110010)原(+50)10的八位二进制反码为 (00110010)反(50)10的八位二进制补码为(00110010)补(50)10的八位二进制原码为(10110010)原(50)10的八位二进制反码为(11001

11、101)反(50)10的八位二进制补码为(11001110)补m个bits带符号的数可表示2m个二进制数，其数值范围：-2m-1 2m-1-1，如-27 27-1=-128 1272022/9/13P17为什么要引入反码和补码？根据带符号数的原码表示法可知：绝对值相同的正负两数，其数值位相同，仅最高位（即符号位）不同。这种表示法对带符号数的运算来讲不方便，甚至产生问题。比如：+94和-94相加或者94-94这样的减法运算，正确的结果应该是0，而原码表示法的结果却不为0。为了把减法运算转换成带符号数的加法运算，引入了反码和补码的概念。2022/9/13P181.1 C语言的入门知识1、何为程序设

12、计？C+语言有何用？2、计算机的数和编码系统：3、计算机的基本原理4、程序设计语言(1)存储程序式计算机原理（冯纽曼VonNeumann式计算机原理） 原理：计算机在开始特定的工作时（比如计算），将预先准备好的程序代码（指可执行代码，而不是源代码）和数据通过一定的方式送到有记忆功能的组件内存储器中保存起来，按一定顺序存储，计算机工作时，只要知道程序中第一条指令存放的地址单元，就能顺序依次取出每一条指令加以识别，并执行指令所规定的操作，达到相应控制或计算的目的。2022/9/13P19(1.1)3、计算机的基本原理：在CPU（中央处理机）中识别外设2022/9/13P20(1.1)3、计算机的基

13、本原理：计算机系统的层次结构图主机外部设备外存储器控制台内存储器Memory中央处理单元CPU输入/输出接口地址总线数据总线控制总线执行程序在运行前会被加载到内存储器；程序运行过程中的变量数据和状态值也保存在内存储器中。主机外部设备外存储器控制台内存储器Memory中央处理单元CPU输入/输出接口地址总线数据总线控制总线执行程序在运行前会被加载到内存储器；程序运行过程中的变量数据和状态值也保存在内存储器中。执行程序在运行前会被加载到内存储器；程序运行过程中的变量数据和状态值也保存在内存储器中。2022/9/13P21(1.1)3、计算机的基本原理：(2)计算机组成和层次结构2022/9/13P

14、22(1.1)3、计算机的基本原理：计算机系统的层次结构图2022/9/13P231.1 C语言的入门知识1、何为程序设计？C+语言有何用？2、计算机的数和编码系统：3、计算机的基本原理4、程序设计语言2022/9/13P24(1.1)4、程序设计语言：（1）汇编语言 读写难、维护难便于记忆代码需具体机器 指令系统支持 代码复杂、编程效率低；代码紧凑，执行效率高 便于移值机器语言汇编语言高级语言2022/9/13P25机器语言汇编语言C 语言高级语言翻译成机器语言后，方能在宿主机器中运行，这个翻译过程称作“编译”2022/9/13P26(1.1)4、程序设计语言：MCS51系列单片（微型计算）

15、机的指令系统中的机器及汇编指令： 机器码指令 汇编指令 操作内容 0000 ，0100(04H) INC A A + 1 A 0000 ，1110(0EH) INC R1 R1 + 1 R1 INC A（INC为单词Increment的缩写），其操作含义是把累加器A的内容（所存放的数据）增1后再放回A 2022/9/13P27(1.1)4、程序设计语言：命令1：将a放入寄存器eax中（ebp是数据段指针，a_$是变量 a的偏移位置）mov eax,DWORD PTR a_$ ebp 8b 45 fcmov ecx,DWORD PTR b_$ ebp8b 4d f8add ecx,ecx03 c

16、9sub eax,ecx2b c1Inc eax40mov DWORD PTR a_$ ebp,eax89 45 fc特点：晦涩、难懂、程序复杂工作量大；语言越低级，越靠近机器；语言越高级越靠近人的表达和理解。2022/9/13P28(1.1)4、程序设计语言：(2)高级语言:比如：Fortran、Basic、Pascal(ObjectPascal) 、C/C+、Java等 特点：引入数据类型和方便的流程控制，以及更接近人的思维模式的程序设计语句。 不局限于机器硬件，而且不要求对硬件有过多的理解； 属于高级语言有相应的数据类型，还有流程控制语言成分；程序易读、易维护，编程工作量相对汇编语言低很

17、多； 代码移植性较好； 代码冗余量大，程序执行效率较低（有的高级语言上是先编译成汇编语言代码，再编译成机器码）。对应前面的汇编指令用C语言表达：a =a2*b+12022/9/13P291.2 C/C+语言的发展及特点1.2.1 C/C+语言的发展过程 C/C+语言是目前世界上流行最广泛的通用程序设计语言。C语言的发展过程可粗略地分为三个阶段：1970年至1973年为诞生阶段，1973年至1988年为发展阶段，1988年以后为成熟阶段 。 C语言的发展过程如下： 1960年：ALGOL 1963年：CPL 1967年：BCPL 1970年：B（托马森） 1972年：C （里奇）贝尔实验室 80

18、年代：C+（Bjarne Stroustrup ）贝尔实验室1983年，ANSI制定了ANSI C标准；2022/9/13P301.2 C/C+语言的发展及特点1.2.1 C/C+语言的发展过程 C/C+是目前世界上流行最广泛的通用程序设计语言。C语言的发展过程可粗略地分为三个阶段：1970年至1973年为诞生阶段，1973年至1988年为发展阶段，1988年以后为成熟阶段 。 C语言的发展过程如下： 1960年：ALGOL 1963年：CPL 1967年：BCPL 1970年：B 1972年：C贝尔实验室 80年代：C+（Bjarne Stroustrup ）贝尔实验室1983年，ANSI制

19、定了ANSI C标准；1987年，ANSI又公布了87 ANSI C标准 ，明确定义了与机器无关的C语言（美国国家标准化协会）2022/9/13P311.2 C+语言的发展及特点1.2.1 C/C+语言的发展过程(cont.)Kernighan和Ritchie合编的The C Programming Language（1988版）详细介绍了ANSI C的全部内容，这本书成为最成功的计算机学术著作之一1990年，ISO国际标准化组织接受了87ANSI C为ISO 标准（ISO9899-1990）1998年ISO国际标准化组织颁布了C+程序设计语言的国际标准ISO/IEC 1488-1998200

20、3更新的C+标准：ISO/IEC 14882:2003 2022/9/13P321.2.2 C/C+语言的特点1. 介乎于高级语言和汇编语言之间，兼有两者的优点。2. 引用结构化程序架构，便于软件工程化。语言简洁(目标代码和源代码都很简洁)，且表达能力强，使用灵活，易于学习和应用。编译系统小巧（关键字个数、输入输出功能非语法成分、数据类型和流程控制结构的最佳组合）5. 可移植性好 。2022/9/13P33 C/C+是一个杰出的程序设计语言，一方面，C/C+的语法限制不太严格，程序设计自由度大，它给程序员无限的自由空间去随意的运用该语言而不受系统约束，就象前面的数据类型可以随意转换，数组下标可

21、以越界，可以任意访问任一内存段等等，这是受批评最多的，但也是最受人喜爱的地方，它使得C /C+较之一个更严谨更完善，而有更多限制的语言更有市场。 灵活和限制：2022/9/13P34灵活和限制： （cont.）指针是C/C+自由和灵活的象征，指针类型可以使程序员访问机器系统的所有地址空间，而不正确使用指针则会导致用户程序的错误运行，甚至更严重的情况是造成整个系统的崩溃。正是指针的使用特殊性，C/C+的语法中对指针的类型检测进行了严格的限制。不同类型的指针不能参与运算、赋值等。2022/9/13P35灵活和限制： （cont.）C/C+语言的灵活性可以使程序员编制任何类型的程序。但是灵活也会使程

22、序员为此付出代价：由于C/C+语法定义和检测较松，程序设计自由度大，使得对程序员的要求较高，Pascal和其它高级语言都通过严格的语法检查来保证程序的正确性，而C /C+则放宽了语法检查（典型的例子不对数组下标的越界进行语法检查），这就要求程序员要熟练掌握C /C+的语法规则，仔细检查所编程序，确保其正确无误，而不要过分地依赖C /C+编译器的查错功能。2022/9/13P36结构化编程 VS 面向对象编程过程性语言和面向对象的语言C语言诞生初期，结构化程序设计盛行，精巧设计的C语言满足用户高效执行、低成本系统移植等需求。但随着开发规模的扩大，其不能很好描述现实世界中对象的缺点造成了诸如代码维

23、护、重用甚至代码设计等困难C+应运而生恰恰是顺应大规模应用的开发，用类(class)类型和对象来对应现实世界中的物体，更好地设计描述现实世界的应用程序，方便了代码重用和代码维护2022/9/13P371.3 C/C+语言程序书写格式和结构特点 1.3.1 C/C+语言程序的书写格式2022/9/13P38【例】 /example.cpp#include int max(int,int); int main(void) int a,b,c; cinab;/从标准输入设备读取数据存进变量a和b c=max(a,b); cout“max =”c=y) z=x; else z=y; return z;

24、 语句结束符注释符编译预处理指令函数原型说明语句定义变量赋值语句，函数调用函数定义函数定义程序执行出口main函数是整个程序执行入口点标准输出流类的对象 cout标准输入流类的对象 cin、是流插入操作符2022/9/13P39 #include /预编译指令不是语句，没有分号 int max(int,int) ;/语句以分号结尾，如函数原型语句 int main(void) int a,b,c; std:cinab; /std为名字空间，在iostream中定义 c=max(a,b); std:cout“max =”c=y) z =x; else z =y; return z; 标准C+诞生

25、前的用法： #include 标准C+： #include 放进名字空间std中2022/9/13P40可以看出，C/C+语言程序有以下若干格式特点 ：C/C+语言程序习惯上使用小写英文字母。C/C+语言程序也是由一个个的语句组成。C/C+语言程序使用分号；作为语句的终止符或分隔符。一般情况下，每个语句占用一个书写行的位置。C/C+语言程序中用大括弧对 ，表示程序的结构层次范围。C/C+语言程序中，为了增强可读性，可以使用适量的空格和空行。2022/9/13P41标准C+库中标识符从属于std名字空间，注意特殊的访问格式#include using std:cout; using std:ci

26、n; using std:endl; int main() / cout number1 number2; / 从键盘读入2个数据 / return 0; #include using namespace std; int main() / cout number1 number2; /读入数据 / return 0; 2022/9/13P421.3.2 C/C+语言程序的结构特点例1.2 C/C+语言程序结构特点（下面代码使用了标准C的输入输出库函数） #include /标准C的输入输出头文件stdio.h int max(int,int) ; int main(void) int a,b

27、,c; scanf(“%d %d”,&a,&b); /scanf库函数在stdio.h中定义，与cin等价 c=max(a,b); printf(“max =%dn”,c); / printf库函数在头文件stdio.h中定义，与cout等价 return 0； int max(int x,int y) int z; if(x=y) z =x;else z =y; return z; 函数定义头函数定义体2022/9/13P43从上面程序可看出：（1）C/C+语言程序的执行是从主函数开始的，主函数中的所有语句执行完毕，则程序执行结束。（2）main函数之外的其它函数都是在执行main函数时，通

28、过嵌套调用得以执行的，在程序中除了可以调用用户自己编制的函数外，还可以调用由系统提供的标准库函数，如scanf、printf 。2022/9/13P44C/C+程序基本结构小结：（1） C/C+程序的组成： 一个C/C+程序可以由若干个函数定义构成，其中必须有且只能有一个以main命名的主函数。（2） 函数定义的组成： 函数定义是一个独立的程序块，相互不能嵌套。 一个函数定义由两个部分组成：函数头和函数体。查看案例2022/9/13P45(3) C/C+标准函数 C/C+函数分为两类： 标准函数 用户定义函数 用户定义函数是由程序员在自己的源程序中编写的函数。 标准函数是由C/C+编译程序提供

29、的一些通用函数，C/C+标准函数又称为C/C+库函数。 用户程序需要使用标准函数时，需要使用前用 # include包含该标准函数所需的系统头文件即可。2022/9/13P461.4 C/C+语言的基本语法单位 1.4.1 标识符 1.4.2 关键字 1.4.3 分隔符 1.4.4 常量2022/9/13P471.4.1 标识符1.标识符:在高级语言程序中由用户(即程序员)或编译程序(有时称系统)定义的常量、变量、数据类型、函数、过程和程序等的名字。2.标识符的组成规则 :由字母、下划线和数字(09)组成，其第一个字符必须是字母或下划线。 字母要区分大小写；下划线_被作为一个字符看待。3. 标

30、识符的有效长度：能够被编译程序识别的标识符的字符的数目称为标识符的有效长度。标准C规定标识符的有效长度为31。注意：标识符不能与关键字同名。2022/9/13P481.4.2 关键字 关键字由固定的小写字母组成，是系统预定的名字，用于表示C/C+语言的语句结构、数据类型、存储类型或运算符。关键字又称为保留字 。标准C定义的32个关键字如下（C+在C基础上扩充到63个）：auto break case char constcontinuedefaultdodoubleelseenumexternfloatforgotoifintlongregisterreturnshortsignedsizeo

31、fstaticstructswitchtypedefunionunsignedvoidvolatilewhile2022/9/13P491.4.3 分隔符 分隔符：包括空格符、制表符、换行符、换页符及注释符。程序中两个相邻的标识符、关键字和常量之间必须用分隔符分开(通常用空格符，逗号符等)。1.4.4 常量（文字量） 文字量: 程序中其数值不发生变化的量.C/C+语言中的常量有三类:数,字符和字符串 。此外,C/C+语言中还经常使用两种表现形式不同的常量:换码序列（又叫转义序列符）和符号常量.。常量的类型是由常量的文字自身隐含说明的 。2022/9/13P501.5 简单的输入与输出 一个完整

32、的计算机程序,常常要求具备输入输出功能.C/C+语言本身没有配备完成输入输出的语句.C/C+语言程序的输入输出功能是通过调用系统提供的标准函数实现的 。2022/9/13P511.5.1 格式化输入输出函数 格式化输入输出函数是按指定的格式完成输入输出过程. 1. 输出函数printf( ) 输出函数printf( )的一般使用形式如下: printf(“输出格式”,输出项系列);调用前必须在程序开头加上头文件包含include 2022/9/13P52（1）printf( )函数的功能是按照给定的输出格式、把输出项输出到标准输出设备，输出格式中用%打头后面跟有一个字母的部分称为转换说明符。

33、%d、%u 十进制整数 %x 十六进制整数 %o八进制整数 %f 、%e、%g 浮点小数（实数） %c 单一字符 %s 字符串例:printf(“v=%fn”,v); %f可以理解为：占位符2022/9/13P53（2）输出格式中除转换说明符以外的其它字符都原封不动地输出到标准输出设备显示器上。其中以打头后跟一个字母或数字的部分称为换码序列。它们的作用是输出控制符号和特殊字符，如上述输出格式中的n是回车换行的控制代码 。 有关换码系列的内容将在在第二章详细介绍。2022/9/13P54(3)使用printf()函数可以有一个以上的输出项，这时输出格式中的转换说明符与输出项的个数必须相同。它们按

34、各自的先后顺序一一对应。如下所示：printf(. %d %x %f, a, b, c);printf(. %d %x %f, a, b, c);2022/9/13P552输入函数scanf( )输入函数scanf( )的一般使用形式如下： scanf(输入格式，输入项系列);调用前包含头文件stdio.h行缓冲输入，需要敲入回车键。(1)输入格式串中一般只使用转换说明符，否则容易出错。(2)输入项必须是地址量，(变量名前加上&表示变量的地址)。2022/9/13P56(3) 输入分隔符的指定。在双引号包围的输入格式中，两个转换说明符%之间出现的字符就是他们对应输入项之间的分隔符。 如scan

35、f(%d:%d,&a,&b);这时输入的数据之间必须有分隔符，例如输入3和5，则实际输入时一定要输入3:5(4) 输入长度的给定 如 scanf(%4d%2d%2d”,&a,&b,&c); 假设一个输入序列为：19900125 则a=1990,b= 1,c=25(5) 输入数据时，遇到下列情况时该数据认为结束 a.遇空格、回车或者tab键 b.遇宽度结束，如“%3d”只取输入项三列 c.遇非法输入结束。2022/9/13P571.5.2 字符输入输出函数 字符输入输出函数是以一个字节的字符代码为单位完成输入输出过程的。字符输入函数getchar( )包含头文件stdio.h。行缓冲输入。 ge

36、tchar( )的功能是从键盘读入一个符号。在程序中必须用另一个变量接收读取的符号对应的代码值，如下所示： c=getchar( ); getchar（c）；/2022/9/13P582. 字符输出函数putchar( )包含头文件stdio.hputchar的功能是输出一个字符到标准输出设备（如：显示器）显示，它的常用调用格式如下： putchar(c);或putchar(c); 它把变量c的值作为ASCII编码值，把与该编码值对应的字符符号输出到标准输出设备显示;后者直接输出小写字母c 2022/9/13P591.5.3 字符串输入输出函数1、gets() 包含stdio.h头文件 调用格

37、式： char str33; gets(str); 功能：实现从标准输入设备中读入一个以回车换行符为结尾的字符串，将回车换行符n转换成空字符0，送入字符数组str中。 说明：一种行缓冲输入，用户敲入回车，函数才开始提取数据。提取的数据被当做字符串。2022/9/13P602、puts() 包含stdio.h头文件 调用格式： 1、puts(“Hello!”);注：输出完 Hello!后会自动回车到下一行 2、char string100 =“This is an example of out-putting string !”; puts(string);功能：实现字符串在外设上输出显示。把str数组中的字符串输出到标准输出设备上，并将隐含的0 转换为回车换行操作。2022/9/13P611.5.4 流输入输出控制一、标准流 标准输入输出流控制是C+中引入的，在这里我们只作一个简单的介绍。在C中标准输入设备是键盘，设备名为 stdin，标准输出设备为显示器，设备名为stdout；在C+中同样的输入输出设备，其设备名对应为cin与cout，它们实际上是C+中 类istream和类ostream的对象。 I / O流是实际输入输出的一系列字