Βασικά, ένας πίνακας είναι ένα σύνολο παρόμοιων αντικειμένων δεδομένων που είναι αποθηκευμένα σε τοποθεσίες διαδοχικών μνημών κάτω από μια κοινή επικεφαλίδα ή ένα όνομα μεταβλητής.
Ενώ μια συνδεδεμένη λίστα είναι μια δομή δεδομένων που περιέχει μια ακολουθία των στοιχείων όπου κάθε στοιχείο συνδέεται με το επόμενο στοιχείο. Υπάρχουν δύο πεδία σε ένα στοιχείο συνδεδεμένης λίστας. Το ένα είναι το πεδίο Δεδομένα και το άλλο είναι πεδίο συνδέσμου. Το πεδίο Δεδομένα περιέχει την πραγματική τιμή που θα αποθηκευτεί και θα επεξεργαστεί. Επιπλέον, το πεδίο σύνδεσης διατηρεί τη διεύθυνση του επόμενου στοιχείου δεδομένων στη συνδεδεμένη λίστα. Η διεύθυνση που χρησιμοποιείται για την πρόσβαση σε έναν συγκεκριμένο κόμβο είναι γνωστή ως δείκτης.
Μια άλλη σημαντική διαφορά μεταξύ μιας συστοιχίας και μιας συνδεδεμένης λίστας είναι ότι το Array έχει σταθερό μέγεθος και απαιτείται να δηλωθεί πριν, αλλά η Linked List δεν περιορίζεται στο μέγεθος και επεκτείνεται και συστέλλεται κατά την εκτέλεση.
Συγκριτικό διάγραμμα
| Βάση σύγκρισης | Παράταξη | Συνδεδεμένη λίστα |
|---|---|---|
| Βασικός | Είναι ένα σταθερό σύνολο σταθερού αριθμού στοιχείων δεδομένων. | Πρόκειται για ένα παραγγελθέν σύνολο που περιλαμβάνει έναν μεταβλητό αριθμό στοιχείων δεδομένων. |
| Μέγεθος | Καθορίζεται κατά τη διάρκεια της δήλωσης. | Δεν χρειάζεται να καθορίσετε. να αναπτυχθούν και να συρρικνωθούν κατά την εκτέλεση. |
| Κατανομή αποθήκευσης | Η θέση του στοιχείου κατανέμεται κατά τη διάρκεια της μεταγλώττισης. | Η θέση στοιχείου ορίζεται κατά τη διάρκεια του χρόνου εκτέλεσης. |
| Η σειρά των στοιχείων | Αποθηκεύτηκε διαδοχικά | Αποθηκεύτηκε τυχαία |
| Πρόσβαση στο στοιχείο | Απευθείας ή τυχαία προσπελάσιμη, δηλ. Καθορίστε το δείκτη ή τον δείκτη συστοιχίας. | Διαδοχικά προσπελάσιμη, δηλαδή, Traverse ξεκινώντας από τον πρώτο κόμβο της λίστας από το δείκτη. |
| Εισαγωγή και διαγραφή στοιχείου | Αργή σχετικά ως μετατόπιση απαιτείται. | Ευκολότερη, ταχύτερη και αποτελεσματικότερη. |
| Ερευνητικός | Δυαδική αναζήτηση και γραμμική αναζήτηση | γραμμική αναζήτηση |
| Απαιτείται μνήμη | πιο λιγο | Περισσότερο |
| Χρήση μνήμης | Ατελέσφορος | Αποτελεσματικός |
Ορισμός του πίνακα
Ένας πίνακας ορίζεται ως ένα σύνολο καθορισμένου αριθμού ομοιογενών στοιχείων ή στοιχείων δεδομένων. Σημαίνει ότι ένας πίνακας μπορεί να περιέχει μόνο έναν τύπο δεδομένων, είτε όλους τους ακέραιους αριθμούς, όλους τους αριθμούς κινητής υποδιαστολής ή όλους τους χαρακτήρες. Η δήλωση ενός πίνακα είναι η εξής:
int a [10].
Όπου το int ορίζει τον τύπο δεδομένων ή τα στοιχεία αποθήκευσης στοιχείων στοιχείων πίνακα. Το "a" είναι το όνομα ενός πίνακα και ο αριθμός που καθορίζεται μέσα στις αγκύλες είναι ο αριθμός των στοιχείων που μπορεί να αποθηκεύσει ένας πίνακας, αυτό ονομάζεται επίσης μέγεθος ή μήκος του πίνακα.
Ας δούμε μερικές από τις έννοιες που πρέπει να θυμόμαστε σχετικά με τις συστοιχίες:
- Τα μεμονωμένα στοιχεία ενός πίνακα μπορούν να προσπελαστούν περιγράφοντας το όνομα του πίνακα, ακολουθούμενο από δείκτη ή δείκτη (προσδιορίζοντας τη θέση του στοιχείου στη συστοιχία) μέσα στις αγκύλες. Για παράδειγμα, για να ανακτήσουμε το 5ο στοιχείο του πίνακα, πρέπει να γράψουμε μια δήλωση a [4].
- Σε κάθε περίπτωση τα στοιχεία μιας συστοιχίας θα αποθηκευτούν σε μια διαδοχική θέση μνήμης.
- Το πρώτο στοιχείο του πίνακα έχει δείκτη μηδέν [0]. Αυτό σημαίνει ότι το πρώτο και το τελευταίο στοιχείο θα οριστούν ως [0] και [9] αντίστοιχα.
- Ο αριθμός των στοιχείων που μπορούν να αποθηκευτούν σε μια διάταξη, δηλαδή το μέγεθος ενός πίνακα ή το μήκος του δίνεται από την ακόλουθη εξίσωση:
(άνω όριο-κάτω όριο) + 1
Για την παραπάνω διάταξη, θα ήταν (9-0) + 1 = 10. Όπου 0 είναι το κατώτερο όριο της συστοιχίας και το 9 είναι το άνω όριο της συστοιχίας. - Οι πίνακες μπορούν να διαβαστούν ή να γραφτούν μέσω του βρόχου. Εάν διαβάζουμε τη μονοδιάστατη διάταξη, απαιτεί ένα βρόχο για ανάγνωση και άλλο για τη γραφή (εκτύπωση) της συστοιχίας, για παράδειγμα:
ένα. Για την ανάγνωση ενός πίνακα
για (i = 0, i <= 9, i ++)
{scanf ("% d", & a [i]); }}
σι. Για τη σύνταξη ενός πίνακα
για (i = 0, i <= 9, i ++)
{printf ("% d", a [i]); }} - Στην περίπτωση μιας συστοιχίας 2-D, θα χρειαζόταν δύο βρόχους και παρόμοια n-διαστάσεων array θα χρειαζόταν n βρόχους.
Οι λειτουργίες που εκτελούνται σε συστοιχίες είναι:
- Δημιουργία πίνακα
- Τράβηγμα συστοιχίας
- Προσθήκη νέων στοιχείων
- Διαγραφή των απαιτούμενων στοιχείων.
- Τροποποίηση στοιχείου.
- Συγχώνευση συστοιχιών
Παράδειγμα
Το παρακάτω πρόγραμμα απεικονίζει την ανάγνωση και τη γραφή του πίνακα.
#include #include void main () { int a[10], i; printf("Enter the array"); for ( i= 0; i <= 9; i++) { scanf ( "%d", &a[ i ] ) ; } printf( "Enter the array" ); for (i = 0 ; i <= 9 ; i++) { printf ( "%d\n", a[ i ] ) ; } getch (); }
Ορισμός της συνδεδεμένης λίστας
Ο συνδεδεμένος κατάλογος είναι ένας συγκεκριμένος κατάλογος με ορισμένα στοιχεία δεδομένων που συνδέονται με ένα άλλο. Σε αυτό το κάθε στοιχείο δείχνει το επόμενο στοιχείο που αντιπροσωπεύει τη λογική σειρά. Κάθε στοιχείο ονομάζεται κόμβος, ο οποίος έχει δύο μέρη.
Το τμήμα INFO που αποθηκεύει τις πληροφορίες και το POINTER που δείχνει το επόμενο στοιχείο. Όπως γνωρίζετε για την αποθήκευση της διεύθυνσης, έχουμε μια μοναδική δομή δεδομένων στο C που ονομάζεται δείκτες. Επομένως, το δεύτερο πεδίο της λίστας πρέπει να είναι ένας τύπος δείκτη.
Οι τύποι των συνδεδεμένων λιστών είναι η λίστα που είναι απλά συνδεδεμένη, η λίστα διπλών συνδέσεων, η λίστα συνδεδεμένων εγκυκλίων, η εγκύκλιος λίστα διπλών συνδέσμων.
Οι λειτουργίες που εκτελούνται στη Συνδεδεμένη Λίστα είναι:
- Δημιουργία
- Τράβηγμα
- Εισαγωγή
- Διαγραφή
- Ερευνητικός
- Αληλουχία
- Απεικόνιση
Παράδειγμα
Το ακόλουθο απόσπασμα απεικονίζει τη δημιουργία μιας συνδεδεμένης λίστας:
struct node { int num; stuct node *next; } start = NULL; void create() { typedef struct node NODE; NODE *p, *q; char choice; first = NULL; do { p = (NODE *) malloc (sizeof (NODE)); printf ("Enter the data item\n"); scanf ("%d", & p -> num); if (p == NULL) { q = start; while (q -> next ! = NULL) { q = q -> next } p -> next = q -> next; q -> = p; } else { p -> next = start; start = p; } printf ("Do you want to continue (type y or n) ? \n"); scanf ("%c", &choice) ; } while ((choice == 'y') || (choice == 'Y')); }
Βασικές διαφορές μεταξύ πίνακα και συνδεδεμένης λίστας
- Ένας πίνακας είναι η δομή δεδομένων που περιέχει μια συλλογή παρόμοιων στοιχείων δεδομένων τύπου ενώ η λίστα των συνδεδεμένων θεωρείται ως μη πρωτόγονη δομή δεδομένων περιέχει μια συλλογή από μη ταξινομημένα συνδεδεμένα στοιχεία γνωστά ως κόμβοι.
- Στη συστοιχία τα στοιχεία ανήκουν σε ευρετήρια, δηλαδή εάν θέλετε να μπει στο τέταρτο στοιχείο πρέπει να γράψετε το όνομα της μεταβλητής με τον δείκτη ή τη θέση του μέσα στο τετράγωνο άγκιστρο.
Σε μια συνδεδεμένη λίστα, όμως, πρέπει να ξεκινήσετε από το κεφάλι και να περάσετε μέχρι να φτάσετε στο τέταρτο στοιχείο. - Ενώ η πρόσβαση σε μια συστοιχία στοιχείων είναι γρήγορη ενώ η λίστα συνδέσεων παίρνει γραμμικό χρόνο έτσι, είναι αρκετά πιο αργή.
- Οι λειτουργίες όπως η εισαγωγή και η διαγραφή σε συστοιχίες καταναλώνουν πολύ χρόνο. Από την άλλη πλευρά, η απόδοση αυτών των εργασιών σε συνδέσμους είναι γρήγορη.
- Οι πίνακες είναι σταθερού μεγέθους. Αντίθετα, οι συνδεδεμένοι κατάλογοι είναι δυναμικοί και ευέλικτοι και μπορούν να επεκταθούν και να συρρικνωθούν το μέγεθος τους.
- Σε μια συστοιχία, η μνήμη εκχωρείται κατά τη διάρκεια της μεταγλώττισης, ενώ σε μια συνδεδεμένη λίστα διατίθεται κατά τη διάρκεια της εκτέλεσης ή του χρόνου εκτέλεσης.
- Τα στοιχεία αποθηκεύονται διαδοχικά σε συστοιχίες ενώ αποθηκεύονται τυχαία σε συνδέσμους.
- Η απαίτηση της μνήμης είναι μικρότερη λόγω των πραγματικών δεδομένων που αποθηκεύονται στο ευρετήριο της συστοιχίας. Αντιθέτως, υπάρχει ανάγκη για περισσότερη μνήμη στις Συνδεδεμένες Λίστες λόγω της αποθήκευσης πρόσθετων επόμενων και προηγούμενων στοιχείων αναφοράς.
- Επιπλέον, η χρήση μνήμης είναι αναποτελεσματική στη συστοιχία. Αντίθετα, η χρήση μνήμης είναι αποτελεσματική στη συστοιχία.
συμπέρασμα
Οι πίνακες συστοιχίας και οι σύνδεσμοι είναι οι τύποι δομών δεδομένων που διαφέρουν ως προς τη δομή, την πρόσβαση και τις μεθόδους χειρισμού, την απαίτηση μνήμης και τη χρήση. Και έχουν ιδιαίτερο πλεονέκτημα και μειονέκτημα σε σχέση με την εφαρμογή του. Κατά συνέπεια, είτε μπορεί να χρησιμοποιηθεί ως ανά ανάγκη.
