算法設(shè)計(jì)基礎(chǔ)題目.ppt

,算,法,設(shè),計(jì),基,礎(chǔ),Introduction to the Design of Algorithm,計(jì)算機(jī)學(xué)院 軟件工程教研室 張榮博,手機(jī)Email:,2,第4講 指針專題,目標(biāo): 本章旨在向?qū)W員介紹指針的概念以及各種指針的用法，通過(guò)本章的學(xué)習(xí)，學(xué)員應(yīng)該掌握如下知識(shí)： 內(nèi)存、地址與指針的概念 指針的用法,地址的概念,3,內(nèi)存地址：物理內(nèi)存中存儲(chǔ)單元的編號(hào)。 使用內(nèi)存：在地址所標(biāo)識(shí)的存儲(chǔ)單元中存放數(shù)據(jù)。 注意：內(nèi)存單元的地址與內(nèi)存單元中的數(shù)據(jù)是兩個(gè)完全不同的概念。 一個(gè)是address； 另一個(gè)是value； 訪問(wèn)方式： (1)直接訪問(wèn)使用變量名進(jìn)行存取 (2)間接訪問(wèn)通過(guò)該變量的地址來(lái)訪問(wèn),address,name,4,程序中: int i; float k;,內(nèi)存中每個(gè)字節(jié)有一個(gè)編號(hào)-地址,.,.,2000,2002,2006,內(nèi)存,0,i,k,編譯或函數(shù)調(diào)用時(shí)為其分配內(nèi)存單元,變量是對(duì)程序中數(shù)據(jù) 存儲(chǔ)空間的抽象,變量與內(nèi)存,指針與指針變量 指針：一個(gè)變量的地址 指針變量：專門(mén)存放變量地址的變量,指針,指針變量,變量的內(nèi)容,變量的地址,變量i地址是2000，指針變量i_pointer地址是2002,6,指針變量與其所指向的變量之間的關(guān)系,指針變量的定義,7,一般形式： 存儲(chǔ)類型 數(shù)據(jù)類型 *指針名；,合法標(biāo)識(shí)符,指針變量本身的存儲(chǔ)類型,指針的目標(biāo)變量的數(shù)據(jù)類型,例 int *p1,*p2; float *q ; static char *name;,注意： 1、int *p1, *p2; 與 int *p1, p2; 2、指針變量名是p1,p2 ,不是*p1,*p2 3、指針變量只能指向定義時(shí)所規(guī)定類型的變量 4、指針變量定義后，變量值不確定，應(yīng)用前必須先賦值,指針變量的初始化及賦值,8,指針變量的初始化 一般形式：存儲(chǔ)類型 數(shù)據(jù)類型 *指針名 = 初始地址值；,賦給指針變量,例 int i，j; int *pointer_1,*pointer_2; pointer_1=,例 float i，j; float *pointer_1,*pointer_2; pointer_1=,&: 取地址運(yùn)算符 *: 取內(nèi)容運(yùn)算符 *與&優(yōu)先級(jí)相同.,9,例 void main( ) int i; static int *p= / ( ) ,不能用auto變量的地址 去初始化static型指針 Why ?,一個(gè)指針變量只能指向同一個(gè)類型的變量,例題,10,#include void main() int a=5; int *p= ,11,main () int a,b; int *pointer_1, *pointer_2; /* 定義指針變量 */ a = 100; b = 10; pointer_1 = 程序運(yùn)行結(jié)果：,100，10 100，10,例：輸入a和b兩個(gè)整數(shù)，按先大后小的順序輸出a和b,12,main () int *p1, *p2, *p , a, b; scanf(“%d,%d“, 運(yùn)行:5,9,a=5,b=9; max=9,min=5 該例不交換變量a、b的值，而是交換指針p1、p2的值。,零指針與空類型指針,13,零指針：(空指針) 定義:指針變量值為零 表示： int * p=0;,p指向地址為0的單元， 系統(tǒng)保證該單元不作它用 表示指針變量值沒(méi)有意義,#define NULL 0 int *p=NULL；,p=NULL與未對(duì)p賦值不同 用途: 避免指針變量的非法引用 在程序中常作為狀態(tài)比較,例 int *p; while(p!=NULL) . ,指針變量作為函數(shù)參數(shù),14,指針變量作為函數(shù)參數(shù)地址傳遞 特點(diǎn)：共享內(nèi)存 ,“ 雙向”傳遞。,例 調(diào)用子函數(shù)，將2個(gè)整數(shù)從大到小輸出,15,void swap(int *p1, int *p2) int p; p=*p1; *p1=*p2; *p2=p; ,void main() int a,b; int *pointer_1,*pointer_2; scanf(“%d,%d“, ,指針與數(shù)組,16,指向數(shù)組元素的指針變量,定義 int a10; int *p; 賦值 p=,數(shù)組名是表示數(shù)組首地址的地址常量 p = a的作用是把數(shù)組的首地址賦給指針變量P， 而不是把數(shù)組a的各元素賦給p。,也可以在定義指針變量時(shí)賦初值 int *pa;,數(shù)組元素表示方法,17,無(wú)論是下標(biāo)法（a i ），還是指針?lè)ǎ? (p +i) ）,盡管表現(xiàn)形式不同，可本質(zhì)都是： *（首址+ 偏移量）,例題：輸出數(shù)組中的全部元素,18,void main() int a10; int *p,i; for(i=0;i10;i+) scanf(“%d“ , ,指針變量的運(yùn)算,19,p+，使p指向下一元素a1； *p+，和*同優(yōu)先級(jí)，自右至左，等價(jià)于*（p+） *（p+）和*（ + p）作用不同。前者，先取*p值，再使p+1。后者先使p+1，再取*p。 和運(yùn)算符可以使指針變量向前或向后移動(dòng)。 若p1與p2指向同一數(shù)組，p1-p2=兩指針間元素個(gè)數(shù)(p1-p2)/d,20,void main() int i,*p,a7; p=a; for(i=0;i7;i+) scanf(“%d“,p+); printf(“n“); for(i=0;i7;i+,p+) printf(“%d“,*p); ,例 注意指針的當(dāng)前值,p=a;,指針變量可以指到數(shù)組后的內(nèi)存單元,指針變量的運(yùn)算,21,數(shù)組名作函數(shù)參數(shù),voidmain() int array10; f(array,10); ,f(int b,int n ) ,array實(shí)參數(shù)組名，代表該數(shù)組首元素的地址,b形參數(shù)組名，用來(lái)接收從實(shí)參傳遞過(guò)來(lái)的數(shù)組首元素的地址，實(shí)際上，形參數(shù)組名是按指針變量處理的,22,f(int arr,int n ) ,f(int *arr,int n ) ,*(arr+i)和arri 等價(jià),例 將數(shù)組a中的n個(gè)整數(shù)按相反順序存放,23,void inv(int *x, int n) int t,*i,*j,*p,m=(n-1)/2; i=x; j=x+n-1; p=x+m; for(;i=p;i+,j-) t=*i; *i=*j; *j=t; ,#include void main() int i,a10=3,7,9,11,0,6,7,5,4,2; inv(a,10); printf(“The array has been reverted:n“); for(i=0;i10;i+) printf(“%d,“,ai); printf(“n“); ,內(nèi)存變化演示,24,void inv(int *x, int n) int t,*i,*j,*p,m=(n-1)/2; i=x; j=x+n-1; p=x+m; for(;i=p;i+,j-) t=*i; *i=*j; *j=t; ,子函數(shù)用數(shù)組、主函數(shù)用指針,25,void inv(int x, int n) int t,i,j,m=(n-1)/2; for(i=0;i=m;i+) j=n-1-i; t=xi; xi=xj; xj=t; ,void main() int i,a10,*p=a; for(i=0;i10;i+,p+) scanf(“%d“,p); p=a; inv(p,10); printf(“The array has been reverted:n“); for(p=arr;parr+10;p+) printf(“%d “,*p); ,實(shí)參用指針變量,形參用數(shù)組名,數(shù)組完全可以用指針代替。,練習(xí)：使用指針，從10個(gè)數(shù)中找出其中最大值和最小值,26,int max=0 , min = 0; void max_min_value(int *array, int n) int *p, *array_end; array_end = array+n; max=min=*array; for(p=array+1;pmax) max=*p; else if(*pmin) min=*p; return; ,27,void main() int i,number10,*p; p=number; printf(“enter 10 integer numbers:n“); for(i=0;i10;i+,p+) scanf(“%d“,p); printf(“the 10 integer numbers:n“); for(p=number,i=0;i10;i+,p+) printf(“%d “,*p); p=number; max_min_value(p,10); printf(“nmax=%d,min=%dn“,max,min); ,運(yùn)行結(jié)果： enter 10 integer numbers 2 4 6 8 0 3 45 67 89 100 the 10 integer numbers: 2 4 6 8 0 3 45 67 89 100 Max100，min3,練習(xí)：對(duì)10個(gè)整數(shù)按由大到小的順序排序,28,void main() int *p,i,a10; p=a; for(i=0;i10;i+) scanf(“%d“,p+); p=a; sort(p,10); for(p=a,i=0;i10;i+) printf(“%d “,*p);p+; ,void sort(int x,int n) int i,j,k,t; for(i=0;ixk)k=j; if(k!=i) t=xi;xi=xk;xk=t; ,選擇法,指針運(yùn)算小結(jié),29,1、指針變量加/減運(yùn)算 p+、p-、p+i、p-i、p+=i、p-=i 加1表示指向下一個(gè)數(shù)據(jù)。 2、指針變量賦值 p = 指針變量可以由空值,NULL的值為0,30,3、空指針 p = NULL 空指針p=NULL表示p不指向任何數(shù)據(jù)。 在stdio.h中，NULL被定義為0： #define NULL 0 習(xí)慣上，不使用 p = 0而使用 p = NULL 指針變量p可以與NULL作比較， 例: if (p = = NULL) . 注意：空指針不指向任何數(shù)據(jù)，與p未賦值不同。 當(dāng)p未賦值時(shí)，其值是不確定的，而空指針 的值是確定數(shù)0。,31,、指針變量相減。 當(dāng)p1、p2指向同一個(gè)數(shù)組的元素，指針相減p2-p1等于p1、p2間的元素個(gè)數(shù)。 注意：指針相加無(wú)意義。 5、兩個(gè)指針的比較 當(dāng)p1、p2指向同一個(gè)數(shù)組的元素時(shí)，可以比較，如、p1 p2。若p1、p2不是指向同一個(gè)數(shù)組的元素，比較無(wú)意義。,野指針,32,“野指針”產(chǎn)生的3種原因： 指針變量沒(méi)有被初始化。任何指針變量剛被創(chuàng)建時(shí)不會(huì)自動(dòng)成為NULL指針，它的默認(rèn)值是隨機(jī)的，它會(huì)亂指一氣。 指針p被free或者delete之后，沒(méi)有置為NULL，讓人誤以為p是個(gè)合法的指針。 指針操作超越了變量的作用范圍。,33,避免“野指針”產(chǎn)生的對(duì)策： 使用指針前一定要保證它指向了有效的內(nèi)存空間（或者申請(qǐng)，或者讓指針指向一塊合法的空間；不要忘記為數(shù)組和動(dòng)態(tài)內(nèi)存賦初值。防止將未被初始化的內(nèi)存作為右值使用。 用malloc或new申請(qǐng)內(nèi)存之后，應(yīng)該立即檢查指針值是否為NULL。防止使用指針值為NULL的內(nèi)存；動(dòng)態(tài)內(nèi)存的申請(qǐng)與釋放必須配對(duì)，防止內(nèi)存泄漏。用free或delete釋放了內(nèi)存之后，立即將指針設(shè)置為NULL。 避免數(shù)組或指針的下標(biāo)越界，特別要當(dāng)心發(fā)生“多1”或者“少1”操作。,習(xí)題,34,1 指針變量a所指的字符串長(zhǎng)度為 , 這個(gè)長(zhǎng)度是可以用strlen(a)測(cè)出來(lái)的。 char *a=“nMY Name is”zhang li”.n”; (1)28 (2) 27 (3) 26 (4) 24 (5)23 2 下面程序的作用是，將兩