C-C++程序设计教程-面向过程分册（第5版）课件 第8章 指针和引用

第8章指针和引用本章学习重点掌握内容：指针与指针变量指针与数组字符指针与字符串指针与函数动态内存分配和释放链表引用类型变量*第8章指针和引用8.1指针与指针变量8.2指针与数组8.3字符指针与字符串8.4动态内存分配和释放8.5指针与函数8.6const指针8.7结构体指针8.8链表8.9引用28.1指针与指针变量8.1.1地址与指针的概念1．地址内存储器由一个个的存储单元组成，每个存储单元的大小为一个字节，每个单元有一个唯一的地址2．变量的地址取地址运算符（&）变量a的存储地址:3．指针一个变量在内存中所占存储单元的地址称为指针，也就是指向该变量的指针.38.1.1地址与指针的概念【例8.1】编程定义一个整型变量，输出该变量的值以及该变量的地址。#include<iostream>usingnamespacestd;intmain(){inti=100;cout<<"变量的值为："<<i<<endl;cout<<"变量的地址为："<<&i<<endl;return0;}48.1.2指针变量专门用于存放地址的变量称为指针变量。其定义的一般形式为：类型标识符*指针变量表int*ip1;（1）“*”定义变量为指针的说明符，（2）指针变量也是一个变量。（3）指针变量名的命名符合标识符的命名规则。（4）类型是该指针变量所要指向的变量的类型。（5）C++语言中定义了一个符号常数

NULL，用来代表空指针值。在VisualC++中，NULL

被定义为

\0x0。58.1.2指针变量变量的指针:指针是某一变量在内存中所占存储单元的地址，是一个地址值。指向变量的指针变量是专门存放其他变量的地址的变量，是个变量，如果某一指针变量中存放了另外一个变量的指针，则称该指针变量是指向那个变量的指针变量。68.1.2指针变量2.与指针有关系的两个运算符（1）&运算符：取地址运算符，用来得到一个普通变量的地址。inti=100;//定义整型数iint*pi;//定义整型指针变量pipi=&i;//将变量i的地址赋值给整型指针变量pi（2）*运算符：间接引用运算符，用来获取指针变量所指向变量的值，后面跟指针变量。inti=100,y;int*ip;ip=&i;78.1.2指针变量3.指针变量的初始化指针变量在定义后，指针变量的值是随机的。声明指针的同时进行初始化赋值类型标识符*指针变量名=初始地址；inti=10,*ip=&i;指针变量名=初始地址；inti;int*pi;//定义整型指针变量pipi=&i;//将整数i的地址赋值给指针变量pi，也就是说使pi指向i*p=100;//相当于i=100;88.1.2指针变量【例8.2】指针变量及其使用方法。#include<iostream>usingnamespacestd;intmain(){inta,b;int*p1,*p2;a=100;b=200;p1=&a;//把变量a的地址赋给指针变量p1，即指针变量p1指向变量ap2=&b;//把变量b的地址赋给指针变量p2，即指针变量p2指向变量bcout<<a<<','<<b<<endl;//输出100，200cout<<*p1<<','<<*p2<<endl;//等价于cout<<a<<','<<b<<endl;return0;}98.1.2指针变量【例8.3】使用指针求两个数的最大值并按从大到小顺序输出。#include<iostream>usingnamespacestd;intmain(){int*p1,*p2,*p,a,b;cout<<"请输入两个数："<<endl;cin>>a>>b;p1=&a;p2=&b;if(a<b){p=p1;p1=p2;p2=p;}cout<<"a="<<a<<",b="<<b<<endl;cout<<"max="<<*p1<<",min="<<*p2<<endl;return0;}108.1.3指针变量的运算指针变量是有类型的即一个指针变量只能指向同一类型的变量。不同类型的指针变量是不可以互相赋值的。指针变量的算术运算指针和整数可进行加、减运算。指针加一，不是加一个单元，而是加指针指向类型所占的单元数。11【例8.4】指针变量的自加、自减、加n和减n运算，如图8-6所示。#include<iostream>usingnamespacestd;intmain(){inta[5]={0,1,2,3,4};int*p;p=&a[0];p++;cout<<*p<<'\t';p=p+3;cout<<*p<<'\t';p--;cout<<*p<<'\t';p=p-3;cout<<*p<<'\t';return0;}8.1.3指针变量的运算12指针变量的关系运算（1）通常指针变量可以进行相等、不等比较（2）任一指针变量可以和NULL进行相等、不等的比较。（3）指向数组元素指针间进行大于、小于、大于等于、小于等于等比较。8.1.3指针变量的运算13【例8.5】用指针变量求数组元素的和，并输出数组每个元素的值及和。#include<iostream>usingnamespacestd;intmain(){inta[5]={1,2,3,4,5},sum=0;int*p,*p1;p1=&a[4];for(p=&a[0];p<=p1;p++){sum+=*p;cout<<*p<<'\t';}cout<<"\nsum="<<sum<<endl;return0;}8.1.3指针变量的运算148.1.4void指针指向void类型指针称为空类型指针。不指定指针指向一个固定的类型。void*指针变量名;void*p;void指针它可以指向任何类型的C++数据。可以用任何类型的指针直接给void指针赋值。158.2.1一维数组与指针数组名就代表数组首地址，也就是数组下标0的元素的地址，因此可以将数组名作为地址赋值给指针变量。inta[10];int*p;p=&a[0];//p=a;引用数组元素(1)下标方式：数组名[下标](2)地址方式：*(地址)(3)指针方式：*指针变量名168.2.1一维数组与指针【例8.6】设有一个数组a，有5个元素。用四种方法输出各元素。#include<iostream>usingnamespacestd;intmain(){inta[5]={23,12,45,33,67},*p=a,i;cout<<"下标方式：";for(i=0;i<5;i++)cout<<a[i]<<"";cout<<"\n地址方式：";for(i=0;i<5;i++)cout<<*(a+i)<<"";cout<<"\n指针方式1：";for(i=0;i<5;i++)cout<<*(p+i)<<"";cout<<"\n指针方式2：";for(p=a;p<a+5;p++)cout<<*p<<"";return0;}178.2.2二维数组与指针

