relyMATE relyMATE - 2 months ago 24
C Question

Print pairs of values that are in a linked list

This is my code for creating a linked list:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct list_element {
int inf;
struct list_element *next;
} List;

List *create() {
List *p, *punt;
int x = 1;/*Random number but different from 0*/
p = (List *)malloc(sizeof(List));
printf("\nFirst value: ");
scanf("%d", &p->inf);
punt = p;

while (1) {/*Till x different from 0*/
printf("\nNext value: ");
scanf("%d", &x);
if (x == 0)
break;
punt->next = (List *)malloc(sizeof(List));
punt = punt->next;
punt->inf = x;
}
punt->next = NULL;
return p;
}

int main(void) {
List *a;
a = create();
}


Suppose the following values to be sent in input(scanf):


10 20 30 40 50 15 35


I need to create a void function which sends to stdout the list of pairs of numbers whose sum is 50, so in this case the output will be


10 40

20 30

15 35


To do this I used two different functions:

In the first I copied the the value of the linked list in an array of int and in the second function, with a backtracking algorithm (performed on the array just created) I found the solutions.

This is my solution:

void BackTrack(int n, int s, int x[7], int z[7], int partial, int max, int check) {
if (n == s) {
int y = 0;
for (int i = 0; i < n; i++){
if (z[i] != 0 && check == 2 && partial == max) {
printf("%d ", z[i]);
y++;
}
}
if(y != 0)
printf("\n");
return;
}

z[s] = 0;
BackTrack(n, s + 1, x, z, partial, max, check);

if (x[s] + partial <= max) {
z[s] = x[s];
partial += x[s];
check++;
BackTrack(n, s + 1, x, z, partial, max, check);
}
}

void ARRAY(List *p) {
int *x = NULL;
int i;
for (i = 0; p != NULL; i++){
x = realloc(x, sizeof(int) * (i + 1));
x[i] = p->inf;
p = p->next;
}
int *z = malloc(sizeof(int) * i);
BackTrack(i, 0, x, z, 0, 50, 0);
}


But I wanna know if there is a way to do this without using before an array conversation as I did? So to fint directly the couples on the linked list. Thanks

Answer
void FindPairs(List *list, int sum) {

  struct list_element *i, *j;

  for (i = list; i; i = i->next) {
    if (i->inf > sum)
      continue;
    for (j = i->next; j; j = j->next) {
      if (i->inf + j->inf == sum)
        printf("%d %d\n", i->inf, j->inf);
    }
  }
}