山东大学软件工程硕士专业课C语言与数据结构考试大纲答疑.ppt

1、参考书目：C程序设计（第二版）谭浩强 清华大学出版社 数据结构（C语言版）严蔚敏 清华大学出版社,山东大学软件学院 2009年11月,程序设计与数据结构,大纲答疑,学习要点,填空题（每空1分，共20分） 简答题（每题5分，共40分） 论述题（每题10分，共30分） 编程题（每题10分，共10分） 注重基础知识点、重要的算法思想掌握 基本的编程能力 C程序设计：数据结构=6：4,知识范围,1.C语言概述 2.数据类型、运算符与表达式 3.顺序程序设计 4.分支结构程序 5.循环控制 6.数组 7.函数 8.指针 9.结构体与链表,10.数据结构概述 11.线性结构 12.栈与队列 13.树 14

2、.图 15.搜索 16.排序算法,1.源程序的结构特点,一个语言源程序可以由一个或多个源文件组成。 每个源文件可由一个或多个函数组成。 一个源程序不论由多少个文件组成，都有一个且只能有一个main函数，即主函数。 每一个说明，每一个语句都必须以分号结尾。 标识符、关键字之间必须至少加一个空格以示间隔。,9种控制语句： if( )else for( ) while( ) dowhile( ) continue break switch goto return,2.语言词汇,在语言中使用的词汇分为六类：标识符，关键字，运算符，分隔符，常量，注释符等。 标识符 在程序中使用的变量名、函数名、标号等统

3、称为标识符。除库函数的函数名由系统定义外，其余都由用户自定义。C 规定，标识符只能是字母(AZ，az)、数字(09)、下划线(_)组成的字符串，并且其第一个字符必须是字母或下划线。 (1)标准C不限制标识符的长度 (2)在标识符中，大小写是有区别的 (3)命名应尽量有相应的意义，作到“顾名思义”,语言词汇,关键字 关键字是由语言规定的具有特定意义的字符串，通常也称为保留字 运算符 语言中含有相当丰富的运算符。运算符与变量，函数一起组成表达式，表示各种运算功能 分隔符 常量 注释符,32个关键字：(由系统定义，不能重作其它定义) auto break case char const contin

4、ue default do double else enum extern float for goto if int long register return short signed sizeof static struct switch typedef unsigned union void volatile while,3.算法,一个程序应包括： 对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构（data structure）。 对操作的描述。即操作步骤，也就是算法（algorithm）。 Nikiklaus Wirth提出的公式：数据结构+算法=程序,算法的概念,做

5、任何事情都有一定的步骤。为解决一个问题而采取的方法和步骤，就称为算法。 计算机算法：计算机能够执行的算法。 计算机算法可分为两大类： 数值运算算法：求解数值； 非数值运算算法：事务管理领域。,4.三种基本结构的流程图,三种基本结构的流程图,5.结构化程序设计方法,自顶向下； 逐步细化； 模块化设计； 结构化编码,结构化程序设计,结构化程序设计的基本思想是采用“自顶向下，逐步求精”的程序设计方法。从问题本身开始，经过逐步细化，将解决问题的步骤分解为由基本程序结构模块组成的结构化程序框图.仅是由顺序、选择和循环三种基本程序结构通过组合、嵌套构成，那么这个新构造的程序一定是一个单入口单出口的程序。据

6、此容易编写出结构良好、易于调试的程序来 以模块化设计为中心，将待开发的软件系统划分为若干个相互独立的模块，这样使完成每一个模块的工作变单纯而明确，为设计一些较大的软件打下了良好的基础,结构化程序设计,由于模块相互独立，因此在设计其中一个模块时，不会受到其它模块的牵连，因而可将原来较为复杂的问题化简为一系列简单模块的设计。模块的独立性还为扩充已有的系统、建立新系统带来了不少的方便，因为我们可以充分利用现有的模块作积木式的扩展 按照结构化程序设计的观点，任何算法功能都可以通过由程序模块组成的三种基本程序结构的组合: 顺序结构、选择结构和循环结构来实现。,6. 数据类型,数据类型总表,数据类型决定：

