Part 2

Entries

October 3, 2011

I updated my linked list development, and committed it to the Subversion repository.
There is an

lab46:~/src/data$ svn commit -m "Updated linkedLinst1-jr.c to include delete node, append, ans insert. Thes functions need work as they do not handle the end  node or the  next to end node correctly -jr"
Sending    data/linkedList1-jr.c
Transmitting file data .
Committed revision 10.

October 6, 2011

After verifying my linked list library, I then added the linkedListLibrary directory and its files to the Subversion repository.

lab46:~/src/data$ svn add linkedListLibrary
A         linkedListLibrary
A         linkedListLibrary/linkedListLib.c
A         linkedListLibrary/linkedList-jr.c
A         linkedListLibrary/linkedListLib.h
A         linkedListLibrary/linkedListTest.c
A  (bin)  linkedListLibrary/linkedListTest
lab46:~/src/data$

After adding the linked list library files to the Subversion repository, I committed them as well.

lab46:~/src/data$ svn commit -m "linked list library, linkedListLib.a, contains the following functions: createList, destroyListHead, destroyListTail, listSizeHead, listSizeTail, printIntDataHead, insert, append, deleteNode, void loadListData, loadNode, createNode, copyList, findData, which have all been verified -John Rine"                                                                                                                                                          Sending        data/linkedList1-jr.c
Adding         data/linkedListLibrary
Adding         data/linkedListLibrary/linkedList-jr.c
Adding         data/linkedListLibrary/linkedListLib.c
Adding         data/linkedListLibrary/linkedListLib.h
Adding  (bin)  data/linkedListLibrary/linkedListTest
Adding         data/linkedListLibrary/linkedListTest.c
Transmitting file data ......
Committed revision 11.
lab46:~/src/data$

I am now finalizing my linked list project page which is at:
http://lab46.corning-cc.edu/user/jr018429/portfolio/libdll .

October 12, 2011

I learned to use a single .h file to prototye all of my functions and the node structure for all of my library files. Below is a record of the steps I went through to get there.
I successfully created and used a static linked list library, or so I thought, when I finalized my linked list project. However, when it came to implementing a static library of stack routines and associated data type, I had a horrible time. every library file wanted a node structure in it however when I linked the library files together, I got error messages! I had to figure out a way to have only one node struct reference that I could share with the library files. I appealed to the instructor for help!

Date: Wed, 12 Oct 2011 19:54:26 -0400 (EDT)
From: John Rine <jr018429@lab46.corning-cc.edu>
To: wedge@lab46.corning-cc.edu, haas@corning-cc.edu
Subject: static library HELP!!!!!

I am trying to finish my stack library and mange all the crap going on in my personal life and it ain't going very good.
I think I got lucky compiling and linking the linked List library.
I am having a time with the stack. I took a different approach with it.
I am having many library files with names describing the functions inside.
For example:
createFixedStack.c createFixedStack.h
listStackSize.c
listStackSize.h
destroyFixedStack.c
destroyFixedStack.h

I also have a test program named:
stackTest.c

please look closely at the #include "..." in the files, also look closely at the way I created the static library.
What am I doing wrong?????
I can't find any good examples on the Internet. My issues are compounded by having a struct. please look closely at how the struct is included in the includes.

I took copious notes. From you class, I got:
main
#include "mything.h"
how does "mything.h in the test program relate to multiple include files??
 I also got the following:
ar rcs libdll.a *.o
How does libdll relate to "mything.h" in the test program?
I am missing something!!!!

in stackTest.c I am declaring the individual .h files:
#include "createFixedStack.h"
#include "destroyFixedStack.h"
#include "listStackSize.h"

I successfully created .o files for these libraries using the following:
lab46:~/Stack$ gcc -c createFixedStack.c -o  createFixedStack.o
lab46:~/Stack$ gcc -c destroyFixedStack.c -o  destroyFixedStack.o
lab46:~/Stack$ gcc -c listStackSize.c -o  listStackSize.o

Then I can successfully create a static library using:
lab46:~/Stack$ ar rcs libStackJRdll.a *.o


Code and includes


//createFixedStack.h
//John T. Rine
//October 12, 2011

#ifndef _CREATEFIXEDSTACK_JR_H
#define _CREATEFIXEDSTACK_JR_H

#include<stdio.h>
#include<stdlib.h>

struct Node
{
       int data;
       struct Node * prev;
       struct Node * next;
};

typedef struct Node node;


void createFiixedStackList(node **, node **, int);

#endif


//createFixedStack.c
//John T. Rine
//October 12, 2011

#include<stdlib.h>
#include<stdio.h>
#include"createFixedStack.h"



void createFixedStack(node **head, node **tail, int elements)
{
       int i;
       node *new;
       new = NULL;
       *head = *tail = NULL;

       for(i = 1; i<=elements; i++)
       {
               if (*head == NULL)
               {
                       *head = (node *) malloc(sizeof(node));
                       *tail = *head;
                       (*head)->prev = NULL;
                       (*head)->next = NULL;
               }
               else
               {
                       new = (node *) malloc(sizeof(node));
                       new->prev = *tail;
                       new->next = NULL;
                       (*tail)->next = new;
                       *tail = new;
               }
       }
}




//destroyFixedStack.h
//John T. Rine
//October 12, 2011

#ifndef _DESTROYFIXEDSTACK_JR_H
#define _DESTROYFIXEDSTACK_JR_H

#include<stdio.h>
#include<stdlib.h>

struct Node
{
       int data;
       struct Node * prev;
       struct Node * next;
};

typedef struct Node node;


