תרגול מס׳ 5

שיעור 14 מתוך 14 בקורס רשימה מקושרת דו-כיוונית – סדרת מבני נתונים מס׳ 6 של Coddy.

אתגר

קל

בהינתן מערך מספרים שלמים ממויין arr (הערכים של רשימה מקושרת דו־כיוונית ממוינת) ומספר שלם target, כתבו פונקציה countPairs שמחזירה את מספר הזוגות של אינדקסים (i, j) כך שיתקיימו i < j וגם arr[i] + arr[j] == target.

הניחו שהקלט אינו מכיל ערכים כפולים.

השתמשו ברשימה מקושרת דו־כיוונית כדי לפתור את הבעיה! השתמשו בשני מצביעים משני הקצוות, הנעים פנימה.

עליכם להשתמש במחלקה DoublyLinkedList (שניתנת בקובץ doublylinkedlist.<ext> יחד עם node.<ext>) — אל תשתמשו בפונקציות מובנות של השפה, כמו reverse, חיתוך, sort או פעולות רשימה של הספרייה הסטנדרטית, כדי לחשב את התוצאה.

נסו בעצמכם

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"

int main() {
    char line1[8192];
    char line2[64];
    if (!fgets(line1, sizeof(line1), stdin)) line1[0] = '\0';
    if (!fgets(line2, sizeof(line2), stdin)) line2[0] = '\0';
    int arr[4096];
    int len = 0;
    char* tok = strtok(line1, " \t\r\n");
    while (tok) { arr[len++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
    int n = atoi(line2);
    int r = countPairs(arr, len, n);
printf("%d\n", r);
    return 0;
}