C语言程序设计中

会计学1C语言程序设计中第7章指针第1页/共253页讲授内容指针的定义与运算指针与数组的关系字符串函数指针与const限定符传递指针参数动态内存分配方法函数指针第2页/共253页7.1指针的定义指针：具有确定属性的地址属性决定了以该地址为起始地址的存储空间（数据单元）大小以及可以存放什么类型的数据指针变量：可以存放指针的变量第3页/共253页7.1指针的定义charc='7';char*chptr=&c;intcount=7;int*countptr=&count;11111100

countPtr01111100count701111100

int类型char类型‘7’01101100

11101100

chPtr01101100ch第4页/共253页7.1指针的定义指针变量声明

int*myPtr;说明了一个指向int类型的指针变量myPtr int*myPtr1,*myPtr2,i,j;可以说明指向任何数据类型的指针指针变量声明时可以初始化为0，NULL或某个地址0或NULL：不指向任何数据单元(推荐使用NULL)第5页/共253页7.2指针的运算&(一元运算，地址运算符)运算结果为操作数（非register）的地址，如inty=5;int*yPtr;yPtr=&y;使yPtr指向yyPtry5500000yptr600000y

y

的地址是

yptr的值6000005第6页/共253页7.2指针的运算*(一元运算，间接引用运算符，其操作数表达式的值必须是指针)，如int*yPtr,y;

yptr=&y; *yptr=7;*yptr=*yptr+7;指针指向的数据单元中的值（右值）指针指向的数据单元（左值）第7页/共253页7.2指针的运算*和

&互为

逆运算，如int*yPtr,y;

yptr=&y; *yptr=7;*yptr=*yptr+*&y;*&*&y=*yptr+*&y;第8页/共253页例子1：指针的运算(&、*的应用示例)#include<stdio.h>

intmain(){intn;int*nPtr;

n=7;nPtr=&n;printf("Theaddressofnis%p\nThevalueofnPtris%p",&n,nPtr);

printf("\n\nThevalueofnis%d\nThevalueof*nPtris%d",n,*nPtr);printf("\n\n&*nPtr=%p\n*&nPtr=%p\n",&*nPtr,*&nPtr);return0;}第9页/共253页7.2指针的运算指针的算术运算指针变量可以自增/自减(++或--)指针可以加/减一个整数(+或+=，-或-=)同类型指针可以相减一元运算符sizeof()操作数为变量名、类型名或常量运算结果为操作数所需存储单元的字节数特例：操作数为数组名时，结果为数组所需存储单元的总字节数如sizeof(int)、sizeof(int*)均为4声明intmyArray[10]，*p=myArray;后

sizeof(myArray)为40、sizeof(p)为4第10页/共253页7.2指针的运算Intv[5],*vPtr=v;

//vPtr为3000vPtr+=2;//赋值后vPtr为3008把vPtr的值当作整数和n*sizeof(int)相加，得到vPtr+n的实际值（指向后续第n个数组元素）指针变量vPtrv[0]v[1]v[2]v[4]v[3]30003004300830123016地址：第11页/共253页7.2指针的运算同类型指针相减

intv[5],*vPtr,*vPtr2;vPtr=&v[0];vPtr2=&v[2];//vPtr2-vPtr结果为2.把vPtr2和vPtr的值当作整数相减后除以sizeof(int)（两个指针间的数组元素个数）第12页/共253页7.2指针的运算指针的关系运算同类型指针可以进行各种关系运算可以判断指针是否为0或NULL

如intv[5],*vPtr,*vPtr2;vPtr=&v[0];vPtr2=&v[2];while(vPtr<vPtr2)vPtr++;第13页/共253页7.2指针的运算指针的赋值运算同类型指针可以赋值不同类型的指针之间的赋值必须进行强制类型转换如int*nPtr;floatf=0.5，*fPtr=&f;nPtr=(int*)fPtr;特例：void类型的指针(类型void*)可以指向任何类型的数据void*类型的指针不能被复引用

可以和其他类型的指针相互赋值第14页/共253页7.2指针的运算如void*vPtr;float*fPtr;vPtr=fPtr;fPtr=vPtr;但下面这种情况不行，必须进行类型的强制转换void*vPtr;float*fPtr;int*iptr;vPtr=fPtr;iPtr=vPtr;//错误

iPtr=(int*)vPtr;//正确第15页/共253页例子2：指针运算例子#include<stdio.h>

