d02-数据结构讲义.ppt

第 * 页 线性表—链式存储与实现 编程题2 将两个非递减有序的有序单链表la和lb归并为非递增的有序表。 Typedef struct LNode { int data; // 数据域 struct Lnode *next; // 指针域 } LNode, *LinkList; LinkList la, lb； // 单链表的头指针 请用la和lb中的结点合并生成一个新的非递增的有序单链表lc。合并完成后，la和lb为空链表。 第 * 页 线性表—链式存储与实现 思考题3 设一带头结点的双向循环链表表示的线性表： L =（a1, a2, …… , an） 请写出一个时间复杂度为O(n)的算法，将L改造为： L =（a1, a2, …… , an, …… , a2, a1） 第 * 页 线性表—链式存储与实现 思考题1 a1 a2 a3 ? L L p ? succ a1 ? p succ a2 p succ a3 p 1）标志后继结点； 2）修改指针（将*p插入在头结点之后）； 3）重置结点*p（p重新指向原表中后继）； 第 * 页 线性表—链式存储与实现 void inverse(LinkList L) { // 逆置带头结点的单链表 L p=L-next; L-next=NULL; while ( p) { succ=p-next; // succ指向*p的后继 p-next=L-next; L-next=p; // *p插入在头结点之后 p = succ; } } 第 * 页 线性表—链式存储与实现 思考题2 12 23 34 45 56 11 32 43 48 54 La Lb Lc ∧ pa pb q pb ∧ q pa q pa q 第 * 页 线性表—链式存储与实现 操作步骤: 建空表 Lc; 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表中第一个结点之前直至其中一个表变空为止; 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的表头结点之后; 释放 La 表和 Lb 表的表头结点。 第 * 页 线性表—链式存储与实现 void union ( LinkList Lc, LinkList La, LinkList Lb ) { // 将非递减的有序表 La 和Lb归并为非递增的 // 有序表Lc,归并之后，La和Lb表不再存在。 // 上述三个表均为带头结点的单链表，Lc 表 // 中的结点即为原 La 或 Lb 表中的结点。 } // union Lc = new LNode; Lc-next = NULL; pa = La-next; pb = Lb-next; // 初始化 …… …… // 归并 delete La; delete Lb; // 释放La 和 Lb的头结点 第 * 页 线性表—链式存储与实现 while ( pa || pb ) { if ( !pa ) { q = pb; pb = pb-next; } else if ( !pb ) { q = pa; pa = pa-next; } else if ( pa-data = pb-data ) { q = pa; pa = pa-next; } else { q = pb; pb = pb-next; } q-next = Lc-next; Lc-next = q; // 插入 } * 第 * 页 2.3 线性表的链式存储与实现 线性链表（单链表）的基本操作 取数据元素操作 GetElem( L, i, e ) 功能：取带有头结点的线性链表 L 中第 i 个元素结点，其值存入 e。 主要步骤 查找到第 i-1 个元素结点 取值存入 e L 21 18 30 75 42 56 ∧ p p p j 1 2 3 第 * 页 2.3 线性表的链式存储与实现 单链表操作的特点 单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。 因此，查找第 i 个数据元素的基本操作为：移动指针p，比较 j 和 i。（若指针 p 始终指向线性表中第 j