二维数组元素的地址a代表二维数组的首地址，也可看成是二维数组第0行的首地址。a+1就代表第1行的首地址，a+2就代表第2行的首地址188.2.2二维数组与指针【例8.7】定义一个3行3列数组，输出每行的首地址及所有元素值。#include<iostream>usingnamespacestd;intmain(){inta[3][3]={{1,2,3},{4,5,6},{7,8,9}};for(inti=0;i<3;i++){cout<<"a["<<i<<"]="<<a[i]<<""<<&a[i][0]<<endl;for(intj=0;j<3;j++)cout<<"a["<<i<<"]["<<j<<"]="<<*(a[i]+j)<<"="<<a[i][j]<<endl;}return0;}198.2.2二维数组与指针【例8.8】用指针变量输出一个3行4列二维数组各元素的值#include<iostream>usingnamespacestd;intmain(){inta[3][4]={1,3,5,7,9,11,13,15,17,19,21,23};int*p;//p是为整型指针变量for(p=a[0];p<a[0]+12;p++)cout<<*p<<"";cout<<endl;return0;}20指向一个数组整体的指针称为数组指针，类型（*指针变量名）[数组元素数];int(*pa)[6];通常使用指向一维数组的指针指向某个二维数组的某一行，因为二维数组的某行是一个一维数组inta[5][5];int*p=&a[0][0];//指针p指向整型元素a[0][0]，p是整型指针int(*pa)[5]=a;

//指针pa指向整型一维数组a[0],pa是指向数组的指针8.2.3指向数组的指针218.2.4指针数组数组元素都为指针的数组称为指针数组类型*数组名[数组元素个数];int*p[4]；inta,b,c[2][3];int*p1[2]={&a,&b};int*p2[2]={c[0],c[1]};228.2.5指向指针的指针（多级指针）类型

