Create a Sorted List abstract data type and Functions to be implemented

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Advanced Linked Lists

typedef structNODE{

value_tvalue;

key_tkey;

struct NODE* next;

struct NODE* sort;

} Node;

In this linked list:

• The datatype for the value being stored is called value_t
• The datatype for the key being stored is called key_t
• As in lab 4, nextlinks to the node in the order it was added to the list (either at the head or the tail)oThis will be referred to as insertionorder
• Similar tolab 4, sortlinks to the node where the key is greater or equal to its key
• e. the list is kept in ascending order by key
• This will be referred to as key sortorder
• Note: unlike lab 4, there is only one key

Create a Sorted List abstract data type

• Has two heads (headfor insertionorder, head_sortfor key sort order)
• Has twotails (tailfor insertionorder, tail_sortfor key sort order)
• If you are notusingthe bonus Node struct
• Has two “previous tail” (the node pointing to the tail node) links prev_tailand prev_tail_sorted
• Has anintfield called size that stored the node count (the number of elements in the list)The datatype should be called Sorted_List

Functions To be implemented

All functions, except where noted,return SUCCESS if the function can complete or FAIL if not

• int size (Sorted_List *)
• int push(Sorted_List *,value_t , key_t)oadd the node to the headof the list

 the node must also be inserted in ascendingsortorderby key, using the sort link

• int append(Sorted_List *, value_t , key_t)osimilar to push, except the node gets added to tail
• int remove_first(Sorted_List * , value_t * , key_t *)oremoves the node from the head of the list

O returns the value and key of the removed node (and frees the node)

o remember to update the sort order links if not using doubly linked lists, you will need to find the previous sorted nodeto change its sort order link

• int remove_last(Sorted_List * , value_t * , key_t * )osimilar to remove_first, except it removes the node from the tail •int remove_smallest_key(Sorted_List * , value_t * ,key_t * )

removes the node with the smallest key

o returns the value and key of the removed node (and frees the node)

o remember to update the insertionorder links if not using doubly linked lists, you will need to find the previous insert order node to change its insertionorder link

• int remove_largest_key (Sorted_List * , value_t * , key_t * )

osimilar to remove_smallest_key, except it removes the node with the largest key

• void empty_list(Sorted_List *)

O empties the contents of the list

• void destroy_list(Sorted_List *)oempties the contents ofthelist,as well as freeing the list itself

To testthe Sorted List ADT

Write two programs called a4q1a_char.c and  a4q1a_int.c

• Data types used

a4q1a_int.c

has its value_tdatatype set equal to int

has it key_tdatatype set equal to double

a4q1a_char.c

hasitsvalue_t datatype set equal to char[80]

• i.e. it can take strings up to 79 characters in length

has its key_tdatatype setequaltoint

• its value is set equal to the length of the string
• Both programs readina text file that contains a series of commands, one per line (i.e each ending with a newline)

The name of the text file should be entered as a command line argument§If there is no file name, read from stdin

• this can use IO redirect, i.e.a4q1a_int < filename.txt
• If using keyboard input, exit using ^d•All commands are echoed to stdout, followed by a colon :,

After that the results of the command follows,

• usually on the same line following11–strlen(cmd name)spaces oron the next linewhen notedNote: Silent commands do not have the colon : after the command, but rather after the command name
• Remember to free the sorted list at the end of the program (use destroy_list)General Note:The two programs should be almost identical, with the following differences

The file input will be slightlydifferent depending on the data type and nature of the input data

Your will have to write similar, but not identicalvoid print_list_all(Sorted_List * )andvoid print_list_sort(Sorted_List * )functions

These functionsprint out the lists according totheir respectivesort orders

See the report commands section below for details(the print_alland print_sortcommands)

You will have to have your make file recompile allfiles that mention or usevalue_t and key_tvariables or Sort_List structs when compiling the two programs

To do this you will need to use condition compilation (see Week1 lecture notes)§In specific, use #ifdef CHAR to compile using the char[80] typedef definitionof value_t and #ifdef INT to compile using the int typedef definition of value_t

E.g.if you stored all your Sort_List ADT functions in a single file called sort_list.cThenfor a4q1a_char.cyou could havein your make fileacommandlikegcc -Wall -ansi -DCHAR-csort_list.c

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of