CIS 20 Fall 2019 – Programming Assingnment 2 – Data Structures
[ad_1]
CIS 20 Fall 2019 – Programming Assingnment 2 – Data Structures
Instructions
● Read every step entirely before beginning.
● This assignment is due Monday, Nov 11 11:59 PM.
● Ask for questions on our CIS 20 team Slack http://laneycis20.slack.com
● You will be able to see your autograder results via http://gradescope.com
● The grace period will last 72 hours after results are released on http://gradescope.com
Goals
❖ Become familiar with array allocation, initialization, and use in C.
❖ Implement Array-based Stack, Array-based Circular Queue, and Doubly Linked List, and Linked List Queue.
Clone the Assignment
Use this link to accept your assignment.
Clone the assignment into your pa directory.
Relevant Readings
C Programming, A Modern Approach:
❖ Chp. 8 – Arrays
❖ Chp. 16 – Structures, Unions, Enumerations
❖ Chp. 17 – Dynamic Memory and Linked Lists
Integer Singly Linked List
Purpose File
Header file containing the interface for your singly linked list data structure. Do not modify this file. src/long_list.h
C file containing the implementation for your singly linked list. src/long_list.c
Tests that validate the data structure adheres to the interface.
You must write thorough tests for all your data structures.
Here is an example of what I am expecting
tests/testLongList.cpp
You will create a singly linked list that is only able to store long data. Remember that a singly linked list only contains a pointer to the next item in the list. Storing only long data simplifies the implementation as well.
Each linked list node will be represented by the long_list_node_t type in long_list.h:
typedef struct long_list_node {
struct long_list_node* next; // pointer to next item
long data; // single long item
} long_list_node_t;
You must use malloc to allocate space for each node in the list. You must #include to use malloc.
Implement each of the following function defined by the long_list.h interface:
long_list.c
Header Description
long_list_node_t *long_list_init() Initializes the linked list by creating a head node.
void long_list_add(
long_list_node_t *head,
long item) Adds an item to the linked list by traversing the list to create the next node. Updates the last node in the list to point to the newly created node.
long long_list_get(
long_list_node_t *head,
int index) Gets an item from the list at the given index by traversing the list.
int long_list_set(
long_list_node_t *head,
int index,
long item) Sets an item from the list at the given index by traversing the list.
Returns 1 if successful. Returns 0 if the index is not within bounds of the list.
void long_list_remove(
long_list_node_t *head,
int index) Removes an item from the list at the given index by traversing the list. Links the previous node to the next node to avoid leaving a gap in the list.
int long_list_contains(
long_list_node_t *head,
long item) Searches for the given item by traversing the list.
Returns 1 if the item exists in the list. Returns 0 if the item does not exist in the list.
int long_list_size(
long_list_node_t *head) Returns the size of the given list by traversing the list.
void long_list_destroy(
long_list_node_t *head) Frees every node in the list by traversing the list.
Array-Based Stack
Purpose File
Header file containing the interface for your stack data structure. Do not modify this file. src/istack.h
C file containing the implementation for your stack. src/istack.c
Tests that validate the data structure adheres to the interface. tests/testIStack.cpp
Using an array as your data storage mechanism. Implement a stack. You must allocate and realloc your stack using malloc and realloc. You must #include to use malloc and realloc.
Your stack will be represented by the istack_t type that is defined in istack.h:
typedef struct {
int capacity; // maximum capacity of data
int size; // the current number of items in data
int index; // index to the top of data
long *data; // array of longs – stores all stack data
} istack_t;
You must use malloc and realloc to initialize and resize the data field. You must #include to use malloc and realloc.
Implement each of the following functions defined by the istack.h interface:
istack.c
Header Description
void istack_init(istack_t *stack) Initializes the stack by allocating an initial data capacity of 8.
Initialize each field to following:
● capacity: 8
● size: 0
● index: -1
● data: malloc(8 * sizeof(long))
void istack_push(
istack_t *stack,
long item) Adds one item to the top of the stack. Advances the index by one before assigning a value to the stack. Invokes ensure_capcity implicitly to ensure that the stack is sufficiently large to contain an additional item.
long istack_pop(istack_t *stack) Removes one item from the top of the stack. Reduces the index by one.
long istack_peek(istack_t *stack) Returns the value at the top index of the stack but does not remove it from the stack.
int istack_ensure_capacity(
istack_t *stack) Ensures that the stack has capacity for another item. If the stack does not have sufficient capacity for another item, it will double the capacity of the stack by invoking realloc on the data field. No data can be lost by invoking this function.
Returns 1 if capacity is sufficient. Returns 0 is realloc fails.
void istack_destroy(istack_t *stack) Frees the data field and the stack struct.
Do NOT free the stack pointer. Free the data pointer.
Set each field to the following:
● capacity: 0
● size: 0
● index: -1
● data: NULL (after freeing)
Array-Based Circular Queue
Purpose File
Header file containing the interface for your queue data structure. Do not modify this file. src/iqueue.h
C file containing the implementation for your queue. src/iqueue.c
Tests that validate the data structure adheres to the interface. tests/testIQueue.cpp
Using an array as your data storage mechanism. Implement a circular queue. You must allocate and realloc your queue using malloc and realloc. You must #include to use malloc and realloc.
Your stack will be represented by the iqueue_t type that is defined in istack.h:
typedef struct {
int capacity; // maximum capacity of data
int size; // the current number of items in data
int front; // index of the front of the queue
int back; // index of the back of the queue
long *data; // array of longs – stores all stack data
} iqueue_t;
You must use malloc and realloc to initialize and resize the data field.
Implement each of the following functions defined by the iqueue.h interface:
iqueue.c
Header Description
void iqueue_init(iqueue_t *queue) Initializes the stack by allocating an initial data capacity of 8.
Initialize each field to following:
● capacity: 8
● size: 0
● front: -1
● back: -1
● data: malloc(8 * sizeof(long))
void iqueue_enqueue(
iqueue_t *queue,
long item) Adds one item to the back of the queue. Increments back index before setting item in the array storage.
long iqueue_dequeue(iqueue_t *queue) Removes one item from the front of the queue. Increments front index after removing item from the array storage.
long iqueue_peek(iqueue_t *queue) Returns the value at the front of the queue without removing it from the queue.
int iqueue_ensure_capacity(
iqueue_t *queue) Ensures that the queue has capacity for another item. If the queue does not have sufficient capacity for another item, it will double the capacity of the queue by invoking realloc on the data field. No data can be lost by invoking this function.
Returns 1 if capacity is sufficient. Returns 0 is realloc fails.
void iqueue_destroy(iqueue_t *queue) Frees the data field and the queue struct.
Do NOT free the queue pointer. Free the data pointer.
Set each field to the following:
● capacity: 0
● size: 0
● front: -1
● back: -1
● data: NULL (after freeing)
Generic Doubly Linked List
Purpose File
Header file containing the interface for your linked list data structure. Do not modify this file. src/linked_list.h
C file containing the implementation for your linked list. src/linked_list.c
Tests that validate the data structure adheres to the interface. tests/testLinkedList.cpp
You will create a doubly linked list that is able to store any kind of data (generic). Remember that a singly linked list only contains a pointer to the next item in the list; this implementation will have a pointer to the next and previous node.
Each linked list node will be represented by the list_node_t type in linked_list.h:
typedef struct list_node {
struct list_node* next; // pointer to next item
struct list_node* prev; // pointer to previous item
void *data; // pointer to a single list item
} list_node_t;
You must use malloc to allocate space for each node in the list as well as for the data in each slot.
Implement each of the following function defined by the linked_list.h interface:
linked_list.c
Header Description
list_node_t *linked_list_init() Initializes the linked list by creating a head node.
void linked_list_add(
list_node_t *head,
void *item) Adds an item to the linked list by traversing the list to create the next node. Updates the last node in the list to point to the newly created node.
void *linked_list_get(
list_node_t *head,
int index) Gets an item from the list at the given index by traversing the list.
int linked_list_set(
list_node_t *head,
int index,
void *item) Sets an item from the list at the given index by traversing the list.
Returns 1 if successful. Returns 0 if the index is not within bounds of the list.
void linked_list_remove(
list_node_t *head,
int index) Removes an item from the list at the given index by traversing the list. Links the previous node to the next node to avoid leaving a gap in the list.
int linked_list_contains(
list_node_t *head,
void *item) Searches for the given item by traversing the list. This effectively only checks to see if the pointers match to the same item (equality of pointers). Identicality of data is not checked.
Returns 1 if the item exists in the list. Returns 0 if the item does not exist in the list.
int linked_list_size(
list_node_t *head) Returns the size of the given list by traversing the list.
void linked_list_destroy(
list_node_t *head) Frees every node in the list by traversing the list.
Generic Doubly Linked List Queue
Purpose File
Header file containing the interface for your queue data structure. Do not modify this file. src/queue_list.h
C file containing the implementation for your queue. src/queue_list.c
Tests that validate the data structure adheres to the interface. tests/testQueueList.cpp
Using a doubly linked list as your data storage mechanism. Implement a queue. You must allocate and realloc your queue using malloc and realloc. However, you will use the linked list implementation you’ve created to support this data structure.
Your stack will be represented by the queue_list_t type that is defined in istack.h:
typedef struct queue_list_t {
list_node_t *front; // front of the queue
list_node_t *back; // back of the queue
} queue_list_t;
Implement each of the following functions defined by the queue_list.h interface:
queue_list.c
Header Description
queue_list_t *queue_list_init() Initializes the
void queue_list_enqueue(
queue_list_t *queue,
void *item) Adds one item to the back of the queue. Increments back index before setting item in the array storage.
void *queue_list_dequeue(
queue_list_t *queue) Removes one item from the front of the queue. Increments front index after removing item from the array storage.
void *queue_list_peek(
queue_list_t *queue) Returns the value at the front of the queue without removing it from the queue.
int queue_list_size(
queue_list_t *queue) Returns the size of the given list using the linked list size function.
void queue_list_destroy(
queue_list_t *queue) Frees every node in the queue by using the linked list free function. Also frees the queue struct.
Set each field to the following:
● front: NULL (after freeing)
● back: NULL
The post CIS 20 Fall 2019 – Programming Assingnment 2 – Data Structures appeared first on mynursing homeworks.
[ad_2]
Source link
