信息學(xué)奧賽課課通-第8單元 電子課件

第8單元指針信息學(xué)奧賽課課通（C++）2021/5/91第1課指針的概念學(xué)習(xí)目標(biāo)1.理解指針的概念。2.學(xué)會(huì)定義和使用指針。2021/5/92指針指針是C++語(yǔ)言的一個(gè)重要概念，也是C++語(yǔ)言的重要特色。C++語(yǔ)言的高度靈活性及極強(qiáng)的表達(dá)能力，在很大程度上表現(xiàn)在巧妙而靈活的運(yùn)用指針。通過(guò)指針可以有效地表示復(fù)雜的數(shù)據(jù)結(jié)構(gòu)；能夠方便地處理數(shù)組和字符串；能夠動(dòng)態(tài)地分配內(nèi)存，直接對(duì)內(nèi)存地址進(jìn)行操作；利用指針作為函數(shù)參數(shù)，能夠?qū)崿F(xiàn)“一次函數(shù)調(diào)用，有多個(gè)返回值”的目的。因此，必須深入學(xué)習(xí)和理解指針的概念，體會(huì)和掌握指針的各種操作，熟練應(yīng)用指針去實(shí)踐編程。2021/5/931.指針的概念對(duì)于“inta=3;”，系統(tǒng)會(huì)在內(nèi)存的某個(gè)區(qū)域開(kāi)辟連續(xù)4個(gè)字節(jié)的單元存儲(chǔ)。對(duì)a的操作就是對(duì)該內(nèi)存區(qū)域進(jìn)行操作，至于是具體的哪4個(gè)單元，我們并不關(guān)心。內(nèi)存單元的位置（編號(hào)）叫作“地址”，可以通過(guò)取地址操作符“&”獲得一個(gè)變量a的起始地址（首個(gè)存儲(chǔ)單元的地址）：&a。指針也是一個(gè)變量。和普通變量不同的是，指針變量里存儲(chǔ)的數(shù)據(jù)是一個(gè)內(nèi)存地址，就好像一個(gè)指示器，指引著你去該內(nèi)存地址開(kāi)始的一塊內(nèi)存區(qū)域存取數(shù)據(jù)。2021/5/942.指針的定義和使用指針變量的定義格式為：數(shù)據(jù)類(lèi)型*指針變量;可以通過(guò)賦值語(yǔ)句給指針變量賦值，例如“p=&a；”表示把變量a的內(nèi)存地址賦值給p，如圖8.1-1所示。指針變量初始化：int*p=NULL；2021/5/95例1、數(shù)字變化【問(wèn)題描述】輸入兩個(gè)不同的整數(shù)，把較小的那個(gè)數(shù)翻倍并輸出?！据斎敫袷健恳恍袃蓚€(gè)整數(shù)（int范圍以?xún)?nèi)），之間用一個(gè)空格隔開(kāi)?！据敵龈袷健恳恍幸粋€(gè)整數(shù)，較小數(shù)翻倍后的結(jié)果?！据斎霕永?3【輸出樣例】42021/5/96//p8-1-1#include<iostream>usingnamespacestd;intmain(){inta,b;int*p;cin>>a>>b;if(a<b)p=&a;elsep=&b;cout<<*p*2<<endl;//取出p指向的內(nèi)存單元里的整數(shù)，乘以2輸出return0;}2021/5/97【程序說(shuō)明】1）變量a和b一旦定義，系統(tǒng)就會(huì)給它們分配內(nèi)存空間，而且在程序運(yùn)行過(guò)程中，其內(nèi)存地址是固定不變的，這種存儲(chǔ)方式稱(chēng)為“靜態(tài)存儲(chǔ)”。2）指針變量p定義后，其地址空間是不確定的，默認(rèn)是NULL。當(dāng)執(zhí)行到p=&a或者p=&b時(shí)，p才指向a或者b的地址，才能確定p的值。這種儲(chǔ)存方式稱(chēng)為“動(dòng)態(tài)存儲(chǔ)”。3）指針的動(dòng)態(tài)性，還體現(xiàn)在可以根據(jù)需要，通過(guò)函數(shù)new（）隨時(shí)申請(qǐng)。看以下例2：2021/5/98例2、閱讀程序，寫(xiě)出程序的運(yùn)行結(jié)果。//p8-1-2#include<iostream>usingnamespacestd;intmain(){int*p;char*q;p=new(int);q=new(char);*p=65;*q=*p;cout<<*p<<““<<*q<<endl;return0;}2021/5/99【程序說(shuō)明】1）運(yùn)行程序，輸出結(jié)果為“65A”。2）程序中聲明了兩個(gè)指針類(lèi)型：一個(gè)指向整數(shù)類(lèi)型的指針p和一個(gè)指向字符類(lèi)型的指針q，分別通過(guò)new(int)和new(char)為p和q向內(nèi)存申請(qǐng)空間。3）“*p=65；”把65這個(gè)整數(shù)存放到p所指向的內(nèi)存單元。4）“*q=*p；”把p所指向的內(nèi)存單元里的值賦值給q所指向的內(nèi)存單元，由于q指向的是一個(gè)字符類(lèi)型，而p指向的是一個(gè)整數(shù)類(lèi)型，在賦值的時(shí)候執(zhí)行了類(lèi)型的強(qiáng)制轉(zhuǎn)換，最終q所指向的內(nèi)存單元里存儲(chǔ)的是65號(hào)字符即為A。2021/5/9103.指針的理解2021/5/911（1）指針的類(lèi)型從語(yǔ)法角度看，把指針定義語(yǔ)句里的指針名字去掉，剩下的部分就是這個(gè)指針的類(lèi)型，也就是指針本身所具有的類(lèi)型。int*ptr;//指針的類(lèi)型是int*char*ptr;//指針的類(lèi)型是char*int**ptr;//指針的類(lèi)型是int**int(*ptr)[3];//指針的類(lèi)型是int(*)[3]int*(*ptr)[4];//指針的類(lèi)型是int*(*)[4]2021/5/912（2）指針?biāo)赶虻念?lèi)型當(dāng)通過(guò)指針來(lái)訪問(wèn)指針?biāo)赶虻膬?nèi)存區(qū)域時(shí)，指針?biāo)赶虻念?lèi)型決定了編譯器將把那片內(nèi)存區(qū)域里的內(nèi)容當(dāng)作什么來(lái)看待。從語(yǔ)法上看，把指針定義語(yǔ)句中的指針名字和名字左邊的指針聲明符“*”去掉，剩下的就是指針?biāo)赶虻念?lèi)型。int*ptr;//指針?biāo)赶虻念?lèi)型是intchar*ptr;//指針?biāo)赶虻念?lèi)型是charint**ptr;//指針?biāo)赶虻念?lèi)型是int*int(*ptr)[3];//指針?biāo)赶虻念?lèi)型是int()[3]int*(*ptr)[4];//指針?biāo)赶虻念?lèi)型是int*()[4]在指針的算術(shù)運(yùn)算中，指針?biāo)赶虻念?lèi)型有很大的作用。指針的類(lèi)型和指針?biāo)赶虻念?lèi)型是兩個(gè)不同的概念。2021/5/913（3）指針的值指針的值是指針本身存儲(chǔ)的數(shù)值，這個(gè)值將被編譯器當(dāng)作一個(gè)地址，而不是一般的數(shù)值。在位長(zhǎng)32位的系統(tǒng)中，內(nèi)存地址都是32位的，所以所有類(lèi)型的指針的值都是一個(gè)32位整數(shù)。指針?biāo)赶虻膬?nèi)存區(qū)域就是從指針的值所代表的那個(gè)內(nèi)存地址開(kāi)始，長(zhǎng)度為sizeof（指針?biāo)赶虻念?lèi)型）的一片內(nèi)存區(qū)域。我們說(shuō)一個(gè)指針的值是X，就相當(dāng)于說(shuō)該指針指向了以X為首地址的一片內(nèi)存區(qū)域。指針?biāo)赶虻膬?nèi)存區(qū)域和指針?biāo)赶虻念?lèi)型是兩個(gè)完全不同的概念。2021/5/914（4）指針本身所占據(jù)的內(nèi)存區(qū)用函數(shù)sizeof（指針的類(lèi)型）測(cè)一下就知道了。在32位的系統(tǒng)中，指針本身占據(jù)了4字節(jié)的長(zhǎng)度。2021/5/915例3、閱讀程序，寫(xiě)出程序的運(yùn)行結(jié)果。//p8-1-3#include<bits/stdc++.h>usingnamespacestd;intmain(){int*p,*q;p=(int*)malloc(40);//動(dòng)態(tài)申請(qǐng)40字節(jié)用來(lái)存放int類(lèi)型，并返回首地址給pq=p;*p=1;p++;*p=2;free(q);//釋放剛才申請(qǐng)的40字節(jié)的空間return0;}2021/5/916【程序說(shuō)明】（1）單步跟蹤程序，發(fā)現(xiàn)執(zhí)行完“*p=1;”，q和p為同一個(gè)地址，*p和*q的值也都是1。（2）繼續(xù)跟蹤程序，執(zhí)行完“*p=2;”，p指向了下一個(gè)整數(shù)空間，在原來(lái)的地址上加4，因?yàn)橐粋€(gè)整型占4個(gè)字節(jié)。*p的值也變成了2。

