资源描述
,13,C,语言电子教案（十八）,第十八讲 第十一章 结构体和共用体,主要内容：,11.7,用结构体指针处理链表,链表概述,动态存储函数,链表的建立,链表的输出,一、链表概述,如果我们使用数组来存放一组数据,必须定义数组的大小。在无法确定数组大小的情况下，就必须将数组定义得足够大，以能适应不同的需要，这将造成系统资源(内存资源)浪费。,使用一种新的数据结构-,链表,，就能克服上述缺点,它将根据需要开辟内存单元，因为链表结构是动态地分配存储，即在需要时才开辟一个结点的存储单元，因而就可以解决内存资源和用户需求之间的矛盾。,链表,:链表是一种新的数据结构,系统对链表的元素是动态地进行存储分配。,结点,:链表中的每一个元素称为结点（又称为域）。,链表的,基本构成,：表头、一个或多个结点（域）、表尾。,表头,: 链表有一个头指针变量,其中存放一个地址,该地址指向链表中的第一个元素(即第一个结点),结点,: 链表中的每一个元素叫作一个结点（又叫域），结点都是结构体类型，每个结点包括若干个实际数据和一个指向本结构体的指针变量（称为指针域）,指针域用来指明下一个结点的地址。,表尾,:链表最后一个结点中的指针域中存放一个空地址(用“,NULL”,来表示),以表示链表的结束。,一、链表概述,一、链表概述（四个结点的链表构成）,2480,头指针,3420,结点1,2600,结点2,NULL,2800,结点3,2000,第四结点,（链尾）,2480,3420,2600,2800,头指针的指针域,存放第一结点地址,第一结点的指针域,存放第二结点地址,第二结点的指针域,存放第三结点地址,第三结点的指针域,存放第四结点地址,链尾的指针域存放空地址,指针域,结点起始地址,二、有关链表的函数,1.,malloc,(),函数 (开辟一个动态存储区函数),调用格式:,malloc,(size),功能: 在内存的动态存储区中分配一个长度为,size,的连续空间,返回值: 空类型指针,其值为该连续存储单元的起始地址,若出错返回0,说明:,size,是一个整型表达式,二、有关链表的函数,2.,malloc,(),函数 (开辟多个动态存储区函数),调用格式:,calloc,(n,size),功能: 在内存的动态存储区中分配,n,个长度为,size,的连续空间,返回值: 空类型指针,其值为该连续存储单元的起始地址,若出错返回0,说明:,size,是一个整型表达式,二、有关链表的函数,3.,free(),函数 (释放动态存储区函数),调用格式:,free(,ptr,),功能: 在内存释放,ptr,所指向的内存区,返回值: 无,说明:,ptr,是,最近一次调用,calloc,(),或,malloc,(),函数时返回的函数值,三、简单的建立单向链表的方法,定义结构体指针变量,p1,p2,headp1,指向新开辟的存储单元,p2,指向链表中最后一个结点,head,指向头结点定义整型变量,n,计,结点个数,n=n+1,Y,N,结点连接（,p1 p2-next）,p2,下移,（,p1 p2）,开辟一个新结点并使,p1,指向它为新单元的数据域输入学号和成绩,p1-num!,=0,n=1;,开辟一个新结点并使,p1,p2,head,指向该结点为新结点数据域输入学号和成绩,三、简单的建立单向建立链表的程序,#,define NULL,0,#define LEN,sizeof,(,struct,student),struct,student long num;,int,score;,struct,student *next; ;,int,n=0;,struct,student *,creat,(),struct,student *p1,*p2, *head;,p1=(,struct,student *),malloc,(LEN);,head=p2=p1;,printf,(,请输入一个学生的学号和成绩:,n);,scanf,(%ld%d,p1-num,p1-score);,while (p1-num!=0),n=n+1; p2-next=p1;,p2=p1;,p1=(,struct,student *),malloc,(LEN);,printf,(,请输入一个学生的学号和成绩:,n);,scanf,(%ld%d,p1-num,p1-score); ,p2-next=NULL;,return(head); ,/*,creat,函数能返回一个指向链表头的指针 */,/*,新开辟一个单元并使,p1,p2,head,指向该单元 */,运行程序,/*,计数器加1，连接，,p2,下移 */,/*,新开辟一个单元并使,p1,指向该单元 */,四、完整的建立单向,链表的,方法,定义结构体指针变量,p1,p2,headp1,指向新开辟的存储单元，,p2,指向链表中最后一个结点,head,指向头结点，定义整型变量,n,计,结点个数,n=n+1,Y,N,p2,下移,（,p1 p2）,开辟一个新结点并使,p1,指向它为新单元的数据域输入学号和成绩,p1-num !,=0,开辟一个新结点并使,p1,p2,指向它,NULLhead，0 n,为新结点数据域输入学号和成绩,n=1,p1,head,作为首结点,结点连接（,p1 p2-next）,Y,N,四、完整的建立单向建立链表的程序,#,define NULL,0,#define LEN,sizeof,(,struct,student),struct,student long num;,int,score;,struct,student *next; ;,int,n=0;,struct,student *,creat,(),struct,student *p1,*p2, *head=NULL;,p1=p2=(,struct,student *),malloc,(LEN);,printf,(,请输入一个学生的学号和成绩:,n);,scanf,(%ld%d,p1-num,p1-score);,while (p1-num!=0),n=n+1;,if(n=1) head=p1; else p2-next=p1;,p2=p1;,p1=(,struct,student *),malloc,(LEN);,printf,(,请输入一个学生的学号和成绩:,n);,scanf,(%ld%d,p1-num,p1-score); ,p2-next=NULL;,return(head); ,/*,creat,函数能返回一个指向链表头的指针 */,/*,新开辟一个单元并使,p1,p2,指向该单元 */,运行程序,/*,记下首结点的地址或连接两个结点 */,/*,新开辟一个单元并使,p1,指向该单元 */,/*,计数器加1*/,/*,p2,下移 */,/*,head,赋以空地址解决空链表问题 */,五、输出,链表的,方法,函数的形参,head,为链表的头结点地址,函数为空类型,Y,N,p !,=NULL,函数中定义一个结构体类型的指针变量,head p(,使,p,指向链表表头）,输出一个结点的数据,p,下移（,p-next p）,Y,N,head !,=NULL,结束,do-while,循环结构,五、输出链表的函数,void print(head),struct,student *head;,struct,student *p;,printf,(“,nNow,These %d records are : n”,n );,p=head;,if(head!=NULL),do,printf,(“%ld %5.1fn”,p-num,p-score);,p=p-next;,while(p!=NULL);,/*,p,指向链表表头 */,运行程序,/*,输出当前结点的数据,*/,/*,条件成立，说明链表是一个非空链表 */,/*,p,下移 */,/* 形参,head,为链表头,结点的起始地址,*/,
展开阅读全文