Page 1 of 1

C LINKED LISTS STRUCTURE TUTORIAL PART 5 C LINKED LISTS STRUCTURE TUTORIAL PART 5 Rate Topic: -----

#1 Elcric  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 102
  • View blog
  • Posts: 453
  • Joined: 02-May 09

Posted 12 June 2010 - 08:11 AM

C LINKED LISTS STRUCTURE TUTORIAL PART 5


CONTENTS
• I. INTRODUCTION
• II. ACKNOWLEDGEMENTS
• III. ANALYSIS OF NEW EXAMPLE PROGRAM FEATURES
• IV. EXAMPLE PROGRAM
• V. REFERENCES

I. INTRODUCTION

Hello; nice to meet you. Welcome to the “C Linked Lists Structure Tutorial Part 5.”

II. ACKNOWLEDGEMENTS

The example program in this tutorial was provided by David Wayne Zavitz. Thank you David! David was kind enough to rewrite the original demo, which was shown in Part 2 of this tutorial series.

David, when you read this, if I am off base on the following analysis, please correct any mistakes I have made by posting your comments.

III. ANALYSIS OF NEW EXAMPLE PROGRAM FEATURES

The following analysis is provided for beginner C programmers. You experts out there probably do not need an analysis; however, most beginners do, so experts please bear with me. Those of you who are beginners, will need to acquire a very good pointers foundation upon which to build an understanding of C linked lists.

Also, all comments from experts and beginners are welcomed, please post your comments! And David, this is your demo, if I missed anything that you think is important, please help me out by posting your comments.

A. #define

The syntax for “#define” as used in the example program is as follows:

#define identifier\
token-string \
token-string \ 
token-string \ 
token-string \ 
token-string



The “\” is required to continue the “token-string” on a new line.

Using “#define” substitutes the “token-string” for all subsequent occurrences of the “identifier” in the program, as follows:

#define HEADER \
    "C LINKED LIST STRUCTURE TUTORIAL PART 5\n\n" \
    "  0  EXIT\n" \
    "  1  Execute the linked list example program, version 1\n" \
    "  2  Execute the linked list example program, version 2\n" \
    "  Enter your menu selection:  "



When the program executes:

    printf(HEADER);



The following is printed to the screen:


C LINKED LIST STRUCTURE TUTORIAL PART 5
0 EXIT
1 Execute the linked list example program, version 1
2 Execute the linked list example program, version 2
Enter your menu selection:


B. Array Pointer For Character Strings

A string in C is an array of characters, with the last character being a "\0". When double quotes are used, as is done in the following example, the nul character ("\0") escape sequence is automatically appended to the end of each string. For example “Genesis” becomes Genesis\0 because by definition a string in C must be nul terminated.

The main feature of a pointer is its two-part nature. For example, a pointer is a variable that contains the memory location address of another variable. And, that memory location address points to a value. The computer is always “thinking” of memory in terms of addresses and values at those addresses.

Given:

char* GRACE[] = { "Genesis", "Exodus", "Leviticus", "Numbers", "Deuteronomy" };



Each pointer in the array is initialized with the address of a string literal.

To point to an element of an array of elements, you need a pointer to the element type. To point to an element of an array of char *, you need a pointer to char *. In other words, you need a char **.

With an array of pointers of type char, each element can point to an independent string, and the lengths of each of the strings can be different.

C. const

In the following statement:

const int SIZE_GRACE = sizeof GRACE / sizeof GRACE[0];



The unary operator sizeof is used to calculate the sizes of data types. sizeof is always a compile-time calculation. The sizeof an array depends on both the size of the array, and the array data type.

When the sizeof operator is applied to an array name by itself, it yields the total number of bytes in that array. Therefore, the numerator, sizeof GRACE, yields the total number of bytes in the array GRACE.

The denominator, sizeof GRACE[0], yields the total number of bytes in the first element of the array GRACE.

Because each element of an array occupies the same amount of memory, the result or quotient, named SIZE_GRACE, is the number of elements in the array.

D. typedef

The following typedef renames the struct tag Bible to Book.

typedef struct Bible
{
    char* bookName;
    int bookOrder;
    struct Bible* nextBook;  /* the pointer link to the next node */
}Book;



E. Function Prototypes

When a function is called, information is passed to the function by means of arguments. These arguments must correspond with the parameters in the definition of the function.

A prototype declares the function name, its parameters, and its return type prior to the function's actual definition. Place one prototype for each function at the beginning of your program as shown in the example code. Using prototypes provides the compiler with information it needs to check that you are using a function correctly.

The example program uses the following four prototypes:

First:

void push_front(Book**, char*, int);



The function push_front does not return a value, as shown by the keyword void preceeding the function name. The function push_front has three parameters separated by commas and shown within the parenthesis following the function name; a pointer to a pointer of type Book, a pointer to a char, and a variable of type int.

Second:

void showAll(Book*);



The function showAll does not return a value, as shown by the keyword void preceeding the function name. The function showAll has one parameter, a pointer of type Book, shown within the parenthesis following the function name.

Third:

void freeAll(Book**);



The function freeAll does not return a value, as shown by the keyword void preceeding the function name. The function freeAll has one parameter shown within the parenthesis following the function name, a pointer to a pointer of type Book.

Fourth:

int menu(void);



The function menu returns a value of type int, as shown by the keyword int preceeding the function name. The function menu does not have any parameters shown within the parenthesis following the function name; therefore, the keyword void is shown where you would normally see the list of parameters.

