Page 1 of 1

C "LINKED LISTS" STRUCTURE TUTORIAL PART 2 C "LINKED LISTS" STRUCTURE TUTORIAL PART 2 Rate Topic: -----

#1 Elcric  Icon User is offline

  • D.I.C Regular
  • member icon

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

Posted 07 May 2010 - 10:35 AM

C "LINKED LISTS" STRUCTURE TUTORIAL PART 2


CONTENTS
• I. INTRODUCTION
• II. VOCABULARY
• III. LINKED LISTS
• IV. “HEAD END”LINKED LIST
• V. EXAMPLE PROGRAM
• VI. REFERENCES

WHAT YOU WILL LEARN IN THIS TUTORIAL

1. You will learn the basic linked list vocabulary.

2. You will learn how to create a “head end” linked list.

• I. INTRODUCTION

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

C++ includes the entire C language; therefore, all C programs, with a few minor exceptions, are also C++ programs.

The C code shown in the tutorial were written using the Microsoft Visual C++ 2008 Express Edition Integrated Development Environment (IDE) and the “C99 subset.”

• II. VOCABULARY

1. What are C’s dynamic allocation functions?

A linked list is a dynamic structure that grows or shrinks based on the needs of the program. Therefore, a linked list uses the dynamic allocation function malloc() to obtain memory and the dynamic allocation function free() to free memory while the program is running.

2. What is a linked list?

Each record of a linked list contains a field with a link to the next record in the list.

3. What is a node?

The records of a linked list are called elements or nodes.

4. What is a list handle?

The first node of a list is its head, which is often called the address, pointer, or handle of the list because it provides entry to the whole list.

• III. LINKED LIST

Each record of a linked list contains data fields and a field with a link to the next record in the list. Each record of a linked list is called an element or node. The head of a list is its first node, which is often called the address, pointer, or handle of the list because it provides entry to the whole list.

When a structure is a member of another structure it is called a nested structure. The following code, from the example program, shows the nested structure holding the pointer link to the next node.

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



• IV. “HEAD END” LINKED LIST

A push function can be used to add nodes to the “head end” of a linked list; this inserts nodes at the beginning of the linked list. The order of records in a “head end” list, end up in the reverse order in which they are added.

The following program code, shows the push function for the “head end” linked list example.

//  push function for the “head end” linked list

Book *addBook(Book **pointerToBook, char *n, int o)  //  ** pointer to pointer to the head
{
	Book *grace;  //  create a temporary node 
	grace = malloc(sizeof(Book));  //  allocate space for node 

	grace->bookName  = n;
	grace->bookOrder = o;
	grace->nextBook  = *pointerToBook;  // pointer to the head

	*pointerToBook = grace;  // pointer to the head

	return *pointerToBook;  //  pointer to the head
}



The following example program code, shows how NULL is used to tell the program it has reached the last node in the linked list.

Book *Genesis = NULL;  //  last node in list is an empty linked list



The following example program code, shows how calls are made to the push function for the “head end” linked list.

addBook(&Genesis, "Genesis", 1);
addBook(&Genesis, "Exodus", 2);
addBook(&Genesis, "Leviticus", 3);
addBook(&Genesis, "Numbers", 4);
addBook(&Genesis, "Deuteronomy", 5);



The following example program code, shows how to print a linked list to the screen.

printf("  FIRST FIVE BOOKS OF THE BIBLE\n\n");

			while(Genesis)  //  while Genesis is not NULL
			{
				printf("  %d %s\n\n", Genesis->bookOrder, Genesis->bookName);
				Genesis = Genesis->nextBook;
			}



• V. EXAMPLE PROGRAM

//*******************************************
//  C LINKED LIST STRUCTURE TUTORIAL PART 2   
//*******************************************  
#include<conio.h>
#include<stdio.h>  
#include<stdlib.h>
#include<string.h>    
#include<windows.h>   

void AltEnter(void);
void DateTime(void);
void menu(void);
void ShowTime(void);

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

//  push function for the “head end” linked list

Book *addBook(Book **pointerToBook, char *n, int o)  //  ** pointer to pointer to the head
{
	Book *grace;  //  create a temporary node 
	grace = malloc(sizeof(Book));  //  allocate space for node 

	grace->bookName  = n;
	grace->bookOrder = o;
	grace->nextBook  = *pointerToBook;  // pointer to the head

	*pointerToBook = grace;  // pointer to the head

	return *pointerToBook;  //  pointer to the head
}

//**********************************

int main(int argc, char *argv[])
{
	ShowTime();
	DateTime();
	menu();
		   
	return 0;
}

//**********************************

void ShowTime(void)
{
	AltEnter();
	system("COLOR 1F");

	return;
}

void AltEnter(void)
{
    keybd_event(VK_MENU,
                0x38,
                0,
                0);
    keybd_event(VK_RETURN,
                0x1c,
                0,
                0);
    keybd_event(VK_RETURN,
                0x1c,
                KEYEVENTF_KEYUP,
                0);
    keybd_event(VK_MENU,
                0x38,
                KEYEVENTF_KEYUP,
                0);
    return;
}

