#第二部分 預備知識部分(第3章)

湖北工業(yè)大學計算機學院沈華1第二部分預備知識部分本部分主要回顧幾個知識點：C語言中的相關內容遞歸存儲分配方式湖北工業(yè)大學計算機學院沈華2第三章C語言、遞歸及存儲分配方式

C語言中的函數參數傳遞C語言中的函數結果返回

C語言中的結構體類型

C語言中的指針什么是遞歸？有幾種遞歸方式？有哪幾種存儲分配方式？C語言中有哪些庫函數支持動態(tài)存儲分配方式？湖北工業(yè)大學計算機學院沈華3C語言中的函數參數傳遞C語言提供了兩種參數傳遞機制：值傳遞將實參的值賦值給形參，函數對形參的改變不影響實參；地址傳遞將實參的地址賦值給形參，形參和實參代表的是同一段內存空間，函數對形參的處理就是對實參的處理。湖北工業(yè)大學計算機學院沈華4算法的描述和分析例3.1閱讀下面的程序段，寫出輸出結果。#include<stdio.h>//值傳遞voidchange1(intx,inty){

x+=10;

y-=5;}

//地址傳遞voidchange2(int*p,int*q){*p=*p+10; *q=*q-5;}voidmain(){inta,b;printf(“pleaseinputtwovalues:\n”);scanf(“%d,%d”,&a,&b);change1(a,b);printf(“theresultaftercallchange1procedure:a=%d,b=%d\n”,a,b);change2(&a,&b);printf(“theresultaftercallchange2procedure:a=%d,b=%d\n”,a,b);}湖北工業(yè)大學計算機學院沈華5C語言為了提高數組傳遞的效率，數組作為函數參數傳遞時實際傳遞的是數組在內存中的首地址，函數的形參數組不再分配內存空間，它共享實參數組的內存空間。函數中對形參數組的處理實際上就是對實參數組的處理，因此能改變實參數組的值。C語言中的函數參數傳遞湖北工業(yè)大學計算機學院沈華6算法的描述和分析例3.2閱讀下面的程序段，寫出輸出結果。voidchange3(intA[])//地址傳遞{

A[0]=A[0]+10; A[1]=A[1]-5;}intmain(){intB[2];printf(“pleaseinputtwovalues:\n”);scanf(“%d,%d”,&B[0],&B[1]);change3(B);printf(“theresultaftercallchange3procedure:B[0]=%d,B[1]=%d\n”,B[0],B[1]);}湖北工業(yè)大學計算機學院沈華7需要補充說明的是，以一維數組作函數的形參時，一般為不帶大小的一維數組，如果需要數組元素個數信息，則另設一個整數類型形參來表示數組的大?。灰远S數組為函數的形參時，一般不帶數組行數，但其列數一定要注明，行數用一個整數類型形參來表示。C語言中的函數參數傳遞湖北工業(yè)大學計算機學院沈華8因為地址傳遞這種參數傳遞方式可以使函數對形參的操作直接影響到對應的實參，因此我們可以通過這種參數傳遞方式將被調函數的處理結果返回到調用函數中。當然，函數名也能帶回一個處理結果，但是實際應用中往往需要將被調函數的多個處理結果返回，此時就需要借助于地址傳遞了。C語言中的函數結果返回湖北工業(yè)大學計算機學院沈華9C語言中的結構體類型結構類型用于表示由固定個數的多種類型元素所構成的復合數據，它是一種用戶自定義類型。結構類型定義格式：struct<結構類型名>{<成員表>};湖北工業(yè)大學計算機學院沈華10例如：下面定義了一個Student類型。該包括兩個成員，一個是表示學號的no，另一個是記錄學生姓名的字符數組name。structStudent{ intno; charname[20];};湖北工業(yè)大學計算機學院沈華11結構類型變量的定義格式有以下幾種：（1）struct<結構類型名><結構類型變量名>;

例如：structStudentst;（2）struct<結構類型名>{<成員表>}<結構類型變量名>;

例如：structStudent{ intno; charname[20];}st;湖北工業(yè)大學計算機學院沈華12（3）struct{<成員表>}<結構類型變量名>;

例如：struct{ intno; charname[20];}st;湖北工業(yè)大學計算機學院沈華13算法的描述和分析結構成員的訪問要通過結構變量名來“限制”，其訪問形式為：

<結構類型變量>.<結構成員名>每個成員都可以看作是一個獨立的變量，可以參與運算，例如：voidf(Studentst){st.no=1;strcpy(,“shenhua”); }湖北工業(yè)大學計算機學院沈華14C語言中的指針在C語言中，用指針類型來描述內存地址，可以說指針是內存地址的抽象表示，一個指針代表了一個內存地址。指針類型的定義格式：typedef<類型>*<指針類型名>;湖北工業(yè)大學計算機學院沈華15C語言中的指針指針變量的定義格式：形式一：<指針類型名><指針變量名>;形式二：<類型>*<指針變量名>;例如：Pointerp;int*q;指針變量p，q均為指向int類型數據的指針變量。湖北工業(yè)大學計算機學院沈華16C語言中的指針對指針變量所指數據的間接訪問：情況一：可以通過“*”來訪問一個指針變量指向的變量。例如：

