INCLUDEPICTURE d "https://upload.wikimedia.org/wikipedia/en/1/10/Arms_Riga_Technical_University.png" * MERGEFORMATINET

RIGA TECHNICAL UNIVERSITY

Faculty of computer science and information Engineering

“Data structure Assignments”

Submitted to:- Submitted by:-

Nidagundi Padmaraj Vishali

Student id.171ADB125

2018/2019

Index

TOC h u z HYPERLINK l "_gjdgxs" h 1. HYPERLINK l "_gjdgxs" h PAGEREF _gjdgxs h Assignment3-5

HYPERLINK l "_tyjcwt" h 2. HYPERLINK l "_tyjcwt" h PAGEREF _gjdgxs h Assignment 6-9

HYPERLINK l "_2s8eyo1" h 3. HYPERLINK l "_2s8eyo1" h PAGEREF _gjdgxs h Assignment 10-27

HYPERLINK l "_17dp8vu" h 4. HYPERLINK l "_17dp8vu" h PAGEREF _gjdgxs h Assignment 27-36

HYPERLINK l "_3rdcrjn" h 5. HYPERLINK l "_3rdcrjn" h Assignment 36-41

Assignment 42-48

Assignment 48-51

Assignment 51-55

Assignment

a) Write a program to display "Hello world!" string to the console.

Program :-

public class Hello{

public static void main(Stringargs){

// prints"Hello,word" to the terminal window.

System.out.println("Hello,word");

}

}

Output :

false

b) Write a program to add two number and display results.

Program:-

import java.util.Scanner;

class AddNumbers

{

public static void main(String args)

{

int x,y,z;

System.out.println("Enter two number to calculate sum");

Scanner in = new Scanner(System.in);

x = in.nextInt();

y = in.nextInt();

z = x+y;

System.out.println("Sum of the integers = " +z);

}

}

Output-

false

Assignment

a) Write algorithm for the Queue

Algorithm:-

Step1: If last = size – 1 then

a) write ("the queue is full")

b) Return

Step 2: If front = – 1 then {insert}

a) front = 0

Step 3: rear = rear + 1

Step4: queue rear = item

END INSERT

b) Write the algorithm for the Tree

Algorithm:-

Int binarySearch (int low, int high, int key)

{while (low <= high)

{

If mid = (low + high) / 2;

If (a mid <key)

{low = mid+ 1;

}

else if (amid>key)

{

High = mid – 1;

} else

{

Go back to the mid;

}

}

return – 1;

}

c) Write a program for show 2 tables only on the screen

Programm code:-

import java.util.Scanner;

class Tables

{

public static void main(String args)

{

int a, b, c, d;

System.out.println("print table");

Scanner in =new Scanner(System.in);

a = in.nextInt();

b = in.nextInt();

for (c = a; c<= b; c++){

System.out.println("Multiplication table of "+c);

for (d = 1; d <= 10; d++){

System.out.println(c+"*"+d+"="+(c*d));

}

}

}

}

Output:-

3.Assignment

a) Use data structure visualizations to understand data structure concepts and make a 5-page report on any 5 topics.

Reports

1.Stack

stack:-stack is data structure whose element can be added and taken only from last position (top).

it is also called LIFO(last in first out)

components of stack:-

top-it is a variable which refers to last position in stack

element-it is component which had data

Max stack-it is variable that describes maximum number of elements in a stacks

Stack Operation: –

* Get started

* Empty action

* Full operation / one node

* Push

* Pop

Main action:

1. Push

Add data to element in stack

2. Pop

Get data from the element in the stack

Use of stack: –

The easiest process of a stack is to reverse a word. You can insert a given word on the stack on the stack – and then press the pop-characters from the stack

1. Parsing

2. Equation changes

algorithm for push operation :-

1.check if the stack is full or not

2.if the stack is full,then print error of overflow and exit the program

3.if the stack is not full,then increment the top and add the elements

algorithm for pop operation:-

1.check if the stack is empty or not

2.if the stack is empty ,then print error of underflow and exit the program.