**变量名;inta=100;int*p1=&a;int**p2=&p1;238.2.5指向指针的指针【例8.9】二级指针的应用#include<iostream>usingnamespacestd;intmain(){inta=1,*p=&a,**pp=&p;cout<<"a="<<a<<endl;cout<<"*p="<<*p<<endl;cout<<"p="<<p<<endl;cout<<"*pp="<<*pp<<endl;//*pp是pcout<<"**pp="<<**pp<<endl;//**pp是间接访问p指针指向的内容即a**pp=100;//相当于a=100cout<<"a="<<a<<endl;return0;}248.3字符指针与字符串8.3.1字符数组与字符指针数组元素类型为字符型的数组称为字符数组。字符数组可存放字符，也可以存放字符串。指向字符串的指针变量称为字符指针，用于保存字符串的首地址。字符指针可以指向一个字符串，字符指针数组可用来指向多个字符串。char*指针变量名[=<字符串>]charstr1[10]="hello",*str2="hello";258.3字符指针与字符串（1）字符数组由若干个元素组成，每个元素存放字符串一个字符字符指针变量存放的是字符类型的地址，字符串首地址。（2）对字符数组初始化是把字符串的各个字符放到字符数组中；对字符指针初始化是把地址赋给字符指针变量。268.3字符指针与字符串（3）对字符数组赋值，只能一个元素一个元素进行，不能对整个数组名赋值，因为数组名是地址；字符指针变量可以用赋值语句赋地址。例如：charstr[6];str="ok";char*ps;ps="hello";ps=str;strcpy(str,"study");（4）用字符数组和字符指针都可以表示字符串，在处理字符串的输入输出时，可以直接输入输出数组名或字符指针名，表示将整个字符串输入输出。278.3字符指针与字符串【例8.10】定义字符数组和字符指针表示字符串，输入输出字符串。#include<iostream>usingnamespacestd;intmain(){chars1[10],s2[10],*pc=s2;cout<<"请输入两个字符串:"<<endl;cin>>s1>>pc;cout<<"s1:"<<s1<<endl;cout<<"pc:"<<pc<<endl;return0;}288.3.2字符指针数组char*数组名[整型常量表达式];char*s[3]={"study","work","life"};298.4动态内存分配和释放308.4.1C++中堆的使用1、new运算符（1）指针变量=new

类型标识符;作用：动态分配由类型确定大小的连续内存单元，并将内存首地址赋给指针变量。（2）指针变量=new类型标识符(value);作用：除完成（1）的功能外，还将value作为所分配内存单元的初始值。（3）指针变量=new类型标识符[表达式];作用：申请一块内存单元用于保存数组。可以通过指针的变化访问所分配单元的每一个元素。（4）指针变量=new类型标识符[表达式]{初始值};作用：申请一块内存单元用于保存数组。并指定初始值。312、delete运算符（1）delete指针变量;作用：将指针变量所指的内存空间归还系统。delete只是删除动态内存空间，并不会删除指针变量。释放内存单元后，该指针变量成为空指针。（2）delete[]

指针变量;或

delete[元素数]

指针变量;作用：将指针变量所指数组内存空间归还给系统。delete[]的方括号中不需要填数组元素数，系统自知。8.4.1C++中堆的使用32new与delete是配对使用的，delete只能释放堆单元。如果new返回的指针值丢失，则所分配的堆单元无法回收，称内存泄漏，同一单元重复释放也是危险的，因为该单元可能已另分配.所以必须妥善保存new返回的指针，以保证不发生内存泄漏，也必须保证不会重复释放堆内存单元。8.4.1C++中堆的使用33【例8.11】用new运算符动态生成由n个元素组成的一维数组，给一维数组输入n个值，求出并输出一维数组元素和，最后用delete运算符动态回收一维数组所占用的内存单元。#include<cstdlib>//exit()函数需要的头文件#include<iostream>usingnamespacestd;intmain(){inti,n,sum=0;cout<<"输入数组长度n:";cin>>n;

int*p=newint[n];//动态分配由n个整型元素组成的一维数组，首地址赋pif(p==NULL){//分配内存单元不成功cout<<"堆分配失败!";

exit(1);//结束程序}cout<<"输入"<<n<<"个元素值：";for(i=0;i<n;i++)cin>>p[i];//给n个元素赋值。for(i=0;i<n;i++)sum+=p[i];//计算n个元素和cout<<"sum="<<sum<<endl;

delete[n]p;//动态归还p所指一维数组内存单元，对于数组，[]是必须的return0;}8.4.1C++中堆的使用348.4.2C语言中堆的使用0．需要的头文件#include<stdlib.h>1．堆的分配malloc函数原型：void*malloc(size_tsize);表示在申请分配size_tsize字节大小的内存空间；如果分配成功，则函数返回为该内存空间的首地址；如果分配失败，则返回NULL。2．堆的释放free(指针变量);35【例8.12】用malloc函数动态生成由n个元素组成的一维数组，输入n个值给一维数组，求出并输出一维数组元素和，最后用free()函数动态回收一维数组所占用的内存空间。8.4.2C语言中堆的使用#include<stdio.h>#include<stdlib.h>//malloc(),exit()需要intmain(){inti,n,sum=0;printf("输入数组长度n:");scanf("%d",&n);int*p=(int*)malloc(n*sizeof(int));//动态分配堆内存空间，首地址赋pif(p==NULL){//分配内存空间不成功printf("堆内存分配失败!");exit(1);}printf("输入%d个元素值：",n);for(i=0;i<n;i++)scanf("%d",p+i);//给n个元素赋值。for(i=0;i<n;i++)sum+=p[i];//计算n个元素和printf("sum=%d\n",sum);