7、 1. 数据占内存字节数 2. 数据取值范围 3. 其上可进行的操作,数据类型,基本数据类型：基本数据类型最主要的特点是，其值不可以再分解为其它类型 构造数据类型：构造数据类型是根据已定义的一个或多个数据类型用构造的方法来定义的： 数组类型 结构体类型 共用体（联合）类型 指针类型：指针是一种特殊的，同时又是具有重要作用的数据类型。其值用来表示某个变量在内存储器中的地址。,一般用大写字母 是宏定义预处理命令，不是C语句 直接常量: 整型常量 实型常量 字符常量 字符串常量,如 #define PRICE 30,常量 定义：程序运行时其值不能改变的量（即常数） 分类: 符号常量:用标识符代表常量

8、 定义格式： #define 符号常量 常量,例 符号常量举例(ch2_1.c) #define PRICE 30 main() int num,total; num=10; total=num*PRICE; printf(total=%d,total); ,运行结果：total=300,字符常量 定义:用单引号括起来的单个普通字符或转义字符.,字符常量的值：该字符的ASCII码值,如 101 -A 012 -n 376 - x61 -a 60 -0 483 -(),例: A-101-x41-65,如 A65， a97， 048 , n10,如 a A ? n 101,转义字符:反斜线后面跟一

9、个字符或一个代码值表示,例 转义字符举例(ch2_001.c,ch2_004.c) main() printf(101 x42 Cn); printf(I say:How are you?n); printf(C Programn); printf(Turbo C); ,运行结果：(屏幕显示) A B C Isay:”How are you?” C Program Turbo C,例 main() printf(“Yb=n”); ,运行结果： 屏幕显示：= 打印机输出：,字符常量与字符串常量不同,字符串常量 定义：用双引号(“”)括起来的字符序列 存储：每个字符串尾自动加一个 0 作为字符串结

10、束标志,例: char ch; ch=“A”;,字符串常量和字符常量区别,字符常量由单引号括起来，字符串常量由双引号括起来 字符常量只能是单个字符，字符串常量则可以含一个或多个字符 可以把一个字符常量赋予一个字符变量，但不能把一个字符串常量赋予一个字符变量。在语言中没有相应的字符串变量。用一个字符数组来存放一个字符串常量。在数组一章内予以介绍 字符常量占一个字节的内存空间。字符串常量占的内存字节数等于字符串中字数加1,变量概念：其值可以改变的量 变量名与变量值 变量与地址,程序中: int i; float k;,内存中每个字节有一个编号-地址,i,k,编译或函数调用时为其分配内存单元,变量是

11、对程序中数据 存储空间的抽象,变量定义的一般格式： 数据类型 变量1，变量2，变量n;,变量初始化:定义时赋初值,例: int a,b,c; float data;,决定分配字节数 和数的表示范围,合法标识符,例: int a=2,b,c=4; float data=3.67; char ch=A; int x=1,y=1,z=1; int x=y=z=1;,变量的使用：先定义，后使用,例1 int student; stadent=19; /Undefined symbol statent in function main,例2 float a,b,c; c=a%b; /Illegal us

