Practice #4
Leçon 13 sur 14 du cours Liste chaînée - Série Structures de données n°5 de Coddy.
Défi
FacileÉtant donné deux tableaux d'entiers triés a et b (les valeurs de deux listes chaînées triées), écrivez une fonction mergeSorted qui renvoie un seul tableau trié contenant toutes les valeurs des deux entrées.
Utilisez une liste chaînée pour résoudre ce problème ! Parcourez les deux listes en parallèle, en ajoutant de manière répétée la plus petite tête dans votre résultat.
Vous devez utiliser la classe LinkedList (fournie dans linkedlist.<ext> ainsi que node.<ext>) — n'utilisez pas les fonctions intégrées du langage comme l'inversion de tableaux, le découpage (slicing) ou les opérations de liste de la bibliothèque standard pour calculer le résultat.
Essayez vous-même
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char line1[8192];
char line2[8192];
if (!fgets(line1, sizeof(line1), stdin)) line1[0] = '\0';
if (!fgets(line2, sizeof(line2), stdin)) line2[0] = '\0';
int a[4096];
int alen = 0;
char* tok = strtok(line1, " \t\r\n");
while (tok) { a[alen++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
int b[4096];
int blen = 0;
tok = strtok(line2, " \t\r\n");
while (tok) { b[blen++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
int rs = 0;
int* r = mergeSorted(a, alen, b, blen, &rs);
for (int idx = 0; idx < rs; idx++) {
if (idx > 0) printf(" ");
printf("%d", r[idx]);
}
printf("\n");
return 0;
}
