C++. Collection App with Linear Link List

Question

Introduction

In this program, you will change your collection app to use a linear linked list. The linear linked list has to be in order by some data field in your item class, such as a name, ID, etc.

Answer 1

#ifndef _SORTED_LINKED_LIST

#define _SORTED_LINKED_LIST

typedef int (*TCompareCallback)(void *,void *);

typedef struct _TDataStr

{

char * data;

int size;

} * TDataStr;

#define DATASTR_SIZE (sizeof(struct _TDataStr))

typedef struct _TListNode

{

struct _TDataStr dataStr;

struct _TListNode * next;

}*TListNode;

#define LISTNODE_SIZE (sizeof(struct _TListNode))

typedef struct _TSortedLinkedList

{

TListNode first;

TListNode last;

TCompareCallback compareFunc;

int count;

} * TSortedLinkedList;

void SortedLinkedList_Init(TSortedLinkedList, TCompareCallback);

int SortedLinkedList_Insert(TSortedLinkedList, TDataStr);

int SortedLinkedList_IndexerGetAtIndex(TSortedLinkedList , int iIndexPos, TDataStr);

int SortedLinkedList_RemoveDelete(TSortedLinkedList, int iIndexPos, TDataStr);

void SortedLinkedList_Destroy(TSortedLinkedList);

void SortedLinkedList_Copy(TSortedLinkedList dest, TSortedLinkedList source);

#endif

/*** SORTED LINKED LIST . cpp ****/

#include <string.h>

#include <stdlib.h>

#ifndef _SORTED_LINKED_LIST

#include "sorted_Linked_List.h"

#endif

using namespace std;

#include <iostream>

void SortedLinkedList_Init(TSortedLinkedList sortedLinkedList, TCompareCallback compareCallbackFuncPtr)

{

sortedLinkedList->first = sortedLinkedList->last = NULL;

sortedLinkedList->count=0;

sortedLinkedList->compareFunc = compareCallbackFuncPtr;

}

int SortedLinkedList_Insert(TSortedLinkedList sortedLinkedList, TDataStr dataStr)

{

int iReturn=0;

TListNode newListNode = (TListNode)malloc(LISTNODE_SIZE);

memcpy(&newListNode->dataStr,dataStr,DATASTR_SIZE);

if (newListNode!=NULL)

{

if (sortedLinkedList->count==0)

{

newListNode->next = NULL;

sortedLinkedList->first = sortedLinkedList->last = newListNode;

}

if (sortedLinkedList->count==1)

{

int iCompareReturn = sortedLinkedList->compareFunc((void *)newListNode->dataStr.data,(void*)sortedLinkedList->first->dataStr.data);

if (iCompareReturn>0)

{

//new Node goes after

newListNode->next = NULL;

sortedLinkedList->last->next = newListNode;

sortedLinkedList->last = sortedLinkedList->last->next;

}

else //new node goes first

{

newListNode->next = sortedLinkedList->first;

sortedLinkedList->first = newListNode;

}

}

else //count>1

{

TListNode cur = sortedLinkedList->first;

while (cur!=NULL)

{

int iCompareReturn = sortedLinkedList->compareFunc((void*)cur->dataStr.data,(void*)newListNode->dataStr.data);

if (iCompareReturn<=0)

{

cur=cur->next;

}

else

{

break;

}

}

if (cur!=NULL) //there exists an item in the list that is greater, before which the new node must be inserted

{

if ((cur != sortedLinkedList->first) && (cur != sortedLinkedList->last)) //cur stopped between first and last

{

//points at the node BEFORE the cur

cout << "inserting in between...." <<endl;

TListNode beforePtr = sortedLinkedList->first;

while (beforePtr->next!=cur) { beforePtr = beforePtr->next; }

//new node is inserted in between beforePtr and cur

newListNode->next = cur;

beforePtr->next = newListNode;

}

else if (cur==sortedLinkedList->first)//the first node is greater, so the new node goes at the front!!

{

cout << "inserting at the beginning..." << endl;

newListNode->next = sortedLinkedList->first;

sortedLinkedList->first = newListNode;

}

else if (cur==sortedLinkedList->last) //the last node is greater, so the new node goes before the last

{

cout << "inserting next to last..." << endl;

TListNode beforePtr= sortedLinkedList->first;

while (beforePtr->next != sortedLinkedList->last) { beforePtr = beforePtr->next;}

newListNode->next = sortedLinkedList->last;

beforePtr->next = newListNode;

}

}

else //the new node is the largest, so it goes on the end

{

cout << "inserting last..." <<endl;

sortedLinkedList->last->next = newListNode;

sortedLinkedList->last=sortedLinkedList->last->next;

}

}

sortedLinkedList->count++;

}

else

{

iReturn=-1;

}

return(iReturn);

}