（3）程序中的“free(q);”是釋放一開(kāi)始申請(qǐng)的40個(gè)字節(jié)的內(nèi)存空間，是配合malloc()使用。注意釋放的是內(nèi)存，q和p的地址還在，指針并沒(méi)有被釋放，指針仍然指向原來(lái)的存儲(chǔ)空間。指針是一個(gè)變量，只有程序結(jié)束時(shí)才被銷(xiāo)毀。釋放了內(nèi)存空間后，原來(lái)指向這塊空間的指針還是存在，只不過(guò)現(xiàn)在指針指向的內(nèi)容是未定義的，里面可能會(huì)有一些垃圾內(nèi)容。繼續(xù)跟蹤看看p、q、*p、*q的值。

2021/5/917動(dòng)態(tài)申請(qǐng)內(nèi)存（1）malloc()void*malloc(unsignedsize);在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配一塊長(zhǎng)度為size字節(jié)的連續(xù)區(qū)域，參數(shù)size為需要內(nèi)存空間的長(zhǎng)度，返回該區(qū)域的首地址。（2）calloc()void*calloc(size_tnumelements,size_tsizeofelement);與malloc相似，參數(shù)sizeofelement為申請(qǐng)地址的單位元素長(zhǎng)度，numelements為元素個(gè)數(shù)，即在內(nèi)存中申請(qǐng)numelements*sizeofelement字節(jié)大小的連續(xù)地址空間。（3）realloc()void*realloc(void*ptr,unsignednewsize);給一個(gè)已經(jīng)分配了地址的指針重新分配空間，參數(shù)ptr為原有的空間地址，newsize是重新申請(qǐng)的地址長(zhǎng)度。2021/5/918實(shí)踐鞏固2021/5/919第2課指針的引用與運(yùn)算學(xué)習(xí)目標(biāo)1.理解并學(xué)會(huì)引用指針。2.掌握指針的常用運(yùn)算。2021/5/9201.指針的引用首先理解指針變量與普通變量的區(qū)別和對(duì)應(yīng)關(guān)系。例如，定義一個(gè)指針變量“int*p；”和一個(gè)普通變量“inta；”，關(guān)于兩者之間的各種引用方式對(duì)應(yīng)關(guān)系如下：1）“p”等同于“&a”，表示的是內(nèi)存地址。2）“*p”等同于“a”，表示變量里存儲(chǔ)的實(shí)際數(shù)據(jù)。3）“*p=3；”等同于“a=3；”，表示變量的賦值方法。2021/5/9212.指針的運(yùn)算如果定義的是局部指針變量，其地址就是隨機(jī)的，直接操作會(huì)引發(fā)不可預(yù)測(cè)的錯(cuò)誤。所以，指針變量一定要初始化后才能引用。由于指針變量存儲(chǔ)的是內(nèi)存地址，所以也可以執(zhí)行加法、減法運(yùn)算，一般用來(lái)配合數(shù)組進(jìn)行尋址操作。例如：2021/5/922例1、閱讀并上機(jī)調(diào)試以下程序，體會(huì)指針變量的加法運(yùn)算。//p8-2-1#include<iostream>usingnamespacestd;intmain(){inta[100],n;cin>>n;for(inti=0;i<n;i++)cin>>a[i];int*p=&a[0];//指針p指向數(shù)組首元素的地址for(inti=0;i<n;i++){cout<<*p<<endl;p++;//指針每次往后移動(dòng)一個(gè)區(qū)域}return0;}2021/5/923【問(wèn)題分析】1）程序的作用是輸入n及n個(gè)整數(shù)，使用指針變量依次遍歷輸出。2）程序中的“p++”是廣義的“p=p+1”，本質(zhì)上是“p+sizeof(int)”。3）注意，“*p+3”和“*（p+3）”是不同的。對(duì)于本題，前者是指a[0]+3，而后者是指a[3]。2021/5/924例2、求和【問(wèn)題描述】輸入n個(gè)正整數(shù)，要求對(duì)這n個(gè)數(shù)中的奇數(shù)和偶數(shù)分別求和。【輸入格式】第1行1個(gè)正整數(shù)n，1≤n≤5000。以下n行，每行一個(gè)正整數(shù)（1~20000之間）。【輸出格式】2行2個(gè)整數(shù)。第1行為所有奇數(shù)之和，第2行為所有偶數(shù)之和?！据斎霕永?310758【輸出樣例】15182021/5/925//p8-2-2#include<iostream>usingnamespacestd;intmain(){intn,a[5011];int*p,*s1,*s2;//s1和s2指向的單元分別存放偶數(shù)和、奇數(shù)和cin>>n;for(inti=0;i<n;i++)cin>>a[i];p=&a[0];s1=new(int);//申請(qǐng)一個(gè)存放整數(shù)類(lèi)型的內(nèi)存空間，把地址記錄在s1中*s1=0;//累加器賦初值0s2=new(int);//申請(qǐng)一個(gè)存放整數(shù)類(lèi)型的內(nèi)存空間，把地址記錄在s2中*s2=0;//累加器賦初值0for(inti=0;i<n;i++){if(*p%2==0)*s1+=*p;else*s2+=*p;p++;}cout<<*s2<<endl<<*s1<<endl;return0;}2021/5/926例3、閱讀并上機(jī)調(diào)試以下程序，體會(huì)無(wú)類(lèi)型指針的使用。//p8-2-3#include<iostream>usingnamespacestd;intmain(){inta=10;doubleb=3.5;void*p;p=&a;cout<<*(int*)p<<endl;p=&b;cout<<*(double*)p<<endl;return0;}2021/5/927例4、閱讀并上機(jī)調(diào)試以下程序，體會(huì)多重指針的使用。//p8-2-4#include<iostream>usingnamespacestd;intmain(){inta=10;int*p;int**pp;p=&a;pp=&p;cout<<a<<“=”<<*p<<“=”<<**pp<<endl;return0;}2021/5/928實(shí)踐鞏固2021/5/929第3課指針與數(shù)組學(xué)習(xí)目標(biāo)1.理解數(shù)組指針。2.學(xué)會(huì)使用指針實(shí)現(xiàn)數(shù)組操作。3.學(xué)會(huì)使用指針實(shí)現(xiàn)字符串操作。2021/5/930指針與數(shù)組在C++中，數(shù)組名在一定意義上可以被看成指針?！皵?shù)組的指針”是指整個(gè)數(shù)組在內(nèi)存中的起始地址，“數(shù)組元素的指針”是指數(shù)組中某個(gè)元素所占存儲(chǔ)單元的地址。一般可以使用“下標(biāo)法”訪問(wèn)數(shù)組元素，如a[5]；也可以使用“地址法”訪問(wèn)數(shù)組元素，因?yàn)閿?shù)組名就代表數(shù)組在內(nèi)存中的起始地址，也就是a[0]的地址，如a+4就表示a[4]的地址；也可以通過(guò)“指針?lè)ā痹L問(wèn)數(shù)組元素，通過(guò)數(shù)組的指針或者數(shù)組元素的指針訪問(wèn)數(shù)組元素，能使目標(biāo)程序質(zhì)量更高，占用內(nèi)存更少，運(yùn)行速度更快。2021/5/931例1、閱讀并上機(jī)調(diào)試以下程序，體會(huì)數(shù)組的指針和數(shù)組元素的指針。//p8-3-1#include<iostream>usingnamespacestd;intmain(){inta[]={10,11,12,13,14,15};int*p=a+4;cout<<*a;cout<<““<<*(a+3);cout<<““<<*(++p)<<endl;return0;}2021/5/932【問(wèn)題分析】1）運(yùn)行程序，輸出“101315”。2）程序中直接拿數(shù)組名a當(dāng)指針用。但是a始終是靜態(tài)的，是不可變的，不能做“a=a+4；”運(yùn)算，而指針可以做“++p”或“p=p+4；”運(yùn)算。3）語(yǔ)句“scanf（“%d“，&n）；”其實(shí)就是指針的意思。如果是數(shù)組，就不需要加取地址符“&”。2021/5/933例2、閱讀并上機(jī)調(diào)試以下程序，體會(huì)動(dòng)態(tài)數(shù)組的定義和使用。//p8-3-2#include<iostream>usingnamespacestd;intmain(){intn,*a;cin>>n;a=newint[n];//申請(qǐng)n個(gè)連續(xù)的int類(lèi)型內(nèi)存空間（動(dòng)態(tài)數(shù)組），并返回首地址給afor(inti=0;i<n;i++)cin>>a[i];for(inti=1;i<n;i++)a[i]+=a[i-1];for(inti=0;i<n-1;i++)cout<<a[i]<<““;cout<<a[n-1]<<endl;return0;}2021/5/934【問(wèn)題分析】1）運(yùn)行程序，輸入10及如下10個(gè)數(shù)“12345678910”，輸出“13610152128364555”。2）因?yàn)橹羔樋梢詣?dòng)態(tài)申請(qǐng)空間。那一次申請(qǐng)100個(gè)變量空間，系統(tǒng)給的地址是連續(xù)的，就可以當(dāng)成數(shù)組使用，這就是“動(dòng)態(tài)數(shù)組”的一種。3）在信息學(xué)競(jìng)賽中遇到大批量數(shù)據(jù)的情況下，數(shù)組開(kāi)小只能拿部分分，開(kāi)大又可能爆空間，此時(shí)就可以定義和使用動(dòng)態(tài)數(shù)組。2021/5/935例3、行列轉(zhuǎn)換【問(wèn)題描述】對(duì)于一個(gè)n×m的稀疏矩陣，按照行、列、值的格式讀入k個(gè)元素（其他位置的值為0），再輸出這些數(shù)?！据斎敫袷健康?行3個(gè)整數(shù)，表示n、m和k，每?jī)蓚€(gè)數(shù)之間用一個(gè)空格隔開(kāi)。以下k行，按照“行優(yōu)先（從上到下、從左到右）”的方式讀入k個(gè)非0元素。每行3個(gè)數(shù)，依次為行號(hào)、列號(hào)、元素值，每?jī)蓚€(gè)數(shù)之間用一個(gè)空格隔開(kāi)?！据敵龈袷健枯敵鰇個(gè)數(shù)，按照“列優(yōu)先（從左到右、從上到下）”的方式輸出，每?jī)蓚€(gè)數(shù)之間用一個(gè)空格隔開(kāi)。【輸入樣例】453121214234345【輸出樣例】1245232021/5/936例4、閱讀并上機(jī)調(diào)試以下程序，體會(huì)使用指針實(shí)現(xiàn)字符串的輸入輸出及存儲(chǔ)。//p8-3-4#include<iostream>#include<cstring>usingnamespacestd;intmain(){char*s;s=newchar;//給s申請(qǐng)一個(gè)地址cin>>s;//輸入字符串以空格或者回車(chē)結(jié)束cout<<s<<endl;cout<<strlen(s);return0;}2021/5/937【程序說(shuō)明】運(yùn)行程序，輸入“helloworld!”。輸出：hello5使用指針實(shí)現(xiàn)字符串的輸入、輸出及存儲(chǔ)，與普通數(shù)組類(lèi)似。只是在使用前一定要給字符串變量指定一個(gè)地址。2021/5/938例5、閱讀并上機(jī)調(diào)試以下程序，體會(huì)使用指針實(shí)現(xiàn)字符串的復(fù)制。//p8-3-5#include<iostream>usingnamespacestd;voidcopy_string(char*from,char*to){//用字符指針作為函數(shù)參數(shù)while(*from!=‘\0’){*to=*from;*to++;*from++;}*to=‘\0’;//在結(jié)束位置強(qiáng)制加結(jié)束符}intmain(){chara[20]=“clanguage”;charb[20]=“verygood”;copy_string(a,b);cout<<a<<endl;cout<<b<<endl;return0;}2021/5/939實(shí)踐鞏固2021/5/940第4課函數(shù)指針及擴(kuò)展學(xué)習(xí)目標(biāo)1.理解并學(xué)會(huì)使用函數(shù)指針。2.了解函數(shù)指針數(shù)組。3.了解引用與指針的區(qū)別。4.了解指向結(jié)構(gòu)體的指針。2021/5/941函數(shù)指針及擴(kuò)展程序中需要處理的數(shù)據(jù)都保存在內(nèi)存空間，而程序以及函數(shù)同樣也保存在內(nèi)存空間，C++支持通過(guò)函數(shù)的入口地址（指針）訪問(wèn)函數(shù)。另一方面，有些函數(shù)在編寫(xiě)時(shí)要調(diào)用其他的輔助函數(shù)，但是尚未確定，在具體執(zhí)行時(shí)，再為其傳遞輔助函數(shù)的地址。比如排序函數(shù)sort（a，a+n，cmp），其中的比較函數(shù)cmp是根據(jù)需要傳遞給sort的，就是傳遞了一個(gè)函數(shù)指針。函數(shù)指針就是指向函數(shù)的指針變量，定義格式如下：類(lèi)型名（*函數(shù)名）（參數(shù)）;2021/5/942例1、閱讀并上機(jī)調(diào)試以下程序，體會(huì)函數(shù)指針的使用。//p8-4-1a#include<iostream>usingnamespacestd;inttest(inta){returna*a;}intmain(){cout<<test<<endl;//或者&test,輸出函數(shù)的地址int(*fp)(inta);//聲明一個(gè)指向函數(shù)的指針變量fpfp=test;//或者&test,將函數(shù)test的入口地址傳給fpcout<<fp(5)<<endl;//調(diào)用函數(shù)cout<<(*fp)(10)<<endl;return0;}2021/5/943使用函數(shù)指針需要注意的幾點(diǎn)：1）定義函數(shù)指針要與函數(shù)原型一致。例如，函數(shù)為“inttest(int)；”，則函數(shù)指針聲明為“int(*fp)(int)；”。2）獲取函數(shù)的地址有兩種方式：一種是直接使用函數(shù)名，如test或者fp=test；另一種是使用取地址符，如&test或者fp=&test。3）調(diào)用函數(shù)有兩種方式：一種是直接使用函數(shù)名，如fp(5)；另一種是使用函數(shù)指針調(diào)用函數(shù)，如(*fp)(5)。4）函數(shù)指針還支持一種結(jié)合typedef的定義方式。參見(jiàn)下一頁(yè)例1的另一個(gè)程序：

