《指针与链表ppt课件》由会员分享，可在线阅读，更多相关《指针与链表ppt课件（14页珍藏版）》请在金锄头文库上搜索。
1、第第1010章章 指针与链表指针与链表1分分 析析 在各种信息管理系统的程序设计中，常常需要在各种信息管理系统的程序设计中，常常需要存储大量的数据记录。存储大量的数据记录。 如果使用如果使用结构体数组结构体数组会带来哪些问题？会带来哪些问题？2 解决办法：解决办法： 采用动态存储分配的数据结构采用动态存储分配的数据结构链表链表10.1 存储空间的分配与释放存储空间的分配与释放 C语言标准函数库语言标准函数库stdlib.h中提供了四个函数，中提供了四个函数，用于实现内存的动态分配和释放。用于实现内存的动态分配和释放。 分别为：分别为：malloc(),calloc(),realloc()和和f
2、ree().1. malloc 函数函数void *malloc (unsigned int size);作用是作用是: 在内存的动态存储区申请一个长度为在内存的动态存储区申请一个长度为size的连的连续空间，并返回存储空间的起始地址；如果没有足够的续空间，并返回存储空间的起始地址；如果没有足够的内存空间可分配，则返回空指针内存空间可分配，则返回空指针NULL.3用法用法：由于函数返回类型为由于函数返回类型为void,因此如果要将函因此如果要将函数返回的指针赋给其它类型的指针变量，应当数返回的指针赋给其它类型的指针变量，应当进行强制类型转换。进行强制类型转换。 例如：例如： int *p=(i
3、nt *)malloc(sizeof(int);struct stud *p=(struct stud *)malloc(sizeof(struct stud);42.calloc函数函数 void *calloc(unsigned n,unsigned size);作用是作用是: 在内存的动态区分配在内存的动态区分配n个长度为个长度为size的连续空间的连续空间,并返回该存储空间的起始地址。并返回该存储空间的起始地址。 主要用于为动态数组申请存储空间。主要用于为动态数组申请存储空间。例如：例如：Int *p=(int *）calloc(10,sizeof(int);53. free函数函数v
4、oid free(void *p);作用是作用是: 释放指针变量释放指针变量p指向的存储空间指向的存储空间.注意注意：p只能是程序中此前最后一次调用只能是程序中此前最后一次调用malloc或或calloc函数所返回的地址。函数所返回的地址。例如：例如：int *p,*q=(int *)calloc(10,sizeof(int); p=q; q+; free(p);610.2 链式存储结构链式存储结构链表链表 链表可以动态的进行存储分配，每一个元素链表可以动态的进行存储分配，每一个元素称为一个称为一个“结点结点”,每个结点都包括两部分每个结点都包括两部分:1249head1249A1356135
5、6B14751475C10211021DNULLhead: 头指针头指针,存放一个地址存放一个地址,指向链表中的第一个结点指向链表中的第一个结点.1.数据域：存储用户需要的实际数据数据域：存储用户需要的实际数据;2.指针域：指向下一个结点的地址指针域：指向下一个结点的地址.表尾表尾: 它的地址部分放一个它的地址部分放一个“NULL”,链表到此结束链表到此结束.710.3 单链表单链表 每个结点只含有一个指针，所有结点每个结点只含有一个指针，所有结点单向联系，每个结点的指针都指向下一个单向联系，每个结点的指针都指向下一个结点，形成一条线性链。结点，形成一条线性链。带头结点的单向链表：带头结点的单
6、向链表： 在单向链表的第一个结点前虚加一个在单向链表的第一个结点前虚加一个“头结点头结点”，头指针，头指针head指向头结点，头结指向头结点，头结点的指针域指向第一个结点，头结点的数点的指针域指向第一个结点，头结点的数据域不使用。据域不使用。8 可用可用结构体类型结构体类型的变量的变量来存储链表来存储链表中的中的结点元素结点元素.1249head1249A13561356B14751475C10211021DNULL 每一个结点中存每一个结点中存放地址的部分可用放地址的部分可用指针指针来实现来实现.例例: struct student int num; float score; struct
7、student *next; 1、建立和输出链表、建立和输出链表9简单静态链表简单静态链表# define NULL 0struct student long num; float score; struct student *next; ;main( ) struct student a,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
8、 %5.2f n”,p-num,p-score); p=p-next; while(p!=NULL);anumscorenextbchead p990189.5990390990585&a&b&cNULL&a&b&cNULL10建立动态链表建立动态链表#define NULL 0#define LEN sizeof(struct student)struct studentlong num; float score; struct student *next;int n;动态建立链表动态建立链表struct student *creat(void)struct student *head,*p
9、End,*pNew; n=0; pEnd=pNew=(struct student *)malloc (LEN); scanf(“%ld,%f”,&pNew-num,&pNew-score); head=NULL; while(pNew-num!=0) n=n+1; if(n=1) head=pNew; else pEnd-next=pNew; pEnd=pNew; pNew=(struct student *)malloc(LEN); scanf(“%ld,%f”,&pNew-num,&pNew-score);pEnd-next=NULL;return(head);11链表的插入操作链表的插
10、入操作3、单链表的插入、单链表的插入struct student *insert(struct student *head, struct student *stud)struct student *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; else p2-next=stud; stud-next=p1; else
11、 p1-next=stud; stud-next=NULL; n=n+1; return(head); 12链表的删除操作链表的删除操作4、单链表的删除、单链表的删除struct student *del(struct student *head, long num) struct student *p1,*p2; if(head=NULL) printf(“nlist null!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; else p2-next=p1-next; printf(“delete:%ldn”,num); n=n-1; else printf(“%ld not been found!n”,num); return(head); 13作业：作业：P237 10.1，10.214
