C语言程序设计第9章指针进阶.ppt

《C语言程序设计第9章指针进阶.ppt》由会员分享，可在线阅读，更多相关《C语言程序设计第9章指针进阶.ppt（61页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第9 9章章 指针进阶指针进阶 学习目标1掌握指针数组的定义及其应用，了解二级指针的基本概念;2.理解二维数组的指针和指向二维数组的指针变量;3.了解指向函数的指针，理解指针型函数;4.初步了解内存的动态分配和动态回收;5.初步掌握单向链表的建立与访问、在单向链表中插入、删除结点等算法。9.1 9.1 指针数组指针数组9.1.1 9.1.1 指针数组的概念指针数组的概念 指针数组：一个数组的每个元素均为指针类型 形式：数据类型*数组名数组长度;int*pa3;char*pname5=JiangSu,ShanDong,ZheJiang,GuangXi，AnHui;指针数组pname字符串pna

2、me0pname1pname2pname3pname4JiangSuShanDongZheJiangGuangXiAnHuipname9.1.2 9.1.2 指向指针的指针变量指向指针的指针变量 指向指针的指针变量：一个指针变量中存放的是另一个指针变量的地址形式：数据类型*指针变量名;int*p;intx=5,*q=&x;int*p;p=&q;变量、一级指针、二级地址之间的关系示意变量、一级指针、二级地址之间的关系示意指针变量q变量x指针变量p&x5&q#includevoidmain()inta=10,*b,*c;b=&a;c=&b;printf(%d,%d,%dn,a,*b,*c);*b=

3、20;/*通过b间接访问a*/printf(%d,%d,%dn,a,*b,*c);*c=30;/*通过c间接访问a*/printf(%d,%d,%dn,a,*b,*c);运行结果：10,10,1020,20,2030,30,30&a变量b变量a&b变量c*c*c或*b10(初值)二级指针示意图二级指针示意图9.1.3 指针数组应用举例指针数组应用举例编程将若干字符串按字母顺序由小到大排序后输出。#include#include#defineN5/*字符串个数*/voidsort(char*name,intn);voidprint(char*name,intn);voidmain()char*p

4、nameN=JiangSu,ShanDong,ZheJiang,GuangXi,AnHui;printf(beforesorted:n);print(pname,N);/*排序前输出各字符串*/sort(pname,N);/*排序*/printf(aftersorted:n);print(pname,N);/*排序后输出各字符串*/voidsort(char*name,intn)char*pt;inti,j,k;for(i=0;in-1;i+)/*选择排序算法*/k=i;for(j=i+1;j0)k=j;if(k!=i)pt=namei;namei=namek;namek=pt;voidpri

5、nt(char*name,intn)inti;for(i=0;in;i+)printf(%sn,namei);/*或printf(%sn,*(name+i);*/(b)排序后排序后指针数组pname字符串pname0pname1pname2pname3pname4JiangSuShanDongZheJiangGuangXiAnHui(a)排序前排序前指针数组pname字符串pname0pname1pname2pname3pname4JiangSuShanDongZheJiangGuangXiAnHui9.2 9.2 二维数组的指针和二维数组的指针和 指向二维数组的指针变量指向二维数组的指针变量

6、9.2.1 9.2.1 二维数组的行地址和列地址二维数组的行地址和列地址一、二维数组的行地址一、二维数组的行地址ints34;s数组的逻辑结构图数组的逻辑结构图s00s10s20s01s11s21s02s12s22s03s13s23s0s1s2ss数组的行地址数组的行地址s0s1s2ss+1s+2*s等于*(s+0)为元素s0*(s+1)即为元素s1*(s+2)即为元素s2由于行地址代表某一行（这一行可以看成是一个一维数组）的地址，而不是某一个元素的地址，故行地址是一个二级指针。例如，s是第0行，即s0（s0可看作是s00、s01、s02、s03四个元素组成的一维数组的数组名）的地址，s+1表