void destroyFixedStackHead(node *);
void destroyFixedStackTail(node *);

#endif



//destroyFixedStack.c
//John T. Rine
//October 12, 2011

#include<stdlib.h>
#include<stdio.h>
#include "destroyFixedStack.h"

void destroyFixedStackHead(node *head)
{
       node *temp;
       node *temp2;
       temp = NULL;
       temp2 = NULL;
       temp = head;
       while(temp != NULL)
       {
               temp2 = temp->next;
               if (temp->prev != NULL) temp->prev = NULL;
               if (temp->next != NULL) temp->next = NULL;
               free(temp);
               temp = temp2;
       }
}

void destroyFixedStackTail(node *tail)
{
       node *temp;
       node *temp2;
       temp = NULL;
       temp2 = NULL;
       temp = tail;
       while(temp != NULL)
       {
               temp2 = temp->prev;
               if (temp->prev != NULL) temp->prev = NULL;
               if (temp->next != NULL) temp->next = NULL;
               free(temp);
               temp = temp2;

       }
}



//listStackSize.h
//John T. Rine
//October 12, 2011

#ifndef _LISTSTACKSIZE_JR_H
#define _LISTSTACKSIZE_JR_H

#include<stdio.h>
#include<stdlib.h>

struct Node
{
       int data;
       struct Node * prev;
       struct Node * next;
};

typedef struct Node node;

int listStackSizeHead(node *);
int listStackSizeTail(node *);

#endif


//listrStackSize.c
//John T. Rine
//October 12, 2011


#include<stdlib.h>
#include<stdio.h>
#include"listStackSize.h"

int listStackSizeHead(node *head)
{
       int size = 0;
       while (head != NULL)
       {
               head = head->next;
               size++;
       }
       return size;
}

int listStackSizeTail(node *tail)
{
       int size = 0;
       while (tail != NULL)
       {
               tail = tail->prev;
               size++;
       }
       return size;
}



//stackTest.c
//Author: John T. Rine
//Date: October 12, 2011


#include "createFixedStack.h"
#include "destroyFixedStack.h"
#include "listStackSize.h"

int main(int argc, char **argv)
{

       node *head, *tail;
       head = tail = NULL;

       printf("Creating a list of 10 nodes...\n");
       createFixedStack(&head, &tail, 10);
       getchar(); //Holds the console window open on a Windows machine
}






However when I try to create the test executable, it bombs-HELP!!!

John T. Rine

Graduate Electrical Technology-Electronics
Graduate General Studies
---
 Lab46: Penguin Powered

October 13, 2011

I finally figured that I could create a struct .h file to define the node structure and then include that .h file in my lother library files. Sure enough, it worked!

Date: Thu, 13 Oct 2011 10:40:10 -0400
From: Matthew Haas <wedge@lab46.corning-cc.edu>
To: John Rine <jr018429@lab46.corning-cc.edu>
Subject: Re: static library HELP!!!!! (fwd)
On Oct 12, 2011, at 11:34 PM, John Rine wrote:

      I got it.
      The issue is that the structure used as a node is shared throughout all of the functions. When you break them up, you can't include the structure in
      every .h file, so what you do is to creat e a structure.h file and include that in the broken up files. Its seems you also need it in the test file as
      well. Man did that was driving me crazy.

</cli> My instructor pointed out, however, that I could have simply made one .h file for all of my library files! Why didn't I think of that?

Date: Thu, 13 Oct 2011 10:40:10 -0400
From: Matthew Haas <wedge@lab46.corning-cc.edu>
To: John Rine <jr018429@lab46.corning-cc.edu>
Subject: Re: static library HELP!!!!! (fwd)
Parts/Attachments:
   1   OK    ~61 lines  Text
   2 Shown   ~62 lines  Text
----------------------------------------

On Oct 12, 2011, at 11:34 PM, John Rine wrote:

      I got it.
      The issue is that the structure used as a node is shared throughout all of the functions. When you break them up, you can't include the structure in
      every .h file, so what you do is to creat e a structure.h file and include that in the broken up files. Its seems you also need it in the test file as
      well. Man did that was driving me crazy.

John,

 You may have appeared to resolve the issue, but I think the situation is still inordinately complex and can be simplified.

 For your stack library, you should be able to get away with just 1 header file, let's call it: stack.h

 stack.h can look as follows:

-------------------------------------
#ifndef _STACK_H
#define _STACK_H

#include "linkedlist.h"

struct stack {
struct list *data;
struct node *top;
};
typedef struct stack Stack;

Node *pop(Stack *);
int push(Stack *, Node *);
Node *peek(Stack *);
int isEmpty(Stack *);

#endif
-------------------------------------

All your .c files can just #include "stack.h", which will take care of all the function prototypes, struct definition, and even pull in the linked list stuff for
you (the linkedlist.h file will similarly have #ifndef _LINKED_LIST_H guards).

With so many header files, the way you seem to be approaching it might be creating a lot more managerial work for yourself... let the preprocessor take care of it
for you.

Is this code on Lab46? I took a quick peek and couldn't find it.

-Matthew
--
Matthew Haas
Lab46 System Administrator
Instructor of Computer & Information Science
http://lab46.corning-cc.edu/haas/home/ [lab46.corning-cc.edu]

October 14, 2011

I finally finished my doubly linked stack library project :) !!! It is available at:
http://lab46.corning-cc.edu/user/jr018429/portfolio/stack
I learned about implementing stacks using doubly linked structure node structures. I also learned how to use a single .h file for all library function prototypes and the library node structure definition. I also learned that another more complicated way of implementing the library would be to create a strucure .h file which defines the node structure and then including that in the other library files, assuming one is using a .h file per library .c file. Yet another way might be to include the node structure definition in each .h file but wrap it in a #ifndef, #define, #endif block as follows:

#ifndef _NODESTRUCT_H
#define _NODESTRUCT_H
struct Node
{
        int data;
        node *next;
        node *prev;
}
#endif

October 19, 2011

State machines are ubiquitous in programming and in hardware design-synchronous digital logic design. I found a very good tutorial on statemachine design at: http://johnsantic.com/comp/state.html . I shared this link and what I know about state-machines with my Data Structures and Systems Programming classes.

Date: Wed, 19 Oct 2011 23:06:46 -0400 (EDT)
From: John Rine <jr018429@lab46.corning-cc.edu>
To: data@lab46.corning-cc.edu, sys@lab46.corning-cc.edu
Subject: State Machines in Programming

Check out this link on state machines:
http://johnsantic.com/comp/state.html

State machines are a very import concept in both hardware and software design.
Stae machines  are either, in the case of hardware, clock driven or in software, loop, or interrupt driven. State machines store their last state and then compare
this last state to input and if defined in their design, will change state when triggered by a clock, loop, or interrupt.
State machines implemented in software can be used to perform hardware control, for example machine tool and robotics software. Soft state machines can be used in
game design such that game flow changes based on the game's previous state and input from the player. One way to implement state machines in software by combining
loop and  selecttion structures.

In hardware they are implemented using a register (flip-flops) and decoding logic. Why even discuss a hardware implement here? Well as we learned last sememmster in
Computer Organizations, hardware can be simulated in software! The decoding logic of a hardware defined state machine decodes the outputs of the state register
(output and state storage) and input and caauses the state register's state to change when the output state and inputs change to some value defined by the design.
Even though a synchronous counter is not considered to be a state machine, it may be helpful as an analogy to understanding them. A synchronous counter is reset
when firat powered up. The decoding circuitry sees 0 on the out put of the counter and decodes this value to be 1 on the input. On the next clock pulse, the counter
changes to 1 on its output. now the decoding circuitry sees 1 on the output and decodes this to 2 on the input. When the next clock tick occurs, the output changes
to 3 and so on... To get to a state machine from a synchronous counter, simply add inouts from the outside to the ddecoding circuitry. Now consider a hardware state
machine, on power up the state machine's outputs are set to 0. Now if a sensor on an input changes state, when the next clock pulse occurs and if the decoding
circuitry is designed to do so, a state machine output will change in response to the sensor's input. This output will maintain its state until the decoding logic
coupled with certain input states associate with the decoding design and a clock pulse causes it to change.
There are two types of hardware state machines:
1. Moore, and
2. Meally
At least one author has described the cpu as a state machine.
I am sure I have made the subject of state machines as clear as mud.

John T. Rine

Graduate Electrical Technology-Electronics
Graduate General Studies
---
 Lab46: Penguin Powered

October 23, 2011

I added and committed my forkExample.c program to the Subversion repository.

lab46:~/src/sysprog$ svn add forkExample.c
A         forkExample.c
lab46:~/src/sysprog$ svn commit -m "Added and commited a simple example of using fork -John Rine"
Adding         sysprog/forkExample.c
Transmitting file data .
Committed revision 16.

I added and committed my useMalloc.c program to the Subversion repository.

lab46:~/src/data$ svn add useMalloc.c
A         useMalloc.c
lab46:~/src/data$ svn commit -m "Added and committed useMalloc.c, an example program demonstrating dynamic memory allocation of structures and arrays -John Rine"
Sending        data/Stack/libdll.a
Adding         data/useMalloc.c
Transmitting file data ..
Committed revision 17.
lab46:~/src/data$

October 24, 2011

I conducted and documented an experiment to determine if a string literal could be assigned to a pointer pointing to dynamically allocated memory and then be used in a program, then when the data is no longer needed, deallocate it. The experiment is documented in Part II, experiment 1.

October 28, 2011

I added and committed the code I wrote to implement an array-based stack data structure.

lab46:~/src/data$ svn add arrayStack.c
A         arrayStack.c
lab46:~/src/data$ svn commit -m "Added and committed an array-based stack program. -John Rine"
Adding         data/arrayStack.c
Sending        data/useMalloc.c
Transmitting file data ..
Committed revision 18.
lab46:~/src/data$

I added and committed the code I wrote to design and test doubly-linked list functions.

lab46:~/src/data$ svn add linkedListDev.c
A         linkedListDev.c
lab46:~/src/data$ svn commit -m "Added and committed linkedListDev.c, a linked list development program -John Rine"
Adding         data/linkedListDev.c
Transmitting file data .
Committed revision 19.
lab46:~/src/data$

October 29, 2011

I added and committed the code I wrote to learn about threads.

lab46:~/src/sysprog$ svn add threadTest.c
A         threadTest.c
lab46:~/src/sysprog$ svn commit -m "Added and committed threadTest.c a program to illustrate thread creation and termination -John Rine"
Sending        sysprog/interface.c
Adding         sysprog/threadTest.c
Transmitting file data ..
Committed revision 20.
lab46:~/src/sysprog$

I added and committed the code I wrote to implement an array-based queue.

lab46:~/src/data$ svn add queueTest.c
A         queueTest.c
lab46:~/src/data$ svn commit -m "Added and committed an array-based example of a queue -John T. Rine"
Adding         data/queueTest.c
Transmitting file data .
Committed revision 21.
lab46:~/src/data$

October 30, 2011

I entered my part deux (II) course objectives for systems programming and data structures courses. I also completed my third experiment for part II. I also wrote system programming topic information for the synchronization methods mutex, and barrier.

