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

 

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. 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

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme