Можно ли изменить структуру?

Question

У меня есть два отдельных связанных списка, которые объединяются в какой-то момент, и я должен найти эту точку. Я думал, могу ли я добавить новый тип данных с именем visit (flag), чтобы я мог сделать все узлы первого связанного список, который был посещен, а затем найти точку пересечения, пересекающуюся со вторым связанным списком. Могу ли я это сделать? Могу ли я изменить структуру после ее определения? Если да, то как? Спасибо заранее.

Answer 1

Нет, вы не можете добавлять или удалять элементы из структуры во время выполнения.

Answer 2

Рассмотрите два примера списков A и B. Вы не знаете, где они пересекаются, но вы проходитесь как и вы знаете, их длины:

A : A1 > A2 > A3 > A4 > NULL   <-- length 4 
B : B1 > B2 > B3 > B4 > B5 > B6 > NULL <-- length 6 

Если есть точка пересечения, некоторый адрес памяти Ai будет равняться по адресу памяти Bj для 1 <= i <= 4 и 3 <= j <= 6.

Почему?

Если адрес A1 равен адресу B1 или B2 (если любой из этих узлов является точкой пересечения), то связанный список A будет действительно два узла или один узел больше. Но мы знаем, что это не так, потому что мы прошли A, и мы уже знаем, как долго это происходит.

Итак, что вы можете сделать, это найти разницу в длинах и пройти эту разницу в течение более длинного из двух списков - узел пересечения, если он существует, будет находиться в хвосте более длинного списка. Затем начинает перебор в оба списков, тестирование для указателя равенства, как вы идете:

# we know B is longer, but you would test this 
# condition and set up different code to handle 
# the two cases 

unsigned int A_len = 4; 
unsigned int B_len = 6; 
unsigned int AB_diff = B_len - A_len; 
struct foo *A_head = ...; # user-defined 
struct foo *B_head = ...; # user-defined 
struct foo *A_iter = NULL; 
struct foo *B_iter = NULL; 

# - start the A-iterator at the first node of A 
# - start the B-iterator at the diff-th node of B 
# 
# - now test for pointer equality until we find a 
# match, or we hit the end of either list 

for (A_iter = A_head, B_iter = B_head + AB_diff; 
     (A_iter != B_iter) || (A_iter->nextNode != NULL); 
     ++A_iter, ++B_iter) { } 

# wherever A_iter and B_iter are now pointing will be 
# either NULL (if they don't intersect) or some non-NULL 
# value representing the intersection node 

Answer 3

Нет, вы не можете изменить структуру после его определения. Почему вы хотите использовать только тип данных и почему не какой-либо другой метод?

Однако, вы можете сохранить адрес каждого узла связанного списка 1 в массиве, а затем использовать его для поиска точки пересечения. Это близко к тому, что вы хотите.

Снова есть много лучших альгорифмов, чтобы найти точку пересечения, которая не нуждается в дополнительном типе данных.

Answer 4

Если структура определена в вашем источнике, вы можете просто добавить дополнительный элемент. Если вам нужно работать со структурой, уже определенной в какой-либо библиотеке (или вашим инструктором), то нет, вы не можете добавлять участников после факта, но лучше всего сохранить хэш-таблицу, которая отображает адрес экземпляров struct к дополнительной информации об этой структуре. В этом случае, поскольку вам нужна только информация о том, был ли экземпляр замечен, просто введите адреса узлов первого списка в хеш-таблицу, затем просмотрите второй список, чтобы узнать, есть ли какой-либо из его узлов в хэш-таблице.

Также см. Ответ Alex Reynolds, который позволяет избежать необходимости в дополнительной информации.