指针与链表教程文件

第10章指针(zhǐzhēn)与链表1第一页，共14页。分析在各种(ɡèzhǒnɡ)信息管理系统的程序设计中，常常需要存储大量的数据记录。如果使用结构体数组会带来哪些问题？2解决办法：采用(cǎiyòng)动态存储分配的数据结构——链表第二页，共14页。10.1存储空间的分配(fēnpèi)与释放C语言标准函数库stdlib.h中提供了四个函数，用于实现内存(nèicún)的动态分配和释放。分别为：malloc(),calloc(),realloc()和free().1.malloc函数void*malloc(unsignedintsize);作用是:在内存的动态存储区申请一个长度为size的连续空间，并返回存储空间的起始地址；如果(rúguǒ)没有足够的内存空间可分配，则返回空指针NULL.3第三页，共14页。用法：由于(yóuyú)函数返回类型为void,因此如果要将函数返回的指针赋给其它类型的指针变量，应当进行强制类型转换。例如(lìrú)：int*p=(int*)malloc(sizeof(int));structstud*p=(structstud*)malloc(sizeof(structstud));4第四页，共14页。2.calloc函数(hánshù)

void*calloc(unsignedn,unsignedsize);作用是:在内存的动态区分配n个长度为size的连续空间,并返回该存储空间的起始地址。主要(zhǔyào)用于为动态数组申请存储空间。例如(lìrú)：Int*p=(int*）calloc(10,sizeof(int));5第五页，共14页。3.free函数(hánshù)voidfree(void*p);作用是:释放指针(zhǐzhēn)变量p指向的存储空间.注意：p只能是程序中此前最后一次调用malloc或calloc函数所返回(fǎnhuí)的地址。例如：int*p,*q=(int*)calloc(10,sizeof(int));p=q;q++;free(p);6第六页，共14页。10.2链式存储(cúnchǔ)结构——链表链表可以动态的进行存储分配，每一个元素(yuánsù)称为一个“结点”,每个结点都包括两部分:1249head1249A13561356B14751475C10211021DNULLhead:头指针,存放一个地址(dìzhǐ),指向链表中的第一个结点.1.数据域：存储用户需要的实际数据;2.指针域：指向下一个结点的地址.表尾:它的地址部分放一个“NULL”,链表到此结束.7第七页，共14页。10.3单链表每个结点只含有(hányǒu)一个指针，所有结点单向联系，每个结点的指针都指向下一个结点，形成一条线性链。带头结点(jiédiǎn)的单向链表：在单向链表的第一个(yīɡè)结点前虚加一个(yīɡè)“头结点”，头指针head指向头结点，头结点的指针域指向第一个(yīɡè)结点，头结点的数据域不使用。8第八页，共14页。可用结构(jiégòu)体类型的变量来存储链表中的结点元素.1249head1249A13561356B14751475C10211021DNULL每一个结点(jiédiǎn)中存放地址的部分可用指针来实现.例:structstudent{intnum;floatscore;

structstudent*next;}1、建立(jiànlì)和输出链表9第九页，共14页。简单(jiǎndān)静态链表#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第十页，共14页。建立(jiànlì)动态链表#defineNULL0#defineLENsizeof(structstudent)structstudent{longnum;floatscore;structstudent*next;};intn;动态(dòngtà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第十一页，共14页。链表的插入(chārù)操作3、单链表的插入(chārù)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第十二页，共14页。链表的删除(shānchú)操作4、单链表的删除(shānchú)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->next=