Μετά τις συστοιχίες, η δεύτερη πιο δημοφιλής δομή δεδομένων είναι η Linked List. Μια συνδεδεμένη λίστα είναι μια γραμμική δομή δεδομένων, κατασκευασμένη από μια αλυσίδα κόμβων στην οποία κάθε κόμβος περιέχει μια τιμή και ένα δείκτη στον επόμενο κόμβο της αλυσίδας. Σε αυτό το άρθρο, ας δούμε πώς να εφαρμόσουμε μια συνδεδεμένη λίστα στο C.
Τι είναι η συνδεδεμένη λίστα στο C;
Μια συνδεδεμένη λίστα είναι μια γραμμική δομή δεδομένων. Κάθε συνδεδεμένη λίστα έχει δύο μέρη, την ενότητα δεδομένων και την ενότητα διευθύνσεων που κρατά τη διεύθυνση του επόμενου στοιχείου στη λίστα, η οποία ονομάζεται κόμβος.
Το μέγεθος της συνδεδεμένης λίστας δεν είναι σταθερό και τα στοιχεία δεδομένων μπορούν να προστεθούν σε οποιαδήποτε τοποθεσία της λίστας. Το μειονέκτημα είναι ότι για να φτάσουμε σε έναν κόμβο, πρέπει να περάσουμε από τον πρώτο κόμβο στον κόμβο που χρειαζόμαστε. Η συνδεδεμένη λίστα είναι σαν πίνακας αλλά σε αντίθεση με έναν πίνακα, δεν αποθηκεύεται διαδοχικά στη μνήμη.
Οι πιο δημοφιλείς τύποι μιας συνδεδεμένης λίστας είναι:
Παράδειγμα συνδεδεμένης λίστας
Μορφή: [δεδομένα, διεύθυνση]
το καλύτερο java ide για το ubuntu
Κεφάλι -> [3.1000] -> [43.1001] -> [21.1002]
Στο παράδειγμα, ο αριθμός 43 υπάρχει στη θέση 1000 και η διεύθυνση υπάρχει στον προηγούμενο κόμβο. Έτσι απεικονίζεται μια συνδεδεμένη λίστα.
Βασικές λειτουργίες συνδεδεμένης λίστας
Υπάρχουν πολλές συναρτήσεις που μπορούν να εφαρμοστούν στη συνδεδεμένη λίστα στο C. Ας προσπαθήσουμε να τις κατανοήσουμε με τη βοήθεια ενός παραδείγματος προγράμματος.Αρχικά, δημιουργούμε μια λίστα, την εμφανίζουμε, εισάγουμε σε οποιαδήποτε τοποθεσία, διαγράφουμε μια τοποθεσία. Ο παρακάτω κώδικας θα σας δείξει πώς να εκτελέσετε λειτουργίες στη λίστα.
#include #include void create () void display () void insert_begin () void insert_end () void insert_pos () void delete_begin () void delete_end () void delete_pos () struct node {int info struct node * next} struct node * start = NULL int main () {int επιλογή ενώ (1) {printf ('n MENU n') printf ('n 1.Create n') printf ('n 2.Display n') printf ('n 3. Εισαγάγετε στο η αρχή n ') printf (' n 4. Εισαγωγή στο τέλος n ') printf (' n 5. Εισαγωγή στην καθορισμένη θέση n ') printf (' n 6. Διαγραφή από την αρχή n ') printf (' n 7. Διαγραφή από το τέλος n ') printf (' n 8. Διαγραφή από την καθορισμένη θέση n ') printf (' n 9. Έξοδος n ') printf (' n ----------------- --------------------- n ') printf (' Εισαγάγετε την επιλογή σας: t ') scanf ('% d ', & option) διακόπτης (επιλογή) {περίπτωση 1 : create () break case 2: display () break case 3: insert_begin () break case 4: insert_end () break case 5: insert_pos () break case 6: delete_begin () break case 7: delete_end () break case 8: delete_pos () break case 9: exit (0) break default: printf ('n Wrong Choice: n') break}} επιστροφή 0} voi d create () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') έξοδος (0) } printf ('nΕισαγάγετε την τιμή δεδομένων για τον κόμβο: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} other {ptr = start ενώ (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} κενή οθόνη () {struct node * ptr if (start == NULL) {printf ('nList είναι κενό: n ') return} else {ptr = start printf (' nΤα στοιχεία λίστας είναι: n ') ενώ (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> next}}} void insert_begin () {struct node * temp temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nΕισαγάγετε το τιμή δεδομένων για τον κόμβο: t ') scanf ('% d ', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} other {temp-> next = start start = temp }} void insert_end () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') επιστροφή} Π rintf ('nΕισαγάγετε την τιμή δεδομένων για τον κόμβο: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} other {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void insert_pos () {struct node * ptr, * temp int i, pos temp = (δομή κόμβου *) malloc ( sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nΕισαγάγετε τη θέση για τον νέο κόμβο που θα εισαχθεί: t') scanf ('% d') , & pos) printf ('nΕισαγάγετε την τιμή δεδομένων του κόμβου: t') scanf ('% d', & temp-> info) temp-> next = NULL if (pos == 0) {temp-> next = start start = temp} else {για (i = 0, ptr = startinext if (ptr == NULL) {printf ('nPosition not found: [Handle with care] n') return}} temp-> next = ptr-> επόμενο ptr -> next = temp}} void delete_begin () {struct node * ptr if (ptr == NULL) {printf ('nList is Empty: n') return} other {ptr = start start = start-> next printf (' nΤο διαγραμμένο στοιχείο είναι:% dt ', ptr-> info) free (ptr)}} void delete_end () {struct node * temp, * ptr if (start == NULL) {printf (' nList is Empty: ') έξοδος (0) } αλλιώς εάν (start-> next == NULL) {ptr = start start = NULL printf ('nΤο διαγραμμένο στοιχείο είναι:% dt', ptr-> info) δωρεάν (ptr)} άλλο {ptr = έναρξη ενώ (ptr- > επόμενο! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ('nΤο διαγραμμένο στοιχείο είναι:% dt', ptr-> info) δωρεάν (ptr)}} άκυρο delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nThe List is Empty: n') exit (0)} else {printf ('nΕισαγάγετε τη θέση του κόμβου προς διαγραφή : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nΤο διαγραμμένο στοιχείο είναι:% dt ', ptr-> info) δωρεάν (ptr )} αλλιώς {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not found: n') return}} temp-> next = ptr-> next printf ('nΤο διαγραμμένο στοιχείο είναι: % dt ', ptr-> info) δωρεάν (ptr)}}}Το πρώτο μέρος αυτού του κώδικα δημιουργεί μια δομή. Δημιουργείται μια δομή συνδεδεμένης λίστας έτσι ώστε να μπορεί να διατηρεί τα δεδομένα και τη διεύθυνση όπως τη χρειαζόμαστε. Αυτό γίνεται για να δώσει στον μεταγλωττιστή μια ιδέα για το πώς πρέπει να είναι ο κόμβος.
struct κόμβος {int info struct node * next}Στη δομή, έχουμε μια μεταβλητή δεδομένων που ονομάζεται info για να κρατήσει δεδομένα και μια μεταβλητή δείκτη για να δείξει τη διεύθυνση. Υπάρχουν διάφορες λειτουργίες που μπορούν να γίνουν σε μια συνδεδεμένη λίστα, όπως:
- δημιουργώ()
- απεικόνιση()
- insert_begin ()
- insert_end ()
- ] insert_pos ()
- delete_begin ()
- delete_end ()
- delete_pos()
Αυτές οι λειτουργίες καλούνται από την κύρια λειτουργία βάσει μενού. Στην κύρια λειτουργία, λαμβάνουμε πληροφορίες από τον χρήστη με βάση τη λειτουργία που ο χρήστης θέλει να κάνει στο πρόγραμμα. Στη συνέχεια η είσοδος αποστέλλεται στη θήκη διακόπτη και βασίζεται στην είσοδο του χρήστη.
Με βάση την είσοδο που παρέχεται, θα καλείται η συνάρτηση. Στη συνέχεια, έχουμε διαφορετικές λειτουργίες που πρέπει να επιλυθούν. Ας ρίξουμε μια ματιά σε καθεμία από αυτές τις λειτουργίες.
Δημιουργία συνάρτησης
Πρώτον, υπάρχει μια λειτουργία δημιουργίας για τη δημιουργία της συνδεδεμένης λίστας. Αυτός είναι ο βασικός τρόπος δημιουργίας της συνδεδεμένης λίστας. Ας δούμε τον κώδικα.
void create () {struct node * temp, * ptr printf ('nΕισαγάγετε την τιμή δεδομένων για τον κόμβο: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL ) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}}Παραγωγή
Πρώτον, δημιουργούνται δύο δείκτες του τύπου κόμβος, ptr και temp . Παίρνουμε την τιμή που απαιτείται για να προστεθεί στη συνδεδεμένη λίστα από τον χρήστη και την αποθηκεύουμε σε πληροφορίες μέρος της μεταβλητής temp και εκχωρούμε temp του επόμενου που είναι το τμήμα διεύθυνσης στο null. Υπάρχει ένας δείκτης έναρξης που κρατά την αρχή της λίστας. Στη συνέχεια, ελέγχουμε για την έναρξη της λίστας. Εάν η αρχή της λίστας είναι μηδενική, τότε αντιστοιχίζουμε temp στον αρχικό δείκτη. Διαφορετικά, διασχίζουμε το τελευταίο σημείο όπου τα δεδομένα έχουν προστεθεί.
Για αυτό, αντιστοιχίζουμε την τιμή έναρξης και διασχίζουμε μέχρι ptr-> next = null . Στη συνέχεια εκχωρούμε ptr-> επόμενο η διεύθυνση temp. Με παρόμοιο τρόπο, υπάρχει κωδικός για εισαγωγή στην αρχή, εισαγωγή στο τέλος και εισαγωγή σε καθορισμένη θέση.
Λειτουργία οθόνης
Εδώ είναι ο κωδικός για τη λειτουργία προβολής.
void display () {struct node * ptr if (start == NULL) {printf ('nList is κενό: n') return} other {ptr = start printf ('nΤα στοιχεία λίστας είναι: n') ενώ (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> επόμενο}}}Παραγωγή
υλοποιήστε ελάχιστο σωρό σε java
Στη λειτουργία εμφάνισης, ελέγχουμε πρώτα εάν η λίστα είναι κενή και επιστρέφουμε εάν είναι κενή. Στο επόμενο μέρος, εκχωρούμε την τιμή έναρξης στο ptr. Στη συνέχεια εκτελούμε έναν βρόχο έως ότου το ptr είναι null και εκτυπώνουμε το στοιχείο δεδομένων για κάθε κόμβο, έως ότου το ptr είναι null, το οποίο καθορίζει το τέλος της λίστας.
Διαγραφή συνάρτησης
Ακολουθεί το απόσπασμα κώδικα για να διαγράψετε έναν κόμβο από τη συνδεδεμένη λίστα.
void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nThe List is Empty: n') exit (0)} other {printf ('nΕισαγάγετε τη θέση του κόμβος προς διαγραφή: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nΤο διαγραμμένο στοιχείο είναι:% dt ', ptr-> info ) δωρεάν (ptr)} άλλο {ptr = έναρξη για (i = 0inext if (ptr == NULL) {printf ('nPosition not found: n') return}} temp-> next = ptr-> next printf ('nThe το διαγραμμένο στοιχείο είναι:% dt ', ptr-> info) δωρεάν (ptr)}}}Παραγωγή
Στη διαδικασία διαγραφής, ελέγχει πρώτα εάν η λίστα είναι κενή, εάν ναι υπάρχει. Εάν δεν είναι κενό, ζητά από το χρήστη να διαγραφεί η θέση. Μόλις ο χρήστης εισέλθει στη θέση, ελέγχει αν είναι η πρώτη θέση, εάν ναι αντιστοιχεί ptr για να ξεκινήσετε και να μετακινήσετε το δείκτη έναρξης στην επόμενη τοποθεσία και διαγράφει το ptr. Εάν το η θέση δεν είναι μηδενική , τότε τρέχει ένα για βρόχο από το 0 μέχρι τη θέση που εισήγαγε ο χρήστης και αποθηκεύτηκε στο θέση μεταβλητός. Υπάρχει μια δήλωση if για να αποφασίσει εάν η καταχωρισμένη θέση δεν είναι παρούσα. Αν Το ptr είναι ίσο με το μηδέν , τότε δεν είναι παρόν.
Εμείς εκχώρηση ptr σε θερμοκρασία στο βρόχο for, και το ptr μεταβαίνει στο επόμενο μέρος. Μετά από αυτό όταν βρεθεί η θέση. Κάνουμε τη μεταβλητή temp για να κρατήσουμε την τιμή του ptr-> επόμενο παρακάμπτοντας έτσι το ptr. Στη συνέχεια διαγράφεται το ptr. Ομοίως, μπορεί να γίνει για τη διαγραφή πρώτου και τελευταίου στοιχείου.
Διπλά συνδεδεμένη λίστα
Ονομάζεται λίστα διπλά συνδεδεμένων επειδή υπάρχουν δύο δείκτες , ένα σημείο στον επόμενο κόμβο και άλλα σημεία στον προηγούμενο κόμβο. Οι λειτουργίες που εκτελούνται σε διπλά συνδεδεμένες είναι παρόμοιες με εκείνες μιας λίστας μεμονωμένων συνδέσεων. Αυτός είναι ο κωδικός για βασικές λειτουργίες.
#include #include struct Node typedef struct Node * PtrToNode typedef PtrToNode List typedef PtrToNode Θέση δομή κόμβος {int e Position προηγούμενη θέση επόμενη} κενό Εισαγωγή (int x, List l, Position p) {Position TmpCell TmpCell = (δομή Node *) malloc (sizeof (struct Node)) εάν (TmpCell == NULL) printf ('Memory out of spacen') αλλιώς {TmpCell-> e = x TmpCell-> previous = p TmpCell-> next = p-> next p-> next = TmpCell}} άκυρο Διαγραφή (int x, List l) {Θέση p, p1, p2 p = Εύρεση (x, l) if (p! = NULL) {p1 = p -> προηγούμενο p2 = p -> επόμενο p1 - > next = p -> next if (p2! = NULL) // εάν ο κόμβος δεν είναι ο τελευταίος κόμβος p2 -> προηγούμενος = p -> προηγούμενος} αλλού printf ('Το στοιχείο δεν υπάρχει !!! n')} άκυρο Εμφάνιση (Λίστα l) {printf ('Το στοιχείο λίστας είναι ::') Θέση p = l-> επόμενο ενώ (p! = NULL) {printf ('% d ->', p-> e) p = p- > next}} int main () {int x, pos, ch, i List l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> προηγούμενο = NULL l-> next = NULL List p = l printf («ΕΦΑΡΜΟΓΗ ΔΙΠΛΩΣ ΣΥΝΔΕΣΜΟΥ ΛΙΣΤΑΣ του L IST ADTnn ') {printf (' nn1). CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnn Εισαγάγετε την επιλογή :: ') scanf ('% d ', & ch) switch (ch) {case 1: p = l printf (' Enter the element to be insert :: ') scanf ('% d', & x) printf ('Εισαγάγετε τη θέση του στοιχείου ::') scanf ('% d', & pos) για (i = 1 inext} Εισαγωγή (x, l, p) break case 2: p = l printf ('Enter the element to be delete ::') scanf ('% d', & x) Delete (x, p) break case 3: Display (l) break}} ενώ (ch<4) } Παραγωγή
τι κάνει το math.abs στην Ιάβα
Έτσι, όπως μπορείτε να δείτε, η έννοια των λειτουργιών είναι αρκετά απλή. Η διπλά συνδεδεμένη λίστα έχει τις ίδιες λειτουργίες με αυτήν της μοναδικής συνδεδεμένης λίστας στη γλώσσα προγραμματισμού Γ. Η μόνη διαφορά είναι ότι υπάρχει μια άλλη μεταβλητή διεύθυνσης που βοηθά να διασχίζει τη λίστα καλύτερα σε μια λίστα διπλής σύνδεσης.
Ελπίζω να έχετε καταλάβει πώς να εκτελείτε βασικές λειτουργίες σε μια λίστα με διπλά συνδεδεμένα στο Γ.
Εάν θέλετε να μάθετε τη συνδεδεμένη λίστα στην Ιάβα, εδώ είναι .
Εάν συναντήσετε οποιεσδήποτε ερωτήσεις, μη διστάσετε να κάνετε όλες τις ερωτήσεις σας στην ενότητα σχολίων του 'Linked List in C' και η ομάδα μας θα χαρεί να απαντήσει.