Transcript What is Data Structures? - East Tennessee State University

What is “Data Structures”?
What will I learn in this course?
Major Topic Groups
C# Language and .NET concepts
.NET Class Library
Data Structures
Algorithms
Algorithm Analysis
What is "Data Structures"?
2
C# and .NET
C# is similar to both Java and C++ in many ways
 The syntax is nearly identical
 If you know Java, you can probably read and understand
simple C# programs with little training
 Major differences between programming in C# and
programming in Java are the class libraries that are provided
 .NET class library provides support for C# (and other .NET languages
such as Visual Basic, F#, IronPython, and even C++.NET)
 Java is supported by AWT, Swing and other libraries in addition to the
standard Java API libraries
What is "Data Structures"?
3
Why Learn C#?
Most large companies in the area that hire our CS
graduates do some or all of their software development
in C#
Nine of 11 companies represented in our advisory
board want graduates to know C#
What is "Data Structures"?
4
What Are Data Structures?
A data structure is a container for holding data
 Usually think of a data structure as holding multiple data items
 An array is an example of this type of data structure
 A Java ArrayList <T> is another example of a data structure
 We may sometimes think of single objects as being data
structures
 A string holds one string of characters that may be manipulated as a
whole (input the string, output the string, compare the string, and so forth)
 A string may also be thought of as a collection of individual characters (or
words) that we want to manipulate individually for some task
 An object of almost any class may be thought of as a container for the
data represented by the object’s attributes
What is "Data Structures"?
5
Organization of the Data
There are many different ways in which individual data
items in a data structure may be organized
 Stored in contiguous memory locations (e.g., an array)
 Stored in non-contiguous (possibly random) memory locations
(e.g., a linked list)
 Stored externally in a file or data base on a hard drive or “in
the cloud”
What is "Data Structures"?
6
Organization of the Data
 A data structure may be organized to facilitate specific
types of usage
 Stored in first-come, first-served manner (a waiting line or queue)
 Stored in last-in, first out manner (stack)
 Stored in order of priority (priority-queue)
 Stored in sorted order
 Organized for efficient storage and retrieval or for efficient access to
particular items
 Organized for minimal memory usage
 Organized for fastest access
What is "Data Structures"?
7
Data Structures
Each type of data structure has its own unique
characteristics
There are trade-offs in deciding which data structure to
use
 Memory requirements
 Efficiency (speed) of storing, finding, retrieving, or processing the
data
 Ease of
 Understanding
 Programming
 Testing/debugging/maintenance
 Trade-offs: A fast algorithm on a given data structure may require
more memory and be more difficult to understand, but a slower
algorithm may take less memory and be easier to maintain
What is "Data Structures"?
8
Organization
We may have many questions to answer such as
 Do we need to access the data randomly (access any item
without accessing all those before it, for example) or is
sequential access sufficient for our needs?
 Does the data need to be in a specific order such as sorted
by value, arranged by time (such as people waiting to buy a
ticket to a movie), arranged by priority (the emergency room
has to deal with someone bleeding profusely ahead of
someone with a cold even if the person with the cold has
been waiting longer), and so forth?
 The organization of the data and the efficiency with which
we can store/find/retrieve/process items becomes more
important as the amount of data gets large (it takes a lot
longer to sort 1,000,000 items than it does to sort 3 items)
What is "Data Structures"?
9
Algorithms
For a given data structure, we may need to do
certain types of common activities such as
 Add data to the data structure
 Retrieve data from the data structure
 Find a particular data item or items in the data structure
 Rearrange (sort) the data into some order meaningful for
a particular task
What is "Data Structures"?
10
Algorithms
For a data structure to be useful, it must be
accompanied by implementations of the algorithms
that allow one to manipulate the data in the desired
ways
Not all data structures are created equal
 There is no “best” data structure for all situations
 Some are more efficient for specific tasks than others are but
the latter group may be more efficient for a different set of
tasks
 One must choose the appropriate data structure for a given
task
What is "Data Structures"?
11
Algorithm Analysis and Selection
There may be many different algorithms that can be
used to accomplish a specific task on a particular data
structure
 One must be able to analyze the different algorithms and
choose one that is reasonably efficient for a given task
 For example, there are many different sorting algorithms; how
should we choose one that works efficiently for our data
What is "Data Structures"?
12
Algorithm Limitations
Some algorithms do not make sense for a
particular type of data structure, and, thus, no
attempt to use them with that type of data
structure should be attempted
 For example, what does it mean to sort a linked list of
colored pixels (does a turquoise pixel come before or
after a puce pixel, for example)?
 A queue is organized by the arrival time of the items it
contains – sorting a queue by (say) employee name
would destroy the ordering required by the queue – it
would no longer be a queue
What is "Data Structures"?
13
Choosing an Algorithm
A better choice of algorithms might be made if one
knows something about the data involved
 For example, one type of sorting algorithm may be more
efficient if the data is already “close” to being in order while
another algorithm may be more efficient on totally random
data
 One may search for a value in an array much more
efficiently if one knows the data is sorted than if the order
of the data is unknown
What is "Data Structures"?
14
Class Libraries
There are many class libraries that contain good
implementations of certain data structures and the
algorithms that support it
 A library may have a class that implements a LinkedList, another
class that implements a Queue, another for a Stack, and so forth
 The implementations may also contain many useful methods
(algorithms)
In this course, where possible, we will learn to use data
structures implemented in the .NET class library
Some data structures are not be implemented in the
.NET library, and we will have to build our own including
the algorithms for inserting, finding, and retrieving items
What is "Data Structures"?
15
What Will We Do?
 Learn to write programs in C#, using the .NET class library
 Learn about different types of data structures
 The organization of the data in the data structure
 When using each type is appropriate
 Select an appropriate data structure for a given task
 Introduction to elementary algorithm analysis techniques
 Analyze algorithms to determine characteristics such as memory efficiency,
execution efficiency, ease of programming including understanding, coding,
and maintenance
 Select an algorithm that is appropriate to the task and reasonably efficient
 Learn about the trade-offs involved in making intelligent
decisions concerning data structures and algorithms
What is "Data Structures"?
17