C语言-链表课件.ppt

1,11.7用指针处理链表1.链表概述1)动态数据结构概念数组和结构体是定长数据结构，而链表、堆栈、队列、树、图等是执行时大小可变的动态数据结构。链表是连成一行的数据项集合，每一个数据项(元素)称为节点，可以在链表中的任意位置进行节点插入或删除操作，使链表数据项的个数随之增加或减少。,2,2)链表的构成单向链表图示：104813701012头节点表内节点尾节点,head,其中：各节点是相同的结构体类型，该类型有三个成员；head是指针变量，存放链表的头节点指针1048；各节点应包含一个指针成员存放下一节点的地址；各节点存储有可能不连续，但各节点逻辑上连续。,3,3)节点的构成上图每个节点具有如下结构体类型：structstudentlongnum;floatscore;structerstudent*next;/*链节成员*/其中：成员num、score用于存放一个节点的具体数据；成员next是指针类型，用于存放下一节点指针，最后一个节点的next成员存放空指针NULL；成员next是指向与自身同一类型的结构，这种结构称为自引用结构。(只有指针成员可自引用)节点是在运行时动态生成的。,4,4)动态内存分配和释放建立和维护动态数据结构需要实现动态内存分配；如在链表中插入节点需要先申请一段存储区域，而删除一个节点需要释放该节点原先占用的存储区域，这可由标准函数实现。内存分配函数原形：void*malloc(unsignedsize);功能：申请长度为size个字节的内存空间；若申请成功，返回存储块起始指针，该指针类型为void*；否则返回空指针(NULL)。内存释放函数原形：voidfree(void*p);功能：释放p所指向的内存块。包含文件：malloc.h、stdlib.h中均有其原型声明。,5,5)采用链表的意义与定长数据结构数组相比，链表能更好地利用内存，按需分配和释放存储空间。在链表中插入或删除一个节点，只需改变某节点“链节”成员的指向，而不需要移动其它节点，相对数组元素的插入和删除效率高。即：链表特别适合于对大线性表频繁插入和删除元素、或成员数目不定的数据结构。,6,6)链表的类型单链表：每个节点只有一个指向后继节点的指针双向链表：每个节点有两个用于指向其它节点的指针；一个指向前趋节点，一个指向后继节点循环链表：使最后一个节点的指针指向第一个节点,7,2.单链表的建立和输出建立链表的准备工作:1)定义链表的节点类型；2)定义与节点同类型的链表头指针变量head并赋值0，表示链表在建立之前是空的；3)定义与节点同类型的工作指针变量p1、p2。,8,建立链表的步骤：1)开辟第一个节点的存储区域，使head、p1、p2指向第一个节点，并输入第一个节点数据；,head,p2,操作：len=sizeof(structstudent);p1=(structstudent*)malloc(len);scanf(%ld,%f,9,2)开辟下一节点的存储区域，使p1指向新节点、输入新节点数据，并将上一个节点的next成员指向新节点；,head,p1,1048,操作：p1=(structstudent*)malloc(len);scanf(%ld,%f,/*使p2也指向新节点*/,1370,1370,10,3)重复第2步，建立并链接多个节点直至所需长度，将末尾节点的next成员赋值0。,head,p2,NULL,10481370,操作：p1=(structstudent*)malloc(len);scanf(%ld,%f,/*末尾节点next赋值0*/,11,【例】建立并输出有3名学生数据的单链表。#include/*包含NULL的定义*/#include#defineN3structstudent/*结构体类型定义*/longnum;floatscore;structstudent*next;/*自引用结构体指针*/;voidmain(),12,voidmain()structstudent*head,*p1,*p2;inti,len;sqrt(5.5);/*TC激活浮点运算*/head=NULL;/*head不指向任何位置*/len=sizeof(structstudent);/*求类型长*/for(i=1;inum,/*标记末尾节点*/,13,voidmain()for(i=1;inext;/*p1指向下一节点*/printf(%d:num=%ld,score=%5.2fn,i,p1-num,p1-score);/*main*/,14,【例】将上题利用函数实现，并求平均成绩。定义如下函数：建立链表函数:structstudent*create(void);输出链表函数:voidplink(structstudent*head);求平均值函数:floataverf(structstudent*head);函数间信息传递：,主函数,create,plink,averf,无参,头指针,头指针,无返回值,平均值,头指针,2019/12/15,15,可编辑,16,#include#include#defineN3structstudent/*全局结构类型*/longnum;floatscore;structstudent*next;voidmain(),17,voidmain()structstudent*head,*create(void);voidplink(structstudent*head);floataverf(structstudent*head);inti,len;floataver;sqrt(5.5);clrscr();/*TC中使用head=NULL;head=create();/*返回链表头指针*/plink(head);aver=averf(head);/*返回平均值*/printf(Average=%5.2fn,aver);,18,structstudent*create()structstudent*head,*p1,*p2;inti,len;len=sizeof(structstudent);for(i=1;inum,/返回链表头指针,19,voidplink(structstudent*head)/*输出各节点*/structstduent*p;inti;for(i=1;inext;printf(%d:num=%ld,score=%5.2fn,i,p-num,p-score);return;,P,P,20,floataverf(structstudent*head)structstudent*p;floatsum=0;intc=0;p=head;/*使p指向首节点*/while(p!=NULL)c+;/*c统计节点数*/sum=sum+p-score;p=p-next;return(sum/c);/*返回平均值*/,21,1370,3.节点的删除步骤：从头节点开始按查找关键字查找要删除的节点；2)找到，则将要删除节点的“链节”成员赋给前一节点的“链节”成员，使删除的节点脱离链表。若：要删除节点为首节点，则将首节点“链节”成员赋给链头指针变量。3)释放已被删除节点占用的空间。10481012,head,p,NULL,1048,1012,22,【例】按上例删除指定学号的节点structstudent*del(structstudent*head,longn)structstudent*p1,*p2;/*n：要删除学号*/p1=head;if(p1-num=n)head=p1-next;/*删除首节点*/elsedop2=p1;p1=p1-next;/*继续找*/while(p1!=NULL/*返回头指针*/,23,voidplink(structstudent*head)/*更具通用性*/structstudent*p;p=head;while(p!=NULL)printf(num=%ld,score=%5.2fn,p-num,p-score);p=p-next;return;注：本形式的链表输出函数具有通用性，可适应由于删除或插入节点引起的链表长度的变化。,24,4.节点的插入插入可分为随意插入和按顺序插入，随意插入包括插入到头部、尾部或中间指定位置；按顺序插入是指按某关键字的顺序插入，而在插入前链表必须已按该关键字进行了排序。按顺序插入的步骤：开辟待插入节点的存储区域并输入数据；2)查找插入位置：从链表首节点开始按关键字成员与待插入节点相同成员进行比较，直到确定了插入位置；,25,3)将插入位置前一节点的“链节”成员赋给待插入节点的“链节”成员；若：插入点在链头，则将头指针赋给待插入节点的“链节”成员；4)将待插入节点的指针赋给前一节点“链节”成员；若：插入点在链头，先将头指针赋给插入节点的指针域，再将待插入节点的指针赋给头指针变量。,head,1048,104813701012,1012,2680,2680,26,【例】按上例在链表中按学号顺序插入节点插入函数：structstudent*insert(structstudent*head)structstudent*p0,*p1,*p2;longn;intlen;len=sizeof(structstudent);p0=(structstudent*)malloc(len);/*申请新节点*/printf(Enternum,scoretoinsert:);scanf(%ld,%f,/*从首节点开始查找*/,27,p1=head;/*插入在头部*/if(nnum)p0-next=head;head=p0;elsedo/*查找插入位置*/p2=p1;p1=p1-next;while(p1!=NULL/*insert*/,28,【例】编写一个通用的函数，可根据需要建立任意节点数的链表。structstudent*creat()/*无参有返回值*/structst