C语言第十八讲 (2)

《C语言第十八讲 (2)》由会员分享，可在线阅读，更多相关《C语言第十八讲 (2)（13页珍藏版）》请在装配图网上搜索。

1、,,,,,,13,,,,,,,,C,语言电子教案（十八）,,第十八讲 第十一章 结构体和共用体,,主要内容：,,§11.7,,用结构体指针处理链表,,链表概述,,动态存储函数,,链表的建立,,链表的输出,一、链表概述,如果我们使用数组来存放一组数据,必须定义数组的大小。在无法确定数组大小的情况下，就必须将数组定义得足够大，以能适应不同的需要，这将造成系统资源(内存资源)浪费。,,使用一种新的数据结构--,链表,，就能克服上述缺点,它将根据需要开辟内存单元，因为链表结构是动态地分配存储，即在需要时才开辟一个结点的存储单元，因而就可以解决内存资源和用户需求之间的矛盾。,链表,:链表是一种新的

2、数据结构,系统对链表的元素是动态地进行存储分配。,,结点,:链表中的每一个元素称为结点（又称为域）。,,链表的,基本构成,：表头、一个或多个结点（域）、表尾。,,表头,: 链表有一个头指针变量,其中存放一个地址,该地址指向链表中的第一个元素(即第一个结点),,结点,: 链表中的每一个元素叫作一个结点（又叫域），结点都是结构体类型，每个结点包括若干个实际数据和一个指向本结构体的指针变量（称为指针域）,指针域用来指明下一个结点的地址。,,表尾,:链表最后一个结点中的指针域中存放一个空地址(用“,NULL”,来表示),以表示链表的结束。,一、链表概述,一、链表概述（四个结点的链表构成）,,,2480

3、,头指针,,,3420,结点1,,,2600,结点2,NULL,,,2800,结点3,2000,第四结点,,（链尾）,,,2480,3420,2600,2800,头指针的指针域,,存放第一结点地址,第一结点的指针域,,存放第二结点地址,第二结点的指针域,,存放第三结点地址,第三结点的指针域,,存放第四结点地址,链尾的指针域存放空地址,指针域,结点起始地址,二、有关链表的函数,1.,malloc,(),函数 (开辟一个动态存储区函数),,调用格式:,malloc,(size),,功能: 在内存的动态存储区中分配一个长度为,size,的连 续空间,,返回值: 空类型指针,其值为该连续存储单元的起始

4、地址, 若出错返回0,,说明:,size,是一个整型表达式,二、有关链表的函数,2.,malloc,(),函数 (开辟多个动态存储区函数),,调用格式:,calloc,(n,size),,功能: 在内存的动态存储区中分配,,n,个长度为,size,的连 续空间,,返回值: 空类型指针,其值为该连续存储单元的起始地址, 若出错返回0,,说明:,size,是一个整型表达式,二、有关链表的函数,3.,free(),函数 (释放动态存储区函数),,调用格式:,free(,ptr,),,功能: 在内存释放,ptr,所指向的内存区,,返回值: 无,,说明:,ptr,是,最近一次调用,calloc,(),或

5、,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

6、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!=

7、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,指向该单元 */,四、完整的建立单

8、向,链表的,方法,,定义结构体指针变量,p1,p2,headp1,指向新开辟的存储单元，,p2,指向链表中最后一个结点,head,指向头结点，定义整型变量,n,计,结点个数,n=n+1,Y,N,p2,下移,（,p1 →p2）,,开辟一个新结点并使,p1,指向它为新单元的数据域输入学号和成绩,p1->num !,=0,开辟一个新结点并使,p1,p2,指向它,,NULL→head，0 →n,,为新结点数据域输入学号和成绩,n==1,p1,→,head,作为首结点,结点连接（,p1 →p2->next）,,Y,N,四、完整的建立单向建立链表的程序,,#,define NULL,,0,,#defi

9、ne 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

10、),,{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,

11、指向该单元 */,/*,计数器加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.1f\n”,p->num,p->score);,,p=p->next;,,,}while(p!=NULL);,,},/*,p,指向链表表头 */,运行程序,/*,输出当前结点的数据,*/,/*,条件成立，说明链表是一个非空链表 */,/*,p,下移 */,/* 形参,head,为链表头,结点的起始地址,,*/,