Simulation of Data Structures
A project report submitted to
Rajiv Gandhi Proudyogiki Vishwavidyalaya, Bhopal
towards partial fulfillment of the degree of
MASTER OF COMPUTER APPLICATIONS
2011
Guided by Submitted by
Mrs. Anuradha Purohit Jitendra Verma
Deptt. Of Computer Technology & Applications Deepesh Wadiwa
Shri G.S. I.T.S, Indore
Department of Computer Technology & Applications
SHRI G.S. INSTITUTE OF TECHNOLOGY &SCIENCE
23, Park Road, INDORE(M.P.)
SHRI G.S. INSTITUTE OF TECHNOLOGY & SCIENCE
INDORE (M.P.)
Recommendation
The project report entitled Simulation of Data Structures submitted by
Jitendra Verma, Deepesh Wadiwa Students of M.C.A Final Year in the
session 2011-12,towards partial fulfillment of degree of Mater of computer
Applications of Rajiv Gandhi Proudyogiki Vishwavidyalaya, Bopal, is
satisfactory account of their work and is approved for the award of degree.
Mrs. Anuradha Purohit Head
Project Guide Department of Computer
Technology & Applications
Dean (Academics)
SGSITS, Indore
SHRI G.S. INSTITUTE OF TECHNOLOGY & SCIENCE
INDORE(M.P.)
Certificate
The project report entitled Simulation of Data Structures submitted by
Jitendra Verma, Deepesh wadiwa Students of M.C.A Final Year in the
session 2011-12,towards partial fulfillment of degree of Master of computer
Applications of Rajiv Gandhi Proudyogiki Vishwavidyalaya, Bhopal, is
satisfactory account of their work and is approved for the award of degree.
Internal Examiner External Examiner
Date: Date:
Acknowledgement
The completion of any task depends upon the cooperation, coordination,
and consolidated efforts of several resources of knowledge, energy, time and
above all the proper guidance of the veterans. Therefore we approached this
matter of acknowledgement through these lines trying our best to give full credit
where it deserves.
We express our heartfelt thanks to our Project Guide Mrs. Anuradha
Purohit for her edified guidance, incessant encouragement and congenial
attitude in every respect. Their profound perception, esteemed inspiration and
dedication helped us at every stage while completing this work. We thank them
for their always down-to-earth views on system design & development and for
keeping our feet on the right path when it was required. And many thanks to
Ms. Sunita Verma (H.O.D) of Computer Technology & applications
Department.
The support and suggestions of our friends are worth our appreciation and
thankfulness. We bow in reverence to our venerable parents and all family
members whose imperishable love and appreciation through thick and thin
rejuvenated us and spurred us on to complete the task. We are deeply indebted
to the College management, who provided us a well equipped computer
laboratory with all required software and library, which was an essential
requirement for the success of this project.
Abstract
Data structure is an important subject for every student who is studying
engineering. It deals with storing data efficiently to improve performance. It
also deals with efficient use of memory space. But it may not be possible to
study and understand various parts of this very important subject in short time.
To understand a topic clearly, visualization plays a big part. By means of
visualization, even a relatively complex topic can be understood easily. Our
project is a data structure simulation. With the help of this simulator, the user
will be able to visualize different elements of data structure (like stack, queue,
linked list and most importantly different sorting techniques). It is being
targeted at the students learning data structure first time. They will be
immensely benefited by this simulation.
Table of Contents
Chapter 1
Introduction
1.1 Preamble
1.2 Objective
1.3 Scope
1.4 Organization of the report
Chapter 2
Literature Survey/Conceptual Framework
Chapter 3
Analysis
3.1 Feasibility Study
3.2 Requirements Analysis & Specifications
3.3 Functional Description
3.4 Information Flow Representation
3.4.1 Data Flow Diagram
3.4.2 Control Flow Diagram
3.4.3 Use Case Diagram
3.5 Behavioral Description
3.5.1 State Transition Diagram
Chapter 4
Planning
4.1 Software Project Estimation
4.2 scheduling
4.2.1 Time line (Gantt) Chart
4.2.2 Project Schedule Table
4.3 Team Organization
4.4 Resource Planning
4.4.1 Hardware Requirements
4.4.2 Software Requirements
Chapter 5
Design
5.1 Architectural Design
5.2 Data Design
5.3 Interface Design
Chapter 6
Implementation
6.1 Coding
6.2 Testing
6.3 Result Set
Chapter 7
Conclusion
7.1 Conclusion
7.2 Limitations
7.3 Difficulties Encountered
References
Chapter 1
Introduction
1.1 Preamble
Data Structures are use for storing data , searching and retrieving data , you
must understand that what is data structure and how it works. If we understand
the Data Structure then we can reduce the access time of data and increases the
performance of our system by working of data structure. So we understand it by
graphical representation. Graphical representation describe the working of
different available data structures.
1.2 Objective
The aim of this project is to implement an automated system for processing and
generating results for storing and retrieving data in a graphical way . we can
easily understand the working of data structures.
1.3 Scope
The Software can be used to:
y Understand different operation of data structures
y Understand different structure for storing data
y Understand working of data structure
The benefits of this software are:
y Implemented using latest technology(Java)
y Can upload results direct on web so reduces paper work
y An interactive user interface
y Plate form independent
1.4 Organization of Report
In Introduction we have provided the information what our project is doing
along with objective and scope is also being given.
In literature survey/conceptual framework we have explained the basic
concepts to understand the project and the technology, which we have to
accomplish our project.
Analysis describes what different stuff we have studied during our software
development, which also includes use case and CRC.
Planning includes the time span, which we have divided to complete the
project, which has Gantt chart and project schedule.
Design describes the consulting architecture of our project which we have used
to develop the software. Along with UML tools like class Diagram and
sequence Diagram.
In Implementation we have explained how our software implemented and
testing strategies that are used to test the software and check how the user is
using the software.
In conclusion limitation and difficulties, which we have, came across during
the development of the project along with some future enhancement, which
could be made to the project.
Chapter 2
Literature Survey/Conceptual Framework
During System development we used different technology such as:
2.1 Java a powerful and popular programming language, it has the
following features:
i) Platform Independence.
ii) The Write-Once-Run-Anywhere.
iii) Provide security.
iv) Object oriented language.
v) Introduced the concept of classes.
After that we arrive at the point of description of our project feature in
this we implement The stack , queue ,tree, list and graph.
We study all the operation which can we perform at those data structures
and implement this as a user friendly way in graphical representation.
2.2 Net beans is java supported GUI application its features are
following:
1) Java supported
2) Provide GUI interface designing facility
3) Drag and drop facility
4) Event handling
Chapter 3
Analysis
3.1 Feasibility study
After request clarification, analyst proposes some solutions. After that for each
solution it is checked whether it is practical to implement that solution. this is
done through feasibility study. In this various feasibility aspects are analyzed
depending on the context of the system. The outcome of the feasibility study
should be very clear.
3.1.1 Technical feasibility
In technical feasibility the following issues are taken into consideration.
Whether the required technology is available or not?
The system does not have any rigid hard-ware and software requirements and
there is availability of the people who can perform the software engineering
activities required for the development of the system.
Hence, the system is technically feasible.
3.1.1Operational feasibility
Operational feasibility is mainly concerned with issues like whether the system
will be used if it is developed and implemented. Thus question arises whether
there will be resistance from users that will affect the possible application
benefits? The answer to these question is: yes, as the system is developed for
convenience of knowing the working of different data structure.
3.2 Requirement Analysis & Specification
The requirement the complex structure of storing data .so it is need the
understand the structure of data store .and how we can access that easily.
3.3 Information Flow Representation
Information is transformed as it flows through a computer-based system
accepts input in a variety of form. We can create a flow model for any
computer based system, regardless of size and complexity.
3.3.1 Use Case Diagram
This models the system from the end users point of view. They are
created during requirement elicitation. The fig. 3.1 shows the UseCase
Diagram for Simulation of Data Structures.
(Fig no.3.1) usecase diagram
Stack Queue
Link List Tree
Graph
Modi fication
Seaching Sorting
Insert
Delet
User
Data Stucture
Operations
Help
Contact Infomation
File System
3.3.2 Use Case Specification:
1) User select data structure and then .
2) perform operation on that data structure.
3) User can view help for performing operation on the data structure.
4) Can contact if problem is occur during operation .
3.3.3 CRC Cards:
1) User-
Class name User
Sub class Nil
Super class Nil
Responsibility:
1. Select data structures
2. Perform operations
Collaborator:
1. Select ds
2. Operation
2) Select data structure:
Class name Select data structure
Sub class Nil
Super class Nil
Responsibility:
1. Select data structures
Collaborator:
1. Select ds
2. User
3) Operation:
Class name Operation
Sub class Nil
Super class Nil
Responsibility:
1. Perform operations
Collaborator:
1. Select ds
2. User
Chapter 4
Planning
Planning includes the time span, which we have divided to
complete the project, which has Gantt chart and project schedule.
4.1 Software Project Estimation
An model for software uses empirically derived formulas to predict effort as a
function of LOC or FP. The empirical data that supports most estimation
models are derived from limited sample of projects.
Our software requires 2 main modules. The sizes of major module are:
(i) Interface 0.4KDLOC
(ii) Algorithms 0.4KDLOC
The different cost driver attribute are:
COST DRIVER RATING (MULTIPLYING
FACTOR)
i. Complexity
ii. Experience
iii. Programmer
capability
iv. Storage
v. Programming
language
experience
vi. Development
schedule
Low
Very low
Very low
Very low
Very low
Very low
0.65
1.11
1.17
-
1.10
1.13
All the factor had nominal [Link] the effort adjustment factor
EAF=multiplication of all factors
EAF=0.65*1.11*1.17*1.10*1.13 =1.04
Now our project is categorized into embedded project, because we have
little experience and requirements are stringent.
So value of constant
a=2.8
b=1.2
The initial effort
Ei=a*( KDLOC)
b
Ei=2.8*(1.00)
1.2
=2.8 programmer month(PM)
Final estimation
E=EAF*Ei
=1.04*2.8
=2.9PM
4.2 SCHEDULING:
GANTT CHART
20uug 15sep 30sep 15oct 30 oct 1nov 11 dec
ID NAME
1 Requlrement Anulysls
2 Conceptuul Deslgn
3 Loglcul Deslgn
4 Physlcul Deslgn
5 Implementutlon
6 Testlng
8 Presentutlon
Fig no 4.2 (gaint chart of scheduling)
4.3 TEAM ORGANIZATION:
There are almost as many human organizational structures for software
development as there is organization that develop software. The best team
structure depends on the management style, of an organization , the no of
people who will populate the team and the overall problem difficulty.
There 3 generic team organizations:
y Democratic Decentralization(DD)
y Controlled Decentralization(CD)
y Controlled Centralized(CC)
Democratic Decentralized(DD)
In our project we are using Democratic Decentralized team. This
software team has no permanent leader. Rather task coordinators are appointed
for short durations and then replaced by others who may coordinate different
task. Decisions on problems and approaches are made by group consensus.
Communication among team member is horizontal. The DD team organization
is best applied to the problems with low modularity because of higher volume
of communication is needed.
Controlled Decentralized(CD)
This software engineering team has defined leader who coordinate specific task
and secondary leaders that have responsibility for the sub-task. Problem solving
remains a group activity, but implementation of solutions is partitioned among
subgroups by team leader. Communication among subgroups may be vertical or
horizontal
Controlled Centralized(CC)
Top level problem solving and internal team coordination are managed
by a team leader. Communication between the team leaders and the team
members is vertical. Thus our software team is Democratic and Decentralized
as there is no leader all of give the innovative idea and the best is chosen to be
implemented. Decision is a group activity, and both being an integral part
of it. Communication among the team is horizontal.
4.4 RESOURCE PLANNING:
A variety of different resources are available to an OO system or product
and many instances , subsystems complete for these resources at the same time.
Global system resources can be external entities or abstraction.
Hardware Requirement
Processor: Pentium Dual core or newer version
RAM: 1GB or above
Disk space: 80GB or above
Monitor: color
Software Requirement
Windows operating system
JAVA
NET BEANS
Chapter 5
Design
Design describes the consulting architecture of our project which we
have used to develop the software. Along with UML tools like class Diagram
and sequence Diagram.
5.1 Architectural design
The architectural design defines the relationship between major structural
elements of the software, the design patterns that can be used to achieve the
requirements that have been defined for the system.
5.1.1 Class Diagram
The class diagram is used to refine the use case diagram and define a detailed
design of the system. The class diagram classifies the actors defined in the use
case diagram into a set of interrelated classes. The relationship or association
between the classes can be either an is-a or has-a relationship. Each class in
the class diagram may be capable of providing certain functionalities. These
functionalities provided by the class are termed methods of the class. The
figure shows the class diagram
Class Diagram
Fig no. 5.1 (class diagram)
5.1.2 Activity Diagram
Activity diagram provides a view of the behavior of a system by
describing the sequence of action in a process. Activity diagrams are similar to
flowchart because they show the flow between the actions in an activity.
Activity diagram
Fig no.5.1 (activity diagam)
Select Menu
Select Data
Structure
View Help View Contact
Information
Stack Linked list Tree Graph Queue
Select Operation
Insert Delete Search Sort
View Simulation
Chapter 6
Implementation
In Implementation we have explained how our software implemented
and testing strategies that are used to test the software and check how the user is
using the software.
6.1 coding
The whole code is compiled and the class files are generated , Due to the
features of java.
public class STACK extends [Link] {
private void jButton5ActionPerformed([Link] evt) {
SELECT_DS DS=new SELECT_DS();
[Link](true);
[Link](false);
Comments
Proper comments are placed within the code everywhere related to the
functioning of java various modules within each of the java files . This makes
the maintenance of the code easier as comments make the code more reliable .
another user other than the developer can easily understand the code with the
help of comment In case of any modifications.
/** Creates new form STACK */
Naming
Each entity, variable , function other modules the code are named such
as directly reflect their functioning . This makes the code easy to understand and
more manageable.
public STACK()
SELECT_DS DS=new SELECT_DS();
Declaration
All the declaration in java files are written with in the deceleration tags of
the Java.
int top=-1;
int Max=7;
Integer stack[]=new Integer[7];
Expression and Statement
As the technology used is java , all the expression and statement
according to the java syntax within the appropriate tags.
Memory Management
Science application handling very large arrays so far efficient execution with
minimum memory ,all variables were taken carefully.
Error Handling and Exception
All the errors and exceptions are handled using block .all the code that
can generate any type of errors /exceptions is placed within the try catch block .
6.2 Portability
The product is build using java /technology and therefore can be run on
any platform as java provides platforms independence .java makes the software
portable to any platform including windows Linux.
6.3 Testing
Testing is the set of activities that are conducted to find error in the
development software.
Following are the objective of testing:
1) Testing is the process of executing program with intent of finding an
error. A good test case one that has a high portability of finding a yet
not-discovered error.
2) A successful test is one that uncovers a yet-not-error. Software testability
is simply how easily a system can be tested.
For testing your system we have used the four step strategies proposed for real
time systems:
1. Verification and validation
2. Unit testing\
3. Integration testing
Chapter 7
Conclusion
In conclusion limitation and difficulties, which we have, came across
during the development of the project along with some future enhancement,
which could be made to the project.
7.1 Technical Achievements
Easy to use graphics user interface:- this objective has been met. The java
swing s allow for better interface design. This GUI designed to look and feel
like a standard windows application.
Scales well to larger strings :- our software efficiently handle the very large
strings
7.2 Limitation :
The software is meeting all the necessary requirements and as such there
is no limitation from its part according to user requirements. By technically
there do seem some limitation to the software solution, which is in case the
following .
y It will support only single user
y Only one operation can perform at a time
y Select only single data structure at a time
y We can not store data
7.3 Difficulties Encountered
New platform: as this project is based on GUI. So we need to learn
netbean technology. We had to devote some time to learn swings component
References:-
1. Langston, Augestine,Tannenbaum, Data Structure using c and c++
,Pearson Education.
2. Kruse, tondo, leung Data Structure And programming in c , Pearson
Education.
3. H. Sahni Fundamentals of Computer Algorithms Galgotia.