Download Anna University B-Tech CSE 3rd Sem CS8381 Data Structures DS Lab Manual Question Paper

FirstRanker.com

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

III SEMESTER - R 2017

--- Content provided by⁠ FirstRanker.com ---

CS8381– DATA STRUCTURES LABORATORY

LABORATORY MANUAL

Name :

Register No :

Section :

--- Content provided by​ FirstRanker.com ---

VISION

is committed to provide highly disciplined, conscientious and enterprising professionals conforming to global standards through value based quality education and training.

MISSION

• To provide competent technical manpower capable of meeting requirements of the industry
• To contribute to the promotion of Academic excellence in pursuit of Technical Education at different levels

--- Content provided by​ FirstRanker.com ---

• To train the students to sell his brawn and brain to the highest bidder but to never put a price tag on heart and soul

PROGRAM EDUCATIONAL OBJECTIVES

1. FUNDAMENTALS

   To impart students with fundamental knowledge in Mathematics, Science and fundamentals of engineering that will mould them to be successful professionals

2. CORE COMPETENCE

   To provide students with sound knowledge in engineering and experimental skills to identify complex software problems in industry and to develop practical solutions for them

   --- Content provided by‍ FirstRanker.com ---

3. BREADTH

   To provide relevant training and experience to bridge the gap between theory and practice this enables them to find solutions for real time problems in industry and organization, and to design products requiring interdisciplinary skills

4. PROFESSIONALISM SKILLS

   To bestow students with adequate training and provide opportunities to work as team that will build up their communication skills, individual leadership and supportive qualities, and to enable them to adapt and work in ever changing technologies

--- Content provided by‌ FirstRanker.com ---

5. LIFELONG LEARNING

   To develop the ability of students to establish themselves as professionals in Computer Science and Engineering and to create awareness about the need for lifelong learning and pursuing advanced degrees

PROGRAM OUTCOMES

1. To apply the basic knowledge of Mathematics, Science and engineering fundamentals in Computer Science and Engineering field
2. To design and conduct experiments as well as to analyze and interpret data and apply the same in the career

--- Content provided by‍ FirstRanker.com ---

3. To design and develop innovative and creative software applications
4. To understand a complex real world problem and develop an efficient practical solution
5. To create, select and apply appropriate techniques, resources, modern engineering and IT tools
6. To understand their roles as a professionals and give the best to the society
7. To develop a system that will meet expected needs within realistic constraints such as economical, environmental, social, political, ethical, safe and sustainable

--- Content provided by​ FirstRanker.com ---

8. To communicate effectively and make others understand exactly what they are trying to convey in both verbal and written forms
9. To work in a team as team member or a leader and make unique contributions and work with coordination
10. To exhibit confidence in self-education and ability for lifelong learning
11. To develop and manage projects in multidisciplinary environments

CS8381 - DATA STRUCTURES LABORATORY

--- Content provided by​ FirstRanker.com ---

SYLLABUS

COURSE OBJECTIVES

• To implement linear and non-linear data structures
• To understand the different operations of search trees
• To implement graph traversal algorithms

--- Content provided by​ FirstRanker.com ---

• To get familiarized to sorting and searching algorithms

LIST OF EXPERIMENTS:

1. Array implementation of Stack and Queue ADTs
2. Array implementation of List ADT
3. Linked list implementation of Stack, Queue and List ADTs

--- Content provided by⁠ FirstRanker.com ---

4. Applications of List, Stack and Queue ADTs
5. Implementation of Binary Trees and operations of Binary Trees
6. Implementation of Binary Search Trees
7. Implementation of AVL Trees
8. Implementation of Heaps using Priority Queues.

--- Content provided by‍ FirstRanker.com ---

9. Graph representation and Traversal algorithms
10. Applications of Graphs
11. Implementation of searching and sorting algorithms
12. Hashing – any two collision techniques

TOTAL: 60 PERIODS

--- Content provided by‍ FirstRanker.com ---

COURSE OUTCOMES

Upon completion of the course, students will be able to:

• Write functions to implement linear and non-linear data structure operations
• Suggest appropriate linear / non-linear data structure operations for solving a given problem
• Appropriately use the linear / non-linear data structure operations for a given problem

--- Content provided by‍ FirstRanker.com ---