data Topics

malloc

malloc is a c library function for dynamically allocating memory in the “heap”. dynamically allocated memory is memory that has been set aside for use during the execution of the program, also know as “run time”. malloc can be used to dynamically allocate variables as well as arrays, including multidimensional arrays and structures. The malloc function becomes available for use in a program after the stdlib.h header has been added to the program.

useMalloc.c

//useMalloc.c
//John T. Rine
//October 23, 2011
 
#include<stdlib.h>
#include<stdio.h>
 
 
struct Test
{
        char *message1;
        char *message2;
};
 
typedef struct Test test;
 
int main(int argc, char **argv)
{
 
        //malloc a struct
        test *testPTR;
 
        testPTR = (test *)malloc(sizeof(test));
 
        testPTR->message1 = "Hello ";
        testPTR->message2 = "world!";
 
        printf("Message1 = %s, message2 = %s\n", testPTR->message1, testPTR->message2);
 
        free(testPTR);
 
 
        //malloc a char array
        int i = 0;
        int ii = 0;
        char * inputString = "John T. Rine\0";
        char * string = NULL;
 
        printf("input string contains %s\n", inputString);
        while(*(inputString + i) != '\0') i++;
        printf("Character count = %d\n", i);
        string = (char *)malloc(sizeof(char) * (i + 1));
        for(ii = 0; ii <= (i + 1); ii++) *(string + ii) = *(inputString + ii);
        printf("Dynamically allocated array contains %s\n", string);
 
        free(string);
 
        return 0;
}

Compilation and execution of useMalloc.c were successful as seen below.

lab46:~/src/data$ ./useMalloc
Message1 = Hello , message2 = world!
input string contains John T. Rine
Character count = 12
Dynamically allocated array contains John T. Rine
lab46:~/src/data$

References

Heap

Since the data structures class is now making copious use of dynamically allocated memory using malloc and free to allocate and deallocate memory to make, manage, and destroy linked lists, stacks, quesues and so on, wouldn't it be a good idea to understand what the heap is, and how its used?
Dynamically allocated memory is usually allocated from a pool of unused memory known as the “heap” or “free store”. Because the exact memory address of a dynamic memory allocation is not known in advance, dynamically allocated memory is accessed indirectly through the use of pointers. The exact method used to organize the heap and allocate and deallocate parts of it is hidden behind an abstract interface.

References

Stack

The stack is a last in, first out (LIFO) data structure. A stack can have any data type, including structures as elements, but has only a few basic operations which can be performed on it: initialize or create, push, pop and peek. The initialize or create operation creates a stack and initializes it. The push operation adds a new item to the top of the stack. The pop operation removes an item from the top of the stack. The stack peek operation gets the data from the top of the stack without deleting it or changing the stack pointer.

arrayStack.c

//arrayStack.c
//John T. Rine
//October 28, 2011
 
#include<stdio.h>
#include<stdlib.h>
 
struct Stack 
{
  char *array;
  int top;
  int size;
};
 
typedef struct Stack stack;
 
int cntChars(char *);
void createStack(stack *, int);
void push(stack *, char);
char pop(stack *);
int isEmpty(stack *);
int isFull(stack *);
 
int main(int argc, char **argv)
{
	int i;
	int count;
	stack newStack;
	char stringArray[200];
 
	printf("Enter a string: ");
	gets(stringArray); 
	count = cntChars(stringArray); 
	createStack(&newStack, count); 
	if(isEmpty(&newStack)) printf("Stack is empty\n");
	else printf("Stack is not empty\n");
	for(i = 0; i < count; i++)
	{
		push(&newStack,stringArray[i]);
                printf("The character going into tos is: %c\n", newStack.array[i]);
	}
        if(isEmpty(&newStack)) printf("Stack is empty\n");
        else printf("Stack is not empty\n");
	for(i = 0; i < count; i++) printf("The character in tos is: %c\n", pop(&newStack));
        for(i = 0; i < count; i++)
        {
                push(&newStack,stringArray[i]);
                printf("The character going into tos is: %c\n", newStack.array[i]);
        }
	push(&newStack,'H');
 
	return 0;
}
 
int cntChars(char *inputString)
{
	// returned value "count" does not include '\0'
	int count = 0;
	while(*(inputString + count) != '\0') ++count;
	return(count);
}
 
void createStack(stack *stackVar, int size)
{
	char *array;
 
	array = (char *)malloc(sizeof(char) * size);
 
  	if (array == NULL)
	{
    		fprintf(stderr, "Not enough memory to create the stack.\n");
    		exit(1);
  	}
 
	stackVar->array = array;
  	stackVar->size = size;
  	stackVar->top = -1;
 
}
 
int isEmpty(stack *stackVar)
{
  return stackVar->top < 0;
}
 
int isFull(stack *stackVar)
{
  return stackVar->top >= stackVar->size - 1;
}
 
void push(stack *stackVar, char  element)
{
	if (isFull(stackVar))
	{
		fprintf(stderr, "Can't push on the stack is full\n");
		exit(1);
	}
	stackVar->array[++stackVar->top] = element;
}
 
 
char pop(stack *stackVar)
{
	if (isEmpty(stackVar))
	{
		fprintf(stderr, "Can't pop from stack; stack is empty\n");
		exit(1);
	}
	return stackVar->array[stackVar->top--];
}

Execution of the source code listed above with the string “Oh no! I have just been Rick rolled!” as input.

