时间戳

首页 > 解决方案 > 将非重复条目从两个链表传递到第三个链表的问题

c - 将非重复条目从两个链表传递到第三个链表的问题

问题描述

我试图创建一个函数，它将两个链表的头作为输入，并创建第三个，它只包含两个列表中的条目，只出现在它们各自的列表中。问题是当我打印第三个列表时，我看到它包含两个列表中的每个条目。

示例列表 1：，1->13->32->4->5列表 2：2->13->42->5

期望结果：list 3 1->32->4->2->2，实际结果：1->13->32->4->5->2->13->42->5

每个列表的头部都被声明为一个全局变量。

typedef struct list_path *lp;
struct list_path
{
    int row,column;
    lp next;

};

lp head_list_1,head_list_2,head_list_3,temp_list,aux_path,temp_union,temp_insert_union,aux_union,aux_path_1,aux_path_2,head_list;

void path_union(lp head_list_1, lp head_list_2) 
{
    aux_path_1 = head_list_1;
    aux_path_2 = head_list_2;
    int exist;

    while (aux_path_1 != NULL)
    {     
        exist = 0;
     
        while (aux_path_2 != NULL)
        {
            if (aux_path_1->row == aux_path_2->row && aux_path_1->column == aux_path_2->column)
            {
                exist=1;
            }
         
            aux_path_2 = aux_path_2->next;
        }

        if (exist == 0)
        {
            insert_union(head_list_3, aux_path_1->row, aux_path_1->column);
        } 

        aux_path_1 = aux_path_1->next;
    }

    aux_path_1 = head_list_1;
    aux_path_2 = head_list_2;

    while (aux_path_2 != NULL)
    {     
        exist = 0;
     
        while (aux_path_1 != NULL)
        {
            if (aux_path_2->row == aux_path_1->row && aux_path_2->column == aux_path_1->column)
            {
                exist = 1;
            }

            aux_path_1 = aux_path_1->next;
        }
     
        if (exist == 0)
        {
            insert_union(head_list_3, aux_path_2->row, aux_path_2->column);
        }

        aux_path_2 = aux_path_2->next;
    }  
}

void insert_union(lp head_list_3, int key_a, int key_b)
{   
    lp union_temp;
    lp list_aux = head_list_3;
    
    while (list_aux->next != NULL)
    {
        list_aux = list_aux->next;
    }

    union_temp = (lp)malloc(sizeof(struct list_path));
    union_temp->row = key_a;
    union_temp->column = key_b;
    list_aux->next = union_temp;
    union_temp->next = NULL;
}

第一个函数使用 2 个嵌套的 while 来查找哪些条目只出现一次，第二个函数将这些键传递给第三个列表。

标签： cloopswhile-looplinked-listfunction-definition

解决方案

您的代码中有多个问题：

  • 实现是有缺陷的：您应该aux_path_2 = head_list_2在第一个循环aux_path_1 = head_list_1的每次迭代开始时和第二个循环的每次迭代开始时进行初始化。

  • 一般的想法是不正确的：您只会插入仅在一个列表中的元素。两个列表共有的元素将在两个循环中被跳过，因此永远不会插入联合列表中。您应该克隆第一个列表并仅在第二个循环中使用测试。

  • 该insert_union函数不能从空列表开始。您应该head_list_3从此函数返回更新后的值并将其存储在调用者中。

  • 不需要为此任务使用全局变量：创建或更新的列表指针应该由两个函数返回。

  • 将指针隐藏在 typedef 后面会令人困惑且容易出错。而不是定义lp，定义list_path为 typedefstruct list_path并用于list_path *保持指针可见。

这是一个使用辅助函数来检查节点是否已给定坐标的修改版本。使用小的泛型函数和变量名有助于提高代码的可读性：

#include <stdlib.h>

typedef struct list_path list_path;
struct list_path {
    int row, column;
    list_path *next;
};

int path_find(list_path *head, int row, int column) {
    for (list_path *aux = head; aux != NULL; aux = aux->next) {
        if (aux->row == row && aux->column == column)
            return 1;
    }
    return 0;
}
    
list_path *path_insert(list_path *head, int row, int column) {
    list_path *temp;
    list_path *aux;
    
    temp = malloc(sizeof(*temp));
    if (temp == NULL) {
        perror("cannot allocate list_path structure");
        abort();
    }
    temp->row = row;
    temp->column = column;
    temp->next = NULL;

    if (head == NULL) {
        // empty list: allocated node is the new head
        head = temp;
    } else {
        // otherwise find the last node of the list
        for (aux = head; aux->next != NULL; aux = aux->next) {
            continue;
        }
        // and append the newly allocated node
        aux->next = temp;
    }
    return head;
}

list_path *path_union(list_path *list1, list_path *list2) {
    list_path *list3 = NULL;

    // clone the first list into list3
    for (list_path *aux1 = list1; aux1 != NULL; aux1 = aux1->next) {     
        list3 = path_insert(list3, aux1->row, aux1->column);
    }

    // append elements only present in list2
    for (list_path *aux2 = list2; aux2 != NULL; aux2 = aux2->next) {     
        if (!path_find(list1, aux2->row, aux2->column)) {
            list3 = path_insert(list3, aux2->row, aux2->column);
        }
    }
    // return a pointer to the union list.
    return list3; 
}

推荐阅读