intx=7;int*p;p=&x;(*p)++;printf(“x=%d\n”,x);輸出結果為：x=8湖北工業(yè)大學計算機學院沈華17C語言中的指針對指針變量所指數據的間接訪問：情況二：可以通過“*”和“.”或“->”來訪問一個指針變量所指結構變量的成員。例如：Studentst={7,“shenhua”};Student*p=&st;printf(“st.no=%d,=%s\n”,(*p).no,p->name);輸出結果為：st.no=7,=shenhua湖北工業(yè)大學計算機學院沈華18遞歸遞歸（Recursive）是指程序或函數重復調用自己，并傳入不同的變量來執(zhí)行的一種程序設計技巧。湖北工業(yè)大學計算機學院沈華19將程序或函數直接調用自己的遞歸稱為直接遞歸，如圖4.1(a)所示；將程序或函數通過調用其他程序或函數而間接調用了自己的遞歸稱為間接遞歸，如圖4.1(b)所示。湖北工業(yè)大學計算機學院沈華20遞歸遞歸必須包括兩個條件：遞歸條件和終止條件。遞歸條件隨著遞歸的進行將會不斷接近終止條件（即問題規(guī)模不斷縮小的過程），并最終達到終止條件（即問題已足夠基本了）。通過在終止條件下對基本問題的求解來解決逐漸復雜的問題，最終得到原問題的解。湖北工業(yè)大學計算機學院沈華21例如求Fibonacci數列的第n個Fibonacci數。該數列的遞歸定義如右：n>2即為遞歸條件，而n=1和n=2是終止條件。當n>2時，經過一次遞歸，將求解fibs(n)的問題轉換為了求解fibs(n-1)和fibs(n-2)；經過足夠多次的遞歸，n一定會減小到1或2到達終止條件，此時可直接求得fibs(1)=1或fibs(2)=1；最內層遞歸的返回將求得fibs(3)，倒數第二層遞歸的返回將求得fibs(4)，依次類推最終得到原問題的解fibs(n)。遞歸實質上是一種“分而自治”（divideandconquer）的思想。湖北工業(yè)大學計算機學院沈華22存儲分配方式對程序實體的內存分配可以采用三種存儲分配方式：靜態(tài)分配方式、自動分配方式和動態(tài)分配方式。這三種方式的主要區(qū)別在于內存分配的時機和占用時間。湖北工業(yè)大學計算機學院沈華23存儲分配方式靜態(tài)分配方式（staticmemoryallocation）是指在程序運行前由編譯器在編譯時進行的內存分配，且直到整個程序運行結束才將這些內存空間釋放給系統(tǒng)。湖北工業(yè)大學計算機學院沈華24存儲分配方式自動存儲分配（automaticmemoryallocation）是指程序執(zhí)行到子程序時才對子程序的形式參數和局部變量進行內存分配，子程序執(zhí)行結束時這些內存空間將自動被收回（對應于棧區(qū)）。湖北工業(yè)大學計算機學院沈華25存儲分配方式動態(tài)存儲分配（dynamicmemoryallocation）是指在程序運行過程中，根據用戶的需求隨時為某程序實體分配所需要的內存空間，當不需要時可隨時釋放所占用的內存空間（對應于堆區(qū)）。湖北工業(yè)大學計算機學院沈華26存儲分配方式前兩種分配方式都有一個共同點：實體所需存儲空間的大小在程序運行前就已確定。但在實際應用過程中，我們發(fā)現很多情況下對于某些實體所需的空間大小只有在程序運行過程中根據具體的運行情況才能確定。此外，運行前確定存儲空間大小還會導致存儲空間浪費（如事先預估的空間過大）和使用不靈活等不足。動態(tài)存儲分配可以解決上述問題。湖北工業(yè)大學計算機學院沈華27C語言為了支持動態(tài)存儲分配都提供了如下標準庫函數：1.free()函數函數原形：voidfree(void*ptr);功能說明：釋放由ptr指示的存儲塊；參數說明：ptr為指向被釋放存儲塊的指針。湖北工業(yè)大學計算機學院沈華282．malloc()函數函數原形：void*malloc(site_tsize);功能說明：從堆空間中分配大小為size個字節(jié)的內存空間給本函數的調用者；參數說明：size指出要求分配的內存空間大小（以字節(jié)為單位）；返回值說明：如分配成功，返回存儲塊的首地址，否則返回空指針(NULL)。湖北工業(yè)大學計算機學院沈華293.calloc()函數函數原形：void*calloc(size_tnmemb,size_tsize);功能說明：從堆空間中分配num×size字節(jié)的內存空間；參數說明：size為所要分配內存單元的對象大?。ㄋ甲止?jié)數），nmemb為所要分配內存單元的對象數；返回值說明：如分配成功，則返回存儲塊的首地址，否則返回空指針（NULL）。湖北工業(yè)大學計算機學院沈華304.realloc()函數函數原形：void*realloc(void*ptr,site_tsize)功能說明：該函數用于為某（些）對象重新分配存儲單元，它將指定對象原來所占據的由ptr指針所指向的存儲單元的大小改為size參數所指定的大?。粎嫡f明：ptr指向為某對象原來分配的內存塊的首地址，size指出該對象所要占據的存儲塊的新的大小（字節(jié)數）；返回值說明：如分配成功，返回新存儲塊的首地址，否則返回空指針（NU