算法设计基础题目.ppt

,算,法,设,计,基,础,Introduction to the Design of Algorithm,计算机学院 软件工程教研室 张荣博,手机Email:,2,第4讲 指针专题,目标: 本章旨在向学员介绍指针的概念以及各种指针的用法，通过本章的学习，学员应该掌握如下知识： 内存、地址与指针的概念 指针的用法,地址的概念,3,内存地址：物理内存中存储单元的编号。 使用内存：在地址所标识的存储单元中存放数据。 注意：内存单元的地址与内存单元中的数据是两个完全不同的概念。 一个是address； 另一个是value； 访问方式： (1)直接访问使用变量名进行存取 (2)间接访问通过该变量的地址来访问,address,name,4,程序中: int i; float k;,内存中每个字节有一个编号-地址,.,.,2000,2002,2006,内存,0,i,k,编译或函数调用时为其分配内存单元,变量是对程序中数据 存储空间的抽象,变量与内存,指针与指针变量 指针：一个变量的地址 指针变量：专门存放变量地址的变量,指针,指针变量,变量的内容,变量的地址,变量i地址是2000，指针变量i_pointer地址是2002,6,指针变量与其所指向的变量之间的关系,指针变量的定义,7,一般形式： 存储类型 数据类型 *指针名；,合法标识符,指针变量本身的存储类型,指针的目标变量的数据类型,例 int *p1,*p2; float *q ; static char *name;,注意： 1、int *p1, *p2; 与 int *p1, p2; 2、指针变量名是p1,p2 ,不是*p1,*p2 3、指针变量只能指向定义时所规定类型的变量 4、指针变量定义后，变量值不确定，应用前必须先赋值,指针变量的初始化及赋值,8,指针变量的初始化 一般形式：存储类型 数据类型 *指针名 = 初始地址值；,赋给指针变量,例 int i，j; int *pointer_1,*pointer_2; pointer_1=,例 float i，j; float *pointer_1,*pointer_2; pointer_1=,&: 取地址运算符 *: 取内容运算符 *与&优先级相同.,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两个整数，按先大后小的顺序输出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的单元， 系统保证该单元不作它用 表示指针变量值没有意义,#define NULL 0 int *p=NULL；,p=NULL与未对p赋值不同 用途: 避免指针变量的非法引用 在程序中常作为状态比较,例 int *p; while(p!=NULL) . ,指针变量作为函数参数,14,指针变量作为函数参数地址传递 特点：共享内存 ,“ 双向”传递。,例 调用子函数，将2个整数从大到小输出,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“, ,指针与数组,16,指向数组元素的指针变量,定义 int a10; int *p; 赋值 p=,数组名是表示数组首地址的地址常量 p = a的作用是把数组的首地址赋给指针变量P， 而不是把数组a的各元素赋给p。,也可以在定义指针变量时赋初值 int *pa;,数组元素表示方法,17,无论是下标法（a i ），还是指针法（* (p +i) ）,尽管表现形式不同，可本质都是： *（首址+ 偏移量）,例题：输出数组中的全部元素,18,void main() int a10; int *p,i; for(i=0;i10;i+) scanf(“%d“ , ,指针变量的运算,19,p+，使p指向下一元素a1； *p+，和*同优先级，自右至左，等价于*（p+） *（p+）和*（ + p）作用不同。前者，先取*p值，再使p+1。后者先使p+1，再取*p。 和运算符可以使指针变量向前或向后移动。 若p1与p2指向同一数组，p1-p2=两指针间元素个数(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;,指针变量可以指到数组后的内存单元,指针变量的运算,21,数组名作函数参数,voidmain() int array10; f(array,10); ,f(int b,int n ) ,array实参数组名，代表该数组首元素的地址,b形参数组名，用来接收从实参传递过来的数组首元素的地址，实际上，形参数组名是按指针变量处理的,22,f(int arr,int n ) ,f(int *arr,int n ) ,*(arr+i)和arri 等价,例 将数组a中的n个整数按相反顺序存放,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; ,子函数用数组、主函数用指针,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); ,实参用指针变量,形参用数组名,数组完全可以用指针代替。,练习：使用指针，从10个数中找出其中最大值和最小值,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个整数按由大到小的顺序排序,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表示指向下一个数据。 2、指针变量赋值 p = 指针变量可以由空值,NULL的值为0,30,3、空指针 p = NULL 空指针p=NULL表示p不指向任何数据。 在stdio.h中，NULL被定义为0： #define NULL 0 习惯上，不使用 p = 0而使用 p = NULL 指针变量p可以与NULL作比较， 例: if (p = = NULL) . 注意：空指针不指向任何数据，与p未赋值不同。 当p未赋值时，其值是不确定的，而空指针 的值是确定数0。,31,、指针变量相减。 当p1、p2指向同一个数组的元素，指针相减p2-p1等于p1、p2间的元素个数。 注意：指针相加无意义。 5、两个指针的比较 当p1、p2指向同一个数组的元素时，可以比较，如、p1 p2。若p1、p2不是指向同一个数组的元素，比较无意义。,野指针,32,“野指针”产生的3种原因： 指针变量没有被初始化。任何指针变量刚被创建时不会自动成为NULL指针，它的默认值是随机的，它会乱指一气。 指针p被free或者delete之后，没有置为NULL，让人误以为p是个合法的指针。 指针操作超越了变量的作用范围。,33,避免“野指针”产生的对策： 使用指针前一定要保证它指向了有效的内存空间（或者申请，或者让指针指向一块合法的空间；不要忘记为数组和动态内存赋初值。防止将未被初始化的内存作为右值使用。 用malloc或new申请内存之后，应该立即检查指针值是否为NULL。防止使用指针值为NULL的内存；动态内存的申请与释放必须配对，防止内存泄漏。用free或delete释放了内存之后，立即将指针设置为NULL。 避免数组或指针的下标越界，特别要当心发生“多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 下面程序的作用是，将两