数据结构：数组 (Array).ppt

《数据结构：数组 (Array).ppt》由会员分享，可在线阅读，更多相关《数据结构：数组 (Array).ppt（134页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、程序设计-2018秋,1,课程网站http:/ Wirth(Is Nih-klaus Virt, not Nickles Worth),2019/10/23,程序设计-2018秋,4,Niklaus Wirth,1959年获ETH学士学位；1963年获UC Berkely博士学位1963 1967在Stanford任教，后短期在 University of Zurich任教。 1968年成为 ETH教授主要贡献程序设计语言：Euler, Algol-W, Pascal, Modula等结构化程序设计1984年图灵奖获得者/1988年IEEE先驱奖获得者1994年当选美国工程院外籍院士,2019

2、/10/23,程序设计-2018秋,5,姚期智（Andrew Chi Chih Yao）,2019/10/23,程序设计-2018秋,6,姚期智（Andrew C. Yao）,1967年获得台湾大学物理学士学位1972年获得美国哈佛大学物理博士学位1975年获得美国伊利诺依大学(UIUC)计算机科学博士学位1975年至1986年曾先后在美国麻省理工学院数学系、斯坦福大学计算机系、加利福尼亚大学伯克利分校计算机系任助教授、教授1986年至2004年在普林斯顿大学计算机科学系担任Wiliam and Edna Macaleer工程与应用科学教授；2004起在清华大学任教；2009年提出“中国计算科

3、学2020计划”1998年当选为美国科学院院士；2000年当选为美国科学与艺术学院院士，获图灵奖；2004年当选为中国科学院外籍院士2017年加入中国籍，成为中国科学院院士,2019/10/23,程序设计-2018秋,7,提要,C语言中的数据类型常量与变量整型数据字符型数据实型数据基本数据类型混合运算和类型转换数据运算表达式和表达式语句,2019/10/23,程序设计-2018秋,8,提要,C语言中的数据类型常量与变量(Constant & Variable)整型数据(Integer)字符型数据(Character or Char)实型数据(Real)基本数据类型混合运算和类型转换数据运算(O

4、peration)表达式(Expression)和表达式语句,2019/10/23,程序设计-2018秋,9,C语言中的数据类型,基本类型整型字符型实型(浮点型):单精度型、双精度型指针类型复合类型数组类型结构类型联合类型: union枚举类型: enum自定义类型,2019/10/23,程序设计-2018秋,10,提要,C语言中的数据类型常量与变量整型数据字符型数据实型数据基本数据类型混合运算和类型转换数据运算表达式和表达式语句,2019/10/23,程序设计-2018秋,11,常量与变量,常量（constant）：在程序运行过程中，其值不能被改变的量变量：在程序运行过程中，其值可以改变的量

5、构成：变量类型、变量名、变量值,2019/10/23,程序设计-2018秋,12,变量（Variable）,C规定在程序中所有用到的变量都必须在程序中定义C中变量对大小写敏感变量的定义一般是在一个函数开头的声明部分也可放在函数中某一段程序内，但其作用域只限于其所在的程序段,2019/10/23,程序设计-2018秋,13,提要,C语言中的数据类型常量与变量整型数据字符型数据实型数据基本数据类型混合运算和类型转换数据运算表达式和表达式语句,2019/10/23,程序设计-2018秋,14,整型数据,整型数据按其数值范围划分成三种基本型、短整型、长整型按其内部表示的最高位的不同理解，可分为两类带符

6、号整型（最高位为符号位）、不带符号整型带符号整型的标记方法基本型：用 int 标记短整型：用 short int 标记，简写为 short长整型：用 long int 标记，简写为 long,2019/10/23,程序设计-2018秋,15,整型数据（续）,不带符号整型指存储一个整数的存储单元中的全部二进位都用作存放数据本身，而不存储符号位不带符号整型的标记方法不带符号的基本型：unsigned int不带符号短整型：unsigned short不带符号长整型：unsigned long,2019/10/23,程序设计-2018秋,16,整型数据（续）,一般一个机器字（word）存放一个int

