Dsa Algos

(DATA STRUCTURE & ALGORITHMS) ALGOS IMPLEMENTATION INTO C++

SUBMITTED BY:-

ABID QA DOO S

SUBMITT ED TO:-

MR. NAUMAN QADIR SB

Data structure In programming, the term data structure refers to a scheme for organizing related pieces of information. The basic types of data structures include: 1. files 2. lists 3. arrays 4. records 5. trees 6. tables 7. Each of these basic structures has many variations and allows different operations to be performed on the data. data structure (′dad·ə ′strək·chər) (computer science) A collection of data components that are constructed in a regular and characteristic way.

data structure The physical layout of data. Data fields, memo fields, fixed length fields, variable length fields, records, word processing documents, spreadsheets, data files, database files and indexes are all examples of data structures.

data structure Way in which data are stored for efficient search and retrieval. The simplest data structure is the one-dimensional (linear) array, in which stored elements are numbered with consecutive integers and contents are accessed by these numbers. Data items stored nonconsecutively in memory may be linked by pointers (memory addresses stored with items to indicate where the "next" item or items in the structure are located). Many algorithms have been developed for sorting data efficiently; these apply to structures residing in main memory and also to structures that constitute information systems and databases.

Introductions to Data Structures Definition of data structures 1• Many algorithms require that we use a proper representation of data to achieve efficiency. 2• This representation and the operations that are allowed for it are called data structures. 3• Each data structure allows insertion, access, deletion etc.

Why do we need data structures? 1• Data structures allow us to achieve an important goal: component reuse 2• Once each data structure has been implemented once, it can be used over and over again in various applications. Common data structures are 1• Stacks 2• Queues 3• Lists 4• Trees 5• Graphs 6• Tables 1• Def 1: Implementation independent data description that specifies the contents, structure and legal operations on the data. 1• Def 2: data structure and a set of operations which can be performed on it. A class in object-oriented design is an ADT. However, classes have additional properties (inheritance and polymorphism) not normally associated with ADTs

array In programming, a series of objects all of which are the same size and type. Each object in an array is called an array element. For example, you could have an array of integers or an array of characters or an array of anything that has a defined data type. The important characteristics of an array are: Each element has the same data type (although they may have different values). •

The entire array is stored contiguously in memory (that is, there are no gaps between elements). 2Arrays can have more than one dimension. A one-dimensional array is called a vector ; a two-dimensional array is called a matrix.