5）可以定義一個(gè)數(shù)組存放多個(gè)函數(shù)指針。參見(jiàn)例2：2021/5/944//p8-4-1b#include<iostream>usingnamespacestd;intadd(inta,intb){returna+b;}typedefint(*addp)(int,int);//聲明一個(gè)函數(shù)指針變量addpintmain(){addpfp=add;//定義addp類(lèi)型的函數(shù)指針fp,并賦值為addcout<<fp(2,3)<<endl;//程序輸出5return0;}2021/5/945例2、模擬計(jì)算器【問(wèn)題描述】輸入兩個(gè)正整數(shù)m和n，再輸入一個(gè)代表運(yùn)算方案的數(shù)字k：1代表求m+n的值；2代表求m-n的值；3代表求m×n的值；4代表求m/n的值（整除）。請(qǐng)函數(shù)指針數(shù)組編程模擬計(jì)算器，輸出相應(yīng)的運(yùn)算結(jié)果?！据斎敫袷健康?行為2個(gè)正整數(shù)m和n；第2行為1個(gè)正整數(shù)k，1≤k≤4?！据敵龈袷健恳恍幸粋€(gè)整數(shù)，表示相應(yīng)的運(yùn)算結(jié)果?！据斎霕永?81【輸出樣例】142021/5/946//p8-4-2#include<iostream>#include<cstdio>usingnamespacestd;intcal1(inta,intb){returna+b;}intcal2(inta,intb){returna-b;}intcal3(inta,intb){returna*b;}intcal4(inta,intb){returna/b;}typedefint(*f)(inta,intb);//自定義一個(gè)函數(shù)指針變量類(lèi)型fintmain(){freopen(“cal.in”,”r”,stdin);freopen(“cal.out”,”w”,stdout);intm,n,k;fa[4]={cal1,cal2,cal3,cal4};//定義函數(shù)指針數(shù)組a,4個(gè)元素,每個(gè)元素為f類(lèi)型,并且分別賦初值cin>>m>>n>>k;cout<<a[k-1](m,n)<<endl;//用a[k-1]()來(lái)調(diào)用相應(yīng)的函數(shù)return0;}2021/5/947例3、閱讀并上機(jī)調(diào)試以下程序，體會(huì)引用變量的使用。//p8-4-3#include<iostream>usingnamespacestd;intmain(){inta=10,b=20;int*f;int&ra=a;//定義一個(gè)引用變量ra,同時(shí)初始化f=&a;cout<<“a=”<<*f<<endl;ra+=5;cout<<“a=”<<*f<<endl;return0;}2021/5/948【問(wèn)題分析】1）運(yùn)行程序，輸出：a=10a=152）“引用變量”是C++中的一種復(fù)合類(lèi)型，它的本質(zhì)就是給原變量起了一個(gè)別名，就像生活中有個(gè)人叫“張三”，大家給他取了一個(gè)別名叫“樂(lè)樂(lè)”，那么這兩個(gè)名字指的是同一個(gè)人。引用就相當(dāng)于給原變量取了一個(gè)別名，對(duì)引用變量的操作就是對(duì)原變量的操作。3）注意區(qū)分引用變量與指針變量，引用也不是取地址。另外，引用在定義的同時(shí)必須進(jìn)行初始化，不能通過(guò)賦值語(yǔ)句，把對(duì)一個(gè)變量的引用改成對(duì)另一個(gè)變量的引用。4）程序中的a、*f和ra都是指向同一個(gè)內(nèi)存地址。2021/5/9495）使用引用會(huì)使程序代碼更加簡(jiǎn)潔，一般用在多重?cái)?shù)組中。例如遞推式“f[a[i][j]]