3.if the stack is not empty,then print the element at the top and decrements the top

2.QUEUE

Queue: – Queue are first in first out type of data structure. in the . In a queue, new elements are added to one end in the queue and are eventually removed from the other end, called Front End. This is called FIFA (first time for the first time).

Basics feature of queue:-

1. Like a bridge, there is a provisional list of similar data types of queues

2.queue is a FIFO (first in first out) structure.

3. Insert a new unit in the row, enter new elements in the queue to remove new elements, all elements need to be removed.

4.peek () function is often used to return the first element value without any documents.

Application of queue:-

1.serving request on a single shared resource ,like a printer ,CPU task scheduling etc

2.in real life scenario,call center phone systems uses queue to hold people calling them in an order,until a server representative in free

3.handling of interrupts in real-time systems.the interrupts are handled in the same order as they arrive ie. first come first served.

Algorithm for enqueue: –

1. Check that the queue is full or not

2. If the queue is full, print the overflow error and exit the programs

3. If the queue is not complete, increase the tail and add the element

Algorithm for dequeue: –

1. Check that the queue is empty

2. If the queue is empty, print overflow errors and exit the programs

3.If the queue is not empty, then print the head on the head and increase the head

3. Link list

Linked List: – A list can be defined as a collection of variable items in the data item. The lists are commonly used non-temporary data structures. A related list containing templates that are created with two parts: the section of the information and the link section or an indicator part

Types of link list: –

1. Singly Linked List

INCLUDEPICTURE d "https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked Lists/pix/linkedlist.bmp" * MERGEFORMATINET

2.doubly linked list

INCLUDEPICTURE d "https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked Lists/pix/doubly.bmp" * MERGEFORMATINET

Linked list operations:-

add first:-the method create a node and prepends it at the beginning of the list.

INCLUDEPICTURE d "https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked Lists/pix/prepend.bmp" * MERGEFORMATINET

traversing:-start with the head and acess each node until you reach null.do not change the head refrence

INCLUDEPICTURE d "https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked Lists/pix/traverse.bmp" * MERGEFORMATINET

add last:-the method appends the node to the end of the list.this requires traversing ,but make sure you stop at the last node.

INCLUDEPICTURE d "https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked Lists/pix/append.bmp" * MERGEFORMATINET

insert "after" :-find a node containing "key"and insert a new node after it.

INCLUDEPICTURE d "https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked Lists/pix/after.bmp" * MERGEFORMATINET

inserting "before":-find a node containing "key"and insert a new node before that node.

INCLUDEPICTURE d "https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked Lists/pix/before.bmp" * MERGEFORMATINET

6.deletion:-find a node containing"key"and delet it

INCLUDEPICTURE d "https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked Lists/pix/delete.bmp" * MERGEFORMATINET

Binary tree

Binary Tree: – We increase the concept of data structures that contain nodes with more than one self-referenced field. A binary is made of tree nodes, where each node has a "left" reference, a "right" reflection, and the data element in the maximum node of the tree. Root is called root.

In each tree, each node is connected directly from one node to the other. This node is called a parent

INCLUDEPICTURE d "https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/pix/binaryTree.bmp" * MERGEFORMATINET

Advantages of tree:-

.trees reflect structural relationship in the data

.tree are used to represent hierarchies

tree provide an efficient insertion and searching

tree are very flexible data ,allowing to move sub trees around with minimum efforts.

Traversal:-A traversal is a process that visits all the nodes in the tree.since a tree is a non linear data structure,there is no unique traversal.we will consider traversal algorithm with we group in the following two kinds.

1.depth-first traversal

2.breadth-first traversal

Binary Search Tree: We consider a specific type of binary tree called a binary search tree (BST). The basic idea behind this data structure is to collect a kind of data collection, search, retrieval.

INCLUDEPICTURE d "https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/pix/pix03.bmp" * MERGEFORMATINET

5.search (linear search and binary searches)