lab46:~/src/data$ gcc arrayStack.c -o arrayStack
/tmp/cczFb9N2.o: In function `main':
arrayStack.c:(.text+0x35): warning: the `gets' function is dangerous and should not be used.
lab46:~/src/data$ ./arrayStack
Enter a string: Oh no! I have just been Rick rolled!
Stack is empty
The character going into tos is: O
The character going into tos is: h
The character going into tos is:
The character going into tos is: n
The character going into tos is: o
The character going into tos is: !
The character going into tos is:
The character going into tos is: I
The character going into tos is:
The character going into tos is: h
The character going into tos is: a
The character going into tos is: v
The character going into tos is: e
The character going into tos is:
The character going into tos is: j
The character going into tos is: u
The character going into tos is: s
The character going into tos is: t
The character going into tos is:
The character going into tos is: b
The character going into tos is: e
The character going into tos is: e
The character going into tos is: n
The character going into tos is:
The character going into tos is: R
The character going into tos is: i
The character going into tos is: c
The character going into tos is: k
The character going into tos is:
The character going into tos is: r
The character going into tos is: o
The character going into tos is: l
The character going into tos is: l
The character going into tos is: e
The character going into tos is: d
The character going into tos is: !
Stack is not empty
The character in tos is: !
The character in tos is: d
The character in tos is: e
The character in tos is: l
The character in tos is: l
The character in tos is: o
The character in tos is: r
The character in tos is:
The character in tos is: k
The character in tos is: c
The character in tos is: i
The character in tos is: R
The character in tos is:
The character in tos is: n
The character in tos is: e
The character in tos is: e
The character in tos is: b
The character in tos is:
The character in tos is: t
The character in tos is: s
The character in tos is: u
The character in tos is: j
The character in tos is:
The character in tos is: e
The character in tos is: v
The character in tos is: a
The character in tos is: h
The character in tos is:
The character in tos is: I
The character in tos is:
The character in tos is: !
The character in tos is: o
The character in tos is: n
The character in tos is:
The character in tos is: h
The character in tos is: O
The character going into tos is: O
The character going into tos is: h
The character going into tos is:
The character going into tos is: n
The character going into tos is: o
The character going into tos is: !
The character going into tos is:
The character going into tos is: I
The character going into tos is:
The character going into tos is: h
The character going into tos is: a
The character going into tos is: v
The character going into tos is: e
The character going into tos is:
The character going into tos is: j
The character going into tos is: u
The character going into tos is: s
The character going into tos is: t
The character going into tos is:
The character going into tos is: b
The character going into tos is: e
The character going into tos is: e
The character going into tos is: n
The character going into tos is:
The character going into tos is: R
The character going into tos is: i
The character going into tos is: c
The character going into tos is: k
The character going into tos is:
The character going into tos is: r
The character going into tos is: o
The character going into tos is: l
The character going into tos is: l
The character going into tos is: e
The character going into tos is: d
The character going into tos is: !
Can't push on the stack is full
lab46:~/src/data$

References

http://www.cs.bu.edu/teaching/c/stack/array/
<html><a href=“http://en.wikipedia.org/wiki/Stack_(abstract_data_type)”>http://en.wikipedia.org/wiki/Stack_(abstract_data_type)</a></html>

Linked List

A linked list is a data structure whose elements each contain pointers to other elements in the linked list. There are singly-linked lists whose pointers only point in one direction, and doubly-linked lists which has pointers pointing in the direction of head and pointers which point in the direction of the tail. The list is traversed using the pointers contained in the node.
For example, a list can be traversed from the head using the “next” pointer as follows:

temp = head;
while(temp != NULL)                //while temp is not at the end of the list
{
	printf("%d ",temp->data); //printf the value of the data in the current node
	temp = temp->next;        //load temp with the address of the next node
}

linkedListDev.c

//linkedListDev.c
//John T. Rine
//October 28, 2011
 
 
#include<stdio.h>
#include<stdlib.h>
 
struct Node
{
	int data;
	struct Node * prev;
	struct Node * next;
};
 
typedef struct Node node;
 
void createList(node **, node **, int);
void destroyListHead(node *);
void destroyListTail(node *);
int listSizeHead(node *);
int listSizeTail(node *);
void printIntDataHead(node *);
void insert(node **, node **, int, int);
void append(node **, node **, int, int);
void deleteNode(node **, node **, int);
void loadListData(node *);
void loadNode(node *, int, int);
void createNode(node*, node*);
void copyList(node *, node **, node **);
int findData(node *, int);
 
int main(int argc, char **argv)
{
 
	node *head, *tail, *copyHead, *copyTail, *temp;
	head = tail = copyHead = copyTail = NULL;
 
	int i = 1;
 
	printf("Creating a list of 4 nodes...\n");
	createList(&head, &tail, 4);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printf("Load list data\n");
	loadListData(head);
	printIntDataHead(head);
	printf("Inserting node 0 with data of 3200 before head node...\n");
	insert(&head, &tail, 0, 3200);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	printf("Inserting node with data of -3200 before tail node...\n");
	insert(&head, &tail, listSizeHead(head) - 1, -3200);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	printf("Appending node with data of 2300 after head node...\n");
	append(&head, &tail, 0, 2300);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	printf("Appending node with data of -2300 after tail node...\n");
	append(&head, &tail, listSizeHead(head) - 1, -2300);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	printf("Loading node 0 with data of 0...\n");
	loadNode(head, 0, 0);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	printf("Loading tail node with data of 255...\n");
	loadNode(head, listSizeHead(head) - 1, 255);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	printf("Deleting head node...\n");
	deleteNode(&head, &tail, 0);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	printf("Deleting tail node...\n");
	deleteNode(&head, &tail, listSizeHead(head) - 1);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	printf("Deleting node 2...\n");
	deleteNode(&head, &tail, 2);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	copyList(head, &copyHead, &copyTail);
	printf("Size of the list is: %d\n", listSizeHead(copyHead));
	printIntDataHead(copyHead);
	printf("The node location of 3 is %d\n", findData(copyHead, 3));
 
	destroyListHead(head);
	return 0;
}
 