12、e of floating point in function main,变量定义位置：一般放在函数开头,整型变量 占字节数随机器不同而不同,一般占一个机器字 shortintlong 可用sizeof(类型标识符）测量,实型变量 float：占4字节，提供7位有效数字 double：占8字节，提供1516位有效数字,字符型变量 字符变量存放字符ASCII码 char与int数据间可进行算术运算,例 float a; a=111111.111; /* a=111111.1*/ double b; b=111111.111; /* b=111111.111*/,例 a=D; /* a=68; *

13、/ x=A+5; /* x=65+5; */ s=!+G /* s=33+71; */,没有字符串变量，用字符数组存放,7.运算符和表达式,算术运算符和表达式 基本算术运算符： + - * / % 结合方向：从左向右 优先级： - -* / % - + - (2) (3) (4) 说明： “-”可为单目运算符时,右结合性 两整数相除，结果为整数 %要求两侧均为整型数据,例 5/2 = -5/2.0 =,例 5%2 = -5%2 = 1%10 = 5%1 = 5.5%2,例 5/2 = 2 -5/2.0 = -2.5,例 5%2 = 1 -5%2 = -1 1%10 = 1 5%1 = 0 5.

14、5%2 (),自增、自减运算符+ - 作用：使变量值加1或减1 种类： 前置 +i, -i (先执行i+1或i-1，再使用i值） 后置 i+,i- (先使用i值,再执行i+1或i-1）,例 j=3; k=+j; j=3; k=j+; j=3; printf(“%d”,+j); j=3; printf(“%d”,j+); a=3;b=5;c=(+a)*b; a=3;b=5;c=(a+)*b;,/k=4,j=4,/k=3,j=4,/4,/3,/c=20,a=4,/c=15,a=4,赋值运算符和表达式 简单赋值运算符 符号： = 格式： 变量标识符=表达式 作用：将一个数据（常量或表达式）赋给一个变

15、量,复合赋值运算符 种类：+= -= *= /= %= = = d=func(); c=d+2;,说明: 结合方向：自右向左 优先级: 12 左侧必须是变量，不能是常量或表达式,赋值表达式的值与变量值相等,且可嵌套,赋值转换规则:使赋值号右边表达式值自动转换成其左边变量的类型,例: a=12; a+=a-=a*a,例: int a=2; a%=4-1; a+=a*=a-=a*=3;,/a=-264 等价于a=a+(a=a-(a*a),/a=0 等价于a=a+(a=a*(a=a-(a=a*3),关系运算符和表达式 关系运算符 种类：= != 结合方向：自左向右 优先级别：,例 ca+b /c(a

16、+b) ab!=c /(ab)!=c a=bc /a=(bc),关系表达式的值：是逻辑值“真”或“假”，用1和0表示,例 int a=3,b=2,c=1,d,f; ab (ab)=c b+cb f=abc,/表达式值1,/表达式值1,/表达式值0,/d=1,/f=0,逻辑运算符和表达式 逻辑运算符 种类： ! ,例 (a=b)?Y:N (x%2=1)?1:0 (x=0)?x:-x (c=a x0,表达式值为a xy?1:1.5 /xy ,值为1.0; xy ,值为1.5,8.程序的三种基本结构,结构化程序设计 基本思想：任何程序都可以用三种基本结构表示，限制使用无条件转移语句（goto） 结构

17、化程序：由三种基本结构反复嵌套构成的程序叫 优点：结构清晰，易读，提高程序设计质量和效率 三种基本结构 顺序结构,选择结构,二分支选择结构,多分支选择结构,循环结构,当型循环结构,直到型循环结构,注：A,B,A1.An可以是一个简单语句，也可以是一个基本结构,格式：printf(“格式控制串”，输出表) 功能：按指定格式向显示器输出数据 返值：正常，返回输出字节数；出错，返回EOF(-1),9.格式输出函数,输出表：要输出的数据（可以没有，多个时以“,”分隔） 格式控制串：包含两种信息 格式说明： %修饰符格式字符 ，用于指定输出格式 普通字符或转义序列：原样输出 格式字符,格式输入函数,格式

18、: scanf(“格式控制串”，地址表） 功能：按指定格式从键盘读入数据，存入地址表指定的 存储单元中,并按回车键结束 返值：正常，返回输入数据个数,地址表：变量的地址，常用取地址运算符,10.分支控制语句,形式二： 格式：if (expression) statement1 else statement2 执行过程： 其语义是：如果表达式的值为真，则执行语句1，否则执行语句2,例：if (xy) max=x; else max=y;,形式三： 格式： 其语义是：依次判断表达式的值，当出现某个值为真时，则执行其对应的语句。然后跳到整个if语句之外继续执行程序。 如果所有的表达式均为假，则执行语

19、句n。然后继续执行后续程序,if ( expr1 ) statement1 else if (expr2 ) statement2 else if (expr3 ) statement3 . else statementn ,例：if (salary1000) index=0.4; else if (salary800) index=0.3; else if (salary600) index=0.2; else if (salary400) index=0.1; else index=0;,如：if(a=b,说明： if后面的表达式类型任意,语句可以是复合语句 if(x) if(x!=0)

20、if(!x) if(x=0),例 考虑下面程序的输出结果: #include main() int x,y; scanf(“%d,%d”, ,Compile Error!,if else 配对原则,缺省 时，else总是和它上面离它最近的未配对的if配对,switch语句（开关分支语句） 一般形式：,switch( 表达式) case E1: 语句组 1; break; case E2: 语句组 2; break; . case En: 语句组 n; break; default: 语句组 ; break; ,执行过程：,switch语句语义是：计算表达式的值。 并逐个与其后的常量表达式值相比

21、较，当表达式的值与某个常量表达式的值相等时， 即执行其后的语句，然后不再进行判断，继续执行后面所有case后的语句。如表达式的值与所有case后的常量表达式均不相同时，则执行default后 说明： 1) 在case后的各常量表达式的值不能相同，否则会出现错误。 2) 在case后，允许有多个语句，可以不用括起来 3) 各case和default子句的先后顺序可以变动，而不会影响程序执行结果 4)default子句可以省略不用,如： case A: case B: case C: printf(“score60n”); break; .,break语句,break语句，专用于跳出switch语

22、句，break 语句只有关键字break，没有参数。在后面还将详细介绍。在每一case语句之后增加break 语句， 使每一次执行之后均可跳出switch语句，从而避免输出不应有的结果。,例 switch(score) case 5: printf(“Very good!”); case 4: printf(“Good!”); case 3: printf(“Pass!”); case 2: printf(“Fail!”); default : printf(“data error!”); ,运行结果：score为5时，输出： Very good! Good! Pass! Fail! data

23、 error!,#include main() int c; printf(Enter m or n or h or other:); c=getchar(); switch(c) case m: printf(nGood morning!n);break; case n: printf(nGood night!n); break; case h: printf(nHello!n); break; default : printf(n?n); break; ,例 根据输入字母输出字符串,while语句 一般形式：,while(表达式) 循环体语句；,执行流程：,11.循环控制语句,while语

24、句,while语句的语义是：计算表达式的值，当值为真(非0)时， 执行循环体语句 特点：先判断表达式，后执行循环体 说明： 循环体有可能一次也不执行 循环体可为任意类型语句 下列情况，退出while循环 条件表达式不成立（为零） 循环体内遇break,return,goto 无限循环: while(1) 循环体;,例 用while循环求,#include main() int i,sum=0; i=1; while(i=100) sum=sum+i; i+; printf(%d,sum); ,dowhile语句 一般形式：,do 循环体语句； while(表达式);,执行流程：,for语句 一

25、般形式：,for(expr1 ; expr2 ; expr3) 循环体语句；,执行流程：,执行过程,1)先求解表达式1。 2)求解表达式2，若其值为真（非0），则执行for语句中指定的内嵌语句，然后执行下面第3）步；若其值为假（0），则结束循环，转到第5）步。 3)求解表达式3。 4)转回上面第2）步继续执行。 5)循环结束，执行for语句下面的一个语句。,for语句最简单的应用形式,for(循环变量赋初值；循环条件；循环变量增量) 语句 循环变量赋初值总是一个赋值语句, 它用来给循环控制变量赋初值; 循环条件是一个关系表达式,它决定什么时候退出循环；循环变量增量，定义循环控制变量每循环一次后