There is no need to look for something in everyday life, cars, buttons, books, tablets, a day, a computer life, if there is a lot of information a user has stored in a lot of information, you should seek and have your own technique quickly fetching your computer memory and learning more about the operating system.

two types of research: –

Linear search

2.binary search

Linear search: – it is very basic and simple search algorithm. In a linear search, we search from the sequence of values and element or value, from the beginning to the element or to the value you want.

The element will be compared with all the existing elements in the column and returns the index of the continuous element when the element is successfully evaporated, while the other returns -1.

Linear search refers to lists that do not list or do not list when there are fewer items in the list.

Characteristics of the linear search algorithm:-

1.It is used to list unregulated and unregulated small objects.

2.It has a complexity of time, i.e. It is linearly dependent on the elemental number of times, but it is not bad.

3.There is a very simple application.

Binary search:-

Binary Search is used with the specified string or list. In the double search, we perform the following steps:

1.We begin by comparing the element element that is searched in the middle of the list / field.

2.If we are at the same time, we return the index of the average element.

3.If we do not match one match, we will check that the search item is lower or higher than the average item.

4.If the element / number to be interrupted is greater than the average, we will select the elements on the right side of the central element (the list / row will be numbered so that we have all the numbers on the right side) and restart from step 1.

5.If the interrupt element / unit is smaller than the average, select the elements on the left side of the central element and start again from step 1.

Binary search is useful and ranked when it has several elements.

The basic requirement for a binary search is that the list / row should be sorted.

Binary Search Features: –

1. Large sorted sequences are excellent for searching.

2. This is a very good time complex with O (log n) time complexity.

3. There is a simple application

b) Write a program for "Binary Tree"

import java.util.Scanner;

class BinarySearch

{

public static void main(String args)

{

int c, first,last,middle,n,search,array;

Scanner in =new Scanner(System.in);

System.out.println("Enter number of element");

n = in.nextInt();

array =new intn;

System.out.println("Enter value to find");

search = in.nextInt();

first =0;

last = n-1;

middle = (first + last)/2;

while (first<=last)

{

if(arraymiddle < search)

first = middle + 1;

else if (arraymiddle== search)

{

System.out.println(search +"found at location"+(middle +1)+".");

break;

}

else

last = middle-1;

middle = (first + last)/2;

}

if(first > last)

System.out.println(search +"is not present in the list.

");

}

}

Output:-

c) Write a program for "Queue"

Program:-

import java.util.Stack;

public class QUE

{

static class Queue

{

Stack<Integer>stack1;

Stack<Integer>stack2;

}

static void push(Stack<Integer>top_ref,int new_data)

{

top_ref.push(new_data);

}

static int pop(Stack<Integer>top_ref)

{

if(top_ref.isEmpty())

{

System.out.println("Stack overflow");

System.exit(0);

}

return top_ref.pop( );

}

static void enQueue(Queue q,int x)

{

push(q.stack1,x);

}

static int deQueue(Queue q)

{

int x;

if(q.stack1.isEmpty()&& q.stack2.isEmpty())

{

System.out.println("Q is empty");

System.exit(0);

}

if(q.stack2.isEmpty( ))

{

while(!q.stack1.isEmpty( ))

{

x=pop(q.stack1);

push(q.stack2,x);

}

}

x=pop(q.stack2);

return x;

}

public static void main(String args)

{

Queue q=new Queue( );

q.stack1=new Stack<>( );

q.stack2=new Stack<>( );

enQueue(q , 1);

enQueue(q , 2);

enQueue(q , 5);

System.out.print(deQueue(q)+" ");

System.out.print(deQueue(q)+" ");

System.out.println(deQueue(q)+" ");

}

}

Output:-

4.Assignment

A) What is the data structure and why do we use the data structure?

In computer science, the data structure is a special way of organizing and storing data in a computer so that it can be scaled up efficiently, or we can say that data struts are a way of organizing all data items. . The method by which not only the elements are stored but also interact with each other.

Data structure requirements: –

In computer science, a data structure is an important way to organize and store data in a computer so that it can be efficiently modified.