int SortedLinkedList_IndexerGetAtIndex(TSortedLinkedList sortedLinkedList , int iIndexPos, TDataStr dataStr)

{

int iReturn=0;

if (iIndexPos>=0 && iIndexPos<sortedLinkedList->count)

{

TListNode cur = sortedLinkedList->first;

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

{

cur=cur->next;

}

memcpy(dataStr,&cur->dataStr.data,DATASTR_SIZE);

}

else

{

iReturn=-1;

}

return(iReturn);

}

int SortedLinkedList_RemoveDelete(TSortedLinkedList, int iIndexPos, TDataStr)

{

}

void SortedLinkedList_Destroy(TSortedLinkedList sortedLinkedList)

{

TListNode cur = sortedLinkedList->first;

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

{

sortedLinkedList->first = sortedLinkedList->first->next;

free(cur);

cur=sortedLinkedList->first;

}

sortedLinkedList->first = sortedLinkedList->last=NULL;

sortedLinkedList->count=0;

}

void SortedLinkedList_Copy(TSortedLinkedList dest, TSortedLinkedList source);

// Main.cpp

using namespace std;

#include <iostream>

#include <string.h>

#include <stdlib.h>

#ifndef _SORTED_LINKED_LIST

#include "sorted_linked_list.h"

#endif

#ifndef _DATAREC

#include "datarec.h"

#endif

int CompareInt(void * rec1, void * rec2)

{

int * intPtr1 = (int*)rec1;

int * intPtr2 = (int*)rec2;

int iNum1 = *intPtr1;

int iNum2 = *intPtr2;

//cout << "comparing " <<iNum1 << " vs " << iNum2 << endl;

return(iNum1-iNum2);

}

int CompareDouble(void * rec1, void * rec2)

{

int iReturn=0;

double * dblPtr1 = (double*)rec1;

double * dblPtr2 = (double*)rec2;

double dblAmt1 = *dblPtr1;

double dblAmt2 = *dblPtr2;

if (dblAmt1!=dblAmt2)

{

iReturn = (dblAmt1 > dblAmt2) ? 1 : -1;

}

return(iReturn);

}

//compares by string, then by subtotal = longIntNum*flAmount

int CompareDataRec(void * rec1, void * rec2)

{

int iReturn=0;

TDataRec dataRecPtr1 = (TDataRec)rec1;

TDataRec dataRecPtr2 = (TDataRec)rec2;

char dataStr1[DATAREC_STR_LENGTH];

char dataStr2[DATAREC_STR_LENGTH];

dataRecPtr1->GetStr(dataStr1);

dataRecPtr2->GetStr(dataStr2);

iReturn = strcmp(dataStr1,dataStr2);

if (iReturn==0)

{

double subtotal1 = dataRecPtr1->GetLongIntNum()*dataRecPtr1->GetAmount();

double subtotal2 = dataRecPtr2->GetLongIntNum()*dataRecPtr2->GetAmount();

iReturn = CompareDouble((void*)&subtotal1,(void*)&subtotal2);

}

return(iReturn);

}

int CompareDataRecCSV(void * rec1, void * rec2)

{

char * strDataRec1 = (char*)rec1;

char * strDataRec2 = (char*)rec2;

char str[DATAREC_STR_LENGTH];

strcpy(str,strtok(strDataRec1,","));

long longIntNum = atol(strtok(NULL,","));

double amount = atof(strtok(NULL,","));

DataRec dataRec1(str,longIntNum,amount);

memset(str,0,DATAREC_STR_LENGTH);

strcpy(str,strtok(strDataRec2,","));

longIntNum = atol(strtok(NULL,","));

amount = atof(strtok(NULL,","));

DataRec dataRec2(str,longIntNum,amount);

return CompareDataRec((void*)&dataRec1,(void*)&dataRec2);

}