intmain(){charc='A',*pc;

intints[5]={1,2,3,4,5},*p1;intm=6,n=7;int*p2,*p3;pc=&c;

printf("c=\'%c\'\tpc=%p\t*pc=\'%c\'\n",c,pc,*pc);

pc+=5;printf("Afterpc+=5:\tpc=%p\n",pc);

p1=ints;

printf("\np1=%p\t*p1=%d\n",p1,*p1);第16页/共253页例子2：指针运算例子p1+=4;printf("Afterp1+=4:\tp1=%p\t*p1=%d\n",p1,*p1);p2=&m;p3=&n;printf("\np2=%p\t*p2=%d\n",p2,*p2);

printf("p3=%p\t*p3=%d\n",p3,*p3);

printf("p2-p3=%d\n",p2-p3);

if(p2<p3)printf("p2<p3\n");elseprintf("p2>=p3\n");

return0;}第17页/共253页程序运行结果c='A'pc=0012FF7C*pc='A'Afterpc+=5:pc=0012FF81

p1=0012FF64*p1=1Afterp1+=4:p1=0012FF74*p1=5

p2=0012FF5C*p2=6p3=0012FF58*p3=7p2-p3=1p2>=p3第18页/共253页7.3指针与数组数组名是指向该数组第一个元素的常量指针

intb[5],*bPtr;bPtr=b;//等价于bPtr=&b[0];*(bPtr+2)=5;//等价于b[2]=5;//等价于*(b+2)=5;等价于bPtr[2]=5;//等价于(b+2)[0]=5;等价于(bPtr+1)[1]=5;注：C++编译器把形如指针表达式[下标表达式]的下标运算转化为表达式*(指针表达式+下标表达式)即地址+偏移量的方式第19页/共253页7.3指针与数组指针数组——数组元素可以是指针

如：int*array[10],i;array[5]=&i;又如：char*suit[4]={"Hearts","Diamonds","Clubs","Spades"};suit的每个元素是一个字符(char)指针字符串中的字符并没有存放在数组中，数组中存放的是指向字符串的指针suit数组的元素数目是固定的，但字符串的长度可以不相等第20页/共253页7.3指针与数组指针数组suit的存储结构suit[3]suit[2]suit[1]suit[0]’H’’e’’a’’r’’t’’s’’\0’’D’’i’’a’’m’’o’’n’’d’’s’’\0’’C’’l’’u’’b’’s’

’\0’’S’’p’’a’’d’’e’’s’’\0’

第21页/共253页7.4常用字符串处理函数

(库文件string.h)求字符串长度：

intstrlen(constchar*s);

字符串拷贝：

char*strcpy(char*dest,constchar*src);字符串连接：char*strcat(char*dest,constchar*src);字符串比较：intstrcmp(constchar*s1,constchar*s2);第22页/共253页7.4常用字符串处理函数

(库文件string.h)在字符串中查找字符：char*strchr(constchar*s,intc);在字符串中反向查找字符：char*strrchr(constchar*s,intc);在字符串中查找字符串：char*strstr(constchar*s1,constchar*s2);打断字符串：char*strtok(char*s,char*delim);第23页/共253页例子3：字符串处理函数strtok的应用#include<stdio.h>#include<string.h>main(){chars[]="HelloC++World";char*d="";char*p;p=strtok(s,d);while(p){printf("%s\n",p);p=strtok(NULL,d);}return0;}

第24页/共253页7.5使用const限定符最低访问原则——良好的程序设计风格可用于不允许被修改的变量和形式参数，数据保护声明const变量时需要初始化constintstudNum=100;

第25页/共253页7.5使用const限定符指向常量数据的非常量指针

inti,j,*q;constint*p;p=&j; //允许p=&i; //允许i=10; //允许*P=5; //不允许

q=P; //不允许第26页/共253页7.5使用const限定符指向非常量数据的常量指针

intvar1,var2;int*constp=&var1;*P=5; //允许P=&var2; //不允许注：指向非常量数据的常量指针的初值有限制，如constintvar;int*constp=&var; //错误！第27页/共253页7.5使用const限定符指向常量数据的常量指针constintval=10;constint*constp=&val;*P=5; //不允许

或intvar;constint*constp=&var;*P=5; //不允许

var=5; //允许第28页/共253页7.5使用const限定符用于限定函数形式参数，以保护实参

