首页 25考研 在职考研 0元畅学 26考研

新东方在线 > 考研 > 计算机 > 考研计算机真题 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

42.(13分)假定采用带头结点的单链表保存单词，当两个单词有

2021-07-11 07:42:00来源：新东方在线

　　【题目】

　　42.(13分)假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如下图所示。

　　设strl和str2分别指向两个单词所在单链表的头结点，链表结点结构为　，请设计一个时间上尽可能高效的算法，找出由str1和str2所指的两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)。要求：

　　(1)给出算法的基本设计思想。

　　(2)根据设计思想，采用C或c++或Java语言描述算法，关键之处给出注释。

　　(3)说明你所设计算法的时间复杂度。

　　【答案要点】

　　(1)给出算法的基本设计思想：(4分)

　　①分别求出str1和str2所指的两个链表的长度m和n;

　　②将两个链表以表尾对齐：令指针p、q分别指向str1和str2的头结点，若m≥n，则使p指

　　向链表中的第m-n+1个结点;若m

　　指的结点到表尾的长度相等。

　　③反复将指针p和q同步向后移动，并判断它们是否指向同一结点。若p和q指向同一结点，

　　则该点即为所求的共同后缀的起始位置。

　　(2)算法实现：(8分)

　　typedef struct Node{

　　char data;

　　struct Node*next;

　　}SNODE;

　　SNODE*findlist(SNODE*str1，SNODE*str2){

　　int m，n;

　　SNODE*p，*q;

　　m=listlen(str1); /*求str1的长度。0(m)*/

　　n=listlen(str2); /$求str2的长度。0(n)*/

　　/*以下3个循环的时间复杂度为：0(max(m，n))*/

　　for(p=str1;m>“;m--) /*使p指向的链表与q指向的链表等长*/

　　p=p->next;

　　for(q=str2;m

　　q=q->next;

　　while(p->next!=NULL&&p->next!=q->next){

　　/*查找共同后缀起始点*/

　　p=p->next; /*两个指针同步向后移动*/

　　q=q->next;

　　}

　　return p->next; /*返回共同后缀的起始点*/

　　}

　　int listlen(SNODE*head){ /*求链表长度*/

　　int len=0：

　　while(head->next!=NULL){

　　len*+;

　　head=head->next;

　　}

　　return len;

　　}

　　(3)说明算法的时间复杂度：(1分)

　　参考答案的时间复杂度为：0(m+rt)或0(max(m，n))。其中m、n分别为两个链表的长度。


考研公开课小程序

本文关键字: 假定采用带头结点的

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
25考研 在职研 AI择校 去测评 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

考研资料大礼包

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10