7、示下一行的地址，即s1的地址。二、二维数组的列地址二、二维数组的列地址 一维数组名代表数组首元素的地址 s0代表一维数组s0中第0列元素的地址（&s00）s1代表一维数组s1中第0列元素的地址（&s10）s2代表一维数组s2中第0列元素的地址（&s20）s0+0、s0+1、s0+2、s0+3分别是s00、s01、s02、s03的地址，这些地址被称为二维数组s的列地址。列地址是数组元素的地址，可以利用列地址指向某一个实际的二维数组元素。s10s11s12s13二维数组二维数组s的行地址和列地址的行地址和列地址s1+0s1+1s1+2s1+3s2+0s2+1s2+2s2+3s0s1s2ss+1s+

8、2行地址列地址一维数组s0一维数组s1一维数组s2s20s22s23s21s0+0s0+1s0+2s0+3s00s01s02s039.2.2 9.2.2 通过地址引用二维数组的元素通过地址引用二维数组的元素ints34,i,j;s数组中各种表示形式和含义表示形式表示形式含含 义义s二维数组名，指向一维数组s0，即第0行首地址s0,*(s+0),*s第0行的首地址s+1第1行首地址s1+0,*(s+1),*(s+1)+0,&s10第1行第0列元素的地址*(s1+2),*(*(s+1)+2),s12,(*(s+1)2第1行第2列元素的值s129.2.3 9.2.3 指向二维数组的指针变量指向二维数

9、组的指针变量一、指向二维数组元素的指针一、指向二维数组元素的指针 列地址是数组元素的地址，使用该地址对一指针变量进行初始化，那么该指针变量就指向二维数组元素。这种指针被称为指向二维数组元素的指针或者被称为列指针#includevoidmain()inta34=0,2,4,6,1,3,5,7,9,10,11,12;int*p;for(p=a0;pa0+12;p+)if(p-a0)%4=0)printf(n);/*保证每行四个元素*/printf(%4d,*p);/*输出当前p所指向元素的值*/运行结果：024613579101112阅读下列程序，考察lessavg函数调用时实参与形参的结合。#i

10、nclude#defineM3#defineN3voidlessavg(float*,int);voidmain()floataMN=65,67,70,80,89,97,69,76,80;lessavg(&a00,M*N);voidlessavg(float*p,intn)floatsum=0,average;float*p1;inti；p1=p;/*p1指向第一个元素a00*/for(;p1p+n;p1+)sum=sum+(*p1);average=sum/n;/*average存储平均值*/printf(average=%5.2f,average);printf(nthearrayelem

11、ents(less%5.2f):n,average);for(i=0;in;i+)if(piaverage)/*或if(*(p+i)average)*/printf(%5.2fn,pi);/*或printf(%5.2fn,*(p+i);*/二、指向二维数组行的指针二、指向二维数组行的指针行地址代表某一行（一行可以看成是一个一维数组）的地址，使用该地址对一指针变量进行初始化，那么该指针变量便指向二维数组的一行。这种指针变量被称为指向二维数组行的指针变量，简称行指针。n形式：数据类型 （*行指针名）长度;“长度”表示行指针所指向的一维数组的长度（即二维数组的列数）“数据类型”表示行指针所指一维数组

12、的元素类型“*”表示其后定义的标识符是指针。例如，变量声明语句“int(*p)4=s;”表示定义的指针变量p用以指向包含4个整型元素的一维数组，也可理解为p用以指向列数为4的二维数组的行。#includevoidmain()ints34=0,2,4,6,1,3,5,7,9,10,11,12;int(*p)4,i,j;scanf(%d%d,&i,&j);p=s;printf(%dn,*(*(p+i)+j);测试数据及运行结果：输入：13输出：79.2.4 二维数组名作为函数参数二维数组名作为函数参数若主函数中有以下定义及函数调用语句：#include#defineM3#defineN4voidm

