数据结构:第13关:查找两个单词链表共同后缀的起始结点
2023-12-15 09:39:11
任务描述
本关任务:假定采用带头结点的单链表保存单词,当两个单词有相同的后缀时,则可共享相同的后缀空间。 例如,“loading”和“being”的存储映像如下图所示:
设str1和str2分别指向两个单词所在单链表的头结点,请实现一个时间上尽可能高效的算法,找出由str1和str2所指的两个链表共同后缀的起始位置的结点,输出该结点对应的字符(如图中的字符i)。
编程要求
输入
多组数据,每组数据有三行,第一行为链表str1和str2的长度n和m,第二行为链表str1的n个元素,第三行为链表str2的m个元素(元素之间用空格分隔)。n=0且m=0时输入结束。
输出
对于每组数据输出一行,为共同后缀的起始位置结点对应的字符。
测试说明
平台会对你编写的代码进行测试:
测试输入: 7 5
l o a d i n g
b e i n g
7 9
f l u e n c y
f r e q u e n c y
0 0
预期输出: i
u
来源
?
开始你的任务吧,祝你成功!
笔者第一次执行时,漏写了count++。结果是无论如何打印都为空,甚至在函数开头写cout<<1;? 都仍然是打印空。笔者并未解决这个不算问题的问题
#include <iostream>
using namespace std;
typedef struct LNode
{
char data;
struct LNode *next;
}LNode,*LinkList;
void CreateList_R(LinkList &L,int n)
{//后插法创建单链表
L=new LNode;
L->next=NULL;
LinkList r=L;
for(int i=0;i<n;i++)
{
LinkList p=new LNode;
cin>>p->data;
p->next=NULL;
r->next=p;
r=p;
}
}
void FindSuffix(LinkList str1, LinkList str2,int n,int m)
{//查找两个单词链表共同后缀的起始结点
/**************begin************/
LinkList p,q;
if(n>m) //p始终为更长那个的工作指针
{
p=str1->next;
q=str2->next;
}
else
{
q=str1->next;
p=str2->next;
}
int diff=n-m;
if(diff<0) diff=diff*(-1);
int count=0;
while(count<diff)
{
p=p->next;
count++;
}
while(p&&q)
{
if(p->data==q->data)
{
cout<<p->data<<endl;
break;
}
p=p->next;
q=q->next;
}
/**************end************/
}
int main()
{
int n,m;
while(cin>>n>>m)
{
if(n==0&&m==0) break;
LinkList str1,str2,p;
CreateList_R(str1,n);
CreateList_R(str2,m);
FindSuffix(str1,str2,n,m);
}
return 0;
}
文章来源:https://blog.csdn.net/qq_74118294/article/details/134937663
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!