I tried to make a function, that takes two linked lists' heads as an input, and creates a third one, that only includes the entries from both lists, that only appear in their respective list. The problem is that when I print the third list, I see that it includes every entry from both lists.
Example list 1: 1->13->32->4->5, list 2: 2->13->42->5
Desired outcome: list 3 1->32->4->2->2, actual outcome: 1->13->32->4->5->2->13->42->5
The head of every list is declared as a global variable.
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;
}
The first function uses 2 nested whiles to find which entries appear only once and the second one passes those keys to the third list.
CodePudding user response：
The problem is that after the inner while loops as for example after this inner while loop
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;
}
the pointers aux_path_2 and aux_path_1 become equal to NULL. So in next iterations of the outer while loops the inner while loops are skipped due to their conditions like this
while (aux_path_2 != NULL)
that at once evaluate to logical false.
You need to reset the values of the pointers aux_path_2 and aux_path_1 in the beginning of the outer while loops before the inner while loops as for example
while (aux_path_1 != NULL)
{
exist = 0;
aux_path_2 = head_list_2; // <===
while (aux_path_2 != NULL)
{
//...
}
Also as soon as the variable exist is set to 1 there is no sense to continue iterations of the inner while loops.
So the inner for loops should be rewritten as for example
while (aux_path_1 != NULL)
{
exist = 0;
for ( aux_path_2 = head_list_2;
!exist && aux_path_2 != NULL;
aux_path_2 = aux_path_2->next )
{
if (aux_path_1->row == aux_path_2->row && aux_path_1->column == aux_path_2->column)
{
exist = 1;
}
}
//...
CodePudding user response：
There are multiple problems in your code:
the implementation is flawed: you should initialize
aux_path_2 = head_list_2at the beginning of each iteration of the first loop andaux_path_1 = head_list_1at the beginning of each iteration of the second loop.the general idea is incorrect: you would only insert elements that are in one list only. Elements common to both lists will be skipped in both loops hence never inserted in the union list. You should instead clone the first list and use the test only in the second loop.
the
insert_unionfunction cannot start from an empty list. You should return the updated value ofhead_list_3from this function and store it in the caller.there is no need to use global variables for this task: created or updated list pointers should be returned by both functions.
it is confusing and error prone to hide pointers behind typedefs. Instead of defining
lp, definelist_pathas a typedef forstruct list_pathand uselist_path *to keep pointers visible.
Here is a modified version using an auxiliary function to check if a node has given coordinates. Using small generic functions and variable names helps improve code readability:
#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;
}