free(p);//释放p所指向的一维数组内存空间return0;}368.5指针与函数8.5.1指针变量与数组名作函数参数函数的参数可以为整型、实型、字符型等基本数据类型的变量。实参与形参间参数的传递是单向的“值传递”。函数的参数也可为指针，实参与形参间参数的传递是“地址传递”。1.指针变量作为函数参数指针变量作为函数参数的函数定义格式：类型标识符函数名(类型*指针变量名，…){

函数体

}函数调用格式：函数名(&变量，…)或函数名(指针变量，…)37【例8.13】编写两个数据交换的函数（传值方法）。#include<iostream>usingnamespacestd;voidswap(int,int);//函数的原型intmain(){inta=3,b=8;cout<<"交换前:"<<endl;cout<<"a="<<a<<"\tb="<<b<<endl;swap(a,b);//函数的调用cout<<"交换后："<<endl;cout<<"a="<<a<<"\tb="<<b<<endl;return0;}voidswap(intx,inty){//函数的定义，x,y重新分配内存inttemp=x;x=y;y=temp;//变量x，y实现交换}8.5.1指针变量与数组名作函数参数38【例8.14】用指针变量作为函数参数实现两个数据的交换（传地址方法）。#include<iostream>usingnamespacestd;voidswap(int*,int*);//函数的原型intmain(){inta=3,b=8;cout<<"交换前:"<<endl;cout<<"a="<<a<<"\tb="<<b<<endl;swap(&a,&b);//函数的调用，以变量a和变量b的地址作为实参值。cout<<"交换后："<<endl;cout<<"a="<<a<<"\tb="<<b<<endl;return0;}voidswap(int*x,int*y){//给指针x,y重新分配内存inttemp=*x;*x=*y;*y=temp;//实现指针所指向变量交换}8.5.1指针变量与数组名作函数参数398.5.1指针变量与数组名作函数参数#include<iostream>usingnamespacestd;voidsum(intarray[],intn){intsum=0,i=0;

while(i<n)

sum+=array[i++];

cout<<sum<<endl;}intmain(){

inta[10]={1,2,3,4,5,6,7,8,9,10};

sum(a,10);

return0;}【例8.15】形参和实参都用数组名来计算数组中各元素的和。40【例8.16】实参用数组名，形参用指针变量来计算数组中各元素的和。8.5.1指针变量与数组名作函数参数#include<iostream>usingnamespacestd;voidsum(int*array,intn){

intsum=0,i=0;

while(i<n)

sum+=array[i++];

cout<<sum<<endl;}intmain(){

inta[10]={1,2,3,4,5,6,7,8,9,10};

sum(a,10);

return0;}41【例8.17】编写函数实现字符串的复制功能。假设源字符串保存在数组ps中，目的字符型数组为pd，用字符指针作为函数参数完成字符串复制功能，程序如下：8.5.1指针变量与数组名作函数参数#include<iostream>usingnamespacestd;voidcopystr(char*s1,char*s2){

//复制函数

while(*s2!='\0')//判断源字符串是否结束

*s1++=*s2++;

*s1='\0';

//结束标识'\0'赋值给目的字符串}intmain(){

charps[]="ok",pd[]="hello";

copystr(pd,ps);

cout<<ps<<endl;

cout<<pd<<endl;

return0;}428.5.2返回指针型的函数#include<iostream>usingnamespacestd;int*max(intx,inty){//指针型函数maxreturn((x>y)?&x:&y);}int*min(intx,inty){//指针型函数minreturn((x<y)?&x:&y);}intmain(){

inta,b,*pm;

cout<<"输入两个整数:"<<endl;

cin>>a>>b;

pm=max(a,b);

cout<<"大的数是："<<(*pm)<<endl;

pm=min(a,b);

cout<<"小的数是："<<(*pm)<<endl;

return0;}【例8.19】输出两不同大小整数变量的较大值和较小值。438.5.3函数指针数名对应着该函数存放在内存中的首地址通过使用函数的地址，也可以调用函数。函数指针即指向一个函数的指针。它的值只能是代码区中的一个地址函数指针定义格式如下：类型标识符(*函数指针名)(参数表)float(*pf)(floatx);44【例8.19】用函数指针的方法求两数中的较大值。#include<iostream>usingnamespacestd;intmax(int,int);//函数声明intmain(){

