数据结构及应用算法教程（修订版） 数据结构_预备知识.ppt

《数据结构及应用算法教程（修订版） 数据结构_预备知识.ppt》由会员分享，可在线阅读，更多相关《数据结构及应用算法教程（修订版） 数据结构_预备知识.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第0章,预备知识,Thursday, August 27, 2009 1,第0章 预备知识,Thursday, August 27, 2009 1,数据结构与算法应用教程,主要内容,1 输入与输出 2 预定义常量 3 函数 4 结构体 5 引用 6 指针 7 内存动态分配与释放 8 枚举 9 类型定义(typedef),1 输入与输出 输入与输出流对象:cout和cin（iostream.h） (1)用cout进行输出 格式:cout变量1变量2； 将提取符作用在流类对象cin上实现输入 如：int a,b; cinab;,例1: cin与cout的使用 #include void main(

2、 ) coutname; cinage; cout“Your name is nameendl; cout“Your age is ageendl; 运行情况如下： Please enter your name and age: Wang-li 19 your name is Wang-li your age is 19,2 预定义常量和类型 符号常量定义:用一个标识符来表示一个常量.注意:符号常量在使用之前一应要首先声明,符号常量声明语句的格式为: const 数据类型说明符 常量名=常量值; 或 数据类型说明符 const 常量名=常量值; 例如:const float pi=3.1415

3、9265; 函数结果主要状态代码： typedef int status; /status是函数的类型，其值是函数结果状态代码。 const true=1; const false=0;,const OK=1 const ERROR=0 const INFEASIBLE= 1 const OVERFLOW= 2 注意:符号常量在声明时必须要赋初值,而在程序中不能改变其值。符号常量的优点:有利于提高程序的可读性和方便修改。,3 函数 3.1 函数的定义：用于完成特定功能或操作的程序模块. 一般格式: 函数类型 函数名（参数表） /算法说明 语句序列 /函数名 如： int max(int ，in

4、t ) * 定义有参函数max * int ？； return（）； ,3.2 函数参数 形式参数：定义函数时函数名后面括号中的变量名称 实际参数：主调函数中调用一个函数时，函数名后面括号中的参数(可以是一个表达式) 函数调用时实参与形参应一一对应，参数结合有两种方式：值传递与地址传递。 3.3 函数的返回值 通过语句return(表达式)获得，返回值的类型应与函数类型一致，若无返回值，函数类型应定义为void。 3.4 函数调用 格式:函数名（实参表列） 说明:有语句、表达式、函数参数三种调用方式,3.5 函数声明 如果使用库函数，还应该在本文件开头用#include命令将 调用有关库函数时

5、所需用到的信息“包含”到本文件中来。 如果使用自定义的函数，而该函数的位置在调用它的函数（即主调函数）的后面，应该在主调函数中对被调用的函 数作声明。 函数原型的一般形式为: 函数类型 函数名(参数类型1，参数类型2)； 3.6 函数的递归调用 在调用一个函数的过程中又出现直接或间接地调用该函 数本身。,递归问题的关键：递推公式、递归条件（边界） 如:已知Fibonacci数列的第n项为： 编写求第n项的递归函数 long fib(int n) /n的合法性在主调函数中检测 long f; if(n=1|n=2) f=1; else f=fib(n-1)+fib(n-2); return (f

6、); ,3.7 带缺省参数的函数 一般情况下，实参个数应与形参个数相同。C+允许实参个数与形参个数不同。办法是在形参表列中对一个或几形 参指定缺省值(或称默认值)。 格式： 函数类型 函数名(类型1 参数1,类型2 参数2=表达式,) 如：某函数首部：void fun(int a，int b，int c=100) 在调用此函数时如写成fun(2，4，6)，则形参a，b，c的值分别为2，4，6。如果写成fun(2，4) ，即少写了最后一个参数，由于在函数定义时已指定了c的缺省值为100，因此a， b，c的值分别为2，4，100。 注意：赋予缺省值的参数必须放在形参表列中的最右端。,4 结构体 结

7、构体:不同类型相互关联的数据的有序集合。 4.1 声明一个结构体类型的一般形式为： struct 结构体名 成员表列； 如：struct student int num; char name20; char sex; int age; float score; char addr30; ;,结构体名,成员类型名,成员名(域名),说明: (1)不要忽略最后的分号; (2)struct student是一个类型名，它和系统提供的标准类型(如int、char、float等)一样具有同样的地位和作用，都可以用来定义变量的类型，只不过结构体类型需要由用户自己指定而已。 (3)“成员表列”称为“域表”,每

