REVISED: Sunday, March 15, 2015
CONTENTS
• I. C "HEAD END" LINKED LIST INTRODUCTION
• II. C "HEAD END" LINKED LIST VOCABULARY
• III. C LINKED LISTS
• IV. C “HEAD END”LINKED LISTS
• V. C "HEAD END" LINKED LIST EXAMPLE PROGRAM SOURCE CODE
• VI. C "HEAD END" LINKED LIST REFERENCES
YOU WILL LEARN:
1. Linked list vocabulary.
2. How to create a “head end” linked list.
I. C "HEAD END" LINKED LIST INTRODUCTION
Welcome to the “C Head End Linked List Tutorial.”
The C code shown in this tutorial was written using the Microsoft Visual C++ Express Edition Integrated Development Environment (IDE) and the “C99 subset.”
II. C "HEAD END" LINKED LIST VOCABULARY
A. What are C’s dynamic allocation functions?
A linked list is a dynamic structure that grows or shrinks based on the needs of the program. Therefore, a linked list uses the dynamic allocation function malloc() to obtain memory and the dynamic allocation function free() to free memory while the program is running.
B. What is a linked list?
Each record of a linked list contains a field with a link to the next record in the list.
C. What is a node?
The records of a linked list are called elements or nodes.
D. What is a list handle?
The first node of a list is its head, which is often called the address, pointer, or handle of the list because it provides entry to the whole list.
III. C LINKED LISTS
Each record of a linked list contains data fields and a field with a link to the next record in the list. Each record of a linked list is called an element or node. The head of a list is its first node, which is often called the address, pointer, or handle of the list because it provides entry to the whole list.
When a structure is a member of another structure it is called a nested structure. The following code, from the example program, shows the nested structure holding the pointer link to the next node.
typedef struct Bible
{
char *bookName;
int bookOrder;
struct Bible *nextBook;
//the pointer link to the next node
}Book;
IV. C "HEAD END" LINKED LIST
A push function can be used to add nodes to the “head end” of a linked list; this inserts nodes at the beginning of the linked list. The order of records in a “head end” list, end up in the reverse order in which they are added.
The following program code, shows the push function for the “head end” linked list example.
//push function for
//the “head end” linked list
Book *addBook(Book **pointerToBook, char *n, int o)
//** pointer to pointer to the head
{
Book *grace;
//create a temporary node
grace = malloc(sizeof(Book));
//allocate space for node
grace->bookName = n;
grace->bookOrder = o;
grace->nextBook = *pointerToBook;
//pointer to the head
*pointerToBook = grace;
//pointer to the head
return *pointerToBook;
//pointer to the head
}
The following example program code, shows how NULL is used to tell the program it has reached the last node in the linked list.
Book *Genesis = NULL;
//last node in list is an empty linked list
The following example program code, shows how calls are made to the push function for the “head end” linked list.
addBook(&Genesis, "Genesis", 1);
addBook(&Genesis, "Exodus", 2);
addBook(&Genesis, "Leviticus", 3);
addBook(&Genesis, "Numbers", 4);
addBook(&Genesis, "Deuteronomy", 5);
The following example program code, shows how to print a linked list to the screen.
printf(" FIRST FIVE BOOKS OF THE BIBLE\n\n");
while(Genesis)
//while Genesis is not NULL
{
printf(" %d %s\n\n", Genesis->bookOrder, Genesis->bookName);
Genesis = Genesis->nextBook;
}
V. C "HEAD END" LINKED LIST EXAMPLE PROGRAM SOURCE CODE
//***********************************
//C "HEAD END" LINKED LIST
//***********************************
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<windows.h>
void AltEnter(void);
void DateTime(void);
void menu(void);
void ShowTime(void);
typedef struct Bible
{
char *bookName;
int bookOrder;
struct Bible *nextBook;
//the pointer link to the next node
}Book;
//push function for the
//“head end” linked list
Book *addBook(Book **pointerToBook, char *n, int o)
//** pointer to pointer to the head
{
Book *grace;
//create a temporary node
grace = malloc(sizeof(Book));
//allocate space for node
grace->bookName = n;
grace->bookOrder = o;
grace->nextBook = *pointerToBook;
//pointer to the head
*pointerToBook = grace;
//pointer to the head
return *pointerToBook;
//pointer to the head
}
//**********************************
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 HEAD END LINKED LIST TUTORIAL\n\n\n\n");
printf(" 0 EXIT\n\n");
printf(" 1 Execute the linked list example program.\n\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 HEAD END LINKED LIST TUTORIAL\n\n\n\n");
Book *Genesis = NULL;
//last node in list is empty linked list
addBook(&Genesis, "Genesis", 1);
addBook(&Genesis, "Exodus", 2);
addBook(&Genesis, "Leviticus", 3);
addBook(&Genesis, "Numbers", 4);
addBook(&Genesis, "Deuteronomy", 5);
printf(" FIRST FIVE BOOKS OF THE BIBLE\n\n");
while(Genesis)
//while Genesis is not NULL
{
printf(" %d %s\n\n", Genesis->bookOrder, Genesis->bookName);
Genesis = Genesis->nextBook;
}
printf("\n\n Type any key to continue.\n\n ");
char screenOpen;
screenOpen = getch();
//keeps screen open until a key is pressed
menu();
break;
}
}
VI. C "HEAD END" 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. Linked list vocabulary.
2. How to create a “head end” linked list.
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