Data Structure

Data Structure

Maryam A. Salih
department of Computer Engineering
Second Class
Lecture Two: INTRODUCTION TO DATA STRUCTURE
Lecture outline

• Introduction
• Abstract Data Type (ADT)
• Containers
• Introduction to Data Structure
• Linear List
Introduction

• Ina well-designed modular program, software

components should satisfy the following two properties:
1. Each component performs one well-defined task.
2. Each component is as independentas possible from the others.
1. Easier to understand; little redundant code.
2. Facilitates software reuse.
3. Easier to implement.
4. Easier to test.
5. Easier to modify.
An Abstract Data Type
• An Abstract Data Type (ADT) is a specification of a set of data and a set of

operations that can be performed on the data.
• In C++, a class represents an ADT.
Type name
Circle
constructor(s): Circle(int,int),
Circle(float,int,int);
Public interface
float computeArea();
float getRadius();
void setRadius(float);
// etc.
Type name
Point
constructor(s): Point(int,int),
Point(); // default (0,0)
Public interface int getX();
int getY();
// etc.
1. Point.h header file (declarations & inline
code)
2. Point.cpp implementation file (code)
3. main.cpp test driver
Containers
• The most general Abstract Data Type (ADT) is that of a container

• A container describes structures that store and give access to objects
Data structure: is a data object together with the relationships (functions)
that exist among the instances and among the individual elements that
compose an instance.
• The queries and operations of interest may be defined on:
• The container as an entity, or
• The objects stored within a container
Operations on a Container
The operations we may wish to perform on a container are:
• Create a new container
• Copy or destroy an existing container
• Empty a container
• Query how many objects are in a container
• Query what is the maximum number of objects a container can hold
• Given two containers:
• Find the union (merge), or
• Find the intersection
Operations on a Container
• Many of these operations on containers are in the Standard Template
Library
Operations on Objects Stored in a Container
Given a container, we may wish to:

• Insert an object into a container
• Access or modify an object in a container
• Remove an object from the container
• Query if an object is in the container
• If applicable, count how many copies of an object are in a container
• Iterate (step through) the objects in a container
Operations on Objects Stored in a Container
• Many of these operations are also common to the Standard Template
Library
Simple and Associative Containers
• We may split containers into two general classifications:
Temperature readings UW Student ID Number
QUEST Student
Circular Academic Academic
Array Server Record
Operations
• In any application, the actual required operations may be only a subset of

the possible operations
• In the design of any solution, it is important to consider both current and future
requirements
• Under certain conditions, by reducing specific operations, the speed can be increased
or the memory decreased
Exercise:
• Some of the characteristics of a book are the title, author(s), publisher,
ISBN, price, and year of publication. Design a class bookType that defines
the book as an ADT.
• Each object of the class bookType can hold the following information about a book:
title, up to four authors, publisher, ISBN, price, and number of copies in stock. To keep
track of the number of authors, add another member variable.
• Include the member functions to perform the various operations on objects of type
bookType. For example, the usual operations that can be performed on the title are to
show the title, set the title, and check whether a title is the same as the actual title of
the book. Similarly, the typical operations that can be performed on the number of
copies in stock are to show the number of copies in stock, set the number of copies in
stock, update the number of copies in stock, and return the number of copies in stock.
Add similar operations for the publisher, ISBN, book price, and authors. Add the
appropriate constructors and a destructor (if one is needed).
• Write C++ program to test the ADT.(Lab. Exercise).
Common Data Structure
• The most common implantation of structure containers are:
• List
• Queue
• Stack
• Tree
• ..etc.
• The data representation for these structures can be either using

• Linear (Array )
• Link list (Chain)
Access to the object
List
• List is a data representation of the form (e1,e2,……,en). Erasing an object
• The elements can be either Simple or Associative elements.

• The list can be implanted as (Linear (array) or Link List
(chain))
• The figure shows some of the main operations that can be Insertion of a new object
applied on a List..
Replacement of the object

Linear List
• ADT (class Diagram)

The elements that will be inserted in the List
The number of elements that are inserted in the List
The maximum number of elements that can be inserted to the List
LinearList<T> :: LinearList(int max)
{
maxsize = max;
element = new T[maxsize];
length = 0;
}
bool Isempty() { return (length==0); }
int Length() { return length; }
void LinearList<T> ::Insert(int k, T x)
{
if(k<0 || k>Length())
throw("Out of bounds");
if(Length() == maxsize)
throw("List is full");
for(int i=Length()-1; i>=k; i--)
element[i+1] = element[i];
element[k]= x; length++;
}
LinearList<T>& LinearList<T> ::Delete(int k, T& x)
{
if(Find(k,x))
{
for(int i=k; i<Length() -1; i++)
element[i] = element[i+1];
length--;
return *this;
}
else
throw("Out of bounds");
}
bool LinearList<T> ::Find(int k, T& x)
{
if(k<1 || k>Length())
return false;
x = element[k-1];
return true;
}
int LinearList<T> ::Search(T x)
{
for (int i=0; i<Length(); i++)
if(element[i]==x)
return ++i;
return 0;
}
void LinearList<T> ::output()
{
for(int i=0; i<Length(); i++)
cout<<element[i]<<" ";
}
~LinearList() { delete [ ]element; }
Thank you

Data Structure

Uploaded by

Copyright:

Available Formats

Data Structure

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Data Structure

Uploaded by

Copyright:

Available Formats

Data Structure

• Ina well-designed modular program, software

• An Abstract Data Type (ADT) is a specification of a set of data and a set of

• The most general Abstract Data Type (ADT) is that of a container

Given a container, we may wish to:

Temperature readings UW Student ID Number

• In any application, the actual required operations may be only a subset of

• The data representation for these structures can be either using

• The elements can be either Simple or Associative elements.

Replacement of the object

• ADT (class Diagram)

You might also like