Λίστα με δείκτες
Συνδεδεμένες Λίστες
Παράδειγμα συνδεδεμένης λίστας με δείκτες
Συνδεδεμένη λίστα με αρχικό κόμβο δείκτη.
#include <stdio.h> #include <stdlib.h> // Ορίζω έναν τύπο δεδομένων με όνομα έστω UINT typedef unsigned int UINT; /* * Ορίζω ένα struct με όνομα έστω Node * Στις συνδεδεμένες λίστες χρησιμοποιείται ο όρος κόμβος(Node) * Μία λίστα αποτελείται από πολλούς συνδεδεμένους κόμβους * Κάθε κόμβος περιέχει έναν δείκτη που "δείχνει" στον επόμενο κόμβο */ struct Node { UINT data; struct Node *next; }; //Κάνω typedef το struct Node typedef struct Node ListNode; /* * Δημιουργεί έναν καινούριο κόμβο και εισάγει τα δεδομένα * Για τη δημιουργία δεσμεύει μνήμη με την malloc() * Επιστρέφει τη διεύθυνση του κόμβου * Μπορεί να κληθεί και από τον πρώτο κόμβο που αρχικά είναι NULL */ ListNode *createNode(UINT e) { ListNode *node = (ListNode*)malloc(sizeof(ListNode)); node->data = e; node->next = NULL; return node; } /* * Ελέγχει αν η λίστα είναι άδεια, επιστρέφει 1 ή 0 * Ο έλεγχος γίνεται στον πρώτο κόμβο (start) */ int isEmpty(ListNode *n) { if(n == NULL) { return 1; } else { return 0; } } /* * Επιστρέφει τον αριθό των κόμβων της λίστας */ int getNumOfNodes(ListNode *node) { int counter = 0; while(node != NULL) { counter++; node = node->next; } return counter; } /* * Προσθέτει κόμβο στο τέλος της λίστας */ void addNodeAtEnd(ListNode *first, UINT e) { ListNode *temp = first; while(temp->next != NULL) { temp = temp->next; } temp->next = createNode(e); } /* * Προσθέτει κόμβο στην αρχή της λίστας */ ListNode *addNodeAtStart(ListNode *first, UINT e) { ListNode *temp = createNode(e); temp->next = first; return temp; } /* * Διαγράφει τον πρώτο κόμβο */ ListNode *deleteFirstNode(ListNode *first) { ListNode *temp = first->next; free(first); return temp; } /* * Διαγράφει τον τελευταίο κόμβο */ ListNode *deleteLastNode(ListNode *first) { ListNode *temp = first; if(first->next == NULL) { free(first->next); return NULL; } else { while(temp->next) { if((temp->next)->next == NULL) { free(temp->next); temp->next = NULL; break; } temp = temp->next; } return first; } } /* * Αναζητεί στοιχείο μέσα στη λίστα. Επιστρέφει 1 ή 0 * Αρχίζει πάντα από τον πρώτο κόμβο (first) */ int search(ListNode *first, UINT e) { int result = 0; while(first != NULL) { if(first->data == e) { result = 1; break; } first = first->next; } return result; } /* * Εκτυπώνει τη λίστα */ void printList(ListNode *first) { while(first != NULL) { printf("%d\t", (int)first->data); first = first->next; } } /* * Επιστρέφει τη διεύθυνση του κόμβου από συγκεκριμένη θέση * Αν είναι κενή η λίστα ή η θέση εκτός ορίου επιστρέφει NULL */ ListNode *getNodeAt(ListNode *first, unsigned int position) { /* Αφήνεται ως άσκηση*/ } /* * Επιστρέφει τη διεύθυνση του επόμενου κόμβου */ ListNode *getNext(ListNode *node) { /* Αφήνεται ως άσκηση*/ } /* * Επιστρέφει το στοιχείο (δεδομένα) από έναν κόμβο */ UINT getElement(ListNode *node) { /* Αφήνεται ως άσκηση*/ } /* * Εισάγει ένα νέο στοιχείο μετά από κάποιον κόμβο */ void insertAfter(ListNode *node, UINT e) { /* Αφήνεται ως άσκηση*/ } /* * Διαγράφει όλη τη λίστα */ void emptyList(ListNode *node) { /* Αφήνεται ως άσκηση*/ } int main() { /* * Αρχικός δείκτης με αρχική τιμή NULL * Δείχνει πάντα τον πρώτο κόμβο */ ListNode *start = NULL; /* * Μενού */ UINT e; int i=1; do { puts("1. Create List"); puts("2. Check if Empty"); puts("3. Get Number of Nodes"); puts("4. Add Node at End"); puts("5. Add Node at Start"); puts("6. Delete First Node"); puts("7. Delete Last Node"); puts("8. Search Node"); puts("9. Print List Nodes"); puts("0. Exit\n"); scanf("%d", &i); //system("clear"); /* UNIX */ //system("cls"); /* DOS */ switch(i) { case 1: /* creates first node */ if(!isEmpty(start)) { puts("oops, there is a list\n"); } else { printf("give element of first node: "); scanf("%d", &e); start = createNode(e); } break; case 2: /* checks if empty */ if(isEmpty(start)) puts("the list is Empty\n"); else puts("the list is NOT Empty\n"); break; case 3: /* gets number of nodes */ if(isEmpty(start)) puts("oops, the list is Empty\n"); else printf("Number of Nodes: %d\n\n", getNumOfNodes(start)); break; case 4: /* adds a new node at the end of the list or first if it's empty */ printf("give element to add: "); scanf("%d", &e); if(isEmpty(start)) { start = createNode(e); } else { addNodeAtEnd(start, e); } puts("Node added!\n"); break; case 5: /* adds a new node at the start of the list or first if it's empty */ printf("give element to add: "); scanf("%d", &e); if(isEmpty(start)) { start = createNode(e); } else { start = addNodeAtStart(start, e); } puts("Node added!\n"); break; case 6: if(isEmpty(start)) puts("oops, the list is Empty\n"); else { start = deleteFirstNode(start); puts("deleted\n"); } break; case 7: /* delete last node */ if(isEmpty(start)) { puts("oops, the list is Empty\n"); } else { start = deleteLastNode(start); puts("deleted\n"); } break; case 8: /* */ printf("give element to search: "); scanf("%d", &e); if(search(start, e)) puts("ok, element found\n"); else puts("oops, element NOT found\n"); break; case 9: printList(start); /* prints the list (all element values) */ printf("\n\n"); break; case 0: i=0; break; default: break; } printf("---------------------------------\n"); } while(i!=0); getchar(); return 0; }