[Δομημένος Προγραμματισμός]Εργασια Ε

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

Για οποιοδήποτε πρόβλημα με register/login, στείλτε email στο contact@thmmy.gr.

[timon]

Εργασία E

Ένα δίκτυο μετάδοσης εντολών, από ένα κεντρικό σταθμό προς έναν αριθμό υποσταθμών είναι, οργανωμένο με τη μορφή δυαδικού δένδρου. Για κάθε σταθμό υπάρχει ένας σταθμός από τον οποίο δέχεται εντολές και δύο σταθμοί προς τους οποίους διαβιβάζει εντολές. Όταν μια εντολή περνά από έναν ενδιάμεσο σταθμό s_i υφίσταται μια καθυστέρηση d_i. Όταν στον κεντρικό σταθμό s₀ δοθεί μια εντολή η οποία πρέπει να διαβιβασθεί προς τον σταθμό s_k ζητείται να βρεθεί ο χρόνος που θα χρειαστεί για να φτάσει η εντολή στον προορισμό της και οι σταθμοί από τους οποίους θα περάσει.

Να γραφεί το πρόγραμμα στο οποίο να ορίζεται η συνάρτηση recur η οποία να δέχεται, μέσα από τα ορίσματά της, την ταυτότητα του σταθμού προς τον οποίο θα διαβιβαστεί η εντολή και με μια recursion διαδικασία βρίσκει τη διαδρομή που θα ακολουθήσει η εντολή για να φτάσει στο σταθμό αυτόν.

 Η συνάρτηση main του προγράμματος να διαβάζει τον αριθμό των σταθμών και το χρόνο καθυστέρησης σε κάθε έναν από αυτούς, να διαβάζει τον σταθμό προορισμού και να καλεί τη συνάρτηση recur για να βρει τη διαδρομή που θα ακολουθήσει η εντολή για να φτάσει στον προορισμό της. Στη συνέχεια να υπολογίζει και να εκτυπώνει το χρόνο που θα χρειαστεί για να φτάσει η εντολή στον προορισμό της και τη διαδρομή που θα ακολουθήσει.

 Η μνήμη για την καταχώρηση των πινάκων που θα χρειαστούν στο πρόγραμμα να δεσμεύεται δυναμικά.

 

Βοηθητικές παρατηρήσεις

 

Για τη δημιουργία του δένδρου να ληφθεί υπ’ όψη ότι ο κάθε υποσταθμός λαμβάνει εντολές από έναν μόνο σταθμό και διαβιβάζει εντολές αποκλειστικά σε δύο μόνο υποσταθμούς (δυαδικό δένδρο)

Η καταχώριση της δομής του δυαδικού δένδρου να γίνεται σε ένα πίνακα με δυο στήλες στον οποίο σε κάθε γραμμή να αντιστοιχεί ένας σταθμός και ως στοιχεία της γραμμής να καταχωρούνται οι ταυτότητες των σταθμών προς τους οποίους αυτός διαβιβάζει εντολές. Ως ταυτότητες στους σταθμούς να δοθούν οι αντίστοιχοι  αριθμοί των γραμμών του πιο πάνω πίνακα.

Στον πίνακα αυτόν για τους σταθμούς που βρίσκονται στα φύλλα του δένδρου και για τους οποίους δεν υπάρχουν σταθμοί προς τους οποίους θα διαβιβάσουν εντολές να καταχωρείται η τιμή -1 στις αντίστοιχες θέσεις.   

Συμβουλευτείτε και το eThmmy για το Δένδρο και τον Πίνακα που είναι σε αρχείο word στο υλικό του μαθήματος

[El Niño]

ΚΑΤΕΒΑΣΤΕ ΤΟ ΑΡΧΕΙΟ .doc.....εχει το δεντρο οπως πρεπει να ειναι!!!!

εδιτ...το αρχειο .doc (για οσους δεν το ξερουν) βρισκεται στην καρτελα υλικο μαθηματος--->εργασιες....

κατεβαστε την και απο δω αμα θελετε!

[El Niño]

παρακληση...μην αρχισετε παλι τα ακαταπαυστα ποστς...διαβαστε και λιγο την ασκηση πριν ρωτησετε κατι γιατι πραγματικα στο τοπικ για την προηγουμενη εργασια δεν βγαζεις ακρη...

