include

include

include

typedef struct node { void* dataPtr; struct node* link; } NODE; typedef struct { int count; NODE* pos; NODE* head; NODE* rear; int (compare) (void argu1, void* argu2); } LIST;

LIST* createList (int (compare) (void argu1, void* argu2)) { //Local Definitions LIST* list; //Statements list = (LIST*)malloc(sizeof(LIST)); if (list) { list->head = NULL; list->pos = NULL; list->rear = NULL; list->count = 0; list->compare = compare; } // if return list; } // createList int addNode(LIST* pList, void* dataInPtr) { //Local Definitions bool found; bool success; NODE* pPre; NODE* pLoc; //Statements found = _search(pList, &pPre, &pLoc, dataInPtr); if (found) // Duplicate keys not allowed return (+1); success = _insert(pList, pPre, dataInPtr); if (!success) // Overflow return (-1); return (0); } // addNode

static bool _insert(LIST* pList, NODE* pPre, void* dataInPtr) { //Local Definitions NODE* pNew; //Statements if (!(pNew = (NODE*)malloc(sizeof(NODE)))) return false; pNew->dataPtr = dataInPtr; pNew->link = NULL; if (pPre == NULL) { // Adding before first node or to empty list. pNew->link = pList->head; pList->head = pNew; if (pList->count == 0) // Adding to empty list. Set rear pList->rear = pNew; } // if pPre else { // Adding in middle or at end pNew->link = pPre->link; pPre->link = pNew; // Now check for add at end of list if(pNew->link == NULL) pList->rear = pNew; } // if else (pList->count)++; return true; } // _insert

bool removeNode (LIST* pList, void* keyPtr, void** dataOutPtr) { //Local Definitions bool found; NODE* pPre; NODE* pLoc; //Statements found = _search(pList, &pPre, &pLoc, keyPtr); if (found) _delete(pList, pPre, pLoc, dataOutPtr); return found; } // removeNode void _delete(LIST* pList, NODE* pPre, NODE* pLoc, void** dataOutPtr) { //Statements *dataOutPtr = pLoc->dataPtr; if (pPre == NULL) // Deleting first node pList->head = pLoc->link; else // Deleting any other node pPre->link = pLoc->link; // Test for deleting last node if (pLoc->link == NULL) pList->rear = pPre; (pList->count)--; free(pLoc); return; } // _delete

bool searchList(LIST* pList, void* pArgu, void** pDataOut) { //Local Definitions bool found; NODE* pPre; NODE* pLoc; //Statements found = _search(pList, &pPre, &pLoc, pArgu); if (found) pDataOut = pLoc->dataPtr; else *pDataOut = NULL; return found; } // searchList bool _search(LIST pList, NODE** pPre, NODE** pLoc, void* pArgu) { //Macro Definition

define COMPARE \

( ((* pList->compare) (pArgu, (pLoc)->dataPtr)) ) //Local Definitions int result; //Statements *pPre = NULL; *pLoc = pList->head; if (pList->count == 0) return false; // Test for argument > last node in list if ( COMPARE > 0) { *pPre = pList->rear; *pLoc = NULL; return false; } // if while ((result = COMPARE) > 0) { // Have not found search argument location *pPre = *pLoc; *pLoc = (*pLoc)->link; } // while if (result == 0) // argument found--success return true; else return false; } // _search static bool retrieveNode(LIST pList, void* pArgu, void** dataOutPtr) { //Local Definitions bool found; NODE* pPre; NODE* pLoc; //Statements found = _search(pList, &pPre, &pLoc, pArgu); if (found) { dataOutPtr = pLoc->dataPtr; return true; } // if *dataOutPtr = NULL; return false; } // retrieveNode bool emptyList(LIST pList) { //Statements return (pList->count == 0); } // emptyList bool emptyList(LIST* pList) { //Statements return (pList->count == 0); } bool fullList(LIST* pList) { //Local Definitions NODE* temp; //Statements if ((temp = (NODE*)malloc(sizeof((pList->head))))) { free(temp); return false; } // if return true; } int listCount(LIST pList) { //Statements return pList->count; } bool traverse(LIST* pList, int fromWhere, void** dataPtrOut) { //Statements if (pList->count == 0) return false; if (fromWhere == 0) { // Start from first node pList->pos = pList->head; dataPtrOut = pList->pos->dataPtr; return true; } // if fromwhere else { // Start from current position if (pList->pos->link == NULL) return false; else { pList->pos = pList->pos->link; *dataPtrOut = pList->pos->dataPtr; return true; } // if else } // if fromwhere else } // traverse LIST destroyList(LIST* pList) { //Local Definitions NODE* deletePtr; //Statements if (pList) { while (pList->count > 0) { // First delete data free(pList->head->dataPtr); // Now delete node deletePtr = pList->head; pList->head = pList->head->link; pList->count--; free(deletePtr); } // while free(pList); } // if return NULL; } // destroyList

헤더파일은 이와 같습니다. Testing Insert and Delete Logic Testing list algorithms requires careful planning. We discuss testing insert logic and delete logic. Testing Insert Logic Because the list is ordered, we need at least four test cases to validate the insert logic:

1. Insert a node into a null list—This test is always done automatically because the list starts out in a null state.
2. Insert a node before the first data node—This test is not automatic; therefore, we need to arrange the input so that this case is tested.
3. Insert between two data nodes—Again, this test is not automatic. We need to make sure that the test cases include the insertion of at least one node between two existing nodes.

4. Insert after the last node—Because this case is the same as the insert into a null list, it is automatic. Nevertheless, we recommend a test case in which the new data are inserted after the last node in the list.

5. Delete to a null list—To fully test the delete logic, one test case should delete all of the data from the list and then insert new data.

6. Delete the first data node in the list—When dealing with lists, the most common locations for errors are the first and last elements in the list. Make sure that one of the test cases deletes the first data node in the list.

7. Delete a node between two data nodes—Because this is the most common case, it is usually tested. We need to analyze the test data, however, to ensure that at least one of the delete cases deletes a node between two data nodes.

8. Delete the node at the end of the list—This test is not automatic. Make sure that one of the delete cases deletes the node at the end of the list.

9. Try to delete a node that doesn’t exist—This test is not obvious. Some programs erroneously delete a node in the list even when the target node does not exist. It is thus very important that we also test the not-found conditions.

10. Try to delete a node whose key is less than the first data node’s key—A subtle error in the program could result in the first node being deleted when the target does not exist. Make sure this case is tested.

11. Try to delete a node whose key is greater than the last data node’s key.

12. Try to delete from an empty list—This is the opposite of the previous condition. It needs to be included in the test cases.

이를 구하라는 데 코드를 못짜겠어서 질문을 올립니다