【趣学C语言和数据结构100例】

【趣学C语言和数据结构100例】

问题描述

61.假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间，例如，loading 和 being 的存储映像如下图所示,设 strl 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 data next。请设计个时间上尽可能高效的算法，找出由 st1 和 str2 所指向两个链表共同后缀的起始位置(如图中字符i所在结点的位置 P)。

62.用单链表保存m 个整数，结点的结构为[data][link]，且|data|<n(n 为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的结点，仅保留第欠出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表 head 如下

63.设线性表L=(a1.a.a3.…,an2,an1.am)采用带头结点的单链表保存，链表中的结点定义如下

typedef struct LNode{int data;struct Lnode* next;
}LNode, LinkList:

请设计一个空间复杂度为o(1)且时间上尽可能高效的算法，重新排列工中的各结点，得到线性表L’=(a1,an,a2,an-1,a3,an2.…)

64.将两个按值有序排列的非空线性链表合并为一个按值有序的线性链表

65.设线性表L=(X1,X2,…,Xn-2,Xn-1,Xn)中存储整型数据，采用带头结点的单链表保存。中奇数位序的数据元素按升序存放，偶数位序的数据元素按降序存放。请设计一个空间复杂度为 0(1)且时间上尽可能高效的算法，将链表中的元素按从小到大的顺序排序

代码分析

61.带头结点的单链表，共同后缀的起始位置
分析：返回节点+对AB不操作，故函数名为Lnode * 函数名(LiukList str1,LiukList str2).。使用while§循环遍历，先记录并计算，str1和str2的长度，先使长度小的先移动他们的差，然后再不到最后的情况下，同时移动，找到相同节点。返回该位置。

62.单链表中删除绝对值一样的节点
分析：传入一个数组和n,故函数名为void 函数名(LiukList L,int n)。创建一个动态数组存储（n+1大小）并初始化为0，然后开始遍历，使用三目运算符，使负的变为正，即（m=p->next->data > 0 ?p->next->data:-p->next->data;），如果再数组中为0，则记录，并继续，如果不为0，则使跳过其。知道循环结束。

63.重新排列，a1,an,a2,an-1,a3,an2.…
思路：1.找到链表的中点 2.反转链表的后半部分，使用头插法 3.交替合并链表的前半部分和反转后的后半部分，使用尾插法。

具体分析：找到链表的中间节点：使用两个指针 p 和 q。p 每次移动一步，q 每次移动两步。当 q 到达链表末尾时，p 刚好位于中间节点。分割链表:q 现在指向后半部分的头节点,将 p 的 next 指向 NULL，以断开链表。 反转后半部分链表：使用指针 r 来保存当前节点的下一个节点。然后将当前节点 q 的 next 指向前半部分的头节点 p 的 next，并将 p 的 next 更新为 q。继续这个过程，直到后半部分的所有节点都被反转并插入到前半部分的开头。使用指针 p 指向前半部分的头节点，指针 q 指向反转后的后半部分的头节点。交替地将 q 的节点插入到 p 的后面，直到 q 的所有节点都被合并。

64.两个值有序非空线性链表合并一个按值有序的链表
分析：返回为一个链表，传入的只要A会改变，故函数名为Linklist func(Linklist A,Linklist B)，定义p和q分别指向A和B，先创造C的头部，令A，B中小的赋值，使用while循环一起遍历，使值小的在C的后面，并更新C的尾部，在结束循环时，在C的尾部加入指向NULL。返回C即可。

65.奇数位序的数据元素按升序存放，偶数位序的数据元素按降序存放->原地条件下->按从小到大的顺序排序
分析：传入链表对其操作并返回。故函数名为：Linklist func(Linklist &L)。定义p并使其指向头节点的下一个的下一个，p 指向链表中第三个节点。使后面的断链即，指向NULL。从p开始使用while循环遍历，定义一个pre指向L从头开始遍历，知道插入位置，使用尾插法插入，并更新p的位置，一直找到其对于的位置。

代码实现

#include<stdio.h>
int main(){
//	61.假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间，例如，loading 和 being 的存储映像如下图所示,设 strl 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 data next。请设计个时间上尽可能高效的算法，找出由 st1 和 str2 所指向两个链表共同后缀的起始位置(如图中字符i所在结点的位置 P)。
Lnode* func(Linklist str1,Linklist L2){int m=0,n=0;Lnode* p=str1->next,q=str2->