中国建设部官方网站监理转注册,phpcms律师网站模板,男学网站开发,徐州网站建设外包有一种存储英文单词的方法#xff0c;是把单词的所有字母串在一个单链表上。为了节省一点空间#xff0c;如果有两个单词有同样的后缀#xff0c;就让它们共享这个后缀。下图给出了单词“loading”和“being”的存储形式。本题要求你找出两个链表的公共后缀。 函数接口定义是把单词的所有字母串在一个单链表上。为了节省一点空间如果有两个单词有同样的后缀就让它们共享这个后缀。下图给出了单词“loading”和“being”的存储形式。本题要求你找出两个链表的公共后缀。 函数接口定义
PtrToNode Suffix( List L1, List L2 );其中List结构定义如下
typedef struct Node *PtrToNode;
struct Node {ElementType Data; /* 存储结点数据 */PtrToNode Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */L1和L2都是给定的带头结点的单链表。函数Suffix应返回L1和L2的公共后缀的起点位置。 裁判测试程序样例
#include stdio.h
#include stdlib.htypedef char ElementType;typedef struct Node *PtrToNode;
struct Node {ElementType Data; /* 存储结点数据 */PtrToNode Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */void ReadInput( List L1, List L2 ); /* 裁判实现细节不表 */
void PrintSublist( PtrToNode StartP ); /* 裁判实现细节不表 */
PtrToNode Suffix( List L1, List L2 );int main()
{List L1, L2;PtrToNode P;L1 (List)malloc(sizeof(struct Node));L2 (List)malloc(sizeof(struct Node));L1-Next L2-Next NULL;ReadInput( L1, L2 );P Suffix( L1, L2 );PrintSublist( P );return 0;
}/* 你的代码将被嵌在这里 */输入样例
如图存储的链表 输出样例 ing 代码
PtrToNode Suffix( List L1, List L2 )
{List P1,P2;P1L1-Next;P2L2-Next;int len10,len20;//求链表1的长度 while(P1){len1;P1P1-Next;}//求链表2的长度 while(P2){len2;P2P2-Next;}//若len1len2,令P1指向链表中的第len1-len21个结点 for(P1L1;len1len2;len1--) P1P1-Next;//若len2len1,令P2指向链表中的第len2-len11个结点 for(P2L2;len2len1;len2--) P2P2-Next;while(P1-Next!P2-Next){// 将指针P1和p2同步向后移动直到P1和p2指向同一结点P1P1-Next;P2P2-Next; } return P1-Next;
}
