☰

Λίστα με πίνακα

Παράδειγμα Λίστας

Υλοποίηση με πίνακα

#include <stdio.h>
  
  /*
   * Ορίζω μέγιστο πλήθος για τη λίστα
  */
  #define MAX 5
  
  /*
   * Ορίζω έναν τύπο δεδομένων με όνομα Element
   * Το Element μπορεί να είναι ένα struct
  */ 
  typedef unsigned int Element;
  
  /*
   * Ορίζω ένα struct με όνομα List
  */
  typedef struct {
    int length;
    Element data[MAX];
  }List;
  
  /*
   * Συνάρτηση αρχικοποίησης, καλείται πρώτη πριν από όποια άλλη
   * Μπορεί να κληθεί επίσης για να μηδενίσει τη λίστα
  */ 
  void create(List *l) {
    l->length = 0;
  }
  
  /*
   * Ελέγχει αν η λίστα είναι άδεια, επιστρέφει 1 ή 0
  */
  int isEmpty(List l) {
    if(l.length == 0)
      return 1;
    else
      return 0;
  }
  
  /*
   * Ελέγχει αν η λίστα είναι γεμάτη, επιστρέφει 1 ή 0
  */ 
  int isFull(List l) {
    if(l.length == MAX)
      return 1;
    else
      return 0;
  }
  
  /*
   * Προσθέτει ένα στοιχείο στo τέλος της λίστας, επιστρέφει 1 ή 0
  */ 
  int addLast(List *l, Element e) {
    if(isFull(*l)) {
      return 0;
    } else {
      l->data[l->length] = e;
      l->length++;
      return 1;
    }
  }
  
  /*
   * Προσθέτει ένα στοιχείο στην αρχή της λίστας.
   * Πρέπει να γίνει μεταφορά (shift) των στοιχείων κατά μία θέση εμπρός
  */
  int addFirst(List *l, Element e) {
    if(isFull(*l)) {
      return 0;
    } else {
      int i;
      for(i = l->length; i>0; i--) {
        l->data[i] = l->data[i-1];
      }
      l->data[0] = e;
      l->length++;
      return 1;
    }
  }
  
  /*
   * Εισάγει ένα στοιχείο ανάμεσα στα άλλα στοιχεία της λίστας.
   * Πρέπει να γίνει μερική μεταφορά (shift) των στοιχείων κατά μία θέση εμπρός.
   * Η αρίθμηση της θέσης (position) αρχίζει από το 0. 
  */
  int insertElementAt(List *l, Element e, int position) {
    if(isFull(*l)) {
      return 0;
    } else if(position < 0 || position > l->length) {
      return 0;
    } else {
      int i;
      for(i = l->length; i>position; i--) {
        l->data[i] = l->data[i-1];
      }
      l->data[position] = e;
      l->length++;
      return 1;
    }
  }
  
  /*
   * Aφαιρεί το τελευταίο στοιχείο της λίστας
   * Και επιστρέφει τη διεύθυνση του στοιχείου, έτσι ο χρήστης μπορεί να δει ποιο ήταν
   * Αν είναι άδεια επιστρέφει NULL (η NULL μπορεί να χρησιμοποιηθεί με δείκτες)
  */
  Element *deleteLast(List *l) {
    Element *e;
    if(isEmpty(*l)) {
      return NULL;
    } else {
      l->length--;
      e = &(l->data[l->length]);
      return e;
    }
  }
  
  /*
   * Aφαιρεί το πρώτο στοιχείο της λίστας
   * Και επιστρέφει τη διεύθυνση του στοιχείου, έτσι ο χρήστης μπορεί να δει ποιο ήταν
   * Πρέπει να γίνει μετακίνηση (shift) προς τα πίσω
   * Αν είναι άδεια επιστρέφει NULL (η NULL μπορεί να χρησιμοποιηθεί με δείκτες)
  */
  Element *deleteFirst(List *l) {
    /* Αφήνεται ως άσκηση */
  }
  
  /*
   * Aφαιρεί κάποιο στοιχείο της λίστας από συγκεκριμένη θέση
   * Θα πρέπει να γίνει μερική μεταφορά (shift) των στοιχείων
   * Επιστρέφει επίσης τη διεύθυνση του διαγραμμένου στοιχείου 
  */
  Element *deleteElementAt(List *l, int position) {
    /* Αφήνεται ως άσκηση */
  }
  
  /*
   * Αναζητεί ένα στοχεί από τη λίστα.
   * Επιστρέφει 1 αν βρεθεί αλλιώς 0
   * Τα κριτήρια αναζήτησης εξαρτώνται από το είδος του στοιχείου (Element)
  */ 
  int searchElement(List l, Element e) {
    int i, yes = 0;
    for(i = 0; i < l.length; i++) {
      if(l.data[i] == e) {
        yes = 1;
        break;
      }
    }
    return yes;
  }
  
  /*
   * Εκτυπώνει τα στοιχεία της λίστας
  */
  void printList(List l) {
    int i;
    for(i = 0; i < l.length; i++) {
      printf("%d\t", (int)l.data[i]);
    }
    printf("\n\n");
  }
  
  int main() {
    
    List list;
    Element e;
    Element *p;
    int position;
    
    create(&list); //Πρέπει να κληθεί στην αρχή
    
    int i=1;
    do
    {
   puts("1. Empty List");
   puts("2. Check if Empty");
      puts("3. Check if Full");
   puts("4. Add Element at End");
      puts("5. Add Element at Start");
      puts("6. Insert Element at");
      puts("7. Delete Last Element");
      puts("8. Search Element");
   puts("9. Print List");
   puts("0. Exit\n");
   scanf("%d", &i);
      
      //system("clear"); /*  UNIX  */
      system("cls"); /*  DOS  */    
     
   switch(i)
   {
        case 1: /* sets list.length=0 */
     create(&list); 
     break;
        case 2: /* checks if empty */
     if(isEmpty(list)) 
            puts("the list is Empty\n"); 
          else 
            puts("the list is NOT Empty\n"); 
     break;	
        case 3: /* checks if full */
     if(isFull(list))
            puts("the list is Full\n"); 
          else
            puts("the list is NOT Full\n");
     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(addLast(&list, e))
            puts("element added!\n");
          else
            puts("oops, the list is full\n");
     break;
        case 5:
     printf("give element to add: "); /* adds a new element at the start of the list or first if it's empty */
     scanf("%d", &e);
          if(addFirst(&list, e))
            puts("element added!\n");
          else
            puts("oops, the list is full\n");
     break;
        case 6:
     printf("give element to insert: "); /* adds a new element at the start of the list or first if it's empty */
     scanf("%d", &e);
          printf("give position to insert at: ");
          scanf("%d", &position);
          if(insertElementAt(&list, e, position))
            puts("element inserted!\n");
          else
            puts("oops, the list is full or position out of bounds\n");
     break;
        case 7: /* deletes last element from the list */
          p = deleteLast(&list);
     if(p == NULL) 
            puts("oops, the list is empty\n");
          else
            printf("element deleted: %d\n", (int)*p);
     break;	
        case 8:
     printf("give element to search for: ");
     scanf("%d", &e);			 
     if(searchElement(list, e))
            puts("element found!\n");
          else
            puts("oops, element NOT found\n");
     break;	
        case 9:
     printList(list); /* prints the list (all element values) */
     break;	
        case 0:
     i=0;
     break;	        
        default:
     break;			 			
   }
    }while(i!=0);
    
    getchar();
    return 0;
  }