int(*p)(int,int);/*定义函数指针，用于存放函数入口地址*/inta,b,c;p=max;/*用函数指针指向函数*/cin>>a>>b;c=(*p)(a,b);/*通过函数指针变量p调用所指向的函数*/cout<<"a="<<a<<"b="<<b<<"max="<<c<<endl;return0;}8.5.3函数指针intmax(intx,inty){intz;if(x>y)z=x;elsez=y;return(z);}458.5.3函数指针#include<iostream>usingnamespacestd;intmain(){

intselect;

while(true){

cout<<"1----添加学生信息\n";

cout<<"2----修改学生成绩\n";

cout<<"3----查询学生信息\n";

cout<<"4----按总成绩排序\n";

cout<<"5----删除学生信息\n";

cout<<"0----退出系统\n";

cin>>select;

switch(select){

case0:

return0;

//结束函数

case1:

add();

continue;//返回功能菜单

case2:

modify();

continue;

case3:

query();

continue;

case4:

sort();

continue;

case5:

del();

continue;

}

}}【例8.20】使用函数指针实现菜单界面。设计一个学籍管理系统，系统具有如下功能：选择1，录入学生信息和成绩；选择2，修改学生成绩；选择3，按姓名查询学生信息；选择4，按总分由高到低排出名次；选择5，删除学生信息；选择0，退出系统。在设计中将每一个功能设计成一个函数，根据选择的不同，调用相应的函数，实现功能。====//定义相关函数voidadd(){cout<<"添加学生信息"<<endl;}voidmodify(){cout<<"修改学生信息"<<endl;}voidquery(){cout<<"查询学生信息"<<endl;}voidsort(){cout<<"排序学生信息"<<endl;}voiddel(){cout<<"删除学生信息"<<endl;}468.5.3函数指针#include<iostream>usingnamespacestd;intmain(){

intselect;

//指向函数的指针数组

void(*func[])()={NULL,add,modify,query,sort,del};

while(true){//使每个数组元素指向不同的函数

cout<<"1----添加学生信息\n";

cout<<"2----修改学生成绩\n";

cout<<"3----查询学生信息\n";

cout<<"4----按总成绩排序\n";

cout<<"5----删除学生信息\n";

cout<<"0----退出系统\n";

cin>>select;

if(select==0)return0;//结束函数调用

if(select>5)cout<<"您输入错误\n";

elsefunc[select]();//通过函数指针调用函数

continue;

//返回主菜单}}【例8.20】使用函数指针实现菜单界面。设计一个学籍管理系统，系统具有如下功能：选择1，录入学生信息和成绩；选择2，修改学生成绩；选择3，按姓名查询学生信息；选择4，按总分由高到低排出名次；选择5，删除学生信息；选择0，退出系统。在设计中将每一个功能设计成一个函数，根据选择的不同，调用相应的函数，实现功能。====//定义相关函数voidadd(){cout<<"添加学生信息"<<endl;}voidmodify(){cout<<"修改学生信息"<<endl;}voidquery(){cout<<"查询学生信息"<<endl;}voidsort(){cout<<"排序学生信息"<<endl;}voiddel(){cout<<"删除学生信息"<<endl;}478.6const指针8.6.1指向常量的指针变量的定义与使用指向常量的指针变量的定义const

类型标识符*指针变量名；定义指针变量所指数据为常量指针指向的内容不允许改变constint*p;//等同于

constint(*p);48#include<iostream.h>voidmain(){constinti=20;intk=40;

constint*p;//指向常量的指针（常量指针），目标内容不能改变p=&i;//指针变量p指向变量icout<<*p<<''<<i;*p=100;//该句错误，不可借助p对它所指向的目标进行重新赋值

p=&k;//可以使p指向另外一个同类型的变量

cout<<*p<<''<<k;*p=200;//该句错误，不能修改p指向的内容

k=200;}8.6.1指向常量的指针变量的定义与使用【例8.21】指向常量的指针变量的使用。498.6.2指针常量指针常量的定义：类型标识符*const

指针变量名=初始指针值;指针本身的值不可改变它不能再指向其它的对象，但它所指向的对象的值可以改变。指针常量在定义时必须初始化char*constp="asked";50#include<iostream>usingnamespacestd;intmain(){chars[]="asked";

char*constp=s;//必须初始化

p="xyz";//该句错误，不可再指向另外的地址

cout<<*p;

*p='s';//正确，可以改变指针指向的内容

cout<<*p;

p++;//该句错误，p的指向不可修改。

*p='q';

cout<<*p<<endl;

return0;}8.6.2指针常量【例8.22】指针常量的使用。518.6.3指向常量的指针常量指向常量的指针常量的定义：const