7、型整数；long型整数的字节数不小于int型整数的字节数；short型整数的字节数不多于int型整数的字节数如TURBO C，短整型整数和基本型整数是2个字节，16个二进位；长整型整数为4个字节，32个二进位。在VC中，基本型整数和长整型整数都为4个字节,2019/10/23,程序设计-2018秋,17,整型数据（续）,在机器内部，负整数是以补码(complement) 表示的采用补码，是为了简化计算负数的补码计算将该数的绝对值的二进制形式，1）按位取反；2）加1,2019/10/23,程序设计-2018秋,18,整型数据（续）,整数表示的数值范围用16个二进位（2 bytes）存储一个整数带

8、符号整数的数值范围是：-32768 32767不带符号整数的数值范围是：0 65535若用32个二进位存储一个整数带符号整数的数值范围是2147483648 2147483647不带符号整数的数值范围是0 4294967295,2019/10/23,程序设计-2018秋,19,整型数据（续）,signed vs. unsigned,2019/10/23,程序设计-2018秋,20,整型数据（续）,=-1,=-32768,2019/10/23,带符号的整数（2 bytes）,程序设计-2018秋,21,整型数据（续）,不同类型的13,2019/10/23,程序设计-2018秋,22,整型数据（续

9、）,整型常量的书写形式有三种十进制整数：如 0，123，-45八进制整数：以数字符0开头，并由数字符07组成的数字符序列。如0123表示八进制整数，其值等于十进制整数：1*82 + 2*81+ 3 = 83十六进制整数 表示十六进制数的数字符有 16 个，它们分别是 09 和 A、B、C、D、E、F，其中六个字母也可以小写。以0x(或0X)开头，并由十六进制数的数字符组成的数字符序列如0x123表示十六进制整数，其值等于十进制整数： 1*162 + 2*161 + 3 = 2910xabc，其值等于10*162 + 11*161 + 12 = 2748,2019/10/23,程序设计-2018

10、秋,23,将任意进制数转换为10进制数,N 代表一个10进制的正整数r 是这个数制的基(Radix)10进制，r=108进制，r=8i 表示这些符号排列的位号Di 是位号为i的位上的一个符号ri 是位号为i的位上的 1 代表的值Di*ri 是第i位的所代表的实际值 表示m+k+1位的值求累加和例如：0x123= 1*162 + 2*161 + 3 = 291,2019/10/23,程序设计-2018秋,24,整型数据（续）,十进制与其它进制正整数的转换w进制数据到十进制数据的转换w进制的数据a1a2an转换为十进制数：a1wn-1+ a2wn-2 +an-1w+an十进制数据到w进制数据的转换

11、十进制的数据a1a2am=b1wn-1+ b2wn-2 +bn-1w+bn如何求bi(i=1 n)？,2019/10/23,程序设计-2018秋,25,整型数据（续）,二进制数据向八进制、16进制数据转换16进制数据向八进制、二进制数据转换,2019/10/23,程序设计-2018秋,26,二到八或十六进制转换,二进制转到八进制 从小数点向左右三位一分组 (10 011 100 . 01)2 = ( 234 . 2 )8 二进制转十六进制 从小数点向左右四位一分组 (1001 1100 . 01)2 = ( 9C . 4 )16 0100,2019/10/23,程序设计-2018秋,27,十进

12、制转二进制,整数部分除2取余 小数部分乘2取整,5,2,1,0,0.625 * 2,1,0.25 * 2,0,0.5 * 2,1,0.0,除尽为止 1011,低,高,求得位数满足要求为止,2019/10/23,程序设计-2018秋,28,整型数据（续）,长整型常数和无符号整型常数表示Long型常数：在整型常数之后接上字母 L(或l)，即为long型常数例如：0L、132L等不带符号的整型常数：在整型常数后面接上字母 U(或u)，则指明该整数常数是 unsigned 型的。例如1U、122U等为指明不带符号的long型常数，则需在整型常数之后同时加上字母U和L，表明该整型常数是 unsigned

13、 long 型的例如：22UL、35LU 等,2019/10/23,程序设计-2018秋,29,整数的溢出,#include main() int a=32767，b; b=a+1; printf(%d，%d，a，b);运行结果为：32767，-32768,+,-,2019/10/23,前提是：int用2 bytes表示,程序设计-2018秋,30,提要,C语言中的数据类型常量与变量整型数据字符型数据实型数据基本数据类型混合运算和类型转换数据运算表达式和表达式语句,2019/10/23,程序设计-2018秋,31,字符型数据,字符型数据用于表示字符及其代表的值字符型数据的内部表示是字符的 AS