26、按什么方式变化。这三个部分之间用“；”分开。,辅助控制语句,break语句 break语句通常用在循环语句和开关语句中。当break用于开关语句switch中时,可使程序跳出switch而执行switch以后的语句.break在switch 中的用法已在前面介绍开关语句时的例子中碰到,这里不再举例。 当break语句用于do-while、for、while循环语句中时,可使程序终止循环而执行循环后面的语句, 通常break语句总是与if语句联在一起。即满足条件时便跳出循环。,辅助控制语句,continue 语句 continue语句的作用是跳过循环体中剩余的语句而强行执行下一次循环。conti

27、nue语句只用在for、while、do-while等循环体中,常与if条件语句一起使用,用来加速循环。,12.数组,在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来。这些按序排列的同类数据元素的集合称为数组。 构造数据类型之一 数组:有序数据的集合,用数组名标识 元素:属同一数据类型,用数组名和下标确定,1 一维数组 一维数组的定义 定义方式： 数据类型 数组名常量表达式；,合法标识符,表示元素个数 下标从0开始, :数组运算符 单目运算符 优先级(1) 左结合 不能用( ),例 int a6;,编译时分配连续内存 内存字节数=数组维数* sizeof(元素数据类型)

28、,数组名表示内存首地址， 是地址常量,一维数组的引用 数组必须先定义，后使用 只能逐个引用数组元素，不能一次引用整个数组 数组元素表示形式： 数组名下标 其中：下标可以是常量或整型表达式,例 int i=15; int datai; (不能用变量定义数组维数),例 int a10; printf(“%d”,a); () 必须 for(j=0;j10;j+) printf(“%dt”,aj); (),例 int data5; data5=10; /C语言对数组不作越界检查，使用时要 注意,一维数组的初始化 初始化方式,在定义数组时，为数组元素赋初值 (在编译阶段使之得到初值）,int a5=1,

29、2,3,4,5; 等价于：a0=1; a1=2; a2=3; a3=4; a4=5;,说明： 数组不初始化，其元素值为随机数 对static数组元素不赋初值，系统会自动赋以0值,当全部数组元素赋初值时，可不指定数组长度,如 int a5=6,2,3; 等价于： a0=6; a1=2;a2=3; a3=0; a4=0; 如 int a3=6,2,3,5,1; (),static int a5; 等价于：a0=0; a1=0; a2=0; a3=0; a4=0;,只给部分数组元素赋初值,int a=1,2,3,4,5,6; 编译系统根据初值个数确定数组维数,2 二维数组及多维数组 二维数组的定义

30、定义方式： 数据类型数组名常量表达式常量表达式；,数组元素的存放顺序 原因:内存是一维的 二维数组：按行序优先 多维数组：最右下标变化最快,例 int a34; float b25; int c234; int a3,4; (),行数,列数,元素个数=行数*列数,3 字符数组和字符串 字符数组 在语言中没有专门的字符串变量，通常用一个字符数组来存放一个字符串 定义,字符数组的初始化 逐个字符赋值 用字符串常量 字符数组的引用,例 char c10, ch34;,字符串 字符串及其结束标志 无字符串变量，用字符数组处理字符串 字符串结束标志：0,13.函数,函数是源程序的基本模块，通过对函数模块

31、的调用实现特定的功能 用户可把自己的算法编成一个个相对独立的函数模块，然后用调用的方法来使用函数。 可以说程序的全部工作都是由各式各样的函数完成的，所以也把语言称为函数式语言。,1) 函数的定义 一般格式,合法标识符,函数返回值类型 缺省int型 无返回值void,函数体,例 有参函数（现代风格） int max(int x,int y) int z; z=xy?x:y; return(z); ,例 无参函数 printstar( ) printf(“*n”); 或 printstar(void ) printf(“*n”); ,2) 函数的返回值,返回语句 形式： return(表达式)；

