Files need: list.h: http://pastebin.com/rFP7CMhE ll_tst.c: http://pastebin.com/u

Question

Files need:

list.h: http://pastebin.com/rFP7CMhE

ll_tst.c: http://pastebin.com/uXzNLJis

llist.c: http://pastebin.com/jJ9xrHWs

Coding needs to be done in basic C.

Implementing Linked List Utility Functions. Examine the files list. h and list. c in the src directory where you found this handout. You will discover that it is a partially implemented linked list "module". The lists store numeric values (the type of which can be changed by altering the typedef for ElemType in list.h). As in previous projects, the . h file gives the interface for an ADT while the actual implementation is given in the .c file. The members of list_struct are also "hidden" in the . c file. The ADT defines many natural operations on lists -- some of these have already been implemented and will be used as motivating examples during lecture; others have not been implemented: It is your job to do the implementation! Look for TODO labels throughout the files. A subtle detail: why did I decide to name the header file list.h (one '1'), but the implementation file list.c (two '1's)??? So... part I is completion of all of the TODO items specified. Rules: you cannot change list. h (except maybe to experiment with different ElemTypes). All of your work is in list.c (except testing code). Discussion: The given linked list structure has two "levels": At the "lowest" level are the linked-list nodes themselves specified as: typedef struct node { ElemType val; struct node *next; } NODE; However, the type NODE isn't even visible to a client program. Only the type LIST is visible to a client (just the type - - not the struct members). Through the header file, LIST is equivalent to a struct list_struct which is specified as follows: struct list_struct { NODE *front; NODE *back; }; Here is a diagram of a list with three entries: . The struct at the left (a list) gives access to the actual nodes. List of TODO functions: lst_count, lst_pop_back, lst_print_rev, lst_reverse, lst_sra_bad_case, lst_remove_all_fast, lst_is_sorted, lst_insert_sorted, lst_merge_sorted

Explanation / Answer

#include <stdio.h>
#include <malloc.h>
#define ISEMPTY printf(" EMPTY LIST:");
/*
* Node Declaration
*/
struct node
{
int value;
struct node *next;
};

snode* create_node(int);
void insert_node_first();
void insert_node_last();
void insert_node_pos();
void sorted_ascend();
void delete_pos();
void search();
void update_val();
void display();
void rev_display(snode *);

typedef struct node snode;
snode *newnode, *ptr, *prev, *temp;
snode *first = NULL, *last = NULL;

/*
* Main :contains menu
*/

int main()
{
int ch;
char ans = 'Y';

while (ans == 'Y'||ans == 'y')
{
printf(" --------------------------------- ");
printf(" Operations on singly linked list ");
printf(" --------------------------------- ");
printf(" 1.Insert node at first");
printf(" 2.Insert node at last");
printf(" 3.Insert node at position");
printf(" 4.Sorted Linked List in Ascending Order");
printf(" 5.Delete Node from any Position");
printf(" 6.Update Node Value");
printf(" 7.Search Element in the linked list");
printf(" 8.Display List from Beginning to end");
printf(" 9.Display List from end using Recursion");
printf(" 10.Exit ");
printf(" ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ");
printf(" Enter your choice");
scanf("%d", &ch);

switch (ch)
{
case 1:
printf(" ...Inserting node at first... ");
insert_node_first();
break;
case 2:
printf(" ...Inserting node at last... ");
insert_node_last();
break;
case 3:
printf(" ...Inserting node at position... ");
insert_node_pos();
break;
case 4:
printf(" ...Sorted Linked List in Ascending Order... ");
sorted_ascend();
break;
case 5:
printf(" ...Deleting Node from any Position... ");
delete_pos();
break;
case 6:
printf(" ...Updating Node Value... ");
update_val();
break;
case 7:
printf(" ...Searching Element in the List... ");
search();
break;
case 8:
printf(" ...Displaying List From Beginning to End... ");
display();
break;
case 9:
printf(" ...Displaying List From End using Recursion... ");
rev_display(first);
break;
case 10:
printf(" ...Exiting... ");
return 0;
break;
default:
printf(" ...Invalid Choice... ");
break;
}
printf(" YOU WANT TO CONTINUE (Y/N)");
scanf(" %c", &ans);
}
return 0;
}

/*
* Creating Node
*/
snode* create_node(int val)
{
newnode = (snode *)malloc(sizeof(snode));
if (newnode == NULL)
{
printf(" Memory was not allocated");
return 0;
}
else
{
newnode->value = val;
newnode->next = NULL;
return newnode;
}
}

/*
* Inserting Node at First
*/
void insert_node_first()
{
int val;

printf(" Enter the value for the node:");
scanf("%d", &val);
newnode = create_node(val);
if (first == last && first == NULL)
{
first = last = newnode;
first->next = NULL;
last->next = NULL;
}
else
{
temp = first;
first = newnode;
first->next = temp;
}
printf(" ----INSERTED----");
}