14、CII 代码(二进制形式)字符型数据的类型符用 char 来标记char c1, c2; /* 定义两个字符变量 */字符型数据占一个字节（8位二进位）表示，也可当作一个8位的整型数据,2019/10/23,程序设计-2018秋,32,字符型数据(续),字符a、b的存储,字符输出,2019/10/23,程序设计-2018秋,33,字符型数据(续),字符型常量是单个字符，它的书写方法：普通字符：用单引号括起一个字符，如 a特殊字符：用字符或字符列来标记，如 r 、 n 、t 。这种方法就能表示特殊字符，见后表回车符 r ：表示对当前行作重叠输出换行符 n ：使以后的输出从下一行首开始制表符 t

15、：使输出位置横向跳至下一个输出区开始列,2019/10/23,程序设计-2018秋,34,特殊字符表标记形式 功 能n 换行符(打印位置移到下一行首)t 制表符，横向跳格到下一个输出区首v 竖向跳格符b 退格r 回车(打印位置移到当前行的首)f 走纸换页 a 产生响铃声 反斜杠字符 单引号符 ” 双引号符 ”ddd ddd为1至3个8进制数字,以该值为ASCII码的字符xhh hh为1至2个16进制数字,以该值为ASCII码的字符,2019/10/23,程序设计-2018秋,35,字符型数据(续),打印机与显示屏输出的组织方法稍有不同打印机：仅当一行字符填满或遇换行符时才输出，即整行一次性输出

16、。当输出空格符或制表符时，作跳格处理，不用空格符填充显示器：逐个字符输出，空格符及制表符经过位置都用空格符输出,2019/10/23,程序设计-2018秋,36,实例,void main() printf( ab ct derftgn); printf(htibbj k);,打印结果：|f|a|b| |c| | | |g|d|e|h| | | | | | |j|i|k|,屏幕输出：|f| | | | | | | |g|d|e|h| | | | | | |j| |k|,注：每个表单元8个字符宽。,2019/10/23,程序设计-2018秋,37,字符型数据(续),字符型常量与字符串常量书写形式的

17、区别字符串常量是一对双引号括起来的字符序列I am a student.“China, a, $1234.00字符型常量a 与字符串常量”a”不同，不允许将字符串常量赋给字符变量字符型数据可与整型数据混合运算由于字符型数据以ASCII代码的二进制形式存储，它与整数的存储形式相类似。因此，在C程序中，字符型数据和整型数据之间可以通用，字符型数据与整型数据可混合运算。一个字符型数据可以用字符格式(%c)输出，显示字符本身；也可以用整数形式输出，显示字符的 ASCII 码值,2019/10/23,程序设计-2018秋,38,字符型数据(续),有些系统(如Turbo c)将字符变量中的最高位作为符号位

18、，也就是将字符处理成带符号的整数，即signed char型。它的取值范围是-128-127如果不想按有符号处理，可以将字符变量定义为unsigned char类型， 这时其取值范围是0-255。signed char 和unsigned char的含义及用法与signed int和unsigned int相仿， 但它只有一个字节,2019/10/23,程序设计-2018秋,39,字符串常量,C规定：在每一个字符串的结尾加一个“字符串结束标志”，以便系统据此判断字符串是否结束C规定以字符0作为字符串结束标志。0是一个ASCII码为0的字符，这是 “空操作字符”，不引起任何控制动作，也不是一个可

19、显示的字符如果有一个字符串“CHINA”，实际上在内存中是C H I N A 0，存储上包含6个字符，代表前5个字符，最后一个字符为0，输出时不输出0C中没有专门的字符串类型，如果想将一个字符串存放在变量中，必须使用字符数组,2019/10/23,程序设计-2018秋,40,实例,#include void main() char c1, c2; /* 定义两个字符型变量 */ c1 = 97; /* a的 ASCII 码值为 97 */ c2 = c1+1; /* 字符型与整型数据混合运算 */ printf(c1 = %c, c2 = %cn, c1, c2); printf(%cs AS

