C++课件简单链表及其应用.ppt

简单链表及其应用 链表是指将一组同类型数据 通常为结构体类型 按其特有的方式连接在一起的一种数据结构 链表中的元素称为结点 每一个结点都包含两类数据 一类数据称为结点的值域 它是描述该结点所包含的实际数据 可以由多个不同类型的数据构成 另一类数据称为链域 它用来存储与本结点相邻的结点的地址 其作用是将各个结点连接在一起 它通常是与结点同类型的指针 任何一个链表都一个起始指针 称为该链表的头指针 head 链表的最后一个结点称为尾结点 它的链域指针不指向任何结点 通常将它设置为空指针 特点每个元素 表项 由结点 Node 构成 线性结构结点可以不连续存储表可扩充 单链表 SinglyLinkedList 存储数据元素 存储后继结点存储地址 头结点 空指针 单链表的存储映像 某单链表示意图如下 头指针head 用C 语言描述的一个简单的单链表如下 structnode intdata 值域node next 链域 例 建立一个简单的链表 它由3个学生数据的结点组成 输出各结点中的数据 defineNULL0p head structstudentdo longnum coutnumscore floatscore p p next student next while p NULL voidmain studenta b c head p a num 99101 a score 89 5 b num 99103 b score 90 c num 99107 c score 85 head 创建无序链表 一个链表是有若干个结点连接而成 创建链表实际上是创建链表中的各个结点 并将它们连接起来 函数nosorted create 实现创建链表 其算法为 如果链表为空 head 0 则将该结点设置为表头 如果链表非空 则将该结点加入到链表的末尾 将结点设置为表头的过程如下图所示 将结点加到链表末尾的过程如下图所示 链表创建结束 链表的输出 voidShowList node head if head 0 coutdatanext 链表某个结点的访问 node access node head intn if head 0 coutnext 0 coutnext returntemp 统计链表结点的个数 intnode count node head node temp head intcount 0 while temp 0 count temp temp next returncount 访问链表尾结点 node accessTail node head if head 0 return0 node temp head while temp next 0 temp temp next returntemp 无序链表的插入 第一种情况 插入一个空表head newnode head next 0 第二种情况 在第一个结点前插入newnode next head head newnode 第三种情况 在链表中间插入newnode next current next current next newnode 第四种情况 在链表末尾插入tail next newnode newnode next 0 第一种情况 删除表中第一个元素 pcur head head head next deletepcur a1 a1 a2 a2 a3 a3 head 删除前 删除后 无序链表结点的删除 head p 第二种情况 删除表中或表尾元素 p next q next deleteq ai 1 ai 1 ai ai ai 1 ai 1 q 删除前 删除后 创建有序链表 所谓有序链表 是指链表中的结点按结点的某个成员的大小进行排列 将一个结点插入到有序链表中时 为了保持有序性 要判断插入的位置 函数insert sort node node node 通过上述插入函数 可以创建一个有序链表 函数sorted create 链表的删除 voiddeletelist node 无序链表的排序 voidconvert inttemp i j node pcur head for i 1 idata pcur n