void createList(node **headd, node **taill, int elements)
{
	int i;
	node *new, *head, *tail;
	new = head  = tail = NULL;
 
	for(i = 1; i<=elements; i++)
	{
		if (head == NULL)
		{
			head = (node *) malloc(sizeof(node));
			tail = head;
			head->prev = NULL;
			head->next = NULL;
		}
		else
		{
			new = (node *) malloc(sizeof(node));
			new->prev = tail;
			new->next = NULL;
			tail->next = new;
			tail = new;
		}
	}
	*headd = head;
	*taill = tail;
}
 
void destroyListHead(node *head)
{
	node *temp;
	node *temp2;
	temp = NULL;
	temp2 = NULL;
	temp = head;
	while(temp != NULL)
	{
		temp2 = temp->next;
		if (temp->prev != NULL) temp->prev = NULL;
		if (temp->next != NULL) temp->next = NULL;
		free(temp);
		temp = temp2;	
	}
}
 
void destroyListTail(node *tail)
{
	node *temp;
	node *temp2;
	temp = NULL;
	temp2 = NULL;
	temp = tail;
	while(temp != NULL)
	{
		temp2 = temp->prev;
		if (temp->prev != NULL) temp->prev = NULL;
		if (temp->next != NULL) temp->next = NULL;
		free(temp);
		temp = temp2;	
	}
}
 
int listSizeHead(node *head)
{
	int size = 0;
	while (head != NULL)
	{	
		head = head->next;
		size++;
	}
	return size;
}
 
int listSizeTail(node *tail)
{
        int size = 0;
        while (tail != NULL)
        {
                tail = tail->prev;
                size++;
        }
        return size;
}
 
void printIntDataHead(node * head)
{
	node * temp = NULL;
 
	temp = head;
	while(temp != NULL)
	{
		printf("%d ",temp->data);
		temp = temp->next;
	}
	printf("\n");
}
 
void insert(node ** head, node ** tail, int position, int data)
{
	int i;
	node *temp, *temp2;
	temp = temp2 = NULL;
 
	temp = *head;
	for(i = 0; i < position; i++)
	{
		temp = temp -> next;
	}
 
		if (*head == NULL)
		{
			*head = (node *) malloc(sizeof(node));
			*tail = *head;
			(*head)->prev = NULL;
			(*head)->next = NULL;
			(*head)->data = data;
		}
		else if (*head == temp)
		{
			temp2 = (node *) malloc (sizeof(node));
			temp2->next = *head;
			(*head)->prev = temp2;
			*head = (*head)->prev;
			(*head)->prev = NULL;
			(*head)->data = data;
		}
		else
		{
			temp2 = (node *) malloc (sizeof(node));	
			temp2->next = temp;
			temp2->prev = temp->prev;
			temp->prev->next = temp2;
			temp->prev = temp2;
			temp2->data = data;
		}
}
 
void append(node **head, node **tail, int position, int data)
{
	int i;
	node *temp, *temp2;
	temp = temp2 = NULL;
 
	temp = *head;
	for(i = 0; i < position; i++)
	{
		temp = temp -> next;
	}
 
		if (*head == NULL)
		{
			*head = (node *) malloc(sizeof(node));
			*tail = *head;
			(*head)->prev = NULL;
			(*head)->next = NULL;
			(*head)->data = data;
		}
		else if (*tail == temp)
		{
			temp2 = (node *) malloc (sizeof(node));
			temp2->prev = *tail;
			temp2->next = NULL;
			(*tail)->next = temp2;
			*tail = temp2;
			(*tail)->data = data;
		}
		else
		{
			temp2 = (node *) malloc (sizeof(node));
			temp2->prev = temp;
			temp2->next = temp->next;
			temp->next->prev = temp2;
			temp->next = temp2;
			temp2->data = data;
 
		}
 
}
 
void deleteNode(node **head, node **tail, int position)
{
	int i;
	node * temp = NULL;
 
	temp = *head;
	for(i = 0; i < position; i++)
	{
		temp = temp->next;
	}
	if(temp != *head && temp != *tail)
	{
		temp->next->prev = temp->prev;
		temp->prev->next = temp->next;
		temp->prev = NULL;
		temp->next = NULL;
	}
	else if (temp == *head)
	{
		temp->next->prev = NULL;
		*head = temp->next;
		temp->next = NULL;
	}
	else
	{
		temp->prev->next = NULL;
		*tail = temp->prev;
		temp->prev = NULL;
	}
	free(temp);
}
 
void loadListData(node *head)
{
	int i = 0;
	node *temp = NULL;
	temp = head;
	printf("Enter a value or -1 to quit: ");
	scanf("%d", &i);
	while(i != -1)
	{
		temp->data = i;
		temp = temp->next;
		if(temp == NULL)
		{
			printf("List is full of data!\n");
			break;
		}
		printf("Enter a value or -1 to quit: ");
		scanf("%d", &i);
	}
 
}
 
 
void loadNode(node *head, int position, int value)
{
	int i;
	node *temp = NULL;
	temp = head;
 
	temp = head;
	for(i = 0; i < position; i++)
	{
		temp = temp->next;
	}
	temp->data = value;
}
 