F. main() Function

The following main() function loops by using the switch statement in the menu() function. When the menu() function returns a 0 to the main function, it is assigned to ok, which makes the while test false, and the do loop stops looping and the program exits. When the menu() function returns a 1 to the main function, it is assigned to ok, which makes the while test true, and the do loop loop again.

/**********************************/
int main(int argc, char* argv[])
{
    int ok;
    do
    {
        ok = menu();
    }while( ok );

    return 0;
}
/**********************************/



G. Function Definitions

As shown in the example program, a function call passes execution control from the calling function to the called function. The arguments, if there are any, are passed by value to the called function. Execution of a return statement in the called function returns control, and if appropriate a value, to the calling function.

The following describes the functions in the example program.

1. int menu(void)

The "nul" described in III B above, is not the same as a "NULL". A nul refers to a zero as defined by the escape sequence “\0”. A nul occupies one byte of memory. NULL is the name of the macro used to initialize null pointers. NULL is #defined in a header file in your C compiler, nul may not be #defined at all.

The following menu() function definition declares Genesis a pointer to type Book, and initializes the value at the address Genesis points to, to NULL.

int menu(void)
{
    Book* Genesis = NULL;  /* initial pointer value for first node in list */



The following statements declare grace a pointer to type Book. And, declare c of type char, and menuSelection of type char.

    Book* grace;
    char c, menuSelection;



The following statements print HEADER to the screen; keeps the screen open until the user presses a key; then flushes the standard input stream (stdin); and continues execution of the program.

    printf(HEADER);
    menuSelection = c = getchar();
    while( c != '\n' ) c = getchar(); /* flush stdin */



The following statements start a switch which uses menuSelection to determine which case to execute. For example, if the user selects 0, the first case is executed and 0 is returned to the main() function and assigned to ok; this makes the while test false and the program exits.

    switch(menuSelection)
    {
        int i;
        case '0':
            return 0;



The following statements are executed when the user enters 1. When the user enters 1, 1 is returned to the main function and assigned to ok, which makes the while test true, and the do loop loop again.

        case '1':
            for( i = 0; i < SIZE_GRACE; ++i )
                push_front(&Genesis, GRACE[i], i+1);
            
            showAll( Genesis ); /* Original Genesis not affected by showAll */
            freeAll( &Genesis ); /* Genesis set to NULL at end of freeALL ... */
            return 1;



The following statements are executed when the user enters 2. When the user enters 2, 1 is returned to the main() function and assigned to ok, which makes the while test true, and the do loop loop again.

        case '2':
            grace = NULL;
            push_front(&grace, GRACE[0], 1);
            Genesis = grace; /* Genesis is now filled with grace ... */

            for( i = 1; i < SIZE_GRACE; ++i )
            {   /* updates 'grace->nextBook' */
                push_front(&(grace->nextBook), GRACE[i], i+1); 
                grace = grace->nextBook; /* moving grace up ... */
            }

            showAll( Genesis );
            freeAll( &Genesis ); /* here Genesis is NULL (grace not defined ) */
            return 1;



The following statements are the default if the user enters something other than 0, 1, or 2. The error message is printed to the screen and 1 is returned to the main function and assigned to ok, which makes the while test true, and the do loop loop again.

        default:
            printf("\nNot a valid option ... try again.\n");
            return 1;
    }
}



2. void push_front(Book** ppBook, char* n, int o)

When called the following push_front function creates a temporary node:

/* Note pointer to a pointer ... i.e. ... */
/* passing in address of pointer to the head of the list so head is updated */
void push_front(Book** ppBook, char* n, int o)
{
    Book* grace;  /*  create a temporary node */
    grace = malloc(sizeof(Book));  /* allocate space for node  */
    if( grace == NULL)
    {
        fprintf( stderr, "Error: malloc failed to allocate memory." );
        exit(1);
    }

    grace->bookName  = n;
    grace->bookOrder = o;
    grace->nextBook  = *ppBook;

    *ppBook = grace;
}




3. void showAll(Book* startGrace)

When called, the following showAll function prints the first five books of the Bible to the screen:

void showAll(Book* startGrace)
{
    printf("\nFIRST FIVE BOOKS OF THE BIBLE\n");
    while( startGrace != NULL )
    {
        printf("  %d %s\n", startGrace->bookOrder, startGrace->bookName);
        startGrace = startGrace->nextBook;
    }
    putchar( '\n' );
}



4. void freeAll(Book** ppBook )

When called the following function calls the free() function to return memory to the heap.

void freeAll(Book** ppBook )
{
    Book *nxt, *cur = *ppBook; /* dereference start pointer */
    for( nxt = cur; cur != NULL; cur = nxt )
    {
        nxt = cur->nextBook; /* get next ...*/
        free( cur ); /* now can free current ... */
    }
    *ppBook = NULL; /* Ok ... set back to NULL, i.e. empty list ... */
}



IV. EXAMPLE PROGRAM

Please use the following link to the example program which is listed in the first comment from David in Part 2 of this tutorial series.

http://www.dreaminco...utorial-part-2/

V. REFERENCES

The C Programming Language by Brian Kernighan and Dennis Ritchie (Englewood Cliffs, N.J.: Prentice-Hall, 1978).

C++: The Complete Reference, Fourth Edition by Herbert Schildt (Berkeley, California: McGraw-Hill/Osborne, 2003).

Is This A Good Question/Topic? 1
  • +

Page 1 of 1