Dsajour 4 - dsa PDF

Preview

Summary

dsa...

Description

Lab Journal – Lab 4

Data Structures and Algorithms Lab Journal - Lab 4 Name:

_SAQIB PERVAIZ__________________

Enrollment #: __01-235181-053__ _______________ Class/Section: _________________________________ Objective This lab session is aimed at enhancing the algorithmic development skills of the students by writing small utility functions for linked lists. Exercises Implement the following exercises. Exercise 1 Create an organized linked list in ascending order i.e., all the entries should be added in the list in ascending order. In order to do so the insert(int value) member function must be modified in the linked list class. An illustration of the working of the program is presented in the following. List list ; list.insert (5) ; list.insert (2) ; list.insert (7) ; list.insert (3) ; List.cpp

//5 //2 5 //2 5 7 //2 3 5 7

void List::insert_org(int value) { if (isEmpty()) insert_beg(value); else { bool flag; Node* temp = head; Node* tempaddr = temp; while (temp != NULL) {

Data Structures and Algorithms

Page 1

Lab Journal – Lab 4 if (value > temp->getdata()) { flag = true; tempaddr = temp; if ((value - temp->getdata()) < 0) break; } if (value < temp->getdata()) { flag = false; tempaddr = temp; if ((temp->getdata() - value) < 0) break; } temp = temp->getnext(); } if (flag) insert_after(tempaddr->getdata(), value); else insert_beg(value); } }

Exercise 2 Write following Non-member (stand-alone) C++ functions to perform following: a. Concatenate two lists of characters together. b. Find intersection of two lists. c. Compare two strings (represented as linked lists) . The function should take two linked lists containing characters of two strings and compare each corresponding character in a lexicogrphical order. The function should return: -

0 if both strings are same

-

1 if first list is lexicographically greater

-

-1 if second string is lexicographically greater

2. bool ispresent(Node *head, type data) { Node *temp = head; while (temp!=NULL) { if (temp->data == data) return true; temp = temp->next; }

Data Structures and Algorithms

Page 2

Lab Journal – Lab 4 return false; }

void unionList(Node *h1, Node *h2) { Node *t1 = h1; Node *t2 = h2; List result; while (t1 != NULL) { result.insert_end(t1->data); t1 = t1->next; } while (t2 != NULL) { if (!ispresent(result.head, t2->data)) result.insert_end(t2->data); t2 = t2->next; } }

3. bool ispresent(Node *head, type data) { Node *temp = head; while (temp!=NULL) { if (temp->data == data) return true; temp = temp->next; } return false; }

void intersection(Node *h1, Node *h2) { Node *t1 = h1; Node *t2 = h2; List result; while (t1!=NULL) { if (ispresent(h2, t1->data)) result.insert_end(t1->data); t1 = t1->next; } } int compare(List a, List b)

Data Structures and Algorithms

Page 3

Lab Journal – Lab 4 { Node *p1 = a.gethead(); Node *p2 = a.gethead(); while (p1 != NULL && p2 != NULL) { if (p1->data == p2->data) continue; else break; } if (p1->data > p2->data) return 1; else if (p1->data < p2->data) return -1; else return 0; }

Implement the given exercises and get them checked by your instructor. S No. 2.

Exercise Exercise 1

3.

Exercise 2a.

4.

Exercise 2b.

5.

Exercise 2c.

Checked By:

+++++++++++++++++++++++++

Data Structures and Algorithms

Page 4...