void createNode(node* head, node* tail)
{
	head = (node *) malloc(sizeof(node));
	tail = head;
	head->prev = NULL;
	head->next = NULL;
}
 
void copyList(node *head, node **copyHead, node **copyTail)
{
	node *new, *temp;
	new = *copyHead = *copyTail = temp = NULL;
	temp = head;
	while(temp != NULL)
	{
		if (*copyHead == NULL)
		{
			*copyHead = (node *) malloc(sizeof(node));
			*copyTail = *copyHead;
			(*copyHead)->prev = NULL;
			(*copyHead)->next = NULL;
			(*copyHead)->data = temp->data;
		}
		else
		{
			new = (node *) malloc(sizeof(node));
			new->prev = *copyTail;
			new->next = NULL;
			(*copyTail)->next = new;
			*copyTail = new;
			(*copyTail)->data = temp->data;
		}
		temp = temp->next;
	}
}
 
int findData(node *head, int data)
{
	int counter = 0;
	while(head != NULL)
	{
		if(head->data == data) break;
		counter++;
		head = head->next;
	}
	return counter;
}

lab46:~/src/data$ ./linkedListDev
Creating a list of 4 nodes...
Size of the list is: 4
Load list data
Enter a value or -1 to quit: 1
Enter a value or -1 to quit: 2
Enter a value or -1 to quit: 3
Enter a value or -1 to quit: 4
List is full of data!
1 2 3 4
Inserting node 0 with data of 3200 before head node...
Size of the list is: 5
3200 1 2 3 4
Inserting node with data of -3200 before tail node...
Size of the list is: 6
3200 1 2 3 -3200 4
Appending node with data of 2300 after head node...
Size of the list is: 7
3200 2300 1 2 3 -3200 4
Appending node with data of -2300 after tail node...
Size of the list is: 8
3200 2300 1 2 3 -3200 4 -2300
Loading node 0 with data of 0...
Size of the list is: 8
0 2300 1 2 3 -3200 4 -2300
Loading tail node with data of 255...
Size of the list is: 8
0 2300 1 2 3 -3200 4 255
Deleting head node...
Size of the list is: 7
2300 1 2 3 -3200 4 255
Deleting tail node...
Size of the list is: 6
2300 1 2 3 -3200 4
Deleting node 2...
Size of the list is: 5
2300 1 3 -3200 4
Size of the list is: 5
2300 1 3 -3200 4
The node location of 3 is 2
lab46:~/src/data$

References

Top

The element of the stack data structure which is available for stack operations (see the data structures topic “Stack” for details of stack operations) is known as the top of TOS (top of stack). The stack position top may have data “pushed” (see the data topic “Pushing” for details of the stack operation push) into it at which point the stack pointer, a pointer pointing to the stack element which is available for stack operations, is incremented so as to expose the next stack element for stack operations. The stack position top may also have data “popped” (see the data topic “Popping” for details of the stack operation pop) from it at which point the stack pointer, is decremented to expose the next stack element for stack operations.

References

<html><a href=“http://en.wikipedia.org/wiki/Stack_(abstract_data_type)”>http://en.wikipedia.org/wiki/Stack_(abstract_data_type)</a></html>
http://www.i-programmer.info/babbages-bag/357-advanced-data-structures.html
http://www.cs.bu.edu/teaching/c/stack/array/
http://www.cs.bu.edu/teaching/c/stack/linked-list/

Overflow Condition

If, a data structure such as a stack is full and cannot accept (store) anymore data, it is considered to be in an overflow state.

References

http://wiki.answers.com/Q/Overflow_and_underflow_conditions_in_data_structures
<html><a href=“http://en.wikipedia.org/wiki/Stack_(abstract_data_type)”>http://en.wikipedia.org/wiki/Stack_(abstract_data_type)</a></html>

Underflow Condition

If, a data structure, such as a stack, is empty, no more data can be taken from it; it cannot be “popped” again as the data retreived would be erroneous, and the data structure position pointer, the stack pointer in the case of stacks, would be manipulated to point to some memory location which is no longer part of the data structure; this is considered to be the “underflow” state.

References

http://wiki.answers.com/Q/Overflow_and_underflow_conditions_in_data_structures
<html><a href=“http://en.wikipedia.org/wiki/Stack_(abstract_data_type)”>http://en.wikipedia.org/wiki/Stack_(abstract_data_type)</a></html>

Free

The function free, is used to release heap (see the data topic “Heap” for details) memory which was previously allocated dynamically, that is at run time, through the use of one of the memory allocation functions. free takes a single pointer argument; it releases the memory pointed to by its argument.

References

Structure

A structure or record is a collection of variables grouped together under a single identifier. The data are related somehow, that is the point of a structure or record. A classic example of a structure or record is that of an employee. Character array or string members of an employee structure or record might be the employee's first and last names, street, address, city, and state of residence. Integer members of the employee structure or record might be employee number, age, etc. The structure data type, also known as an abstract data type, provides an elegant and powerful way for keeping related data together.

References

http://en.wikipedia.org/wiki/Record_(computer_science)
http://www.roseindia.net/c-tutorials/c-structure.shtml

Queue

A queue is a FIFO (see the data topic “FILO/FIFO” for details) type data structure. That is, data is taken from the queue in the same order that it was placed into it. Enqueuing Dequeue The following program demonstrates an array-based queue.

queueTest.c

//queueTest.c
//John T. Rine
//October 29, 2011
 
#include<stdio.h>
#include<stdlib.h>
 
struct Queue
{
	char *queueArray;
	int count;
	int size;
	int startIndex;
};
 
