c語言課件第8.3章

1、8.5動態(tài)存儲空間分配,動態(tài)存儲空間分配相對于靜態(tài)存儲空間分配具有如下特點：①不需要預先分配存儲空間；②分配的空間可以根據(jù)程序的需要擴大或縮小。C語言提供了若干動態(tài)存儲空間分配函數(shù)，常用的有：malloc函數(shù)、calloc函數(shù)和free函數(shù)。,,(1) malloc()函數(shù),,原 型：void *malloc(unsigned int size);頭文件：#include 參　數(shù)：size――參數(shù)是一個無符號整形數(shù)，表示分配

2、存儲空間的字節(jié)數(shù)功 能：在內(nèi)存的動態(tài)存儲區(qū)中分配一個長度為size的連續(xù)空間說 明：若成功，返回指向分配區(qū)域起始地址的指針(類型為void)；若失敗，返回空指針NULL,(2) calloc()函數(shù),void * calloc( unsigned n, unsigned size );頭文件：#include 參　數(shù)：size――表示分配存儲空間的字節(jié)數(shù)；n――有多少個size功 能：在內(nèi)存的動態(tài)區(qū)存儲中分配n個長度為s

3、ize的連續(xù)空間說 明：若成功，返回指向分配區(qū)域起始地址的指針(類型為void)；若失敗，返回空指針NULL,(3) free()函數(shù),原 型：void free(void *ptr);頭文件：#include 參　數(shù)：ptr欲釋放內(nèi)存單元的地址功 能：在完成對所分配內(nèi)存空間的使用之后，要通過調(diào)用free()函數(shù)來釋放它，釋放后的內(nèi)存區(qū)能夠重新分配給其他變量使用說 明：參數(shù)ptr必須是先前調(diào)用動態(tài)空間分配函數(shù)(mall

4、oc或calloc等)時返回的指針,例8-10動態(tài)分配一塊區(qū)域，存儲一個學生數(shù)據(jù)，并輸出該學生數(shù)據(jù)。,程序清單8-11　StructStu.c,#include "stdio.h"#include "stdlib.h"struct sStudent{int nNum;char *cName;char cSex;float fScore;} *psStu;vo

5、id main(void){ psStu = ( struct sStudent * ) malloc( sizeof ( struct sStudent ) );,程序清單8-11　StructStu.c,psStu->nNum=102; psStu->cName="Zhang ping"; psStu->cSex='M'; psStu->fSco

6、re=62.5; printf( "Number=%d\nName=%s\n", psStu->nNum,psStu->cName); printf("Sex=%c\nScore=%f\n",psStu->cSex,psStu->fScore);free(psStu);},,運行結(jié)果如圖8-22所示。,8.6鏈表,8.6.1鏈表的概念問題：結(jié)構(gòu)

7、體內(nèi)的成員類型可以是其本身嗎？ 程序清單8-12　StuTest.c,程序清單8-12　StuTest.c,#include "stdio.h"#include "stdlib.h"struct student{int nNum;char cName[20];int nScoreAvg;struct student sStu;};void main(){

8、 printf("僅用來測試！");},其編譯結(jié)果如圖8-23。,說明,錯誤提示的意思為：用正在定義的student聲明成員變量stu1有錯誤。這樣，可以得到結(jié)論：結(jié)構(gòu)體內(nèi)的成員不可以用“自己”去定義。,struct student{int nNum;char cName[20];int nScoreAvg;struct student * sStu;};,數(shù)據(jù)域,,指針域,

9、,再次進行編譯，發(fā)現(xiàn)錯誤沒有了，編譯通過了，程序可以運行了。這是什么原因呢？,這個奇妙的指針可以指向什么樣的內(nèi)存單元呢？,鏈表,(1)鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表各結(jié)點指針域進行鏈接的。鏈表由一系列結(jié)點組成，結(jié)點可以在運行時動態(tài)生成。,數(shù)據(jù)域和指針域,(2)鏈表中的每個結(jié)點通常由兩個域組成，一個稱為數(shù)據(jù)域data，另一個稱為指針域next。數(shù)據(jù)域用來存儲用戶的數(shù)據(jù)，而指針域是一個結(jié)構(gòu)類型

