预备知识

预备知识基础：已学过“C程序设计”这门课程，并掌握数据类型、表达式、基本控制结构（顺序、分支和循环）、数组、指针、函数、以及输入输出等内容。数据结构课程需要扩充的知识：1C++的不同的表示2自定义数据类型（结构体、枚举类型、联合体）3复习函数，介绍函数重载4复习指针，介绍动态内存分配1C++的不同的表示（1）输入输出语句原来使用scanf()和printf()函数。现输出使用输出流对象cout和插入符，例：coutx;cout“x+y=”x+y;输入使用输入流对象cin和提取符，例：cinn;cinab;键盘输入时，两数之间用空格隔开。注意：以上对象和符号在头文件iostream.h中定义，所以，需要在源代码文件的开始包含它。1C++的不同的表示（2）简单的I/O格式控制endl插入换行符，并刷新流setprecision(int)设置浮点数的小数位数（包括小数点）setw(int)设置域宽例cout“请输入一个整数：”endl;a=3.1415926；coutsetprecision(3)aendl;name=“黄俊民”；coutsetw(12)name;1C++的不同的表示（3）嵌入的头文件C程序若包含输入输出语句，需要在主函数的前面嵌入#include“iostream.h”C++则需要#include“iostream”usingnamespacestd;1C++的不同的表示（4）变量赋初值inta=3;可以写成inta(3);2自定义数据类型2.1typedef声明为一个数据类型定义一些有具体意义的别名，以后可将别名当作数据类型使用。如：typedefdoublearea,volume;areaa;volumev;a和v还是浮点型数据，但程序可读性增强了。2自定义数据类型2.2枚举类型(enum)这种类型也是为了程序的可读性。具体做法是将变量需要的取值一一列举出来，便构成了一个枚举类型。枚举类型的声明形式如下：enum枚举类型名{变量值列表};例如：enumweekday{sun,mon,tue,wed,thu,fri,sat};enummonyh{Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec};2.2枚举类型(enum)枚举类型(enum)枚举类型应用说明：对枚举元素按常量处理，不能对它们赋值。例如，不能写：sun=0;Jan=1;枚举元素具有缺省值，它们依次为：0,1,2,......。也可以在声明时另行指定枚举元素的值，如：enumweekday{sun=7,mon=1,tue,wed,thu,fri,sat};枚举值可以进行关系运算。整数值不能直接赋给枚举变量，如需要将整数赋值给枚举变量，应进行强制类型转换。2.2枚举类型(enum)枚举类型(enum)定义枚举类型变量：enumweekdayday_id;enummonthmonth_id;也可weekdayday_id;monthmonth_id;枚举类型(enum)举例口袋中有红、黄、蓝、白、黑五种颜色的球若干个。每次从口袋中取出3个不同颜色的球，问有多少种取法。分析：由于球只能是五种颜色之一，故可用枚举类型表示球的颜色。设取出的球为i、j、k，根据题意，i、j、k分别可以有五种取值，且i≠j≠k。可以用穷举法，逐个检验每一种可能的组合，从中找出符合要求的组合并输出。#includeiostream.hvoidmain（）{enumcolor{red,yellow,blue,white,black};//枚举类型enumcolorpri;intn,loop,i,j,k;charc;n=0;for(i=red;i=black;i++)for(j=red;j=black;j++)if(i!=j)//前两个球不同{for(k=red;k=black;k++)if((k!=i)&&(k!=j))//第三个球不同于前两个{n=n+1;coutn;for(loop=1;loop=3;loop++){switch(loop){case1:pri=(enumcolor)i;break;case2:pri=(enumcolor)j;break;case3:pri=(enumcolor)k;break;default:break;}switch(pri){casered:coutred;break;caseyellow:coutyellow;break;caseblue:coutblue;break;casewhite:coutwhite;break;caseblack:coutblack;break;default:break;}}coutendl;}}couttotal:nendl;}2自定义数据类型2.3结构类型将数据对象组织在一起，成为一种组合的数据，对于程序设计十分有用。以前我们学习过“数组”，就是一种组合的数据类型。但是，组成数组的元素，它们的类型都是相同的。结构类型是一种将不同类型的数据对象组织在一起的数据类型，具体元素及其组织由用户自己定义。2.3结构类型定义结构类型struct结构名{数据类型成员名1；数据类型成员名2；：数据类型成员名n；};如structplanet{charname[MAXSIZE];floatdiameter,orbitrad;//星球直径和轨道半径};2.3结构类型定义结构类型数据struct结构名数据名；如structplanetpln;或者typedefstructplanetPLANET;PLANETpln;使用结构类型数据数据名•成员元素名如cout“输入”pln.name“的数据：”endl;cinpln.diameterpln.orbitrad;2.3结构类型定义指向结构类型数据的指针struct结构名*指针名；如structplanetpln,*ppln;或者typedefstructplanetPLANET;PLANETpln,*ppln;使用结构类型数据指针名-成员元素名如果ppln=&pln;那么cout“输入”ppln-name“的数据：”endl;cinppln-diameterppln-orbitrad;例将月日数转换为年天数的C函数staticintday_tab[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31},{0,31,29,31,30,31,30,31,31,30,31,30,31}};structdate{//定义结构类型intday,month,year;};intday_of_year(structdated){//函数inti,day,leap;day=d.day;leap=d.year%4==0&&d.year%100!=0||d.year%400==0;for(i=1;id.month;i++)day+=day_tab[leap][i];return(day);}例将月日数转换为年天数的C函数staticintday_tab[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31},{0,31,29,31,30,31,30,31,31,30,31,30,31}};structdate{//定义结构类型intday,month,year;};intday_of_year(structdate*pd){//函数inti,day,leap;day=pd-day;leap=pd-year%4==0&&pd-year%100!=0||pd-year%400==0;for(i=1;ipd-month;i++)day+=day_tab[leap][i];return(day);}2.4联合（共同体）几个不同类型的数据共用同一组内存单元，这种数据类型称为联合（union）。联合的定义union联合名{数据类型1成员1；数据类型2成员2；：：数据类型n成员n;};联合数据定义union联合名数据变量名；2.4联合联合数据变量的引用：联合数据变量名•成员名例uniondata{inti;floatf;charc;}；uniondatax;数据变量x有4个字节（它的最大成员空间为它的存储空间大小）。若使用x.i，则2个字节；若使用x.f，则4个字节；若使用x.c，则1个字节。设计一个既能填入学生数据、又能用于教师的数据类型，并用于实际处理。structrecord{intnumber;charname[20];charjob;//学生s；教师tunion{intclass;//学生填班级号charposition[12];//教师填职务}category;}person[2];程序中可使用下列形式的语句：intn,i;for(i=0;i2;i++){cinperson[i].numberperson[i].nameperson[i].job;if(person[i].job==‘s’)cinperson[i].category.class;elseif(person[i].job==‘t’)cinperson[i].category.position;elsecout“inputerror”endl;}3.复习函数，介绍函数重载(1)函数的定义函数返回值类型函数名（形式参数表）{语句序列}其中：——若无返回值，函数类型为void;——若无形式参数，形式参数表为void;否则，形式参数表为：type1name1,type2name2,┅,typennamen(1)函数的定义假如是main()函数，也可有形式参数和返回值。其中，返回值将被传递给操作系统；而带有形式参数的主函数，具体写成：main(intargc,char*argv[]){语句序列}argc表示参数个数argv[i]/*0≤i≤argc-1*/指向存储参数的字符串注意：c语言中的main()函数，常用void来定义类型。但在c++中，则使用int来定义类型，对于运行正常，能够执行到程序的逻辑结尾处，则return0;（2）函数的调用调用其他函数的函数，称为主调函数；被其他函数调用的函数，称为被调函数。在调用函数前，需声明函数原形，然后方可调用。函数原形的形式：函数返回值类型被调函数名（形式参数表）函数调用：函数名（实际参数表）其中：实际参数表中的参数个数与函数原形的形参个数相同，类型相符，并用逗号分隔。假若被调函数有返回值，它可出现在表达式中。(3)函数的参数传递——值调用函数调用时，给被调函数的形参分配空间，将实参的值传递给形参。被调函数执行完毕，形参的值不影响实参。——指针作为函数参数主调函数的实参指针和被调函数的形参指针指向共同的数据内存空间，被调函数直接处理主调函数的数据，主调函数直接得到被调函数的结果。这样实现参数双向传递。(3)函数的参数传递——引用调用引用名是某个变量的别名。在被调函数中，将引用作为形参。主调函数的变量名和被调函数的引用名在调用时实现对应，它们表示的是相同存储空间（存放变量值）的符号地址。在被调函数中任何对引用的操作，实际上就是对那个存储空间中的值的操作。最后都将在主调函数的实参上反映出来。具体格式：返回类型函数名（参数类型&引用名，…）例两个变量的值互换（1）指针参数（2）引用参数#includeiostream.hvoidswap(int*p1,int*p2){inttemp;temp=*p1;*p1=*p2;*p2=temp;}intmain(){inti=3,j=5;swap(&i,&j);couti“,”jendl;return0;}#includeiostream.hvoidswap(int&a,int&b){inttem