《C语言链表》PPT课件

《《C语言链表》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、111.7用指针处理链表1.链表概述1)动态数据结构概念数组和结构体是定长数据结构，而链表、堆栈、队列、树、图等是执行时大小可变的动态数据结构。链表是连成一行的数据项集合，每一个数据项(元素)称为节点，可以在链表中的任意位置进行节点插入或删除操作，使链表数据项的个数随之增加或减少。22)链表的构成单向链表图示：104813701012头节点表内节点尾节点210189.513702304901012291885NULL1048head其中：各节点是相同的结构体类型，该类型有三个成员；head是指针变量，存放链表的头节点指针10

2、48；各节点应包含一个指针成员存放下一节点的地址；各节点存储有可能不连续，但各节点逻辑上连续。33)节点的构成上图每个节点具有如下结构体类型：structstudent{longnum;floatscore;structerstudent*next;};/*链节成员*/其中：成员num、score用于存放一个节点的具体数据；成员next是指针类型，用于存放下一节点指针，最后一个节点的next成员存放空指针NULL；成员next是指向与自身同一类型的结构，这种结构称为自引用结构。(只有指针成员可自引用)节点是在运行时动

3、态生成的。44)动态内存分配和释放建立和维护动态数据结构需要实现动态内存分配；如在链表中插入节点需要先申请一段存储区域，而删除一个节点需要释放该节点原先占用的存储区域，这可由标准函数实现。内存分配函数原形：void*malloc(unsignedsize);功能：申请长度为size个字节的内存空间；若申请成功，返回存储块起始指针，该指针类型为void*；否则返回空指针(NULL)。内存释放函数原形：voidfree(void*p);功能：释放p所指向的内存块。包含文件：malloc.h、stdlib.h中均有其原型声明。55)采

4、用链表的意义与定长数据结构数组相比，链表能更好地利用内存，按需分配和释放存储空间。在链表中插入或删除一个节点，只需改变某节点“链节”成员的指向，而不需要移动其它节点，相对数组元素的插入和删除效率高。即：链表特别适合于对大线性表频繁插入和删除元素、或成员数目不定的数据结构。66)链表的类型单链表：每个节点只有一个指向后继节点的指针双向链表：每个节点有两个用于指向其它节点的指针；一个指向前趋节点，一个指向后继节点循环链表：使最后一个节点的指针指向第一个节点72.单链表的建立和输出建立链表的准备工作:1)定义链表的节点类型；2)定

5、义与节点同类型的链表头指针变量head并赋值0，表示链表在建立之前是空的；3)定义与节点同类型的工作指针变量p1、p2。8建立链表的步骤：1)开辟第一个节点的存储区域，使head、p1、p2指向第一个节点，并输入第一个节点数据；210189.5headp1p2操作：len=sizeof(structstudent);p1=(structstudent*)malloc(len);scanf("%ld,%f",&p1->num,&p1->score);head=p2=p1;92)开辟下一节点的存储区域，使p1指向新节点、输入新节点数

6、据，并将上一个节点的next成员指向新节点；210189.5headp1p22304901048操作：p1=(structstudent*)malloc(len);scanf("%ld,%f",&p1->num,&p1->score);p2->next=p1;p2=p1;/*使p2也指向新节点*/13701370p2p1103)重复第2步，建立并链接多个节点直至所需长度，将末尾节点的next成员赋值0。210189.51370headp2230490291885p2NULL10481370p110121012p2p1操作：p1=

7、(structstudent*)malloc(len);scanf("%ld,%f",&p1->num,&p1->score);p2->next=p1;p2=p1;/*使p2也指向新节点*/p2->next=NULL;/*末尾节点next赋值0*/11【例】建立并输出有3名学生数据的单链表。#include/*包含NULL的定义*/#include#defineN3structstudent/*结构体类型定义*/{longnum;floatscore;structstudent*next;/*自

8、引用结构体指针*/};voidmain(){┇}12voidmain(){structstudent*head,*p1,*p2;inti,len;sqrt(5.5);/*TC激活浮点运算*/head=NULL;/*head不指向任何位置*/len=sizeof(