Thread: How to make a chain-structure

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    18

    How to make a chain-structure

    i have a structure:

    Code:
    struct Book
    
    {
    char pIBSN[21];
    char pAutor[21];
    char pTitle[21];
    int published;
    struct Book *pNext;   //pointer to next book
    }
    I allso have function where i can enter the books. Lets say there are 20 books. How do i make a chain-structure that displays the books in alphabethical order?

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Dammit, I was all set to get into the nitty-gritty of making steel into chain, but -- oh well!

    You want a linked list (probably double linked), and you can sort it, etc. Normally, something like this is handled NOT by sorting the list, but by sorting an index to the list. This works VERY well when you have 80,000 books in your library, but is unnecessary when you have less than 1,000.

    Google "double linked list in C" or check the forum's tutorial. No sense re-writing it all.

  3. #3
    Registered User
    Join Date
    Mar 2008
    Posts
    4
    That's a code for a double linked list.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    struct celula
    {
     int item;
     struct celula *proximo;
     struct celula *anterior;
    };
    
    
    typedef struct celula no;
    
    no *head, *tail;
    
    void *aloca();
    void insere_final(int x);
    void insere_inicio(int x);
    void excluir(int x);
    void exibe(void);
    
    void *aloca(void)
    {
           void *novo = (no *) malloc(sizeof(no));
           if(novo == NULL){ 
                  printf("Memory allocation failure") ;
                  exit(1);
           }
           return novo;
    }
    
    void insere_final(int x)
    {
     no *novo = aloca();
     novo->item = x;
     if(head == NULL) head = tail = novo;
     else{
          novo -> anterior = tail;
          tail -> proximo = novo;
          novo -> proximo = NULL;
          tail = novo;a
     }
    }
    
    void excluir(int x)
    {
         no *p = head;
         if(p == NULL) printf("Lista vazia");
         else{
              while(p->item != x){
                   p = p->proximo;
              }
              printf("Value%d sucessfully deleted \n", p->item);
         }
    }
    
    void exibe(void)
    {
     no *n = head;
     if(n == NULL){
                printf("Empty list");
     }
     while(n != NULL){
                   printf("Value: %d", n->item);
                   n = n->proximo;
     }
    }
    
    int main()
    {
        insere_final(1);
        insere_final(2);
        exibe();
    }
    
    In your case, your structure will be:
    struct Book
    {
    char pIBSN[21];
    char pAutor[21];
    char pTitle[21];
    int published;
    struct Book *pNext;   //pointer to next book
    struct Book *pPrev;   //pointer to previous book
    }
    It's important to note that my list inserts the elements just on the list's end. If you want, you can order that list with a simple quicksort algorithm for example.
    Hope i could help

  4. #4
    Registered User
    Join Date
    Feb 2008
    Posts
    18
    wow! i should had said that im a beginner at C programming and i was hoping kinda smaller, smpler code. For now its hard to understand all of this but i try...
    thank you!

  5. #5
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,058
    Quote Originally Posted by MalickT View Post
    wow! i should had said that im a beginner at C programming and i was hoping kinda smaller, smpler code. For now its hard to understand all of this but i try...
    thank you!
    Maybe this will be a little easier to understand....

    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    
    struct Book
    {
        char pIBSN[21];
        char pAuthor[21];
        char pTitle[21];
        int published;
        struct Book *pNext;   //pointer to next book
        struct Book *pPrior;   //pointer to previous book
    }BookEntry;
    
    struct Book *start, *last, *info;
    
    void StoreRecord( struct Book  *i,  /* new element */
                    struct Book  **start, /* first element */
                    struct Book  **last /* last element */
                    )
    {
        struct Book *old, *p;
        if(*last == NULL) /* first element in list */
        {
            i->pNext = NULL;
            i->pPrior = NULL;
            *last = i;
            *start = i;
            return;
        }
        p = *start; /* start at top of list */
        old = NULL;
        while(p)
        {
            if(stricmp(p->pAuthor, i->pAuthor) < 0) //Sort by Author
            {
                old = p;
                p = p->pNext;
            }
            else
            {
                if(p->pPrior)
                {
                    p->pPrior->pNext = i;
                    i->pNext = p;
                    i->pPrior = p->pPrior;
                    p->pPrior = i;
                    return;
                }
                i->pNext = p; /* new first element */
                i->pPrior = NULL;
                p->pPrior = i;
                *start = i;
                return;
            }
        }
        old->pNext = i;
        i->pNext = NULL;
        i->pPrior = old;
        *last = i;
    }
    
    int main(void)
    {
        start = last = info = NULL;
        if((info = (struct Book *) malloc(sizeof(BookEntry))) == NULL)
            return -1; // Out of memory
        strcpy(info->pAuthor,"Michner, James");
        strcpy(info->pTitle,"Gone With The Wind");
        strcpy(info->pIBSN,"978-3-16-148410-0");
        info->published = 1;
        StoreRecord(info, &start, &last);
        if((info = (struct Book *) malloc(sizeof(BookEntry))) == NULL)
            return -1; // Out of memory
        strcpy(info->pAuthor,"Patterson, David");
        strcpy(info->pTitle,"John Adams");
        strcpy(info->pIBSN,"158-7-96-151410-1");
        info->published = 0;
        StoreRecord(info, &start, &last);
        if((info = (struct Book *) malloc(sizeof(BookEntry))) == NULL)
            return -1; // Out of memory
        strcpy(info->pAuthor,"Dr. Seuss");
        strcpy(info->pTitle,"Horton Hears a Who");
        strcpy(info->pIBSN,"987-6-54-321098-7");
        info->published = 1;
        StoreRecord(info, &start, &last);
    
        printf("\nPrint in sorted author order from beginning to end\n\n");
        info = start;
        while(info) // Beginning to End
        {
            printf("%-20s %-20s %-20s %d\n",info->pAuthor, info->pTitle, info->pIBSN, info->published);
            info = info->pNext;
        }
        printf("\n\nPrint in sorted author order from end to beginning\n\n");   
        info = last;
        while(info) // End to Beginning
        {
            printf("%-20s %-20s %-20s %d\n",info->pAuthor, info->pTitle, info->pIBSN, info->published);
            info = info->pPrior;
        }
        return 0;
    }

  6. #6
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    I would suggest you do the following things:

    Create a data structure who will hold your "collection of books". This will make your code "easier to understand" and looks better. And for this collection of books, i suggest you write the following functions:

    Code:
    typedef struct _BooksCollection
    {
       struct Book *first;
    } BooksCollection;
    
    BooksCollection initBooksCollection();
    /*   Return an empty collection of books */
    
    BooksCollection addBooksToBooksCollection(BooksCollection bc, char author[],
                                              char title[], char ibsn[], int published);
    /*   Add a books to the collection */
    
    void displayBooksCollection(BooksCollection bc);
    /*  Display every books in a collection */
    Now, you only have to implement those functions. Try to implement them and then test. Your application will looks something like

    Code:
    ...
    
    int main()
    {
       BooksCollection bc;
    
       bc = initBooksCollection();
       bc = addBooksToBooksCollection(bc, "Rowling", "Harry Pother", "4353-535", 1);
       bc = addBooksToBooksCollection(bc, "Petzold", "Windows Programming", "1243-535", 1);
       displayBooksCollection(bc);
    
       return 0;
    }
    Of course, this isn't really complete, but for a beginner, it guess it could be a nice exercise. And if you want more information about linked list, well, just look on wikipedia or google or even the cprogramming FAQ might have something about this. Looks for singly-linked lists. This is as simple as it gets.
    I hate real numbers.

  7. #7
    Registered User
    Join Date
    Mar 2008
    Posts
    65
    How does struct work, and what doe it do? I'm new to c aswell, and need to learn things.
    Thanks
    -matt

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by mcotter222 View Post
    How does struct work, and what doe it do? I'm new to c aswell, and need to learn things.
    Thanks
    -matt
    struct keyword allows you to group together data that belongs together: say name, address, telephone number, and age, into one data structure.

    If your struct was id, then id.name, id.address, id.telephone, etc, would allow you to assign or retrieve data from the struct id you made.

    There's much more, but I don't want to thread-jack the OP, any further. Catch a few tutorials on the web (there are many good one's around), and then start a new thread with any questions you have.

  9. #9
    Registered User
    Join Date
    Feb 2008
    Posts
    18
    Ok, getting better but still hard little hard to understand. I simplifyed my code. Now I just have the structure:

    Code:
    struct Book
    
    {
    char pIBSN[21];
    char pAutor[21];
    char pTitle[21];
    int published;
    struct Book *pNext;   //pointer to next book
    }
    and i have collection of books (wich are actualy movies hehe...)

    Code:
    struct Book Collection[18]=
    {
           {"1-800-423-0563","Adam Drozdek","Data structures and algorihtms in C++",2001},
           {"1-56592-453-3","Kyle Loudon","Mastering algorithms with C",1999},
           {"1-4815-1623-42","Hal Hanzo","The Dharma Foundation",1958},
           {"2-454-3543-44","Michael Jackson","King Of Pop",1997},
           {"2-244-44-21","Robert Zemeckiz","Forrest Gump",1994},
           {"4-567-3-675","Steven Spielberg","Amistad",1997},
           {"3-45-44-535","Michel Bay","Transformers",2007},
           {"6-465-34565-33","Luc Besson","The Messenger - The Story Of Jon Of Arc", 1999},
           {"1-455-6463-33","James Cameron","Terminator 2: Judgement Day",1991},
           {"8-900-345-343","George Lucas","Star Wars: Episode III-Revenge Of The Sith",2005},
           {"1-800-34-334","Michel Mann","Collateral",2004},
           {"1-455-435-434","Terrence Malick","The Thin Red Line",1999},
           {"1-445-3554-33","James Cameron","Avtar",2009},
           {"1-800-566-346","Cameron Crow","Vanilla Sky",2001},
           {"1-455-345-4345","Steven Spielberg","A.I. - Articifial Intelligenc",2001},
           {"2-454-446-45","Stanley Kubick","Clockwork Orange",1972},
           {"3-456-3545-565","Quentin Tarantino","Pulp Fiction",1994},
           {"1-484-345-45","Oliver Stone","Natural Born Killers",1994}
    
    };
    Now it shuld be easier to do a linked-structure and sort them by name?

    My assignment demands that the function must be a protype of something like this:

    Code:
    struct Book **CreateStructure(struct Book *pCollection, int n=18);  // function i have to programm
    can someone explain why there must be two pointers in the beginning of the function? It would be easier for me to understand if i had an illustation picture of the structure i must create...

  10. #10
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,058
    can someone explain why there must be two pointers in the beginning of the function? It would be easier for me to understand if i had an illustation picture of the structure i must create...
    IMHO, I think your instructor wants to get you involved in some crazy pointer manipulation.

    But for starters, I modified your Book structure as follows:

    Code:
    struct Book
    {
    	char pIBSN[21];
    	char pAuthor[21];
    	char pTitle[58];    // Increase from 21 to 58 to avoid overlow condition
    	int published;
    	struct Book *pNext;   //pointer to next book
    }BookEntry;  // This is needed to malloc Book structure
    Your CreateeStructure should look like this..


    Code:
    struct Book **CreateStructure(struct Book *pCollection, int n)
    {
    	struct Book *NewBook ,**BookReturn = NULL;
    .
    .
    .               // Need additional code here
    .
    
    	BookReturn = &FirstBook;
    	return BookReturn;
    }

    Your main driver function should look like this..

    Code:
    int main(void)
    {
    	struct Book **myBooks = NULL;
    
    	myBooks = CreateStructure(Collection, 18);
                    // Here you will have to print the records in the list
    return 0;
    }
    The CreateStructure only needs about 18 more lines of code to be complete and main only needs two more lines of code to print the records.

  11. #11
    Registered User
    Join Date
    Feb 2008
    Posts
    18
    well thats the problem, i dont know what code to write. I understand that main functions calls CreateStructure functions, thats how i would have built it. But i still i dont understand why there must be two pointers and how do i make chain-structure in alphabethical order. (yes my instructor drives crazy with pointers).

  12. #12
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,058
    First of all you'll need two additional global variables

    Code:
    Book *FirstBook = NULL;  // first book
    Book *LastBook  = NULL;  // last book
    I hope the following description may be of some help...

    In CreateStruct you'll need a loop to iterate thru your Collection structure array. In this loop, you will first malloc a NewBook record. Then strcpy all the fields from your Collection structure into the fields of your NewBook structure fields. Set the next record pointer in NewBook to NULL since this is the end.

    If it is the first Collection record to be added to the linked list then Firstbook and LastBook should both point to NewBook. Otherwise, the LastBook next record pointer should point to NewBook and LastBook should point to Newbook.

    Keep in mind all of the above is done in a loop that iterates thru your Collections structure array.

  13. #13
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,058
    I have a tendency to write code as I'm following a thread to make sure I know what I'm talking about. This thread was no exception. So, since the OP lost interest, I'm posting one possible solution.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct Book
    {
        char pIBSN[21];
        char pAuthor[21];
        char pTitle[58];    // Increase from 21 to 58 to avoid overlow condition
        int published;
        struct Book *pNext;   //pointer to next book
    }BookEntry;  // This is needed to malloc structure
    
    Book *FirstBook = NULL;  // first book
    Book *LastBook  = NULL;  // last book
    
    struct Book Collection[18] =
    {
        {"1-800-423-0563","Adam Drozdek","Data structures and algorihtms in C++",2001},
        {"1-56592-453-3","Kyle Loudon","Mastering algorithms with C",1999},
        {"1-4815-1623-42","Hal Hanzo","The Dharma Foundation",1958},
        {"2-454-3543-44","Michael Jackson","King Of Pop",1997},
        {"2-244-44-21","Robert Zemeckiz","Forrest Gump",1994},
        {"4-567-3-675","Steven Spielberg","Amistad",1997},
        {"3-45-44-535","Michel Bay","Transformers",2007},
        {"6-465-34565-33","Luc Besson","The Messenger - The Story Of Jon Of Arc", 1999},
        {"1-455-6463-33","James Cameron","Terminator 2: Judgement Day",1991},
        {"8-900-345-343","George Lucas","Star Wars: Episode III-Revenge Of The Sith",2005},
        {"1-800-34-334","Michel Mann","Collateral",2004},
        {"1-455-435-434","Terrence Malick","The Thin Red Line",1999},
        {"1-445-3554-33","James Cameron","Avtar",2009},
        {"1-800-566-346","Cameron Crow","Vanilla Sky",2001},
        {"1-455-345-4345","Steven Spielberg","A.I. - Articifial Intelligenc",2001},
        {"2-454-446-45","Stanley Kubick","Clockwork Orange",1972},
        {"3-456-3545-565","Quentin Tarantino","Pulp Fiction",1994},
        {"1-484-345-45","Oliver Stone","Natural Born Killers",1994}
    
    };
    
    Book *BookBubbleSort( Book *BookList)
    {
        Book *Blist, *Btemp = BookList, *Bprevious, *Bprevious1 = BookList;
        int iIndex1, iIndex2, iTotalBooks = 0;
    
        //determine total number of books
        for (; Btemp->pNext; Btemp = Btemp->pNext)
            iTotalBooks++;
        for (iIndex1 = 0; iIndex1 < iTotalBooks-1; iIndex1++) 
        {
            for (iIndex2 = 0, Blist = BookList; 
                Blist && Blist->pNext && (iIndex2 <= iTotalBooks-1-iIndex1);
                iIndex2++)
            {
                if (!iIndex2)
                {
                    //we are at beginning, so treat start book as previous book
                    Bprevious = Blist;
                }
                //compare the two books
                if (strcmp(Blist->pNext->pIBSN, Blist->pIBSN) < 0) 
                {  
                    //swap the books
                    Btemp = (Blist->pNext ? Blist->pNext->pNext :0);
                    if (!iIndex2 && (Bprevious == BookList))
                    {
                        //we do not have any special "marker" books
                        //so change beginning of the book list to point 
                        //to the beginning alphabetical order
                        BookList = Blist->pNext;
                    }
                    Bprevious1 = Blist->pNext;
                    Bprevious->pNext = Blist->pNext;
                    Blist->pNext->pNext = Blist;
                    Blist->pNext = Btemp;
                    Bprevious = Bprevious1;
                }
                else
                {
                    Blist = Blist->pNext;
                    if(iIndex2)
                    {
                        //just keep track of previous book, 
                        //for swapping books this is required
                        Bprevious = Bprevious->pNext;
                    }
                }     
            } 
        }
        return BookList;
    }
    
    struct Book **CreateStructure(struct Book *pCollection, int n)
    {
        struct Book *NewBook ,**BookReturn = NULL;
        int iIndex;
    
        for(iIndex = 0; iIndex < n; iIndex++)
        {
            if((NewBook = (struct Book *) malloc(sizeof(BookEntry))) == NULL)
                return NULL; // Out of memory
            strcpy(NewBook->pIBSN, (*(pCollection+iIndex)).pIBSN);
            strcpy(NewBook->pAuthor,(*(pCollection+iIndex)).pAuthor);
            strcpy(NewBook->pTitle,(*(pCollection+iIndex)).pTitle);
            NewBook->published = (*(pCollection+iIndex)).published;
            NewBook->pNext = NULL;   // this is the end
            if (FirstBook == NULL) {
                FirstBook = NewBook;    // if this is the first node
                LastBook  = NewBook;    // it's both the FirstBook and LastBook.
            }
            else LastBook->pNext = NewBook; // prev end points to NewBook
            LastBook = NewBook;         // new end of list
        }
        BookReturn = &FirstBook;
        *BookReturn = BookBubbleSort(*BookReturn);
        return BookReturn;
    }
    
    int main(void)
    {
        struct Book **myBooks = NULL;
    
        myBooks = CreateStructure(Collection, 18);
        for (; FirstBook != NULL; FirstBook = (**myBooks).pNext) 
            printf("%s  %s  %s %d\n", (**myBooks).pIBSN, (**myBooks).pAuthor, (**myBooks).pTitle, (**myBooks).published);   
        return 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Establishing 'make clean' with GNU make
    By Jesdisciple in forum C Programming
    Replies: 9
    Last Post: 04-11-2009, 09:10 AM
  2. pthread question how would I init this data structure?
    By mr_coffee in forum C Programming
    Replies: 2
    Last Post: 02-23-2009, 12:42 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. chain of objects within pop framework help needed
    By Davey in forum C++ Programming
    Replies: 0
    Last Post: 04-15-2004, 10:01 AM
  5. Pointer to a structure
    By frenchfry164 in forum C Programming
    Replies: 5
    Last Post: 03-16-2002, 06:35 PM