Η συγχώνευση είναι μια ακόμη βασική λειτουργία των δομών δεδομένων. Η συγχώνευση δυο ταξινομημένων πινάκων έχει ως σκοπό τη δημιουργία ενός τρίτου πίνακα που θα περιέχει τα στοιχεία και των δύο αρχικών πινάκων, ταξινομημένα κατά την ίδια φορά.
Στη συνέχεια παρουσιάζεται ένα πρόγραμμα που πραγματοποιεί τη συγχώνευση δύο πινάκων Α[m] και Β[n] σε έναν πίνακα Γ[m+n]. Χρησιμοποιούνται τρεις δείκτες για τη χρήση των στοιχείων των πινάκων, πιο συγκεκριμένα ο δείκτης i για τον πίνακα Α, ο δείκτης j για τον πίνακα Β και ο δείκτης k για τον Γ.
A
1
|
4
|
6
|
8
|
11
|
12
|
17
|
Β
2
|
3
|
5
|
20
|
24
|
Γ
1
|
2
|
3
|
4
|
5
|
6
|
8
|
11
|
12
|
17
|
20
|
24
|
Η μέθοδος προχωρά ως εξής: Το μικρότερο στοιχείο από τους πίνακες Α και Β τοποθετείται στον πίνακα Γ με ταυτόχρονη αύξηση του αντίστοιχου δείκτη. Η διαδικασία αυτή επαναλαμβάνεται μέχρις ότου τελειώσουν τα στοιχεία του ενός πίνακα. Ύστερα τα υπόλοιπα στοιχεία του άλλου πίνακα μεταφέρονται στον πίνακα Γ.
ΠΡΟΓΡΑΜΜΑ Συγχώνευση_Πινάκων
ΣΤΑΘΕΡΕΣ
n = 7
m = 5
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Α[n], B[m], Γ[n+m], ί, j, k, t
ΑΡΧΗ
!Εισαγωγή στοιχείων στους πίνακες Α και Β
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ n
ΔΙΑΒΑΣΕ Α[i]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ m
ΔΙΑΒΑΣΕ B[j]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
!Συγχώνευση Πινάκων
i ←1
j <- 1
k <- 1
k <- 1
ΟΣΟ i ≤ n ΚΑΙ j ≤ m ΕΠΑΝΕΛΑΒΕ
ΑΝ Α[i] < Β[j] ΤΟΤΕ
Γ[k] ← Α[i]
i ← i+1
ΑΛΛΙΩΣ
Γ[k] ← B[j]
j ← j+1
ΤΕΛΟΣ_ΑΝ
k ← k+1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΝ i > n ΤΟΤΕ
ΓΙΑ t ΑΠΟ k ΜΕΧΡΙ n+m
Γ[t] ← B[j]
j ← j+1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΛΛΙΩΣ
ΓΙΑ t ΑΠΟ k ΜΕΧΡΙ n+m
Γ[t] ← Α[i]
i ← i+1
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ Συγχώνευση_Πινάκων
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου