programming Assignment#6 – Linear Data Structure Due Date: Midnight of April 13
ID: 3706265 • Letter: P
Question
programming
Assignment#6 – Linear Data Structure
Due Date: Midnight of April 13 (Friday)
Purpose: The purpose of this assignment is to help you:
• Understand linear data structure
• Become familiar with data structure implementation
Instructions: Be sure to read the following general instructions carefully:
This assignment should be completed individually by all students. You are encouraged to demonstrate your solution during lab session, and submit your solution through the dropbox. You must name your submission according to the following rule: studentID(yourlastname)_ASSnumber.zip. e.g., 300123456(smith)_ASS#6.zip
Rubric
Functionality Marks
Q1 5*2
The scenario 2*2
The explanation 1.5*2*2
Q2.1 10
Class properties 0.5
Constructors 0.5
Insertion method 4
Remove method 4
Display method 1
Q2.2 10
Generate two ordered-list objects 1.5*2
Method Merge 6
The app can generate right result 1
Question 1 [10 marks]
1.1. Provide a scenario to demonstrate stack usage, explain why and how to use stack.
[5 marks]
1.2. Provide a scenario to demonstrate queue usage, explain why and how to use queue
[5 marks]
Question 2[20 marks]
Implement a sorted singly linked list. You can do it from scratch or by inheriting the class List in LinkedListLibrary which has been demonstrated during the class [10 marks]
Write a program that merges two ordered singly linked list objects of integers into a single ordered-list object of integers. Method Merge should receive references to each of the list objects to be merged and should return a reference to the merged-list object [10 marks]
Explanation / Answer
1)
1.1) A stack data structure refers to adding and removing of elements in a specified order. Stack follows LIFO (Last In First Out) principle. This means the item/element inserted in the stack at the end, is removed first.
Example -
A good real-life example of a stack is the pile of dinner plates that you encounter when you eat at the local cafeteria: When you remove a plate from the pile, you take the plate on the top of the pile. But this is exactly the plate that was added ("inserted'') most recently to the pile by the dishwasher. If you want the plate at the bottom of the pile, you must remove all the plates on top of it to reach it.
1.2) A queue data structure refers to adding and removing of elements in FIFO (First In First Out) principle. In this, the element that is entered first, is removed first unlike stack.
Example -
When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
2) Implementation of Linked List:-
public class LinkListImplementation {
}
Merge 2 Single Linked List into one Linked List:-
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
/* pull off the front node of the source and put it in dest */
void MoveNode(struct Node** destRef, struct Node** sourceRef);
/* Takes two lists sorted in increasing order, and splices
their nodes together to make one big sorted list which
is returned. */
struct Node* SortedMerge(struct Node* a, struct Node* b)
{
/* a dummy first node to hang the result on */
struct Node dummy;
/* tail points to the last result node */
struct Node* tail = &dummy;
/* so tail->next is the place to add new nodes
to the result. */
dummy.next = NULL;
while (1)
{
if (a == NULL)
{
/* if either list runs out, use the other list */
tail->next = b;
break;
}
else if (b == NULL)
{
tail->next = a;
break;
}
if (a->data <= b->data)
MoveNode(&(tail->next), &a);
else
MoveNode(&(tail->next), &b);
tail = tail->next;
}
return(dummy.next);
}
void MoveNode(struct Node** destRef, struct Node** sourceRef)
{
/* the front source node */
struct Node* newNode = *sourceRef;
assert(newNode != NULL);
/* Advance the source pointer */
*sourceRef = newNode->next;
/* Link the old dest off the new node */
newNode->next = *destRef;
/* Move dest to point to the new node */
*destRef = newNode;
}
/* 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;
}
}
/* 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;
/* Let us create two sorted linked lists to test
the functions
Created lists, a: 5->10->15, b: 2->3->20 */
push(&a, 15);
push(&a, 10);
push(&a, 5);
push(&b, 20);
push(&b, 3);
push(&b, 2);
/* Remove duplicates from linked list */
res = SortedMerge(a, b);
printf("Merged Linked List is: ");
printList(res);
return 0;
}
public static void main(String[] args) throws java.lang.Exception {Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.