8、一个成员也称为结构体中的一个域。成员名命名规则与变量名相同。,4.2 定义结构体类型变量的方法 先定义结构体类型再定义变量 如：struct student student1,student2; 在声明类型的同时定义变量 一般形式为: struct结构体名 成员表列 变量名表列； 直接定义结构体类型变量 一般形式为: struct 成员表列 变量名表列；,4.3 结构体变量的引用 不能将一个结构体变量作为一个整体进行输入和输出。 引用结构体变量中成员的方式: 结构体变量名.成员名 说明: “.”是成员(分量)运算符,它在所有的运算符中优先级最高，student1.num表示student1变量

9、中的num成员,可以对变量的成员赋值,例如: student1.num=10010; /将整数10010赋给student1变量中的成员num student1.age+； /使student1.age中的成员age进行自加运算,4.4 结构体变量的初始化 与其他类型变量一样，对结构体变量可以在定义时指定初始值。例: 对结构体变量初始化。 struct student long int num； char name20； char sex； char addr20； a=89031，Li Lin，M，123 Beijing Road；,5 引用 (1)引用的概念 “引用”(reference)

10、是C+的一种新的变量类型，它的作用是为一个变量起一个别名, 并没有开辟新的存储区。 定义方法: 类型名 不可建立对不同类型变量的引用,例2：了解引用和变量的关系 #include #include void main( ) int a=10; int 运行结果如下： 100100 2020,(3)引用作为函数参数 有了变量名，为什么还需要一个别名呢？C+之所以增加“引用”，主要是把它作为函数参数，以扩充函数传递数据的功能。 函数调用参数传递方式：值传递与地址传递。 C+提供了向函数传递数据的第三种方法，即传送变量的别名。,例3：利用“引用形参”实现两个变量的值互换 #include void