• Apply appropriate hash functions that result in a collision free scenario for data storage and retrieval

CS8381 – DATA STRUCTURES LABORATORY

CONTENTS

Ex. No: 1a

--- Content provided by⁠ FirstRanker.com ---

Date:

IMPLEMENTATION OF STACK ADT

Aim:

To write a C program to implement Stack ADT by using arrays

Algorithm:

--- Content provided by‌ FirstRanker.com ---

1. Create a Stack[ ] with MAX size as your wish.
2. Write function for all the basic operations of stack - PUSH(), POP() and DISPLAY().
3. By using Switch case, select push() operation to insert element in the stack.
   • Step 1: Check whether stack is FULL. (top == SIZE-1)
   • Step 2: If it is FULL, then display "Stack is FULL!!! Insertion is not possible!!!" and terminate the function.
   • Step 3: If it is NOT FULL, then increment top value by one (top++) and set stack[top] to value (stack[top] = value).

   --- Content provided by​ FirstRanker.com ---

4. Similarly, By using Switch case, select pop() operation to delete element from the stack.
   • Step 1: Check whether stack is EMPTY. (top == -1)
   • Step 2: If it is EMPTY, then display "Stack is EMPTY!!! Deletion is not possible!!!" and terminate the function.
   • Step 3: If it is NOT EMPTY, then delete stack[top] and decrement top value by one (top--).

--- Content provided by​ FirstRanker.com ---

5. Similarly, By using Switch case, select display() operation to display all element from the stack.
   • Step 1: Check whether stack is EMPTY. (top == -1)
   • Step 2: If it is EMPTY, then display "Stack is EMPTY!!!" and terminate the function.
   • Step 3: If it is NOT EMPTY, then define a variable 'i' and initialize with top. Display stack[i] value and decrement i value by one (i--).
   • Step 3: Repeat above step until i value becomes '0'.

--- Content provided by​ FirstRanker.com ---

6. Close the program

Sample output:

Enter the size of STACK[MAX=100]:10

STACK OPERATIONS USING ARRAY

1.PUSH

--- Content provided by⁠ FirstRanker.com ---

2.POP

3.DISPLAY

4.EXIT

Enter the Choice:1

Enter a value to be pushed:12

--- Content provided by‌ FirstRanker.com ---

Enter the Choice:1

Enter a value to be pushed:24

Enter the Choice:1

Enter a value to be pushed:98

Enter the Choice:3

--- Content provided by FirstRanker.com ---

The elements in STACK

98

24

12

Press Next Choice

--- Content provided by FirstRanker.com ---

Enter the Choice:2

The popped elements is 98

Enter the Choice:3

The elements in STACK

24

--- Content provided by‌ FirstRanker.com ---

12

Press Next Choice

Enter the Choice:4

EXIT POINT

Result:

--- Content provided by FirstRanker.com ---

Thus the C program to implement Stack ADT by using array is executed successfully and the output is verified.

Program Outcome:

Thus the student can know to implement Linear Data Structure – Stack by using array

Applications:

1. Expression evaluation

--- Content provided by​ FirstRanker.com ---

2. Function call and return process.

Ex. No: 1b

Date:

IMPLEMENTATION OF QUEUE ADT

Aim:

--- Content provided by​ FirstRanker.com ---

To write a C program to implement Queue ADT by using arrays

Algorithm:

1. Create a Queue[ ] with MAX size as your wish.
2. Write function for all the basic operations of stack - Enqueue(), Dequeue() and Display().
3. By using Switch case, select Enqueue() operation to insert element in to the rear/back end of the queue.
   • Check whether queue is FULL. (rear == SIZE-1)

   --- Content provided by‍ FirstRanker.com ---

   • If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and terminate the function.
   • If it is NOT FULL, then increment rear value by one (rear++) and set queue[rear] = value
4. Similarly, by using Switch case, select Dequeue() function is used to remove the element from the front end of the queue.
   • Check whether queue is EMPTY. (front == rear)
   • If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and terminate the function.

   --- Content provided by​ FirstRanker.com ---

   • Step 3: If it is NOT EMPTY, then increment the front value by one (front ++). Then display queue[front] as deleted element. Then check whether both front and rear are equal (front == rear), if it TRUE, then set both front and rear to '-1' (front = rear = -1).
