Transcript The Program Life Cycle. - Concordia University Wisconsin

Day 14.
0. Questions on Assignment 4?
1. Linked list concept.
2. Linked implementation of a Queue.
3. What does .NET provide?
0. Questions on assignment 4?
My advice:
Develop your solution incrementally.
First make sure you have all of the data
members and member methods you need.
Add to TempQueue.cs
Then devise a simulation algorithm.
Modify Queue_Driver.cs
1. Linked List concept.
 So far we have focused on the use of an
array as the container for a data structure.
 Arrays are easy to use, but have some
disadvantages.
 Discuss.
 1) How big?
 2) The problem of contiguous storage.
Dynamic nodes.
 Rather than use contiguous storage like an
array, it is possible to store each element in
its own memory location. The elements
might happen to be contiguous, but don’t
have to be.
 See diagram.
A problem.
If we simply allocate elements, noncontiguously, what difficulty do we face?
This is particularly bad for stacks and queues,
because in both cases, the order matters.
On a stack, data is arranged from newest
(Top) to oldest (bottom).
Likewise in a queue, the Front is oldest and
the Rear is newest.
We need a system to maintain the
order of the data.
We need at least one way into the list from the
outside (an external pointer).
The nodes of the list should be “intelligent.”
They will contain not only data (“Info”)
but also a pointer to the next node in the
list (“Next”).
See diagram.
The null concept.
We also need to know if a linked list is empty,
or if we have reached the end of a list.
For this purpose, we can use the keyword
“null,” which means “no valid address.”
It is important to avoid doing something to a
pointer set to null. Why?
Uses of linked lists.
Linked lists are just as versatile as arrays.
Obviously, they can be used to implement a
standard list. But also:
We can use them to define a stack, and then
do Push and Pop dynamically (i.e. the
stack literally shrinks and grows).
See diagram.
Uses of linked lists.
We can also use a linked list to define a
queue, and then do Enq and Deq
dynamically.
For this, notice that we will need 2 external
pointers to the linked list, Front and Rear.
See diagram.
2. Linked implementation of a
queue.
See LinkedQueue.cs
First we need to define a Node class.
Within the class we have Info to hold data and Next
as a pointer.
What is bizarre about the definition of “Next”?
There is also a constructor used to fill in a node’s
Info and Next when the node is created by Enq.
Data members.
The Linked_Queue class has 2 external
pointers: Front and Rear, both of type
Node.
NumberElements keeps track of the number
of elements in the queue.
It is initialized to zero by the constructor, and
then is updated…how?
Member methods include.
(a) a constructor.
Why set both Front and Rear to null?
(b) Enq:
Creates a new node.
If the queue was empty,
special treatment. Why?
else
what does the code do?
Member methods.
(c) EmptyQueue. Why?
(d) Count.
(e) Deq.
Needs to return data from the old front
node, update the Front pointer, and
deallocate the old front.
Note exception handling.
How does it work?
(1) Enq into empty queue.
(2) Enq at Rear of existing queue.
(3) Deq from Front.
(4) Deq last element.
See diagrams.
How to use the code.
See LinkedQueueDriver.CS.
This code:
(1) instantiates the Linked_Queue class as a
queue of integers.
(2) Uses Enq, Deq and Count.
What will it output?
3. What does .NET provide?
System.Collections provides non-generic data
structures where each element is stored as
an object, including:
ArrayList
Stack
Queue
SortedList
Example.
using System.Collections;
Queue Q = new Queue();
Q.Enqueue (3);
Q.Enqueue (2);
Q.Enqueue (1);
foreach (int value in Q)
Console.WriteLine (value);
Generic collections.
System.Collections.Generic provides generic
data structures, including:
Stack<T>
Queue<T>
LinkedList<T>
The latter is actually maintained as a doublylinked list.
LinkedList<T> offers the following:
AddAfter (node, newNode).
AddBefore (newNode, node).
AddFirst (node). [ “Push”]
AddLast (node). [“Enq”].
RemoveFirst () [“Pop” or “Deq”].
RemoveLast ().
Using LinkedList<T> to model a
queue:
See DynamicQDriver.CS.
Advantages of generic collections:
(a) Quick development time.
(b) Control abstraction.
(c) Standardized to facilitate coordination
between independent programmers on a
team.