10、的指針，用來存儲下一個結(jié)點的地址。結(jié)點的結(jié)構(gòu)定義的一般形式為：struct node{數(shù)據(jù)類型 data;struct node * next;};,動態(tài)數(shù)據(jù)結(jié)構(gòu)-鏈表,動態(tài)數(shù)據(jù)結(jié)構(gòu)是在程序的執(zhí)行過程中可以擴大和縮小的數(shù)據(jù)結(jié)構(gòu)動態(tài)數(shù)據(jù)結(jié)構(gòu)的創(chuàng)建和操作都需要使用指針,Linked List,鏈表是指將若干個數(shù)據(jù)項按一定的原則連接起來的表。鏈表中每一個數(shù)據(jù)稱為節(jié)點。鏈表連接的原則是: 前一個節(jié)點指向下一個節(jié)點;而且只

11、有通過前一個節(jié)點才能找到下一個節(jié)點.在 C中，每個節(jié)點都可以用 struct 來表示：typedef struct node_s{char current[3];int volts;struct node_s *linkp;}node_t;,創(chuàng)建節(jié)點(1/2),node_t *n1_p, *n2_p, *n3_p;n1_p = (node_t * ) malloc(sizeof(node_t));st

12、rcpy(n1_p->current, “AC”);n1_p->volts = 115;n2_p = (node_t *) malloc (sizeof(node_t));strcpy(n2_p->current, “DC”);n2_p->volts = 12;n3_p = n2_p;,創(chuàng)建節(jié)點(2/2),AC\0,115,???,DC\0,12,???,連接兩個節(jié)點,AC\0,115,???

13、,DC\0,12,???,n1_p->linkp = n2_p;“n2_p->volts” ＝ “n1_p-> linkp->volts”,第三個節(jié)點,AC\0,115,???,DC\0,12,???,n3_p,n2_p->linkp = (node_t*)malloc(sizeof(node_t));strcpy(n2_p->linkp->current, “AC”);n2_p->

14、;linkp->volts = 220;,AC\0,220,???,三節(jié)點鏈表,通常最后一個節(jié)點指向 null.n2_p->linkp->linkp = NULL;n1_p 是頭節(jié)點,???,p= n1_p;,printf(“%d,%f \n”, (*p). current, (*p).volt);,node_t *p;,動態(tài)鏈表的輸出,在鏈表中插入節(jié)點,讓新節(jié)點指向最后一個節(jié)點讓第二個節(jié)點指向新節(jié)點,curr

15、ent,volts,linkp,DC\0,12,current,volts,linkp,AC\0,220,NULL,,練習,若有以下定義:,struct link { int data; struct link *next; } a,b,c,*p,*q;,a,b,c,能將節(jié)點C 插入到上述鏈表結(jié)構(gòu)中的 a與 b之間,以形成新的鏈表結(jié)構(gòu)的語句組是:,A) a.next = c; c.

16、next = b; B) p.next = q; q.next = p.next; C) p->next = &c; q -> next=p -> next; D) (*p).next = q; (*q).next = &b;,練習,若已建立下面的鏈表結(jié)構(gòu)，指針 p、s 分別指向 圖中所示的節(jié)點，則不能將 s所指的節(jié)點插入到鏈表 末尾的語句組是：,A)

17、s->next=NULL; p=p->next; p->next=s; B) p=p->next; s->next=p->next; p->next=s; C) p=p->next; s->next=p; p->next=s; D) p=(*p)

18、.next; (*s).next=(*p).next; (*p).next=s;,A)s->next = NULL; p = p->next p->next = s;,,Null,B)p = p->next;s->next = p->next; p->next = s;,NULL,,C)p = p->next;s->next = p; p->ne

19、xt = s;,,,D)p = (*p).next;(*s).next = (*p).next; (*p).next = s;,NULL,,2. 查找鏈表,例8-12編寫一個search()函數(shù)，按照規(guī)定的學生結(jié)點結(jié)構(gòu)，實現(xiàn)按學號查找。,,3. 插入鏈表,向鏈表中插入結(jié)點分為3種情況。（1）在鏈表最前端插入，如圖8-31所示。插入前到插入后的變化通過如下代碼來實現(xiàn)。（2）在鏈表中間插入，如圖8-32所示。根據(jù)鏈表的特性，中間插

