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

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

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

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

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

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

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

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