1.) write a sorted list class using array by implementing sorted list ADT(page 4
ID: 3553798 • Letter: 1
Question
1.) write a sorted list class using array by implementing sorted list ADT(page 413 on text book). The data should consist of the following.
a. name
b. date of birth
c. gender
list should be sorted by name.
write an additional method to return the index of the name if found (using binary search), otherwise -1.
write a main driver program to:
1. let users enter name, date of birth, and gender.
2. let users search the list and display his/her DOB, gender and age as of today.
the ADT for question 1 is
add(newEntry)
remove(anEntry)
getPosition(anEntry)
getEntry(givenPosition)
contains(anEntry)
remove(givenPosition)
clear()
getLenght()
isEmpty()
toArray()
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
struct test_struct
{
int val;
struct test_struct *next;
};
struct test_struct *head = NULL;
struct test_struct *curr = NULL;
struct test_struct* create_list(int val)
{
printf(" creating list with headnode as [%d] ",val);
struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));
if(NULL == ptr)
{
printf(" Node creation failed ");
return NULL;
}
ptr->val = val;
ptr->next = NULL;
head = curr = ptr;
return ptr;
}
struct test_struct* add_to_list(int val, bool add_to_end)
{
if(NULL == head)
{
return (create_list(val));
}
if(add_to_end)
printf(" Adding node to end of list with value [%d] ",val);
else
printf(" Adding node to beginning of list with value [%d] ",val);
struct test_struct *ptr = (struct test_struct*)malloc(sizeof(struct test_struct));
if(NULL == ptr)
{
printf(" Node creation failed ");
return NULL;
}
ptr->val = val;
ptr->next = NULL;
if(add_to_end)
{
curr->next = ptr;
curr = ptr;
}
else
{
ptr->next = head;
head = ptr;
}
return ptr;
}
struct test_struct* search_in_list(int val, struct test_struct **prev)
{
struct test_struct *ptr = head;
struct test_struct *tmp = NULL;
bool found = false;
printf(" Searching the list for value [%d] ",val);
while(ptr != NULL)
{
if(ptr->val == val)
{
found = true;
break;
}
else
{
tmp = ptr;
ptr = ptr->next;
}
}
if(true == found)
{
if(prev)
*prev = tmp;
return ptr;
}
else
{
return NULL;
}
}
int delete_from_list(int val)
{
struct test_struct *prev = NULL;
struct test_struct *del = NULL;
printf(" Deleting value [%d] from list ",val);
del = search_in_list(val,&prev);
if(del == NULL)
{
return -1;
}
else
{
if(prev != NULL)
prev->next = del->next;
if(del == curr)
{
curr = prev;
}
else if(del == head)
{
head = del->next;
}
}
free(del);
del = NULL;
return 0;
}
void print_list(void)
{
struct test_struct *ptr = head;
printf(" -------Printing list Start------- ");
while(ptr != NULL)
{
printf(" [%d] ",ptr->val);
ptr = ptr->next;
}
printf(" -------Printing list End------- ");
return;
}
int main(void)
{
int i = 0, ret = 0;
struct test_struct *ptr = NULL;
print_list();
for(i = 5; i<10; i++)
add_to_list(i,true);
print_list();
for(i = 4; i>0; i--)
add_to_list(i,false);
print_list();
for(i = 1; i<10; i += 4)
{
ptr = search_in_list(i, NULL);
if(NULL == ptr)
{
printf(" Search [val = %d] failed, no such element found ",i);
}
else
{
printf(" Search passed [val = %d] ",ptr->val);
}
print_list();
ret = delete_from_list(i);
if(ret != 0)
{
printf(" delete [val = %d] failed, no such element found ",i);
}
else
{
printf(" delete [val = %d] passed ",i);
}
print_list();
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.