Page 1 of 1

C “LINKED LISTS” STRUCTURE TUTORIAL PART 4 C “LINKED LISTS” STRUCTURE TUTORIAL PART 4 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 03 June 2010 - 11:53 AM

C “LINKED LISTS” STRUCTURE TUTORIAL PART 4


CONTENTS
• I. INTRODUCTION
• II. REVIEW OF RELEVANT C PROGRAMMING CONCEPTS
• III. REVIEW OF RELEVANT LINKED LIST CONCEPTS
• IV. ANALYSIS OF NEW EXAMPLE PROGRAM FEATURES
• V. EXAMPLE PROGRAM
• VI. REFERENCES

I. INTRODUCTION

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

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 was written using the Microsoft Visual C++ 2008 Express Edition Integrated Development Environment (IDE) and the “C99 subset.”

The reason for having the tutorial broken down into several parts is to gradually introduce you to the concept of linked lists. Each part gradually builds on the previous part. This gradual approach should make it easier to grasp the concept of structures and linked lists.


II. REVIEW OF RELEVANT C PROGRAMMING CONCEPTS

A. Variables

A variable is an object; a named region of storage in memory.

An lvalue is an expression referring to an object. The lvalue is that which is permitted on the left side of the assignment “=” operator. The rvalue is that which is permitted on the right side of the assignment “=” operator. Rvalues cannot be used on the left side of the assignment “=” operator.

Lvalue is a memory address and rvalue is a value stored at a memory address.

An "lvalue" of a variable is the value representing its address, i.e. where it is stored in memory. The "rvalue" of a variable is the value stored in that variable, at that address.


B. Variable Address

Once a variable is declared, we can get its memory address by preceding its name with the unary “&” operator, as in &head.

C. Variable Value

We can "dereference" a pointer, i.e. refer to the value of that which it points to, by using the unary “*” operator as in *head.

D. Composite Types

C has no classes; however, you can use struct to create composite types. The main difference between a C++ class and a C structure is that a class can have both variables and functions; however, a structure can only have variables.

E. Accessing A Struct

When not using pointers, if a variable is defined to be of a struct type you can use the variable’s name followed by the dot operator followed by the member's name, as shown below.

head.nodeOrder, head.nodeName, head.nextNode;



When using pointers, if a variable is defined to be of a struct type, the individual values in the different fields, called members, can be selected by appending the name of the member to the name of the variable. The dereferencing operator “*” can be used and the dot access applied to the outcome. For example, for the variable "head" we can use the following identifiers to refer to each of the three members of head:

(*head).nodeOrder, (*head).nodeName, (*head).nextNode;



The same equivalent results can be achieved by using the indirect member access operator “->” as follows:

head->nodeOrder, head->nodeName, head->nextNode);



F. Nodes

Nodes do not have unique names and are not declared as unique variables.

When a variable name, defined to be of a struct type; i.e., “head” is used alone in a program, the variable name refers to an object, a complete node and all its members.

Nodes are declared by using the C functions sizeof() and malloc(). Use sizeof() to determine each nodes’ memory storage allocation, and then malloc() to allocate the storage. You must use a pointer when you use malloc() or the storage allocation space is lost.

sizeof() accepts a data type as an argument, and returns the amount of memory storage you require in bytes.

malloc() is a function that takes one argument and returns one value. The argument malloc() takes is the amount of memory storage you require in bytes. The return value from malloc() is a memory address for use in a pointer. As previously mentioned above, you must use a pointer when you use malloc() or the storage allocation space is lost.

malloc() returns a void pointer to the start of the allocated memory.


temp = malloc(sizeof(NODE));



G. Typedef

typedef assigns a new name to a specified data type. The rule for using typedef is that the new name for the data type is the name used in the definition of the data type. The example program uses upper case identifiers for typedef data types.

/*  model is the structure tag;
    and, model is also the structure type.
    typedef renames struct type model to NODE.  */
