算法設計基礎題目.ppt

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