data structure program of c++

Question

Based on the header file given below;

Write the code for main( ) function to decode the secret message as given in the array of characters below by using the concept of Stack Linked List. You are required to insert the decoded characters into two (2) stack alternatively; the first character is decoded and push into the first stack, the second character is decoded and push into the second stack, the third character is decoded and push into the first stack again, the fourth character is decoded and push into the second stack again and alternately until the end of the array.

 

You have to use the given array and decode each character based on the following:-

              char data [ 8 ] = {'M', 'G', 'G', 'E', 'G', 'P', 'R', 'Q'};

 

To decode the secret message in the array, you are required to replace the characters based on the secret key. The key for the first stack is -2 and the key for the second stack is -4. This means, before you push the first character into the first stack, you must replace it with the character of two (2) letters backward while the second character for the second stack must be replaced with the character of four (4) letters backward. This is done for each character alternatively for the given array. For example, letter 'M' will be replaced by letter 'K' for the first stack and letter 'G' will be replaced with letter 'C' for second stack. You must use coding to do the replacement of the characters.

 

Your code must also display data from both stack. As the stack will store data by using the concept of First In Last Out, all data in the stack will be in reverse after printing. You may use another one or two stack more or any other way to rearrange the output of the first and second stack so that the printed values will be in correct order.

 

You may use or call any of the following functions to write the code for main( ) function:-

·        Push( )

·        Pop( )

·        Empty( )

·        TopStack( )

 

Output Example:

    K E E P C A L M                                                 

 

//StackLL.h

#ifndef STACKLL_H

#define STACKLL_H

template <class MyData>

struct Nod

{

      MyData data;

      Nod <MyData> *next;

};

 template <class MyData>

class StackLL

{

private:

      int count;

      Nod <MyData> *top;

public:

      StackLL();

      void Push(MyData);

      void Pop();

      bool Empty();

      MyData TopStack();

};

#endif;

Answer 1

//************ DataNode.h *****************************//

#ifndef _DATA_NODE

#define _DATA_NODE

#include <stdlib.h>

typedef

class DataNode

{

private:

void * data;

int size;

public:

int GetSize() { return(size); }

DataNode( void * Data, int n);

DataNode( DataNode & dataNode);

DataNode( DataNode * dataNode);

~DataNode();

Get( void * buff);

DataNode( char * dataStr);

void HexDump(char * debugMsg=NULL);

} * TDataNode;

#define DATA_NODE_SIZE (sizeof(DataNode))

#define TDATA_NODE_SIZE (sizeof(TDataNode))

#endif

//***** _STACK.H ************************************//

#ifndef _STACK

#define _STACK

#ifndef _DATA_NODE

#include "datanode.h"

#endif

typedef struct _TStackNode

{

TDataNode dataNode;

struct _TStackNode * next;

} *TStackNode;

#define STACK_NODE_SIZE (sizeof(struct _TStackNode))

#define TSTACK_NODE_SIZE (sizeof(TStackNode))

typedef

class _Stack

{

private:

TStackNode head;

TStackNode tail;

int count;

public:

int GetCount() { return(count); }

bool IsEmpty() { return(count==0); }

_Stack();

_Stack(_Stack & );

void Push( TDataNode dataNode);

TDataNode Pop();

TDataNode Top();

TDataNode Tail();

} *TStack;

#define STACK_SIZE ( sizeof(_Stack))

#define TSTACK_SIZE (sizeof(TStack))

//********* DataNode.cpp ********************//

#include <stdlib.h>

#include <string.h>

#include <stdio.h>

#ifndef _DATA_NODE

#include "datanode.h"

#endif

DataNode::DataNode( void * Data, int n)

{

this->data = malloc(n);

if (this->data!=NULL)

{

memcpy(this->data,Data,n);

this->size = n;

}

else

{

this->data = NULL;

this->size=0;

}

}

DataNode::DataNode( DataNode & dataNode)

{

int n = dataNode.size;

this->data = malloc(n);

if (this->data!=NULL)

{

memcpy(this->data,dataNode.data,n);

this->size = n;

}

else

{

this->data = NULL;

this->size=0;

}

}

DataNode::DataNode( DataNode * dataNode)

{

int n = dataNode->size;

this->data = malloc(n);

if (this->data!=NULL)

{

memcpy(this->data,dataNode->data,n);

this->size = n;

}

else

{

this->data = NULL;

this->size=0;

}

}

DataNode:: ~DataNode()

{

if (this->data !=NULL)

{

free(this->data);

this->data=NULL;

}

this->size=0;

}

DataNode::Get( void * buff)

{

memcpy(buff,this->data,this->size);

}

DataNode::DataNode( char * dataStr)

{

int n = strlen(dataStr)+1;

this->data = malloc(n);

if (this->data!=NULL)

{

strcpy((char*)this->data,dataStr);

this->size = n;

}

else

{

this->data = NULL;

this->size=0;

}

}

