/* Task 2: Debugging a program with stacks, queues, and doubly-linked lists There are a number of errors in the following program. All errors are located in main() and structure definitions. Function declarations and definitions are correct! Locate all errors, fix them (as shown below), run the program and save its output as a comment at the end of the source file. Example: int num = 10; int *ptr; num = &ptr; // <== Error: Comment the line and write the correct line below // Write a short justification where appropriate // num = &ptr; // Error #1 ptr = # Name: */ #include #include #include #include #define DUMMY_TRAILER '\177' // octal ASCII code of the // last character in the ASCII table #define NUM_CITIES 10 typedef struct { char name[12]; int temperature[5]; } CITY; // Stack and Queue Node typedef struct node NODE; struct node { CITY city; node *next; }; // Doubly Linked List Node typedef struct d_node D_NODE; struct d_node { CITY city; NODE *forw; NODE *back; }; // Stack Functions NODE *push(NODE *stack, const CITY *pStu); NODE *pop(NODE **stack); // Queue Functions void enqueue(NODE **queue, NODE **rear, const CITY *pStu); NODE *dequeue(NODE **queue, NODE **rear); // Doubly Linked List Functions D_NODE *init_list(void); int insert(D_NODE *list, const CITY *pStu); void traverse_forw(D_NODE *list); void traverse_back(D_NODE *list); // Other Functions void printCity(const CITY *pCity); int main (void) { CITY cList[NUM_CITIES] = { {"Cupertino", {88, 89, 87, 85, 89}}, {"Flagstaff", {81, 80, 88, 89, 89}}, {"Los Angeles", {87, 88, 89, 89, 90}}, {"Philadelphia", {96, 99, 99, 90, 95}}, {"Phoenix", {106, 109, 109, 100, 105}}, {"Portland", {89, 90, 85, 89, 90}}, {"Reno", {108, 105, 109, 100, 108}}, {"Salem", {85, 90, 85, 89, 90}}, {"Tucson", {107, 100, 109, 100, 108}}, {"Yreka", {101, 109, 100, 108, 109}} }; NODE *stack = NULL; NODE *top = NULL; NODE *queue = NULL, *rear = NULL; NODE *front; D_NODE *list; list = init_list(); // build stack and queue with data from an array of CITY structures srand((unsigned int)time(NULL)); int count = rand() % 10; for ( int n = 0; n < count; n++) { int i = rand() % NUM_CITIES; int duplicate = insert(list, &cList[i]); if(duplicate) { // already in the list! push(stack, &cList[i]); enqueue(&queue, &rear, cList[i]); } } // display list printf(" LIST contents (forwards): "); traverse_forw(list); printf(" LIST contents (backwards): "); traverse_back(list); // display stack if (top) { printf(" STACK contents from top to bottom: "); while ((top = pop(stack))) { printCity(top->city); } } else printf ("Empty Stack! "); // display queue if (front) { printf(" QUEUE contents from front to rear: "); while ((front = dequeue( queue, rear))) { printCity(front->city); } } else printf ("Empty Queue! "); return 0; } /*************************************************** Displays the fileds of a CIS_CLASS structure Pre pCls - a pointer to a CIS_CLASS structure Post */ void printCity(const CITY *pCity) { printf("%-20s %3d ", pCity->name, pCity->temperature[0]); } // Stack Functions /*************************************************** Stack Insert: insert in the beginning */ NODE *push(NODE *stack, const CITY *pCity) { NODE *pnew; pnew = (NODE *) malloc(sizeof (NODE)); if (!pnew) { printf("... error in push! "); exit(1); } pnew->city = *pCity; pnew->next = stack; stack = pnew; return stack; } /*************************************************** Stack Delete: delete the first node */ NODE *pop(NODE **stack) { NODE *first; if (*stack == NULL) return NULL; first = *stack; *stack = (*stack)->next; first->next = NULL; return first; } // Queue Functions /*************************************************** Queue Insert: insert at the end */ void enqueue(NODE **queue, NODE **rear, const CITY *pCity) { NODE *pnew; pnew = (NODE *) malloc(sizeof (NODE)); if (!pnew) { printf("... error in enqueue! "); exit(1); } pnew->city = *pCity; pnew->next = NULL; if (*queue == NULL) *queue = pnew; else (*rear)->next = pnew; *rear = pnew; return; } /*************************************************** Queue Delete: remove the first node */ NODE *dequeue(NODE **queue, NODE **rear) { NODE *first; if (*queue == NULL) return NULL; first = *queue; *queue = (*queue)->next; if (*queue == NULL) *rear = NULL; first->next = NULL; return first; } // Doubly Linked List Functions /*************************************************** Initialization of a circularly doubly-linked list with one sentinel node */ D_NODE *init_list(void) { D_NODE *list; // allocate the sentinel node list = (D_NODE *) malloc(sizeof (D_NODE)); if (!list) { printf("Error in init_list! "); exit(1); } list->city.name[0] = DUMMY_TRAILER; list->city.name[1] = '\0'; list->forw = list; list->back = list; return list; } /*************************************************** Insert a node in a sorted circularly doubly-linked list with one sentinel node return 1 - if duplicate return 0 - otherwise */ int insert(D_NODE *list, const CITY *data) { D_NODE *curr = list->forw; D_NODE *prev = list; D_NODE *pnew; int duplicate = 1; // search while (strcmp(data->name, curr->city.name) > 0) { prev = curr; curr = curr->forw; } if (strcmp(data->name, curr->city.name) ) { duplicate = 0; // not a duplicate pnew = (D_NODE *) malloc(sizeof (D_NODE)); if (!pnew) { printf("Fatal memory allocation error in insert! "); exit(3); } pnew->city = *data; pnew->forw = curr; pnew->back = prev; prev->forw = pnew; curr->back = pnew; } return duplicate; } /*************************************************** Traverses forward a circularly doubly-linked list with one sentinel node to print out the contents of each node */ void traverse_forw(D_NODE *list) { list = list->forw; // skip the dummy node while (list->city.name[0] != DUMMY_TRAILER) { printCity(&list->city); list = list->forw; } } /*************************************************** Traverses backward a circularly doubly-linked list with one sentinel node to print out the contents of each node */ void traverse_back(D_NODE *list) { list = list->back; // skip the dummy node while (list->city.name[0] != DUMMY_TRAILER) { printCity(&list->city); list = list->back; } } /* ================= Sample Output #1 ================= */ /* LIST contents (forwards): Cupertino 88 Los Angeles 87 Philadelphia 96 Phoenix 106 Reno 108 Tucson 107 LIST contents (backwards): Tucson 107 Reno 108 Phoenix 106 Philadelphia 96 Los Angeles 87 Cupertino 88 STACK contents from top to bottom: Tucson 107 Philadelphia 96 QUEUE contents from front to rear: Philadelphia 96 Tucson 107 */ /* ================= Sample Output #2 ================= */ /* LIST contents (forwards): Flagstaff 81 Philadelphia 96 Yreka 101 LIST contents (backwards): Yreka 101 Philadelphia 96 Flagstaff 81 Empty Stack! Empty Queue! */