voidoutput(constdouble*pd){cout<<*pd; //允许*pd=15.5;//不允许!}或voidoutput(constdouble&d){cout<<d; //允许

d=15.5;//不允许!}第29页/共253页7.6指针和引用指针和引用都可以实现通过一个变量访问另一个变量

inta;int*aptr=&a;*aptr=10;//修改了变量ainta;int&b=a;//定义引用变量b，b是a的别名b=10;//修改了变量a第30页/共253页例子4：参数为指针的函数#include<iostream.h>

voidswap(int*,int*);

intmain(){intx=10,y=20;swap(&x,&y); //传递x和y的地址

cout<<"x:"<<x<<"y:"<<y<<endl;return0;}

voidswap(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}第31页/共253页例子5：用指针实现冒泡排序函数voidswap(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}voidbubbleSort(int*array,intsize){intpass,j;for(pass=0;pass<size-1;pass++)for(j=0;j<size-pass-1;j++)if(array[j]<array[j+1])swap(&array[j],&array[j+1]);}第32页/共253页7.7动态内存分配静态内存分配声明变量,编译时可以确定所需内存空间大小栈式分配动态内存分配编译时可以确定所需内存空间大小，运行时分配通过malloc函数或运算符new实现和malloc函数对应的释放内存函数是free和new对应的释放内存运算符是delete有可能分配不成功堆式分配第33页/共253页7.7动态内存分配使用函数malloc和函数freevoid*malloc(unsignedsize);

例如：

int*p=(int*)malloc(sizeof(int));(*p)++;int*score=(int*)malloc(sizeof(int)*10);if(score!=NULL)for(intj=0;j<10;j++)cin>>score[j];voidfree(void*ptr);

如：free(p);free(score);第34页/共253页7.7动态内存分配使用new和delete运算符new运算符

int*p=newint;(*p)++;int*score=newint[10];for(intj=0;j<10;j++)cin>>score[j];使用delete运算符释放内存，如deletep;delete[]score;第35页/共253页例子6：对运行时指定数目的整数进行排序#include<stdlib.h>#include<iostream.h>

voidsortArray(int[],int);voiddisplayArray(int[],int);

intmain(){int*a;inti,num;

cout<<"Pleaseenterthenumberofintegers:";cin>>num;

a=newint[num];

if(a==NULL){cout<<"mallocerror!exit."<<endl;return1;}第36页/共253页例子6：对运行时指定数目的整数进行排序for(i=0;i<num;i++)cin>>a[i];

sortArray(a,num);

cout<<"Aftersorting:"<<endl;for(i=0;i<num;i++)cout<<a[i]<<"";cout<<endl;

delete[]a;

return0;

}第37页/共253页例子6：对运行时指定数目的整数进行排序voidsortArray(intb[],intlen){for(intpass=0;pass<len–1;pass++)for(inti=pass+1;i<=len–1;i++)if(b[pass]>b[i]){inthold=b[pass];b[pass]=b[i];b[i]=hold;}}第38页/共253页学习目的检测理解指针的概念掌握传递指针参数的机制理解指针、数组与字符串之间的关系掌握内存分配和释放的方法了解指针函数的作用第39页/共253页作业7.2,7.4,7.9,7.10上机：7.6,7.12,7.13第40页/共253页第8章结构、联合、枚举第41页/共253页讲授内容结构的定义与使用联合的定义与使用枚举的定义与使用第42页/共253页8.1结构逻辑上相关的数据的汇集其成员可以是任何类型结构可以拥有不同类型的成员（区别于数组）定义记录——新的数据类型和指针一起构成链表、栈、队列和树等数据结构和类（class）的定义非常相似第43页/共253页8.1.1结构的定义格式：struct<结构名> {<成员列表>};例子：

structstudent{intnum;charname[20];charsex;floatscore;};第44页/共253页8.1.1结构的定义解释：struct:保留字，表示开始定义结构studentstudent：结构名，用于说明结构类型的变量student有四个成员：int类型的num、char类型的数组name和变量sex以及float类型的score结构的定义以分号结尾第45页/共253页8.1.1结构的定义说明：结构成员不能是本结构的实例结构成员可以是指向本结构类型的指针结构定义不导致内存分配定义新类型第46页/共253页8.1.1结构的定义声明结构变量studentstud1,stud2,*sptr,stu[20];定义结构时同时声明结构变量structstudent{intnum;charname[20];charsex;floatscore;}stud1,stud2;第47页/共253页8.1.1结构的定义结构的定义可以嵌套structdate{intyear;intmonth;intday;};structpeople{intnum;charname[20];charsex;

datebirthday;};structpeoplewang;第48页/共253页8.1.1结构的定义结构变量的初始化studentstud5={102,"LiXiaoming",'M',92};第49页/共253页8.1.2引用结构变量成员结构变量的赋值stud1=stud2;

存取结构的成员点操作符(.)：和结构变量名一起使用printf("%s",);wang.birthday.year=1986;箭头操作符(->)：和结构指针名一起使用sptr=&stud1;printf("%s",sptr->name);sptr->name等价于(*sptr).name第50页/共253页8.2.1结构与函数预定义类型的结构成员可以作为普通变量使用假设有如下函数定义：

voidf1(int);voidf2(float);voidf3(char*);voidf4(int*)；voidf5(float*);声明结构变量：structstudentstud;第51页/共253页8.2.1结构与函数下面的函数调用是合法的：f1(stud.num);//传递stud.num的值f1([2]);//传递数组元素[2]的值f2(stud.score);//传递stud.score的值

f3();//传递数组的值，即第一个元素的地址f3(&[2])；//传递数组元素[2]的地址f4(&stud.num)；//传递成员stud.num的地址f5(&stud.score)；//传递成员stud.score的地址第52页/共253页8.2.1结构与函数结构变量也可以作函数的参数或返回值函数原型：voidf6(students);

voidf7(student&s);voidf8(student*s);函数调用：f6(stud);f7(stud);f8(&stud);第53页/共253页例子1：结构变量作为函数的参数#include<iostream.h>structstudent{intnum;charname[20];charsex;floatscore;};voidfunCallByValue(student);voidfunCallByReference(student&);voidfunCallByPointer(student*);voiddisplayStudentInfo(conststudent&);

第54页/共253页例子1：结构变量作为函数的参数voiddisplayStudentInfo(conststudent&stud){cout<<endl;cout<<"num="<<stud.num<<"\t";cout<<"name="<<<<"\t";cout<<"sex="<<stud.sex<<"\t";cout<<"score="<<stud.score<<endl;}voidfunCallByValue(studentstud){stud.score++;}voidfunCallByReference(student&stud){stud.score++;}

voidfunCallByPointer(student*stud){stud->score++;}

第55页/共253页例子1：结构变量作为函数的参数intmain(){studenttheStud={102,"LiXiaoming",'M',92};cout<<"Initialinformation:";displayStudentInfo(theStud);funCallByValue(theStud);cout<<"\nAftercallbyvalue:";displayStudentInfo(theStud);funCallByReference(theStud);cout<<"\nAftercallbyreference:";displayStudentInfo(theStud);funCallByPointer(&theStud);cout<<"\nAftercallbypointer:";displayStudentInfo(theStud);return0;}

第56页/共253页程序执行结果：Initialinformation:num=102name=LiXiaomingsex=Mscore=92

Aftercallbyvalue:num=102name=LiXiaomingsex=Mscore=92

Aftercallbyreference:num=102name=LiXiaomingsex=Mscore=93

Aftercallbypointer:num=102name=LiXiaomingsex=Mscore=94第57页/共253页例子2：函数返回结构变量#include<iostream.h>structstudent{intnum;charname[20];charsex;floatscore;};studentgetStudent();voiddisplayStudentInfo(conststudent&stud);voiddisplayStudentInfo(conststudent&stud){cout<<endl;cout<<"num="<<stud.num<<"\t";cout<<"name="<<<<"\t";cout<<"sex="<<stud.sex<<"\t";cout<<"score="<<stud.score<<endl;}第58页/共253页例子2：函数返回结构变量studentgetStudent(){studentstud;cout<<"Pleaseenterthenumber:";cin>>stud.num;cout<<"Pleaseenterthename:";cin>>;cout<<"Pleaseenterthesex:";cin>>stud.sex;cout<<"Pleaseenterthescore:";cin>>stud.score;returnstud;}

第59页/共253页例子2：函数返回结构变量intmain(){studenttheStud={102,"LiXiaoming",'M',92};

cout<<"Initialstudentinformation:";displayStudentInfo(theStud);

theStud=getStudent();cout<<"\nAftercallgetStudent:";displayStudentInfo(theStud);

return0;}

第60页/共253页程序执行结果：Initialstudentinformation:num=102name=LiXiaomingsex=Mscore=92Pleaseenterthenumber:105Pleaseenterthename:JohnPleaseenterthesex:MPleaseenterthescore:95

AftercallgetStudent:num=105name=Johnsex=Mscore=95第61页/共253页8.2.2结构与数组结构数组——结构类型的数组元素structstudent{ intnum; charname[20]; charsex; floatscore;}class[5];第62页/共253页例子3：将学生记录按学号大小排序#include<iostream.h>#defineSTUDENT_Num 5structstudent{intnum;charname[20];charsex;floatscore;};voiddisplayStudentsInfo(conststudentstuds[],intlen){for(inti=0;i<len;i++){

cout<<"num="<<studs[i].num<<"\t";cout<<"name="<<studs[i].name<<"\t";cout<<"sex="<<studs[i].sex<<"\t";cout<<"score="<<studs[i].score<<endl;}}第63页/共253页例子3：将学生记录按学号大小排序voidsortArray(studentstuds[],intlen){for(intpass=0;pass<len-1;pass++)

for(inti=pass+1;i<=len-1;i++)if(studs[pass].num>studs[i].num) {studenthold;hold=studs[pass];studs[pass]=studs[i];studs[i]=hold;}}第64页/共253页例子3：将学生记录按学号大小排序intmain(){

studenttheClass[STUDENT_Num]={ {110,"ZhangPing",'M',45}, {102,"LiXiaoming",'M',92}, {153,"WangMing",'M',52.5}, {134,"ChengLing",'F',87}, {105,"WangXiaofang",'F',95}};cout<<"Initialstudentinformation:\n";displayStudentsInfo(theClass,STUDENT_Num);cout<<"\nAftersorting:\n";sortArray(theClass,STUDENT_Num);displayStudentsInfo(theClass,STUDENT_Num);return0;}第65页/共253页程序执行结果：Initialstudentinformation:num=110name=ZhangPingsex=Mscore=45num=102name=LiXiaomingsex=Mscore=92num=153name=WangMingsex=Mscore=52.5num=134name=ChengLingsex=Fscore=87num=105name=WangXiaofangsex=Fscore=95

