Transcript List

CSC 313 Data Structures And
Algorithms
Supplementary Lecture Note
by
Aborisade D.O.
Course Contents
•
•
•
•
•
•
•
•
List
Linked List
Application of Linked List
Stack and Its Applications
Queues and its Applications
Recursion and its Applications
Trees and Binary Trees
References
List
• List of various kinds exist in everyday life. List of HOD’s, list of
Deans, appointment list, mailing list class list, e.t.c. These list
have a common feature that motivate its definition as the
Abstract data type (ADT) which is a finite sequence (ordered
set) of elements (which could be empty). Data structure like
Stacks, queue, deques are special kinds of lists.
• ADT List Basic operation:
Construction: creating an empty
Empty: Check if the list is empty
Traverse: Go through the list or part of it, accessing and
processing the elements in order.
Insert: Add an item at any point in the list
Delete: Remove am item from the list at any point in the list
List
• Storage Structure of List
a1
a[0]
a2
a3
……..,
an
a[1]
a[2]
……….. a[n-1]
a[n]
…………………………………………..a[CAPACITY-1]
This implementation of a list is referred to as
sequential-storage implementation.
List
For Construction: Using an array to store the list
elements, we use compiler to allocate memory for it.
For Empty: We need to check mySize is 0.
For Traverse: Lists are traversed using a loop in which
the array or vector index varies e.g
for(int i=0;i<mySize; i++)
Process(myArray[i]);
• For Insert: Suppose we wish to insert the new value
56 after the element 48 in the integer list
List
23, 25, 34, 48,61,79,82,89,91,99
to produce the new list
23, 25,34,48,56,61,79,82,89,91,99 it is somewhat
complicated to insert, because of the fixed size of the
array used as the storage structure limits the size of the
list. Therefore, to insert a new item it would be
necessary to move array elements to make room for it.
For Delete: Implementing the delete operation also
requires shifting array elements if list elements are to
be stored in consecutive array locations.
List
23 25 34 48 61 79 82 89 91 99
23 25 34 48 56 61 79 82 89 91 99
23 25 34 48 56 61 79 82 89 91 99
23 34 48 56 61 79 82 89 91 99
Linked List
• The need to shift elements from one position to the
other in the list when items are inserted or deleted
has been observed to be responsible for the
inefficiency of the sequential-storage
implementation for dynamic list. An alternative way
to implement list to eliminate this inefficiency is the
Linked list.
• A linked-list is an ordered collection of elements
called nodes, each of which has two parts:
Linked list
- a data part that stores an element of the list.
- a next part that stores a link or pointer that indicates the
location of the node containing the next list element. If
there is no next element then a null value is used e.g to
represent
9, 17, 22, 26,34 can be represented as follows:
data
first
9
next
17
22
26
34
Linked list
• A linked list could also be described as list whose
nodes contain two fields: an integer value and a link
to the next node, whereby the last node is linked to a
terminator used to signify the end of the list.
15
12
38
X
• Doubly Linked list: is a linked list whose nodes
contain three fields namely an integer value, the link
forward, and the link backward to the previous node.
Doubly linked list
X
40
31
50
X
Multiply Linked list: Each node contains two or more link
fields, each field being used to connect the same set of data
records in a different order (e.g., by name, by department,
by date of birth, etc.). (While doubly linked lists can be seen
as special cases of multiply linked list, the fact that the two
orders are opposite to each other leads to simpler and
more efficient algorithms, so they are usually treated as a
separate case.)
Multiply(Multi-linked list)
• Doubly-linked lists are a special case of Multi-linked lists;
it is special in two ways: (1) each node has just 2
pointers. (2)the pointers are exact inverses of each other
• In multiply (or multi- linked list) each node can have any
number of pointers to other nodes, and there may or
may not be inverses for each pointer.
• Multi-linked list is to organize a collection of
elements in two different ways. For example,
suppose my elements include the name of a person
and his/her age. e.g. (FRED,19) (MARY,16) (JACK,21)
(JILL,18)
Multi linked list to order Name and Age
Multi linked list for Sparse Matrix
X=1 2 3
---------Y=1 | 0 88 0
Y=2 | 0 0 0
Y=3 | 27 0 0
Y=4 | 19 0 66
Multi linked list-Sparse Matrix
• The sparse matrix is represented by having linked
lists for each row and each column. Because each
node is in exactly one row and one column it will
appear in exactly two lists - one row list and one
column. So it needs two pointers: Next-in-this-row
and Next-in-this-column.
Multi linked list-Sparse Matrix
Stack attributes
• Is a LIFO data structure
• Stack functions in the following ways;
(i) If an item is added to the stack, those below are
pushed down and cannot be accessed.
(ii) If an item is removed from the stack, those below it
are poped up by one position.
(iii) The stack becomes empty when there is no item in
it.
(iv) The stack is full if there is no room in it for anymore
item.
Stack-OPERATIONS
Basic operations in stack includes:
Construct: Build or design a stack
Check: Find out if a stack is empty.
Push: Add an item to a stack.
Pop: Remove an item from a stack.
Top: Retrieve the top element of stack
Construction for the stack class
class Stack
{
/**********Function Members *****/
public:
/*----------Constructor-----* Precondition: A stack has been declared.
* Postcondition: The stack has been constructed as an empty stack
*********************************************************
Stack();
/**********Data Members*************/
private:
StackElement myArray[STACK_CAPACITY];
Int myTop;
//--------Definition of Class Constructor
inLine Stack: : Stack()
{myTop=-1}
#endif
Stack-Application Areas
• Function calls
• Reverse Polish Notation
Queues
• A queue is a “waiting line” such as;
- a line of persons waiting to check out at a
supermarket.
-a line of vehicles at a toll gate.
-a line of planes waiting to land at airport e.t.c.
In each of the above, the items are serviced in the
order in which they arrive. Hence, it FIFO or FCFS. In a
queue, insertion and deletion are restricted to the ends
of the list. The items are removed from a queue at the
end called the front(head) and elements are added
only at the other end called back(tail or rear)
Queues operations
•
•
•
•
Construct a queue.
Check if a queue is empty.
AddQ: Add an item at the back of a queue.
Front: Retrieve the element at the front of the
queue.
• RemoveQ: Remove the element at the font of the
queue.
• Deque: is a double-ended queue. It is the data
structure where insertions and deletion takes place
at both ends.
Application areas
Queue:
• Information Centre Simulation
Deque:
* Scrolling of windows
* Entering of data through keyboard and deleting it
with backspace.
Queue-Algorithm
• Algorithm for Arrival of New Call
1. Generate a random integer x in the range 0 to 100.
2. If x<simVals.arrivaRate
a. Increment simVals.callsReceived by 1
b. Generate a new random number x.
c. Set i to 1
d. While x> simVals.servicePercent(i)
Increment i by 1
e. Construct the newCall with its timeOfArrival initialized to
t.Minutes() and its serviceTime initialized to i.
f. Add newCall to the incomingCalls queue.
Recursion
• Recursion is a programming concept whereby a
function is made to call itself.
• Types of recursion are:
- Direct recursion: where a function calls itself.
- Indirect recursion: where a function is called is
called by the chains of function calls initiated by
itself.
A common example is the program for calculating a
factorial of a number.
Recursion-Application areas
-
Some of the application areas include:
Binary Search:
Palindrome Checker: Palindrome Number e.g
8504058, 5665 and 33
Towers of Hanoi
Parsing
Recursion-Algorithm
Algorithm for Recursive Palindrome Checker
1. If numDigits ≤ 1
Return the value true
2. Divide number by 10 numDigits-1 to obtain firstDigit.
3. Set lastDigit equal to number % 10
4. If firstDigit ≠last Digit
Return the value false
5. Apply the algorithm recursively to number with firstDigit and
lastDigit removed that is, to Number % 10numberDigit-1/10, and
numDigits-2.
Trees
• A tree is made up of a finite set of elements called
nodes or vertices and a finite set of directed arcs
that connect pairs of nodes. It is a data structure that
is suitable for modeling hierarchical data.
1
3
2
4
5
9
6
7
8
8
Trees
• 9 Vertices (Vertex 1= Root)
• Leaves( Vertex with no outgoing arc).
• Children (Nodes that are directly accessible from a
given node with only one directed arc).
• Parent (Nodes from which a child or children
emanate).
• Siblings (Nodes or vertices of the same parent).
Binary Trees
• Trees in which each node has at most two children
are called Binary Trees. They can be used to solve a
variety of problems.
• They are mostly used in modeling processes in which
some experiments or tests with two possible
outcomes (e.g off or on, 0 or 1, false or true, down or
up) is performed repeatedly. An example is the
possible outcomes of flipping a coin three times.
Binary Tree
As Recursive Data Structure:
Owing to the recursive nature of Binary Tree, many
basic operations can be simply performed on it using
recursive algorithms e.g using NLR(Preorder) while
traversing.
where N means Visit the root and process the data in it.
L MEANS traverse the left subtree of a node, and R
means traverse the right subtree of a node. We also
have LNR (Inorder), and LRN (Postorder).
Binary Trees
• Example: Represent the binary tree (expression tree)
below in its (i) inorder (ii) preorder and (iii) postorder
traversal.
+
D
-
A
*
B
C
Binary tree-Solution
• Inorder traversal: A-B*C+D
• Preorder traversal: +-A*BCD
• Postorder traversal: ABC*-D+
References
• Malik, D.S.: Data Structures using C++ 2ND
Edition. 2009.
• Clliford, A.S :Data Structures and Algorithm
Analysis Using C++ (Third Edtion).