C : 링크 된 목록의 검색 기능

Question

두 개의 연결된 목록이 있습니다.

typedef struct node 
{ 
    char value[256]; 
    struct node *next; 
} Node_t; 

    typedef struct node1 
    { 
     char value1[256]; 
     int count; 
     struct node1 *next; 
    } Node1_t; 

모두 연결리스트 데이터를 가지고, 내가 어떤 데이터가 공통적으로 두 개의 연결리스트간에 데이터를 비교하려는 두 개의 연결리스트와 유사한 데이터를 찾을 수있는 방법은 무엇입니까?

감사합니다.

Answer 1

두 목록이 정렬되면, 다음과 같은 알고리즘 (의사 코드, 실행의 복잡성 O(n+m))를 사용할 수 있습니다 : 목록 중 하나가 정렬되지 않은 경우

INPUT: list1, list2 (first nodes of the lists you want to compare, sorted!) 

while list1 != null AND list2 != null 
    if list1->value < list2->value 
     list1->value = list1->next 

    elseif 
     list2->value < list1->value 
      list2->value = list2->next 

    else 
     list3->appendValue(list1->value) 
     list1->next 

, 각 요소를 비교해야 두 번째 목록의 각 요소 (런타임 복잡성 O(n*m))와 첫 번째 목록에서 :

INPUT: list1, list2 (first nodes of the lists you want to compare) 

while list1 != null 
    list2temp = list2 

    while list2temp != null 
     if list1->value == list2temp->value 
      list3->appendValue(list1->value) 
     list2temp = list2temp->next 
    list1 = list1->next 

그것은 먼저 목록을 정렬 할 종종 더 나은 다음 첫 번째 방법을 사용,이 O(n log n + m log m)의 런타임 복잡성이 발생합니다. 두 경우 모두 list3에는 두 목록의 공통 요소가 포함됩니다.

Answer 2

list = head; 
while (list) { 
    list1 = head1; 
    while (list1) { 
    if (yourcompare(list->value, list1->value) == 0) { 
     // do something with common data 
     // if only possible case: then break; 
    } 
    list1 = list1->next; 
    } 
    list = list->next; 
} 

list1의 일치하는 값이 다시 일치하지 않으면 '짧은 업데이트'와 같은 부기 데이터를 추가 할 수 있습니다. 그래서 당신은 'if (! list1-> updated) {...; list1-> updated = TRUE;} '내부에있는 동안.