5. Similarly, by using Switch case, select display() operation to display all element of the queue.
   • Step 1: Check whether queue is EMPTY. (front == rear)
   • Step 2: If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function.
   • Step 3: If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front+1'.

   --- Content provided by‌ FirstRanker.com ---

   • Step 3: Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same until 'i' value is equal to rear (i <= rear)
6. Close the program

Output:

1.Insert element to queue

--- Content provided by FirstRanker.com ---

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 1

Inset the element in queue : 10

--- Content provided by⁠ FirstRanker.com ---

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 1

--- Content provided by​ FirstRanker.com ---

Inset the element in queue : 15

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

--- Content provided by‍ FirstRanker.com ---

Enter your choice : 1

Inset the element in queue : 20

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

--- Content provided by‍ FirstRanker.com ---

4.Quit

Enter your choice : 1

Inset the element in queue : 30

1.Insert element to queue

2.Delete element from queue

--- Content provided by​ FirstRanker.com ---

3.Display all elements of queue

4.Quit

Enter your choice : 2

Element deleted from queue is : 10

1.Insert element to queue

--- Content provided by​ FirstRanker.com ---

2.Delete element from queue

3.Display all elements of queue

4.Quit

Enter your choice : 3

Queue is :

--- Content provided by⁠ FirstRanker.com ---

15 20 30

1.Insert element to queue

2.Delete element from queue

3.Display all elements of queue

4.Quit

--- Content provided by‌ FirstRanker.com ---

Enter your choice : 4

Result:

Thus the C program to implement Stack ADT by using array is executed successfully and the output is verified.

Program Outcome:

Thus the student can know to implement Linear Data Structure – Queue by using array

--- Content provided by FirstRanker.com ---

Applications:

1. Queue is used by Operating systems for job scheduling.
2. Queue is used in networking to handle congestion.

Viva Voce:

1. What is linear and Non-linear data structure?

--- Content provided by FirstRanker.com ---

2. What is array?
3. Define ADT.
4. What is Stack and list the operations of stack?
5. What is Queue and list the operations of queue?
6. How the insertion and deletion takes plays in stack?

--- Content provided by‌ FirstRanker.com ---

7. How the insertion and deletion takes plays in queue?
8. What is push in stack?
9. What is pop in stack?
10. What is enqueue?
11. What is dequeue?

--- Content provided by​ FirstRanker.com ---

EX NO: 2

IMPLEMENTATION OF LIST ADT

DATE

Aim:

To write a C program to implement List ADT by using arrays

--- Content provided by⁠ FirstRanker.com ---

Algorithm:

1. Create an array[] with MAX size as your wish.
2. Write function for all the basic operations of list - create(), insert(), deletion(), search(), display().
3. By using Switch case, select create() operation to create the list.
   • List Will be in the form: A1, A2, A3, .... An
   • First Element of the List: A1

   --- Content provided by‍ FirstRanker.com ---

   • Last Element of the List: An
   • ith Element of the List: Ai,
   • Position of Element A¡ : i, Position ranges from 0 to N
   • Size of the List: N
   • Empty List: If Size of the list is Zero (i.e N=0), it is Empty List.

   --- Content provided by‍ FirstRanker.com ---

   • Precedes and Succeeds: For any list except empty list, we say that Ai+1 follows (or succeeds) Ai (i<N) and that Ai-1 precedes Ai (i>1)
4. Similarly, by using Switch case, select insert() operation to insert element in the list.
   • Insert x at position p in list L
   • If p = END(L), insert x at the end
   • If L does not have position p, result is undefined

   --- Content provided by‍ FirstRanker.com ---

5. Similarly, by using Switch case, select delete() function is used to remove the element from the list.
   • delete element at position p in L
   • undefined if p = END(L) or does not exist
6. Similarly, by using Switch case, select search() function is used to retrieve the required element from the list if it is available.
   • returns element at position p on L

   --- Content provided by‍ FirstRanker.com ---

   • undefined if p does not exist or p = END(L)
7. Similarly, by using Switch case, select display() operation to display all element of the list
   • print the elements of L in order of occurrence
8. Close the program

--- Content provided by​ FirstRanker.com ---

Output:

Main Menu

1. Create

2. Delete

3. Search

--- Content provided by⁠ FirstRanker.com ---

