有一種存儲英文單詞的方法，是把單詞的所有字母串在一個單鏈表上。為了節(jié)省一點空間，如果有兩個單詞有同樣的后綴，就讓它們共享這個后綴。下圖給出了單詞“l(fā)oading”和“being”的存儲形式。本題要求你找出兩個鏈表的公共后綴。

函數(shù)接口定義：

PtrToNode Suffix( List L1, List L2 );

其中List結(jié)構(gòu)定義如下：

typedef struct Node *PtrToNode; struct Node {ElementType Data; /* 存儲結(jié)點數(shù)據(jù) */PtrToNode Next; /* 指向下一個結(jié)點的指針 */ }; typedef PtrToNode List; /* 定義單鏈表類型 */

L1和L2都是給定的帶頭結(jié)點的單鏈表。函數(shù)Suffix應(yīng)返回L1和L2的公共后綴的起點位置。

裁判測試程序樣例：

#include <stdio.h> #include <stdlib.h>typedef char ElementType;typedef struct Node *PtrToNode; struct Node {ElementType Data; /* 存儲結(jié)點數(shù)據(jù) */PtrToNode Next; /* 指向下一個結(jié)點的指針 */ }; typedef PtrToNode List; /* 定義單鏈表類型 */void ReadInput( List L1, List L2 ); /* 裁判實現(xiàn)，細(xì)節(jié)不表 */ void PrintSublist( PtrToNode StartP ); /* 裁判實現(xiàn)，細(xì)節(jié)不表 */ 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;P1=L1->Next;P2=L2->Next;int len1=0,len2=0;//求鏈表1的長度 while(P1){len1++;P1=P1->Next;}//求鏈表2的長度 while(P2){len2++;P2=P2->Next;}//若len1>len2,令P1指向鏈表中的第len1-len2+1個結(jié)點 for(P1=L1;len1>len2;len1--) P1=P1->Next;//若len2>len1,令P2指向鏈表中的第len2-len1+1個結(jié)點 for(P2=L2;len2>len1;len2--) P2=P2->Next;while(P1->Next!=P2->Next){// 將指針P1和p2同步向后移動，直到P1和p2指向同一結(jié)點P1=P1->Next;P2=P2->Next; } return P1->Next; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的共享后缀的链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。