/*
* Inserting Node at Last
*/
void insert_node_last()
{
int val;

printf(" Enter the value for the Node:");
scanf("%d", &val);
newnode = create_node(val);
if (first == last && last == NULL)
{
first = last = newnode;
first->next = NULL;
last->next = NULL;
}
else
{
last->next = newnode;
last = newnode;
last->next = NULL;
}
printf(" ----INSERTED----");
}

/*
* Inserting Node at position
*/
void insert_node_pos()
{
int pos, val, cnt = 0, i;

printf(" Enter the value for the Node:");
scanf("%d", &val);
newnode = create_node(val);
printf(" Enter the position ");
scanf("%d", &pos);
ptr = first;
while (ptr != NULL)
{
ptr = ptr->next;
cnt++;
}
if (pos == 1)
{
if (first == last && first == NULL)
{
first = last = newnode;
first->next = NULL;
last->next = NULL;
}
else
{
temp = first;
first = newnode;
first->next = temp;
}
printf(" Inserted");
}
else if (pos>1 && pos<=cnt)
{
ptr = first;
for (i = 1;i < pos;i++)
{
prev = ptr;
ptr = ptr->next;
}
prev->next = newnode;
newnode->next = ptr;
printf(" ----INSERTED----");
}
else
{
printf("Position is out of range");
}
}

/*
* Sorted Linked List
*/
void sorted_ascend()
{
snode *nxt;
int t;

if (first == NULL)
{
ISEMPTY;
printf(":No elements to sort ");
}
else
{
for (ptr = first;ptr != NULL;ptr = ptr->next)
{
for (nxt = ptr->next;nxt != NULL;nxt = nxt->next)
{
if (ptr->value > nxt->value)
{
t = ptr->value;
ptr->value = nxt->value;
nxt->value = t;
}
}
}
printf(" ---Sorted List---");
for (ptr = first;ptr != NULL;ptr = ptr->next)
{
printf("%d ", ptr->value);
}
}
}

/*
* Delete Node from specified position in a non-empty list
*/
void delete_pos()
{
int pos, cnt = 0, i;

if (first == NULL)
{
ISEMPTY;
printf(":No node to delete ");
}
else
{
printf(" Enter the position of value to be deleted:");
scanf(" %d", &pos);
ptr = first;
if (pos == 1)
{
first = ptr->next;
printf(" Element deleted");
}
else
{
while (ptr != NULL)
{
ptr = ptr->next;
cnt = cnt + 1;
}
if (pos > 0 && pos <= cnt)
{
ptr = first;
for (i = 1;i < pos;i++)
{
prev = ptr;
ptr = ptr->next;
}
prev->next = ptr->next;
}
else
{
printf("Position is out of range");
}
free(ptr);
printf(" Element deleted");
}
}
}
/*
* Updating Node value in a non-empty list
*/
void update_val()
{
int oldval, newval, flag = 0;

if (first == NULL)
{
ISEMPTY;
printf(":No nodes in the list to update ");
}
else
{
printf(" Enter the value to be updated:");
scanf("%d", &oldval);
printf(" Enter the newvalue:");
scanf("%d", &newval);
for (ptr = first;ptr != NULL;ptr = ptr->next)
{
if (ptr->value == oldval)
{
ptr->value = newval;
flag = 1;
break;
}
}
if (flag == 1)
{
printf(" Updated Successfully");
}
else
{
printf(" Value not found in List");
}
}
}

/*
* searching an element in a non-empty list
*/
void search()
{
int flag = 0, key, pos = 0;

if (first == NULL)
{
ISEMPTY;
printf(":No nodes in the list ");
}
else
{
printf(" Enter the value to search");
scanf("%d", &key);
for (ptr = first;ptr != NULL;ptr = ptr->next)
{
pos = pos + 1;
if (ptr->value == key)
{
flag = 1;
break;
}
}
if (flag == 1)
{
printf(" Element %d found at %d position ", key, pos);
}
else
{
printf(" Element %d not found in list ", key);
}
}
}
/*
* Displays non-empty List from Beginning to End
*/
void display()
{
if (first == NULL)
{
ISEMPTY;
printf(":No nodes in the list to display ");
}
else
{
for (ptr = first;ptr != NULL;ptr = ptr->next)
{
printf("%d ", ptr->value);
}
}
}

/*
* Display non-empty list in Reverse Order
*/
void rev_display(snode *ptr)
{
int val;

if (ptr == NULL)
{
ISEMPTY;
printf(":No nodes to display ");
}
else
{
if (ptr != NULL)
{
val = ptr->value;
rev_display(ptr->next);
printf("%d ", val);
}

}
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.