The data structure mainly determines the following four things: –

1. Organizing the Data

2. Accidental Mode

3. Cooperative degree

4. Processing options for information

B) Explain the different types of data structure

The classification of the data structure is as follows: –

1.Linear

2.Non-Linear

3.Homogeneous

4.Non-homogeneous

5.Dynamics

6.Static

Linear: –

Linear data structure is arranged sequentially, in which only one data element can be accessed. Examples of linear data structure are linked to the list, pile, queue, etc.

Non-Linear: –

Non-creative data structures are not systematically arranged, in which every data element is associated with other data elements. Non creative data structures are described as trees, graphs, etc.

Homogeneous: –

The only data structure in which the data type is similar to data elements. The data element in the same is related to a data type. For example, array

Non homogeneous: –

Non-identical data structures are those where data items are not related to the same data type. All data elements are different data types. For example: classes, structures, union etc.

Dynamic: –

Elements of memory are determined before the completion of their execution. Using M.F.C.M. MF Data storage is done before using AL elements. For example: Linked lists

Static: –

Elements of this data are agitated even before the program is implemented. For example: array

c) Various types of non-primitive data structures, non-primitive data structures are: –

The data structure are not atomic, is called non-primitive or composite. Examples are records, arrays and strings. These are very good. The non-initial data structure emphasizes the structure of the set of similar or forged data items.

There are non-primitive data types: –

Type: –

?.Arrays

?.Structure

. union

. Linked List

?.stack

?.Queue

Create a simple tree with 4 nodes

class Node

{

int key;

Node left,right;

public Node(int item)

{

key=item;

left=right=null;

}

}

class BinaryTree

{

Node root;

BinaryTree(int key)

{

root=new Node(key);

}

BinaryTree()

{

root=null;

}

public static void main(Stringargs)

{

BinaryTree tree=new BinaryTree();

tree .root=new Node(1);

tree .root.right=new Node(2);

tree .root.right.right=new Node(4);

}

}

Program for reversing a queue

Program:-

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

public class Queue_reverse{

static Queue<Integer>queue;

static void print()

{

while(!queue.isEmpty())

{

System.out.print(queue.peek()+" ");

queue.remove();

}

}

static Queue<Integer>reverseQueue(Queue<Integer>q)

{

if(q.isEmpty())

return q;

int data =q.peek();

q.remove();

q=reverseQueue(q);

q.add(data);

return q;

}

public static void main(String args)

{

queue= new LinkedList<Integer>();

queue.add(23);

queue.add(35);

queue.add(59);

queue.add(79);

queue.add(83);

queue.add(90);

queue.add(19);

queue.add(46);

queue.add(77);

queue.add(22);

queue=reverseQueue(queue);

print();

}

}

Output:-

5.Assignment

Binary search tree

Programm:-

import java.util.Scanner;

class BinarySearch

