(PAT)1032 Sharing (可以用数组表示地址)

比眉伴天荒 2022-05-11 06:58 165阅读 0赞

To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, `loading` and `being`are stored as showed in Figure 1.

![fig.jpg][]

Figure 1

You are supposed to find the starting position of the common suffix (e.g. the position of `i` in Figure 1).

### Input Specification: ###

Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive N (≤105), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by −1.

Then N lines follow, each describes a node in the format:

Address Data Next

where`Address` is the position of the node, `Data` is the letter contained by this node which is an English letter chosen from \{ a-z, A-Z \}, and `Next` is the position of the next node.

### Output Specification: ###

For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output `-1` instead.

### Sample Input 1: ###

11111 22222 9
    67890 i 00002
    00010 a 12345
    00003 g -1
    12345 D 67890
    00002 n 00003
    22222 B 23456
    11111 L 00001
    23456 e 67890
    00001 o 00010

### Sample Output 1: ###

67890

### Sample Input 2: ###

00001 00002 4
    00001 a 10001
    10001 s -1
    00002 a 10002
    10002 t -1

### Sample Output 2: ###

-1

解题思路:

我们可以把数组大小定义成100010,这样就形成了一个地址池,根据题目中给出的自身地址和next地址,可以利用这个地址池进行存储.寻找第一个公共节点时,我们可以让链表1先进行遍历,将遍历到的节点都标记位true

然后让链表2进行遍历,遍历到为true的节点就是第一个公共节点

#include <iostream>
    #include <algorithm>
    using namespace std;
    const int maxn = 100010;  //地址池
    
    class Node {
    public:
    	int next;
    	char algpa;
    	bool flag;
    }node[maxn];
    
    int main() {
    	for (int i = 0; i < maxn; ++i) {
    		node[i].flag = false;
    	}
    
    	int firstAddr = 0;
    	int secondAddr = 0;
    	int n = 0;
    	cin >> firstAddr >> secondAddr >> n;
    
    	for (int i = 0; i < n; ++i) {
    		int addr,next = 0;
    		char data;
    		cin >> addr >> data >> next;
    		node[addr].next = next;
    		node[addr].algpa = data; 
    	}
    
    	int p1 = firstAddr;  //第一个首地址
    	int p2 = secondAddr; //第二个首地址
    
    	while (p1 != -1) {  //先把第一条链表做上标记
    		node[p1].flag = true;
    		p1 = node[p1].next;   //向下遍历
    	}
    
    	while (p2 != -1) {
    		if (node[p2].flag == true) {  //找到第一个重合词
    			break;
    		}
    		p2 = node[p2].next;
    	}
    
    	if (p2 != -1) {
    		printf("%05d\n", p2);
    	}
    	else {
    		printf("-1\n");
    	}
    
    	return 0;
    }

[fig.jpg]: /images/20220511/2cb9f16c2f7d4ced8b07a30dfe0e1f76.png