Microsoft Word - 第3章.doc

Transcription

1 第 3 章 线性表 Ⅱ 链表 常见考点 链表存储结构的特点 单链表结构及其算法设计方法 双链表结构及其算法设计方法 循环链表结构及其算法设计方法 灵活运用链表解决一些较复杂的应用问题 3.1 线性表链式存储结构概述 要点归纳 1. 链表线性表的链式存储结构称为链表, 通常线性表中的一个元素用一个链表结点存放, 每个结点增加指针域表示结点之间的逻辑关系 有一个指针域的链表称为单链表 ( 通常结点指针指向其后继结点 ); 有两个指针域的链表称为双链表 ( 通常结点的一个指针指向其后继结点, 另外一个指针指向其前驱结点 ) 链表和顺序表相比, 由于每个结点需要额外空间表示逻辑关系, 所以链表的存储密度相对较低 ( 双链表的存储密度低于单链表 ); 当查找序号为 i 的结点时需要从前向后扫描, 对应的时间为 O(n), 所以链表不具有随机存取特性 但由于链表中的每个结点单独分配空间, 所以链表具有很好的适应性, 不需要事先确定空间大小 ; 在链表中插入和删除结点只需要修改前后相关结点的指针域, 不用移动结点 2. STL 的 list 链表容器 STL 提供了 list 链表容器, 它是一个双链表类模板, 可以从任何地方快速地插入与删除 它的每个元素之间用指针相连, 不能随机访问元素 其主要的成员函数如下 size(): 返回表中实际元素的个数 empty(): 判断表是否为空 push_back(): 在表的尾部插入元素 77

2 直击招聘 程序员面试笔试 C 数据结构深度解析 pop_back(): 删除最后一个元素 remove (): 删除所有指定值的元素 erase(): 从容器中删除一个或几个元素 clear(): 删除所有的元素 insert(pos,elem): 在 pos 处插入 elem 元素并返回该元素的位置 swap(): 交换两个元素 begin(): 该函数返回链表容器的第 1 个元素 end(): 该函数返回链表容器的最后一个元素后面的一个位置 在编程中使用链表的地方都可以用 list<t> 链表容器代替, 但为了理解链表的概念和原理, 后面的算法没有使用 list<t>, 而是直接采用基础编程 面试题解析 面试题 3-1 对于一个线性表既要求能够进行较快速的插入和删除, 又要求存储结构能反映数据之间的逻辑关系, 则应该用 ( ) A. 顺序存储方式 B. 链式存储方式 C. 散列存储方式 D. 以上均可以答 : 线性表主要有顺序和链式两类存储方式, 而后者能够进行较快速的插入和删除 答案为 B 面试题 3-2 以下( ) 不是链表的特征 A. 数据在内存中一定是连续的 B. 在插入或删除时无须移动其他元素 C. 可以随机访问表内的元素 D. 需要事先估计存储空间答 : 以上只有在插入或删除时不需要移动其他元素是链表的特征, 其他都不是 答案为 A C D 面试题 3-3 以下关于链式存储结构的叙述中( ) 是不正确的 A. 结点除自身信息外还包括指针域, 因此存储密度小于顺序存储结构 B. 逻辑上相邻的结点物理上不必邻接 C. 可以通过计算直接确定第 i 个结点的存储地址 D. 插入 删除运算操作方便, 不必移动结点答 : 链式存储结构不具有随机存取特性, 即不能通过计算直接确定第 i 个结点的存储地址 答案为 C 面试题 3-4 频繁的插入 删除操作使用什么结构比较合适, 链表还是数组? 答 : 若采用数组存储含 n 个元素的线性表, 插入 删除操作平均大约需要移动 n/2 个元素, 而采用链表存储线性表时插入 删除操作不需要移动元素, 只需要修改结点的指针域, 所以更高效, 答案为链表 78