类型标识符*const指针变量名=初始指针值;指向常量的指针常量：既不允许修改指针变量的值也不允许借助该指针变量对其所指向的对象的值进行修改在定义时必须初始化intb;constint*constp=&b;//指向常量的指针常量528.6const指针538.7结构体指针指针指向结构体变量，指向结构体变量的指针称为结构体指针。结构体变量在内存中要占据一定的内存空间，那么它肯定有起始地址。结构体指针指向了结构体变量.结构体指针变量中的值就是所指向的结构体变量的起始地址引用结构体成员的方法:结构体变量.成员名(*p).成员名p->成员名548.7.1结构体指针的概念#include<iostream>#include<cstring>usingnamespacestd;structstudent{longintnum;

charname[20];

chargender;

floatscore;}stu,*p;intmain(){

p=&stu;//指针指向结构体

stu.num=2006101;//引用方法1

strcpy(,"李琳");

p->gender='M';//引用方法3

p->score=89;//下面是引用方法2

cout<<(*p).num<<","<<p->name<<",";

cout<<stu.gender<<","<<p->score<<endl;

return0;}【例8.23】通过指针变量p引用它所指向的结构体变量stu中的成员值。558.7.2指向结构体数组元素的指针structstudent{intnum;charname[20];charsex;intage;}stu[3],*p;p=stu；//指针p指向结构体

stu[0]p++;//指针p指向下一个结构体56#include<iostream>#include<cstring>usingnamespacestd;structstudent{longintnum;charname[20];charsex;intage;}stu[3]={{2006101,"LiLin",'M',18},{2006102,"ZhangFeng",'M',19},{2006103,"WangMin",'F',20}};8.7.2指向结构体数组元素的指针intmain(){

student*p;//结构体指针

for(p=stu;p<stu+3;p++)

cout<<p->num<<","

<<p->name<<","

<<p->gender<<","

<<p->age<<endl;

return0;}【例8.24】通过指向结构体指针p输出结构体数组元素的成员数据578.7.3结构体指针作为函数参数#include<iostream>usingnamespacestd;structstudent{

intnum;

charname[20];

intscore;

chargrade;};voidsetgrade(student*p){

intk;

for(k=0;k<3;k++,p++){

if(p->score>=85)p->grade='A';

elseif(p->score>=70)p->grade='B';

elseif(p->score>=60)p->grade='C';

elsep->grade='D';

}}intmain(){

studentstu[3],*q;

inti;

q=stu;//指向结构体数组

for(i=0;i<3;i++){//输入数据

cout<<"输入学生"<<i+1<<"的信息：";

cin>>stu[i].num>>stu[i].name>>stu[i].score;

}

setgrade(q);//设置等级

for(i=0;i<3;i++)//输出结果

cout<<stu[i].num<<","<<stu[i].name<<","

<<stu[i].score<<","<<stu[i].grade<<endl;

return0;}【例8.25】输入3个学生的基本信息，每个学生的信息包括学号、姓名、成绩、等级，在自定义函数中实现根据学生的成绩设置其等级（成绩≥85为A，成绩≥70为B，成绩≥60为C，成绩<60为D）。588.8链表链表是一种动态数据结构，它的特点是：用一组任意的存储单元(可以是连续的，也可以是不连续的)存放数据元素。链表（SingleLinkedlist）也称线性链表。由一个个结点（Node）组成链表的头指针head指向链表的第一个结点，指针变量的值为链表的第一个结点的地址。链表中最后一个结点称为链尾或表尾表尾结点中存放一个NULL(表示空地址)，因此该结点不再指向其它结点。598.8.1链表概述在链表中，可以从第一个结点开始遍历全部结点要访问第i个结点，必须首先访问第i-1个结点，取出第i个结点的地址。structnode{intinfo;//数据域

node*next;//指针域};链表的特点在于动态地进行内存分配即在需要时才会开辟一个结点的存储空间，当某个存储空间不再需要时可以释放。608.8.2链表的基本操作（1）创建链表和遍历链表；（2）查找结点；（3）插入结点：包括在第一个结点之前、在中间结点之前或在链尾结点之后；（4）删除结点。61建立和遍历链表1）向后建立链表（新结点插入链尾）的过程可以描绘为：头指针为空；while（未结束）{

生成新结点，判断是否第一个结点；

是第一个结点，头指针就指向第一个结点

不是第一个结点，则把新结点插入链尾；}8.8.2链表的基本操作628.8.2链表的基本操作

新生成的结点p插入链尾638.8.2链表的基本操作【例8.26】以“向后生成”的方式建立学生情况（仅含学号）的链表。假设从键盘输入时，如果学号为