20、入需要找到插入點。設p為找到的插入點，則下述語句可完成中間插入 。（3）在鏈表末尾插入，如圖8-33所示。與(2)相同，在找到指向鏈表的末尾結(jié)點的指針p后。通過如下代碼來實現(xiàn)。,4. 刪除鏈表,分為3種情況 (1) 在刪除鏈表的第一個結(jié)點。如圖8-36所示，刪除前到刪除后的變化通過如下代碼來實現(xiàn)。(2) 在刪除鏈表的某個中間結(jié)點。如圖8-37所示，刪除前到刪除后的變化通過如下代碼來實現(xiàn) 。(3) 在刪除鏈表的末尾結(jié)點。如圖8-3

21、8所示，刪除前到刪除后的變化通過如下代碼來實現(xiàn) 。,8.6.3帶頭結(jié)點鏈表簡介,頭結(jié)點是在鏈表的開始結(jié)點之前附加一個結(jié)點，如圖8-41所示。(1) 無論鏈表是否為空，其頭指針都是指向頭結(jié)點的非空指針（空表中頭結(jié)點的指針域空），因此空表和非空表的處理也就統(tǒng)一了。,8.6.3帶頭結(jié)點鏈表簡介,(2) 由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中,所以在鏈表的第一個位置上的操作就和在鏈表的其它位置上操作一致，無須進行特殊處理。針對空表和非

22、空表，圖8-43描述了單鏈表中插入新結(jié)點的情況。圖8-44描述了單鏈表中刪除結(jié)點的情況。,8.6.3帶頭結(jié)點鏈表簡介,struct line{ int num ; struct line *next;};# include # include #define LEN sizeof ( struct line ),例子: 請建立一個有9個節(jié)點的鏈表，要求鏈表節(jié)點的成員num的值依次分別為1-9的整數(shù)，每建立一個節(jié)點都將

23、之插入到原頭節(jié)點前面，使新節(jié)點變成頭節(jié)點，最后輸出num值為偶數(shù)的節(jié)點。,void main( ){ int k ; struct line *p , *head ; head=NULL; for(k=1; knum=k; p->next=head; head=p; } while( ( p=p->next) != NULL ) { printf(&quo

24、t;%d, ", p->num) ; p=p->next; }},根據(jù)以下定義, ______ 是正確的,struct node {char s[10];int k;} p[5];A．p.k=2B．p[0]->k=2 C．(p->s)[0]=‘a(chǎn)’D．p[0].s=“a”,#include #include struct link { i

25、nt mark; struct link * next;};void f(struct link **);main( ){ struct link * head, *p; head=(struct link *)malloc(sizeof(struct link)); head->mark = 0; head->next=NULL; f(&head);

26、 for (p=head; p!=NULL; p=p->next) printf("%d#", p->mark);},練習輸入55 92 63 69 -1后，程序的輸出結(jié)果,void f(struct link ** head) {int mark; struct link *p; scanf("%d", &mark);

27、 if ( markmark++; return ; } else { p=(struct link *)malloc(sizeof(struct link)); p->mark = mark; p->next = *head; *head = p; f(head); }},,0

28、,,,,,,,head,,70,輸入1 2 3 4 5 0后，寫出下列程序的輸出結(jié)果。 #define LEN sizeof(struct line) #define NULL 0 struct line{ int num ; struct line *next ; } main() { struct line *p1 , *p2 , *head ;

29、int j, k = 0; p1 = p2 = head = (struct line *) malloc (LEN) ; scanf("%d", &p1->num) ;,while (p1->num != 0){ p1 = (struct line *) malloc (LEN) ; scanf("%d",

30、&p1->num) ; if ( p1->num == 0 ) p2->next = NULL ; else { p2->next = p1 ; p2 = p1 ; } k++; } p2->next = head ; p1 = head-