void DateTime(void)
{
	printf("\n");
	printf("\n");
	printf("\n");
	printf("                              ");
	printf(__DATE__);
	printf("    ");
	printf(__TIME__);
	printf("\n");
	printf("\n");

	return;
}

void menu(void)
{
	system("CLS");  
	DateTime();
	printf("\n\n                     C LINKED LIST  STRUCTURE TUTORIAL  PART 2\n\n\n\n");
	
	printf("  0  EXIT\n\n");
	printf("  1  Execute the linked list example program.\n\n\n");
	printf("\n\n  Please type your menu selection; for example, 0 to EXIT.\n\n  ");

	char menuSelection;
	menuSelection = getch();

	switch(menuSelection)
	{
		case '0':
			break;

		case '1':
			system("CLS");  
			DateTime();
			printf("\n\n                     C LINKED LIST  STRUCTURE TUTORIAL  PART 2\n\n\n\n");

			Book *Genesis = NULL;  //  last node in list is empty linked list

			addBook(&Genesis, "Genesis", 1);
			addBook(&Genesis, "Exodus", 2);
			addBook(&Genesis, "Leviticus", 3);
			addBook(&Genesis, "Numbers", 4);
			addBook(&Genesis, "Deuteronomy", 5);

			printf("  FIRST FIVE BOOKS OF THE BIBLE\n\n");

			while(Genesis)  //  while Genesis is not NULL
			{
				printf("  %d %s\n\n", Genesis->bookOrder, Genesis->bookName);
				Genesis = Genesis->nextBook;
			}
 										
			printf("\n\n  Type any key to continue.\n\n  ");

			char screenOpen;
			screenOpen = getch();  //  keeps screen open until a key is pressed

			menu();     
			break;																								
	}
}



• VI. 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
  • +

Replies To: C "LINKED LISTS" STRUCTURE TUTORIAL PART 2

#2 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,788
  • Joined: 20-September 08

Posted 13 May 2010 - 11:49 PM

I liked your demo ...

You might like to see this possible 'part 3' ...

/***************************************
 C LINKED LIST STRUCTURE TUTORIAL PART 3
   this version not linked to a Win OS
 & demos a variation on using push_front
 ***************************************/ 
 
/* http://developers-heaven.net/forum/index.php/board,48.0.html */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HEADER \
    "C LINKED LIST STRUCTURE TUTORIAL PART 3\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:  "
		
char* GRACE[] = { "Genesis", "Exodus", "Leviticus", "Numbers", "Deuteronomy" };
const int SIZE_GRACE = sizeof GRACE / sizeof GRACE[0];

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

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

int menu(void);

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

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


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

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

    switch(menuSelection)
    {
        int i;
        case '0':
            return 0;
        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;
        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;

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

/* 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;
}

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' );
}

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 ... */
}


This post has been edited by JackOfAllTrades: 01 December 2010 - 09:57 AM

Was This Post Helpful? 1
  • +
  • -

#3 Elcric  Icon User is offline

  • D.I.C Regular
  • member icon

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

Posted 15 May 2010 - 10:00 AM

Hello David W,

WOW! Fantastic! I love it! Great job!

Was This Post Helpful? 0
  • +
  • -

#4 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,788
  • Joined: 20-September 08

Posted 15 May 2010 - 10:58 AM

View PostElcric, on 15 May 2010 - 11:00 AM, said:

Hello David W,

WOW! Fantastic! I love it! Great job!



Speaking of a great job ... have you see this ...


Grab your bags, ice-picks and harnesses and ropes ... for the climb and rappel of your life ... into Noah's ark .... at over 4000 meters ...

http://www.youtube.c...h?v=MwHK_JvGEgI

They found at least 7 different wooden rooms under snow and ice near each other on Mt Ararat above the 12,000 foot (4000 meter height ...)
Was This Post Helpful? 2
  • +
  • -

#5 Elcric  Icon User is offline

  • D.I.C Regular
  • member icon

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

Posted 17 May 2010 - 02:01 AM

Hello David W,

I always knew they would find it! Thanks for the link!

Was This Post Helpful? 1
  • +
  • -

#6 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,788
  • Joined: 20-September 08

Posted 17 May 2010 - 02:23 AM

View PostElcric, on 17 May 2010 - 03:01 AM, said:

Hello David W,

I always knew they would find it! Thanks for the link!


Do you have the same feeling that I do ... re. the significance of this event ... at this time of increasing distress on multiple fronts?

Recall the words ... "as it was in the days of Noah ... even so shall it be in the day of the son of man ..."

It's time to start looking up ... over all the depressing waves of troubles coming on the whole world right now ... We will soon be in new glorious bodies ... and greet our Saviour and all his saints ... (that great crowd of dear faithful witnesses that have gone on before) ... face to face.

Baruch HaShem!

Shalom shalom,

David Wayne Zavitz

This post has been edited by David W: 17 May 2010 - 02:33 AM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1