32、或 return 表达式; 或 return; 功能：使程序控制从被调用函数返回到调用函数中，同时把返值带给调用函数 说明： 函数中可有多个return语句 若无return语句，遇时，自动返回调用函数 若函数类型与return语句中表达式值的类型不一致，按函数类型为准，自动转换-函数调用转换 void型函数,例 无返回值函数 void swap(int x,int y ) int temp; temp=x; x=y; y=temp; ,3) 函数的调用,调用形式 函数名(实参表); 说明： 实参与形参个数相等，类型一致，按顺序一一对应 实参表求值顺序，因系统而定（Turbo C 自右向左）,

33、调用方式,函数语句： 例 printstar(); printf(“Hello,World!n”); 函数表达式： 例 m=max(a,b)*2; 函数参数： 例 printf(“%d”,max(a,b); m=max(a,max(b,c);,4) 函数参数及其传递方式 形参与实参 形式参数：定义函数时函数名后面括号中的变量名 实际参数：调用函数时函数名后面括号中的表达式,例 比较两个数并输出大者,main() int a,b,c; scanf(%d,%d, ,说明： 实参必须有确定的值 形参必须指定类型 形参与实参类型一致，个数相同 若形参与实参类型不一致，自动按形参类型转换函数调用转换 形

34、参在函数被调用前不占内存;函数调用时为形参分配内存；调用结束，内存释放,4) 函数参数及其传递方式 形参与实参 形式参数：定义函数时函数名后面括号中的变量名 实际参数：调用函数时函数名后面括号中的表达式,5)参数传递方式,值传递方式 方式：函数调用时,为形参分配单元,并将实参的值复制到形参中；调用结束，形参单元被释放，实参单元仍保留并维持原值 特点： 形参与实参占用不同的内存单元 单向传递,例 交换两个数,/*ch7_2.c*/ #include main() int x=7,y=11; printf(x=%d,ty=%dn,x,y); printf(swapped:n); swap(x,y)