[Merlin]

Πως κάνω malloc σε δισδιάστατο πίνακα?

[ΡΕΣΑΛΤΟ]

Γενικά αν καποιος μπορεί να εξηγησει με απλά λογια τη διαδικασία δυναμικής δεσμευσης μνημης.....

[Γιώργος]

Πως κάνω malloc σε δισδιάστατο πίνακα?

Code:

int **vlammeno;
vlammeno = (int **) malloc(2*sizeof(int *));
vlammeno[0] = (int *) malloc(N*sizeof(int));
vlammeno[1] = (int *) malloc(N*sizeof(int));

Ή και με for μπορείς να το κάνεις το β' σκέλος.
Αντίστοιχα προχωράς για 2-3-4.... διαστάσεις.

SOS - μην ξεχνάτε να ΕΛΕΓΧΕΤΕ μετά από κάθε malloc την περίπτωση OUT OF MEMORY (aka vlammeno == NULL, κοκ).


Ο Κορτέσης είναι ό,τι να 'ναι, έτσι;
Βασικά προβλήματα που εντόπισα:

• Δεν διευκρινίζει ΠΟΥ θα αποθηκεύονται οι καθυστερήσεις. Υποθέτω extra πίνακας.
• Δεν διευκρινίζει πώς θα διαβαστούν οι κόμβοι. Δηλαδή ο πρώτος θα είναι ο κεντρικός;
• Δηλαδή βασικό "πρόβλημα" είναι πώς στο διάβολο ο χρήστης θα ξέρει ποιο είναι το head του δέντρου, ο κεντρικός-κεντρικός κόμβος. Μία σκέψη είναι να θεωρήσουμε τον κόμβο #1 σαν κεντρικό και να βγάλουμε μήνυμα λάθους αν ο χρήστης προσπαθήσει να λινκάρει άλλον κόμβο στον κόμβο #1.
• Αφήνει flu την περίπτωση ο χρήστης να λινκάρει δύο αρχικούς κόμβους σε ένα κόμβο (δηλαδή να δέχεται πληροφορίες από 2+ κόμβους) κι αν θέλει έλεγχο ή όχι.
• Και flu την περίπτωση με κόμβο ή κόμβους που παραμένουν ασύνδετοι. Εκεί οκ, βγάζεις μήνυμα "δεν υπάρχει σύνδεση".

[Merlin]

Μ' αρέσει που ήρθα σήμερα σπίτι με την νοοτροπία ότι θα ξεπετούσα την άσκηση στα γρήγορα και θα είχα αρκετό χρόνο και για την άσκηση στα ψηφιακά,χαχα έλεος είμαι ώρες-ώρες

[Γιώργος]

Επίσης έχετε υπόψην ότι θα χρειαστείτε για την recur κάποιον αλγόριθμο διάσχισης γράφου ή έστω... γιαλαντζί γράφου εν προκειμένω, ούτε καν structs δεν έχουμε.

Από εδώ:

http://en.wikipedia.org/wiki/Graph_traversal