3 第 3 章线性表 Ⅱ 链表 3.2 单链表算法设计 要点归纳 1. 单链表的结构和基本运算 在单链表中, 声明结点类型如下 : typedef struct LNode { T data; struct LNode *next; // 指向后继结点 LinkNode; // 声明单链表结点类型 通常, 单链表采用的是带头结点的结构, 如图 3.1 所示, 这样做的目的是使得空表和非空表 首结点和其他结点的处理相一致, 从而简化算法设计 L 头结点首结点尾结点 a 1 a 2 a n 图 3.1 带头结点的单链表 在单链表中如果有头结点, 通常用头结点的地址 ( 即头指针 ) 来标识整个单链表, 第 1 个数据结点称为首结点, 指向首结点的指针称为首指针 在不带头结点的单链表中通常用首指针来标识整个单链表, 指向尾结点的指针称为尾指针 在单链表中从一个结点出发只能向后查找后继结点, 所以插入和删除一个结点需要已知前驱结点, 通过修改相关指针域达到插入和删除结点的目的 2. 单链表的算法设计 1 基于查询操作的算法设计这类算法首先是通过单链表的指针链进行查找, 找到满足条件的结点后进行插入或者删除操作 例 3-1 设计一个算法删除非空单链表 L 中所有值最大的结点 ( 假设这样的结点可能有多个 ) 解 : 通过一遍扫描求出最大结点值为 max, 再从头到尾扫描删除所有值为 max 的结点 由于在单链表中删除结点需要已知前驱结点, 为此用 pre 指向 p 结点的前驱结点, 两者同步移动 对应的算法如下 : 79

4 直击招聘 程序员面试笔试 C 数据结构深度解析 void Delmaxnodes(LinkNode *&L) { LinkNode *pre=l,*p=l->next; T max=p->data; while(p!=null) // 查找最大结点的结点值 max { if(p->data>max) max=p->data; p=p->next; p=l->next; while(p!=null) // 查找等于 max 的结点并删除 { if(p->data==max) { pre->next=p->next; // 删除 p 结点 free(p); // 释放 p 结点 p=pre->next; // 让 p 继续指向 pre 结点的后继结点 { pre=p; //pre p 指针同步后移 p=p->next; 2 基于建表思路的算法设计单链表的建表就是根据给定的数据序列来整体创建单链表, 其方式有头插法建表和尾插法建表 头插法建表就是先创建头结点 L, 并将其 next 指针设置为 NULL 每次创建一个新结点 s, 将它插入到头结点之后 首结点之前, 即 s->next=l->next;l->next=s 所以采用头插法建立的单链表的结点值顺序与数据序列的顺序相反 尾插法建表就是先创建头结点 L, 设置一个指向尾结点的指针 r, 初始时 r=l 每次创建一个新结点 s, 将它插入到单链表的末尾, 即 r->next=s;r=s( 保证 r 始终指向尾结点 ) 最后需要将尾结点 next 域设置为空, 即 r->next=null 所以采用尾插法建立的单链表的结点值顺序与数据序列的顺序相同 这两个建表算法尽管简单, 但是有很多相关算法的基础 在一些情况下, 建表的结点已经存在, 只需要采用建表思路修改结点的指针域来生成新的单链表 例 3-2 设计一个算法将非空单链表 L 的所有结点逆置 解 : 用 p 扫描所有数据结点, 先建立只有头结点的空单链表 L, 然后将 p 结点采用头插法一个一个地插入 对应的算法如下 : void Reverse(LinkNode *&L) 80

5 第 3 章线性表 Ⅱ 链表 { LinkNode *p=l->next,*q; L->next=NULL; while(p!=null) // 变为空的单链表 // 扫描所有数据结点 { q=p->next; // 临时保存 p 结点的后继结点 p->next=l->next; L->next=p; p=q; 3 有序单链表的算法设计 // 头插法 可以利用有序单链表的有序性和二路归并等提高算法的效率, 其思路与有序顺序表的相关算法思路相同 例 3-3 设计一个算法将两个非空递增有序单链表合并为一个递减有序单链表, 要求空间复杂度为 O(1) 解 : 题目要求空间复杂度为 O(1), 所以只能利用两个单链表 L1 L2 的数据结点来新建合并后的单链表 L3 因为是由两个递增单链表创建一个递减单链表, 所以采用头插法来建立单链表 L3 对应的算法如下: void Merge(LinkNode *&L1,LinkNode *&L2,LinkNode *&L3) { LinkNode *p1=l1->next,*p2=l2->next,*q; free(l1);l1=null; // 释放 L1 头结点并置为 NULL free(l2);l2=null; // 释放 L2 头结点并置为 NULL L3=(LinkNode *)malloc(sizeof(linknode)); L3->next=NULL; while(p1!=null && p2!=null) { if(p1->data<p2->data) { q=p1->next; // 临时保存 p1 结点的后继结点 p1->next=l3->next; // 采用头插法将 p1 结点插入到 L3 中 L3->next=p1; p1=q; { q=p2->next; // 临时保存 p2 结点的后继结点 p2->next=l3->next; // 采用头插法将 p2 结点插入到 L3 中 L3->next=p2; p2=q; if(p2!=null) p1=p2; // 若 p2 没有扫描完, 让 p1 指向 p2 结点 81

6 直击招聘 程序员面试笔试 C 数据结构深度解析 while(p1!=null) // 将没有扫描完的依次扫描 { q=p1->next; // 临时保存 p1 结点的后继结点 p1->next=l3->next; // 采用头插法将 p1 结点插入到 L3 中 L3->next=p1; p1=q; 上述算法的时间复杂度为 O(m+n) 如果要求不破坏单链表 L1 L2, 那么就需要采用复制方法创建单链表 L3 的所有数据结点, 对应的空间复杂度为 O(m+n) 面试题解析 面试题 3-5 在一个单链表 HL 中, 若要在指针 first 所指结点的后面插入一个指针 second 所指向的结点, 则执行 ( ) A.second->next=first->next ; first->next=second; B.first->next=second->next; second=first; C.second->next=first->next ; second->next=first; D.first->next=second->next; second->next=first; 答 : 先让 second 结点的 next 指针域指向 first 的后继结点, 即 second->next=first->next, 再让 first 结点的指针域指向 second 结点, 即 first->next=second 答案为 A 面试题 3-6 在一个单链表中, 若删除 p 所指结点的后继结点, 则执行 ( ) A.p = p->next; p->next = p->next->next; B.p->next = p->next; C.p->next = p->next->next; D.p = p->next->next; 答 : 在删除 p 所指结点的后继结点时, 让 p 结点的指针域指向其后继结点的后继结点, 即 p->next=p->next->next 答案为 C 面试题 3-7 将长度为 n 的单链表连接在长度为 m 的单链表之后, 其算法的时间复杂度为 ( ) A.O(m) B.O(1) C.O(n) D.O(m+n) 答 : 其操作是先在长度为 m 的单链表中通过遍历找到尾结点 p( 时间复杂度为 O(m)), 再让 p 结点的指针域指向长度为 n 的单链表的首结点 ( 时间复杂度为 O(1)), 总的时间复杂度为 O(m) 答案为 A 面试题 3-8 输入一个链表的头结点, 从尾到头输出每个结点的值 链表的结点定义如下 : 82

7 第 3 章线性表 Ⅱ 链表 struct ListNode { int m_nkey; ListNode* m_pnext; ; 解 : 除了结点类型不同, 其他与例 3-2 完全一样 尽管该题不难, 但该题以及变种经常出现在各大公司的面试 笔试题中 面试题 3-9 设计一个递归算法逆置一个非空单链表 解 : 例 3-2 是采用头插法实现单链表的逆置的, 这里要求采用递归方法 通常, 单链表的递归算法是针对不带头结点的单链表 假设由首结点指针 first 标识一个不带头结点的非空单链表, 设 f(first) 返回逆置后的首结点指针, 为大问题, 则 f(first->next) 返回逆置后的首结点指针 p, 为小问题, 如图 3.2 所示 当小问题解决后, 大问题的求解只需要将 a 1 结点 (first 指向它 ) 链接到 first->next 结点的末尾就可以了 对应的递归模型如下 : f(first) 返回 first 当 first=null 或者只有一个结点时 f(first) f(first->next); 将 first 结点链接到 first->next 的后面 其他情况 first first->next a 1 a 2 a n-1 a n p=f(first->next): 小问题 first->next p a 2 a n a n 图 3.2 小问题的求解结果 对应的算法如下 : LinkNode *reverse(linknode *first) // 逆置不带头结点的单链表 first { LinkNode *p; if(first==null first->next==null) return first; p=reverse(first->next); first->next->next=first; // 将 first 结点链接到 first->next 结点的后面 first->next=null; // 将 first 结点作为逆置后的尾结点 return p; void Reverse(LinkNode *&L) // 逆置带头结点的单链表 L 83

8 直击招聘 程序员面试笔试 C 数据结构深度解析 { L->next=reverse(L->next); //L->next 为不带头结点的单链表 注意 : 在 reverse(linknode *first) 函数中,first 是值参数 ( 对应的实参是不变的 ), 逆置后单链表的首结点指针是作为返回值实现的, 如果将其改为引用参数, 结果是错误的 面试题 3-10 将一个非空单链表中序号从 i 到 j 的结点逆置 解 : 又是单链表的逆置, 但需要考虑以下几点 参数 i j 可能错误, 例如它们的值超过了单链表的长度等, 所以对应函数设计为 bool 函数类型 先找到第 i-1 个结点 pre, 置 pre->next=null( 断开 ) p 扫描 pre 结点原来的后面结点一直到第 j 个结点 ( 让 r 指向第 1 个 p 结点 ), 将每个 p 结点采用头插法插入到 pre 结点之后 ( 逆置这些结点, 逆置后的尾结点就是 r 结点 ) 最后将余下的结点链接在 r 结点的后面 对应的算法如下 : int ListLength(LinkNode *L) { LinkNode *p=l;int i=0; while(p->next!=null) { i++; p=p->next; return(i); bool Reverseij(LinkNode *&L,int i,int j) // 求单链表的长度 { int k=0,n; //k 用于扫描时的结点计数 LinkNode *pre=l,*p,*q,*r; n=listlength(l); if(i<0 i>n j<0 j>n i>j) return false; while(k<i-1 && pre!=null) { k++; pre=pre->next; p=pre->next; r=p; pre->next=null; //n 为单链表 L 的长度 // 参数错误返回假 // 查找第 i-1 个结点 pre //p 指向第 1 个逆置的结点 // 用 r 保存第 1 个逆置的结点 // 断开 84

9 第 3 章线性表 Ⅱ 链表 while(k<j && p!=null) // 将 p 结点到第 j 个结点采用头插法插入到 pre 结点之后 { k++; q=p->next; //q 临时保存 p 结点的后继结点 p->next=pre->next; pre->next=p; p=q; r->next=q; // 将第 j 个结点的后继结点连接到 r 结点之后 return true; 注意单链表结构中没有存放长度的地方, 有人在编程时假设头结点中存放了结点个数, 甚至直接用 L->length 表示长度, 这都是错误的 如果是在线编程, 程序可能会导致崩溃 ; 如果是面试或者笔试, 严厉的考官会直接判 0 分 面试题 3-11 对于一个带头结点的整数单链表, 以第 1 个结点为基准, 将所有小于其值的结点移动到它的前面, 将所有大于等于其值的结点移动到它的后面 解 :base 为基准值,pre 指向首结点,p 指向其后继结点 当 p NULL 时循环, 若 p->data<base, 通过 pre 结点将 p 结点删除, 并采用头插法插入到前面, 否则 pre p 同步向后面移动 对应的算法如下 : void Move(LinkNode *&L) { LinkNode *pre,*p; T base; if(l==null L->next==NULL) return; base=l->next->data; pre=l->next; p=pre->next; //base 存放基准值 while(p!=null) { if(p->data<base) // 若 p 结点值小于基准值 { pre->next=p->next; // 删除 p 结点, 其采用头插法插入到 L 中 p->next=l->next; L->next=p; p=pre->next; //p 继续指向 pre 结点的后继结点 { pre=p; //pre p 同步后移 p=pre->next; 85

10 直击招聘 程序员面试笔试 C 数据结构深度解析 面试题 3-12 单链表的分割: 将一个非空单链表中所有小于等于 x 的结点移动到所有大于 x 结点的前面 解法 1:pre 指向首结点,p 指向其后继结点 当 p NULL 时循环, 若 p->data x, 通过 pre 结点将 p 结点删除, 并采用头插法插入到前面, 否则 pre p 同步向后面移动 对应的算法如下 : void move1(linknode *&L,T x) { LinkNode *pre=l,*p=pre->next; while(p!=null) { if(p->data<=x) // 删除 p 结点, 其采用头插法插入到 L 中 { pre->next=p->next; p->next=l->next; L->next=p; p=pre->next; { pre=p; //pre p 同步后移 p=pre->next; 解法 2: 扫描单链表 L, 采用尾插法建立两个单链表 L 和 L1, 将所有小于等于 x 的结点插入到 L 中, 将所有大于 x 的结点插入到 L1 中, 最后将 L1 和 L1 链接起来 对应的算法如下 : void move2(linknode *&L,int x) { LinkNode *p=l->next,*r,*r1,*l1; r=l; L1=(LinkNode *)malloc(sizeof(linknode)); r1=l1; while(p!=null) { if(p->data<=x) // 将 p 结点链接到 L 的末尾 { r->next=p; r=p; { r1->next=p; r1=p; p=p->next; // 将 p 结点链接到 L1 的末尾 86

11 第 3 章线性表 Ⅱ 链表 r->next=l1->next; // 将 L1 链接在 L 的后面 r1->next=null; free(l1); 面试题 3-13 设计一个算法求非空单链表的中间位置结点 例如,(1,2,3,4,5) 的中间位置结点是 3( 元素个数为奇数 ), 而 (1,2,3,4) 的中间位置结点是 2( 元素个数为偶数 ) 解 : 采用快 慢两个指针 fast 和 slow, 初始时均指向头结点 当 fast NULL 且 fast->next NULL 时循环, 慢指针向后移动一个结点, 即 slow=slow->next, 快指针向后移动两个结点, 即 fast=fast->next->next 循环结束后,slow 指向的结点就是满足题目要求的中间位置结点 对应的算法如下 : LinkNode * Middle(LinkNode *L) { LinkNode *fast=l,*slow=l; while(fast!=null && fast->next!=null) { slow=slow->next; fast=fast->next->next; return slow; 面试题 3-14 单链表重新排列 1: 将一个非空单链表 (a 1,a 2,,a n,b 1,b 2,,b n ) 重新排列为 (a 1,b 1,a 2,b 2,,a n,b n ), 要求空间复杂度为 O(1) 解 : 在第 2 章中相同问题的数据序列是采用数组存储的, 最佳解决方法是高难度的完美洗牌算法, 这里采用单链表存储数据, 相应算法要简单得多 采用尾插法建新表 L,r 作为尾指针 p 指向 a 1 结点, 调用上一个面试题的算法求出中间结点 q,q=q->next 指向 b 1 结点, 当 q NULL 时循环, 依次将 p q 结点链接到新表的表尾 对应的算法如下 : void Rearrange1(LinkNode *&L) { LinkNode *p,*q,*r; if(l->next==null) return; r=l; //r 作为新链表的尾结点 p=l->next; //p 指向 a1 结点 q=middle(l); //q 指向中间结点 ( 这里单链表数据结点的个数是偶数 ) q=q->next; //q 指向 b1 结点 while(q!=null) { r->next=p;r=p; // 将 p 结点链接到新链表的表尾 p=p->next; r->next=q;r=q; // 将 q 结点链接到新链表的表尾 87

12 直击招聘 程序员面试笔试 C 数据结构深度解析 q=q->next; r->next=null; // 尾结点的 next 域置空 ( 尽管这里不需要, 但这样做是一个好习惯 ) 面试题 3-15 单链表重新排列 2: 将一个非空单链表 (a 1,a 2,,a n 1,a n ) 重新排列为 (a 1,a n,a 2,a n 1, ) 解 : 将原单链表 L 按中间结点拆分为两个单链表, 其中,L 中含前半部分结点,L1 含后半部分结点 ( 注意, 当 n 为偶数时, 两个单链表中的结点个数相同 ; 当 n 为奇数时,L 中比 L1 中多一个结点 ) 将 L1 逆置, 然后采用上一个面试题的方法产生最终的结果单链表 对应的算法如下 : void Split(LinkNode *&L,LinkNode *&L1) // 找中间位置的结点并分为两个单链表 { LinkNode *pmid; pmid=middle(l); // 求中间结点 L1=(LinkNode *)malloc(sizeof(linknode)); L1->next=pmid->next; pmid->next=null; void Rearrange2(LinkNode *&L) { LinkNode *p,*q,*l1,*r; Split(L,L1); Reverse(L1); p=l->next;q=l1->next; r=l; while(p!=null && q!=null) // 创建后半部分的带头结点的单链表 L1 // 断开 // 单链表重新排列 // 将 L 拆分 // 将 L1 逆置, 调用例 3-2 的算法 // 新表尾指针 { r->next=p;r=p; // 将 p 结点链接到新链表的表尾 p=p->next; r->next=q;r=q; q=q->next; if(p!=null) { r->next=p;r=p; r->next=null; free(l1); // 将 q 结点链接到新链表的表尾 // 考虑原 L 中元素个数为奇数的情况 // 尾结点的 next 域置空 面试题 3-16 设计一个算法, 判断一个非空单链表中存放的数据序列是否为回文 88

13 第 3 章线性表 Ⅱ 链表 解 : 采用递归和非递归两种解法, 这里非递归解法改变了原来的单链表 ( 如果不改变, 可以通过复制结点来实现 ), 而递归解法没有改变原来的单链表 非递归解法 : 找到中间结点, 将后半部分结点构成带头结点的单链表 L1, 将单链表 L1 逆置, 然后依次按结点顺序判断前半部分结点和后半部分结点的值是否相同 对应的算法如下 : bool Ispal1(LinkNode *L) { LinkNode *pmid,*p=l->next,*q,*l1; if(l->next==null L->next->next==NULL) return true; L1=(LinkNode *)malloc(sizeof(linknode)); pmid=middle(l); L1->next=pmid->next; Reverse(L1); pmid->next=l1->next; q=l1->next; free(l1); while(p!=pmid->next && q!=null) { if(p->data!=q->data) return false; p=p->next; q=q->next; return true; // 求中间结点 // 将后半部分结点构成带头结点的单链表 L1 // 将带头结点的单链表 L1 逆置 // 重新链接起来 // 依次按结点顺序判断 递归解法 : 先看另外一个例子, 逆向输出一个不带头结点的单链表的所有结点值 假设不带头结点的单链表结点值序列为 (a 1,a 2,,a n ), 设 f(l) 是逆向输出单链表 L 的所有结点值, 即 a n a n 1 a 2 a 1, 则 f(l->next) 是逆向输出, 结果为 a n a 2 对应的递归模型如下: f(l) 不做任何事情 f(l) f(l->next); 输出 L->data 当 L=NULL 时其他情况 对应的递归算法如下 : void Redisplay(LinkNode *L) { if(l==null) return; { Redisplay(L->next); printf("%d ",L->data); // 依次输出 a n a 2 a 1 89

14 直击招聘 程序员面试笔试 C 数据结构深度解析 注意, 上述函数的形参是值参, 不是引用参数 在递归调用 Redisplay(L->next) 之后, 第 1 次输出的是 a n ( 尾结点 ), 然后依次是 a n 1 a 1 对于本题, 求解函数是 f(left,right), 初始时 left right 均指向首结点, 一直调用 f(left,right->next), 让 right 指针指向尾结点, 按如图 3.3 所示的过程进行判断 其中,left 指针从左向右扫描一遍,right 从右向左扫描一遍, 显然不是高效的 那么能不能让 left 和 right 指针相遇时 ( 即 left==right 或者 left->next==right) 结束呢? 除非强制 ( 如用 exit 函数 ) 进行, 否则没有意义, 因为递归调用要找到尾结点, 总是需要 n-1 次递归调用 left right right->next a 1 a 2 a n 1 a n f(left,right->next):right 依次指向 a n a n-1 第 1 次出口 (right >next==null) 判断 : 若 left >data==right >data ( 即 a 1 ==a n ), 返回真, 否则返回假 第 2 次是 left=left >next, 若 left >data==right >data( 即 a 2 ==a n 1 ), 返回真, 否则返回假 图 3.3 f(left,right) 的求解过程 对应的递归算法如下 : bool Ispal2(LinkNode *&left,linknode *right)// 判断首指针为 left 的单链表是否为回文 { if(left==null) return true; if(right->next==null) { if(left->data!=right->data) return false; return true; { if(ispal2(left,right->next)) // 递归调用到 right 指向尾结点 { left=left->next; return(left->data==right->data?true:false); return false; 注意, 其中形参 left 是引用参数,right 是非引用参数 对于带头结点的单链表 L, 调 90

15 第 3 章线性表 Ⅱ 链表 用方式是 IsPal2(L->next,L->next) 面试题 3-17 两个整数序列 A=(a 1,a 2,,a m ) 和 B=(b 1,b 2,,b n ) 已经采用两个单链表存储, 设计一个算法, 判断序列 B 是否为序列 A 的连续子序列 解 : 先在 A 中找到与 B 中首结点值相等的结点 pa,pb 指向 B 的首结点, 然后比较两者对应的结点值是否相等, 若相等, 则同步后移, 如果 B 比较完毕, 说明 B 是 A 的连续子序列 ; 否则,pa 后移一个结点, 再采用相同的过程进行判断 对应的算法如下 : bool Subseq(LinkNode *A,LinkNode *B) { LinkNode *pa=a->next,*pb,*q; while(pa!=null) { pb=b->next; while(pa!=null && pa->data!=pb->data) // 找首结点值相等的结点 pa=pa->next; q=pa; while(q!=null && pb!=null && q->data==pb->data) { q=q->next; // 若对应的结点值相同, 则同步后移 pb=pb->next; if(pb==null) //B 序列比较完毕 return true; if(pa!=null) // 若 A 序列未遍历完, 则从下一个结点开始重复进行 pa=pa->next; return false; 面试题 3-18 求解荷兰国旗问题 设有一个条块序列, 每个条块为红 (0) 白 (1) 蓝(2)3 种颜色中的一种 假设该序列采用单链表存储, 设计一个时间复杂度为 O(n) 的算法, 使得这些条块按红 白 蓝的顺序排好, 即排成荷兰国旗图案 解 : 用 p 指针扫描单链表 L 的结点, 根据 p->data 值将该结点插入到 3 个单链表 L L1 和 L2(L1 和 L2 不带头结点 ) 中, 均采用尾插法建表, 最后将它们链接起来 对应的算法如下 : void HollandFlag(LinkNode *&L) { LinkNode *L1,L2,*r,*r1,*r2,*p; L1=NULL; L2=NULL; p=l->next; r=l; while(p!=null) 91

16 直击招聘 程序员面试笔试 C 数据结构深度解析 { if(p->data==0) // 遇到 0 结点 { r->next=p; // 将 p 结点链接到带头结点的单链表 L 中 r=p; if(p->data==1) // 遇到 1 结点 { if(l1==null) // 将 p 结点链接到不带头结点的单链表 L1 中 { L1=p; r1=p; { r1->next=p; r1=p; // 遇到 2 结点 { if(l2==null) // 将 p 结点链接到不带头结点的单链表 L2 中 { L2=p; r2=p; { r2->next=p; r2=p; p=p->next; r->next=r1->next=r2->next=null; r->next=l1; //L 的尾结点和 L1 的首结点链接起来 r1->next=l2; //L1 的尾结点和 L2 的首结点链接起来 面试题 3-19 编程找出两个非空无环单链表第 1 个相交的结点 解 :p q 指针指向两个单链表的首结点, 分别求出两个单链表的长度 m n, 让较长的链表先移动 m-n 个结点, 再逐个比较 p==q 是否成立 对应的算法如下 : LinkNode *SameNode(LinkNode *L1,LinkNode *L2) { LinkNode *p=l1->next,*q=l2->next; if(l1->next==null L2->next==NULL) return NULL; int m=listlength(l1); // 求 L1 的长度 int n=listlength(l2); // 求 L2 的长度 int k=0; 92

17 第 3 章线性表 Ⅱ 链表 if(m>n) { while(p!=null && k<m-n) //p 指针后移动 m-n 个结点 { p=p->next; k++; if(n>m) { while(q!=null && k<n-m) //q 指针后移动 n-m 个结点 { q=q->next; k++; while(p!=null && q!=null && p!=q) { p=p->next; //p q 同步后移 q=q->next; if(p!=null && q!=null) // 找到相交的结点 return p; return NULL; 面试题 3-20 给定一个无序的整数单链表, 假设所有结点值在 [1,100] 区间内, 删除其中结点值重复的结点 ( 多个结点值相同的结点仅保留一个 ), 要求时间复杂度为 O(n) 解 : 采用以空间换时间的方式, 定义一个标记数组 a, 初始时所有元素为 false,a[i]=true 表示结点值 i 是重复的, 对于重复的结点进行删除 对应的算法如下 : #define MAX 101 void Delsamenodes(LinkNode *&L) { bool a[max]; // 标记数组 LinkNode *pre,*p; if(l->next==null L->next->next==NULL) return; for(int i=0;i<max;i++) a[i]=false; pre=l; p=pre->next; while(p!=null) { if(!a[p->data]) //p 结点值不重复 { a[p->data]=true; // 修改标记元素 pre=p; //pre p 同步后移 93

18 直击招聘 程序员面试笔试 C 数据结构深度解析 p=p->next; //p 结点值重复 { pre->next=p->next; // 删除 p 结点 free(p); p=pre->next; 面试题 3-21 给定单链表的头指针和一个结点指针, 在 O(1) 时间内删除该结点 链表结点的定义如下 : struct ListNode { int m_nkey; ListNode * m_pnext; ; 函数的声明如下 : void DeleteNode(ListNode* plisthead,listnode* ptobedeleted); 解 : 由于结点类型是已知的, 当要删除的 ptobedeleted 结点不是尾结点时, 可以将后继结点的结点值复制到该结点中, 然后删除其后继结点, 时间为 O(1); 当要删除的 ptobedeleted 结点是尾结点时 ( 只有一种情况 ), 需要修改前驱结点的 m_pnext 指针域为 NULL, 只能通过从头到尾找到其前驱结点再进行修改, 时间为 O(n), 但平均起来时间复杂度仍然为 O(1), 即 [(n 1)O(1)+O(n)]/n=O(1) 对应的算法如下: void DeleteNode(ListNode* plisthead, ListNode* ptobedeleted) { ListNode *pre,*p; if(plisthead==null ptobedeleted==null) return; if(ptobedeleted->m_pnext!=null) //ptobedeleted 不是尾结点 { p=ptobedeleted->m_pnext; //p 指向其后继结点 ptobedeleted->m_nkey=p->m_nkey; ptobedeleted->m_pnext=p->m_pnext; free(p); { pre=plisthead; p=pre->m_pnext; while(p!=ptobedeleted) // 复制结点值 // 删除 p 结点 //ptobedeleted 是尾结点 // 查找 ptobedeleted 结点的前驱结点 pre { pre=p; //pre p 指针同步后移 94

19 第 3 章线性表 Ⅱ 链表 p=p->m_pnext; pre->m_pnext=null; free(ptobedeleted); // 删除 ptobedeleted 结点 面试题 3-22 编程求一个非空单链表中倒数的第 k 个结点 解 : 采用递归和非递归两种解法, 这里非递归解法改变了原来的单链表 ( 如果不改变, 可以采用复制结点来实现 ), 而递归解法没有改变原来的单链表 非递归解法 : 倒数第 k 个结点即为正数第 n-k+1 个结点 定义两个指针变量 p 和 q, 初始时均指向头结点 首先 p 指针沿链表移动找到第 k 个结点 ( 前面有 k-1 个结点 ), 然后 p q 指针同步向后移动, 当 p 指针为空时 ( 此步骤中 p 走了 n-k+1 个结点, 相应地 q 从头开始也走了 n-k+1 个结点 ),q 指针所指的结点就是倒数的第 k 个结点 对应的算法如下 : LinkNode *Searchk1(LinkNode *L,int k) { LinkNode *p=l,*q=l; int count=0; while(p!=null && count<k) // 查找第 k 个结点 p { count++; p=p->next; if(p==null) // 没有时返回空, 表示没找到 return NULL; { while(p!=null) //p 和 q 同步后移直到 p=null { q=q->next; p=p->next; return q; 递归解法 : 设 f(l,k,i) 的功能是返回不带头结点单链表 L 中倒数的第 k 个结点 (i 用于全局计数倒数的第几个结点, 从 0 开始 ), 它是大问题 ;f(l->next,k,j) 是 小问题, 显然有 i=j+1, 当 i==k 时表示找到了倒数的第 k 个结点 递归模型如下 : f(l,k,i)=null f(l,k,i)=l f(l,k,i)=p 当 L=NULL 时 若 p=f (L->next,k,i), 有 i+1=k 成立 其他情况 对应的递归算法如下 : 95

20 直击招聘 程序员面试笔试 C 数据结构深度解析 LinkNode *Searchk2(LinkNode *L,int k,int &i) { LinkNode *p; if(l==null) return NULL; p=searchk2(l->next,k,i); i++; if(i==k) return L; return p; // 求倒数的第 k 个结点 // 空表返回 NULL 调用上述递归函数的方式是 int i=0;p=searchk2(l->next,k,i) 若 p=null, 表示单链表 L 中没有倒数的第 k 个结点, 否则 p 指向的就是倒数的第 k 个结点 面试题 3-23 编程删除一个递增有序单链表中值重复的结点, 所有值相同的结点仅保留一个 解 : 由于是有序表, 所有相同值域的结点都是相邻的 用 p 扫描递增单链表, 若 p 结点的值域等于其后结点的值域, 则删除后者 对应的算法如下 : void Delsamenode(LinkNode *&L) { LinkNode *p=l->next,*q; while(p->next!=null) { if(p->data==p->next->data) // 找到重复值的结点 { q=p->next; //q 指向这个重复值的结点 p->next=q->next; free(q); p=p->next; // 删除 q 结点 面试题 3-24 有一个递增有序单链表 L1 和一个递减有序单链表 L2, 将它们所有结点合并为一个递增有序单链表 L3, 要求空间复杂度为 O(1) 解 : 先将单链表 L2 的所有结点逆置变为递增的, 然后采用二路归并算法由两个递增有序单链表 L1 L2 合并为 L3 由于要求空间复杂度为 O(1), 不能进行结点的复制 对应的算法如下 : void Merge(LinkNode *&L1,LinkNode *&L2,LinkNode *&L3) { LinkNode *p,*q,*r; Reverse(L2); p=l1->next; // 将单链表 L2 逆置, 调用例 3-2 的算法 q=l2->next; L3=(LinkNode *)malloc(sizeof(linknode)); 96

21 第 3 章线性表 Ⅱ 链表 r=l3; while(p!=null && q!=null) { if(p->data<q->data) { r->next=p;r=p; // 将较小的 p 结点链接到 L3 的末尾 p=p->next; { r->next=q;r=q; // 将较小的 q 结点链接到 L3 的末尾 q=q->next; if(p!=null) r->next=p; // 将 L1 没有扫描完的结点链接到 L3 的末尾 if(q!=null) r->next=q; // 将 L2 没有扫描完的结点链接到 L3 的末尾 free(l1);l1=null; free(l2);l2=null; 面试题 3-25 编程求两个递增有序单链表 L1 L2 的公共结点构成的单链表 L3, 要求不改变单链表 L1 和 L2 解 : 由于两个单链表是递增有序的, 可以采用二路归并算法提高求公共结点的效率, 结果单链表 L3 采用尾插法建表 因为题目要求不改变单链表 L1 和 L2, 所以公共结点采用复制的方法 对应的算法如下 : void InterList(LinkNode *L1,LinkNode *L2,LinkNode *&L3) { LinkNode *p=l1->next,*q=l2->next,*s,*r; L3=(LinkNode *)malloc(sizeof(linknode)); // 建立 L3 的头结点 r=l3; //r 始终指向单链表 L3 的尾结点 while(p!=null && q!=null) { if(p->data<q->data) p=p->next; if(p->data>q->data) q=q->next; // 公共结点 { s=(linknode *)malloc(sizeof(linknode)); s->data=p->data; // 建立一个新结点 r->next=s; r=s; p=p->next; q=q->next; 97

22 直击招聘 程序员面试笔试 C 数据结构深度解析 r->next=null; // 将尾结点的 next 域置为 NULL 面试题 3-26 用单链表表示集合, 假设所有单链表中的元素是递增有序的, 设计一个算法求两个单链表 L1 L2 表示的集合的差集 L3 即 L3=L1 L2, 要求不改变单链表 L1 和 L2 解 : 由于两个单链表是递增有序的, 可以采用二路归并算法提高求差集的效率, 并且差集 L3 的结点只能来源于 L1 的结点, 结果单链表 L3 采用尾插法建表 因为题目要求不改变单链表 L1 和 L2, 所以 L3 的结点采用复制的方法 对应的算法如下 : void Difference(LinkNode *L1,LinkNode *L2,LinkNode *&L3) { LinkNode *p=l1->next,*q=l2->next,*s,*r; L3=(LinkNode *)malloc(sizeof(linknode)); r=l3; while(p!=null && q!=null) { if(p->data<q->data) // 只将 L1 中大的元素添加到 L3 中 { s=(linknode *)malloc(sizeof(linknode)); s->data=p->data; r->next=s;r=s; p=p->next; if(p->data>q->data) q=q->next; // 跳过 L2 中较大的元素 // 公共元素不能添加到 L3 中 { p=p->next; q=q->next; while(p!=null) // 若 L1 未遍历完, 将余下的所有元素添加到 L3 中 { s=(linknode *)malloc(sizeof(linknode)); s->data=p->data; r->next=s;r=s; p=p->next; r->next=null; 面试题 3-27 编程高效地将 3 个递增有序单链表的所有结点归并为一个递增有序单链表, 要求空间复杂度为 O(1) 解 : 其思路参见例 个有序单链表用 L[3] 指针数组标识, 段号分别为 0~2, 用 p[3] 指针数组扫描它们的结点,x[3] 数组存放 3 个段当前要比较的结点值, 当段 i 扫描完毕, x[i] 取值 对应的完整程序如下: 98

23 第 3 章线性表 Ⅱ 链表 #include "LinkList.cpp" #define INF int Min(T x[],int k) { int i,mink=0; for(i=1;i<k;i++) if(x[i]<x[mink]) mink=i; // 包含单链表的基本运算算法 // 定义 // 通过简单比较找到最小元素的段号 if(x[mink]==inf) // 若最小元素为, 返回 -1 return -1; return mink; void Merge3(LinkNode *L[3],LinkNode *&L1) { LinkNode *p[3],*r,*s; int mink,i; T x[3]; L1=(LinkNode *)malloc(sizeof(linknode)); r=l1; for(i=0;i<3;i++) p[i]=l[i]->next; for(i=0;i<3;i++) x[i]=(p[i]!=null)?p[i]->data:inf; while(true) // 三路归并算法 //r 为结果单链表的尾结点指针 //p[i] 指向 L[i] 单链表的首结点 // 将 3 个有序单链表的首结点值复制到数组 x 中 { mink=min(x,3); // 求出最小结点值的段号 if(mink==-1) break; // 全部归并完毕, 退出循环 { s=(linknode *)malloc(sizeof(linknode)); r->next=null; s->data=x[mink]; r->next=s;r=s; void main() { LinkNode *h[3],*h1; // 将最小结点值复制并链接到 L1 的表尾 p[mink]=p[mink]->next; // 后移较小结点的扫描指针 x[mink]=(p[mink]!=null)? p[mink]->data:inf; T a[]={1,4,7,10; int n=sizeof(a)/sizeof(a[0]); T b[]={2,5,8; // 将尾结点的 next 域置为 NULL // 重新取该结点值 99

24 直击招聘 程序员面试笔试 C 数据结构深度解析 int m=sizeof(b)/sizeof(b[0]); T c[]={3,6,9; int k=sizeof(c)/sizeof(c[0]); CreateListR(h[0],a,n); printf("h[0]: ");DispList(h[0]); CreateListR(h[1],b,m); printf("h[1]: ");DispList(h[1]); CreateListR(h[2],c,k); printf("h[2]: ");DispList(h[2]); printf(" 三路归并产生 h1\n"); Merge3(h,h1); printf("h1: ");DispList(h1); for(int i=0;i<3;i++) // 销毁单链表 DestroyList(h[i]); DestroyList(h1); 程序的执行结果如图 3.4 所示 图 3.4 三路归并算法的执行结果 面试题 3-28 将 N 个长度均为 M 的有序链表进行合并, 合并以后的链表也保持有序, 时间复杂度为 ( ) A.O(N M log 2 N) B.O(N M) C.O(N) D.O(M) 答 : 采用 N 路归并思路, 在 N 个结点中查找最小结点可以采用堆或者败者树结构 ( 时间复杂度为 O(log 2 N)),N M 个结点均扫描一次, 所以总时间为 O(N M log 2 N) 答案为 A 面试题 3-29 要对一个单链表排序, 限制如下 : 平均时间复杂度是 O(nlog 2 n), 并且要避免最坏的 O(n 2 ) 情况, 空间复杂度是 O(1) 你能不能设计这样的算法对其进行排序? 答 : 能 数据序列采用单链表存储, 而无法对链表随机访问, 快速排序的效果并不好, 堆排序也是无法实现的, 可以采用二路归并排序 100

25 第 3 章线性表 Ⅱ 链表 3.3 双链表算法设计 要点归纳 双链表中的每个结点包含两个分别指向前驱结点和后继结点的指针域 双链表中结点的类型声明如下 : typedef struct node { T data; struct node *prior; struct node *next; DLinkNode; // 前驱结点指针 // 后继结点指针 因此, 与单链表相比, 在双链表中查找某个结点的前驱结点和后继结点都很方便 正因为如此, 删除第 i 个结点可以直接找到该结点, 通过修改其前 后结点的 4 个指针域来实现删除操作 很多双链表的算法设计与单链表类似, 只是插入和删除操作有所不同 面试题解析 面试题 3-30 与单链表相比, 双链表的优点之一是 ( ) A. 更节省存储空间 B. 便于进行随机访问 C. 更容易访问相邻结点 D. 可以省略头指针和尾指针答 : 双链表中的每个结点都有前 后指针, 所以更容易访问前 后相邻结点 答案为 C 面试题 3-31 有一个用双链表存放的整数序列, 你能不能设计时间复杂度为 O(nlog 2 n) 的算法对其进行排序? 答 : 能, 可以采用快速排序或者二路归并排序算法 面试题 3-32 设计一个算法由一个双链表 A 复制产生另外一个双链表 B 答 : 这里提供非递归和递归两种解法 非递归解法 : 扫描双链表 A 的所有结点, 通过复制来创建双链表 B 的结点, 并采用尾插法将这些结点链接起来 对应的算法如下 : void Copy1(DLinkNode *A,DLinkNode *&B) // 由双链表 A 产生双链表 B { DLinkNode *pa=a->next,*pb,*r; B=(DLinkNode *)malloc(sizeof(dlinknode)); r=b; 101

26 直击招聘 程序员面试笔试 C 数据结构深度解析 while(pa!=null) // 一边扫描 A 的结点 pa 一边复制 { pb=(dlinknode *)malloc(sizeof(dlinknode)); pb->data=pa->data; r->next=pb; pb->prior=r; r=pb; pa=pa->next; r->next=null; // 复制 pb 结点 // 将 pb 结点链接到 B 的末尾 // 将尾结点的 next 域置为 NULL 递归解法 : 若 pa 是双链表 A 的首指针, 首先创建双链表 B 的头结点 hb 由 pa 创建 B 的递归模型如下 : f(pa,hb,pb) pb=null 当 pa=null 时 f(pa,hb,pb) 由 pa 结点复制产生 pb 结点 ; 当 pa=null 时让 pb 结点的 prior 指向 hb 结点 ; 对应的递归算法如下 : f(pa->next,pb,pb->next); void copy(dlinknode *pa,dlinknode *hb,dlinknode *&pb) { if(pa==null) pb=null; { pb=(dlinknode *)malloc(sizeof(dlinknode)); pb->data=pa->data; pb->prior=hb; copy(pa->next,pb,pb->next); void Copy2(DLinkNode *A,DLinkNode *&B) // 由双链表 A 产生双链表 B { B=(DLinkNode *)malloc(sizeof(dlinknode)); copy(a->next,b,b->next); 面试题 3-33 有一个不带头结点的双链表, 其每个结点包含两个指针 next 和 prior, 其中指针 next 指向下一个结点, 指针 prior 也指向一个结点, 沿 next 可以像普通链表一样完成顺序遍历, 沿 prior 可能会有重复, 即两个不同结点的 prior 指针可能指向同一个结点 设计一个算法复制该双链表 解 : 这称为含随机指针的双链表复制, 需要采用特殊方法复制 其步骤如下 : 通过 next 指针从头结点 first 出发扫描全部结点 ( 不考虑 prior 指针 ), 对于每个结点复制一个新结点并插入到其后面, 例如 first=(1,2,3), 这样做后改变为 first=(1,1',2,2',3,3'), 其中 1' 表示结点 1 复制产生的结点 对应的算法如下 : 102

27 第 3 章线性表 Ⅱ 链表 void CreateSame(DLinkNode *&first) { DLinkNode *p=first,*q; while(p!=null) { q=(dlinknode *)malloc(sizeof(dlinknode)); q->data=p->data; q->next=p->next; p->next=q; p=p->next->next; // 复制结点作为后继结点 // 由 p 结点复制产生 q 结点 // 将 q 结点链接到 p 结点之后 考虑 prior 指针 从头结点 first 出发扫描原来双链表的全部结点, 修改其后继结点的 prior 指针 例如, 对于结点 1, 求出其 prior, 即 1.prior, 假设 1.prior 为结点 3( 结点 3 的后继结点是结点 3', 即 3.next), 则将 p->next( 结点 2') 的 prior 指针修改为 3.next 对应的算法如下 : void Updateprior(DLinkNode *&first) { DLinkNode *p=first,*q; // 修改新结点的 prior 指针 while(p!=null) { q=p->prior; // 求出 p->prior, 它指向 q 结点 p->next->prior=q->next; // 将 p 结点之后的新结点的 prior 修改为 q->next p=p->next->next; 分离出结果双链表 second 扫描 first 的所有结点, 采用尾插法建立新 first 和 second 两个链表, 即恢复 first 为初始状态,second 为复制后的结果双链表 对应的算法如下 : void CreateCopy(DLinkNode *&first,dlinknode *&second) // 产生结果双链表 second { DLinkNode *p=first->next->next; //p 指向第 3 个结点 DLinkNode *r1,*r2; r1=first; //r1 为 first 链表的尾结点指针 second=first->next; //second 指向第 2 个结点 r2=second; //r2 为 second 链表的尾结点指针 while(p!=null) { r1->next=p;r1=p; // 将 p 结点链接到 first 链表的表尾 p=p->next; r2->next=p;r2=p; // 将 p 结点链接到 second 链表的表尾 p=p->next; r1->next=r2->next=null; // 将尾结点的 next 域置为 NULL 完成题目功能的算法如下 : 103

28 直击招聘 程序员面试笔试 C 数据结构深度解析 void Copy(DLinkNode *first,dlinknode *&second) { CreateSame(first); Updateprior(first); CreateCopy(first,second); 3.4 循环链表算法设计 要点归纳 循环链表分为循环单链表和循环双链表, 前者包含一个环, 后者包含两个环, 所以都可以从任意结点出发访问其他所有结点 循环链表算法设计的关键是判断尾结点, 对于带头结点的循环链表 L,p->next==L 成立时表示 p 结点是尾结点 有些考试题中的循环链表并非总是将尾结点的 next 域指向头结点, 需要根据题意来判断 面试题解析 面试题 3-34 在( ) 中, 只要指出表中任何一个结点的位置, 就可以从它出 发依次访问到表中的其他所有结点 A. 单链表 B. 双链表 C. 循环单链表 D. 循环双链表 答 : 在循环单链表和循环双链表中都有环路, 可以从链表中的任何一个结点出发依次 访问到表中的其他所有结点 答案为 C D 面试题 3-35 在一个带头结点的循环双链表中插入一个新结点( 非尾结点 ), 需要 修改的指针域的数量是 ( ) A.2 个 B.6 个 C.3 个 D.4 个 答 : 和非循环双链表一样, 在循环双链表中插入一个新结点 ( 非尾结点 ) 也需要修改 4 个指针域 答案为 D 面试题 3-36 阅读下列函数说明和 C 代码, 将应填进 (n) 处的子句写在答题 纸的对应栏内 算法功能说明 : 设有一个带表头结点的双向循环链表 L, 每个结点有 4 个数据成员, 即指向先驱结点的指针 prior 指向后继结点的指针 next 存放数据的成员 data 和访问频度 freq 所有结点的 freq 初始时都为 0 每当在链表上进行一次 Locate(x) 时令元素值 x 的结点的访问频度 freq 加 1, 104

29 第 3 章线性表 Ⅱ 链表 并将该结点前移, 链接到目前它的访问频度相等的结点的后面, 使得链表中的所有结点保持按访问频度递减的顺序排列, 以使频繁访问的结点总是靠近表头 实现上述功能的函数如下 : // 结点类型 NodeType 声明 void Locate(NodeType *first,int x) { NodeType *p=first->next; while(p!=first && (1) ) p=p->next; // 查找 data 域为 x 的结点 if(p!=first) // 找到 data 域为 x 的结点 p { (2); // 修改结点 p 的 freq 域 NodeType *current=p; //current 指向 p 结点 current->prior->next=current->next; // 将 current 结点删除 current->next->prior=current->prior; p=current->prior; while(p!=first && (3) ) p=p->prior; // 向前查找 freq 值小于等于 current->freq 的结点 p current->next=(4); // 将 current 结点插入到 p 结点的后面 current->prior=p; p->next->prior=current; p->next=(5); printf("sorry. Not find!\n"); // 没找到 data 域为 x 的结点 答 : 参考代码注释 ( 由作者增加的 ) 理解函数功能, 对应的答案如下 (1) p->data!=x (2) p->freq++ (3) current->freq>p->freq (4) p->next (5) current 面试题 3-37 设计一个算法判断一个带头结点的单链表中是否有环 例如, N1 N2 N3 N4 N5 N2 是一个有环的链表, 环的入口处是 N2 结点 解 : 这里所谓的有环, 并非像一般的循环单链表那样总是尾结点的 next 指向头结点 设置一个快指针 fast 和一个慢指针 slow, 首先它们都指向头结点 然后 fast 每次移动两个结点,slow 每次移动一个结点 如果单链表 L 中有环, 则一定会出现 fast=slow 的情况 ( 就像两个人在操场的环形跑道上跑步, 从同一起点出发, 一个人跑得快, 另外一个人跑得慢, 这样一直跑下去, 他们后面一定会相遇的 ) 如果单链表 L 中没有环, 则一定不会出现 fast=slow 的情况, 所以可以通过判断 105

30 直击招聘 程序员面试笔试 C 数据结构深度解析 fast=slow 是否成立来确定单链表 L 中是否有环 对应的算法如下 : bool Cycle(LinkNode *L) { LinkNode *fast=l,*slow=l; while(fast!=null && fast->next!=null) { fast=fast->next->next; slow=slow->next; if(slow==fast) return true; return false; // 判断单链表 L 中是否存在环 面试题 3-38 求一个有环单链表 L 的环的入口处 解 : 设置一个快指针 fast 和一个慢指针 slow, 首先它们都指向头结点 然后 fast 每次移动两个结点,slow 每次移动一个结点 设整个单链表的长度为 len, 环的长度为 l, 从起点到环入口处的距离为 a, 环入口处与相遇处的距离为 b 当 fast 和 slow 相遇时,fast 已经在环内走了 n 圈 (n 1), 假设 slow 走了 s 步, 则 fast 走了 2s 步, 而 fast 的步数等于 s 加上环内多走的 n 圈, 所以有 : 2s=s+nl 即 s=nl 显然,s=a+b=nl=(n-1)l+l=(n-1)l+(len-a), 也就是 a=(n-1)l+(len-a-b) 而 len-a-b=l-b, 这样有 a=(n-1)l+l-b 而 l-b 恰好是相遇处与环入口处的距离, 也就是说, 从起点到环入口处的距离 a 等于在环内转了 n-1 圈后相遇处与环入口处的距离 l-b, 这样, 当到达相遇处时只需要再走 a 个结点即到达环入口处 为此, 当找到相遇处 slow 时设置一个 p 指针 ( 初始为 L), 让 p slow 同步后移, 当它们指向同一个结点时这个结点就是环入口处 图 3.5 所示为一个求有环单链表的环入口处的示例, 其中数据结点个数为 11, 环入口处为 4, 相遇处为 8 a= 环入口处 11 5 l-b= b= 相遇处 图 3.5 求有环单链表的环入口处的示例 106

31 第 3 章线性表 Ⅱ 链表 由上述原理得到的算法如下 : LinkNode *Findcycle(LinkNode *L) { LinkNode *fast=l,*slow=l,*p; while(fast!=null && fast->next!=null) { fast=fast->next->next; slow=slow->next; if(slow==fast) { p=l; while(p!=slow) { p=p->next; return NULL; slow=slow->next; return slow; // 返回有环单链表 L 的环入口结点 // 找到相遇处 //p slow 指向同一个结点时即为入口处 面试题 3-39 有一个双链表, 其中某个结点的一个指针指错了, 现要编写一个程序将错误的指针修改过来, 请你说明该程序的思路 答 : 这样的双链表一定是循环双链表, 否则是无法解决的 例如, 若是非循环双链表, 其中一个结点的 next 指针出错, 那么就无法遍历后面的结点, 显然就无法改正错误 当该链表是循环双链表时, 解决思路如下 : 找到出错的结点, 这个错了的指针有两种情况 :next 没有指向正确的后继结点或者 prior 没有指向正确的前驱结点 先通过 next 指针从头结点开始遍历, 通过异常检测语句抛出异常, 如果捕获到某个结点有异常, 说明是该结点的 next 指针有异常 ; 如果没有异常, 再对 prior 指针采用相同方式进行 假设确定 q 结点的 prior 指针出错, 通过 pre p 指针从头结点开始沿 next 指针找到 q 结点 (pre 是 p 的前驱结点 ), 将 q 结点的 prior 指针改为指向 pre 结点即可 假设确定 q 结点的 next 指针出错, 通过 p pnext 指针从头结点开始沿 prior 指针找到 q 结点 (pnext 是 p 的后继结点 ), 将 q 结点的 next 指针改为指向 pnext 结点即可 面试题 3-40 有一个循环双链表, 其结点类型如下 : typedef struct node { int data; struct node *prior,*next; DLinkNode; 现有两个循环双链表 A B, 知道其头指针为 pheada 和 pheadb, 请写一函数将两链 107

32 直击招聘 程序员面试笔试 C 数据结构深度解析 表中 data 值相同的所有结点删除 解 : 这里提供两种条件下的两个解法 解法 1: 如果题目要求在两个循环双链表 A B 中删除 data 值相同的所有结点后剩下结点的相对顺序不变, 例如 A=(7,2,3,2,3,3,4) B=(2,5,2,3,8,5,3), 删除后有 A=(7,4) B=(5,8,5), 采用逐个查找判断方法, 对于 A 中某个 data 值为 value 的结点, 在链表 B 中查找是否存在相同值的结点, 若有, 删除链表 B 中所有 data 值为 value 的结点, 同时删除链表 A 中所有 data 值为 value 的结点 对应的算法如下 : bool DeteleNode(DLinkNode *&pheader,int value) // 在循环双链表 pheader 中查找值为 value 的结点并删除, 若有这样的结点返回真, 否则返回假 { bool flag=false; DLinkNode *pre=pheader,*p=pre->next; while(p!=pheader) // 循环删除所有值为 value 的结点 { if(p->data==value) // 找到值为 value 的结点 { flag=true; pre->next=p->next; p->next->prior=pre; free(p); p=pre->next; // 删除 p 指向的结点 { pre=p; //pre p 指针同步后移 return flag; p=p->next; void Delsamenodes1(DLinkNode *&pheada,dlinknode *&pheadb) { int value; // 删除两个链表中相同的结点 if(pheada->next==pheada pheadb->next==pheadb) return; // 其中有一个空表时直接返回 DLinkNode *pre=pheada,*p=pre->next; DLinkNode *preq,*q; while(p!=pheada) { value=p->data; if(detelenode(pheadb,value)) { preq=pre;q=p; while(q!=pheada) { if(q->data==value) // 扫描 A 的结点 p //p 指向的结点 B 中存在相同值结点 // 删除 A 中所有这样的结点 108

33 第 3 章线性表 Ⅱ 链表 { preq->next=q->next; q->next->prior=preq; free(q); q=preq->next; { preq=q; //preq q 指针同步后移 q=q->next; p=pre->next; { pre=p; //pre p 指针同步后移 p=p->next; 若循环双链表 A B 的长度分别为 m n, 上述算法的时间复杂度为 O(m(n+m)) 解法 2: 如果没有解法 1 的要求, 即删除 data 值相同的所有结点后剩下结点的相对顺序可以改变, 可以先对两个循环双链表 A B 进行排序, 然后采用二路归并思路找相同的结点并删除 例如 A=(7,2,3,2,3,3,4) B=(2,5,2,3,8,5,3), 删除后有 A=(4,7) B=(5,5,8) 对应的算法如下 : void Sort(DLinkNode *&L) // 循环双链表递增排序 { DLinkNode *p=l->next->next,*q,*pre; L->next->next=L; // 建立只有一个结点的循环双链表 L->prior=L->next; while(p!=l) { q=p->next; pre=l; while(pre->next!=l && pre->next->data<p->data) pre=pre->next; // 在 L 中查找有序插入 p 结点的位置 p->next=pre->next; // 将 p 结点插入到 pre 结点之后 pre->next->prior=p; pre->next=p; p->prior=pre; p=q; void Delsamenodes2(DLinkNode *&pheada,dlinknode *&pheadb) 109

34 直击招聘 程序员面试笔试 C 数据结构深度解析 { int value; DLinkNode *prea,*pa,*preb,*pb; Sort(pHeadA); Sort(pHeadB); prea=pheada; pa=prea->next; preb=pheadb; pb=preb->next; while(pa!=pheada && pb!=pheadb) { if(pa->data<pb->data) { prea=pa; pa=pa->next; if(pa->data>pb->data) { preb=pb; pb=pb->next; { value=pa->data; while(pa!=pheada) { if(pa->data==value) { prea->next=pa->next; pa->next->prior=prea; free(pa); pa=prea->next; break; while(pb!=pheadb) { if(pb->data==value) { preb->next=pb->next; pb->next->prior=preb; free(pb); pb=preb->next; break; // 删除两个链表中相同的结点 //pa->data==pb->data // 删除 A 中相同的结点 // 删除 B 中相同的结点 上述排序算法采用的是直接插入排序, 时间复杂度为 O(n 2 ) 若循环双链表 A B 的长度分别为 m n, 上述算法的时间复杂度为 O(m 2 +n 2 ) 可以采用快速排序将排序时间降低为 110

35 第 3 章线性表 Ⅱ 链表 O(nlog 2 n), 这样上述算法的时间复杂度为 O(mlog 2 m+nlog 2 n) 面试题 3-41 有一个链表, 其每个结点包含两个指针 p1 和 p2, 其中指针 p1 指向下一个结点, 指针 p2 也指向一个结点, 沿 p1 可以像普通链表一样完成顺序遍历, 沿 p2 可能会有重复 一种可能的例子如图 3.6 所示, 其中实线箭头是 p1 指针, 虚线箭头是 p2 指针 头指针 图 3.6 一个链表结构示例 链表结点的数据类型如下 : struct Node { Node * p1; ; Node * p2; int data; 设计函数, 翻转这个链表, 并返回头指针 函数定义是 Node * Revert(Node* head) 解法 1: 如果对这道题有不清楚的地方, 需要跟面试官交流, 例如 沿 p2 可能会有重复 是什么意思, 每个结点的 p2 指针是否指向唯一结点 如果两个不同结点 a b 的 p2 指针指向同一个结点 c, 那么翻转后 c 结点的 p2 指针指向 a 结点还是 b 结点? 这里假设 p2 指针是一个循环指针, 从头结点出发可以遍历到头结点结束 ( 题目给定的图就是这种情况 ) 在这种假设的前提下,p1 的翻转就是像单链表那样将 p1 指针逆置, p2 的翻转就是像循环单链表那样将 p2 指针逆置 对应的算法如下 : void Reversep1(Node *&L) { Node *p=l->p1,*q; L->p1=NULL; while(p!=null) // 逆置 p1 指针 // 建立一个空链表 { q=p->p1; //q 临时保存 p1 方向的后继结点 p->p1=l->p1; L->p1=p; p=q; void Reversep2(Node *&L) { Node *p=l->p2,*q; // 将 p 结点插入到首部 // 逆置 p2 指针 111

36 直击招聘 程序员面试笔试 C 数据结构深度解析 L->p2=L; while(p!=l) // 建立一个空循环链表 { q=p->p2; //q 临时保存 p2 方向的后继结点 p->p2=l->p2; L->p2=p; p=q; Node *Revert(Node* head) { if head==null head->p1==null) return NULL; Reversep1(head); Reversep2(head); return head; // 将 p 结点插入到首部 // 翻转链表 head 并返回头指针 // 逆置 p1 指针 // 逆置 p2 指针 解法 2: 如果 p2 指针不是一个循环指针, 但每个结点的 p2 指针指向唯一结点, 此时无法通过 p2 指针遍历所有结点, 为此设计一个 map 容器 mymap, 在通过 p1 指针遍历链表时将当前结点 p 的 p->prior 和 p 地址值保存在 mymap 中, 遍历结束后对 mymap 中所有的元素执行操作 it->first->p2=it->second, 以实现 p2 指针的逆置 对应的算法如下 : #include <map> using namespace std; void Reverse(Node *&L) { map<node *,Node *> mymap; Node *p=l->p1,*q; // 逆置 p1 p2 指针 L->p1=NULL; // 建立一个空链表 mymap.insert(pair<node *,Node *>(p->p2,p)); while(p!=null) // 用尾插法逆置 p1 { mymap.insert(pair<node *,Node *>(p->p2,p)); q=p->p1; p->p1=l->p1; L->p1=p; p=q; map<node *,Node *>::iterator it; //q 临时保存 p1 方向的后继结点 // 将 p 结点插入到首部 // 逆置 p2 指针 for(it=mymap.begin();it!=mymap.end();++it) it->first->p2=it->second; 面试题 3-42 如何判断两个循环链表是否相等? 例如 "aabbcc" 和 "ccaabb" 是相等的, 请给出思路 112

37 第 3 章线性表 Ⅱ 链表 答 : 设 s=xy, 其中 x y 为循环链表中的连续子序列, 若 t=yx, 现在判断 t 是否与 s 相等 采用的方法是将循环链表 s 复制一份并链接在后面, 即 ss=xyxy, 若 t 与 s 相等, 则 t 一定是 ss 的子连续序列 所以相应的判断条件为若 t 是 ss 的子连续序列, 则 t 与 s 相等, 否则 t 与 s 不相等 例如,s="aabbcc",t="ccaabb",ss="aabbccaabbcc", 显然 t 是 s 的子连续序列, 所以 t 与 s 相等 3.5 自测题和参考答案 自测题 3-1 在一个带头结点的单链表 HL 中, 若要在第 1 个元素之前插入一个由指针 p 指向 的结点, 则执行 ( ) A.p->next=HL; p=hl; B.p->next=HL; HL=p; C.p->next=HL->next; HL->next=p; D.HL=p; p->next=hl; 3-2 在双向链表中有两个指针域,prior 和 next 分别指向前驱和后继, 设 p 指向链表 中的一个结点, 现要求删去 p 所指的结点 ( 假设链表中的结点数大于 2,p 不是尾结点 ), 则正确的删除方法是 ( ) A.p->prior->next=p->prior; p->prior->next=p->next; free(p); B.free(p);p->prior->next=p->prior; p->prior->next=p->next; C.p->prior->next=p->prior; free(p); p->prior->next=p->next; D. 以上 A B C 都不对 3-3 对于双向循环链表, 每个结点有两个指针域 next 和 prior, 分别指向前驱和后继 结点 在 p 指针所指向的结点 (p 结点不是尾结点 ) 之后插入 s 指针所指结点的操作应为 ( ) A.p->next=s; p->next->prior=s;s->prior=p; s->next=p->next; B.s->prior=p; s->next=p->next ; p->next=s; p->next->prior=s; C.p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; D.s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; 3-4 设一个链表最常用的操作是在末尾插入结点和删除尾结点, 则选用 ( ) 最节 省时间 A. 单链表 B. 单循环链表 C. 带尾指针的单循环链表 D. 带头结点的双循环链表 113

38 直击招聘 程序员面试笔试 C 数据结构深度解析 3-5 有一个长度为 100 的循环链表, 指针 A 和指针 B 指向了链表中的同一个结点,A 以步长为 1 向前移动,B 以步长为 3 向前移动, 一共需要同时移动 ( ) 步 A 和 B 才能 再次指向同一个结点 A.99 B.100 C.101 D.49 E.50 F 以下关于单向链表的说法正确的是 ( ) A. 如果两个单向链表相交, 那么它们的尾结点一定相同 B. 快 慢指针是判断一个单向链表有没有环的一种方法 C. 有环的单向链表跟无环的单向链表不可能相交 D. 如果两个单向链表相交, 那么这两个链表都一定不存在环 3-7 设计一个算法删除单链表中倒数的第 k 个结点 3-8 设计一个算法将一个单链表递增排序 3-9 已知带头结点的循环单链表 L 中至少有 3 个结点, 每个结点的两个域为 data 和 next, 其中 data 的类型为整型 设计一个算法判断该链表中的每个结点值是否小于其后续 两个结点值之和, 若满足, 返回 true, 否则返回 false 3-10 已知单链表 L( 带头结点 ) 是一个递增有序表, 试写一个高效算法, 删除表中 值大于 min 且小于 max 的结点 ( 若表中有这样的结点 ), 同时释放被删结点的空间, 这里 min 和 max 是两个给定的参数 请分析你的算法的时间复杂度 3-11 有两个递减有序单链表 a 和 b( 每个单链表中不含相同的元素 ), 将它们看成是 两个集合, 设计一个高效算法求 a 和 b 的差集, 要求不破坏 a b 单链表 3-12 有两个递减有序单链表 a 和 b( 每个单链表中不含相同的元素 ), 将它们看成是 两个集合, 设计一个高效算法求 a 和 b 的交集, 要求不破坏 a b 单链表 3-13 有 3 个不含相同元素的递减有序单链表 a b 和 c, 设计一个高效算法求它们公 共的元素, 结果也用单链表 d 表示, 要求不破坏 a b c 单链表 3-14 编程求解 Josephu 问题 设编号为 1 2 n 的 n 个人围坐一圈, 约定编 号为 k(1 k n) 的人从 1 开始报数, 数到 m 的那个人出列, 它的下一位又从 1 开始报 数, 数到 m 的那个人又出列, 以此类推, 直到所有人出列为止, 由此产生一个出队编号的 序列 参考答案 3-1 答 : 该操作是在结点 HL 之后插入首结点 p, 即 p->next=hl->next; HL->next=p 答案为 C 3-2 答 : 其操作应该是 p->prior->next=p->next; p->next->prior=p->prior; free(p) 答案为 D 3-3 答 : 在循环双链表中, 在 p 结点之后插入 s 结点与双链表中的操作相同, 修改 4 114

39 第 3 章线性表 Ⅱ 链表 个指针域 答案为 D 3-4 答 : 在带头结点的双循环链表中可以用时间 O(1) 找到尾结点, 所以在末尾插入结点和删除尾结点的时间均为 O(1) 答案为 D 3-5 答 : 这样的循环链表是不带头结点的,A B 指针一慢一快, 当两者差一圈时刚好指向同一个结点, 设移动步数为 x, 则 3*x-1*x=100,x=50 答案为 E 3-6 答 : 如果两个单链表相交, 至少有一个相交结点, 其后的结点共享, 所以尾结点一定相同 可以通过快 慢指针判断一个单链表有没有环,fast low 均指向头结点,fast 每次走两步,slow 每次走一步, 若两者相等, 说明有环 有环的单链表跟无环的单链表不可能相交, 因为相交时两个链表均有环 答案为 A B C 3-7 解 : 首先 p q 指向头结点, 移动 p 指针使其指向第 k 个结点, 然后 p q 同步后移,p 指向尾结点时 q 指向倒数的第 k-1 个结点, 再删除其后继结点 对应的算法如下 : bool Delrevk(LinkNode *&L,int k) { LinkNode *p=l,*q=l; int i=0; while(p!=null && i<k) { p=p->next; i++; if(p==null) return false; while(p->next!=null) { p=p->next; q=q->next; p=q->next; q->next=p->next; free(p); return true; // 查找第 k 个结点 p // 查找倒数的第 k-1 个结点 //p 指向倒数的第 k 个结点 // 删除 p 结点 3-8 解 : 采用直接插入排序方法 对应的算法如下 : void Sort(LinkNode *&L) { LinkNode *p,*pre,*q; p=l->next->next; L->next->next=NULL; //p 指向 L 的第 2 个数据结点 // 构造只含一个数据结点的有序表 while(p!=null) { q=p->next; //q 保存 p 结点的后继结点的指针 pre=l; // 从有序表开头进行比较,pre 指向插入结点的前驱结点 while(pre->next!=null && pre->next->data<p->data) pre=pre->next; // 在有序表中找插入 p 所指结点的前驱结点 (pre 所指向 ) 115

40 直击招聘 程序员面试笔试 C 数据结构深度解析 p->next=pre->next; pre->next=p; p=q; // 在 pre 所指结点之后插入 p 所指结点 // 扫描原单链表余下的结点 3-9 解 : 用 p 指针扫描循环单链表 L 的所有结点, 一旦找到不满足条件 p->data<p-> next->data+p->next->next->data 的结点 p, 则中止循环, 返回假 ; 否则继续扫描 当 while 循环正常结束时返回真 对应的算法如下 : bool Judge(LinkNode *L) { LinkNode *p=l->next; bool flag=true; while(p->next->next!=l && flag) { if(p->data>p->next->data+p->next->next->data) flag=false; p=p->next; return flag; 3-10 解 : 由于单链表 L 是一个递增有序表, 首先找到值域刚好大于 min 的结点 p 及其前驱结点 pre, 再依次删除所有值域小于 max 的结点 对应的算法如下 : void Delnodes(LinkNode *&L,ElemType min,elemtype max) { LinkNode *p=l->next,*pre=l; //pre 指向结点 p 的前驱结点 while(p!=null && p->data<=min) // 查找刚好大于 min 的结点 p { pre=p; //pre p 同步后移 p=p->next; while(p!=null && p->data<max) { pre->next=p->next; free(p); p=pre->next; // 删除所有小于 max 的结点 3-11 解 : 采用二路归并思路 ( 与前面的面试题 3-26 不同, 这里的元素是递减排列的 ) 将 a 中所有不在 b 中出现的元素存放到数组 c 中,c 即为 a-b 的结果, 单链表 c 采用尾插法建表 算法如下 : void Difference(LinkNode *a,linknode *b,linknode *&c) { LinkNode *pa=a->next,*pb=b->next,*s,*r; c=(linknode *)malloc(sizeof(linknode)); 116

41 第 3 章线性表 Ⅱ 链表 r=c; while(pa!=null && pb!=null) { if(pa->data>pb->data) // 只将 a 中大的元素添加到 c 中 { s=(linknode *)malloc(sizeof(linknode)); s->data=pa->data; r->next=s;r=s; pa=pa->next; if (pa->data<pb->data) // 跳过 b 中较大的元素 pb=pb->next; { pa=pa->next; pb=pb->next; // 公共元素不能添加到 c 中 while(pa!=null) // 若 a 未遍历完, 将余下的所有元素添加到 c 中 { s=(linknode *)malloc(sizeof(linknode)); s->data=pa->data; r->next=s;r=s; pa=pa->next; r->next=null; 3-12 解 : 采用二路归并思路 ( 与前面的面试题 3-25 不同, 这里的元素是递减排列的 ) 将 a b 中都出现的元素存放到数组 c 中,c 即为 a 和 b 的交集, 单链表 c 采用尾插法建表 算法如下 : void Intersection(LinkNode *a,linknode *b,linknode *&c) { LinkNode *pa=a->next,*pb=b->next,*s,*r; c=(linknode *)malloc(sizeof(linknode)); r=c; while(pa!=null && pb!=null) { if(pa->data==pb->data) // 将共同的元素放入 c 中 { s=(linknode *)malloc(sizeof(linknode)); s->data=pa->data; r->next=s;r=s; pa=pa->next; pb=pb->next; if(pa->data>pb->data) pa=pa->next; //pa 结点大, 跳过 117

42 直击招聘 程序员面试笔试 C 数据结构深度解析 pb=pb->next; r->next=null; //pb 结点大, 跳过 3-13 解 : 采用三路归并算法 ( 与前面的面试题 3-27 不同, 这里的元素是递减排列的 ), pa pb pc 分别扫描 a b c 单链表, 只有在 3 个当前元素相同时才将其添加到结果单链表 d 中, 单链表 d 采用尾插法建表, 其中 INF 表示 对应的算法如下: int Max(T x[]) { int i,mink=0; for(i=1;i<3;i++) if(x[i]>x[mink]) mink=i; // 通过简单比较找到最大元素的段号 if (x[mink]==-inf) // 若最大元素为 -, 归并完毕, 返回 -1 return -1; return mink; void Common(LinkNode *a,linknode *b,linknode *c,linknode *&d) { LinkNode *pa=a->next,*pb=b->next,*pc=c->next; LinkNode *s,*r; d=(linknode *)malloc(sizeof(linknode)); r=d; T x[3]; x[0]=(pa!=null?pa->data:-inf); x[1]=(pb!=null?pb->data:-inf); x[2]=(pc!=null?pc->data:-inf); while (true) { int mink=max(x); if(mink==-1) break; if(x[0]==x[1] && x[1]==x[2]) { s=(linknode *)malloc(sizeof(linknode)); s->data=x[0]; r->next=s; r=s; switch(mink) { // 移动最大元素所在段的指针 case 0: pa=pa->next;x[0]=(pa!=null?pa->data:-inf); break; case 1: pb=pb->next;x[1]=(pb!=null?pb->data:-inf); break; 118

43 第 3 章线性表 Ⅱ 链表 case 2: pc=pc->next;x[2]=(pc!=null?pc->data:-inf); break; r->next=null; 3-14 解 : 用不带头结点的单链表实现 由 n 采用尾插法创建一个不带头结点的单链表 first 先从 first 开始移动 k 个结点找到第 k 个人, 再循环 n 次, 即从 first 开始移动 m 1 个结点, 出列后继结点 q, 删除该结点,first 移动到下一个结点 对应的完整程序和测试数据如下 : #include <stdio.h> #include <malloc.h> typedef struct node { int data; struct node *next; // 指向后继结点 LinkNode; // 声明单链表结点类型 void CreateList(LinkNode *&first,int n) // 用尾插法建立循环单链表 first { LinkNode *s,*r; first=(linknode *)malloc(sizeof(linknode)); first->data=1; r=first; for(int i=2;i<=n;i++) { s=(linknode *)malloc(sizeof(linknode)); s->data=i; r->next=s; r=s; r->next=first; void Move(LinkNode *&first,int k) { int i=1; while(i<k) { i++; first=first->next; void Josephu(int n,int k,int m) { int j; LinkNode *first,*q; CreateList(first,n); // 创建首结点 first // 创建新结点 s // 设置为循环单链表 // 移动 k 个结点 119

44 直击招聘 程序员面试笔试 C 数据结构深度解析 Move(first,k); // 移动 k 个结点查找第 k 个人 for(j=1;j<=n;j++) // 出列 n 个人 { Move(first,m-1); // 移动 m-1 个结点 q=first->next; printf("%d ",q->data); // 出列一个人 first->next=q->next; free(q); first=first->next; void main() { int n=8,k=4,m=4; Josephu(n,k,m); // 输出 :