指針與鏈表課件

第10章指針與鏈表1第10章指針與鏈表1分析在各種信息管理系統(tǒng)的程序設(shè)計中，常常需要存儲大量的數(shù)據(jù)記錄。

如果使用結(jié)構(gòu)體數(shù)組會帶來哪些問題？2解決辦法：

采用動態(tài)存儲分配的數(shù)據(jù)結(jié)構(gòu)——鏈表分析在各種信息管理系統(tǒng)的程序設(shè)計中，常常需要存儲大10.1存儲空間的分配與釋放

C語言標(biāo)準(zhǔn)函數(shù)庫stdlib.h中提供了四個函數(shù)，用于實現(xiàn)內(nèi)存的動態(tài)分配和釋放。分別為：malloc(),calloc(),realloc()和free().1.malloc函數(shù)void*malloc(unsignedintsize);作用是:在內(nèi)存的動態(tài)存儲區(qū)申請一個長度為size的連續(xù)空間，并返回存儲空間的起始地址；如果沒有足夠的內(nèi)存空間可分配，則返回空指針NULL.310.1存儲空間的分配與釋放C語言標(biāo)準(zhǔn)函數(shù)庫s用法：由于函數(shù)返回類型為void,因此如果要將函數(shù)返回的指針賦給其它類型的指針變量，應(yīng)當(dāng)進(jìn)行強制類型轉(zhuǎn)換。

例如：int*p=(int*)malloc(sizeof(int));structstud*p=(structstud*)malloc(sizeof(structstud));4用法：由于函數(shù)返回類型為void,因此如果要將函數(shù)返回的指針2.calloc函數(shù)

void*calloc(unsignedn,unsignedsize);作用是:在內(nèi)存的動態(tài)區(qū)分配n個長度為size的連續(xù)空間,并返回該存儲空間的起始地址。主要用于為動態(tài)數(shù)組申請存儲空間。例如：Int*p=(int*）calloc(10,sizeof(int));52.calloc函數(shù)void*calloc(unsign3.free函數(shù)voidfree(void*p);作用是:釋放指針變量p指向的存儲空間.注意：p只能是程序中此前最后一次調(diào)用malloc或calloc函數(shù)所返回的地址。例如：int*p,*q=(int*)calloc(10,sizeof(int));p=q;q++;free(p);63.free函數(shù)voidfree(void*p);作10.2鏈?zhǔn)酱鎯Y(jié)構(gòu)——鏈表鏈表可以動態(tài)的進(jìn)行存儲分配，每一個元素稱為一個“結(jié)點”,每個結(jié)點都包括兩部分:1249head1249A13561356B14751475C10211021DNULLhead:

頭指針,存放一個地址,指向鏈表中的第一個結(jié)點.1.數(shù)據(jù)域：存儲用戶需要的實際數(shù)據(jù);2.指針域：指向下一個結(jié)點的地址.表尾:它的地址部分放一個“NULL”,鏈表到此結(jié)束.710.2鏈?zhǔn)酱鎯Y(jié)構(gòu)——鏈表鏈表可以動態(tài)的進(jìn)行存儲10.3單鏈表每個結(jié)點只含有一個指針，所有結(jié)點單向聯(lián)系，每個結(jié)點的指針都指向下一個結(jié)點，形成一條線性鏈。帶頭結(jié)點的單向鏈表：在單向鏈表的第一個結(jié)點前虛加一個“頭結(jié)點”，頭指針head指向頭結(jié)點，頭結(jié)點的指針域指向第一個結(jié)點，頭結(jié)點的數(shù)據(jù)域不使用。810.3單鏈表每個結(jié)點只含有一個指針，所有可用結(jié)構(gòu)體類型的變量來存儲鏈表中的結(jié)點元素.1249head1249A13561356B14751475C10211021DNULL每一個結(jié)點中存放地址的部分可用指針來實現(xiàn).例:structstudent{intnum;floatscore;

structstudent*next;}1、建立和輸出鏈表9可用結(jié)構(gòu)體類型的變量來存儲鏈表中的結(jié)點元素.1249h簡單靜態(tài)鏈表#defineNULL0structstudent{longnum;floatscore;structstudent*next;};main(){structstudenta,b,c,*head,*p;a.num=9901;a.score=89.5;b.num=9903;b.score=90;c.num=9905;c.score=85;

head=&a;a.next=&b;b.next=&c;c.next=NULL;p=head;do{printf(“%ld%5.2f\n”,p->num,p->score);

p=p->next;}while(p!=NULL);}anumscorenextbcheadp990189.5990390990585&a&b&cNULL&a&b&cNULL10簡單靜態(tài)鏈表#defineNULL0anumscore建立動態(tài)鏈表#defineNULL0#defineLENsizeof(structstudent)structstudent{longnum;floatscore;structstudent*next;};intn;動態(tài)建立鏈表structstudent*creat(void){structstudent*head,*pEnd,*pNew;n=0;pEnd=pNew=(structstudent*)malloc(LEN);scanf(“%ld,%f”,&pNew->num,&pNew->score);head=NULL;while(pNew->num!=0){n=n+1;if(n==1)head=pNew;elsepEnd->next=pNew;pEnd=pNew;pNew=(structstudent*)malloc(LEN);scanf(“%ld,%f”,&pNew->num,&pNew->score);}pEnd->next=NULL;return(head);}11建立動態(tài)鏈表#defineNULL0動態(tài)建立鏈表11鏈表的插入操作3、單鏈表的插入structstudent*insert(structstudent*head,structstudent*stud){structstudent*p1,*p2;p1=head;if(head==NULL){head=stud;stud->next=NULL;}else{while(p1->num>stud->num&&p1->next!=NULL)){p2=p1;p1=p1->next;}if(p1->next!=NULL){if(head==p1)head=stud;elsep2->next=stud;stud->next=p1;}else{p1->next=stud;stud->next=NULL;}}n=n+1;return(head);}12鏈表的插入操作3、單鏈表的插入12鏈表的刪除操作4、單鏈表的刪除structstudent*del(structstudent*head,longnum){structstudent*p1,*p2;

if(head==NULL)

{printf(“\nlistnull!\n”);exit(0);}p1=head;while(num!=p1->num&&p1->next!=NULL){p2=p1;p1=p1->next;}

if(num==p1->num){if(p1==head)head=p1->next;elsep2->