Scribd
Upload
45 views2 pages

Sem 3 DS

The document discusses different data structures including linear data structures like arrays, linked lists, stacks and queues as well as non-linear data structures like trees and graphs. It also discusses abstract data types, array implementation of lists, linked lists using nodes, free pools, garbage collection, infix to postfix conversion, postfix evaluation using stacks, circular queues, binary tree traversals and representations.

Uploaded by

The Smart Boy KungFuPawn
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
45 views2 pages

Sem 3 DS

The document discusses different data structures including linear data structures like arrays, linked lists, stacks and queues as well as non-linear data structures like trees and graphs. It also discusses abstract data types, array implementation of lists, linked lists using nodes, free pools, garbage collection, infix to postfix conversion, postfix evaluation using stacks, circular queues, binary tree traversals and representations.

Uploaded by

The Smart Boy KungFuPawn
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 2

Data Structure - Storing, Organising, Retrieving

DS
-Primitive(basic)
=> int, char, float
-Non Primitive(derived)
-Linear(using either sequential memory location or links)
=> arrays, linked lists, stacks, queues
-Non Linear(hierarchical and no adjacency relationship)
=> trees, graphs

ADTs - Abstract Data Types


-mathematical model or user defined type
-know data & operations but don't know implementation details
=> lists, sets, graphs, trees
advantage - modularity

Array - Fixed size, Continuous memory locations

insert(ele, index)
delete(ele)

Implementation of List ADT


- Array based (better performance)
- Linked List based (linear, dynamic)
- Cursor based

Linked List contains a START pointer which stores addr of 1st node.
the NEXT pointer stores addr of next node.
for last node NEXT pointer contains NULL

Free pool - List of free memory cells or available space

the AVAIL pointer stores addr of first free space in free pool

Garbage Collection - collecting all unused cells and adding their addr to the free
pool

Infix to Postfix
----------------
Array - Operand
Stack - Operator
Higher priority operators can be placed above Lower priority operators

Postfix Evaluation
------------------
Stack - Operand

Circular queue
Insertion - rear pointer position
rear = (rear+1)%max_size
Queue[rear]
Deletion - front pointer position
Value = Queue[front]
front = (front+1)%max_size

void inorder(Tree T)
{
if(T!=NULL)
{
inorder(T->left);
printf(T->data); //root
inorder(T->right);
}
}

inorder - Left Root Right


preorder - Root Left Right
postorder - Left Right Root

Full binary tree - 2 or more child


Perfect binary tree - 2 child, all leaf nodes at same lvl
Complete binary tree - all lvls filled except leaf level

linear representation of binary tree using array


for element in position i
left child position = 2i
right child position = 2i+1
parent position = i/2

expression tree - binary tree


leaf nodes - operands
interior nodes - operators

You might also like