13、ain()intaMN;fun(a);则fun函数（设为void类型）定义时的首部可以是以下三种形式之一：(1)voidfun(int(*p)N)(2)voidfun(intpN)(3)voidfun(intpMN)n注意：上述三种方式中，无论是哪一种方式，编译系统都将把p处理成一个行指针。和一维数组相同，数组名传递给形参的是一个地址值，因此，对应的形参也必定是一个类型相同的指针变量，在函数中引用的将是主函数中的数组元素，系统只为形参开辟一个存放地址的存储单元，而不可能在调用函数时为形参开辟一系列存放数组元素的存储单元。#include#defineM3#defineN4intmax_valu

14、e(int(*p)4,intrnum);voidmain()intsMN=1,3,12,7,2,14,6,28,15,47,34,12;printf(maxvalueis%dn,max_value(s,M);intmax_value(int(*p)N,intrnum)/*或intmax_value(intpN,intrnum)*/inti,j,max;max=p00;/*或max=*p;*/for(i=0;irnum;i+)for(j=0;jmax)max=pij;/*或max=*(*(p+i)+j);*/returnmax;运行结果：maxvalueis479.3 9.3 函数的指针与函数的

15、指针与 指向函数的指针变量指向函数的指针变量*9.3.1 指向函数的指针变量的定义指向函数的指针变量的定义形式为：数据类型（*指针变量名）（）;“数据类型”表示指针变量所指向函数的返回值的类型。最后的空括号表示指针变量所指的是一个函数。例如，int(*pf)();pf被定义为一个可以指向函数的指针变量，该函数的返回值（函数值）是整型。它在没有赋值前不指向一个具体的函数，不能随便使用。9.3.2 9.3.2 用指向函数的指针变量调用函数用指向函数的指针变量调用函数形式：（*指针变量名）（实参表列）;#includeintmax(int,int);intmin(int,int);voidmain(

16、)int(*p)();intx,y,l,j;printf(Pleaseinputtwonumbers:n);scanf(%d%d,&x,&y);p=max;/*函数名max表示函数的入口地址（首地址）*/l=(*p)(x,y);/*通过函数指针变量调用max函数，与“z=max(x,y)”等价*/printf(max=%dn,l);p=min;/*函数名min表示min函数的入口地址（首地址）*/j=(*p)(x,y);/*通过函数指针变量调用min函数，与“z=min(x,y)”等价*/printf(min=%dn,j);intmax(inta,intb)if(ab)returna;else

17、returnb;intmin(inta,intb)if(ab)returna;elsereturnb;测试数据及运行结果：输入：610输出：max=10min=69.4 9.4 返回值为指针的函数返回值为指针的函数形式：数据类型*函数名(形参表)函数名前的“*”号表明这是一个指针型函数，即返回值是一个指针。数据类型表示了返回的指针所指向数据的类型。例如：int*ap(intx,inty).表示ap是一个返回指针值的指针型函数，它返回的指针指向一个整型变量。编写一个函数连接两个字符串，并返回连接后字符串的首地址#includechar*catstr(char*str1,char*str2);vo

18、idmain()chars1100=beijing;chars2100=2008;char*result=NULL;result=catstr(s1,s2);printf(ntheresultis:%sn,result);char*catstr(char*str1,char*str2)char*temp=str1;while(*str1!=0)str1+;while(*str2!=0)*str1=*str2;str1+;str2+;*str1=0;returntemp;运行结果：theresultis:beijing20089.5 9.5 链表链表9.5.1 链表的概念链表的概念链表是一种常见

19、的重要的数据结构，它是动态地进行存储分配的一种结构。一、自引用结构体当一个结构体中的一个或多个成员的基类型就是本结构体类型时，称为可以“引用自身的结构体”，简称自引用结构体。例如：structnodecharc;structnode*next;a;next是一个可以指向struct node类型变量的指针成员，因此，“a.next=&a;”就是合法的赋值语句，由此构成的存储结构如图。自引用结构体示意自引用结构体示意B#includestructstudentintid;floatscore;structstudent*next;voidmain()structstudenta,b,c,*hea

