数据结构-预备知识PPT课件

第0章,预备知识,Thursday,August27,2009nysfxy1,第0章预备知识,Thursday,August27,2009nysfxy1,数据结构与算法应用教程,主要内容,1输入与输出2预定义常量3函数4结构体5引用6指针7内存动态分配与释放8枚举9类型定义(typedef),1输入与输出输入与输出流对象:cout和cin（iostream.h）(1)用cout进行输出格式:cout变量1变量2；将提取符作用在流类对象cin上实现输入如：inta,b;cinab;,例1:cin与cout的使用#includevoidmain()coutname;cinage;cout“Yournameisnameendl;cout“Yourageisageendl;运行情况如下：Pleaseenteryournameandage:Wang-li19yournameisWang-liyourageis19,2预定义常量和类型符号常量定义:用一个标识符来表示一个常量.注意:符号常量在使用之前一应要首先声明,符号常量声明语句的格式为:const数据类型说明符常量名=常量值;或数据类型说明符const常量名=常量值;例如:constfloatpi=3.14159265;函数结果主要状态代码：typedefintstatus;/status是函数的类型，其值是函数结果状态代码。consttrue=1;constfalse=0;,constOK=1constERROR=0constINFEASIBLE=1constOVERFLOW=2注意:符号常量在声明时必须要赋初值,而在程序中不能改变其值。符号常量的优点:有利于提高程序的可读性和方便修改。,3函数3.1函数的定义：用于完成特定功能或操作的程序模块.一般格式:函数类型函数名（参数表）/算法说明语句序列/函数名如：intmax(int，int)*定义有参函数max*int？；return（）；,3.2函数参数形式参数：定义函数时函数名后面括号中的变量名称实际参数：主调函数中调用一个函数时，函数名后面括号中的参数(可以是一个表达式)函数调用时实参与形参应一一对应，参数结合有两种方式：值传递与地址传递。3.3函数的返回值通过语句return(表达式)获得，返回值的类型应与函数类型一致，若无返回值，函数类型应定义为void。3.4函数调用格式:函数名（实参表列）说明:有语句、表达式、函数参数三种调用方式,3.5函数声明如果使用库函数，还应该在本文件开头用#include命令将调用有关库函数时所需用到的信息“包含”到本文件中来。如果使用自定义的函数，而该函数的位置在调用它的函数（即主调函数）的后面，应该在主调函数中对被调用的函数作声明。函数原型的一般形式为:函数类型函数名(参数类型1，参数类型2)；3.6函数的递归调用在调用一个函数的过程中又出现直接或间接地调用该函数本身。,递归问题的关键：递推公式、递归条件（边界）如:已知Fibonacci数列的第n项为：编写求第n项的递归函数longfib(intn)/n的合法性在主调函数中检测longf;if(n=1|n=2)f=1;elsef=fib(n-1)+fib(n-2);return(f);,3.7带缺省参数的函数一般情况下，实参个数应与形参个数相同。C+允许实参个数与形参个数不同。办法是在形参表列中对一个或几形参指定缺省值(或称默认值)。格式：函数类型函数名(类型1参数1,类型2参数2=表达式,)如：某函数首部：voidfun(inta，intb，intc=100)在调用此函数时如写成fun(2，4，6)，则形参a，b，c的值分别为2，4，6。如果写成fun(2，4)，即少写了最后一个参数，由于在函数定义时已指定了c的缺省值为100，因此a，b，c的值分别为2，4，100。注意：赋予缺省值的参数必须放在形参表列中的最右端。,4结构体结构体:不同类型相互关联的数据的有序集合。4.1声明一个结构体类型的一般形式为：struct结构体名成员表列；如：structstudentintnum;charname20;charsex;intage;floatscore;charaddr30;,结构体名,成员类型名,成员名(域名),说明:(1)不要忽略最后的分号;(2)structstudent是一个类型名，它和系统提供的标准类型(如int、char、float等)一样具有同样的地位和作用，都可以用来定义变量的类型，只不过结构体类型需要由用户自己指定而已。(3)“成员表列”称为“域表”,每一个成员也称为结构体中的一个域。成员名命名规则与变量名相同。,4.2定义结构体类型变量的方法先定义结构体类型再定义变量如：structstudentstudent1,student2;在声明类型的同时定义变量一般形式为:struct结构体名成员表列变量名表列；直接定义结构体类型变量一般形式为:struct成员表列变量名表列；,4.3结构体变量的引用不能将一个结构体变量作为一个整体进行输入和输出。引用结构体变量中成员的方式:结构体变量名.成员名说明:“.”是成员(分量)运算符,它在所有的运算符中优先级最高，student1.num表示student1变量中的num成员,可以对变量的成员赋值,例如:student1.num=10010;/将整数10010赋给student1变量中的成员numstudent1.age+；/使student1.age中的成员age进行自加运算,4.4结构体变量的初始化与其他类型变量一样，对结构体变量可以在定义时指定初始值。例:对结构体变量初始化。structstudentlongintnum；charname20；charsex；charaddr20；a=89031，LiLin，M，123BeijingRoad；,5引用(1)引用的概念“引用”(reference)是C+的一种新的变量类型，它的作用是为一个变量起一个别名,并没有开辟新的存储区。定义方法:类型名不可建立对不同类型变量的引用,例2：了解引用和变量的关系#include#includevoidmain()inta=10;int运行结果如下：1001002020,(3)引用作为函数参数有了变量名，为什么还需要一个别名呢？C+之所以增加“引用”，主要是把它作为函数参数，以扩充函数传递数据的功能。函数调用参数传递方式：值传递与地址传递。C+提供了向函数传递数据的第三种方法，即传送变量的别名。,例3：利用“引用形参”实现两个变量的值互换#includevoidswap(int输出结果为i=5j=3,说明：实参传给形参的是变量的地址,也就是使形参a具有变量i的地址，从而使a和i共享同一单元。为便于理解，我们说把变量i的名字传给引用变量a，使a成为i的别名。系统传送的是实参的地址而不是实参的值，这种用法比使用指针变量简单、直观、方便。注：当读者看到如：int*p,i=3;p=指针法：*(a+i)or*(p+i),(2)二维数组指针定义格式:指针类型名(*指针名)常数;如：inta34,(*p)4=a;对数组元素的引用：下标法：aijorpij指针法：*(*(a+i)+j)or*(*(p+i)+j)6.3字符串指针定义格式:char*指针名;如：charstr=C+Program.;char*p;p=str;,例4：将两个字符串合并为一个字符串#include#includevoidmain()charstr100=Welcometo;char*ps=C+.;inti,len;len=strlen(str);for(i=0;*(ps+i);i+)strlen+i=*(ps+i);coutTheresult:strendl;,6.4指针数组定义格式:类型名*数组名数组长度;如：int*p4,b10;inta=5,c;p0=例5：使用指针数组对若干个字符串按从小到大排序输出#include#include,voidmain()char*p5=C,C+,JAVA,Delpha,ASP;inti,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函数指针函数是一段程序，运行时与变量一样占用内存空间，有一个起始地址，即指向此函数的指针。定义格式:类型名（*函数名）（形参表）=函数名;如：若有函数：intfun(int,char);则：int(*p)(int,char);p=fun;orint(*p)(int,char)=fun;/p为指向函数fun的指针注：函数名为指针常量，不可改变；函数指针一般用于作函数参数，用来简化有规律的函数调用。例6：使用函数名作函数参数#include,intminus(inta,intb)returna-b;intplus(inta,intb)returna+b;intmultiply(inta,intb)returna*b;intdivide(inta,intb)returna/b;intop(inta,intb,int(*p)(int,int);voidmain()cout5+3=op(5,3,plus)endl;cout5-3=op(5,3,minus)endl;cout5*3=op(5,3,multiply)endl;cout5/3=m;coutThescoresofNO.mare:endl;q=search(score,m);for(i=0;i4;i+)cout*(q+i);cout指向运算符,7内存动态分配与释放（运算符new和delete）C+提供了较简便而功能较强的运算符new和delete来取代malloc、calloc和free函数。(1)new运算符简单变量动态存储格式为：指针变量=new类型名（初值表列）；例如：int*p=newint;/开辟一个存放整数的空间，返回一个指向整型数据的指针int*p=newint(100);/开辟一个存放整数的空间，并指定该整数的初值为100float*p=newfloat(3.14159)/开辟一个存放浮点数的空间，并指定该浮点数的初值为3.14159，将返回的指向实型数据的指针赋给指针变量p。,数组动态存储格式：指针变量=new类型名元素个数；如:intn=5,*p=newintn;char*ps=newchar10;/开辟一个存放字符数组的空间，该数组有10个元素，返回一个指向字符数据首字符的指针float(*q)4=newfloat54;/申请可存放5行4列浮点数的空间注：用new分配数组空间时不能指定初值。(2)delete运算符格式:delete指针变量作用:释放由new申请到的内存空间。如：deletep;deleteps,q;/加方括号，表示对数组空间的操作,例9：动态开辟空间以存放一个结构体变量#include#includestructstudentcharname10;intnum;charsex;voidmain()student*p=newstudent;strcpy(p-name,WangFun);p-num=10123;p-sex=M;coutnamenum;coutsexnump1-score;head=NULL;while(p1-num!=0)n+;if(n=1)head=p1;elsep2-next=p1;p2=p1;p1=newstudent;cinp1-nump1-score;p2-next=NULL;returnhead;,voidprint(student*head)/遍历链表student*p;coutnumscorenext;while(p!=NULL);,8枚举定义枚举类型的一般格式：enum枚举类型名枚举元素表；例如：enumbooltrue,false;说明：1.枚举元素为符号常量，不能改变其值；2.枚举常量的值为整数，按定义时的顺序依次为:0,1,2,enumweekday(Sun,Mon,Tue,Wed,Thu,Fri,Sat);enumweekday(Sun=7,Mon=1,Tue,Wed,Thu,Fri,Sat);3.枚举常量可赋给枚举变量，但不可将一整数赋给枚举变量weekdayday;day=Mon;couti;gc=character(i);switch(gc)casea:couta;break;caseb:coutb;break;casec:coutc;break;cased:coutd;break;,9用typedef定义类型用typedef声明新的类型名来代替已有的类型名。typedefintINTEGER;/声明INTEGER为整型typedeffloatREAL;声明结构类型typedefstructintmonth；intday；intyear；DATE;变量声明：INTEGERi,j,k;REALx,y,z;DATEbirthday,workday;,用typedef定义类型的方法：先按定义变量的方法写出定义体（如：inti）。将变量名换成新类型名（例如：将i换成COUNT）。在最前面加typedef（例如：typedefintCOUNT）。然后可以用新类型名去定义变