4. Insert

5.Display

6.Exit

Enter your Choice: 3

Enter the number of nodes 3

--- Content provided by⁠ FirstRanker.com ---

Enter the element: 67

Enter the element: 69

Enter the element: 71

Do You Want to continue: y

Main Menu

--- Content provided by‍ FirstRanker.com ---

1. Create

2. Delete

3. Search

4. Insert

5.Display

--- Content provided by‍ FirstRanker.com ---

6.Exit

Enter your Choice: 4

Enter the position u need to insert: 2

Enter the element to insert: 56

The list after insertion:

--- Content provided by​ FirstRanker.com ---

The elements of the list ADT are:

67

69

56

71

--- Content provided by‍ FirstRanker.com ---

Do You Want to continue: y

Main Menu

1.Create

2. Delete

3. Search

--- Content provided by‍ FirstRanker.com ---

4. Insert

5.Display

6.Exit

Enter your Choice: 2

Enter the position u want to delete: 2

--- Content provided by FirstRanker.com ---

The elements after deletion: 67 69 71

Do You Want to continue: y

Main Menu

1.Create

2. Delete

--- Content provided by‍ FirstRanker.com ---

3. Search

4. Insert

5.Display

6.Exit

Enter your Choice: 3

--- Content provided by​ FirstRanker.com ---

Enter the element to be searched: 69

Value is in 1 position

Do You Want to continue: y

Main Menu

1.Create

--- Content provided by‌ FirstRanker.com ---

2. Delete

3. Search

4. Insert

5.Display

6.Exit

--- Content provided by​ FirstRanker.com ---

Enter your Choice: 5

The elements of the list ADT are:

67

69

71

--- Content provided by‌ FirstRanker.com ---

Do You Want to continue: N

Result:

Thus the C program to implement List ADT by using array is executed successfully and the output is verified.

Program Outcome:

Thus the student can know to implement Linear Data Structure – List by using array

--- Content provided by‍ FirstRanker.com ---

Applications:

1. It is very much useful in sorting algorithms.
2. Example: Selection sort

Viva Voce:

1. What is array?

--- Content provided by​ FirstRanker.com ---

2. Define ADT.
3. What is List?
4. Differentiate List and Array.
5. What are the different operations involved in List?
6. How the search operation works in list?

--- Content provided by FirstRanker.com ---

7. How will you find the list is full?
8. How will you find the list is empty?
9. Is the list belongs to linear data structure? Justify
10. Differentiate List and Linked list.

Ex. No.: 3a

--- Content provided by FirstRanker.com ---

LINKED LIST IMPLEMENTATION OF STACK ADT

Date:

Aim:

To write a C program to implement Stack ADT by using linked list

Algorithm:

--- Content provided by⁠ FirstRanker.com ---

1. Include all the header files which are used in the program. And declare all the user defined functions.
2. Define a 'Node' structure with two members data and next.
3. Define a Node pointer 'top' and set it to NULL.
4. Implement the main method by displaying Menu with list of operations and make suitable function calls in the main method.
5. push(value) - Inserting an element into the Stack
   • Create a newNode with given value.

   --- Content provided by⁠ FirstRanker.com ---

   • Check whether stack is Empty (top == NULL)
   • If it is Empty, then set newNode ? next = NULL.
   • If it is Not Empty, then set newNode ? next = top.
   • Finally, set top = newNode.

--- Content provided by‌ FirstRanker.com ---

6. pop() - Deleting an Element from a Stack
   1. Check whether stack is Empty (top == NULL).
   2. If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!" and terminate the function
   3. If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'.
   4. Then set 'top = top ? next'.
   5. Finally, delete 'temp' (free(temp)).

   --- Content provided by​ FirstRanker.com ---

7. display() - Displaying stack of elements
   1. Check whether stack is Empty (top == NULL).
   2. If it is Empty, then display 'Stack is Empty!!!' and terminate the function.
   3. If it is Not Empty, then define a Node pointer 'temp' and initialize with top.
   4. Display 'temp ? data --->' and move it to the next node. Repeat the same until temp reaches to the first node in the stack (temp ? next != NULL).

   --- Content provided by​ FirstRanker.com ---

   5. Finally! Display 'temp ? data ---> NULL'.

Output