20、CII code = %dn, c2, c2); printf(“I am 100 Fudan.10n”); printf(“Shanghai0Beijing”); 程序输出： c1 = a, c2 = b bs ASCII code = 98 I am Fudan Shanghai,2019/10/23,100代表ASCII码为64的字符，即；10代表ASCII码为8的字符，退格；0代表字符串结束符。,程序设计-2018秋,41,提要,C语言中的数据类型常量与变量整型数据字符型数据实型数据基本数据类型混合运算和类型转换数据运算表达式和表达式语句,2019/10/23,程序设计-2018秋,4

21、2,实型数据,实型数据（real number）又称浮点数（float number）因计算机只能表示有限位的实数，故实型数据是实数的有限子集。实型数据有数值大小（范围）和有效位数多少（精度）两个方面实型有三种单精度实型:用float标记，单精度实型又称浮点型float x, y; 双精度实型:用double标记double result;长双精度实型:用long double标记long double z;,2019/10/23,程序设计-2018秋,43,实型数据(续),实型数据在内存中的存放形式系统把一个实型数据分成小数部分和指数部分，分别存放,2019/10/23,实型数据(续),单精

22、度浮点数使用32位来表示实数：31位是符号位；30位到23位这8位用于存放偏置指数（biased exponent）；22位到0位这23位存放有效数字（significant)。 将十进制实数转化为单精度浮点数步骤如下 将十进制实数转化为对应的二进制实数 将得到的二进制实数以类似于科学计数法的方法写出：+1.xxxxEyyyy；xxxx称为有效数字，yyyy称为指数实数若为正，31位为0；若为负，31位为1 将指数加上十六进制数7F得到偏置指数，然后将所得结果放到30位到23位的右边，左边补0 将有效数字放到22位到0位的左边，右边补0,2019/10/23,程序设计-2018秋,44,8.5

23、的二进制表示为：1000.1进一步地,用二进制的科学计数法表示为:1.0001*23,实型数据(续),2019/10/23,程序设计-2018秋,45,注：指数位采用“移位存储”方式，原始数+127,程序设计-2018秋,46,实型数据(续),计算机中，是用二进制数来表示小数部分以及用2的幂次来表示指数部分的在4个字节(32位)中，究竟用多少位来表示小数部分，多少位来表示指数部分，标准C并无具体规定，由各C编译系统自定不少C编译系统以24位表示小数部分(包括符号)，以8位表示指数部分(包括指数的符号)小数部分占的位(bit)数愈多，数的有效数字愈多，精度愈高；指数部分占的位数愈多，则能表示的数

24、值范围愈大,2019/10/23,程序设计-2018秋,47,实型数据(续),float 型实型数据在内存中占用4个字节(32个二进位)，约6-7个十进位有效数字，能表示绝对值最接近0的实数约为10的-38次方，最大的实数约为10的38次方double型实型数据占用8个字节(64个二进位)，15-16个十进位有效数字，能表示绝对值最接近0的实数约为10的-308次方，最大的实数约为10的308次方long double型实型数据占用16个字节(128个二进位)，18-19个十进位有效数字，能表示绝对值最接近0的实数约为10的-4392次方，最大的实数约为10的4392次方,2019/10/23

25、,程序设计-2018秋,48,实型数据(续),实型常量的一般书写格式正负号 整数部分 . 小数部分 指数部分其中，正负号可有可无，无正负号即为正实数；整数部分和小数部分都是十进数字符序列；指数部分是 e(或E)，接上正负号和十进数字符序列三条限制整数部分和小数部分可以任选，但不可同时都没有小数点和指数部分不可以同时都没有指数部分以1个e或者E开头，后跟一个整数合法的实型常数：7.、.457、1E5、1.5e-6 不正确的实型常数： E4、.E5、4.0E 用 f 标识 float 型常数；用l(或 L)标识 long double 型常数，而无后缀符的实型常数被认为是 double 型常数,2

