☰

Λίστα με δείκτες

Συνδεδεμένες Λίστες

Παράδειγμα συνδεδεμένης λίστας με δείκτες

Συνδεδεμένη λίστα με αρχικό κόμβο δείκτη.

#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;
}