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.
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.
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.
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.
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.
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”.
“Pointer variable” means “variable of a pointer type”.
F. Multiple Indirection
“Pointers to pointers” is called 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.
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.
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.
A function pointer can be the return value of a function.
K. Declarations
Keep every declaration on its own line.
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.
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.
//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"
No comments:
Post a Comment