Page 1 of 1

C “LINKED LISTS” STRUCTURE TUTORIAL PART 3 C “LINKED LISTS” STRUCTURE TUTORIAL PART 3 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 14 May 2010 - 11:12 AM

C “LINKED LISTS”
STRUCTURE TUTORIAL PART 3


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

I. INTRODUCTION

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

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.”

A linked list is a chain of structures of the same type. Each link of the chain is a node with a member with a pointer to the next node in the chain and member[s] of different types containing relevant information. Therefore, pointers are a key to understanding and programming linked lists. If you have problems understanding linked lists, brush up on pointers.

II. REVIEW OF SINGLE LINKED LIST BASICS

The single linked list is one of the most common data structures used in C. It is called a single linked list because it only points to the next node, and not the next node and the previous node; etc. Each record of a single linked list is called an element or node. Each node in the single linked list is a struct and contains fields called members which contain data plus a pointer to the next node.

The information in a single linked list can only be accessed sequentially and not randomly. To read the hundredth node of a single linked list, you must first read each of the preceding 99 nodes.

A single linked list normally consists of a root node, allocated on the stack, and one or more nodes, allocated on the heap by calling malloc.

Each node has two parts:

A. The data member[s] containing the information you want stored in the single linked list.

B. The link member to the next node. Setting the link member to NULL indicates the end of the linked list.

III. REVIEW OF RELEVANT C PROGRAMMING CONCEPTS

A. C is a ''call by value'' language, which means a called function is only given a copy of its arguments, not their addresses.

B. A pointer is a memory address.

C. If a pointer is not initialized it will point to a random memory location; therefore, always initialize pointers.

D. An assignment to a pointer variable changes the address in the variable, not the value at that address.

E. “Pointer variable” means “variable of a pointer type”.

F. “Pointers to pointers” is called multiple indirection.

G. A pointer is a constant.

H. C functions have addresses; therefore, pointers can point to C functions.

I. Function pointers can be passed as parameters in function calls.

J. A function pointer can be the return value of a function.

K. Keep every declaration on its own line.

IV. ANALYSIS OF EXAMPLE PROGRAM

A. TYPEDEF

A typedef is used to define the compound variable type object named model as type node; for example:

//  typedef renames struct type model to node.
typedef struct model  //  model is the structure tag.
{
	int nodeOrder;           //  Sequential order of 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;



As shown above, the compound variable type object named node has the following three members:

struct node
• Int bookOrder
• char *bookName
• struct *nextNode

node is the model, the template used by the program to declare all structures needed by the single linked list program.

B. MENU SWITCH CASE 0

The program exits.

C. MENU SWITCH CASE 1

The program creates an empty single linked list structure named head of type node.

				//  Declares head a structure pointer to an empty single linked list structure of type node.
				node *head = NULL;



The compound variable type object named head has the following three members:

struct head
• Int bookOrder
• char *bookName
• struct *nextNode

At this point the program has an empty single linked list named head stored in memory.

D. *addNode() POINTER FUNCTION

1. *addNode() Function Pointer Function Call.

The program executes an addNode() function call.

//  Calls function addNode(), and passes arguments, including address of head, to function addNode().
				addNode(1, "Genesis", &head);



2. *addNode() Function

Notice that the arguments in the *addNode() function call are the same number, type, and sequence as their corresponding parameters in the *addNode function definition.

addNode() function call parameters
• int o
• char n
• struct pointerToNode

The *addNode function processes the function call:

//  ** pointer to pointer means the first pointer contains the address 
//  of the second pointer, which points to the struct variable
//  object name head, the start of the single linked list.
node *addNode(int o, char *n, node **pointerToNode)  
{



3. temp node Definition

In the example program, the struct temp is embedded inside of the function addNode(). The addNode function creates a new node named temp.

	//  Declares temp a structure pointer to type node.
	node *temp;



The addNode function creates the following single linked list structure named temp of type node.

struct temp
• int bookOrder
• char *bookName
• struct *nextNode

The struct temp is used as a struct to hold a new node while the addNode() function uses malloc to allocate the new node memory and a memory address. The addNode() function assigns the memory address to the struct compound variable type object named temp.

	// Declares and initializes the temp node by reserving a memory address for the new node.
	temp = malloc(sizeof(node));



The temp node is assigned a pointer to NULL.

	//  temp node, nextNode member, is assigned a pointer to NULL.
	temp->nextNode  = *pointerToNode; 

	temp->nodeOrder = o;
	temp->nodeName  = n;



The memory address of the new temp node is copied to the head node, nextNode member. Now the head node points to the new temp node and the new temp node, nextNode member, points to NULL.

	//  Assignes the memory address of the new temp node to the head node.
	*pointerToNode = temp;
	//  Now the head node points to the new temp node.
	//  And, the new temp node points to NULL.



Finally, the function addNode() returns the memory address pointed to by the head node. This provides any subsequent addNode() function calls with the new memory address for the head of the linked list.

//  Returns new pointer to head.
	return *pointerToNode;
	
}



E. REMAINING FUNCTION CALLS

The remaining function calls are processed in the same manner; however, instead of using NULL, use the new pointer to head:

				addNode(2, "Exodus", &head);
				addNode(3, "Leviticus", &head);
				addNode(4, "Numbers", &head);
				addNode(5, "Deuteronomy", &head);



V. EXAMPLE PROGRAM

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

//  Function prototypes.
void altEnter(void);
void dateTime(void);
void menu(void);
void showTime(void);

//  typedef renames struct type model to node.
//  model is the structure tag.
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;

//  ** pointer to pointer means the first pointer contains the address 
//  of the second pointer, which points to the struct compound variable 
//  type head, the start of the single linked list.
node *addNode(int o, char *n, node **pointerToNode)  
{
	//  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.
	temp = malloc(sizeof(node)); 

	//  The temp node, nextNode member, is assigned a pointer to NULL.
	temp->nextNode  = *pointerToNode; 

	temp->nodeOrder = o;
	temp->nodeName  = n;
	
	//  Assignes the memory address of the new temp node to the head node.
	*pointerToNode = temp;
	

	//  Now the head node points to the new temp node.
	//  And the new temp node points to NULL.
	
	//  Returns new pointer to head.
	return *pointerToNode;
}

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

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 3\n\n\n\n");
	
	printf("  0  EXIT\n\n");
	printf("  1  Screen print UNSORTED 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':
			{
				system("CLS");  
				dateTime();
				printf("\n\n                      C LINKED LIST STRUCTURE TUTORIAL PART 3\n\n\n\n");

printf("  THE SINGLE LINKED LIST STRUCTURE NAMED HEAD OF TYPE NODE IS SHOWN BELOW:\n\n\n\n");
				printf("  #                 NAME              POINTER\n\n");
				printf("  head->nodeOrder   head->nodeName    head->nextNode\n\n\n");

				//  Declares head a pointer to a structure of type node.
				node *head = NULL;    

				//  Calls function addNode(), and passes arguments, including
				//  address of head, to function addNode().
				addNode(1, "Genesis", &head);
				addNode(2, "Exodus", &head);
				addNode(3, "Leviticus", &head);
				addNode(4, "Numbers", &head);
				addNode(5, "Deuteronomy", &head);

				//  While head is not NULL.
				while(head)  
				{
					printf("  %-17d %-17s %-17p\n\n", head->nodeOrder, head->nodeName, head->nextNode);
					head = head->nextNode;
				}

				printf("\n\n  Type any key to continue.\n\n  ");

				//  Keeps screen open until a key is pressed.
				char screenOpen;
				screenOpen = getch();  
	 										
				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
  • +

Page 1 of 1