0

表示链表建立过程结束。#include<iostream>usingnamespacestd;structnode{//链表节点

intinfo;//数据域

node*next;//指针域};node*createdown();intmain(){

node*chain,*p;//定义链表

chain=createdown();//创建链表

p=chain;//显示链表内容

while(p!=NULL){

cout<<p->info<<endl;

p=p->next;

}

deletechain;//释放内存空间

return0;}648.8.2链表的基本操作【例8.26】以“向后生成”的方式建立学生情况（仅含学号）的链表。假设从键盘输入时，如果学号为

0

表示链表建立过程结束。node*createdown(){//指针函数node*head=NULL,*tail,*p;intdata;//结点中的数据do{cout<<"输入结点数据(0结束)：";cin>>data;//获取结点数据if(data!=0){//接收到的数据

p=newnode;//申请结点内存

p->info=data;//写入结点数据

p->next=NULL;//链尾特征if(head==NULL){//链表无结点head=tail=p;//首尾指向一处}else{

tail->next=p;//加入新的链尾

tail=p;//更新链尾指针}}else{

break;//接收到0，结束循环}}while(true);

returnhead;//返回链首指针}658.8.2链表的基本操作（2）遍历链表voiddisplay(node*head)//遍历链表{node*q=head;while(q!=NULL){cout<<setw(3)<<q->info;

q=q->next;}cout<<endl;}668.8.2链表的基本操作二、链表查找node*traversal(node*head,intdatafind){node*p=head;while(p!=NULL&&p->info!=datafind)p=p->next;returnp;//p为NULL则未找到}678.8.2链表的基本操作三、插入结点在表头插入结点:①生成新结点；②把新结点连接到表头；③修改表头指针。688.8.2链表的基本操作【例8.27】以“向前生成”的方式建立学生情况（仅含学号）的链表。假设从键盘输入时，如果学号为0表示链表建立结束。node*createup(){node*head=NULL,*p;//空链表intdata;do{cout<<"节点数据(0结束):";cin>>data;if(data!=0){//有效数据p=newnode;//创建结点p->info=data;//写入数据p->next=head;//链接结点head=p;//更新链首}else{

break;//数据为0则结束}}while(true);returnhead;}698.8.2链表的基本操作（2）在

p结点之前插入NewNode结点708.8.2链表的基本操作（3）在链尾结点之后插入结点718.8.2链表的基本操作【例8.28】在头指针为head的学生链表中，在数据值等于key的结点前面插入学号数据值等于insertKey的结点，并返回头指针。#include<iomanip>usingnamespacestd;structnode{//链表节点intinfo;//数据域node*next;//指针域};voidshowChain(node*chain){node*p=chain;//显示链表内容while(p!=NULL){cout<<setw(3)<<p->info;p=p->next;}cout<<endl;}intmain(){node*chain;//定义链表chain=createup();//创建链表showChain(chain);//显示链表chain=insert(3,6,chain);//找3并在其前插入6showChain(chain);//显示链表deletechain;//释放内存空间return0;}728.8.2链表的基本操作【例8.28】在头指针为head的学生链表中，在数据值等于key的结点前面插入学号数据值等于insertKey的结点，并返回头指针。node*insert(intkey,intinsertKey,node*head){node*pre,*cur;if(head==NULL){//空链表cout<<"链表为空"<<endl;}else{//非空链表pre=cur=head;//开始指向链首if(cur->info==key){//key在链首node*np=newnode;//创建结点np->info=insertKey;//写入keynp->next=cur;//前插入结点head=np;//修改链首}else{//key不在链首do{pre=cur;//遍历链表查找keycur=cur->next;}while(cur!=NULL&&cur->info!=key);if(cur!=NULL){//找到keynode*np=newnode;//创建结点np->info=insertKey;//写入数据np->next=cur;//前插入结点pre->next=np;}else{//key不存在cout<<"链表中不存在key："<<key<<endl;}}}

returnhead;}738.8.2链表的基本操作四、删除结点（1）删除链首结点指针p指向链首，head指针指向它的下一个结点，释放原有的头结点。

node*p=head;head=p->next;//更新链首

p->next=NULL;//断开链接deletep;//删除链首748.8.2链表的基本操作（2）删除链表中间的结点p，需要知道其前驱结点指针q。