typedef struct model         
{
	int nodeOrder;           /*  Sequential order of a book in the bible.  */
	char *nodeName;          /*  Name of book in the bible.  */
	struct model *nextNode;  /*  Nested structure, recursive structure 	pointer, link to next node.  */
}NODE;



H. Linked List Versus Array

A linked list is an excellent replacement for an array if a program has frequent insertions and deletions of nodes and no random access requirements.

I. NULL Pointer

By definition a null pointer does not point anywhere.

III. REVIEW OF RELEVANT LINKED LIST CONCEPTS

A. Each Node

Each node in a linked list contains an object and, if applicable, a pointer to the next node. The head points to the next node; and the last node, referred to as the tail, points to null.

B. Adding New Nodes

In the example program, after the first pass through the program, to add a new node to the beginning of the linked list, all we have to do is point the new node to the previous head node. The new node becomes the head node.

IV. ANALYSIS OF NEW EXAMPLE PROGRAM FEATURES

A. Empty Linked List

When you run “switch 1” you will see a screen print of the temp nodes on the top half of the screen and the linked list nodes on the bottom half of the screen. The very bottom of the screen shows the “empty linked list”.

Why, you might ask, does the “empty linked list” show a memory address? We have not run malloc(), how can it have a memory address? Think back to “Structure Tutorial Part 1.” In that tutorial we said, “Memory is automatically allocated for all the members by the compiler when a structure variable is declared.” As shown below, when we declared “head” the compiler allocated the memory “&head” for us and assigned “head” NULL.


NODE *head = NULL;



At this point all we have is an empty structure which we are calling an empty linked list. In other words we have the “head” and the “tail” of our linked list because our linked list only has one node.

B. First Node

When we make the function call we pass “&head” to the function. The “&head” address contains the pointer NULL.

insertHeadEnd(1, "Genesis", &head);



The first node created by the function becomes both the head and the tail which replaces the empty linked list. We no longer have an empty linked list.

C. Subsequent Nodes

When the first node is created, the temp node, nextNode member, becomes the "head" and is assigned the value NULL. Subsequent calls to the insertHeadEnd function, result in the temp node, nextNode member, being assigned the value of the pointer to the previous head node. The newly added node becomes the head node.

V. EXAMPLE PROGRAM

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

/*  model is the structure tag;  
    and, model is also the structure type.
    typedef renames struct type model to NODE.  */
typedef struct model         
{
	int nodeOrder;           /*  Sequential order of a book in the bible.  */
	char *nodeName;          /*  Name of book in the bible.  */
	struct model *nextNode;  /*  Nested structure, recursive structure pointer, link to next node.  */
}NODE;

/********************************
 *  Function prototypes         *
 ********************************/
void altEnter(void);
void dateTime(void);
void keepsScreenOpen(void);
void menu(void);
void printLinkedList(NODE *head);
void screen(void);
void screenPrintTempHeading(void);
void screenPrintHeadHeading(void);
void showTime(void);
void switch1Heading(void);
void tutorialTitle(void);

/*  A pointer provides indirect access to the value of the variable whose
    address it stores.  ** pointer to pointer, means the value stored at
	the first pointer address, is a pointer which points to the
	value stored at the second pointer address, which is the struct
	compound variable head of type NODE, which is the start of the single
	linked list.  */