=(f[a[i][j]-1]

+f[a[i][j]-2])*a[i][j]”，可以先定義引用變量“int&k=a[i][j]”，然后簡(jiǎn)化寫(xiě)成“f[k]

=(f[k-1]+f[k-2])*k”。6）函數(shù)參數(shù)一般都是使用普通變量實(shí)現(xiàn)“傳值”方式，也可以使用指針參數(shù)實(shí)現(xiàn)“傳址”方式，比如數(shù)組。有了引用，就可以使用“引用參數(shù)”，使得函數(shù)中的變量名成為調(diào)用函數(shù)中的變量的別名。這種傳遞參數(shù)的方式叫“按引用傳遞”。2021/5/950例4、閱讀并上機(jī)調(diào)試以下程序，體會(huì)引用參數(shù)。//p8-4-4,交換兩個(gè)變量的值#include<iostream>usingnamespacestd;voidchange1(int&m,int&n){//引用參數(shù)intt=m;m=n;n=t;return;}voidchange2(int*m,int*n){//指針參數(shù)intt=*m;*m=*n;*n=t;return;}2021/5/951voidchange3(intm,intn){//普通變量參數(shù)intt=m;m=n;n=t;return;}intmain(){intx=7,y=160;change1(x,y);cout<<x<<““<<y<<endl;change2(&x,&y);cout<<x<<““<<y<<endl;change3(x,y);cout<<x<<““<<y<<endl;return0;}2021/5/952例5、閱讀并上機(jī)調(diào)試以下程序，體會(huì)指向結(jié)構(gòu)體變量的指針。//p8-4-5#include<iostream>usingnamespacestd;structtstudent{intnum;charname[20];charsex;intage;};tstudentx={13,”lihao”,’m’,35};tstudent*p;intmain(){p=&x;cout<<x.num<<endl;cout<<(*p).name<<endl;cout<<p->age<<endl;return0;}2021/5/953【程序說(shuō)明】1）運(yùn)行程序，輸出：13Lihao352）一個(gè)指向結(jié)構(gòu)體變量的指針就是該變量占據(jù)的內(nèi)存空間的起始地址，如圖8.4-1所示（下一頁(yè)）。3）訪問(wèn)結(jié)構(gòu)體成員的方法為：結(jié)構(gòu)體名.成員名。使用指針訪問(wèn)結(jié)構(gòu)體成員有兩種方式：結(jié)構(gòu)體名->成員名，或者（*指針變量名）.成員名。例如p->name，或者（*p）.name，但不能寫(xiě)成*。4）如果函數(shù)的參數(shù)是一個(gè)結(jié)構(gòu)體變量（按值傳遞），那么函數(shù)調(diào)用時(shí)就要復(fù)制整個(gè)結(jié)構(gòu)體，效率不高。這種情況下，一般使用指針參數(shù)或者引用參數(shù)。2021/5/9542021/5/955實(shí)踐鞏固2021/5/956第5課指針應(yīng)用舉例學(xué)習(xí)目標(biāo)學(xué)會(huì)使用指針建立鏈表，并熟練應(yīng)用鏈表結(jié)構(gòu)解決一些實(shí)際問(wèn)題。2021/5/957線性表是一種常用的數(shù)據(jù)結(jié)構(gòu)，其中的每一個(gè)元素（結(jié)點(diǎn)）都有唯一的前驅(qū)和唯一的后續(xù)。當(dāng)然，第一個(gè)元素只有后續(xù)，最后一個(gè)元素只有前驅(qū)。線性表一般分為“順序表”和“鏈表”。順序表可以簡(jiǎn)單理解成前面學(xué)過(guò)的數(shù)組。它是一種邏輯上和物理上都是有序的、連續(xù)存儲(chǔ)的靜態(tài)結(jié)構(gòu)。鏈表是一種物理上不連續(xù)存儲(chǔ)的動(dòng)態(tài)結(jié)構(gòu)，數(shù)據(jù)之間的邏輯順序是通過(guò)鏈表中的指針鏈接關(guān)系實(shí)現(xiàn)的。線性表2021/5/958鏈表鏈表由一系列“結(jié)點(diǎn)”組成，結(jié)點(diǎn)可以在需要時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域至少包括兩部分：一是存儲(chǔ)數(shù)據(jù)元素的“數(shù)據(jù)域”；二是存儲(chǔ)下一個(gè)結(jié)點(diǎn)內(nèi)存地址的“指針域”。圖8.5-1就是一個(gè)鏈表的示意圖，其中，head表示頭結(jié)點(diǎn)，數(shù)據(jù)域的值為5的結(jié)點(diǎn)為尾結(jié)點(diǎn)，其指針域?yàn)镹ULL。鏈表中每個(gè)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義如下：structnode{intnum;node*next;};2021/5/959（1）鏈表的建立建立鏈表有“頭插法”和“尾插法”兩種方法，前者是把新結(jié)點(diǎn)插在頭結(jié)點(diǎn)之后，后者是把新結(jié)點(diǎn)插在尾結(jié)點(diǎn)之后。本課以尾插法為例建立鏈表，就是不斷地在鏈表尾部鏈接一個(gè)新結(jié)點(diǎn)。如圖8.5-2所示，r為鏈表的尾部結(jié)點(diǎn)，p為要增加的新結(jié)點(diǎn)，只需要把r->next指向p即可，然后把r再指向新的尾部。2021/5/960（1）鏈表的建立——尾插法2021/5/961（2）鏈表的遍歷鏈表的遍歷就是從鏈表的頭結(jié)點(diǎn)head開(kāi)始，依次訪問(wèn)每一個(gè)元素，直到鏈表尾部，包括查找、輸出等操作。如果已經(jīng)創(chuàng)建了一個(gè)鏈表，如何查找其中是否有給定的元素x呢？只需要從頭結(jié)點(diǎn)開(kāi)始掃描，如果當(dāng)前結(jié)點(diǎn)數(shù)據(jù)域的值等于x，那么就表示找到了x，如果到達(dá)鏈表尾部還沒(méi)有找到，則鏈表中沒(méi)有x這個(gè)元素。同樣，鏈表的輸出也是從頭結(jié)點(diǎn)開(kāi)始一個(gè)一個(gè)輸出，直到鏈表尾部結(jié)束。2021/5/962（3）鏈表的插入鏈表的插入就是在鏈表給定位置插入一個(gè)新結(jié)點(diǎn)。如圖8.5-3所示，就是在鏈表數(shù)據(jù)域值為4和9的兩個(gè)結(jié)點(diǎn)中間插入一個(gè)數(shù)據(jù)域值為7的結(jié)點(diǎn)。如果在表頭表尾插入結(jié)點(diǎn)要特殊處理。2021/5/963（4）鏈表的刪除鏈表的刪除就是刪除鏈表中的某一個(gè)元素，如圖8.5-4所示，就是要?jiǎng)h除鏈表中數(shù)據(jù)域值為7的結(jié)點(diǎn)。如果刪除頭結(jié)點(diǎn)要特殊處理。2021/5/964例1、陶陶摘蘋(píng)果【問(wèn)題描述】陶陶家的院子里有一棵蘋(píng)果樹(shù)，秋天樹(shù)上會(huì)結(jié)10個(gè)蘋(píng)果。蘋(píng)果成熟的時(shí)候，陶陶就會(huì)跑去摘蘋(píng)果。陶陶有個(gè)30厘米高的板凳，當(dāng)她不能直接用手摘到蘋(píng)果的時(shí)候，就會(huì)踩到板凳上再試試?，F(xiàn)在已知10個(gè)蘋(píng)果到地面的高度，以及陶陶把手伸直的時(shí)候能夠達(dá)到的最大高度，請(qǐng)幫陶陶算一下她能夠摘到的蘋(píng)果的數(shù)目。假設(shè)她碰到蘋(píng)果，蘋(píng)果就會(huì)掉下來(lái)?！据斎敫袷健康?行包含10個(gè)100~200之間（包括100和200）的正整數(shù)（以厘米為單位）分別表示10個(gè)蘋(píng)果到地面的高度，兩個(gè)相鄰的正整數(shù)之間用一個(gè)空格隔開(kāi)。第2行只包括一個(gè)100~120之間（包含100和120）的正整數(shù)（以厘米為單位），表示陶陶把手伸直的時(shí)候能夠達(dá)到的最大高度。2021/5/965【輸出格式】一行一個(gè)整數(shù)，表示陶陶能夠摘到的蘋(píng)果的數(shù)目?！据斎霕永?00200150140129134167198200111110【輸出樣例】5【問(wèn)題分析】定義一個(gè)一維數(shù)組記錄10個(gè)蘋(píng)果的高度，如果陶陶手伸直能夠到的高度加上30大于或等于蘋(píng)果的高度，那么這個(gè)蘋(píng)果就會(huì)掉下來(lái)，則能摘到的蘋(píng)果數(shù)就加一。可以用動(dòng)態(tài)存儲(chǔ)實(shí)現(xiàn)本題。2021/5/966//p8-5-1#include<iostream>#include<cstdio>usingnamespacestd;inta[11];intmain(){freopen(“apple.in”,”r”,stdin);freopen(“apple.out”,”w”,stdout);int*p;ints=0;p=a;for(inti=0;i<10;i++){cin>>*p;p++;}p=new(int);cin>>*p;for(inti=0;i<10;i++)if(a[i]<=*p+30)s++;cout<<s<<endl;return0;}建議跟蹤程序，體會(huì)過(guò)程。2021/5/967例2、插入排序【問(wèn)題描述】給出一個(gè)整數(shù)x和一個(gè)數(shù)列，這個(gè)數(shù)列保證從小到大排列?，F(xiàn)在