数据结构单链表.ppt

第二章线性表 链表 单链表 定义特点C描述基本形态基本操作实现 一组数据项的集合 其中每个数据项都是一个结点的一部分 每个结点都包含指向下一个结点的链接 即指针 1 数据元素在 逻辑关系上的相邻 用 指针 来表示 2 单链表中访问数据元素时需从头开始 顺序访问 3 比顺序表的优势在于 提供高效地重排数据项的能力 L 单链表的C描述 typedefstructLNode ElemTypedata 数据域structLNode next 指针域 LNode LinkList LinkListL L为单链表的头指针 头指针指向单链表中的第一个结点 用指针表示链接 用结构体表示结点 结点是由数据项和链接组成的 链接是指向下一结点的指针 单链表的基本形态 空表非空表 为了操作方便 在第一个结点之前虚加一个 头结点 哑元结点 L L next NULL 不允许删除操作 L 可以进行插入 删除操作 单链表基本操作 1 初始化 动态分配 StutasInitList LinkList j 1 2 3 单链表基本操作 2 取单链表中指定位序的数据元素 演示例子 取单链表中第3个元素值 取元素的基本操作 单链表是一种 顺序访问 的结构 为找第i个数据元素 必须先找到第 i 1 个数据元素 1 指针p始终指向单链表中第j个结点 2 移动指针 比较j和i 相等则找到 StatusGetElem L LinkListL inti ElemType e L是带头结点的链表的头指针 以e返回第i个元素 GetElem L 算法时间复杂度为 O ListLength L p L next j 1 p指向第一个结点 j为计数器 while p 顺指针向后查找 直到p指向第i个元素 或p为空 if p 与顺序表相比 链表不适合于查找第i个元素的操作 单链表基本操作 3 插入 在第i个元素前插入e 单链表中 有序对改变为和 在单链表中插入结点只需要修改指针 若要在第i个结点之前插入元素 修改的是第 i 1 个结点的指针 StatusListInsert L LinkList L inti ElemTypee L为带头结点的单链表的头指针 本算法 在链表中第i个结点之前插入新的元素e LinstInsert L 算法的时间复杂度为 O ListLength L elsereturnERROR p L j 0 while p 寻找第 i 1 个结点if p j i 1 s LinkList malloc sizeof LNode 生成新结点s data e s next p next p next s 插入returnOK s p 有序对和改变为 单链表基本操作 4 删除 第i个元素 在单链表中删除第i个结点时 要找到单链表中第 i 1 个结点 修改其指向后继的指针 q p next p next q next e q data free q p q StatusListDelete L LinkList L inti ElemType e 删除以L为头指针 带头结点 的单链表中第i个结点 ListDelete L 算法的时间复杂度为 O ListLength L p L j 0 while p next 寻找第i 1个结点 并令p指向它 if p next j i 1 q p next p next q next 删除并释放结点e q data free q returnOK elsereturnERROR 删除位置不合理 对比单链表和顺序表的基本操作 插入和删除的简单性是链表存在的理由只修改相关结点的指向保持链表特性单链表的访问方式是顺序访问查找第i个数据项的代价 沿着链表 一个一个结点地访问 直到找的这个数据项 算法时间复杂度 O ListLength L 单链表基本操作 5 清空 while L next p L next L next p next free p 算法时间复杂度 O ListLength L 单链表基本操作 6 销毁 while L p L next free L L p 单链表基本操作 7 判空 if L next NULL returnTRUE elsereturnFALSE 8 求表长 intListLength LinkListL p L next i 0 while p i p p next returni 单链表基本操作 9 搜索 查找元素 p L next i 1 while p 从第一个结点开始搜索 搜索成功 返回位序 否则 返回0 单链表的应用 1 建立单链表 链表是一个动态结构 它不需要预分配空间 因此生成链表的过程是一个结点 逐个插入 的过程 逆序建立单链表 顺序建立单链表 新结点插入在头结点的后面 作为重排链表后的第一个结点 新结点插入在尾结点的后面 作为重排链表后的最后一个结点 逆序建立单链表 操作步骤 建立一个带头结点的空单链表 输入数据元素ai 建立新结点p 并把p插入在头结点之后成为第一个结点 重复执行 步 直到完成单链表的建立 a1 a1 a2 voidCreateList N LinkList L intn 逆序输入n个数据元素 建立带头结点的单链表 CreateList L 算法的时间复杂度为 O Listlength L L LinkList malloc sizeof LNode L next NULL 先建立一个带头结点的单链表 for i 1 idata 输入元素值p next L next L next p 插入 顺序建立单链表 操作步骤 建立一个带头结点的空单链表 输入数据元素ai 建立新结点 并把其插入在尾结点p之后成为最后一个结点 重复执行 步 直到完成单链表的建立 a1 p a1 p p a2 p a3 p p p an 顺序建立单链表 即新元素插入表尾 L LinkList malloc sizeof LNode L next NULL 先建立一个带头结点的单链表 时间复杂度为O n p L for i 1 idata q next p next p next q p q 单链表的应用 2 归并有序链表 归并有序单链表La和有序单链表Lb得到有序单链表Lc 链表结点之间的关系是通过指针指向建立起来的 所以用链表进行合并不需要另外开辟存储空间 可以直接利用原来两个表的存储空间 合并过程中只需要把La和Lb两个链表中的结点重新进行链接即可 单链表的应用 归并思想 需要设立3个指针pa pb pc 其中pa和pb分别指向La和Lb中当前待比较插入的结点 而pc指向Lc中当前最后一个结点 Lc的表头结点设为La的表头结点 指针的初值为 pa和pb分别指向La和Lb表中的第一个结点 pc指向空表Lc中的头结点 通过比较指针pa和pb所指向的元素的值 依次从La或Lb中 摘取 元素值较小的结点插入到Lc的最后 当其中一个表变空时 只要将另一个表的剩余段链接在pc所指结点之后即可 归并有序单链表 voidMergeList L LinkList 算法时间复杂度 O m n 算法空间复杂度 O 1 单链表的应用 3 稀疏多项式的运算 稀疏多项式可以抽象成一个线性表 稀疏多项式的相加过程和归并两个有序表的过程极其类似 不同之处在于 多项式的相加过程在比较两个多项式指数时要考虑三种情况 等于 小于 大于 链式存储结构更加灵活 合并过程空间复杂度为O 1 多项式A x 7 3x 9x8 5x17和多项式B x 8x 22x7 9x8 单链表的应用 稀疏多项式的相加 规则 对于两个多项式中所有指数相同的项 对应系数相加 若其和不为零 则作为 和多项式 中的一项插入到 和多项式 链表中去 对于两个多项式中指数不相同的项 则将指数值较小的项插入到 和多项式 链表中去 和多项式 链表中的结点无需生成 而应该从两个多项式链表中摘取 111 227 A 稀疏多项式相加 typedefstructPNode floatcoef intexpn structPNode next PNode Polynomial 用单链表表示多项式时 每个链表结点存储多项式中的一个非零项 包括系数 coef 和指数 expn 两个数据域以及一个指针域 next 稀疏多项式相加 假设头指针pa和pb的单链表分别为多项式A和B的存储结构 指针p1和p2分别指向A和B中当前进行比较的某个结点 则逐一比较两个结点中的指数项 对于指数相同的项 对应系数相加 若其和不为零 则将插入到 和多项式 链表中去 对于指数不相同的项 则通过比较将指数较小的项插入到 和多项式 链表中去 稀疏多项式相加 voidAddPolyn Polynomial else 稀疏多项式相加 r p1 p1 p1 next free r r p2 p2 p2 next free r elseif p1 expnexpn p3 next p1 p3 p1 p1 p1 next else p3 next p2 p3 p2 p2 p2 next p3 ne