数据结构-预备知识.ppt

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

1、 Saturday,October 06,2012 1第0章 Thursday,August 27,2009 1 Thursday,August 27,2009 1 Saturday,October 06,2012 2l l 主要内容 1 1 输入与输出输入与输出 2 2 预定义常量预定义常量 3 3 函数函数 4 4 结构体结构体 5 5 引用引用 6 6 指针指针 7 7 内存动态分配与释放内存动态分配与释放 8 8 枚举枚举 9 9 类型定义类型定义(typedeftypedef)Saturday,October 06,2012 31 1 输入与输出输入与输出输入与输出流对象输入与输出流

2、对象:coutcout和和cincin（iostream.hiostream.h）(1)(1)用用coutcout进行输出进行输出格式格式:coutcout表达式表达式11表达式表达式22；用预定义的插入符用预定义的插入符，作用于流类对象，作用于流类对象coutcout上实现输出上实现输出如：如：coutcouthello!hello!endlendl;coutcouta=setw(5)aa=setw(5)a变量变量11变量变量22；将提取符将提取符作用在流类对象作用在流类对象cincin上实现输入上实现输入如：如：intint a,ba,b;cincinab;ab;Saturday,Octo

3、ber 06,2012 4例例1:cin与与cout的使用的使用#include void main()coutPlease enter your name and age:name;cinage;cout“Your name is nameendl;cout“Your age is ageendl;运行情况如下：运行情况如下：Please enter your name and age:Wang-li 19 your name is Wang-liyour age is 19 Saturday,October 06,2012 52 2 预定义常量和类型预定义常量和类型符号常量定义符号常量定义

4、:用一个标识符来表示一个常量用一个标识符来表示一个常量.注意注意:符号常量符号常量在使用之前一应要首先声明在使用之前一应要首先声明,符号常量声明语句的格式为符号常量声明语句的格式为:const 数据类型说明符数据类型说明符 常量名常量名=常量值常量值;或或 数据类型说明符数据类型说明符 const 常量名常量名=常量值常量值;例如例如:const float pi=3.14159265;函数结果主要状态代码：函数结果主要状态代码：typedef int status;/status是函数的类型，其值是函数结果状态代码。是函数的类型，其值是函数结果状态代码。const true=1;const

5、false=0;Saturday,October 06,2012 6 const OK=1 const ERROR=0 const INFEASIBLE=1 const OVERFLOW=2注意注意:符号常量在声明时必须要赋初值符号常量在声明时必须要赋初值,而在程序中不能改变而在程序中不能改变其值。符号常量的优点其值。符号常量的优点:有利于提高程序的可读性和方便修有利于提高程序的可读性和方便修改。改。Saturday,October 06,2012 73 3 函数函数3.1 函数的定义：函数的定义：用于完成特定功能或操作的程序模块用于完成特定功能或操作的程序模块.一般格式一般格式:函数类型函数

6、类型 函数名（参数表）函数名（参数表）/算法说明算法说明 语句序列语句序列 /函数名函数名如：如：int max(int，int)*定义有参函数定义有参函数max *int？；return（）；（）；Saturday,October 06,2012 83.2 函数参数函数参数形式参数：定义函数时函数名后面括号中的变量名称实际参数：主调函数中调用一个函数时，函数名后面括号中的参数(可以是一个表达式)函数调用时实参与形参应一一对应，参数结合有两种方式：值传递与地址传递。3.3 函数的返回值函数的返回值 通过语句return(表达式)获得，返回值的类型应与函数类型一致，若无返回值，函数类型应定义为v

7、oid。3.4 函数调用函数调用格式:函数名（实参表列）说明:有语句、表达式、函数参数三种调用方式 Saturday,October 06,2012 93.5 函数声明函数声明 如果使用库函数，还应该在本文件开头用#include命令将调用有关库函数时所需用到的信息“包含”到本文件中来。如果使用自定义的函数，而该函数的位置在调用它的函数（即主调函数）的后面，应该在主调函数中对被调用的函数作声明。函数原型的一般形式为:函数类型 函数名(参数类型1，参数类型2)；3.6 函数的递归调用函数的递归调用 在调用一个函数的过程中又出现直接或间接地调用该函数本身。Saturday,October 06,2