Aftersorting:num=102name=LiXiaomingsex=Mscore=92num=105name=WangXiaofangsex=Fscore=95num=110name=ZhangPingsex=Mscore=45num=134name=ChengLingsex=Fscore=87num=153name=WangMingsex=Mscore=52.5第66页/共253页8.2.3结构与指针声明结构指针变量student*pStud,stud;pStud=&stud;使用结构指针变量(*pStud).numpStud->num第67页/共253页例子4：结构指针变量的声明和使用

#include<iostream.h>structstudent{intnum;charname[20];charsex;floatscore;};intmain(){ studentstud={102,"LiXiaoming",'M',92}; student*pStud=&stud;

cout<<"Accessstructurethroughstructurevariable:\n"; cout<<"num="<<stud.num<<"\t"; cout<<"name="<<<<"\t"; cout<<"sex="<<stud.sex<<"\t"; cout<<"score="<<stud.score<<endl;第68页/共253页例子4：结构指针变量的声明和使用

//通过指针访问结构，使用圆点运算符访问成员

cout<<"Accessstructurethroughpointerand(.):\n"; cout<<"num="<<(*pStud).num<<"\t"; cout<<"name="<<(*pStud).name<<"\t"; cout<<"sex="<<(*pStud).sex<<"\t"; cout<<"score="<<(*pStud).score<<endl;

