CE242-Spring’09-Homework#2
CE242 Data Structures and Algorithms Course @KHas – Spring 2009 – Homework #2 questions and solutions.
CE242 Data Structures and Algorithms course description is available here.
Download questions and solutions
Note: “ce242-spring09-hw2-q1-a.cpp” and “ce242-spring09-hw2-q1-b.cpp” need “List.cpp” module, so link them together while building the code.
Source files:
[List.h] | show
// ==================================================
// - File______: List.h _____________________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================
#ifndef LIST_H_
#define LIST_H_
/* type definitions */
struct Node
{
void *pData;
Node *pNext;
};
struct List
{
Node *pHead;
Node *pTail;
int size;
};
#define NodeNext(pNode) (pNode)->pNext
#define NodeData(pNode) (pNode)->pData
/* Function declarations */
List *ListCreate();
Node *ListPrepend(List *pList, const void *pData);
Node *ListAppend(List *pList, const void *pData);
void *ListDeleteHead(List *pList);
void *ListDeleteNth(List *pList, int idx);
Node *ListFindNode(List *pList, bool (*compare)(const void *, const void *), const void *pCmpData);
void *ListDeleteNode(List *pList, bool (*compare)(const void *, const void *), const void *pCmpData);
void ListForeach(List *pList, void (*callback)(void *, void *), void *pCallbackData);
void ListTruncate(List *pList);
int ListGetSize(List *pList);
bool ListIsEmpty(List *pList);
void ListDestroy(List *pList);
#endif /* LIST_H_ */
[List.cpp] | show
// ==================================================
// - File______: List.cpp ___________________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================
#include <cstdlib>
#include "List.h"
List *ListCreate()
{
List *pList;
pList = new List;
pList->pHead = NULL;
pList->pTail = NULL;
pList->size = 0;
return pList;
}
Node *ListPrepend(List *pList, const void *pData)
{
Node *pNode;
pNode = new Node;
pNode->pData = (void *) pData;
pNode->pNext = pList->pHead;
pList->pHead = pNode;
if (pList->size == 0)
{
pList->pTail = pNode;
}
++pList->size;
return pNode;
}
Node *ListAppend(List *pList, const void *pData)
{
Node *pNode;
pNode = new Node;
pNode->pData = (void *) pData;
pNode->pNext = NULL;
if (pList->size == 0)
{
pList->pHead = pNode;
}
else
{
pList->pTail->pNext = pNode;
}
pList->pTail = pNode;
++pList->size;
return pNode;
}
void *ListDeleteHead(List *pList)
{
Node *pNode;
void *pData;
if (pList->size == 0)
{
return NULL;
}
pNode = pList->pHead;
pData = pNode->pData;
pList->pHead = pNode->pNext;
delete pNode;
--pList->size;
if (pList->size <= 1)
{
pList->pTail = pList->pHead;
}
return pData;
}
void *ListDeleteNth(List *pList, int idx)
{
if ((idx < 0) || (idx >= pList->size))
{
return NULL;
}
if (idx == 0)
{
return ListDeleteHead(pList);
}
int i;
void *pData;
Node *pCur, *pPrev;
for (
pPrev = pList->pHead, pCur = pPrev->pNext, i = 1;
pCur != NULL;
pPrev = pCur, pCur = pCur->pNext, ++i
)
{
if (i == idx)
{
pPrev->pNext = pCur->pNext;
pData = pCur->pData;
delete pCur;
--pList->size;
return pData;
}
}
return NULL;
}
Node *ListFindNode(List *pList, bool (*compare)(const void *, const void *), const void *pCmpData)
{
for (Node *pNode = pList->pHead; pNode != NULL; pNode = pNode->pNext)
{
if (compare(pNode->pData, pCmpData))
{
return pNode;
}
}
return NULL;
}
void *ListDeleteNode(List *pList, bool (*compare)(const void *, const void *), const void *pCmpData)
{
Node *pCur, *pPrev;
void *pData;
/* handle first item outside of the loop */
if ((pPrev = pList->pHead) == NULL)
{
return NULL;
}
if (compare(pPrev->pData, pCmpData))
{
pList->pHead = pPrev->pNext;
pData = pPrev->pData;
delete pPrev;
--pList->size;
return pData;
}
/* first item is not what we are looking for, so traverse the entire list */
for (
pCur = pPrev->pNext;
pCur != NULL;
pPrev = pCur, pCur = pCur->pNext
)
{
if (compare(pCur->pData, pCmpData))
{
pPrev->pNext = pCur->pNext;
pData = pCur->pData;
delete pCur;
--pList->size;
return pData;
}
}
return NULL;
}
void ListForeach(List *pList, void (*callback)(void *, void *), void *pCallbackData)
{
for (Node *pNode = pList->pHead; pNode != NULL; pNode = pNode->pNext)
{
callback(pNode->pData, pCallbackData);
}
}
void ListTruncate(List *pList)
{
Node *pNode, *pNodeTmp;
for (pNode = pList->pHead; pNode != NULL; pNode = pNodeTmp)
{
pNodeTmp = pNode->pNext;
delete pNode;
}
pList->pHead = NULL;
pList->pTail = NULL;
pList->size = 0;
}
int ListGetSize(List *pList)
{
return pList->size;
}
bool ListIsEmpty(List *pList)
{
return (pList->size == 0);
}
void ListDestroy(List *pList)
{
ListTruncate(pList);
delete pList;
}
[ce242-spring09-hw2-q1-a.cpp] | show
// ==================================================
// - File______: ce242-spring09-hw2-q1-a.cpp ________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================
#include <iostream>
#include "List.h"
using namespace std;
struct Grade
{
int studId;
int grade;
};
void printGrade(void *pData, void *pCallbackData)
{
cout <<
"id: " << ((Grade *) pData)->studId <<
", grade: " << ((Grade *) pData)->grade << endl;
}
void deleteGrade(void *pData, void *pCallbackData)
{
delete (Grade *) pData;
}
void filterFailedGrades(void *pData, void *pCallbackData)
{
if (((Grade *) pData)->grade < 30)
{
ListAppend((List *) pCallbackData, pData);
}
}
void filterPassedGrades(void *pData, void *pCallbackData)
{
if (((Grade *) pData)->grade >= 30)
{
ListAppend((List *) pCallbackData, pData);
}
}
int main()
{
List *pListGrades = ListCreate();
int id, grade;
Grade *pGrade;
// read input
while (true)
{
cout << "id: ";
cin >> id;
if (id < 0)
{
break;
}
cout << "grade: ";
cin >> grade;
pGrade = new Grade;
pGrade->studId = id;
pGrade->grade = grade;
ListAppend(pListGrades, pGrade);
}
// create failed and passed lists
List *pListPassed = ListCreate();
List *pListFailed = ListCreate();
// filter main list for failed and passed grades
ListForeach(pListGrades, filterPassedGrades, pListPassed);
ListForeach(pListGrades, filterFailedGrades, pListFailed);
// print lists
cout << "--- all grades ------------------" << endl;
ListForeach(pListGrades, printGrade, NULL);
cout << "--- passed grades ---------------" << endl;
ListForeach(pListPassed, printGrade, NULL);
cout << "--- failed grades ---------------" << endl;
ListForeach(pListFailed, printGrade, NULL);
// destroy failed and passed lists
ListDestroy(pListPassed);
ListDestroy(pListFailed);
// delete all Grade objects pListGrades contains and destroy pListGrades
ListForeach(pListGrades, deleteGrade, NULL);
ListDestroy(pListGrades);
return 0;
}
[ce242-spring09-hw2-q1-b.cpp] | show
// ==================================================
// - File______: ce242-spring09-hw2-q1-b.cpp ________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================
#include <iostream>
#include "List.h"
using namespace std;
struct Grade
{
int studId;
int grade;
};
const int LIST_FAILED_IDX = 0;
const int LIST_PASSED_IDX = 1;
void printGrade(void *pData, void *pCallbackData)
{
cout <<
"id: " << ((Grade *) pData)->studId <<
", grade: " << ((Grade *) pData)->grade << endl;
}
void deleteGrade(void *pData, void *pCallbackData)
{
delete (Grade *) pData;
}
void filterFailedAndPassedGrades(void *pData, void *pCallbackData)
{
List **pListArr = (List **) pCallbackData;
Grade *pGrade = (Grade *) pData;
if (pGrade->grade < 30)
{
ListAppend(pListArr[LIST_FAILED_IDX], pGrade);
}
else
{
ListAppend(pListArr[LIST_PASSED_IDX], pGrade);
}
}
int main()
{
List *pListGrades = ListCreate();
int id, grade;
Grade *pGrade;
// read input
while (true)
{
cout << "id: ";
cin >> id;
if (id < 0)
{
break;
}
cout << "grade: ";
cin >> grade;
pGrade = new Grade;
pGrade->studId = id;
pGrade->grade = grade;
ListAppend(pListGrades, pGrade);
}
// create failed and passed lists
List *pListPassed = ListCreate();
List *pListFailed = ListCreate();
List *listArr[2];
listArr[LIST_FAILED_IDX] = pListFailed;
listArr[LIST_PASSED_IDX] = pListPassed;
// filter main list for failed and passed grades
ListForeach(pListGrades, filterFailedAndPassedGrades, listArr);
// print lists
cout << "--- all grades ------------------" << endl;
ListForeach(pListGrades, printGrade, NULL);
cout << "--- passed grades ---------------" << endl;
ListForeach(pListPassed, printGrade, NULL);
cout << "--- failed grades ---------------" << endl;
ListForeach(pListFailed, printGrade, NULL);
// destroy failed and passed lists
ListDestroy(pListPassed);
ListDestroy(pListFailed);
// delete all Grade objects pListGrades contains and destroy pListGrades
ListForeach(pListGrades, deleteGrade, NULL);
ListDestroy(pListGrades);
return 0;
}