26、019/10/23,程序设计-2018秋,49,实型数据(续),计算机接受的实型值与书写的实数会有一定的误差例如：float x = 111111.111，因x只有约7位有效数字，实数111111.111所对应的二进制形式中，超出存储位数的那些位就不会被存储由于实数运算的计算误差，两个数学上完全等价的计算公式，会因计算顺序不同，得到的两个结果不能保证相等常用判别两实数非常相近的表达式绝对误差 fabs(x-y) 1e-6相对精度 fabs(x-y) (int) 8,65536l - (int) 0,2019/10/23,程序设计-2018秋,66,类型转换(续),将unsigned int型数

27、据赋给long int型变量时，不存在符号扩展问题，只需将高位补0即可将一个unsigned类型数据赋给一个占字节数相同的整型变量(例如：unsigned int=int，unsigned long=long，unsigned short=short)，将unsigned型变量的内容原样送到非unsigned型变量中，但如果数据范围超过相应整型的范围，则会出现数据错误unsigned int a=65535; int b; b=a；结果是：b=-1,2019/10/23,程序设计-2018秋,67,类型转换(续),将非unsigned型数据赋给长度相同的unsigned型变量，也是原样照赋(连

28、原有的符号位也作为数值一起传送),main() unsigned a； int b=-1； a=b； printf(%u，a)； ,结果是：65535,2019/10/23,程序设计-2018秋,68,提要,C语言中的数据类型常量与变量整型数据字符型数据实型数据基本数据类型混合运算和类型转换数据运算表达式和表达式语句,2019/10/23,程序设计-2018秋,69,运算符的优先级和结合性,运算符的优先级指表达式求值时，如果存在多个运算符，则按运算符的优先级由高到低的次序计算。如大家习惯的“先乘除后加减”，表达式 x-y*z ，因 y 的左侧减号优先级低于 y 右侧乘号，上式相当于 x-(y*

29、z) 运算符的结合性是指运算分量对运算符的结合方向，是从左至右，或自右至左结合性确定了在相同优先级运算符连续出现时的计算顺序，或者说，当一个运算对象两侧运算符的优先级别相同时,运算对象与运算符的结合顺序算术运算符的结合性是从左至右的，即连续的加减或连续的乘除是从左向右计算赋值运算符的结合性是从右至左的，即连续的赋值运算是从右向左逐个计算赋值,2019/10/23,程序设计-2018秋,70,算术运算(Arithmetic Operation),种类：+(加)、-(减)、*(乘)、/(除)、%(求余)、+(取正)、-(取负)、+(自增)、-(自减)两个整数相除结果为整数，如 7/4 的结果为 1

30、求余运算符(%)要求参与运算的两个运算分量均为整型数据，如 5 % 3 的值为 2。一般来说，求余运算所得结果的符号与被除数的符号相同-5 % 3 的值为 -2，5 % -3 的值为 2 在 b0 的情况下，a = (a / b) * b + a % b加、减、乘、除和求余运算都是双目运算符，结合性都是从左至右的取正 (+) 和取负 (-) 是单目运算符，结合性是从右至左，优先级高于 +、-、*、/、% 等双目运算符,2019/10/23,优先级,算术运算：+/+、-/-；*、/、%；+、-,2019/10/23,程序设计-2018秋,71,程序设计-2018秋,72,前缀 +（Prefix

31、Increment）,前缀+的一般形式：+ + 变量基本类型变量指针变量数组的元素构造型变量的成分变量在+ + 变量中，变量的数据类型必须是整型或某种指针类型“+变量”先使变量值增加1个单位，并以新值为变量的结果,2019/10/23,程序设计-2018秋,73,前缀 +,若x是满足这种要求的变量，则 + x使变量x的值增大1个单位，并以x的新值作为表达式“+ x”的结果，它等价于x = x+1 一个单位的含义是如果 x 是整型的，则 +x 就是普通的解释：“x 的值比原值增加 1”如果 x 是指针，并且是指向数组的某个元素，则 +x 使它指向数组的后一个元素,2019/10/23,程序设计-

