Showing posts with label typedef. Show all posts

Thursday, September 22, 2011

C SINGLE LINKED LIST

REVISED: Sunday, March 15, 2015

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

YOU WILL LEARN:
1. The C Single Linked List.
2. The C Pointers.
3. The C strut.

I. C SINGLE LINKED LIST INTRODUCTION

Welcome to the “C Single Linked List Tutorial.”

The C code shown in the tutorial was written using the Microsoft Visual C++ 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 C 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. A Data Member

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

B. A Link Member

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 SINGLE LINKED LIST PROGRAMMING CONCEPTS

A. Call By Value

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

B. Memory Address

A pointer is a memory address.

C. Always Initialize Pointers

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

D. Assignments

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

E. Pointer Variable

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

F. Multiple Indirection

“Pointers to pointers” is called multiple indirection.

G. Constants

A pointer is a constant.

H. Function Addresses

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

I. Passing Function Pointers

Function pointers can be passed as parameters in function calls.

J. Return Value of a Function

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

K. Declarations

Keep every declaration on its own line.

IV. ANALYSIS OF C SINGLE LINKED LIST 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. C SINGLE LINKED LIST EXAMPLE PROGRAM SOURCE CODE

//***********************************
//C Single Linked List Tutorial
//***********************************
#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 SINGLE LINKED LIST TUTORIAL\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\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. C SINGLE LINKED LIST 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).

YOU HAVE LEARNED:

1. The C Single Linked List.
2. The C Pointers.
3. The C strut.

Elcric Otto Circle

--> --> -->

How to Link to My Home Page

It will appear on your website as:
"Link to ELCRIC OTTO CIRCLE's Home Page"

C “LINKED LISTS” STRUCTURE PROGRAMMING CONCEPTS

REVISED: Sunday, March 15, 2015

CONTENT:
• I. C "LINKED LISTS" STRUCTURE PROGRAMMING CONCEPTS INTRODUCTION
• II. REVIEW OF C STRUT CONCEPTS
• III. REVIEW OF C "LINKED LIST" CONCEPTS
• IV. ANALYSIS OF C "LINKED LIST" EXAMPLE PROGRAM
• V. C "LINKED LIST" EXAMPLE PROGRAM SOURCE CODE
• VI. C "LINKED LISTS" STRUCTURE PROGRAMMING CONCEPTS REFERENCES

YOU WILL LEARN:
1. C Strut concepts.
2. C Linked list concepts.

I. C "LINKED LISTS" STRUCTURE PROGRAMMING CONCEPTS INTRODUCTION

Welcome to “C 'LINKED LISTS' STRUCTURE PROGRAMMING CONCEPTS.”

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

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

The reason for having the C structure linked list tutorials 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 C STRUT 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 C 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 C LINKED LIST EXAMPLE PROGRAM

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? And the answer is, “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. C LINKED LIST EXAMPLE PROGRAM SOURCE CODE

/***********************************
C "LINKED LIST"
STRUCTURE TUTORIAL ***********************************/
#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)
112
{
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 \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 \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. C "LINKED LISTS" STRUCTURE PROGRAMMING CONCEPTS 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).

YOU WILL LEARN:
1. C Strut concepts.
2. C Linked list concepts.

Elcric Otto Circle

-->

-->

-->

How to Link to My Home Page

It will appear on your website as:
"Link to ELCRIC OTTO CIRCLE's Home Page"