//通过指针访问结构，使用箭头运算符访问成员

cout<<"Accessstructurethroughpointerand(->):\n"; cout<<"num="<<pStud->num<<"\t"; cout<<"name="<<pStud->name<<"\t"; cout<<"sex="<<pStud->sex<<"\t"; cout<<"score="<<pStud->score<<endl;

return0;}第69页/共253页程序执行结果：Accessstructurethroughstructurevariable:num=102name=LiXiaomingsex=Mscore=92Accessstructurethroughpointerand(.):num=102name=LiXiaomingsex=Mscore=92Accessstructurethroughpointerand(->):num=102name=LiXiaomingsex=Mscore=92第70页/共253页8.2.4—8.3位段联合设计程序时C++为了节省空间提供的解决方法空间问题不是程序设计的主要问题，感兴趣的同学可以自己看看第71页/共253页8.4枚举枚举用标识符表示的整数集合enumweekday{Sun,Mon,Tue,Wed,Thu,Fri,Sat};

枚举常量：与一般符号常量类似，自动定值起始值为0开始，递增值为1可以用=为枚举常量定值枚举定义中的标识符必须唯一枚举变量声明：与一般变量相同枚举变量只能被赋予相应的枚举常量第72页/共253页8.4.1定义枚举型变量枚举举例enumweekday{Sun=1,Mon,Tue,Wed,Thu,Fri,Sat};enumweekday{Sun=1,Mon,Tue=5,Wed,Thu,Fri=10,Sat};枚举变量的使用weekdayday;

