c語(yǔ)言課件第8.3章

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

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

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

4、oc或calloc等)時(shí)返回的指針,例8-10動(dòng)態(tài)分配一塊區(qū)域，存儲(chǔ)一個(gè)學(xué)生數(shù)據(jù)，并輸出該學(xué)生數(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);},,運(yùn)行結(jié)果如圖8-22所示。,8.6鏈表,8.6.1鏈表的概念問(wèn)題：結(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("僅用來(lái)測(cè)試！");},其編譯結(jié)果如圖8-23。,說(shuō)明,錯(cuò)誤提示的意思為：用正在定義的student聲明成員變量stu1有錯(cuò)誤。這樣，可以得到結(jié)論：結(jié)構(gòu)體內(nèi)的成員不可以用“自己”去定義。,struct student{int nNum;char cName[20];int nScoreAvg;struct student * sStu;};,數(shù)據(jù)域,,指針域,

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

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

11、有通過(guò)前一個(gè)節(jié)點(diǎn)才能找到下一個(gè)節(jié)點(diǎn).在 C中，每個(gè)節(jié)點(diǎn)都可以用 struct 來(lái)表示：typedef struct node_s{char current[3];int volts;struct node_s *linkp;}node_t;,創(chuàng)建節(jié)點(diǎn)(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é)點(diǎn)(2/2),AC\0,115,???,DC\0,12,???,連接兩個(gè)節(jié)點(diǎn),AC\0,115,???

13、,DC\0,12,???,n1_p->linkp = n2_p;“n2_p->volts” ＝ “n1_p-> linkp->volts”,第三個(gè)節(jié)點(diǎn),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é)點(diǎn)鏈表,通常最后一個(gè)節(jié)點(diǎn)指向 null.n2_p->linkp->linkp = NULL;n1_p 是頭節(jié)點(diǎn),???,p= n1_p;,printf(“%d,%f \n”, (*p). current, (*p).volt);,node_t *p;,動(dòng)態(tài)鏈表的輸出,在鏈表中插入節(jié)點(diǎn),讓新節(jié)點(diǎn)指向最后一個(gè)節(jié)點(diǎn)讓第二個(gè)節(jié)點(diǎn)指向新節(jié)點(diǎn),curr

15、ent,volts,linkp,DC\0,12,current,volts,linkp,AC\0,220,NULL,,練習(xí),若有以下定義:,struct link { int data; struct link *next; } a,b,c,*p,*q;,a,b,c,能將節(jié)點(diǎn)C 插入到上述鏈表結(jié)構(gòu)中的 a與 b之間,以形成新的鏈表結(jié)構(gòu)的語(yǔ)句組是:,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;,練習(xí),若已建立下面的鏈表結(jié)構(gòu)，指針 p、s 分別指向 圖中所示的節(jié)點(diǎn)，則不能將 s所指的節(jié)點(diǎn)插入到鏈表 末尾的語(yǔ)句組是：,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編寫一個(gè)search()函數(shù)，按照規(guī)定的學(xué)生結(jié)點(diǎn)結(jié)構(gòu)，實(shí)現(xiàn)按學(xué)號(hào)查找。,,3. 插入鏈表,向鏈表中插入結(jié)點(diǎn)分為3種情況。（1）在鏈表最前端插入，如圖8-31所示。插入前到插入后的變化通過(guò)如下代碼來(lái)實(shí)現(xiàn)。（2）在鏈表中間插入，如圖8-32所示。根據(jù)鏈表的特性，中間插

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

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

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

23、之插入到原頭節(jié)點(diǎn)前面，使新節(jié)點(diǎn)變成頭節(jié)點(diǎn)，最后輸出num值為偶數(shù)的節(jié)點(diǎn)。,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);},練習(xí)輸入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-