q->next=p->next;deletep;758.8.2链表的基本操作【例8.29】从头指针head的链表中删除结点数据值等于key的结点，并返回头指针。node*deleteNode(intkey,node*head){node*cur=head,*pre;if(head->info==key){//删除链首结点head=cur->next;deletecur;cout<<"删除成功"<<endl;returnhead;}for(pre=head;pre->next!=NULL;pre=pre->next)if(pre->next->info==key){//删除中间结点cur=pre->next;pre->next=cur->next;deletecur;cout<<"删除成功"<<endl;returnhead;}cout<<"无结点可删除，删除失败";returnhead;}768.9引用引用给一个已经定义的变量（目标变量）重新起一个别名，系统不为引用类型变量分配内存空间，对引用的操作就是对目标变量的操作主要用于函数之间的数据传递引用的声明：类型标识符&引用名=目标变量名；inta;int&ra=a;778.9.1引用及声明方法【例8.30】了解引用和变量的关系。#include<iostream>#include<iomanip>usingnamespacestd;intmain(){inta=10;int&b=a;//声明b是a的引用

a=a*a;//a值变化，b值也变化cout<<"a="<<a<<setw(10)<<"b="<<b<<endl;cout<<"&a="<<&a<<setw(10)<<"&b="<<&b<<endl;

b=b/5;//b值变化，a值也变化cout<<"b="<<b<<setw(10)<<"a="<<a<<endl;cout<<"&b="<<&b<<setw(10)<<"&a="<<&a<<endl;return0;}788.9.1引用及声明方法由于指针变量也是变量，可声明一个指针变量的引用。类型标识符*&引用名=指针变量名;

int*a;int*&p=a;intb=10;p=&b;cout<<*a<<endl;cout<<*p<<endl;不能建立数组的引用引用是对某一变量的引用，因此引用本身不占存储空间inta;int&ra=a;int&*p=&ra;//错误不能建立空类型void的引用void&ra=3;//错误798.9.2用引用作为函数的参数#include<iostream>usingnamespacestd;voidswap(int&p1,int&p2){//形参都是引用intp;//系统不给p1,p2分配内存p=p1;p1=p2;p2=p;}intmain(){inta,b;cout<<"输入两个数:"<<endl;cin>>a>>b;//输入a,b两变量的值cout<<"交换前:"<<endl;cout<<a<<""<<b<<endl;swap(a,b);//直接以变量a和b作为实参调用swap函数cout<<"交换后:"<<endl;cout<<a<<""<<b<<endl;//输出结果return0;}【例8.31】使用引用作为函数参数，实现两个数交换。808.9.3函数同时返回多个值【例8.32】使用引用使函数返回多个值。编写可以同时返回10个数中的最大值和最小值的函数max_min。#include<iostream.h>voidmax_min(int*p,intn,int&max,int&min);

//声明函数max_minvoidmain(){inta[10],ma,

mi;for(inti=0;i<10;i++)

cin>>a[i];max_min(a,10,ma,mi);//调用函数

max_mincout<<ma<<'\t'<<mi<<endl;}818.9.3使一个被调函数同时返回多个值voidmax_min(int*p,intn,int&max,int&min){//形参max和min定义成引用inti=0;//从头开始max=*(p+i);min=*(p+i);for(i=1;i<n;i++){if(max<*(p+i))max=*(p+i);//这就是对实参变量ma赋值if(min>*(p+i))min=*(p+i);//这就是对实参变量mi赋值

}}828.9.4用const限定引用【例8.33】用const限定引用，禁止通过引用修改目标，常用于函数的参数设计。#include<iostream>usingnamespacestd;intfn(constint&x){inty;//x++;错误，x不能修改y=x;cout<<"x="<<x<<'\t';returny;}intmain(){inta=100;intpa=fn(a);cout<<"a="<<a<<'\t';cout<<"pa="<<pa<<endl;return0;}838.9.5用引用作为函数返回值【例8.34】用返回引用的函数值作为赋值表达式的左值。#include<iostream>usingnamespacestd;int&put(intn);//返回引用的函数intvals[10],error=-1;intmain(){

put(0)=10;//等价于vals[0]=10;

put(9)=20;//等价于vals[9]=10;cout<<vals[0];cout<<vals[9];return0;}int&put(intn){if(n>=0&&n<=9)returnvals[n];else{cout<<"下标错误";returnerror;}}848.10综合应用实例【例3.35】编写返回指针值的函数。实现将输入的一个字符串按逆向输出。#include<iostream>usingnamespacestd;char*fun(char*p1){while(*p1++)

;//指针移到串尾p1--;returnp1;//指向串尾地址的指针}intmain(){chars1[100],*q,*p1;cout<<"输入一个字符串：";cin.getline(s1,