day=mon;day=(weekday)2day=2;//error第73页/共253页学习目的检测能够建立和使用结构、联合、枚举掌握通过传值、传引用、传指针等方式为函数传递结构参数的方法第74页/共253页作业0第75页/共253页第9章链表第76页/共253页讲授内容自引用结构、链表的概念内存的动态分配和释放单向链表的定义与操作双向链表的定义与操作第77页/共253页9.1链表的基本概念结构数组--必须将数组的大小设定成足够大的值太浪费能否需要多少分配多少？链表=动态内存分配+结构+指针所有结构形成一条链可以在任何地方插入或删除元素第78页/共253页9.2单向链表自引用结构结构中包含指向同类型结构的指针通过指针连接成链表，终点是NULL指针(0)第79页/共253页9.2.1单向链表定义例子：structnode{intdata;node*next;};

next：指向下一个node类型的结构，连接node的纽带head2852296NULL第80页/共253页9.2.1单向链表定义存放学生信息的链表节点structstudent{intnum;charname[20];charsex;floatscore;student*next;};动态申请内存的方法student*p=(student*)malloc(sizeof(student));或student*p=newstudent;第81页/共253页9.2.2单向链表的操作建立单向链表声明一个链首指针变量head，并赋初值NULL(包含0个节点的链表)动态分配一个新节点，将该节点链入链尾重复上一步第82页/共253页例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾#include<iostream.h>structnode{ intdata; node*next;};node*createList(intn);intmain(){intn;node*listHead=NULL;cout<<"Pleaseenterthenumberofnodes:";cin>>n;if(n>0) listHead=createList(n);

return0;}第83页/共253页例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾node*createList(intn){node*temp,*tail=NULL,*head=NULL;intnum;

cin>>num;head=newnode;//为新节点动态分配内存

if(head==NULL){

cout<<"Nomemoryavailable!";returnNULL; } else{head->data=num;head->next=NULL;tail=head;}第84页/共253页例子1：建立链表，读入n个整数，每个整数作为一个新结点插入到链尾

for(inti=0;i<n-1;i++){cin>>num;temp=newnode;//为新节点动态分配内存

if(temp==NULL){

cout<<"Nomemoryavailable!";returnhead;}else {temp->data=num;temp->next=NULL;tail->next=temp;tail=temp;}} returnhead;}

第85页/共253页建立链表过程tailtempheadNULL初始状态NULLNULL读入1后tailtemphead1NULL第86页/共253页建立链表过程读入2后tailtemphead12NULL读入3后tailtemphead13NULL2第87页/共253页9.2.2单向链表的操作遍历链表依次访问链表中的每个节点的信息head->data=15;

head->next->data=15;一般遍历方法node*curNode=head;while(curNode)curNode=curNode->next;

第88页/共253页例子2：编写一个函数，输出例1链表中各节点的data成员的值voidoutputList(node*head){cout<<"List:";node*curNode=head;while(curNode){cout<<curNode->data;if(curNode->next) cout<<"->";curNode=curNode->next;}cout<<endl;return;}第89页/共253页例子3：编写一个函数，在例1的链表中查找包含指定整数的节点node*findData(intn,node*head){node*curNode=head;while(curNode){if(curNode->data==n){cout<<"Find"<<n<<"inthelist."<<endl;returncurNode;}curNode=curNode->next;}cout<<"Can'tfind"<<n<<"inthelist."<<endl;returnNULL;}

第90页/共253页9.2.2单向链表的操作在链表中节点a之后插入节点c(1)指针cptr指向节点c,aptr指向节点a；(2)把a后继节点的地址赋给节点c的后继指针

cptr->next＝aptr->next；(3)把c的地址赋给节点a的后继指针aptr->next=cptr;第91页/共253页例子4：编写一个函数，将输入的整数从小到大插入链表node*insertData(intn,node*head){node*curNode=head;//指向插入点的后节点

node*preNode=NULL;//指向插入点的前节点

node*newNode=NULL;//指向新建节点while((curNode!=NULL)&&(curNode->data<n)){preNode=curNode;//后节点变为前节点

curNode=curNode->next;}newNode=newnode;

if(newNode==NULL){

cout<<"Nomemoryavailable!"; returnhead; }第92页/共253页例子4：编写一个函数，将输入的整数从小到大插入链表newNode->data=n;if(preNode==NULL)//插入到链表头{

newNode->next=curNode;

returnnewNode;}

