数据结构全套配套课件C语言描述第2版李学刚教学课件2-04链表及其描述.pptx

《数据结构全套配套课件C语言描述第2版李学刚教学课件2-04链表及其描述.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2016数据结构Datastructure讲授：简勇链表及其描述常州信息职业技术学院02三、链表的插入03链表及其描述0.412一、链表的有关概念1．结点（Node）的组成线性表中的数据元素及元素之间的逻辑关系可由结点来表示。结点由两部分组成：一部分是用来存储数据元素的值的数据域，另一部分是用来存储元素之间逻辑关系的指针域，指针域存放的是该结点的直接后继结点的地址。结点的结构如图2-1：指针域数据域2．单链表（LingleLinkedList）用链式存储结构表示的线性表称为链表，即用一组任意（可以连续也可以不连续）的存储单元来存放线性表的结点；把每个结点只有一个指针域的链表称为

2、单链表。一、链表的有关概念04链表及其描述0.4一、链表的有关概念343．开始结点、尾结点、头结点和头指针在链表中存储第一个数据元素（a1）的结点称为开始结点；存储最后一个数据元素（an）的结点称为尾结点，由于尾结点没有直接后继，所以尾结点指针域的值为NULL，NULL在表示链表的示意图中经常用‘^’来代替；在开始结点之前附加的一个结点称为头结点；指向链表中第一个结点（头结点或开始结点）的指针称为头指针。4．单链表示意图不带头结点的单链表如图2-2(a)，带头结点的单链表如图2-2(b)。…开始结点head尾结点…开始结点head尾结点头结点(a)不带头结点单链表(b)带头结点

3、单链表图2-2单链表05链表及其描述0.455．结点的生成与释放当需要建立新的结点时，可以使用C语言为我们提供的动态存储分配函数malloc，向系统申请一个指定大小和类型的存储空间来生成一个新结点，新结点必须要用指向结点的指针来指向。一、链表的有关概念【示例2-3】设p是指向单链表结点的指针，可使用语句p=(ListNode*)malloc(sizeof(ListNode));向系统申请含有sizeof(ListNode)字节的存储空间，并强制转换为ListNode*类型，使p指向该存储空间，即指向新生成的结点。当由用户申请的某个存储空间（比如p指向的空间）不需要时，可使用fr

4、ee(p)；释放p指向的结点空间，以便其它应用程序使用，不至于造成空间的浪费。06链表及其描述0.4二、（链表）结点的描述typedefcharDataType;//定义结点的数据域类型typedefstructnode{//结点类型定义DataTypedata;//结点的数据域structnode*next;//结点的指针域}ListNode;//结构体类型标识符typedefListNode*LinkList;ListNode*p;//定义一个指向结点的指针LinkListhead;//定义指向链表的头指针07链表及其描述0.4123（1）LinkList和ListNode

5、*是不同名字的同一个指针类型，各有专门的用途以示区别。（2）专门使用LinkList定义指向单链表的头指针。（3）专门使用ListNode*定义指向某一结点的指针，如有定义ListNode*p;并使p指向某结点，则p指向结点的数据域可表示为p->data，p指向结点的指针域可表示为p->next。注意：THANKS2016.9.18