****** MENU ******

1. Push

--- Content provided by‌ FirstRanker.com ---

2. Pop

3. Display

4. Exit

Enter your choice:1

Enter the value to be insert: 3

--- Content provided by FirstRanker.com ---

Insertion Success

****** MENU ******

1. Push

2. Pop

3. Display

--- Content provided by⁠ FirstRanker.com ---

4. Exit

Enter your choice:1

Enter the value to be insert: 5

Insertion Success

****** MENU ******

--- Content provided by​ FirstRanker.com ---

1. Push

2. Pop

3. Display

4. Exit

Enter your choice:2

--- Content provided by FirstRanker.com ---

Deleted Element: 5

****** MENU ******

1. Push

2. Pop

3. Display

--- Content provided by FirstRanker.com ---

4. Exit

Enter your choice:3

3->?NULL

****** MENU ******

1. Push

--- Content provided by​ FirstRanker.com ---

2. Pop

3. Display

4. Exit

Enter your choice:4

...Program finished with exit code 0

--- Content provided by​ FirstRanker.com ---

Result:

Thus the C program to implement Stack ADT by using linked list is executed successfully and the output is verified.

Program Outcome:

Thus the student can know to implement Linear Data Structure – Stack by using linked list

Applications:

--- Content provided by​ FirstRanker.com ---

1. It is very much useful in memory management

Ex. No.: 3b

Date:

LINKED LIST IMPLEMENTATION OF QUEUE ADT

Aim:

--- Content provided by FirstRanker.com ---

To write a C program to implement Queue ADT by using linked list

Algorithm:

1. Include all the header files which are used in the program. And declare all the user defined functions.
2. Define a 'Node' structure with two members data and next.
3. Define two Node pointers 'front' and 'rear' and set both to NULL.

--- Content provided by FirstRanker.com ---

4. Implement the main method by displaying Menu of list of operations and make suitable function calls in the main method to perform user selected operation.
5. enqueue(value) - Inserting an element into the queue
   • Create a newNode with given value and set 'newNode ? next' to NULL.
   • Check whether queue is Empty (rear == NULL)
   • If it is Empty then, set front = newNode and rear = newNode.
   • If it is Not Empty then, set rear ? next = newNode and rear = newNode.

   --- Content provided by​ FirstRanker.com ---

6. dequeue() - Deleting an Element from queue
   • Check whether queue is Empty (front == NULL).
   • If it is Empty, then display "Queue is Empty!!! Deletion is not possible!!!" and terminate from the function
   • If it is Not Empty then, define a Node pointer 'temp' and set it to 'front'.
   • Then set 'front = front ? next' and delete 'temp' (free(temp)).

   --- Content provided by FirstRanker.com ---

7. display() - Displaying queue of elements
   • Check whether queue is Empty (front == NULL).
   • If it is Empty then, display 'Queue is Empty!!!' and terminate the function.
   • If it is Not Empty then, define a Node pointer 'temp' and initialize with front.
   • Display 'temp ? data --->' and move it to the next node. Repeat the same until 'temp' reaches to 'rear' (temp ? next != NULL).

   --- Content provided by⁠ FirstRanker.com ---

   • Finally! Display 'temp ? data ---> NULL'.

Sample Output

:: Queue Implementation using Linked List ::

****** MENU ******

--- Content provided by​ FirstRanker.com ---

1. Insert

2. Delete

3. Display

4. Exit

Enter your choice: 1

--- Content provided by​ FirstRanker.com ---

Enter the value to be insert: 5

Insertion is Success!!!

****** MENU ******

1. Insert

2. Delete

--- Content provided by FirstRanker.com ---

3. Display

4. Exit

Enter your choice: 1

Enter the value to be insert: 7

Insertion is Success!!!

--- Content provided by FirstRanker.com ---

****** MENU ******

1. Insert

2. Delete

3. Display

4. Exit

--- Content provided by⁠ FirstRanker.com ---

Enter your choice: 2

Deleted element: 5

****** MENU ******

1. Insert

2. Delete

--- Content provided by⁠ FirstRanker.com ---

3. Display

4. Exit

Enter your choice: 3

7 >>> NULL

--- Content provided by‍ FirstRanker.com ---

This download link is referred from the post: Anna University B.Tech Lab Manual