Assignment 6: Linked List Applications
Set A
1)Write a program that merges two ordered linked lists into third new list. When two lists are merged the data in the resulting list are also ordered. The two original lists should be left unchanged. That is merged list should be new one. Use linked implementation.
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
} *temp = NULL, *first = NULL, *second = NULL, *third = NULL, *last = NULL;
struct Node* Create (int A[], int n)
{
int i;
struct Node *t, *last;
temp = (struct Node *) malloc(sizeof(struct Node));
temp->data = A[0];
temp->next = NULL;
last = temp;
for (i = 1; i < n; i++)
{
t = (struct Node *) malloc(sizeof(struct Node));
t->data = A[i];
t->next = NULL;
last->next = t;
last = t;
}
return temp;
}
void Display(struct Node *p)
{
while (p != NULL)
{
printf ("%d ", p->data);
p = p->next;
}
}
void Merge(struct Node *first, struct Node *second)
{
if (first->data < second->data)
{
third = last = first;
first = first->next;
last->next = NULL;
}
else
{
third = last = second;
second = second->next;
last->next = NULL;
}
while (first != NULL && second != NULL)
{
if (first->data < second->data)
{
last->next = first;
last = first;
first = first->next;
last->next = NULL;
}
else
{
last->next = second;
last = second;
second = second->next;
last->next = NULL;
}
}
if (first != NULL)
last->next = first;
else
last->next = second;
}
int main()
{
int A[] = { 3, 4, 7, 9 };
int B[] = { 2, 5, 6, 8 };
first = Create (A, 4);
second = Create (B, 4);
printf ("1st Linked List: ");
Display (first);
printf ("\n2nd Linked List: ");
Display (second);
Merge (first, second);
printf ("\n\nMerged Linked List: \n");
Display (third);
return 0;
}
2) Write a program that adds two single variable polynomials. Each polynomial should be represented as a list with linked list implementation.
#include<stdio.h>
#include<stdlib.h>
struct Node {
int coeff;
int pow;
struct Node* next;
};
// Function to create new node
void create_node(int x, int y, struct Node** temp)
{
struct Node *r, *z;
z = *temp;
if (z == NULL) {
r = (struct Node*)malloc(sizeof(struct Node));
r->coeff = x;
r->pow = y;
*temp = r;
r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;
}
else {
r->coeff = x;
r->pow = y;
r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;
}
}
// Function Adding two polynomial numbers
void polyadd(struct Node* poly1, struct Node* poly2, struct Node* poly)
{
while (poly1->next && poly2->next) {
if (poly1->pow > poly2->pow) {
poly->pow = poly1->pow;
poly->coeff = poly1->coeff;
poly1 = poly1->next;
}
else if (poly1->pow < poly2->pow) {
poly->pow = poly2->pow;
poly->coeff = poly2->coeff;
poly2 = poly2->next;
}
else {
poly->pow = poly1->pow;
poly->coeff = poly1->coeff + poly2->coeff;
poly1 = poly1->next;
poly2 = poly2->next;
}
// Dynamically create new node
poly->next
= (struct Node*)malloc(sizeof(struct Node));
poly = poly->next;
poly->next = NULL;
}
while (poly1->next || poly2->next) {
if (poly1->next) {
poly->pow = poly1->pow;
poly->coeff = poly1->coeff;
poly1 = poly1->next;
}
if (poly2->next) {
poly->pow = poly2->pow;
poly->coeff = poly2->coeff;
poly2 = poly2->next;
}
poly->next
= (struct Node*)malloc(sizeof(struct Node));
poly = poly->next;
poly->next = NULL;
}
}
// Display Linked list
void show(struct Node* node)
{
while (node->next != NULL) {
printf("%dx^%d", node->coeff, node->pow);
node = node->next;
if (node->coeff >= 0) {
if (node->next != NULL)
printf("+");
}
}
}
int main()
{
struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL;
// Create first list of 5x^2 + 4x^1 + 2x^0
create_node(5, 2, &poly1);
create_node(4, 1, &poly1);
create_node(2, 0, &poly1);
// Create second list of -5x^1 - 5x^0
create_node(-5, 1, &poly2);
create_node(-5, 0, &poly2);
printf("1st Number: ");
show(poly1);
printf("\n2nd Number: ");
show(poly2);
poly = (struct Node*)malloc(sizeof(struct Node));
// Function add two polynomial numbers
polyadd(poly1, poly2, poly);
// Display resultant List
printf("\nAdded polynomial: ");
show(poly);
return 0;
}
Set B
1) Write a program that sorts the elements of linked list using any of sorting technique.
#include<stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
int main()
{
struct node *temp1,*temp2, *t,*newNode, *startList;
int n,k,i,j;
startList=NULL;
printf("Input number of elements in the linked list?");
scanf("%d",&n);
printf("Input the elements in the linked list:\n");
for(i=1;i<=n;i++)
{
if(startList==NULL)
{
newNode=(struct node *)malloc(sizeof(struct node));
scanf("%d",&newNode->data);
newNode->next=NULL;
startList = newNode;
temp1=startList;
}
else
{
newNode=(struct node *)malloc(sizeof(struct node));
scanf("%d",&newNode->data);
newNode->next=NULL;
temp1->next = newNode;
temp1=newNode;
}
}
for(i=n-2;i>=0;i--)
{
temp1=startList;
temp2=temp1->next;
for(j=0;j<=i;j++)
{
if(temp1->data > temp2->data)
{
k=temp1->data;
temp1->data=temp2->data;
temp2->data=k;
}
temp1=temp2;
temp2=temp2->next;
}
}
printf("Sorted order is: \n");
t=startList;
while(t!=NULL)
{
printf("%d\t",t->data);
t=t->next;
}
}
2) Write a program that multiply two single variable polynomials. Each polynomial should be represented as a list with linked list implementation.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
// Define useful field of Node
int data;
int power;
struct Node * next;
}Node;
Node * getNode(int data, int power)
{
// Create dynamic memory of Node
Node * ref = (Node * ) malloc(sizeof(Node));
if (ref == NULL)
{
// Failed to create memory
return NULL;
}
ref->data = data;
ref->power = power;
ref->next = NULL;
return ref;
}
// Update node value
void updateRecord(Node * ref, int data, int power)
{
ref->data = data;
ref->power = power;
}
typedef struct MultiplyPolynomial
{
// Define useful field of MultiplyPolynomial
struct Node * head;
}MultiplyPolynomial;
MultiplyPolynomial * getMultiplyPolynomial()
{
// Create dynamic memory of MultiplyPolynomial
MultiplyPolynomial * ref = (MultiplyPolynomial * )
malloc(sizeof(MultiplyPolynomial));
if (ref == NULL)
{
// Failed to create memory
return NULL;
}
ref->head = NULL;
return ref;
}
// Insert Node element
void insert(MultiplyPolynomial * ref, int data, int power)
{
if (ref->head == NULL)
{
// Add first node
ref->head = getNode(data, power);
}
else
{
Node * node = NULL;
Node * temp = ref->head;
Node * location = NULL;
// Find the valid new node location
while (temp != NULL && temp->power >= power)
{
location = temp;
temp = temp->next;
}
if (location != NULL && location->power == power)
{
// When polynomial power already exists
// Then add current add to previous data
location->data = location->data + data;
}
else
{
node = getNode(data, power);
if (location == NULL)
{
// When add node in begining
node->next = ref->head;
ref->head = node;
}
else
{
// When adding node in intermediate
// location or end location
node->next = location->next;
location->next = node;
}
}
}
}
// Perform multiplication of given polynomial
MultiplyPolynomial * multiplyPolynomials(
MultiplyPolynomial * ref, MultiplyPolynomial * other)
{
// Define some useful variable
MultiplyPolynomial * result = getMultiplyPolynomial();
// Get first node of polynomial
Node * poly1 = ref->head;
Node * temp = other->head;
int power_value = 0;
int coefficient = 0;
// Execute loop until when polynomial are exist
while (poly1 != NULL)
{
temp = other->head;
while (temp != NULL)
{
// Get result info
power_value = poly1->power + temp->power;
coefficient = poly1->data * temp->data;
insert(result, coefficient, power_value);
// Visit to next node
temp = temp->next;
}
// Visit to next node
poly1 = poly1->next;
}
// return first node
return result;
}
// Display given polynomial nodes
void display(MultiplyPolynomial * ref)
{
if (ref->head == NULL)
{
printf("Empty Polynomial ");
}
printf(" ");
Node * temp = ref->head;
while (temp != NULL)
{
if (temp != ref->head)
{
printf(" + %d", temp->data);
}
else
{
printf("%d",temp->data);
}
if (temp->power != 0)
{
printf("x^%d", temp->power);
}
// Visit to next node
temp = temp->next;
}
printf("\n");
}
int main()
{
MultiplyPolynomial * a = getMultiplyPolynomial();
MultiplyPolynomial * b = getMultiplyPolynomial();
// Add node in polynomial A
insert(a, 9, 3);
insert(a, 4, 2);
insert(a, 3, 0);
insert(a, 7, 1);
insert(a, 3, 4);
// Add node in polynomial b
insert(b, 7, 3);
insert(b, 4, 0);
insert(b, 6, 1);
insert(b, 1, 2);
// Display Polynomial nodes
printf("\n Polynomial A\n");
display(a);
printf(" Polynomial B\n");
display(b);
MultiplyPolynomial * result = multiplyPolynomials(a, b);
// Display calculated result
printf(" Result\n");
display(result);
}
Set C
1) Write a program to find common elements of two linked lists and create third list. Ensure that the common elements appear only once in the third list.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int num;
struct node *next;
};
void create(struct node **);
int find(struct node *, struct node *);
void release(struct node **);
void display(struct node *);
int main()
{
struct node *p = NULL, *q = NULL;
int result;
printf("Enter data into the list\n");
create(&p);
printf("Enter data into the list\n");
create(&q);
printf("Displaying list1:\n");
display(p);
printf("Displaying list2:\n");
display(q);
result = find(p, q);
if (result)
{
printf("The first matched element is %d.\n", result);
}
else
{
printf("No matching element found.\n");
}
release (&p);
return 0;
}
int find(struct node *p, struct node *q)
{
struct node *temp;
while (p != NULL)
{
temp = q;
while (temp != NULL)
{
if (temp->num == p->num)
{
return p->num;
}
temp = temp->next;
}
p = p->next;
}
/*Assuming 0 is not used in the list*/
return 0;
}
void create(struct node **head)
{
int c, ch;
struct node *temp, *rear;
do
{
printf("Enter number: ");
scanf("%d", &c);
temp = (struct node *)malloc(sizeof(struct node));
temp->num = c;
temp->next = NULL;
if (*head == NULL)
{
*head = temp;
}
else
{
rear->next = temp;
}
rear = temp;
printf("Do you wish to continue [1/0]: ");
scanf("%d", &ch);
} while (ch != 0);
printf("\n");
}
void display(struct node *head)
{
while (head != NULL)
{
printf("%d\t", head->num);
head = head->next;
}
printf("\n");
}
void release(struct node **head)
{
struct node *temp;
while ((*head) != NULL)
{
temp = *head;
(*head) = (*head)->next;
free(temp);
}
}
No comments:
Post a Comment