{

public static void main(String args)

{

int c, first,last,middle,n,search,array;

Scanner in =new Scanner(System.in);

System.out.println("Enter number of element");

n = in.nextInt();

array =new intn;

System.out.println("Enter value to find");

search = in.nextInt();

first =0;

last = n-1;

middle = (first + last)/2;

while (first<=last)

{

if(arraymiddle < search)

first = middle + 1;

else if (arraymiddle== search)

{

System.out.println(search +"found at location"+(middle +1)+".");

break;

}

else

last = middle-1;

middle = (first + last)/2;

}

if(first > last)

System.out.println(search +"is not pesent in the list.

");

}

}

Output:-

2.Queue:-

Program:-

import java.util.Stack;

public class QUE

{

static class Queue

{

Stack<Integer>stack1;

Stack<Integer>stack2;

}

static void push(Stack<Integer>top_ref,int new_data)

{

top_ref.push(new_data);

}

static int pop(Stack<Integer>top_ref)

{

if(top_ref.isEmpty())

{

System.out.println("Stack overflow");

System.exit(0);

}

return top_ref.pop( );

}

static void enQueue(Queue q,int x)

{

push(q.stack1,x);

}

static int deQueue(Queue q)

{

int x;

if(q.stack1.isEmpty()&& q.stack2.isEmpty())

{

System.out.println("Q is empty");

System.exit(0);

}

if(q.stack2.isEmpty( ))

{

while(!q.stack1.isEmpty( ))

{

x=pop(q.stack1);

push(q.stack2,x);

}

}

x=pop(q.stack2);

return x;

}

public static void main(String args)

{

Queue q=new Queue( );

q.stack1=new Stack<>( );

q.stack2=new Stack<>( );

enQueue(q , 1);

enQueue(q , 2);

enQueue(q , 5);

System.out.print(deQueue(q)+" ");

System.out.print(deQueue(q)+" ");

System.out.println(deQueue(q)+" ");

}

}

Output:-

6.Assignment

Answer the following question with examples

a) What is a Data Structure?b) What are the Data Structure Types?c) Why we need OR use Data Structure in programming?d) What are the linear and non-linear data Structures?e) What are the various operations that can be performed on different Data Structures?f) What is Tree and where it can be used?g) What is Stack and where it can be used?h) What is Queue and where it can be used?i) What is a Linked List and What are its types?j)What is Search and where it can be used?

A)What is the data structure and why do we use the data structure?

Computer science is a unique way of organizing and organizing a computer’s data, that it can be used effectively and in advanced or data structures are all data components. To understand collective elements, focus on your relationship with each other

B) Explain different types of data structure

The data structure classifications are like:

1.Linear

2. Non-linear

3.Homogeneous

4. It is not homogeneous

5.Dynamics

6.Static

Linear:-

The linear data structure is organized sequentially, in which only one data element can be reached. Examples of linear data structures are lists, stacks, queues, etc.

Non linear: –

The nonlinear data structure is not organized sequentially every element of data in it is connected to other elements of different data. Example of non-linear data structure are tree, graphs, etc.

Homogeneous: -The homogeneous data structure is one in which data elements have the same data type. All data elements in homogeneity belong to the single data type. For example, arrays

Non-homogeneous: -The non-homogeneous data structure is one in which data elements do not belong to the same data type. All data elements have different types of data. For example: classes, structure, union, etc.

Dynamic:-

The memory allocation of the elements is performed before execution is executed. In the data structure before the elements are used, memory allocation is performed with the use of D.M.Afunction. For example: Linked lists

Static:-

The allocation of the elements in this data schema is done before the program is executed. For example: array

C) data structures requirement: –

In computer science, data structure is a special way to organize and store data on a computer so that it can be accessed efficiently and accessible.

The data structure basically specifies four of the following: –

i) data organization

ii) method access

iii) Associate Degree

iv) Processing options for information

D) Linear Data Structure: –

Linear data structure is a single data structure that combines continuous or written data elements from one end to another. In a linear data structure, the data element passes one after the other, and only part of the component can be reached directly.

An example of a linear data structure is array, stack, queue, linked lists.

Non-linear Data Structure: –

Data styles where data items are not organized in the order form non-creative data structure. In other words, a data element of non-creative data structures should be connected to more than one element to represent a particular relationship between them. Can. The data structure consists of tree and graph.

E) Basic Concept – Operations that can be performed on data structures

1. Traversing

2. Searching

3. Inserting

4. Deleting

5. Sort

6. Merge

1. Traversing – It can be processed every time it is used to access the data item, so it can be processed

2. Searching – It is used to find the location of the data item if it is a data item collection

3.Inserting- it is used to add a new data item in the given collection of data items

4.Deleting- it is used to delete an existing data item from the given collection of data items

5.Sorting- it is used to arrange the data item in some order I.e in ascending or descending order in case of numerical data and in dictionary order in case of alphanumeric data

6.Merging- it is used to combine the data items of two sorted files into single file in the sorted form

F)Trees: – The tree can be defined as limited to the data elements. Radius is a type of data structure where data elements are arranged in sorted order. TR shows a strong link between the different elements

Why trees: –

The following are common use of trees