20、d,*p;a.id=1000;a.score=90;b.id=1001;b.score=86;c.id=1002;c.score=78;/*对结点的id和score成员赋值*/head=&a;/*将结点a的起始地址赋给头指针head*/a.next=&b;/*将结点b的起始地址赋给a结点的next成员*/b.next=&c;/*将结点c的起始地址赋给b结点的next成员*/c.next=NULL;/*c结点的next成员不存放其他结点地址*/p=head;/*使p指针指向a结点*/while(p!=NULL)/*p的值为NULL,表示链表已经结束*/printf(%d%5.1fn,p-id,p

21、-score);/*输出p指向的结点的数据*/p=p-next;/*使p指向下一结点*/运行结果：100090.0100186.0100278.0三个学生成绩链表三个学生成绩链表head100090next100186next100278NULLabc9.5.2 9.5.2 动态内存分配动态内存分配 动态内存分配通过内存管理函数来实现，常用的内存管理函数有以下三个：1、分配内存空间函数malloc函数原形：void*malloc(unsignedintsize)；功能：在内存的动态存储区中分配一块长度为size字节的连续内存空间。若分配成功，则函数的返回值为该存储区的首地址；否则返回NULL(

22、空指针)。例如：char*pc;pc=(char*)malloc(sizeof(char);2、分配内存空间函数calloc函数原形：void*calloc(unsignedintn,unsignedintsize);功能：在内存动态存储区中分配n块长度为size字节的连续的内存空间。若分配成功，则函数的返回值为该存储区的首地址；否则返回NULL(空指针)。int*pi;pi=(int*)calloc(2,sizeof(int);3、释放内存空间函数free函数原形：voidfree(void*p);功能：释放p所指向的一块内存空间，该函数无返回char*pc;pc=(char*)malloc

23、(sizeof(char);free(pc);structstudentintid;floatscore;structstudent*next;voidmain()structstudent*ps;ps=(structstudent*)malloc(sizeof(structstudent);ps-id=10001;ps-score=97;printf(studentid=%dnscore=%fn,ps-id,ps-score);free(ps);运行结果：studentid=10001score=97.0000009.5.3 9.5.3 单向链表的常用操作单向链表的常用操作 常用的链表操作如

24、初始链表建立、链表的输出、链表结点的插入和删除等操作。设有结构类型定义如下：structstudentintid;floatscore;structstudent*next;以学生成绩管理程序为例，来阐述链表的常用操作。一、链表的建立一、链表的建立 链表的建立是指在程序的执行过程中从无到有的建立起一个链表，即一个一个地开辟结点空间，输入结点的数据，并建立起结点之间的链接关系。注意：1.指出链表的首结点2.指明链尾 置链表最后一个结点指针域的值为NULL（宏名，代表0）。3.申请内存空间，建立新结点并添加到链表中(1)给新结点分配空间，并保留该空间的首地址。例如：new=(structstude

25、nt*)malloc(sizeof(structstudent);new指针变量指向structstudent类型。new指针变量存储新结点的地址，或称为指向新结点。(2)给新结点数据成员赋值。例如：New-id=1000;new-score=98;new-next=NULL;(3)将新结点加入到链表中，考虑以下两种情况：n第一种：如果原链表为空表，则将新建结点作为首结点。这时指针head应指向该结点。执行语句head=new;如图（a）执行语句tail=new;后，如图（b）(a)(b)链表的建立（原链表为空表）链表的建立（原链表为空表）100098NULLheadnew100098NULL

26、headnewtailn第二种：如果原链表为非空，则将新建结点添加到表尾，尾指针tail指向表尾的最后一个结点执行语句tail-next=new;后，如图(a)所示执行语句tail=new;后，如图(b)所示。（a）200097tail200198NULLnew（b）200097200198NULLnewtail建立链表的函数如下：#include#includestructstudentintid;floatscore;structstudent*next;structstudent*create()structstudent*head,*tail,*new;head=tail=new=NU

27、LL;/*NULL是宏名，代表0*/new=(structstudent*)malloc(sizeof(structstudent);scanf(%d,%f,&new-id,&new-score);new-next=NULL;while(new-id!=0)/*当学号值为零时，表示链表建立完毕*/if(head=NULL)/*判断链表是空还是非空*/head=new;/*空表情况*/elsetail-next=new;/*非空表情况*/tail=new;/*新添加结点成为链表的尾结点*/new=(structstudent*)malloc(sizeof(structstudent);scanf

28、(%ld,%f,&new-id,&new-score);new-next=NULL;tail-next=NULL;/*尾结点的指针值为空，本语句可不写*/return(head);/*返回链表的首地址*/二、链表的输出二、链表的输出链表的输出函数如下：voidprint(structstudent*head)structstudent*current;printf(Now,recoedsare:n);current=head;while(current!=NULL)printf(%d%fn,current-id,current-score);current=current-next;三、链表结

29、点的删除三、链表结点的删除 1.1.被删除的是首结点被删除的是首结点 如果被删除结点是链表中的首结点，那么只要将头指针head指向首结点的下一个结点即可删除首结点head=current-next;(a)删除前删除前100098headcurrent100189100098head100189current(b)删除后删除后2 2被删除结点不是首结点被删除结点不是首结点前一结点的指针指向当前结点的下一结点即可删除当前结点 prior-next=current-next;（a a）删除前）删除前200098current200189200279prior 删除非首结点前后链表示意图删除非首结点前

30、后链表示意图200098current200189200279prior(b)(b)删除后删除后实现在链表中删除结点操作的函数如下：structstudent*del(structstudent*head,longid)structstudent*prior,*current;if(head=NULL)printf(nListnull!n);elsecurrent=head;while(id!=current-id¤t-next!=NULL)prior=current;/*prior指向当前结点*/current=current-next;/*current指向下一个结点（新的当前

31、结点）*/if(id=current-id)if(current=head)/*判断结点是首结点还是其他结点*/head=current-next;/*头指针head指向首结点的下一个结点*/elseprior-next=current-next;/*前一结点的指针指向当前结点的下一结点*/printf(n%ddeletedn,id);elseprintf(%dnotbeenfound!n,id);return(head);四、链表结点的插入四、链表结点的插入 将一个待插入结点插入到已有链表的适当位置。在将链表结点插入链表时，首先要找到插入位置，方法是从第一个结点开始依次往后查找（遍历各结点）

32、，直到找到插入位置为止；然后把新结点插到相应位置。考虑以下两种情况：1.寻找待插入的位置2.插入结点插入结点时，应考虑以下三种情况：(1)在首结点前插入新结点new-next=current;head=new;(a)插入前插入前current100189head100098new(待插入结点)(b)插入后插入后100098head100189currentnew新结点作为首结点插入时单向链表变化示意图新结点作为首结点插入时单向链表变化示意图(2)插入位置在链表中间new-next=current;prior-next=new;待插结点new(a)(a)插入前插入前200098current20

33、0279prior200189在链表中间插入新结点时单向链表变化示意在链表中间插入新结点时单向链表变化示意200098200189200279currentpriornew(b)(b)插入后插入后(3)新结点作为尾结点插入current-next=new;new-next=NULL;（a）插入前插入前300097current300179NULLprior300289new（b）插入后插入后300097300179300289NULLnewpriorcurrent实现在链表中插入新结点操作的函数如下：structstudent*insert(structstudent*head,structs

34、tudent*stud)/*stud指向待插入的新结点*/structstudent*new,*current,*prior;current=head;new=stud;if(head=NULL)/*原来是空链表*/head=new;new-next=NULL;else/*下面循环的目标是找到新结点待插入的位置*/while(new-idcurrent-id)&(current-next!=NULL)prior=current;/*prior指向当前结点*/current=current-next;/*current指向当前结点的下一个结点*/if(new-idid)/*该分支表示把新结点放到

35、第一个比它大的结点前面*/if(head=current)/*判断是否插入到第一个结点的前面*/head=new;/*插入到第一个结点的前面*/elseprior-next=new;/*插入到中间*/new-next=current;else/*该分支代表没有找到比新结点大的结点，所以插入到最后*/current-next=new;new-next=NULL;return(head);9.6 9.6 典型例题典型例题例：设某单向链表结点的定义如下：typedefstructnodecharch;structnode*next;linklist;编程要求：(1)编写函数linklist*crea

36、te(charx)，其功能为建立一个单向链表，该链表中每个结点的值域保存x数组的一个元素值；(2)编写函数linklist*revlist(linklist*head)，其功能是将head链逆置。例如，原链表如图(a)所示，逆置后的链表如图(b)所示(3)编写main函数，初始化一个字符数组，以该字符数组名作为实在参数调用create函数生成单向链表；调用revlist函数将所生成的链表逆置，最后输出链表中每个结点的值。headABCDNULL（a）原始链表原始链表headDCBANULL（b）逆置链表逆置链表链表逆置前后示意图链表逆置前后示意图#include#includetypedefs

37、tructnodecharch;structnode*next;linklist;linklist*create(charx)inti;linklist*pt,*pr,*p=NULL;for(i=0;xi!=0;i+)pt=(linklist*)malloc(sizeof(linklist);pt-ch=xi;pt-next=NULL;if(p=NULL)/*判断链表是否是空链表*/p=pt;pr=pt;/*空链表情况*/elsepr-next=pt;pr=pt;/*链表非空情况*/returnp;/*返回链表的头指针*/linklist*revlist(linklist*head)linkl

38、ist*hp,*p=NULL;hp=head;head=NULL;/*head链表为空链表*/while(hp)/*判断hp链表是否结束*/p=hp;/*p指向当前hp所指向的结点*/hp=hp-next;/*hp指向当前结点的下一结点*/p-next=head;/*p所指向结点的指针成员指向head链表的首结点*/head=p;/*p所指向结点成为链表的首结点*/returnhead;voidprint(linklist*phead)while(phead!=NULL)/*判断链表是否结束*/printf(%c,phead-ch);/*输出当前phead所指向结点的ch成员值*/phead=

39、phead-next;/*phead指向当前结点的下一结点*/printf(n);voidmain()linklist*head;charx=ABCD;head=create(x);/*建立链表，并且head指向链表的第一个结点*/print(head);/*输出链表，实参为链表的头指针*/head=revlist(head);/*倒序链表，且head指向倒序后链表的第一个结点*/print(head);/*输出链表，实参为链表的头指针*/运行结果：ABCDDCBA例:请设计程序，实现两个链表的合并。设链表的结点定义如下：typedefstructnodecharch;structnode*n

40、ext;linklist;链表pa和pb均已按成员ch升序排列，现要求实现两个链表的合并，合并后的链表按成员ch升序排列。合并前后的链表如所示。链表归并示意图链表归并示意图paAGHNULLpbCDNULLpcACHNULLDG#includetypedefstructnodecharch;structnode*next;linklist;linklist*merge(linklist*pa,linklist*pb)linklist*pc=NULL,*ptail=NULL;/*pc为新链表的头指针*/while(pa!=NULL&pb!=NULL)if(pa-chch)if(pc=NULL)pc=pa;elseptail-next=pa;ptail=pa;/*ptail指向新链表的尾结点*/pa=pa-next;/*pa指向当前结点的下一个结点（pa链表）*/elseif(pc=NULL)pc=pb;elseptail-next=pb;ptail=pb;/*ptail指向新链表的尾结点*/pb=pb-next;/*pb指向当前结点的下一个结点（pb链表）*/if(pa!=NULL)ptail-next=pa;/*pa没有结束，pa链表剩余结点链接到新链表的末尾*/elseptail=pb;/*pb没有结束，pb链表剩余结点链接到新链表的末尾*/returnpc;