void DataNode::HexDump(char * debugMsg)

{

printf("****************************************************\n");

if (debugMsg != NULL)

{

printf("%s\n",debugMsg);

printf("****************************************************\n");

}

int n = this->size;

printf(" SIZE = %d \n",n);

char * buff = (char*)malloc(n);

memcpy(buff,this->data,n);

for (int iLoop=0; iLoop<n; iLoop++)

{

printf("%x",buff[iLoop]);

}

printf("\n");

}

//************ _Stack.cpp *****************************//

#include <stdio.h>

#ifndef _STACK

#include "_stack.h"

#endif

_Stack::_Stack()

{

head=tail=NULL;

count=0;

}

// deep copies

_Stack::_Stack(_Stack & stack )

{

int n = stack.count;

TStackNode curPtr = stack.head;

for (int iLoop=0; iLoop<n; iLoop++)

{

this->Push(curPtr->dataNode);

curPtr = curPtr->next;

}

}

void _Stack::Push( TDataNode dataNode)

{

if (count==0)

{

printf("first Push:\n");

head = (TStackNode) malloc(STACK_NODE_SIZE);

head->dataNode = new DataNode(dataNode);

dataNode->HexDump((char*)"pushed");

head->next = NULL;

tail = head;

}

else

{

printf("stack Push:\n");

TStackNode newStackNode = (TStackNode) malloc(STACK_NODE_SIZE);

newStackNode->dataNode = new DataNode(dataNode);

dataNode->HexDump((char*)"pushed");

newStackNode->next = NULL;

tail->next = newStackNode;

tail = tail->next;

}

count++;

printf(" count = %d \n",count);

}

TDataNode _Stack::Pop()

{

TDataNode dataNodeReturn = NULL;

if (count>1)

{

//points at next to last node

TStackNode cur = head;

for (int iLoop=0; iLoop<count-2; iLoop++)

{

cur=cur->next;

}

TStackNode tempStackNode = tail;

tail = cur;

tail->next=NULL;

count--;

printf(" Pop: count = %d \n",count);

dataNodeReturn = tempStackNode->dataNode ;

}

else if (count==1)

{

dataNodeReturn = head->dataNode;

head=tail=NULL;

count=0;

}

return(dataNodeReturn);

}

TDataNode _Stack::Top()

{

return(head->dataNode);

}

TDataNode _Stack::Tail()

{

return(tail->dataNode);

}

//*********** Main.cpp *************************//

using namespace std;

#include <iostream>

#include <string.h>

#ifndef _STACK

#include "_stack.h"

#endif

#ifndef _DEBUG

int main(int argc, char ** argv)

{

char data [ 8 ] = {'M', 'G', 'G', 'E', 'G', 'P', 'R', 'Q'};

TDataNode dataNodes[8];

for (int iLoop=0; iLoop<8; iLoop++)

{

int diff = ((iLoop%2)==0) ? 2 : 4;

data[iLoop]-=diff;

dataNodes[iLoop] = new DataNode(&data[iLoop],sizeof(char));

}

_Stack stack1;

_Stack stack2;

for (int iLoop=0; iLoop<8; iLoop++)

{

if ((iLoop%2)==0)

{

stack1.Push(dataNodes[iLoop]);

}

else

{

stack2.Push(dataNodes[iLoop]);

}

}

_Stack stackA;

_Stack stackB;

for (int iLoop=0; iLoop<4; iLoop++)

{

TDataNode dataNodeA = stack1.Pop();

TDataNode dataNodeB = stack2.Pop();

stackA.Push(dataNodeA);

stackB.Push(dataNodeB);

}

for (int iLoop=0; iLoop<4; iLoop++)

{

TDataNode dataNode = stackA.Pop();

char ch;

dataNode->Get(&ch);

cout << ch;

}

for (int iLoop=0; iLoop<4; iLoop++)

{

TDataNode dataNode = stackB.Pop();

char ch;

dataNode->Get(&ch);

cout << ch;

}

}

#else

int main(int argc, char** argv)

{

char dataStr[25];

strcpy(dataStr,"HELLO");

int iNum=12;

long longIntNum = 52769;

TDataNode A[3];

A[0] = new DataNode(dataStr);

A[1] = new DataNode(&iNum,sizeof(int));

A[2] = new DataNode(&longIntNum,sizeof(long));

for (int iLoop=0; iLoop<3; iLoop++)

{

char debugMsg[25];

sprintf(debugMsg," rec # %d ",(iLoop+1));

A[iLoop]->HexDump(debugMsg);

}

_Stack myStack;

for (int iLoop=0; iLoop<3; iLoop++)

{

myStack.Push(A[iLoop]);

}

while (!myStack.IsEmpty())

{

TDataNode curDataNode = myStack.Pop();

curDataNode->HexDump();

}

return 0;

}

#endif