USING C++ For the following problems define a struct node with data of type int.

Question

USING C++

For the following problems define a struct node with data of type int.

4.   Implement a function that merges two linked lists in order. The function must be able to merge two ordered lists in descending or ascending order. The function accepts pointers to the two lists and an order to merge the lists, and returns a pointer to the beginning of the merged lists. Be sure to test your function! You may start with code that you have written for other labs. EXTRA CHALLENGE: Could you implement a merge lists function which merges n lists in order? This function would accept a pointer to an array of n pointers, where each pointer refers to a list.

5. Write a pseudocode algorithm that uses two stacks to simulate one queue. Only consider insertions and deletions from the queue. Since this is pseudocode, you do not have to describe how to implement push and pop (these are the operations that you will discuss to simulate the queue). However, you may assume that these are acceptable terms to use within your pseudocode algorithm. Make sure that the algorithm clearly describes what needs to be done with the stack during insertions and deletions from the queue.

Explanation / Answer

4.=================================

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>

/* Link list node */
struct node
{
int data;
struct node* next;
};

/* Function to insert a node at the beginging of the linked list */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

/* Function to print nodes in a given linked list */
void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

node * SortedMerge(node*a,node *b,char type[]) {
   //Base conditions
   char asc[4]= "asc";
   if(!a)
   return b;

   if(!b)
   return a;

   struct node dummy;
   dummy.next = NULL;
   node* tail = &dummy;

   while(a&&b) {
if(strcmp(type,asc)==0){
       if(a->data <= b->data) {
           tail->next = a;
           a= a->next;
       }
       else {
           tail->next = b;
           b=b->next;
       }
       tail= tail->next;
       tail->next = NULL;
   } else{
   if(a->data >= b->data) {
           tail->next = a;
           a= a->next;
       }
       else {
           tail->next = b;
           b=b->next;
       }
       tail= tail->next;
       tail->next = NULL;
   }
   }
   if(!a) {
       tail->next = b;
   }
   if(!b) {
       tail->next = a;
   }
   return dummy.next;
}

/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct node* res = NULL;
struct node* a = NULL;
struct node* b = NULL;

struct node* res2 = NULL;
struct node* a2= NULL;
struct node* b2 = NULL;

char type[10];
/* Let us create two sorted linked lists to test the functions
Created lists shall be a: 5->10->15, b: 2->3->20 */
push(&a, 15);
push(&a, 10);
push(&a, 5);
push(&a,1);

push(&b, 20);
push(&b, 9);
push(&b, 3);
push(&b, 2);

/* Remove duplicates from linked list */
res = SortedMerge(a, b,"asc");

printf(" Merged Linked List is (ascending) : ");
printList(res);

push(&a2,1);
push(&a2, 5);
push(&a2, 10);
push(&a2, 15);

push(&b2, 2);
push(&b2, 3);
push(&b2, 9);
push(&b2, 20);

res2= SortedMerge(a2, b2,"dsc");
printf(" Merged Linked List is (descending) : ");
printList(res2);

getchar();
return 0;
}

=================================================================

5)

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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