Μπορείτε να ρίξετε μια ματιά. (BFS or DFS I'd say)

[ΡΕΣΑΛΤΟ]

Φίλε Γιώργο επειδή σε κόβω αλάνι, αμα καποια στιγμη βρεις χρονο και εχεις διαθεση και δεν εχεις τιποτα χειροτερο να κανεις, μηπως σου ειναι ευκολο να εξηγησεις τη λογικη της δυναμικής δέσμευσης μνημης, τουλαχιστον τα πρακτικα που θα μας χρειαστουν για να λυσουμε την ασκηση. Θα σωσεις πολυ κοσμο...

[Γιώργος]

Κοίτα.... δες ένα απλό παράδειγμα να στο κάνω λιανά.

block #1:

Code:

int table[5];

block #2:

Code:

int *table;

table = (int *) malloc(5*sizeof(int));

Τα δύο blocks κάνουν ακριβώς το ίδιο, δεσμεύουν πέντε θέσεις "πίνακα" για ακέραιους.
Το πρώτο block είναι απλό, το καταλαβαίνεις.

Όσον αφορά το 2ο block, εκεί όρισα την table σαν δείχτη σε Int. Γενικά, για την C, δείκτης και πίνακας είναι το ίδιο πράμα.

Αυτό που σε ενδιαφέρει είναι ότι: με την malloc λέω στο λειτουργικό σύστημα να πάρει 5 (συνεχόμενες νομίζω) θέσεις μνήμης, να τις οργανώσει όπως αυτή ξέρει και να λινκάρει τον δείκτη table στο πρώτο στοιχείο της.

Δηλαδή όταν γράφεις *table (δηλαδή εκεί που δείχνει ο δείκτης) είναι το ίδιο γράφοντας table[0]. Αντίστοιχα, το table[1] είναι επόμενη διεύθυνση μνήμης μετά το table[0]. Νομίζω είναι μετά 4 bytes, αλλά δεν σε ενδιαφέρει, καθώς η malloc έχει φροντίσει να "διαχωρίσει" τις θέσεις μνήμης κατάλληλα ώστε όταν γράφεις table[1] να ξέρει να πάει στην επόμενη θέση μνήμης.

Το 5*sizeof(int) λέει στην malloc αυτό, να επιστρέψει 5 θέσεις μνήμης με μέγεθος όσο είναι το μέγεθος του τύπου για int.

Το (int *) μπροστά απ' την malloc είναι απλά ένα casting που πρέπει να μπαίνει γιατί η malloc είναι void. Υποθέτω ότι μπαίνει ώστε να ξέρει ότι τα 30 bytes (5*4) να τα χωρίσει σε 5 blocks των int.



Τώρα γιατί να το κάνεις αυτό; Γιατί έτσι μπορείς να δεσμεύσεις πίνακα σε οποιοδήποτε σημείο του προγράμματος, καθώς μπορεί να μην ξέρεις εξ' αρχής το μέγεθος.

[Σημείωση: η αλήθεια είναι ότι η C νομίζω το επιτρέπει να δηλώσεις int table[5]; στην μέση του προγράμματος, αλλά η C99 νομίζω δεν το επιτρέπει....]


Επίσης είναι ιδιαίτερα χρήσιμο όταν δεσμεύεις χώρο για δομές δεδομένων (structs) που μπορεί να θέλουν μπόλικη μνήμη.



Εάν το λειτουργικό σύστημα δεν έχει την απαιτούμενη μνήμη που ζητάς, τότε η malloc επιστρέφει NULL. Γι' αυτό ελέγχουμε πάντα μετά από μια malloc αν το αποτέλεσμα είναι NULL και αν ναι, γράφουμε μήνυμα λάθους και τερματίζουμε επί τόπου το πρόγραμμα.



ps: πιθανώς οι περισσότεροι να ξεπαρθενευτείτε σε αυτήν την άσκηση με το πρώτο σας segmentation fault.

Δεν 'ναι τίποτα, κάποια μαλακία θα 'χει παιχτεί με την δέσμευση μνήμης ή με προσπέλαση σε μνήμη που δεν έχει δεσμευθεί.

[ΡΕΣΑΛΤΟ]

παιδι γραφεις,,,, 8)
μπυρες και πουπουλα!

[El Niño]

ας κανει και τοπικ να εξηγει για να το δουνε περισσοτεροι!ολοι θα το χρειαστουν!

[Γιώργος]

Παιδιά, για ό,τι χρειαστείτε υπάρχει topic :: βοηθητικά links!

Πχ αν πάτε στο πρώτο link, έχει αυτό το άρθρο: malloc & free - διαβάστε το!
Είναι μεγαλούτσικο, μην τρομάξετε, αλλά άμα κάτσετε με υπομονή τα λέει άψογα.



Η μαγεία είναι να ψάχνεις μόνος σου.

[El Niño]

νταξει δεν διαφωνω απλα δεν καταλαβαινω και πολυ αγγλικα !

[Emfanever]

[Σημείωση: η αλήθεια είναι ότι η C νομίζω το επιτρέπει να δηλώσεις int table[5]; στην μέση του προγράμματος, αλλά η C99 νομίζω δεν το επιτρέπει....]

νομίζω ισχυει το αντίστροφο...


και φυσικά μη ξεχνάτε να κάνετε στο τέλος του προγράμματος, ένα ωραίο, ανούσιο free!!!