ar·ray (ə-rā') tr.v., -rayed, -ray·ing, -rays. 1. To set out for display or use; place in an orderly arrangement: arrayed the whole regiment on the parade ground. 2. To dress in finery; adorn. n. 1. An orderly, often imposing arrangement: an array of royal jewels. 2. An impressively large number, as of persons or objects: an array of heavily armed troops; an array of spare parts. See synonyms at display. 3. Splendid attire; finery. 4. Mathematics. a. A rectangular arrangement of quantities in rows and columns, as in a matrix.

b. Numerical data linearly ordered by magnitude. 5. Computer Science. An arrangement of memory elements in one or more planes.

linked list In data management, a group of items, each of which points to the next item. It allows for the organization of a sequential set of data in noncontiguous storage locations. The following code would traverse the list and display names and account balance:

tree structure A type of data structure in which each element is attached to one or more elements directly beneath it. The connections between elements are called branches. Trees are often called inverted trees because they are normally drawn with the root the top.

at

The elements at the very bottom of an inverted tree (that is, those that have no elements below them) are called leaves. Inverted trees are the data structures used to represent hierarchical file structures. In this case, the leaves are files and the other elements above the leaves are directories. A binary tree is a special type of inverted tree in which each element has only two branches below it.

TABLE Refers to data arranged in rows and columns. A spreadsheet, for example, is a table. In relational database management systems, all information is stored in the form of tables.

TRAVERSING TRAVERSE ( A , LB , N ) Here we have an array “A” with lower bound “ LB” and “N” number of elements. This algo will perform traversing in array “A”. Step # 1.

Repeat For ( I = LB to N+LB-1) (a) PROCESS A[I]

(b) END OF LOOP (OPTIONAL) Step # 2

EXIT

INSERTION Insertion ( A , LB , N , K , ITEM , SIZE ) Here we have an array “A” with its lower bound “LB” and “N” are its no of elements. “SIZE” is the possible size of array “A”. “ITEM” is the element we want to insert and “K” is the position where insertion take place. This algo will perform insertion. Step # 1

IF (( N=SIZE) || (KN+LB)) a. DISPLAY(“ INSERTION CAN NOT TAKE PLACE”) b. EXIT

Step # 2

REPEAT FOR ( I = N+LB-1 DOWN TO K) a. A[I+1]=A[I] b. A[K]=ITEM

Step # 3

N=N+1

Step # 4

EXIT

DELETION DELETION ( A , LB , N , K , ITEM ) Here we have an array “A” with its lower bound “LB” and “N” are its no of elements. “SIZE” is the possible size of array “A”. “ITEM” is the element we want to delete and “K” is the position where deletion take place. This algo will perform deletion. Step # 1

IF ((KN+LB-1)) c. DISPLAY(“ DELETION CAN NOT TAKE PLACE”)

d. EXIT Step # 2

ITEM =

A[K]

Step # 3

REPEAT FOR ( I = ( K + 1) TO N+LB-1) c. A[I-1]=A[I]

Step # 4

N=N-1

Step # 5

EXIT

SEARCHING LINEAR SEARCH SINGLE LINEAR_SEARCH_SINHLE ( A , LB , N , ITEM) Here we have an array “A” with its lower bound “LB” and “N” are its no of elements. “SIZE” is the possible size of array “A”. “ITEM” is the element we want to search. This algo will perform linear single search. Step # 1

REPEAT (FOR I= LB TO N+LB-1) a. IF (A[I]==ITEM )

.I DISPLAY(“ ITEM FOUND”) .II EXIT .b DISPLAY(“ITEM NOT FOUND”) Step # 2

EXIT

LINEAR SEARCH MULTIPLE LINEAR_SEARCH_MULTIPLE ( A , LB , N , ITEM , K) Here we have an array “A” with its lower bound “LB” and “N” are its no of elements. “SIZE” is the possible size of array “A”. “ITEM” is the element we want to search. This algo will perform linear multiple search n array “A”. Step # 1

INITIALIZE COUNT = 0

Step # 2

REPEAT (FOR I= LB TO N+LB-1) a. IF (A[I]==ITEM )

.I COUNT=COUNT + 1 Step # 3

IF (COUNT==0) a

DISPLAY(“ITEM NOT FOUND”)

ELSE DISPLAY(“ITEM FOUND”) DISPLAY(‘COUNT’) Step # 4

EXIT

SEARCHING BINARY SERACH SINGLE ASCENDING BINARY_SERACH_SINGLE ( A,LB,N,ITEM) Here we have an array “A” with its lower bound “LB” and “N” are its no of elements. “SIZE” is the possible size of array “A”. “ITEM” is the element we want to search. This algo will perform binary single search in ascending order. Step # 1.

INTIALIZE BEG = LB

Step # 2

INTIALIZE END = N + LB – 1

Step # 3

REPEAT a

WHILE ( BEG <= END)

MIDPOS = (BEG + END) / 2

b IF ( A [MIDPOS] < ITEM ) BEG=MIDPOS+1 c

ELSE IF ( A[MIDPOS] > ITEM) END = MIDPOS – 1

d ELSE i. DIPLAY (“ ITEM FOUND”) ii. DISPLAY (‘ MIDPOS’) iii. EXIT STEP #4

DISPLAY (“ ITEM NOT FOUND”)

STEP # 5

EXIT

BINARY SERACH SINGLE DESCENDING BINARY_SERACH_SINGLE ( A,LB,N,ITEM) Here we have an array “A” with its lower bound “LB” and “N” are its no of elements. “SIZE” is the possible size of array “A”. “ITEM” is the element we want to search. This algo will perform binary single search in descending order. Step # 1.

INTIALIZE BEG = LB

Step # 2

INTIALIZE END = N + LB – 1

Step # 3

REPEAT

WHILE ( BEG <= END)

e

MIDPOS = (BEG + END) / 2

f

IF ( A [MIDPOS] > ITEM ) BEG=MIDPOS+1

g ELSE IF ( A[MIDPOS] < ITEM) END = MIDPOS – 1 h ELSE i. DIPLAY (“ ITEM FOUND”) ii. DISPLAY (‘ MIDPOS’) iii. EXIT STEP #4

DISPLAY (“ ITEM NOT FOUND”)

STEP # 5

EXIT

SEARCHING BINARY SERACH MULTIPLE ASCENDING BINARY_SERACH_MULTIPLE ( A,LB,N,ITEM,K) Here we have an array “A” with its lower bound “LB” and “N” are its no of elements. “SIZE” is the possible size of array “A”. “ITEM” is the element we want to search. This algo will perform multiple binary search in ascending order. Step # 1.

INTIALIZE

BEG = LB

Step # 2

INTIALIZE

END = N + LB – 1

INITIALIZE COUNT = 0 Step # 3

REPEAT

WHILE ( BEG <= END)

MIDPOS = (BEG + END) / 2 a

IF ( A [MIDPOS] < ITEM ) BEG=MIDPOS+1

b

ELSE IF ( A[MIDPOS] > ITEM) END = MIDPOS – 1

c

ELSE (1)

COUNT = 1

(2)

I =MIDPOS – 1

(3)

REPEAT WHILE ( A[I] = ITEM)

COUNT = COUNT + 1 I= I - 1 (4)

J = MIDPOS + 1

(5)

REPEAT WHILE ( A[I] = ITEM)

COUNT = COUNT + 1 J=J+1 (6)

DISPLAY (“ ITEM FOUND”)

(7)

DISPLAY (‘COUNT’)

(8)

EXIT

STEP #4

DISPLAY (“ ITEM NOT FOUND”)

STEP # 5

EXIT

BINARY SERACH MULTIPLE DESCENDING BINARY_SERACH_MULTIPLE ( A,LB,N,ITEM,K) Here we have an array “A” with its lower bound “LB” and “N” are its no of elements. “SIZE” is the possible size of array “A”. “ITEM” is the element we want to search. This algo will perform binary multiple search in descending order. Step # 1.

INTIALIZE

BEG = LB

Step # 2

INTIALIZE

END = N + LB – 1

INITIALIZE COUNT = 0 Step # 3

REPEAT

WHILE ( BEG <= END)

MIDPOS = (BEG + END) / 2 d IF ( A [MIDPOS] > ITEM ) BEG=MIDPOS+1 e

ELSE IF ( A[MIDPOS] < ITEM) END = MIDPOS – 1

f

ELSE (1)

COUNT = 1

(2)

I =MIDPOS – 1

(3)

REPEAT WHILE ( A[I] = ITEM)

COUNT = COUNT + 1 I= I - 1 (4)

J = MIDPOS + 1

(5)

REPEAT WHILE ( A[I] = ITEM)

COUNT = COUNT + 1 J=J+1 (6)

DISPLAY (“ ITEM FOUND”)

(7)

DISPLAY (‘COUNT’)

(8)

EXIT

STEP #4

DISPLAY (“ ITEM NOT FOUND”)

STEP # 5

EXIT

SORTING MERGING MERGING ( A , B , C , LBA , LBB , LBC , NA , NB ) Here we have an array “A” , “B” & “C” with their lower bounds “LBA” , “LBB” & “LBC” respectively. “NA” are the number of elements of array “A”, “NB” of array “B” . This algo will perform merging of array “A” & array “B” in array “C”. Step # 1

INITIALIZE

PTRA

=

LBA

Step # 2

INITIALIZE

PTRB

=

LBB

Step # 3

INITIALIZE

PTRC

= LBC

Step # 4

REPEAT WHILE ( PTRA<= LBA+NA-1) && ( PTRB <= LBB+NB-1) a

IF ( A[PTRA] < B[PTRB]) i. C[PTRC=A[PTRA] ii. PTRA=PTRA + 1 ELSE i. C[PTRC]= B[PTRB] ii. PTRB=PTRB + 1

b PTRC = PTRC + 1 Step # 5

IF ( PTRA > NA+LBA -1) a

REPEAT WHILE ( PTRB<= NB + LBB -1 i. C[PTRC]=B[PTRB] ii. PTRB = PTRB + 1 iii. PTRC = PTRC +1 ELSE

b REPEAT WHILE PTRA<= NA+LBA-1 i. C[PTRC] = A[PTRA]

Step # 6

EXIT

ii. PTRC

=

PTRC+1

iii. PTRA

= PTRA +1

SORTING BUBBLE SORT BUBBLE_SORT ( A , LB , N ) Here we have an array “A” with its lower bound “LB” and “N” number of elements. This algo will perform bubble sorting in array “A”. Step # 1

LAST = N + LB – 1

Step # 2

REPEAT FOR ( I= 1 TO N-1) a

REPEAT FOR ( J = LAB TO LAST – 1 ) IF ( A[J]> A[J+1]) A[J]

b Step # 3

LAST

A [J+1] = LAST – 1

EXIT

SELECTION SORT SELECTION_SORT ( A , LB , N ) Here we have an array “A” with its lower bound “LB” and “N” number of elements. This algo will perform selection sorting in array “A”. Step # 1.

REPEAT FOR ( I = LB TO N + LB -1 ) a

MINLOC = I

b REPEAT FOR ( J = I + 1 TO N + LAB - 1 ) i. IF ( A[MINLOC] > A [ J ] ) ii. MINLOC C A[ I ] Step # 2

EXIT

A[MINLOC]

=J

SHELL SORT SHELL_SORT(A,LB,N) Here we have an array “A” with lower bound “ LB” and “N” number of elements. This algo will perform shell sorting in array “A”.

STEP # 1.

GAP

INT ( N/2 )

STEP # 2

REPEAT WHILE (GAP#0) (c) EXCHANGE

0

(d) REPEAT WHILE (EXCHANGE # 0)

1. EXHANGE

0

2. REPEAT FOR I = (LB TO (N+LB-1) – GAP) a. IF (A[I] > A[I+GAP] i. A[I] ii. EXCHANGE (e) GAP=INT(GAP/2) STEP # 3

EXIT

A[I + GAP ] 1

INSERTION SORT INSERTION_SORT (A,LB,N) Here we have an array “A” with lower bound “ LB” and “N” number of elements. This algo will perform insertion sorting in array “A”.

STEP # 1.

REPEAT FOR ( LAST =LB +1 TO (N+LB-1)) (a) TEMP

A[LAST]

(b) PTR

LAST - 1

(c) REPEAT WHILE ((TEMP=LB) 1. A[PTR + 1] 2. PTR

PTR - 1

(d) A[PTR + 1] STEP # 2

A[PTR]

TEMP

EXIT

SINGLE LINK LIST

1. TRAVERSING STEP # 1.

IF (START=NULL) a) LINK LIST EMPTY b) EXIT.

STEP #2.

PTR START

STEP #3

WHILE (PTR#NULL) a) PROCESS (PTR->INFO) b) PTRPTR->NEXT

STEP #4

EXIT.

2. INSERTION AT FIRST STEP #1

PTR MEMORY ALLOCATE FOR NEW ELEMENT

STEP #2

PTR->INFO  ITEM

STEP #3

PTR-> NEXT  START

STEP #4

START  PTR

3. INSERTION AT LAST STEP #1

PTR MEMORY ALLOCATE FOR NEW ELEMENT

STEP #2

PTR->INFO  ITEM

STEP #3

PTR-> NEXT = NULL

STEP #4

PTR1  START

STEP #5

WHILE (PTR1 -> NEXT # NULL) a) PTR1 PTR1 -> NEXT

STEP #6

PTR1 -> NEXT  PTR

STEP #7

EXIT

4. INSERTION IN MIDDLE (BEFORE GIVEN NODE) STEP #1

PTR1 MEMORY ALLOCATE FOR NEW ELEMENT

STEP #2

PTR1->INFO  ITEM

STEP #3

PTR1-> NEXT = NULL

STEP #4

PTR2  START

STEP #5

WHILE (PTR2 -> NEXT # PTR) b) PTR2 PTR2 -> NEXT

STEP #6

PTR2 -> NEXT  PTR1

STEP #7

EXIT

5. AFTER GIVEN NODE STEP #1

PTR1 MEMORY ALLOCATE FOR NEW ELEMENT

STEP #2

PTR1->INFO  ITEM

STEP #3

PTR1-> NEXT  PTR->NEXT

STEP #6

PTR -> NEXT  PTR1

STEP #7

EXIT

DELETION 6. AT FIRST NODE STEP #1

IF (START = NULL) a) DISPLAY(“ LINK LIST EMPTY”) b) EXIT

STEP #2

PTR  START

STEP #3

START  START ->NEXT

STEP #4

ITEM  PTR -> INFO

STEP # 5

DIS ALLOCATE MEMORY OCCUPIED BY PTR.

STEP #6

EXIT

7. AT LAST NODE STEP #1

IF (START = NULL) c) DISPLAY(“ LINK LIST EMPTY”) d) EXIT

STEP #2

PTR  START

STEP #3

WHILE (PTR -> NEXT -> NEXT # NULL)

a) PTR  PTR -> NEXT. STEP #4

PTR1  PTR -> NEXT

STEP # 5

PTR -> NEXT = NULL

STEP # 6

ITEM  PTR1 -> INFO

STEP # 5

DIS ALLOCATE MEMORY OCCUPIED BY PTR.

STEP #6

EXIT

DOUBLE LINK LIST 8. TRAVERSING FORWARD STEP # 1.

IF (START=NULL) a) LINK LIST EMPTY b) EXIT.

STEP #2.

PTR START

STEP #3

WHILE (PTR#NULL) a) PROCESS (PTR->INFO) b) PTRPTR->NEXT

STEP #4

EXIT.

9. TRAVERSING BACKWARD STEP # 1.

IF (START=NULL) a) LINK LIST EMPTY b) EXIT.

STEP #2.

PTR START

STEP #3

WHILE (PTR#NULL) a) PTRPTR->NEXT

STEP # 4

PTR1START

STEP #5

REPEAT WHILE (PTR1->BACK #NULL) a) PROCESS PTR1->INFO b) PTR1PTR->BACK

STEP #4

EXIT.

10. INSERTION AT LAST STEP #1

PTR MEMORY ALLOCATE FOR NEW ELEMENT

STEP #2

PTR->INFO  ITEM

STEP #3

PTR-> NEXT = NULL

STEP #4

PTR1  START

STEP #5

WHILE (PTR1 -> NEXT # NULL) e) PTR1 PTR1 -> NEXT

STEP #6

PTR1 -> NEXT  PTR

STEP #7

PTR -> BACK  PTR1

STEP #7

EXIT

DELETION 11. AT LAST NODE STEP #1

IF (START = NULL) f) DISPLAY(“ LINK LIST EMPTY”) g) EXIT

STEP #2

PTR  START

STEP #3

WHILE (PTR -> NEXT -> NEXT # NULL) b) PTR  PTR -> NEXT.

STEP #4

PTR1  PTR -> NEXT

STEP # 5

PTR -> NEXT = NULL

STEP # 6

ITEM  PTR1 -> INFO

STEP # 5

DIS ALLOCATE MEMORY OCCUPIED BY PTR.

STEP #6

EXIT