35、; printf(x=%d,ty=%dn,x,y); swap(int a,int b) int temp; temp=a; a=b; b=temp; ,5)参数传递方式,地址传递 方式：函数调用时，将数据的存储地址作为参数传递给形参 特点： 形参与实参占用同样的存储单元 “双向”传递 实参和形参必须是地址常量或变量,/*ch9_3.c*/ swap(int *p1,*p2; ) int p; p=*p1; *p1=*p2; *p2=p; main() int a,b; scanf(%d,%d, ,例 交换两个数,6)函数的嵌套与递归调用 嵌套调用 C规定：函数定义不可嵌套，但可以嵌套调用函数

36、,7) 数组作为函数参数 数组元素作函数实参值传递,例 两个数组大小比较,n=0 m=0 k=0,a和b为有10个元素的整型数组 比较两数组对应元素 变量n,m,k记录aibi, ai=bi, aik,认为数组ab 若nk,认为数组ab 若n=k,认为数组a=b,数组名作函数参数 地址传递 在主调函数与被调函数分别定义数组,且类型应一致 形参数组大小(多维数组第一维)可不指定 形参数组名是地址变量,例 求学生的平均成绩,#include float average(int stu10, int n); void main() int score10, i; float av; printf(I

37、nput 10 scores：n); for( i=0; i10; i+ ) scanf(%d, ,float average(int stu10, int n) int i; float av,total=0; for( i=0; in; i+ ) total += stui; av = total/n; return av; ,实参用数组名,形参用数组定义, int stu ,14. 指针 1)变量与地址,程序中: int i; float k;,内存中每个字节有一个编号-地址,i,k,编译或函数调用时为其分配内存单元,变量是对程序中数据 存储空间的抽象,指针与指针变量 指针：一个变量的地

38、址 指针变量：专门存放变量地址的变量叫,2000,指针,指针变量,变量的内容,变量的地址, -直接访问,3,例 *i_pointer=20; -间接访问,20,2 )指针变量 指针变量与其所指向的变量之间的关系,指针变量的定义 一般形式： 存储类型 数据类型 *指针名；,合法标识符,指针变量本身的存储类型,指针的目标变量的数据类型,表示定义指针变量 不是*运算符,例 int *p1,*p2; float *q ; static char *name;,注意： 1、int *p1, *p2; 与 int *p1, p2; 2、指针变量名是p1,p2 ,不是*p1,*p2 3、指针变量只能指向定义

39、时所规定类型的变量 4、指针变量定义后，变量值不确定，应用前必须先赋值,指针变量的初始化 一般形式：存储类型 数据类型 *指针名=初始地址值；,赋给指针变量， 不是赋给目标变量,例 int i; int *p=,变量必须已说明过 类型应一致,例 int i; int *p=,用已初始化指针变量作初值,例 main( ) int i; static int *p= . (),不能用auto变量的地址 去初始化static型指针,指针变量作为函数参数地址传递 特点：共享内存,“双向”传递,swap(int x,int y) int temp; temp=x; x=y; y=temp; main()