32、2018秋,74,后缀 + (Postfix Decrement),后缀+的一般形式是：变量 + +表达式“变量 +”运算结果是该变量的原来值，在确定了表达式结果之后，用与前缀 + 相同的方式增大该变量的值 1 个单位前缀 + 和后缀 + 都能使表达式所对应的变量的值增加 1 个单位，但是它们所代表的表达式的值却不相同前者是变量增加后的值，后者是变量还未增加的原先值,2019/10/23,程序设计-2018秋,75,前缀 + vs. 后缀 +,例如 i,j 为整型变量，且 i 现有值为 4，求 j = +i j = i+结果：都使变量i的值变为5，但使 j 的值为 5使 j 的值为 4,201

33、9/10/23,程序设计-2018秋,76,前缀 -,前缀-的一般形式是：- - 变量左值表达式与前述的意义一样与前缀+相似，不同的只是前缀 - - 使表达式所对应的变量的值减少(或后退)1个单位并以变量的新值为表达式“ 变量”的运算结果,2019/10/23,程序设计-2018秋,77,后缀 -,后缀-的一般形式是：变量 - -表达式与前述的意义一样后缀 - - 作用于表达式对应的变量时，以该变量的值作为表达式“变量 - -”的运算结果，即先取其值为结果，然后用与前缀 - - 相同的方式减少该变量1个单位,2019/10/23,程序设计-2018秋,78,+和-运算符,+和-运算符仅适用于变

34、量(赋值存储对象)，不能用于一般的数值表达式 4+ 或 (i+j)+ 都是不合法的+和-是带有副作用的运算符。不要在一个表达式中对同一变量多次使用这样的运算符如i =4，表达式(i+)+(i+)可能认为它的值为9(4+5)。然而在有些C系统中, 它的值为 8；表达式(+i)+(+i)的值为12。因为这些系统在处理 i+ 时，先使用 i 的原值计算整个表达式，然后再让i 连续两次自增处理 +i 时，在计算表达式值之前，先对 i 执行两次自增，然后才计算表达式,2019/10/23,程序设计-2018秋,79,+和-运算符（续）,函数调用中，多个实参表达式的求值顺序，因从左到右与从右到左的不同，会

35、产生不同的结果例子：设i为4，函数调用printf(%d %dn, i, i+)如参数表的求值顺序从左到右，则输出4 4反之，将输出5 4,2019/10/23,程序设计-2018秋,80,+和-运算符（续）,因 + 与 + ( - 与 - - 类似) 是两个不同运算符，对于类似表达式 i+j会有不同的理解(i+) + j 或 i + (+j)C编译的处理方法是自左至右让尽可能多的字符组成一个合法的句法单位(如标识符、数字、运算符等)。因此，i+j被解释成(i+) + j, 不是 i + (+j)自增(+)和自减(- -)运算符结合方向自右至左,2019/10/23,程序设计-2018秋,81

36、,关系运算（Relational Operation）,关系运算符(大于)、=(大于等于)、=(等于)、!=(不等于)关系运算符用于描述对两个值进行关系比较，判定比较条件是否满足在高级语言中，习惯称条件满足为“真”，不满足为“假”在C中，约定条件满足时，表达式的值为1；条件不满足为 0,2019/10/23,程序设计-2018秋,82,关系运算（续）,关系运算符的优先级：、= 高于 =，!=如表达式 x y = c y) = (c u+v 等效于 x (u+v)关系运算符的结合方向是自左至右,2019/10/23,优先级,算术运算：+/+、-/-；*、/、%；+、-关系运算：、=； =，!=,

37、2019/10/23,程序设计-2018秋,83,程序设计-2018秋,84,逻辑运算(Logical Operation),运算符：&(逻辑与)、|(逻辑或)、!(逻辑非)运算符 & 和 | 是双目运算符，要求有两个整型的运算分量，用于连接多个判定条件，构成更复杂的条件判定运算符 ! 是单目运算符，用于描述对给定条件的否定判定逻辑运算产生的结果也是一个真值或假值用1表示逻辑运算结果为真用0表示运算结果为假判定一个运算分量的值为真或假时，以运算分量的值不等于零为真，值等于0 为假,2019/10/23,程序设计-2018秋,85,逻辑运算优先级,逻辑运算符按优先级排列为! 、(&、|)& 和 | 的优先级低于关系运算符的优先级；! 的优先级高于算术运算符的优先级逻辑运算符|和&的结合方向是自左至右而逻辑运算符!的结合方向是自右至左,