2. 考研
  3. 两个整数序列A=a1，a2，a3，…，am和B=b1，b2，b3，…，bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。

两个整数序列A=a1，a2，a3，…，am和B=b1，b2，b3，…，bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。

admin2018-08-12  28
问题 两个整数序列A=a1，a2，a3，…，am和B=b1，b2，b3，…，bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。
选项
答案typedef struct LNode{ int data； struct LNode * next； } * Linkedlist； int Pattern(LinkedList A，B){ ／／A和B分别是数据域为整数的单链表，本算法判断链表B是否是 ／／链表A的子序列。如是，返回1；否则，返回0，表示失败。 Linkedlist * p， * pre，* q； P=A； ／／p为链表A的工作指针，本题假定链表A和链表B均无头结点 pre=p； ／／pre记住每趟比较中链表A的开始结点 q=B； ／／q是链表B的工作指针 while(p&&q) if(p一>data==q一>data){p=p一>next； q=q一>next； } else{ pre=pre一>next；p=pre； ／／链表A新的开始比较结点 q=B； ／／q从链表B第一结点开始 if(q==null)return(1)； ／／链表B是链表A的子序列 else return(0)； ／／链表B不是链表A的子序列 } }／／算法结束 提示：本题实质上是一个模式匹配问题，这里匹配的元素是整数而不是字符。因两整数序列已存入两个链表中，操作从两链表的第一个结点开始，若对应数据相等，则后移指针；若对应数据不等，则链表A从上次开始比较结点的后继开始，链表B仍从第一结点开始比较，直到链表B到尾表示匹配成功。链表A到尾链表B未到尾表示失败。操作中应记住链表A每次的开始结点，以便下趟匹配时好从其后继开始。
解析
转载请注明原文地址:https://kaotiyun.com/show/IcRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)