8、012 10递归问题的关键：递推公式、递归条件（边界）递归问题的关键：递推公式、递归条件（边界）如:已知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);Saturday,October 06,2012 113.7 带缺省参数的函数带缺省参数的函数 一一般般情情况况下下，实实参参个个数数应应与与形形参参个个数数相相同同。C+允允许许实实参参个个数数与与形形参参个个数数不不同同。办办法法是是在在形形参参表表列列中中对对

9、一一个个或或几几形形参指定缺省值参指定缺省值(或称默认值或称默认值)。格式：格式：函数类型函数类型 函数名函数名(类型类型1 1 参数参数1,1,类型类型2 2 参数参数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，

10、4，100。注意：赋予缺省值的参数必须放在形参表列中的最右端。注意：赋予缺省值的参数必须放在形参表列中的最右端。Saturday,October 06,2012 124 4 结构体结构体结构体结构体:不同类型相互关联的数据的有序集合。不同类型相互关联的数据的有序集合。4.1 声明一个结构体类型的一般形式为：声明一个结构体类型的一般形式为：struct 结构体名结构体名 成员表列；成员表列；如：如：struct student int num;char name20;char sex;int age;float score;char addr30;结构体名成员类型名成员名(域名)Saturday

11、,October 06,2012 13说明说明:(1)不要忽略最后的分号不要忽略最后的分号;(2)struct student是一个类型名，它和系统提供的标准类是一个类型名，它和系统提供的标准类型型(如如int、char、float等等)一样具有同样的地位和作用，都可一样具有同样的地位和作用，都可以用来定义变量的类型，只不过结构体类型需要由用户自己以用来定义变量的类型，只不过结构体类型需要由用户自己指定而已。指定而已。(3)“成员表列成员表列”称为称为“域表域表”,每一个成员也称为结构体中每一个成员也称为结构体中的一个域。成员名命名规则与变量名相同。的一个域。成员名命名规则与变量名相同。Sat

12、urday,October 06,2012 144.2 定义结构体类型变量的方法定义结构体类型变量的方法n 先定义结构体类型再定义变量先定义结构体类型再定义变量如：如：structstruct student student1,student2;student student1,student2;n 在声明类型的同时定义变量在声明类型的同时定义变量一般形式为一般形式为:structstruct结构体名结构体名 成员表列成员表列 变量名表列；变量名表列；n 直接定义结构体类型变量直接定义结构体类型变量一般形式为一般形式为:structstruct 成员表列成员表列 变量名表列；变量名表列；Sat

13、urday,October 06,2012 154.3 结构体变量的引用结构体变量的引用不能将一个结构体变量作为一个整体进行输入和输出。不能将一个结构体变量作为一个整体进行输入和输出。引用结构体变量中成员的方式引用结构体变量中成员的方式:结构体变量名结构体变量名结构体变量名结构体变量名.成员名成员名成员名成员名说明说明:“.”是成员是成员(分量分量)运算符运算符,它在所有的运算符中优先它在所有的运算符中优先级最高，级最高，student1.num表示表示student1变量中的变量中的num成员成员,可以可以对变量的成员赋值对变量的成员赋值,例如例如:student1.num=10010;/将

14、整数将整数10010赋给赋给student1变量中的成员变量中的成员num student1.age+；/使使student1.age中的成员中的成员age进行自加运算进行自加运算 Saturday,October 06,2012 164.4 4.4 结构体变量的初始化结构体变量的初始化结构体变量的初始化结构体变量的初始化 与其他类型变量一样，对结构体变量可以在定义时指定初与其他类型变量一样，对结构体变量可以在定义时指定初始值。例始值。例:对结构体变量初始化。对结构体变量初始化。struct student long int num；char name20；char sex；char addr

15、20；a=89031，Li Lin，M，123 Beijing Road；Saturday,October 06,2012 175 引用引用(1)引用的概念引用的概念 “引用引用”(reference)是是C+的一种新的变量类型，它的的一种新的变量类型，它的作用是为一个变量起一个别名作用是为一个变量起一个别名,并没有开辟新的存储区。并没有开辟新的存储区。定义方法定义方法:类型名类型名&引用变量名引用变量名=变量名变量名;假如有一个变量假如有一个变量a，想给它起一个别名，想给它起一个别名b，可以这样写：，可以这样写：int a;int&b=a;(2)说明说明:引用与被引用的变量具有相同的存储地址

16、引用与被引用的变量具有相同的存储地址;对引用和对被引用变量的操作是一样的对引用和对被引用变量的操作是一样的,对引用的存取就是对引用的存取就是对被引用变量的存取，对引用变量的存取就是对引用的存取对被引用变量的存取，对引用变量的存取就是对引用的存取引用变量必须初始化引用变量必须初始化;不可建立对不同类型变量的引用不可建立对不同类型变量的引用 Saturday,October 06,2012 18例例2：了解引用和变量的关系：了解引用和变量的关系#include#include void main()int a=10;int&b=a;/声明声明b是是a的引用的引用 a=a*a;/a的值变化了，的值变

17、化了，b的值也应一起变化的值也应一起变化 coutasetw(6)bendl;b=b/5;/b的值变化了，的值变化了，a的值也应一起变化的值也应一起变化 coutbsetw(6)aendl;运行结果如下：运行结果如下：1001002020 Saturday,October 06,2012 19(3)引用作为函数参数引用作为函数参数 有了变量名，为什么还需要一个别名呢？有了变量名，为什么还需要一个别名呢？C+之所以增加之所以增加“引用引用”，主要是把它作为函数参数，以扩充函数传递数据的，主要是把它作为函数参数，以扩充函数传递数据的功能。功能。函数调用参数传递方式：函数调用参数传递方式：值传递与地

18、址传递。值传递与地址传递。C+提供了向函数传递数据的第三种方法，即传送变量的提供了向函数传递数据的第三种方法，即传送变量的别名。别名。Saturday,October 06,2012 20例例3：利用：利用“引用形参引用形参”实现两个变量的值互换实现两个变量的值互换#include void swap(int&a,int&b)int temp;temp=a;a=b;b=temp;void main()int i=3,j=5;swap(i,j);couti=i j=jendl;输出结果为输出结果为i=5 j=3 Saturday,October 06,2012 21说说明明：实实参参传传给给形形

19、参参的的是是变变量量的的地地址址,也也就就是是使使形形参参a具具有有变变量量i的的地地址址，从从而而使使a和和i共共享享同同一一单单元元。为为便便于于理理解解，我我们们说说把把 变变 量量i的的 名名 字字 传传 给给 引引 用用 变变 量量a，使使a成成 为为i的的 别别 名名。系系统统传传送送的的是是实实参参的的地地址址而而不不是是实实参参的的值值，这这种种用用法法比比使用指针变量简单、直观、方便。使用指针变量简单、直观、方便。注注：当当读读者者看看到到&a这这样样的的形形式式时时，怎怎样样区区别别是是声声明明引引用用变变量量还还是是取取地地址址的的操操作作呢呢？请请记记住住,当当&a的的

20、前前面面有有类类型型符符时时（如如int&a）,它它必必然然是是对对引引用用的的声声明明,如如果果前前面面无无类类型型符符（如如&a），则是取变量的地址。），则是取变量的地址。Saturday,October 06,2012 226 6 指针指针6.1 变量的指针：变量的指针：变量在内存中的地址变量在内存中的地址指针变量的定义：基类型指针变量的定义：基类型*指针变量名指针变量名;如：如：int*p,i=3;p=&i;引用指针变量引用指针变量p指向的存储单元的内容：指向的存储单元的内容：*p6.2 数组的指针数组的指针(1)一维数组指针一维数组指针定义格式定义格式:指针类型名指针类型名*指针名指

21、针名;如：如：int a5;/a为指针常量为指针常量 int*p=a;/p为指针变量为指针变量对数组元素的引用：对数组元素的引用：下标法：下标法：ai or pi;指针法：指针法：*(a+i)or*(p+i)Saturday,October 06,2012 23(2)(2)二维数组指针二维数组指针定义格式定义格式:指针类型名指针类型名 (*(*指针名指针名)常数常数;如：如：int a34,(*p)4=a;对数组元素的引用：对数组元素的引用：下标法：下标法：aij or pij 指针法：指针法：*(*(a+i)+j)or*(*(p+i)+j)6.3 6.3 字符串指针字符串指针定义格式定义格式

22、:char*:char*指针名指针名;如：如：char str=C+Program.;char*p;p=str;Saturday,October 06,2012 24例例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;Saturday,October 06,2012 256.4 6.4 指针

23、数组指针数组定义格式定义格式:类型名类型名*数组名数组名数组长度数组长度;如：如：int*p4,b10;int a=5,c;p0=&a;p1=b;p2=&c;char*p5=C,C+,JAVA,Delpha,ASP;例例5：使用指针数组对若干个字符串按从小到大排序输出使用指针数组对若干个字符串按从小到大排序输出#include#include Saturday,October 06,2012 26void main()char*p5=C,C+,JAVA,Delpha,ASP;int i,j,k;char*ch;for(i=0;i5-1;i+)k=i;for(j=i+1;j0)k=j;if(k!

24、=i)ch=pk;pk=pi;pi=ch;for(i=0;i5;i+)coutpiendl;Saturday,October 06,2012 276.5 6.5 函数指针函数指针函数是一段程序，运行时与变量一样占用内存空间，有一个函数是一段程序，运行时与变量一样占用内存空间，有一个起始地址，即指向此函数的指针。起始地址，即指向此函数的指针。定义格式定义格式:类型名类型名（*函数名）（形参表）函数名）（形参表）=函数名函数名;如：若有函数：如：若有函数：int fun(int,char);则：则：int(*p)(int,char);p=fun;or int(*p)(int,char)=fun;/

25、p为指向函数为指向函数fun的指针的指针注：函数名为指针常量，不可改变；函数指针一般用于作函注：函数名为指针常量，不可改变；函数指针一般用于作函数参数，用来简化有规律的函数调用。数参数，用来简化有规律的函数调用。例例6：使用函数名作函数参数使用函数名作函数参数#include Saturday,October 06,2012 28int 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

26、;int op(int a,int b,int(*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,÷)endl;int op(int a,int b,int(*p)(int,int)return p(a,b);Saturday,October 06,2012 296.6 6.6 返回指针的函数返回指针的函数函数的返回值可以是指针，称为指针函数。函数的返回值可以是指针，称为指针函数。定义格式定义格式

27、:类型名类型名 *函数名（形参表）函数名（形参表）函数体函数体例例7：有若干学生成绩，要求输入学生的序号，输出学生的全有若干学生成绩，要求输入学生的序号，输出学生的全部成绩（使用指针函数）部成绩（使用指针函数）#include void main()float score4=60,70,80,90,56,66,87,77,65,99,75,68;float*search(float(*p)4,int n);float*q;int i,m;Saturday,October 06,2012 30 coutm;coutThe scores of NO.m are:endl;q=search(scor

28、e,m);for(i=0;i4;i+)cout*(q+i);coutendl;float*search(float(*p)4,int n)return*(p+n-1);Saturday,October 06,2012 316.7 6.7 结构体指针结构体指针结构体指针指结构体变量所占据的内存段的起始地址。结构体指针指结构体变量所占据的内存段的起始地址。例例8：结构体指针应用示例结构体指针应用示例#include#include#include struct student long num;char name20;char sex;float score;Saturday,October 06

29、,2012 32void main()student stu_1,stu_2;student*p;p=&stu_2;stu_1.num=89101;strcpy(stu_1.name,Li Lin);stu_1.sex=M;stu_1.score=89.5;stu_2=stu_1;/结构体变量整体赋值结构体变量整体赋值 coutnum name ；coutsex scoreendl;cout(*p).num (*p).name ；cout(*p).sex (*p).score成员名成员名指向运算符指向运算符 Saturday,October 06,2012 337 内存动态分配与释放（运算符n

30、ew和delete）C+提提供供了了较较简简便便而而功功能能较较强强的的运运算算符符new和和delete来来取取代代malloc、calloc和和free函数。函数。(1)new运算符运算符简单变量动态存储格式为：简单变量动态存储格式为：指针变量指针变量=new 类型名（初值表列）；类型名（初值表列）；例如：例如：int*p=new int;/开辟一个存放整数的空间，返回一个指向整型数据的指针开辟一个存放整数的空间，返回一个指向整型数据的指针 int*p=new int(100);/开辟一个存放整数的空间，并指定该整数的初值为开辟一个存放整数的空间，并指定该整数的初值为100 float*p

31、=new float(3.14159)/开开辟辟一一个个存存放放浮浮点点数数的的空空间间，并并指指定定该该浮浮点点数数的的初初值值为为3.14159，将返回的指向实型数据的指针赋给指针变量，将返回的指向实型数据的指针赋给指针变量p。Saturday,October 06,2012 34数组动态存储格式：数组动态存储格式：指针变量指针变量=new 类型名类型名元素个数元素个数；如如:int n=5,*p=new intn;char*ps=new char10;/开辟一个存放字符数组的空间，该数组有开辟一个存放字符数组的空间，该数组有10个元素，返个元素，返回一个指向字符数据首字符的指针回一个指向

32、字符数据首字符的指针 float(*q)4=new float54;/申请可存放申请可存放5行行4列浮点数的空间列浮点数的空间注：注：用用new分配数组空间时不能指定初值。分配数组空间时不能指定初值。(2)delete运算符运算符格式格式:delete 指针变量指针变量作用作用:释放由释放由new申请到的内存空间。申请到的内存空间。如：如：delete p;delete ps,q;/加方括号，表示对数组空间的操作加方括号，表示对数组空间的操作 Saturday,October 06,2012 35例例9：动态开辟空间以存放一个结构体变量：动态开辟空间以存放一个结构体变量#include#inc

33、lude 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;coutName:name Num:num;cout Sex:sexendl;delete p;Saturday,October 06,2012 36例例10：链表创建与遍历：链表创建与遍历#include#include struct student long num;float score;student*next;int n=0;/统计结

34、点个数统计结点个数void main()void print(student *head);/函数声明函数声明 student*creat();student*head;head=creat();print(head);Saturday,October 06,2012 37student*creat()/创建链表创建链表 student*head,*p1,*p2;p1=p2=new student;cout请输入编号与成绩请输入编号与成绩(输入输入0 0 结束结束):p1-nump1-score;head=NULL;while(p1-num!=0)n+;if(n=1)head=p1;else

35、p2-next=p1;p2=p1;p1=new student;cinp1-nump1-score;p2-next=NULL;return head;Saturday,October 06,2012 38void print(student*head)/遍历链表遍历链表 student*p;coutendlNow,These n records are:endl;p=head;if(head)do coutnum scorenext;while(p!=NULL);Saturday,October 06,2012 398 8 枚举枚举定义枚举类型的一般格式：定义枚举类型的一般格式：enum 枚举

36、类型名枚举类型名枚举元素表枚举元素表；例如：例如：enum bool true,false;说明：说明：1.枚举元素为符号常量，不能改变其值；枚举元素为符号常量，不能改变其值；2.枚举常量的值为整数，按定义时的顺序依次为枚举常量的值为整数，按定义时的顺序依次为: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;co

37、utday;/结果为结果为14.枚举值可以比较大小枚举值可以比较大小 Saturday,October 06,2012 40例例11：由序号求枚举值：由序号求枚举值#include /C:/Program%20Files/Microsoft%20Visual%20Studio/Common/MSDev98/Bin/MSDEV.EXE%20%20./%E4%BE%8B1.cppvoid main()int i;typedef enum a=1,b,c,d character;character gc;couta b c di;gc=character(i);switch(gc)case a:co

38、uta;break;case b:coutb;break;case c:coutc;break;case d:coutd;break;Saturday,October 06,2012 419 用typedef定义类型用用typedef声明新的类型名来代替已有的类型名。声明新的类型名来代替已有的类型名。typedef int INTEGER;/声明声明INTEGER为整型为整型 typedef float REAL;声明结构类型声明结构类型 typedef struct int month；int day；int year；DATE;变量声明：变量声明：INTEGER i,j,k;REAL x,

39、y,z;DATE birthday,workday;Saturday,October 06,2012 42用用typedeftypedef定义类型的方法：定义类型的方法：先按定义变量的方法写出定义体（如：先按定义变量的方法写出定义体（如：intint i i）。）。将变量名换成新类型名（例如：将将变量名换成新类型名（例如：将i i换成换成COUNTCOUNT）。）。在最前面加在最前面加typedeftypedef （例如：（例如：typedeftypedef intint COUNT COUNT）。）。然后可以用新类型名去定义变量。然后可以用新类型名去定义变量。如：如：先按定义数组变量形式书写

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