40、 int a,b; scanf(%d,%d, ,例 将数从大到小输出,5,9,5,5,9,COPY,指针变量作为函数参数地址传递 特点：共享内存,“双向”传递,swap(int x,int y) int temp; temp=x; x=y; y=temp; main() int a,b; scanf(%d,%d, ,例 将数从大到小输出,值传递,5,9,运行结果：5, 9,swap(int *p1, int *p2) int p; p=*p1; *p1=*p2; *p2=p; main() int a,b; int *pointer_1,*pointer_2; scanf(%d,%d, ,5,

41、9,2000,2002,5,9,COPY,5,例 将数从大到小输出,swap(int *p1, int *p2) int p; p=*p1; *p1=*p2; *p2=p; main() int a,b; int *pointer_1,*pointer_2; scanf(%d,%d, ,5,9,2000,2002,5,9,例 将数从大到小输出,运行结果：9，5,地址传递,3) 指针与数组 指向数组元素的指针变量,例 int array10; int *p; p=,数组名是表示数组首地址的地址常量,数组元素表示方法, 变址运算符 ai *(a+i),ai pi *(p+i) *(a+i),例 数

42、组元素的引用方法,main() int a5,*pa,i; for(i=0;i5;i+) ai=i+1; pa=a; for(i=0;i5;i+) printf(*(pa+%d):%dn,i,*(pa+i); for(i=0;i5;i+) printf(*(a+%d):%dn,i,*(a+i); for(i=0;i5;i+) printf(pa%d:%dn,i,pai); for(i=0;i5;i+) printf(a%d:%dn,i,ai); ,指针的算术运算： pi p id (i为整型数，d为p指向的变量所占字节数) p+, p-, p+i, p-i, p+=i, p-=i等 若p1与p

43、2指向同一数组，p1-p2=两指针间元素个数(p1-p2)/d p1+p2 无意义,例 p指向float数，则 p+1 p+1 4,例 p指向int型数组，且p= 则p+1 指向a1,例 int a10; int *p=,例 int a10; int *p1=,1,4) 指针与字符串 字符串表示形式 用字符数组实现,例 main( ) char string=“I love China!”; printf(“%sn”,string); printf(“%sn”,string+7); ,用字符指针实现,例 main( ) char *string=“I love China!”; printf(

44、“%sn”,string); string+=7; while(*string) putchar(string0); string+; ,字符指针初始化:把字符串首地址赋给string char *string; string=“I love China!”;,*string!=0,15.结构体,1) 结构体 结构体是一种构造数据类型 用途：把不同类型的数据组合成一个整体-自定义数据类型 结构体类型定义,struct 结构体名 类型标识符 成员名； 类型标识符 成员名； . ；,成员类型可以是 基本型或构造型,struct是关键字, 不能省略,合法标识符 可省:无名结构体,例 struct s

45、tudent int num; char name20; char sex; int age; float score; char addr30; ;,结构体类型定义描述结构 的组织形式,不分配内存,结构体类型定义的作用域,例 struct student int num; char name20; char sex; int age; float score; char addr30; ; struct student stu1,stu2;,2) 结构体变量的定义 先定义结构体类型，再定义结构体变量 一般形式：,struct 结构体名 类型标识符 成员名； 类型标识符 成员名； . ； st

46、ruct 结构体名 变量名表列；,例 #define STUDENT struct student STUDENT int num; char name20; char sex; int age; float score; char addr30; ; STUDENT stu1,stu2;,3) 结构体变量的引用 引用规则 结构体变量不能整体引用,只能引用变量成员,可以将一个结构体变量赋值给另一个结构体变量 结构体嵌套时逐级引用,成员(分量)运算符 优先级: 1 结合性:从左向右,引用方式： 结构体变量名.成员名,4) 结构体变量的初始化 形式一：,struct 结构体名 类型标识符 成员名；

47、 类型标识符 成员名； . ； struct 结构体名 结构体变量=初始数据；,例 struct student int num; char name20; char sex; int age; char addr30; ; struct student stu1=112,“Wang Lin”,M,19, “200 Beijing Road”;,6) 结构体和指针 指向结构体变量的指针 定义形式：struct 结构体名 *结构体指针名; 例 struct student *p;,使用结构体指针变量引用成员形式,存放结构体变量在内存的起始地址,指向运算符 优先级: 1 结合方向：从左向右,例 指

48、向结构体的指针变量,main() struct student long int num; char name20; char sex; float score; stu_1,*p; p= ,例 int n; int *p= n=10,struct student stu1; struct student *p= (*p).num=101,16.数据结构,Niklaus Wirth：Algorithm + Data Structures = Programs 程序设计: 为计算机处理问题编制一组指令集 算法:处理问题的策略 数据结构:问题的数学模型 例如: 数值计算的程序设计问题 结构静力分析

49、计算 线性代数方程组 全球天气预报 环流模式方程 非数值计算的程序设计问题,例1 书目自动检索系统,书目文件,例2 人机对奕问题,例3多叉路口交通灯管理问题,基本概念和术语,数据所有能被输入到计算机中，且被计算机处理的符号的集合 数据元素数据的基本单位，也称节点或记录 数据项有独立含义的数据最小单位 数据结构数据元素和数据元素关系的集合 根据数据元素间关系的基本特性，有四种基本数据结构 集合数据元素间除“同属于一个集合”外，无其它关系 线性结构一个对一个，如线性表、栈、队列 树形结构一个对多个，如树 图状结构多个对多个，如图,数据的逻辑结构只抽象反映数据元素的逻辑关系 数据的存储（物理）结构数

50、据的逻辑结构在计算机存储器中的实现,基本概念和术语,基本概念和术语,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,基本概念和术语,抽象数据类型,是指一个数学模型以及定义在此数学模型上的一组操作 例如： 矩阵 +（求转置、加、乘、求逆、求特征值） 构成一个矩阵的抽象数据类型 数据结构+定义在此数据结构上的一组操作 = 抽象数据类型,17.算法的描述和算法分析,算法（algorithm）解决某一特定问题的具体步骤的描述，是指令的有限序列,算法的五个特性,有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成

51、确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径； 可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之 有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中； 有输出它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能,算法的评价,算法的评价衡量算法优劣的标准 正确性(correctness) 可读性(readability) 健

52、壮性(robustness) 效率与低存储量,18. 线性表的类型定义,线性表（Linear_List)定义： 线性表是最常用且最简单的一种数据结构。简言之一个线性表是n(n=0)个数据元素的有限序列， 记为（a1,a2,ai-1,ai,ai+1,an) 线性表中元素的个数n（n=0)定义为线性表的长度,n=0时称为空表。 举例： 英文字母表（A，B，CZ）也是一个线性表，其元素是英文字母,线性表的类型定义,线性结构的特点: 在数据元素的非空有限集中： 1、存在唯一的一个被称做“第一个”的数据元素 2、存在唯一的一个被称做“最后一个”的数据元素； 3、除第一个之外，集合中每个数据元素均只有一个

