תרגול #4
שיעור 13 מתוך 14 בקורס רשימה מקושרת – סדרת מבני נתונים #5 של Coddy.
אתגר
קלבהינתן שני מערכים של מספרים שלמים ממוינים, a ו־b (הערכים של שתי רשימות מקושרות ממוינות), כתבו פונקציה mergeSorted שמחזירה מערך ממוין יחיד המכיל את כל הערכים משתי הקלטים.
השתמשו ברשימה מקושרת כדי לפתור את הבעיה! עברו על שתי הרשימות במקביל, והוסיפו שוב ושוב את הראש הקטן יותר לתוצאה.
עליכם להשתמש במחלקה LinkedList (שמסופקת בקובץ linkedlist.<ext> יחד עם node.<ext>) — אל תשתמשו בפונקציות מובנות של השפה, כמו פעולת ההיפוך המובנית של מערכים, חיתוך או פעולות רשימה מהספרייה הסטנדרטית, כדי לחשב את התוצאה.
נסו בעצמכם
#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;
}
כל השיעורים ביחידה רשימה מקושרת – סדרת מבני נתונים #5
תרגלו בעצמכם: קומפיילר C אונליין