NODE *insertHeadEnd(int o, char *n, NODE **pointerToHead)  
{
	/* Declares temp a pointer to a structure of type NODE.  */
	NODE *temp;  

	/*  Declares and initializes the temp node by reserving a memory address
	    for the new node.  malloc() returns a pointer to the memory address.
        */
	temp = malloc(sizeof(NODE));
	if (temp == NULL)
	{
		printf("\n\n  ERROR!  Out of memory!");
		printf("  NODE memory not allocated,");
		printf(" malloc() returned NULL!\n\n");

		keepsScreenOpen();
									
		menu(); 
	}

	/*  When the first node is created, the temp node, nextNode member, 
	    becomes the "head" and is assigned the value NULL.
		Subsequent calls to the insertHeadEnd function result in
		the temp node, nextNode member, being assigned the value of
		the pointer to the previous head node.
		The newly added node becomes the head node.*/
	temp->nextNode  = *pointerToHead; 

	/*  The temp node, nodeOrder member, is assigned 
	    the value stored at the address of o.  */
	temp->nodeOrder = o;

	/*  The temp node, nodeName member, is assigned
	    the value stored at the address of n.  */
	temp->nodeName  = n;
	
	/*  temp has become the head of the linked list.
	    The pointer to the memory address of temp is assigned to
	    *pointerToHead, which will be returned to the next executable
		line of code beneath the function call where it can be
		used as the new &head.*/
	*pointerToHead = temp;

	printf("  %-2d %-15s %-15p %-10p %-10p %-10p\n\n", temp->nodeOrder,
	                                                   temp->nodeName,
	                                                   temp->nextNode,
	                                                   temp,
	                                                   &temp,
	                                                   *temp);

	keepsScreenOpen();

	/*  Returns the pointer to the new head node of the linked list.*/
	return *pointerToHead;
}

/**********************************/
int main(int argc, char *argv[])
{
	showTime();
	dateTime();
	menu();
		   
	return 0;
}

/************************************
 *  Function definitions            *
 ************************************/
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 4\n\n\n\n");
	
	printf("  0  EXIT\n\n");
	printf("  1  Screen prints output from linked list example program.\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':
			{
				tutorialTitle();
				switch1Heading();
				screenPrintTempHeading();

				/*  Declares head a pointer to a structure of type NODE;
				    and, initializes head to NULL.  */
				NODE *head = NULL;
				
				/*  Calls function insertHeadEnd(), and passes arguments;
				    including address of head, to function insertHeadEnd().  */
				insertHeadEnd(1, "Genesis", &head);
				insertHeadEnd(2, "Exodus", &head);
				insertHeadEnd(3, "Leviticus", &head);
				insertHeadEnd(4, "Numbers", &head);
				insertHeadEnd(5, "Deuteronomy", &head);

				screenPrintHeadHeading();

				printLinkedList(head);

				keepsScreenOpen();

				menu();
			}
			break;
	}
}

/************************************/
void tutorialTitle(void)
{
	system("CLS");  
	dateTime();
	printf("\n\n                      C LINKED LIST STRUCTURE TUTORIAL  PART 4\n\n\n\n");

	return;
}

/************************************/
void switch1Heading(void)
{
	printf("  NOTE:  WHEN CURSOR IS FLASHING, TYPE ANY KEY TO CONTINUE:\n\n\n\n");
					
	return;
}

/************************************/
void screenPrintTempHeading(void)
{
	printf("  temp->nodeOrder\n\n\n");
	printf("     temp->nodeName  temp->nextNode  temp       &temp      *temp\n\n\n");
	
	return;
}

/************************************/
void screenPrintHeadHeading(void)
{
	printf("\n  head->nodeOrder\n\n\n");
	printf("     head->nodeName  head->nextNode  head       &head      *head\n\n\n");
	
	return;
}

/************************************/
void printLinkedList(NODE *head)
{
	/*  While head is not NULL.  */
	while(head)  
	{
		printf("  %-2d %-15s %-15p %-10p %-10p %-10p\n\n", head->nodeOrder,
												     head->nodeName,
												     head->nextNode,
												     head,
												     &head,
													 *head);
		head = head->nextNode;
	}

	printf("\n  EMPTY LINKED LIST                  %-10p %-10p\n\n", head, &head);
	printf("\n\n  Type any key to continue.\n\n  ");

	return;
}

void keepsScreenOpen(void)
{
/*  Keeps screen open until a key is pressed.  */
	char screenOpen;
	screenOpen = getch();

	return;
}



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

Page 1 of 1