11、swap( int 输出结果为 i=5 j=3,说明：实参传给形参的是变量的地址,也就是使形参a具有变量i的地址，从而使a和i共享同一单元。为便于理解，我们说 把变量i的名字传给引用变量a，使a成为i的别名。 系统传送的是实参的地址而不是实参的值，这种用法比 使用指针变量简单、直观、方便。 注：当读者看到 如：int *p,i=3; p= 指针法：*(a+i) or *(p+i),(2)二维数组指针 定义格式:指针类型名 (*指针名)常数; 如：int a34,(*p)4=a; 对数组元素的引用： 下标法：aij or pij 指针法：*(*(a+i)+j) or *(*(p+i)+j) 6.

12、3 字符串指针 定义格式:char *指针名; 如：char str=C+ Program. ; char *p; p=str;,例4：将两个字符串合并为一个字符串 #include #include void main() char str100=Welcome to ; char *ps=C+. ; int i,len; len=strlen(str); for (i=0;*(ps+i);i+) strlen+i=*(ps+i); coutThe result:strendl; ,6.4 指针数组 定义格式: 类型名 *数组名数组长度; 如： int *p4, b10; int a=5,c

13、; p0= 例5：使用指针数组对若干个字符串按从小到大排序输出 #include #include ,void main() char *p5=C,C+,JAVA,Delpha,ASP; int i,j,k; char *ch; for (i=0;i0) k=j; if(k!=i) ch=pk; pk=pi; pi=ch; for (i=0;i5;i+) coutpiendl; ,6.5 函数指针 函数是一段程序，运行时与变量一样占用内存空间，有一个起始地址，即指向此函数的指针。 定义格式: 类型名 （*函数名）（形参表）=函数名; 如：若有函数：int fun(int,char); 则：in

14、t (*p)(int, char); p=fun; or int (*p)(int,char)=fun; /p为指向函数fun的指针 注：函数名为指针常量，不可改变；函数指针一般用于作函数参数，用来简化有规律的函数调用。 例6：使用函数名作函数参数 #include ,int minus(int a,int b) return a-b; int plus(int a,int b) return a+b; int multiply(int a,int b) return a*b; int divide(int a,int b) return a/b; int op(int a,int b,int

15、 (*p)(int,int); void main() cout5+3=op(5,3,plus)endl; cout5-3=op(5,3,minus)endl; cout5*3=op(5,3,multiply)endl; cout5/3=op(5,3, ,6.6 返回指针的函数 函数的返回值可以是指针，称为指针函数。 定义格式: 类型名 *函数名（形参表）函数体 例7：有若干学生成绩，要求输入学生的序号，输出学生的全部成绩（使用指针函数） #include void main() float score4=60,70,80,90,56,66,87,77,65,99,75,68; float *

16、search(float (*p)4,int n); float *q; int i,m;,coutm; coutThe scores of NO. m are:endl; q=search(score,m); for(i=0;i4;i+) cout*(q+i) ; coutendl; float *search(float (*p)4,int n) return *(p+n-1); ,6.7 结构体指针 结构体指针指结构体变量所占据的内存段的起始地址。 例8：结构体指针应用示例 #include #include #include struct student long num; char

17、name20; char sex; float score; ;,void main() student stu_1,stu_2; student *p; p= ,通过指针访问结构体成员： (*p).成员名 p-成员名 指向运算符,7 内存动态分配与释放（运算符new和delete） C+提供了较简便而功能较强的运算符new和delete来取代 malloc、calloc和free函数。 (1) new运算符 简单变量动态存储格式为： 指针变量=new 类型名（初值表列）； 例如： int *p=new int; /开辟一个存放整数的空间，返回一个指向整型数据的指针 int *p=new in

18、t(100); /开辟一个存放整数的空间，并指定该整数的初值为100 float *p=new float(3.14159) /开辟一个存放浮点数的空间，并指定该浮点数的初值为 3.14159，将返回的指向实型数据的指针赋给指针变量p。,数组动态存储格式：指针变量=new 类型名元素个数； 如: int n=5, *p=new intn; char *ps=new char10; /开辟一个存放字符数组的空间，该数组有10个元素，返回一个指向字符数据首字符的指针 float (*q)4=new float54; /申请可存放5行4列浮点数的空间 注：用new分配数组空间时不能指定初值。 (2)

19、 delete运算符 格式: delete 指针变量 作用:释放由new申请到的内存空间。 如：delete p; delete ps , q; /加方括号，表示对数组空间的操作,例9：动态开辟空间以存放一个结构体变量 #include #include struct student char name10; int num; char sex; ; void main ( ) student *p= new student; strcpy(p-name,Wang Fun ); p-num=10123; p-sex=M; coutnamenum; coutsexendl; delete p;

20、,例10：链表创建与遍历 #include #include struct student long num; float score; student *next; ; int n=0; /统计结点个数 void main() void print(student *head); /函数声明 student *creat(); student *head; head=creat(); print(head); ,student *creat() /创建链表 student *head,*p1,*p2; p1=p2=new student; coutp1-nump1-score; head=N

21、ULL; while(p1-num!=0) n+; if(n=1) head=p1; else p2-next=p1; p2=p1; p1=new student; cinp1-nump1-score; p2-next=NULL; return head; ,void print(student *head) /遍历链表 student *p; coutnumscorenext; while(p!=NULL); ,8 枚举 定义枚举类型的一般格式： enum 枚举类型名枚举元素表； 例如：enum bool true,false; 说明： 1. 枚举元素为符号常量，不能改变其值； 2. 枚举常

22、量的值为整数，按定义时的顺序依次为:0,1,2, enum weekday (Sun,Mon,Tue,Wed,Thu,Fri,Sat); enum weekday (Sun=7,Mon=1,Tue,Wed,Thu,Fri,Sat); 3. 枚举常量可赋给枚举变量，但不可将一整数赋给枚举变量 weekday day; day=Mon; coutday; /结果为1 4. 枚举值可以比较大小,例11：由序号求枚举值 #include / 演示 void main() int i; typedef enum a=1,b,c,d character; character gc; couti; gc=c

23、haracter(i); switch(gc) case a:couta;break; case b:coutb;break; case c:coutc;break; case d:coutd;break; ,9 用typedef定义类型 用typedef声明新的类型名来代替已有的类型名。 typedef int INTEGER; /声明INTEGER为整型 typedef float REAL; 声明结构类型 typedef struct int month； int day； int year； DATE; 变量声明： INTEGER i,j,k; REAL x,y,z; DATE bir

24、thday,workday;,用typedef定义类型的方法： 先按定义变量的方法写出定义体（如：int i）。 将变量名换成新类型名（例如：将i换成COUNT）。 在最前面加typedef （例如：typedef int COUNT）。 然后可以用新类型名去定义变量。 如：先按定义数组变量形式书写：int n100; 将变量名换成指定的类型名：int NUM100; 在前面加上typedef,得到:typedef int NUM100; 用来定义变量： NUM n; 注：数据结构中基本数据类型约定为ElemType，用户在使用该数据类型时再具体定义。如：typedef int ElemType;,其它说明： 1. 结束语句 return 或return /用于函数结束 break语句 /用于循环或switch 语句中 continue语句 /用在循环中结束本次循环过程， 进入下一次循环 exit语句 /表示出现异常情况时，控制退出函数 2. 注释形式 /* 字符串 */ 多行注释 /字符串 单行注释,