1. Editing authorized data

2. Make simple information just to find the information

3. Sort data randomly

4. Work flow to create a digital image for visual effect

5. Raster algorithm

Other uses of trees: –

1) There may be a reason for using trees because you want to store such information that naturally makes the hierarchy. For example, the file system on the computer:

2) If we organize the keys in the form of a tree (some orders, eg, with BST), we can search a given key in the medium time (faster than the linked list and slower than the array). Self-balance search like AVL and Red-Black Trees guarantee the upper limit of o (logan) for tree searching.

3) We can insert / delete keys in medium time (slower than faster and countless linked lists than arrays) O (logon) to insert / delete self-balanced search trees such as AVL and red-black trees High range guarantee.

4) Unlike linked lists and aliases, there is no upper limit on the number of nodes applied to the pointer’s pointers as connected using the pointer.

G) Queue: – queue are the first type of data structures. The new elements in a row include the rows ending from one end and the one is always removed from the other end, which is called at the front end. One FiFO(first at first).

H) Stack: – An order of elements like a stack array is collected, but it is a special feature that can be removed and the elements can be inserted only from one end, at the top of the stack. LIFO (last first out)

It is a non-primitive data structure.

• It is also called as the last to enter, first type of data structure (LIFO).

• Exp. Train, stack of trays, etc.

• At the moment of the insertion or elimination of an element, the base of the stack remains the same.

• The insertion of the element is called Push • The elimination of the element is called Pop

I) Linked List: – A list can be described as the variable number of data items. The list is the most useful non-godmother data systems. A link list contains the unit named nodes, where two nodes create two sections: notice partitions and a link segment or signal indicator

7.Assignment

Write a programm for Stack implementation in any one of the programming language

Program:-

public class Stack {

private int maxSize;

private long stackArray;

private int top;

public Stack(int s){

maxSize = s;

stackArray = new longmaxSize;

top = -1;

}

public void push(long j){

stackArray++top = j;

}

public long pop(){

return stackArraytop–;

}

public long peek(){

return stackArraytop;

}

public boolean isEmpty(){

return (top == -1);

}

public boolean isFull(){

return (top == maxSize -1);

}

public static void main(Stringargs){

Stack theStack = new Stack(10);

theStack.push(5);

theStack.push(10);

theStack.push(20);

theStack.push(34);

theStack.push(46);

while (!theStack.isEmpty()){

long value = theStack.pop();

System.out.print(value);

System.out.print(" ");

}

System.out.println("");

}

}

Output:-

8.Assignment

Write a program for queue implementation

Program:-

import java.lang.reflect.Array;

import java.util.Arrays;

public class Queue<E>{

Earr;

int head=-1;

int tail=-1;

int size;

public Queue(Class<E>c,int size){

EnewInstance =(E)Array.newInstance(c,size);

this.arr=newInstance;

this.size=0;

}

boolean push(E e){

if(size==arr.length)

return false ;

head =(head+1)%arr.length;

arrhead=e;

size++;

if(tail==-1){

tail=head;

}

return true;

}

boolean pop(){

if(size==0){

return false;

}

E result=arrtail;

arrtail=null;

size–;

tail=(tail+1)%arr.length;

if(size==0){

head=-1;

tail=-1;

}

return true;

}

E peek(){

if(size==0)

return null;

return arrtail;

}

public int size(){

return this.size;

}

public String toString(){

return Arrays.toString(this.arr);

}

public static void main(Stringargs){

Queue<Integer>q =new Queue<>(Integer.class,5);

q.push(2);

q.push(7);

q.push(5);

q.push(6);

q.push(9);

q.pop();

q.push(2);

System.out.println(q);

}

}

Output:-

Bibliography

Refrence:-https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html

Refrence:-https://www.studytonight.com/data-structures/search-algorithms

Refrence:-https://estudijas.rtu.lv/pluginfile.php/1438907/mod_resource/content/1/DATA%20STRUCTURE.pdf

Refrence:-https://www.tutorialspoint.com/javaexamples/data_stack.htm