typedef  struct Queue queue;
 
 
void createQueue(queue *, int);
void destroyQueue(queue *);
void enqueue(queue *, char);
void printQueue(queue *);
int queueCount(queue *);
char dequeue(queue *);
 
int main(int argc, char **argv)
{
	queue newQueue;
 
	createQueue(&newQueue, 25);
	destroyQueue(&newQueue);
	enqueue(&newQueue, 'J');
        enqueue(&newQueue, 'o');
        enqueue(&newQueue, 'h');
        enqueue(&newQueue, 'n');
	printf("Calling printQueue(&newQueue)...\n");
        printQueue(&newQueue);
	printf("Calling and printing return value from dequeue...\n");
	printf("%c, ", dequeue(&newQueue));
        printf("%c, ", dequeue(&newQueue));
	printf("\n");
	printf("Calling printQueue(&newQueue)...\n");
	printQueue(&newQueue);
 
	return 0;
}
 
void createQueue(queue *queuePTR, int size)
{
	char *queueArrayPTR = NULL;
	queueArrayPTR = (char *)malloc(sizeof(char) * size);
	queuePTR->queueArray = queueArrayPTR;
	queuePTR->size = size;
	queuePTR->count = 0;
	queuePTR->startIndex = 0;
}
 
void destroyQueue(queue *queuePTR)
{
	free(queuePTR->queueArray);
}
 
void enqueue(queue *queuePTR, char data)
{
	int queueArrayIndex;
	if(queuePTR->count < queuePTR->size)
	{
		queueArrayIndex = queuePTR->startIndex + queuePTR->count;
		queuePTR->queueArray[queueArrayIndex] = data;
		queuePTR->count++;
	}
	else printf("Queue is full!\n");  
}
 
void printQueue(queue *queuePTR)
{
	int i;
	for(i = 0; i < queuePTR->count; i++) printf("%c, ",queuePTR->queueArray[(queuePTR->startIndex + i)%queuePTR->size]);
	printf("\n");
}
 
 
int queueCount(queue *queuePTR)
{
	return queuePTR->count;
}
 
char dequeue(queue *queuePTR)
{
	char ret;
	if(queuePTR->count == 0)
	{
		 printf("queue is empty!\n");
		exit(1);
	}
	ret = queuePTR->queueArray[queuePTR->startIndex];
    	queuePTR->count--;
    	queuePTR->startIndex = (queuePTR->startIndex + 1)%queuePTR->size;
    	return ret;
}

This is the output of the queueTest.c program:

lab46:~/src/data$ gcc queueTest.c -o queueTest
lab46:~/src/data$ ./queueTest
Calling printQueue(&newQueue)...
J, o, h, n,
Calling and printing return value from dequeue...
J, o,
Calling printQueue(&newQueue)...
h, n,
lab46:~/src/data$

References

http://www.cs.bu.edu/teaching/c/queue/array/types.html
http://technical-interview.com/Implement_a_Queue_using_an_Array.aspx
<html><a href=“http://en.wikipedia.org/wiki/Queue_(abstract_data_type)”>http://en.wikipedia.org/wiki/Queue_(abstract_data_type)</a></html>

Array

An array is a set of similar data type data stored in a contiguous section of memory. Since data contained in a array is packaged in similar sized memory blocks and stored in contiguous memory locations, it becomes possible to simply add an array element offset to the base address of the array to access data at a specific element withing the array. The following program illustrates the use off an index to access elements of an array.

arrayTest.c

//arrayTest.c
//John T. Rine
//October 29, 2011
 
#include<stdio.h>
 
int main(int argc, char **argv)
{
        char array[26] = {0};
        int i;
        printf("Enter a string (<= 25 character) to place into a character array\n");
        gets(array);
        printf("array contains %s\n", array);
        i = 0;
        while(array[i] != '\0')
        {
                printf("array[%d] = %c\n", i, array[i]);
                printf("*(array + %d) = %c\n", i, *(array + i));
                i++;
        }
 
        return 0;
}

This is the output of the arrayTest.c program listed above.

lab46:~/src/data$ ./arrayTest
Enter a string (<= 25 character) to place into a character array
John T. Rine
array contains John T. Rine
array[0] = J
*(array + 0) = J
array[1] = o
*(array + 1) = o
array[2] = h
*(array + 2) = h
array[3] = n
*(array + 3) = n
array[4] =
*(array + 4) =
array[5] = T
*(array + 5) = T
array[6] = .
*(array + 6) = .
array[7] =
*(array + 7) =
array[8] = R
*(array + 8) = R
array[9] = i
*(array + 9) = i
array[10] = n
*(array + 10) = n
array[11] = e
*(array + 11) = e
lab46:~/src/data$

References

LIFO/FIFO

LIFO is an acronym for “Last In, First Out”; FIFO is an acronym for “First In, First Out”. The stack is a last in, first out or LIFO data structure whereas the queue is a first in, first out or FIFO data structure. Due to the nature of the stack, one use is to reverse the order of data items. The data items to be reveresed are pushed onto the stack, and then to reverse them, they are popped off.

References

http://en.wikipedia.org/wiki/FIFO
<html><a href=“http://en.wikipedia.org/wiki/LIFO_(computing)”>http://en.wikipedia.org/wiki/LIFO_(computing)</a></html>
http://introcs.cs.princeton.edu/java/43stack/

hpc1 Topics

Keyword 1

References

Keyword 2

Identification and definition of the chosen keyword.

If you want to demonstrate something on the command-line, you can do so as follows:

lab46:~$ cd src
lab46:~/src$ gcc -o hello hello.c
lab46:~/src$ ./hello
Hello, World!
lab46:~/src$