#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    10
    Rep Power
    0

    Doubt with this library, which is on the list!


    Guys, I'm studying linked lists, but I'm confused! This library, my teacher gave to us, but find themselves right, this list has fixed size yet! Now, if some of the benefits of using list is not fixed size! Another question that list is headless or not?
    I will be grateful for any help!

    Code:
    #include "stdio.h"
    #include "stdlib.h"
    
    #define SIZE_MAX 100
    
    typedef int TListPos;
    typedef int TListKey;
    
    struct TList {
             int size;
             TListKey keys[SIZE_MAX];
           };
    
    void createlist (TList *l);                     // Cria uma lista l vazia
    bool emptylist (TList l);                       // Retorna V se l estiver vazia; e F, caso contrario
    int listsize (TList l);                         // Retorna o tamanho da lista l
    TListPos getpos (int i, TList l);               // Retorna a posição do iº elemento da lista l. Se i for maior que o tamanho da lista, retorna a posicao final da lista.
    TListKey getkey (TListPos p, TList l);          // Retorna a chave da posição p
    bool final (TListPos p, TList l);               // Retorna V se p é o final da lista; e F, caso contrario
    TListPos first (TList l);                       // Retorna a posicao do primeiro elemento da lista
    TListPos last (TList l);                        // Retorna a posicao do ultimo elemento da lista. Se a lista estiver vazia, retorna a primeira posicao
    TListPos next (TListPos p, TList l);            // Retorna a posicao seguinte a p, na lista. Se p for final, retorna p
    int indexof (TListKey k, TList l);              // Retorna o indice da chave k na lista l. Se k não estiver em l, retorna 0
    void insert (TListKey k, TListPos p, TList *l); // Insere a chave k na posicao p da lista l
    void remove (TListPos p, TList *l);             // Remove o elemento da posicao p na lista l
    void printlist (TList l, char *s);              // Imprime os elementos da lista l, precedidos do texto em s
    void insert(TListKey k, TListPos p, TList *l);
    void sort(TList *l);
    void remove (TListPos p, TList *l);		// Remove o item na posiçao
    
    void createlist (TList *l) {
      (*l).size = 0;
    }
         
    bool emptylist (TList l) {
      return l.size == 0;
    }
    
    int listsize (TList l) {
      return l.size;
    }
        
    TListPos getpos (int i, TList l) {
      return (i >= 1) && (i <= l.size)? i - 1: l.size;
    }
    
    TListKey getkey (TListPos p, TList l) {
      return l.keys[p];
    }
    
    bool final (TListPos p, TList l) {
      return p == l.size;
    }
    
    TListPos first (TList l) {
      return 0;
    }
    
    TListPos last (TList l) {
      return emptylist(l)? 0: l.size - 1;
    }
    
    TListPos next (TListPos p, TList l) {
      return final(p , l)? p : p + 1;
    }
    
    int indexof (TListKey k, TList l) {        
      int i = 0;                                
      TListPos p;
      
      for ( p = first(l); !final(p, l); p = next(p, l) ) {
        i++;
        
        if ( getkey(p, l) == k)
          return i;
      }
      
      return 0;
    }
    
    void insert (TListKey k, TListPos p, TList *l) {
      if ((*l).size < SIZE_MAX) {    
        int i;
        
        for (i = (*l).size; i > p; i--)
          (*l).keys[i] = (*l).keys[i - 1];
        
        (*l).keys[p] = k;
        (*l).size++;
      }
    }
    
    void printlist (TList l, char *s) {
      printf("%s", s);
      
      if (emptylist(l))
        printf(" vazia!");
      else {
        TListPos p = first(l);
        
        while(!final(p, l)) {      
          printf(" %d", getkey(p, l));
          p = next(p, l);
        }
      }
      
      printf("\n");
    }
    
    void insertord (TListKey k, TList *l) {
      if (emptylist(*l))
        insert(k, first(*l), l);
      else {
        TListPos p = first(*l);
        
        while ((!final(p, *l)) && (getkey(p, *l) < k))
          p = next(p, *l);
          
        insert(k, p, l);
      }
    }
    
    void sort(TList *l) {
      TList tmp;
      TListKey k;
      
      createlist(&tmp);
      
      while (!emptylist(*l)) {
        k = getkey(first(*l), *l);
        remove(first(*l), l);
        insertord(k, &tmp);
      }          
      
      while (!emptylist(tmp)) {
        k = getkey(first(tmp), tmp);
        remove(first(tmp), &tmp);
        insert(k, next(last(*l), *l), l);  
      }    
    }
    
    void remove (TListPos p, TList *l) {
      int i;
      
      for (i = p; i < (*l).size - 1; i++)
        (*l).keys[i] = (*l).keys[i + 1];
      
      (*l).size--;
    }
    Last edited by tek6; September 29th, 2012 at 12:16 AM. Reason: Not translated into English.
  2. #2
  3. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,158
    Rep Power
    2222
    OK, even though you did not use code tags, you did at least try to keep your code's formatting. However, if we were to have to try to compile your code to see what's going on, those asterixes not allow that to work.

    Here is what you do:
    Type this: [code]{insert code here}[/code]
    Those things in the square brackets are called code tags. They keep the browser's HTML interpreter from removing the leading spaces and hence preserve your code's formatting. All you need to do is to highlight and copy your formatted code and highlight the "{insert code here}" and paste your code in its place.

    The primary language here is English. I hope that is not a problem for you. Portuguese?
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    10
    Rep Power
    0
    I'm from Brazil. I will not have any problems.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2012
    Posts
    156
    Rep Power
    34
    I copied your code to my editor, and as I "walked" through it to format it my way I found these issues:

    The proper way to include standard headers (and headers from a few libraries) is with angle brackets; quotes are used to include user-defined headers (and headers from a few other libraries).

    bool is not defined without including the header <stdbool.h>

    You have repeated declarations of a couple functions (not very important)

    The usual way to access elements of a struct through a pointer is using the -> token (pointer->member versus (*pointer).member).

    When I then compiled it, my compiler said: "error: unknown type name ‘TList’"; so I added a typedef to the code. Note that I think struct TList is perfectly readable, the typedef has ne beneficial use.
    Code:
    typedef struct TList Tlist;
    second compilation: my compiler (rightly) complains that "remove()" is already defined by <stdio.h>. The library function named remove() is used to delete files from the file system.
    After I renamed the code's remove() function to listremove() and updated all references, the third compilation terminated without errors or warnings.

    --------

    this list has fixed size yet! Now, if some of the benefits of using list is not fixed size!
    You're absolutely right.
    This implementation is not the proper way to write linked lists.
    You can give a bad note to your teacher :)
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2012
    Posts
    10
    Rep Power
    0

    Smile


    O.o
    Originally Posted by bdb
    You can give a bad note to your teacher :)
    Thank you! I asked this question because I was looking on the internet and saw this code:

    Code:
    struct cel {
        int  content;
        struct cel *next;
    };
    
    typedef struct cel cell;
    
    void insert (int x, cell *p)
    {
       cell *new;
       new = mallocc (sizeof (cell));
       new->content = x;
       new->next = p->next;
       p->next = next;
    }
    That is totally different of him. Thus my list, in theory, has no end! Unlike his list (teacher).

    Thanks!

IMN logo majestic logo threadwatch logo seochat tools logo