每日编程Day 1，有哪些编程技巧和挑战值得探索？
- 内容介绍
- 文章标签
- 相关推荐
本文共计703个文字，预计阅读时间需要3分钟。
问题描述：使用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间。例如，logging和being，如下图所示。设str1和str2分别指向两个单词所对应的单链表。
问题描述
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀，则可共享相同的后缀存储空间，例如，“loaging”和“being”, 如下图所示。
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为
请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)。
解决方法
（1）算法的基本思想
顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另外一个链表长k个结点，之后同步遍历两个链表。这样我们就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的。所以它们肯定同时到达第一个公共结点。于是得到算法思路：
①求它们的长度len1,len2；
②遍历两个链表，使p,q指向的链表等长；
③同步遍历两个链表，直至找到相同结点或链表结束。
（2）代码实现
#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;
typedef struct Node
{
ElemType data;
struct Node *next;
}Node,*LinkList;
int LinkLength(LinkList L)
{
int k=0;
while(L)
{
k++;
L=L->next;
}
return k;
}
LinkList CreateList(int n)
{
LinkList h=(LinkList)malloc(sizeof(Node));
Node *r,*s;
r=h;
char ch;
int i;
for(i=0;i<=n;i++)
{
s=(LinkList)malloc(sizeof(Node));
scanf("%c",&ch);
s->data=ch;
r->next=s;
r=s;
}
r->next=NULL;
h=h->next;
return h;
}
void Print(LinkList L)
{
while(L!=NULL)
{
printf("%c",L->data);
L=L->next;
}
printf("\n");
}
LinkList find(LinkList str1,LinkList str2)
{
LinkList p=str1;
LinkList q=str2;
int len1=LinkLength(str1),len2=LinkLength(str2);
for(p=str1;len1>len2;len1--)//使p指向的链表与q指向的链表等长
p=p->next;
for(q=str2;len1<len2;len2--)//使q指向的链表与p指向的链表等长
q=q->next;
while(p->next!=NULL&&p->data!=q->data)//查找共同后缀起始点
{
p=p->next;
q=q->next;
}
return p;
}
int main()
{
LinkList L1;
int n1;
printf("请输入L1链表的长度，以回车结束，然后输入结点的值：");
scanf("%d",&n1);
L1=CreateList(n1);
printf("L1链表为：");
Print(L1);
LinkList L2;
int n2;
printf("请输入L2链表的长度，以回车结束，然后输入结点的值：");
scanf("%d",&n2);
L2=CreateList(n2);
printf("L2链表为：");
Print(L2);
printf("\n");
LinkList L3;
printf("L1和L2公共后缀的起始结点（即相交结点）为：");
L3=find(L1,L2);
printf("%c",L3->data);
return 0;
}
（3）运行结果
本文共计703个文字，预计阅读时间需要3分钟。
问题描述：使用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间。例如，logging和being，如下图所示。设str1和str2分别指向两个单词所对应的单链表。
问题描述
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀，则可共享相同的后缀存储空间，例如，“loaging”和“being”, 如下图所示。
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为
请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)。
解决方法
（1）算法的基本思想
顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的长度不同。假设一个链表比另外一个链表长k个结点，之后同步遍历两个链表。这样我们就能够保证它们同时到达最后一个结点。由于两个链表从第一个公共结点到链表的尾结点都是重合的。所以它们肯定同时到达第一个公共结点。于是得到算法思路：
①求它们的长度len1,len2；
②遍历两个链表，使p,q指向的链表等长；
③同步遍历两个链表，直至找到相同结点或链表结束。
（2）代码实现
#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;
typedef struct Node
{
ElemType data;
struct Node *next;
}Node,*LinkList;
int LinkLength(LinkList L)
{
int k=0;
while(L)
{
k++;
L=L->next;
}
return k;
}
LinkList CreateList(int n)
{
LinkList h=(LinkList)malloc(sizeof(Node));
Node *r,*s;
r=h;
char ch;
int i;
for(i=0;i<=n;i++)
{
s=(LinkList)malloc(sizeof(Node));
scanf("%c",&ch);
s->data=ch;
r->next=s;
r=s;
}
r->next=NULL;
h=h->next;
return h;
}
void Print(LinkList L)
{
while(L!=NULL)
{
printf("%c",L->data);
L=L->next;
}
printf("\n");
}
LinkList find(LinkList str1,LinkList str2)
{
LinkList p=str1;
LinkList q=str2;
int len1=LinkLength(str1),len2=LinkLength(str2);
for(p=str1;len1>len2;len1--)//使p指向的链表与q指向的链表等长
p=p->next;
for(q=str2;len1<len2;len2--)//使q指向的链表与p指向的链表等长
q=q->next;
while(p->next!=NULL&&p->data!=q->data)//查找共同后缀起始点
{
p=p->next;
q=q->next;
}
return p;
}
int main()
{
LinkList L1;
int n1;
printf("请输入L1链表的长度，以回车结束，然后输入结点的值：");
scanf("%d",&n1);
L1=CreateList(n1);
printf("L1链表为：");
Print(L1);
LinkList L2;
int n2;
printf("请输入L2链表的长度，以回车结束，然后输入结点的值：");
scanf("%d",&n2);
L2=CreateList(n2);
printf("L2链表为：");
Print(L2);
printf("\n");
LinkList L3;
printf("L1和L2公共后缀的起始结点（即相交结点）为：");
L3=find(L1,L2);
printf("%c",L3->data);
return 0;
}