Data structure (Python)
Trist1111
hw5.ziphw5/instructions.pdf
__MACOSX/hw5/._instructions.pdf
hw5/.DS_Store
__MACOSX/hw5/._.DS_Store
hw5/BonusHW_export (1).zip
type.h
/* type.h Defines the type to be stored in the data structure. These macros are for convenience to avoid having to search and replace/dup code when you want to build a structure of doubles as opposed to ints for example. */ #ifndef __TYPE_H #define __TYPE_H #define TASK_DESC_SIZE 128 struct Task { char description[TASK_DESC_SIZE]; /* description of the task */ int priority; /* task priority */ }; typedef struct Task Task; # ifndef TYPE # define TYPE Task # define TYPE_SIZE sizeof(Task) # endif /* function used to compare two TYPE values to each other */ int compare(TYPE left, TYPE right); #endif
toDoList.h
#ifndef __TODOLIST_H #define __TODOLIST_H #include "dynArray.h" TYPE createTask (int priority, char *desc); void saveList(DynArr *heap, FILE *filePtr); void loadList(DynArr *heap, FILE *filePtr); void printList(DynArr *heap); #endif
toDoList.c
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #include "toDoList.h" /* Create a task from the description and the priority param: priority priority of the task param: desc pointer to the description string pre: none post: none ret: a task with description and priority */ TYPE createTask (int priority, char *desc) { TYPE newTask; newTask.priority = priority; strcpy(newTask.description, desc); return newTask; } /* Save the list to a file param: heap pointer to the list param: filePtr pointer to the file to which the list is saved pre: The list is not empty post: The list is saved to the file in tab-delimited format. Each line in the file stores a task, starting with the task priority, followed by a tab character (\t), and the task description. The tasks are not necessarily stored in the file in priority order. */ void saveList(DynArr *heap, FILE *filePtr) { /* FIX ME */ } /* Load the list from a file param: heap pointer to the list param: filePtr pointer to the file pre: none post: The tasks are retrieved from the file and are added to the list. Refer to the saveList() function for the format of tasks in the file */ void loadList(DynArr *heap, FILE *filePtr) { /* FIX ME */ } /* Print the list param: heap pointer to the list pre: the list is not empty post: The tasks from the list are printed out in priority order. The tasks are not removed from the list. */ void printList(DynArr *heap) { /* FIX ME */ } /* Compare two tasks by priority param: left first task param: right second task pre: none post: none ret: -1 if priority of left < priority of right 1 if priority of left > priority of right 0 if priority of left = priority of right */ int compare(TYPE left, TYPE right) { if (left.priority < right.priority) return -1; else if (left.priority > right.priority) return 1; else return 0; }
todo.txt
0 take a nap 1 study heap-based priority queue 101 review trees for Midterm 2 3 do assignment 7
program_demo.txt
flip ~/cs261/as5/todo_list 605% ./prog ** TO-DO LIST APPLICATION ** Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program g Your to-do list is empty! Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program a Please enter the task description: do assignment 5 Please enter the task priority (0-999): 3 The task 'do assignment 5' has been added to your to-do list. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program a Please enter the task description: study heap-based priority queue Please enter the task priority (0-999): 1 The task 'study heap-based priority queue' has been added to your to-do list. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program a Please enter the task description: review trees for Midterm 2 Please enter the task priority (0-999): 101 The task 'review trees for Midterm 2' has been added to your to-do list. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program g Your first task is: study heap-based priority queue Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program a Please enter the task description: take a nap Please enter the task priority (0-999): 0 The task 'take a nap' has been added to your to-do list. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program s Please enter the filename: todo.txt The list has been saved into the file successfully. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program e Bye! ============ flip ~/cs261/as5/todo_list 613% ./prog ** TO-DO LIST APPLICATION ** Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program g Your to-do list is empty! Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program l Please enter the filename: todo.txt The list has been loaded from file successfully. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program g Your first task is: take a nap Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program r Your first task 'take a nap' has been removed from the list. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program p study heap-based priority queue do assignment 5 review trees for Midterm 2 Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program r Your first task 'study heap-based priority queue' has been removed from the list. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program r Your first task 'do assignment 5' has been removed from the list. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program r Your first task 'review trees for Midterm 2' has been removed from the list. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program r Your to-do list is empty! Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program e Bye!
Makefile
default: prog dynArray.o: dynArray.c dynArray.h type.h gcc -Wall -ansi -c dynArray.c toDoList.o: toDoList.c toDoList.h type.h gcc -Wall -ansi -c toDoList.c prog: dynArray.o toDoList.o main.c gcc -Wall -ansi -o prog dynArray.o toDoList.o main.c clean: rm dynArray.o rm toDoList.o cleanall: clean rm prog
main2.c
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #include "toDoList.h" int main2 (int argc, const char * argv[]) { TYPE task1, task2, task3, task4, task5, task6, task7, task8, task9, task10; DynArr mainList; int i; initDynArr(&mainList, 10); /* create tasks */ task1 = createTask(9, "task 1"); task2 = createTask(3, "task 2"); task3 = createTask(2, "task 3"); task4 = createTask(4, "task 4"); task5 = createTask(5, "task 5"); task6 = createTask(7, "task 6"); task7 = createTask(8, "task 7"); task8 = createTask(6, "task 8"); task9 = createTask(1, "task 9"); task10 = createTask(0, "task 10"); /* add tasks to the dynamic array */ addDynArr(&mainList, task1); addDynArr(&mainList, task2); addDynArr(&mainList, task3); addDynArr(&mainList, task4); addDynArr(&mainList, task5); addDynArr(&mainList, task6); addDynArr(&mainList, task7); addDynArr(&mainList, task8); addDynArr(&mainList, task9); addDynArr(&mainList, task10); /* sort tasks */ sortHeap(&mainList); /* print sorted tasks from the dynamic array */ for (i = 0; i < mainList.size; i++) { printf("%d\n", mainList.data[i].priority); } return 0; }
main.c
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #include "toDoList.h" int main (int argc, const char * argv[]) { TYPE newTask, firstTask; char desc[TASK_DESC_SIZE], filename[50], *nlptr; int priority; char cmd = ' '; FILE *filePointer; DynArr mainList; initDynArr(&mainList, 10); printf("\n\n** TO-DO LIST APPLICATION **\n\n"); do { printf("Press:\n" "'l' to load to-do list from a file\n" "'s' to save to-do list to a file\n" "'a' to add a new task\n" "'g' to get the first task\n" "'r' to remove the first task\n" "'p' to print the list\n" "'e' to exit the program\n" ); /* get input command (from the keyboard) */ cmd = getchar(); /* clear the trailing newline character */ while (getchar() != '\n'); switch (cmd) { case 'a': /* add new task */ printf("Please enter the task description: "); /* get task description from user input (from keyboard) */ if (fgets(desc, sizeof(desc), stdin) != NULL) { /* remove trailing newline character */ nlptr = strchr(desc, '\n'); if (nlptr) *nlptr = '\0'; } /* get task priority from user input (from keyboard) */ do { printf("Please enter the task priority (0-999): "); scanf("%d", &priority); } while(!(priority >= 0 && priority <= 999)); /* clear the trailing newline character */ while (getchar() != '\n'); /* create task and add the task to the heap */ newTask = createTask(priority, desc); addHeap(&mainList, newTask); printf("The task '%s' has been added to your to-do list.\n\n", desc); break; case 'g': /* get the first task */ if (sizeDynArr(&mainList) > 0) { firstTask = getMinHeap(&mainList); printf("Your first task is: %s\n\n", firstTask.description); } else printf("Your to-do list is empty!\n\n"); break; case 'r': /* remove the first task */ if (sizeDynArr(&mainList) > 0) { firstTask = getMinHeap(&mainList); removeMinHeap(&mainList); printf("Your first task '%s' has been removed from the list.\n\n", firstTask.description); } else printf("Your to-do list is empty!\n\n"); break; case 'p': /* print the list */ if (sizeDynArr(&mainList) > 0) { printList(&mainList); } else printf("Your to-do list is empty!\n\n"); break; case 's': /* save the list to file */ if (sizeDynArr(&mainList) > 0) { /* get filename from user input (from keyboard) */ printf("Please enter the filename: "); if (fgets(filename, sizeof(filename), stdin) != NULL) { /* remove trailing newline character */ nlptr = strchr(filename, '\n'); if (nlptr) *nlptr = '\0'; } /* open the file */ filePointer = fopen(filename, "w"); if (filePointer == NULL) { fprintf(stderr, "Cannot open %s\n", filename); break; } /* save the list to the file */ saveList(&mainList, filePointer); /* close the file */ fclose(filePointer); printf("The list has been saved into the file successfully.\n\n"); } else printf("Your to-do list is empty!\n\n"); break; case 'l': /* load the list from the file */ printf("Please enter the filename: "); /* get filename from user input (from keyboard) */ if (fgets(filename, sizeof(filename), stdin) != NULL) { /* remove trailing newline character */ nlptr = strchr(filename, '\n'); if (nlptr) *nlptr = '\0'; } /* open the file */ filePointer = fopen(filename, "r"); if (filePointer == NULL) { fprintf(stderr, "Cannot open %s\n", filename); break; } /* load the list from the file */ loadList(&mainList, filePointer); /* close the file */ fclose(filePointer); printf("The list has been loaded from file successfully.\n\n"); break; case 'e': /* exit the program */ printf("Bye!\n\n"); break; default: printf("What is your command anyway?\n\n" ); break; } } while(cmd != 'e'); /* free the list */ freeDynArr(&mainList); return 0; }
dynArray.h
/* dynArray.h : Dynamic Array implementation. */ #ifndef DYNAMIC_ARRAY_INCLUDED #define DYNAMIC_ARRAY_INCLUDED 1 #include "type.h" struct DynArr { TYPE *data; /* pointer to the data array */ int size; /* Number of elements in the array */ int capacity; /* capacity ofthe array */ }; typedef struct DynArr DynArr; /* Dynamic Array Functions */ void initDynArr(DynArr *v, int capacity); DynArr *newDynArr(int cap); void freeDynArr(DynArr *v); void deleteDynArr(DynArr *v); void _dynArrSetCapacity(DynArr *v, int newCap); int sizeDynArr(DynArr *v); void addDynArr(DynArr *v, TYPE val); TYPE getDynArr(DynArr *v, int pos); void putDynArr(DynArr *v, int pos, TYPE val); void swapDynArr(DynArr *v, int i, int j); void removeAtDynArr(DynArr *v, int idx); int isEmptyDynArr(DynArr *v); void copyDynArr(DynArr *source, DynArr *destination); /* Heap-based Priority Queue Interface */ TYPE getMinHeap(DynArr *heap); void addHeap(DynArr *heap, TYPE node); void removeMinHeap(DynArr *heap); void sortHeap(DynArr *heap); #endif
dynArray.c
/* dynArray.c: Dynamic Array implementation. */ #include <assert.h> #include <stdlib.h> #include "dynArray.h" /* ************************************************************************ Dynamic Array Functions ************************************************************************ */ /* Initialize (including allocation of data array) dynamic array. param: v pointer to the dynamic array param: cap capacity of the dynamic array pre: v is not null post: internal data array can hold cap elements post: v->data is not null */ void initDynArr(DynArr *v, int capacity) { v->data = (TYPE *) malloc(sizeof(TYPE) * capacity); assert(v->data != 0); v->size = 0; v->capacity = capacity; } /* Allocate and initialize dynamic array. param: cap desired capacity for the dyn array pre: none post: none ret: a non-null pointer to a dynArr of cap capacity and 0 elements in it. */ DynArr* newDynArr(int cap) { DynArr *r = (DynArr *)malloc(sizeof( DynArr)); assert(r != 0); initDynArr(r,cap); return r; } /* Deallocate data array in dynamic array. param: v pointer to the dynamic array pre: none post: d.data points to null post: size and capacity are 0 post: the memory used by v->data is freed */ void freeDynArr(DynArr *v) { if(v->data != 0) { free(v->data); /* free the space on the heap */ v->data = 0; /* make it point to null */ } v->size = 0; v->capacity = 0; } /* Deallocate data array and the dynamic array ure. param: v pointer to the dynamic array pre: none post: the memory used by v->data is freed post: the memory used by d is freed */ void deleteDynArr(DynArr *v) { freeDynArr(v); free(v); } /* Resizes the underlying array to be the size cap param: v pointer to the dynamic array param: cap the new desired capacity pre: v is not null post: v has capacity newCap */ void _dynArrSetCapacity(DynArr *v, int newCap) { int i; /* Create a new underlying array */ TYPE *newData = (TYPE*)malloc(sizeof(TYPE)*newCap); assert(newData != 0); /* copy elements to new data array */ for(i = 0; i < v->size; i++) newData[i] = v->data[i]; /* Delete the old underlying array */ freeDynArr(v); /* update capacity and size and data */ v->data = newData; v->capacity = newCap; v->size = i; } /* Get the size of the dynamic array param: v pointer to the dynamic array pre: v is not null post: none ret: the size of the dynamic array */ int sizeDynArr(DynArr *v) { return v->size; } /* Adds an element to the end of the dynamic array param: v pointer to the dynamic array param: val the value to add to the end of the dynamic array pre: the dynArry is not null post: size increases by 1 post: if reached capacity, capacity is doubled post: val is in the last utilized position in the array */ void addDynArr(DynArr *v, TYPE val) { /* Check to see if a resize is necessary */ if(v->size >= v->capacity) _dynArrSetCapacity(v, 2 * v->capacity); v->data[v->size] = val; v->size++; } /* Get an element from the dynamic array from a specified position param: v pointer to the dynamic array param: pos integer index to get the element from pre: v is not null pre: v is not empty pre: pos < size of the dyn array and >= 0 post: no changes to the dyn Array ret: value stored at index pos */ TYPE getDynArr(DynArr *v, int pos) { assert(pos < v->size); assert(pos >= 0); return v->data[pos]; } /* Put an item into the dynamic array at the specified location, overwriting the element that was there param: v pointer to the dynamic array param: pos the index to put the value into param: val the value to insert pre: v is not null pre: v is not empty pre: pos >= 0 and pos < size of the array post: index pos contains new value, val */ void putDynArr(DynArr *v, int pos, TYPE val) { assert(pos < v->size); v->data[pos] = val; } /* Swap two specified elements in the dynamic array param: v pointer to the dynamic array param: i,j the elements to be swapped pre: v is not null pre: v is not empty pre: i, j >= 0 and i,j < size of the dynamic array post: index i now holds the value at j and index j now holds the value at i */ void swapDynArr(DynArr *v, int i, int j) { TYPE temp; assert(i < v->size); assert(j < v->size); temp = v->data[i]; v->data[i] = v->data[j]; v->data[j] = temp; } /* Remove the element at the specified location from the array, shifts other elements back one to fill the gap param: v pointer to the dynamic array param: idx location of element to remove pre: v is not null pre: v is not empty pre: idx < size and idx >= 0 post: the element at idx is removed post: the elements past idx are moved back one */ void removeAtDynArr(DynArr *v, int idx) { int i; for(i = idx; i < v->size-1; ++i) v->data[i] = v->data[i+1]; if(idx >= 0 && idx < v->size) --v->size; } /* Copy elements from a dynamic array to another dynamic array param: source pointer to the source dynamic array param: destination pointer to the destination dynamic array pre: s is not null and s is not empty post: destination is initialized post: the elements from source are copied to destination */ void copyDynArr(DynArr *source, DynArr *destination) { int i; assert(source->size > 0); initDynArr(destination, source->capacity); /* copy elements to destination array */ for(i = 0; i < source->size; i++) destination->data[i] = source->data[i]; destination->size = source->size; } /* ************************************************************************ Heap-based Priority Queue Implementation ************************************************************************ */ /* internal function prototypes */ int _smallerIndexHeap(DynArr *heap, int i, int j); void _adjustHeap(DynArr *heap, int max, int pos); /* Get the index of the smaller node between two nodes in a heap param: heap pointer to the heap param: i index of one node param: j index of other node pre: i < size and j < size ret: the index of the smaller node */ int _smallerIndexHeap(DynArr *heap, int i, int j) { assert(i < sizeDynArr(heap)); assert(j < sizeDynArr(heap)); if (compare(getDynArr(heap, i), getDynArr(heap, j)) == -1) return i; else return j; } /* Get the first node, which has the max priority (i.e., min value), from the heap param: heap pointer to the heap pre: heap is not empty ret: value of first node */ TYPE getMinHeap(DynArr *heap) { /* FIXME */ TYPE temp; return temp; } /* Add a node to the heap param: heap pointer to the heap param: node node to be added to the heap pre: heap is not null post: node is added to the heap */ void addHeap(DynArr *heap, TYPE node) { /* FIXME */ } /* Adjust heap to maintain heap property param: heap pointer to the heap param: max max index of the heap nodes in the dynamic array param: pos position index where the adjustment starts pre: none post: heap property is maintained for nodes from index pos to index max */ void _adjustHeap(DynArr *heap, int max, int pos) { /* FIXME */ } /* Remove the first node, which has the max priority (i.e., min value), from the heap param: heap pointer to the heap pre: heap is not empty post: the first node is removed from the heap */ void removeMinHeap(DynArr *heap) { /* FIXME */ } /* builds a heap from an arbitrary dynArray param: v dynamicArray pre: v is not empty post: v is a proper heap */ void _buildHeap(DynArr *heap) { /* FIXME */ } /* In-place sort of the heap param: heap pointer to the heap pre: heap is not empty post: the dynArr is in reverse sorted order */ void sortHeap(DynArr *heap) { /*FIXME*/ }
__MACOSX/hw5/._BonusHW_export (1).zip
__MACOSX/hw5/._BonusHW_export
hw5/BonusHW_export /type.h
/* type.h Defines the type to be stored in the data structure. These macros are for convenience to avoid having to search and replace/dup code when you want to build a structure of doubles as opposed to ints for example. */ #ifndef __TYPE_H #define __TYPE_H #define TASK_DESC_SIZE 128 struct Task { char description[TASK_DESC_SIZE]; /* description of the task */ int priority; /* task priority */ }; typedef struct Task Task; # ifndef TYPE # define TYPE Task # define TYPE_SIZE sizeof(Task) # endif /* function used to compare two TYPE values to each other */ int compare(TYPE left, TYPE right); #endif
__MACOSX/hw5/BonusHW_export /._type.h
hw5/BonusHW_export /toDoList.h
#ifndef __TODOLIST_H #define __TODOLIST_H #include "dynArray.h" TYPE createTask (int priority, char *desc); void saveList(DynArr *heap, FILE *filePtr); void loadList(DynArr *heap, FILE *filePtr); void printList(DynArr *heap); #endif
__MACOSX/hw5/BonusHW_export /._toDoList.h
hw5/BonusHW_export /program_demo.txt
flip ~/cs261/as5/todo_list 605% ./prog ** TO-DO LIST APPLICATION ** Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program g Your to-do list is empty! Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program a Please enter the task description: do assignment 5 Please enter the task priority (0-999): 3 The task 'do assignment 5' has been added to your to-do list. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program a Please enter the task description: study heap-based priority queue Please enter the task priority (0-999): 1 The task 'study heap-based priority queue' has been added to your to-do list. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program a Please enter the task description: review trees for Midterm 2 Please enter the task priority (0-999): 101 The task 'review trees for Midterm 2' has been added to your to-do list. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program g Your first task is: study heap-based priority queue Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program a Please enter the task description: take a nap Please enter the task priority (0-999): 0 The task 'take a nap' has been added to your to-do list. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program s Please enter the filename: todo.txt The list has been saved into the file successfully. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program e Bye! ============ flip ~/cs261/as5/todo_list 613% ./prog ** TO-DO LIST APPLICATION ** Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program g Your to-do list is empty! Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program l Please enter the filename: todo.txt The list has been loaded from file successfully. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program g Your first task is: take a nap Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program r Your first task 'take a nap' has been removed from the list. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program p study heap-based priority queue do assignment 5 review trees for Midterm 2 Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program r Your first task 'study heap-based priority queue' has been removed from the list. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program r Your first task 'do assignment 5' has been removed from the list. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program r Your first task 'review trees for Midterm 2' has been removed from the list. Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program r Your to-do list is empty! Press: 'l' to load to-do list from a file 's' to save to-do list to a file 'a' to add a new task 'g' to get the first task 'r' to remove the first task 'p' to print the list 'e' to exit the program e Bye!
__MACOSX/hw5/BonusHW_export /._program_demo.txt
hw5/BonusHW_export /todo.txt
0 take a nap 1 study heap-based priority queue 101 review trees for Midterm 2 3 do assignment 7
__MACOSX/hw5/BonusHW_export /._todo.txt
hw5/BonusHW_export /dynArray.c
/* dynArray.c: Dynamic Array implementation. */ #include <assert.h> #include <stdlib.h> #include "dynArray.h" /* ************************************************************************ Dynamic Array Functions ************************************************************************ */ /* Initialize (including allocation of data array) dynamic array. param: v pointer to the dynamic array param: cap capacity of the dynamic array pre: v is not null post: internal data array can hold cap elements post: v->data is not null */ void initDynArr(DynArr *v, int capacity) { v->data = (TYPE *) malloc(sizeof(TYPE) * capacity); assert(v->data != 0); v->size = 0; v->capacity = capacity; } /* Allocate and initialize dynamic array. param: cap desired capacity for the dyn array pre: none post: none ret: a non-null pointer to a dynArr of cap capacity and 0 elements in it. */ DynArr* newDynArr(int cap) { DynArr *r = (DynArr *)malloc(sizeof( DynArr)); assert(r != 0); initDynArr(r,cap); return r; } /* Deallocate data array in dynamic array. param: v pointer to the dynamic array pre: none post: d.data points to null post: size and capacity are 0 post: the memory used by v->data is freed */ void freeDynArr(DynArr *v) { if(v->data != 0) { free(v->data); /* free the space on the heap */ v->data = 0; /* make it point to null */ } v->size = 0; v->capacity = 0; } /* Deallocate data array and the dynamic array ure. param: v pointer to the dynamic array pre: none post: the memory used by v->data is freed post: the memory used by d is freed */ void deleteDynArr(DynArr *v) { freeDynArr(v); free(v); } /* Resizes the underlying array to be the size cap param: v pointer to the dynamic array param: cap the new desired capacity pre: v is not null post: v has capacity newCap */ void _dynArrSetCapacity(DynArr *v, int newCap) { int i; /* Create a new underlying array */ TYPE *newData = (TYPE*)malloc(sizeof(TYPE)*newCap); assert(newData != 0); /* copy elements to new data array */ for(i = 0; i < v->size; i++) newData[i] = v->data[i]; /* Delete the old underlying array */ freeDynArr(v); /* update capacity and size and data */ v->data = newData; v->capacity = newCap; v->size = i; } /* Get the size of the dynamic array param: v pointer to the dynamic array pre: v is not null post: none ret: the size of the dynamic array */ int sizeDynArr(DynArr *v) { return v->size; } /* Adds an element to the end of the dynamic array param: v pointer to the dynamic array param: val the value to add to the end of the dynamic array pre: the dynArry is not null post: size increases by 1 post: if reached capacity, capacity is doubled post: val is in the last utilized position in the array */ void addDynArr(DynArr *v, TYPE val) { /* Check to see if a resize is necessary */ if(v->size >= v->capacity) _dynArrSetCapacity(v, 2 * v->capacity); v->data[v->size] = val; v->size++; } /* Get an element from the dynamic array from a specified position param: v pointer to the dynamic array param: pos integer index to get the element from pre: v is not null pre: v is not empty pre: pos < size of the dyn array and >= 0 post: no changes to the dyn Array ret: value stored at index pos */ TYPE getDynArr(DynArr *v, int pos) { assert(pos < v->size); assert(pos >= 0); return v->data[pos]; } /* Put an item into the dynamic array at the specified location, overwriting the element that was there param: v pointer to the dynamic array param: pos the index to put the value into param: val the value to insert pre: v is not null pre: v is not empty pre: pos >= 0 and pos < size of the array post: index pos contains new value, val */ void putDynArr(DynArr *v, int pos, TYPE val) { assert(pos < v->size); v->data[pos] = val; } /* Swap two specified elements in the dynamic array param: v pointer to the dynamic array param: i,j the elements to be swapped pre: v is not null pre: v is not empty pre: i, j >= 0 and i,j < size of the dynamic array post: index i now holds the value at j and index j now holds the value at i */ void swapDynArr(DynArr *v, int i, int j) { TYPE temp; assert(i < v->size); assert(j < v->size); temp = v->data[i]; v->data[i] = v->data[j]; v->data[j] = temp; } /* Remove the element at the specified location from the array, shifts other elements back one to fill the gap param: v pointer to the dynamic array param: idx location of element to remove pre: v is not null pre: v is not empty pre: idx < size and idx >= 0 post: the element at idx is removed post: the elements past idx are moved back one */ void removeAtDynArr(DynArr *v, int idx) { int i; for(i = idx; i < v->size-1; ++i) v->data[i] = v->data[i+1]; if(idx >= 0 && idx < v->size) --v->size; } /* Copy elements from a dynamic array to another dynamic array param: source pointer to the source dynamic array param: destination pointer to the destination dynamic array pre: s is not null and s is not empty post: destination is initialized post: the elements from source are copied to destination */ void copyDynArr(DynArr *source, DynArr *destination) { int i; assert(source->size > 0); initDynArr(destination, source->capacity); /* copy elements to destination array */ for(i = 0; i < source->size; i++) destination->data[i] = source->data[i]; destination->size = source->size; } /* ************************************************************************ Heap-based Priority Queue Implementation ************************************************************************ */ /* internal function prototypes */ int _smallerIndexHeap(DynArr *heap, int i, int j); void _adjustHeap(DynArr *heap, int max, int pos); /* Get the index of the smaller node between two nodes in a heap param: heap pointer to the heap param: i index of one node param: j index of other node pre: i < size and j < size ret: the index of the smaller node */ int _smallerIndexHeap(DynArr *heap, int i, int j) { assert(i < sizeDynArr(heap)); assert(j < sizeDynArr(heap)); if (compare(getDynArr(heap, i), getDynArr(heap, j)) == -1) return i; else return j; } /* Get the first node, which has the max priority (i.e., min value), from the heap param: heap pointer to the heap pre: heap is not empty ret: value of first node */ TYPE getMinHeap(DynArr *heap) { /* FIXME */ TYPE temp; return temp; } /* Add a node to the heap param: heap pointer to the heap param: node node to be added to the heap pre: heap is not null post: node is added to the heap */ void addHeap(DynArr *heap, TYPE node) { /* FIXME */ } /* Adjust heap to maintain heap property param: heap pointer to the heap param: max max index of the heap nodes in the dynamic array param: pos position index where the adjustment starts pre: none post: heap property is maintained for nodes from index pos to index max */ void _adjustHeap(DynArr *heap, int max, int pos) { /* FIXME */ } /* Remove the first node, which has the max priority (i.e., min value), from the heap param: heap pointer to the heap pre: heap is not empty post: the first node is removed from the heap */ void removeMinHeap(DynArr *heap) { /* FIXME */ } /* builds a heap from an arbitrary dynArray param: v dynamicArray pre: v is not empty post: v is a proper heap */ void _buildHeap(DynArr *heap) { /* FIXME */ } /* In-place sort of the heap param: heap pointer to the heap pre: heap is not empty post: the dynArr is in reverse sorted order */ void sortHeap(DynArr *heap) { /*FIXME*/ }
__MACOSX/hw5/BonusHW_export /._dynArray.c
hw5/BonusHW_export /Makefile
default: prog dynArray.o: dynArray.c dynArray.h type.h gcc -Wall -ansi -c dynArray.c toDoList.o: toDoList.c toDoList.h type.h gcc -Wall -ansi -c toDoList.c prog: dynArray.o toDoList.o main.c gcc -Wall -ansi -o prog dynArray.o toDoList.o main.c clean: rm dynArray.o rm toDoList.o cleanall: clean rm prog
__MACOSX/hw5/BonusHW_export /._Makefile
hw5/BonusHW_export /main2.c
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #include "toDoList.h" int main2 (int argc, const char * argv[]) { TYPE task1, task2, task3, task4, task5, task6, task7, task8, task9, task10; DynArr mainList; int i; initDynArr(&mainList, 10); /* create tasks */ task1 = createTask(9, "task 1"); task2 = createTask(3, "task 2"); task3 = createTask(2, "task 3"); task4 = createTask(4, "task 4"); task5 = createTask(5, "task 5"); task6 = createTask(7, "task 6"); task7 = createTask(8, "task 7"); task8 = createTask(6, "task 8"); task9 = createTask(1, "task 9"); task10 = createTask(0, "task 10"); /* add tasks to the dynamic array */ addDynArr(&mainList, task1); addDynArr(&mainList, task2); addDynArr(&mainList, task3); addDynArr(&mainList, task4); addDynArr(&mainList, task5); addDynArr(&mainList, task6); addDynArr(&mainList, task7); addDynArr(&mainList, task8); addDynArr(&mainList, task9); addDynArr(&mainList, task10); /* sort tasks */ sortHeap(&mainList); /* print sorted tasks from the dynamic array */ for (i = 0; i < mainList.size; i++) { printf("%d\n", mainList.data[i].priority); } return 0; }
__MACOSX/hw5/BonusHW_export /._main2.c
hw5/BonusHW_export /main.c
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #include "toDoList.h" int main (int argc, const char * argv[]) { TYPE newTask, firstTask; char desc[TASK_DESC_SIZE], filename[50], *nlptr; int priority; char cmd = ' '; FILE *filePointer; DynArr mainList; initDynArr(&mainList, 10); printf("\n\n** TO-DO LIST APPLICATION **\n\n"); do { printf("Press:\n" "'l' to load to-do list from a file\n" "'s' to save to-do list to a file\n" "'a' to add a new task\n" "'g' to get the first task\n" "'r' to remove the first task\n" "'p' to print the list\n" "'e' to exit the program\n" ); /* get input command (from the keyboard) */ cmd = getchar(); /* clear the trailing newline character */ while (getchar() != '\n'); switch (cmd) { case 'a': /* add new task */ printf("Please enter the task description: "); /* get task description from user input (from keyboard) */ if (fgets(desc, sizeof(desc), stdin) != NULL) { /* remove trailing newline character */ nlptr = strchr(desc, '\n'); if (nlptr) *nlptr = '\0'; } /* get task priority from user input (from keyboard) */ do { printf("Please enter the task priority (0-999): "); scanf("%d", &priority); } while(!(priority >= 0 && priority <= 999)); /* clear the trailing newline character */ while (getchar() != '\n'); /* create task and add the task to the heap */ newTask = createTask(priority, desc); addHeap(&mainList, newTask); printf("The task '%s' has been added to your to-do list.\n\n", desc); break; case 'g': /* get the first task */ if (sizeDynArr(&mainList) > 0) { firstTask = getMinHeap(&mainList); printf("Your first task is: %s\n\n", firstTask.description); } else printf("Your to-do list is empty!\n\n"); break; case 'r': /* remove the first task */ if (sizeDynArr(&mainList) > 0) { firstTask = getMinHeap(&mainList); removeMinHeap(&mainList); printf("Your first task '%s' has been removed from the list.\n\n", firstTask.description); } else printf("Your to-do list is empty!\n\n"); break; case 'p': /* print the list */ if (sizeDynArr(&mainList) > 0) { printList(&mainList); } else printf("Your to-do list is empty!\n\n"); break; case 's': /* save the list to file */ if (sizeDynArr(&mainList) > 0) { /* get filename from user input (from keyboard) */ printf("Please enter the filename: "); if (fgets(filename, sizeof(filename), stdin) != NULL) { /* remove trailing newline character */ nlptr = strchr(filename, '\n'); if (nlptr) *nlptr = '\0'; } /* open the file */ filePointer = fopen(filename, "w"); if (filePointer == NULL) { fprintf(stderr, "Cannot open %s\n", filename); break; } /* save the list to the file */ saveList(&mainList, filePointer); /* close the file */ fclose(filePointer); printf("The list has been saved into the file successfully.\n\n"); } else printf("Your to-do list is empty!\n\n"); break; case 'l': /* load the list from the file */ printf("Please enter the filename: "); /* get filename from user input (from keyboard) */ if (fgets(filename, sizeof(filename), stdin) != NULL) { /* remove trailing newline character */ nlptr = strchr(filename, '\n'); if (nlptr) *nlptr = '\0'; } /* open the file */ filePointer = fopen(filename, "r"); if (filePointer == NULL) { fprintf(stderr, "Cannot open %s\n", filename); break; } /* load the list from the file */ loadList(&mainList, filePointer); /* close the file */ fclose(filePointer); printf("The list has been loaded from file successfully.\n\n"); break; case 'e': /* exit the program */ printf("Bye!\n\n"); break; default: printf("What is your command anyway?\n\n" ); break; } } while(cmd != 'e'); /* free the list */ freeDynArr(&mainList); return 0; }
__MACOSX/hw5/BonusHW_export /._main.c
hw5/BonusHW_export /dynArray.h
/* dynArray.h : Dynamic Array implementation. */ #ifndef DYNAMIC_ARRAY_INCLUDED #define DYNAMIC_ARRAY_INCLUDED 1 #include "type.h" struct DynArr { TYPE *data; /* pointer to the data array */ int size; /* Number of elements in the array */ int capacity; /* capacity ofthe array */ }; typedef struct DynArr DynArr; /* Dynamic Array Functions */ void initDynArr(DynArr *v, int capacity); DynArr *newDynArr(int cap); void freeDynArr(DynArr *v); void deleteDynArr(DynArr *v); void _dynArrSetCapacity(DynArr *v, int newCap); int sizeDynArr(DynArr *v); void addDynArr(DynArr *v, TYPE val); TYPE getDynArr(DynArr *v, int pos); void putDynArr(DynArr *v, int pos, TYPE val); void swapDynArr(DynArr *v, int i, int j); void removeAtDynArr(DynArr *v, int idx); int isEmptyDynArr(DynArr *v); void copyDynArr(DynArr *source, DynArr *destination); /* Heap-based Priority Queue Interface */ TYPE getMinHeap(DynArr *heap); void addHeap(DynArr *heap, TYPE node); void removeMinHeap(DynArr *heap); void sortHeap(DynArr *heap); #endif
__MACOSX/hw5/BonusHW_export /._dynArray.h
hw5/BonusHW_export /toDoList.c
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #include "toDoList.h" /* Create a task from the description and the priority param: priority priority of the task param: desc pointer to the description string pre: none post: none ret: a task with description and priority */ TYPE createTask (int priority, char *desc) { TYPE newTask; newTask.priority = priority; strcpy(newTask.description, desc); return newTask; } /* Save the list to a file param: heap pointer to the list param: filePtr pointer to the file to which the list is saved pre: The list is not empty post: The list is saved to the file in tab-delimited format. Each line in the file stores a task, starting with the task priority, followed by a tab character (\t), and the task description. The tasks are not necessarily stored in the file in priority order. */ void saveList(DynArr *heap, FILE *filePtr) { /* FIX ME */ } /* Load the list from a file param: heap pointer to the list param: filePtr pointer to the file pre: none post: The tasks are retrieved from the file and are added to the list. Refer to the saveList() function for the format of tasks in the file */ void loadList(DynArr *heap, FILE *filePtr) { /* FIX ME */ } /* Print the list param: heap pointer to the list pre: the list is not empty post: The tasks from the list are printed out in priority order. The tasks are not removed from the list. */ void printList(DynArr *heap) { /* FIX ME */ } /* Compare two tasks by priority param: left first task param: right second task pre: none post: none ret: -1 if priority of left < priority of right 1 if priority of left > priority of right 0 if priority of left = priority of right */ int compare(TYPE left, TYPE right) { if (left.priority < right.priority) return -1; else if (left.priority > right.priority) return 1; else return 0; }
