数据结构第二部分-预备知识PPT课件

-,1,第二部分预备知识,知识点：C语言相关内容递归存储分配方式,-,2,C语言相关内容,1、函数参数传递C语言提供了两种参数传递机制：值传递：将实参的值赋值给形参，函数对形参的改变不影响实参；地址传递：将实参的地址赋值给形参，形参和实参代表的是同一段内存空间，函数对形参的处理就是对实参的处理。,-,3,例1阅读下面的程序段，写出输出结果。#include/值传递voidchange1(intx,inty)x+=10;y-=5;/地址传递voidchange2(int*p,int*q)*p=*p+10;*q=*q-5;,voidmain()inta,b;printf(“Inputtwovalues:n”);scanf(“%d,%d”,printf格式：printf(格式串,表达式1,表达式n)；scanf格式：scanf(格式串,变量1,变量n)；格式串形式：“%+字符”，其中%d表示整形数据；“%c”表示字符数据；“%s”表示字符串数据；“n”表示换行预处理文件：#include,-,4,例2阅读下面的程序段，写出输出结果。voidchange3(intA)/地址传递A0=A0+10;A1=A1-5;voidmain()intB2;printf(“pleaseinputtwovalues:n”);scanf(“%d,%d”,结论：数组作为函数参数传递时实际传递的是数组在内存中的首地址，函数的形参数组不再分配内存空间，它共享实参数组的内存空间。,-,5,注意：以一维数组作函数的形参时，一般为不带大小的一维数组，如果需要数组元素个数信息，则另设一个整数类型形参来表示数组的大小；以二维数组为函数的形参时，一般不带数组行数，但其列数一定要注明，行数用一个整数类型形参来表示。,-,6,2、函数结果返回函数名最多能带回一个处理结果，但是实际应用中往往需要将被调函数的多个处理结果返回，此时就需要借助于地址传递了。,-,7,3、结构体类型结构类型用于表示由固定个数的多种类型元素所构成的复合数据，它是一种用户自定义类型。结构类型定义格式：struct;例如：structStudentintno;charname20;,-,8,结构类型变量的定义格式有以下几种：（1）struct;例如：structStudentst;（2）struct;例如：structStudentintno;charname20;st;（3）struct;例如：structintno;charname20;st;,-,9,结构成员的访问形式：.每个成员都可以看作是一个独立的变量，可以参与运算，例如：voidf(Studentst)st.no=1;strcpy(,“shenhua”);,-,10,4、指针指针是内存地址的抽象表示，一个指针代表了一个内存地址。指针类型的定义格式：typedef*;例如：typedefint*Pointer;指针变量的定义格式：形式一：;形式二：*;例如：Pointerp;int*q;/指针变量p，q均为指向int类型数据的指针变量。,-,11,对指针变量所指数据的间接访问：情况一：可以通过“*”来访问一个指针变量指向的变量。例如：intx=7;int*p;p=输出结果为：st.no=7,=“shenhua”,-,12,递归,递归（Recursive）：是指程序或函数重复调用自己，并传入不同的变量来执行的一种程序设计技巧。,例如：n!=1*2*3*4*(n-1)*nn!递归定义n!=1当n=0,1时n!=n(n-1)!当n1时,用(n-1)!定义n!,-,13,将程序或函数直接调用自己的递归称为直接递归，如图(a)所示；将程序或函数通过调用其他程序或函数而间接调用了自己的递归称为间接递归，如图(b)所示。,-,14,递归必须包括两部分：）递归条件：能够将一般问题简化成一个或多个规模较小的相同性质的问题。）终止条件：即对无需递归的最小问题的处理方法；n！的递归算法：intfact(intn)intf;if(n=0|n=1)f=1;elsef=n*fact(n-1);returnf;,-,15,例3：编写求解Hanci塔问题的递归算法：有三个各为X，Y，Z的塔座，在X项有n个大小不同，依小到大编号为1，2n的圆盘。现要求将X上的n个圆盘移至Z上，并仍以同样顺序叠放，圆盘移动时必须遵守下列原则：1）每次移动一个盘子；2）圆盘可以放在X，Y，Z中的任一塔座上；3）任何时刻都不能将较大的圆盘压放在较小圆盘之上。,-,16,例如：n=3时圆盘移动的过程如下图所示：,Y,X,Z,-,17,首先给出求解Hanci塔问题的递归描述（定义）基本项：n=1时，将n号圆盘从X移至Z；递归项：n1时，将X上1n-1号圆盘从X移至Y；将X上的n号圆盘从X移至Z;将Y上1n-1号圆盘从Y移至Z;,将规模为n的问题的求解归结为规模为n-1的问题的求解,-,18,递归算法：voidhanoi(intn,charx,chary,charz)/将塔座x上按直径由小到大且自上而下编号为1至n的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。搬动操作move(x,n,z)可定义为将编号为n的圆盘从x塔座移到z塔座if(n=1)move(x,1,z);/将编号为1的圆盘从x移动zelsehanoi(n-1,x,z,y);/将x上编号为1至n-1的圆盘移到y,z作辅助塔move(x,n,z);/将编号为n的圆盘从x移到zhanoi(n-1,y,x,z)；/将y上编号为1至n-1的圆盘移到z，x作辅助塔,-,19,存储分配方式,对程序实体的内存分配可以采用三种存储分配方式：静态分配方式、自动分配方式和动态分配方式。这三种方式的主要区别在于内存分配的时机和占用时间。静态分配方式（staticmemoryallocation）：是指在程序运行前由编译器在编译时进行的内存分配，且直到整个程序运行结束才将这些内存空间释放给系统。如对全局变量、static局部变量和符号常量用此。,-,20,自动存储分配（automaticmemoryallocation）：是指程序执行到子程序时才对子程序的形式参数和局部变量进行内存分配，子程序执行结束时这些内存空间将自动被收回（对应于栈区）。动态存储分配（dynamicmemoryallocation）：是指在程序运行过程中，根据用户的需求随时为某程序实体分配所需要的内存空间，当不需要时可随时释放所占用的内存空间（对应于堆区）。,-,21,C语言为了支持动态存储分配提供如下标准库函数，在使用这些函数进行动态存储分配之前，需要在程序的最开始增加预处理命令#include1.free()函数函数原形：voidfree(void*ptr);功能说明：释放由ptr指示的存储块；参数说明：ptr为指向被释放存储块的指针。例如：free(st);/释放st指向的存储区等价于deletea；,-,22,2malloc()函数函数原形：void*malloc(site_tsize);功能说明：从堆空间中分配大小为size个字节的内存空间给本函数的调用者；参数说明：size指出要求分配的内存空间大小（以字节为单位）；返回值说明：如分配成功，返回存储块的首地址，否则返回空指针(NULL)。例如：int*a=(int*)malloc(n*sizeof(int)/a指针指向一个长度为n个int大小的堆空间等价于int*a=newintn;,-,23,3.calloc()函数函数原形：void*calloc(size_tnum,size_tsize);功能说明：从堆空间中分配numsize字节的内存空间；参数说明：size为所要分配内存单元的对象大小（所占字节数），num为所要分配内存单元的对象数；返回值说明：如分配成功，则返回存储块的首地址，否则返回空指针（NULL）。例如：int*a=(int*)calloc(n,sizeof(int)/a指针指向一个长度为n个int大小的堆空间等价于int*a=newintn;,-,24,4.realloc()函数函数原形：void*realloc(void*ptr,site_tsize)功能说明：该函数用于为某（些）对象重新分配存储单元，它将指定对象原来所占据的由ptr指针所指向的存储单元的大小改为size参数所指定的大小；参数说明：ptr指向为某对象原来分配的内存块的首地址，size指出该对象所要占据的存储块的新的大小（字节数）；返回值