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.
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:
The same equivalent results can be achieved by using the indirect member access operator “->” as follows:
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.
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).
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"
No comments:
Post a Comment