指针与链表ppt课件.ppt
第10章 指针与链表,1,分 析,在各种信息管理系统的程序设计中，常常需要存储大量的数据记录。 如果使用结构体数组会带来哪些问题？,2,解决办法： 采用动态存储分配的数据结构链表,10.1 存储空间的分配与释放,C语言标准函数库stdlib.h中提供了四个函数，用于实现内存的动态分配和释放。 分别为：malloc(),calloc(),realloc()和free().1. malloc 函数,void *malloc (unsigned int size);,作用是: 在内存的动态存储区申请一个长度为size的连续空间，并返回存储空间的起始地址；如果没有足够的内存空间可分配，则返回空指针NULL.,3,用法：由于函数返回类型为void,因此如果要将函数返回的指针赋给其它类型的指针变量，应当进行强制类型转换。,例如： int *p=(int *)malloc(sizeof(int);struct stud *p=(struct stud *)malloc(sizeof(struct stud);,4,2.calloc函数,void *calloc(unsigned n,unsigned size);,作用是: 在内存的动态区分配n个长度为size的连续空间,并返回该存储空间的起始地址。 主要用于为动态数组申请存储空间。,例如：Int *p=(int *）calloc(10,sizeof(int);,5,3. free函数,void free(void *p);,作用是: 释放指针变量p指向的存储空间.,注意：p只能是程序中此前最后一次调用malloc或calloc函数所返回的地址。,例如：int *p,*q=(int *)calloc(10,sizeof(int); p=q; q+; free(p);,6,10.2 链式存储结构链表,链表可以动态的进行存储分配，每一个元素称为一个“结点”,每个结点都包括两部分:,head: 头指针,存放一个地址,指向链表中的第一个结点.,1.数据域：存储用户需要的实际数据;,2.指针域：指向下一个结点的地址.,表尾: 它的地址部分放一个“NULL”,链表到此结束.,7,10.3 单链表,每个结点只含有一个指针，所有结点单向联系，每个结点的指针都指向下一个结点，形成一条线性链。,带头结点的单向链表：,在单向链表的第一个结点前虚加一个“头结点”，头指针head指向头结点，头结点的指针域指向第一个结点，头结点的数据域不使用。,8,可用结构体类型的变量来存储链表中的结点元素.,每一个结点中存放地址的部分可用指针来实现.,例: struct student int num; float score; struct 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=,9901,89.5,9903,90,9905,85,&a,&b,&c,NULL,&a,&b,&c,NULL,10,建立动态链表,#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,*pEnd,*pNew; n=0; pEnd=pNew=(struct student *)malloc (LEN); scanf(“%ld,%f”,11,链表的插入操作,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 ,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 ,13,作业：P237 10.1，10.2,14,