53、前驱 4、除最后一个之外，集合中每个数据元素均只有一个后继。 在非空线性表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素,ai是第i个数据元素,称i为数据元素ai在线性表中的位序,1) 线性表的顺序表示和实现,顺序表：将线性表存储到计算机中，可采用许多不同的方法，其中简单而自然的是顺序存储方法：即把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元里。用此方法存储的线性表简称为顺序表。 基地址：线性表中第一个数据元素的存储位置，通常称作线性表的起始位置或基地址。,1) 线性表的顺序表示和实现,线性表中所有数据元素的类型是相同的，则每个数据元素所占用的

54、存储空间的大小也相同。 假设线性表中的每个元素需占用 l 个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系： LOC(ai+1)=LOC(ai) + l 一般来说，线性表的第 i 个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(i-1) * l,1) 线性表的顺序表示和实现,在顺序表中，每个数据元素的存储地址是该数据元素在表中的位置的线性函数 只要知道基地址和每个数据元素的所占存储空间的大小，就可根据公式求出任一数据元素的存储地址 因此，顺序表是一种

55、随机存取的存储结构 由于高级程序设计语言中的数组类型也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构,1) 线性表的顺序表示和实现,顺序表的基本操作： 定义了线性表存储结构后，就可讨论在该存储结构上如何具体实现定义在逻辑结构上的操作了。 构造一个空的线性表 线性表的插入操作： 在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素。除非i=n+1，否则必须移动元素才能反映这个逻辑关系的变化,x,1) 线性表的顺序表示和实现,线性表的删除操作： 删除线性表的第i个数据元素。 线性表的第i个数据元素删除后，线性表的逻辑关系发生变化,1)线性表的顺序表示和实现,顺序

56、表的特点： 逻辑关系上相邻的两个元素在物理位置上也相邻。可以随机存取表中任意元素，它的存储位置可用一个简单、直观的公式来表示。 顺序表的优点： （1）无须为表示结点间的逻辑关系而增加额外的存储空间； （2）可以方便地随机存取表中的任一结点,1)线性表顺序表示和实现,顺序表的缺点： （1）插入和删除运算不方便，除表尾位置外，在表的其它位置上进行插入和删除操作都必须移动大量的结点，效率较低 （2）由于顺序表要求占用连续的存储空间，存储分配只能预先进行（静态分配），因此当表长变化较大时，难以确定合适的存储规模，若按可能达到的最大长度预先分配表空间，则可能造成一部分空间长期闲置而得不到充分利用；若事先对表长估计不足，则插入操作可能使表长超过预先分配的空间而造成溢出,2)线性表的链式表示和实现,链表：将按链接方式存储的线性表称为链表 链表从链接方式的角度分为：单链表、循环链表和双链表 链接存储是最常用的存储方法之一，不仅可以表示线性表，也可以表示各种非线性的数据结构,2)线性表的链式表示和实现,线性链表（单链表） 用线性链表表示线性表时，元素间的逻辑关系由结点中的指针指示。即指针为元素间的逻辑关系的映象。则逻辑上相邻的两个元素，其存储的物理位置不必相邻。此存储结构为非顺序映象。,2)线性表的链式表示和实现,线性表的单链表存储结构的描述： struct Lnode ElemType d