else{preNode->next=newNode;newNode->next=curNode;

returnhead;}}第93页/共253页9.2.2单向链表的操作从链表中删除一个节点c(1)在链表中查找要删除的节点c，用指针cptr指向节点c;(2)如果c有前驱节点(设为d,用指针dptr指向d)，则将d的后继指针指向c的后继节点：dptr->next=cptr->next(3)释放c占用的空间第94页/共253页例子5：编写一个函数，删除链表中包含指定整数的节点node*deleteData(intn,node*head){node*curNode=head;//指向当前节点

node*preNode=NULL;//指向当前节点的前驱节点

while(curNode&&curNode->data!=n){preNode=curNode;//当前节点变为前驱节点curNode=curNode->next;}

if(curNode==NULL){cout<<"Can'tfind"<<n<<"inthelist"<<endl;returnhead;}if(preNode==NULL)//删除链首节点

head=head->next;else

preNode->next=curNode->next;deletecurNode;returnhead; //返回链首指针}

第95页/共253页9.3双向链表单向链表：有利于从链首向链尾遍历有些时候双向遍历是需要的——双向链表第96页/共253页9.3.1双向链表的定义定义双向链表的节点：structnode{intdata; node*next;//指向后续节点 node*pre;//指向前面的节点};第97页/共253页9.3.1双向链表的定义双向链表的例子：双向链表一般也由头指针唯一确定双向链表首尾相接可以构成双向循环链表head28NULL52296NULL第98页/共253页9.3.2双向链表的操作建立双向链表新节点链入链尾原链尾节点的后继指针指向新节点新节点的前驱指针指向原链尾节点新链尾节点的后继指针置为空指针将新节点链入链头原链头节点的前驱指针指向新节点新节点的后继指针指向原链头节点新链头节点的前驱指针置为空指针第99页/共253页例子6：编写一个函数，按数据输入的顺序建立双向链表node*createBidirList(intn){node*temp,*tail=NULL,*head=NULL; intnum;

cin>>num;head=newnode;//为新节点动态分配内存

if(head==NULL) {

cout<<"Nomemoryavailable!";returnNULL;}else{head->data=num;head->next=NULL;head->pre=NULL;tail=head;}第100页/共253页例子6：编写一个函数，按数据输入的顺序建立双向链表for(inti=0;i<n-1;i++){cin>>num;temp=newnode;//为新节点动态分配内存

if(temp==NULL){

cout<<"Nomemoryavailable!";returnhead;}else{temp->data=num;temp->next=NULL;temp->pre=tail;tail->next=temp;tail=temp;}}returnhead;}第101页/共253页9.3.2双向链表的操作双向链表的遍历有链首节点，则可以沿着后继指针从头至尾遍历有链尾节点，则可以沿着前驱指针从尾向头遍历第102页/共253页例子7：编写一个函数，输出双向链表中各节点的data成员的值voidoutputBidirList(node*head){cout<<"List:";node*curNode=head;while(curNode){if(curNode->pre)cout<<"<-";cout<<curNode->data;if(curNode->next)cout<<"->";curNode=curNode->next;}cout<<endl;return;}第103页/共253页9.3.2双向链表的操作在双向链表中插入和删除一个节点优点：获取插入节点或被删除节点的前驱和后继节点比较方便注意点：需要维护的指针较多第104页/共253页例子8：编写函数，将整数n插入到一个已排序的双向链表中(从小到大)node*insertData(intn,node*head){ node*curNode=head; //指向插入点的后节点

node*preNode=NULL; //指向插入点的前节点

node*newNode=NULL; //指向新建节点 //寻找插入位置

while((curNode!=NULL)&&(curNode->data<n)){ preNode=curNode; curNode=curNode->next; } newNode=newnode;//为新节点动态分配内存

if(newNode==NULL){//内存分配不成功

cout<<"Notmemoryavailable!"; returnhead; }第105页/共253页例子8：编写函数，将整数n插入到一个已排序的双向链表中(从小到大) newNode->data=n; if(preNode==NULL) {//链头

newNode->next=curNode; newNode->pre=NULL; if(curNode!=NULL) curNode->pre=newNode; returnnewNode; } if(curNode==NULL) {//链尾

newNode->pre=preNode; preNode->next=newNode; newNode->next=NULL; returnhead; }第106页/共253页例子8：编写函数，将整数n插入到一个已排序的双向链表中(从小到大) else {//链中

preNode->next=newNode; newNode->next=curNode; newNode->pre=preNode; curNode->pre=newNode; returnhead; }}第107页/共253页例子9：编写函数，在双向链表中查找并删除指定node*deleteData(intn,node*head){node*curNode=head; //指向当前节点

while(curNode&&curNode->data!=n)

curNode=curNode->next;if(curNode==NULL){cout<<"Can'tfind"<<n<<endl;returnhead;}第108页/共253页例子9：编写函数，在双向链表中查找并删除指定

if(curNode->pre==NULL){

head=head->next;head->pre=NULL;}else{

curNode->pre->next=curNode->next;if(curNode->next!=NULL)

curNode->next->pre=curNode->pre;}deletecurNode;returnhead; //返回链首指针}第109页/共253页学习目的检测理解自引用结构和链表的含义掌握通过动态分配和释放内存来建立和维护链表第110页/共253页作业+上机第111页/共253页第10章面向对象程序设计基本概念第112页/共253页讲授内容面向对象程序设计方法的产生和发展面向对象程序设计语言面向对象程序设计的特点类和对象的基本概念消息第113页/共253页10.1面向对象语言和方法(1/6)六十年代末期——Simula67（面向对象语言的鼻祖）包含了类和继承的概念类——描述特性相同或相近的一组对象的结构和行为继承——将多个类组织成层次结构，实现数据和操作的共享第114页/共253页10.1面向对象语言和方法(2/6)七十年代末八十年代初——Smalltalk（第一个真正的集成开发环境）包含类和继承，更严格的信息隐藏带有一个巨大的、标准类库第一个使用MVC(Model-View-Controller)模式开发交互式应用软件第115页/共253页10.1面向对象语言和方法(3/6)Smalltalk使面向对象方法为人们注目面向对象语言被分为两大阵营纯粹的面向对象语言：Smalltalk、Eiffel、Java混合型面向对象语言：C++和CLOS基于对象的语言：Ada支持数据抽象类型（包）、函数和运算符重载、多态性，但不支持继承第116页/共253页10.1面向对象语言和方法(4/6)结构化程序设计软件的结构化分析、设计方法工程化的概念的方法但无法很好地支持越来越复杂、庞大的系统需求面向对象方法直接将问题的求解映射到问题本身上有目的地将系统分解为模块将问题分解为一系列的实体（对象）方便设计，可维护性、可扩充性好第117页/共253页10.1面向对象语言和方法(5/6)简单的例子——图书馆管理系统包含reader（读者）对象、librarian（图书管理员）对象、bookshelf（书架）对象等所有的操作由各对象协作完成借书reader对象向librarian对象提出借书请求librarian对象向bookshelf对象提出查书和取书请求然后逐步响应，逐步返回，共同完成借书操作万物皆对象第118页/共253页10.1面向对象语言和方法(6/6)面向对象方法的一些特性程序设计的重点在数据而不是函数程序由对象组成对象之间通过相互协作来完成功能大多数对象的定义以数据为中心函数与相关的数据紧密结合数据可以被隐藏很容易扩充新的数据和函数第119页/共253页10.2类、对象和消息(1/10)面向对象程序设计的一般步骤分析实际问题，分辨并抽取其中的类和对象设计相应的类，并根据这些类创建各种对象协调这些对象完成程序功能（消息）第120页/共253页10.2类、对象和消息(2/10)万物皆对象每个学生、每个班级、每个学校、每个国家、每棵树、每本书、每部汽车——具体的实体“张三”、“李四”都是对象，但“人”不是“人”不是具体的实体，是类，是抽象概念类是某些对象共同特征的表示类是创建对象的模板，对象是类的实例第121页/共253页10.2类、对象和消息(3/10)如何区分类和对象——以“人”和“张三”为例“人”描述了所有人（包括“张三”）都具有的属性和行为，如有姓名、身高、体重，有鼻子、眼睛、四肢，能交流、能思维等等类（“人”）描述的概念是抽象的“人”的姓名是什么？“人”的身高是什么？对象（“张三”）是具体的“张三”的姓名是“张三”“张三”的身高是185CM第122页/共253页10.2类、对象和消息(4/10)还有哪些类和对象的例子教室——301-105教室国家——中国学校——国防科技大学……第123页/共253页例子：读者类ReaderclassReader{public: Reader(); //构造函数

intregistration(char*name); //注册

intborrowBook(intbookNo); //借书

intreturnBook(intbookNo); //还书private: char*name; //姓名

char*certifNo; //借书证号};第124页/共253页10.2类、对象和消息(5/10)格式说明类的定义以关键字class开头class后面是类名（Reader）类名后面花括号扩起来的部分是类的体类的定义以分号结尾第125页/共253页10.2类、对象和消息(6/10)内容说明类的定义可以包含数据和函数关键字public后面定义