Data Structures & Algorithms
Data Structures are the programmatic way of storing data so that data can be used
efficiently. Almost every enterprise application uses various types of data structures in one
or the other way.
This tutorial will give you a great understanding of the Data Structures needed to
understand the complexity of enterprise-level applications and the need for algorithms,
and data structures.
CopyrightandDisclaimer
© Copyright 2016 by Tutorials Point (I) Pvt. Ltd. All the content and graphics published in this e-book are the property of Tutorials Point (I)
Pvt. Ltd.
The user of this e-book is prohibited to reuse, retain, copy, distribute or republish
any contents or a part of the contents of this e-book in any manner without the written consent
of the publisher.
We strive to update the contents of our website and tutorials as timely and as precisely as
possible, however, the contents may contain inaccuracies or errors. Tutorials Point (I) Pvt.
Ltd. provides no guarantee regarding the accuracy, timeliness, or completeness of our
website or its contents including this tutorial. If you discover any errors on our website or
in this tutorial, please notify us at contact@tutorialspoint.com
1. Overview
Data Structure is a systematic way to organize data in order to use it efficiently. The following terms are the foundation terms of a data structure.
Interface − Each data structure has an interface. The interface represents the set of
operations that a data structure supports. An interface only provides the list of
supported operations, type of parameters they can accept and the return type of these
operations.
Implementation − Implementation provides the internal representation of a
data structure. Implementation also provides the definition of the algorithms used
in the operations of the data structure
Characteristics of a DataStructure
1. Correctness − Data structure implementation should implement its interface
correctly.
2. Time Complexity − Running time or the execution time of operations of data
structure must be as small as possible.
3. Space Complexity − Memory usage of a data structure operation should be as
little as possible.
Need for Data Structure
1. Data Search − Consider an inventory of 1 million(106) items of a store. If the
application is to search for an item, it has to search an item in 1 million(106) items
every time slowing down the search. As data grows, the search will become slower.
2. Processor Speed − Processor speed although very high, falls limited if the
data grows to billion records.
3. Multiple Requests − As thousands of users can search data simultaneously on a
web server, even the fast server fails while searching the data.
BasicTerminology
Data − Data are values or set of values.
Data Item − Data item refers to single unit of values.
Group Items − Data items that are divided into sub items are called as Group
Items.
Elementary Items − Data items that cannot be divided are called as Elementary
Items.
Attribute and Entity − An entity is that which contains certain attributes or
properties, which may be assigned values.
Entity Set − Entities of similar attributes form an entity set.
Field − Field is a single elementary unit of information representing an attribute
of an entity.
Record − Record is a collection of field values of a given entity.
File − File is a collection of records of the entities in a given entity set.
2. Environment Setup
TryitOptionOnline
You really do not need to set up your own environment to start learning C programming
language. Reason is very simple, we already have set up C Programming environment
online, so that you can compile and execute all the available examples online at the same
time when you are doing your theory work. This gives you confidence in what you are
reading and to check the result with different options. Feel free to modify any example
and execute it online.
Try the following example using the Try it option available at the top right corner of the
sample code box −
For most of the examples given in this tutorial, you will find the Try it option, so just make
use of it and enjoy your learning.
#include <stdio.h>
int main(){
/* My first program in C */
printf("Hello, World! \n");
return 0;
}
For most of the examples given in this tutorial, you will find Try it option, so just make
use of it and enjoy your learning.
Local Environment Setup
If you are still willing to set up your environment for C programming language, you
need the following two tools available on your computer, (a) Text Editor and (b) The C
Compiler
Text Editor
This will be used to type your program. Examples of a few editors include Windows Notepad,
OS Edit command, Brief, Epsilon, EMACS, and vim or vi.
0The name and the version of the text editor can vary on different operating systems. For
example, Notepad will be used on Windows, and vim or vi can be used on Windows as well
as Linux or UNIX.
The files you create with your editor are called source files and contain program source
code. The source files for C programs are typically named with the extension ".c".
Before starting your programming, make sure you have one text editor in place and you
have enough experience to write a computer program, save it in a file, compile it, and
finally execute it.
The C Compiler
The source code written in the source file is the human-readable source for your program.
It needs to be "compiled", to turn into machine language so that your CPU can actually
execute the program as per the given instructions.
This C programming language compiler will be used to compile your source code into a
final executable program. We assume you have the basic knowledge about a programming
language compiler.
Most frequently used and free available compiler is GNU C/C++ compiler. Otherwise, you
can have compilers either from HP or Solaris if you have respective Operating Systems
(OS).
The following section guides you on how to install GNU C/C++ compiler on various OS.
We are mentioning C/C++ together because GNU GCC compiler works for both C and C++
programming languages.
InstallationonUNIX/Linux:-
If you are using Linux or UNIX, then check whether GCC is installed on your system by
entering the following command from the command line −
$ gcc -v
If you have GNU compiler installed on your machine, then it should print a message such
as the following −
Using built-in specs.
Target: i386-redhat-linux
Configured with: ../configure --prefix=/usr .......
Thread model: posix
gcc version 4.1.2 20080704 (Red Hat 4.1.2-46)
If GCC is not installed, then you will have to install it yourself using the detailed instructions
available at http://gcc.gnu.org/install/
This tutorial has been written based on Linux and all the given examples have been
compiled on Cent OS flavor of Linux system.
InstallationonMacOS:-
If you use Mac OS X, the easiest way to obtain GCC is to download the Xcode development
environment from Apple's website and follow the simple installation instructions.
Once you
have Xcode setup, you will be able to use the GNU compiler for C/C++.
Xcode is currently available at developer.apple.com/technologies/tools/
InstallationonWindows:-
To install GCC on Windows, you need to install MinGW. To install MinGW, go to the MinGW
homepage, www.mingw.org, and follow the link to the MinGW download page. Download
the latest version of the MinGW installation program, which should be named MinGW-
.exe.
While installing MinWG, at a minimum, you must install gcc-core, gcc-g++, binutils, and
the MinGW runtime, but you may wish to install more.
Add the bin subdirectory of your MinGW installation to your PATH environment variable,
so that you can specify these tools on the command line by their simple names.
When the installation is complete, you will be able to run gcc, g++, ar, ranlib, dlltool, and
several other GNU tools from the Windows command line.
Algorithm
The algorithm is a step-by-step procedure, which defines a set of instructions to be executed
in a certain order to get the desired output. Algorithms are generally created independent
of underlying languages, i.e. an algorithm can be implemented in more than one
programming language.
From the data structure point of view, the following are some important categories of
algorithms −
1. Search − Algorithm to search an item in a data structure.
2. Sort − Algorithm to sort items in a certain order.
3. Insert − Algorithm to insert an item in a data structure.
4. Update − Algorithm to update an existing item in a data structure.
5. Delete − Algorithm to delete an existing item from a data structure.
Characteristics of an Algorithm
Not all procedures can be called an algorithm. An algorithm should have the following
characteristics −
1. Unambiguous − The algorithm should be clear and unambiguous. Each of its steps
(or phases), and their inputs/outputs should be clear and must lead to only one
meaning.
2. Input − An algorithm should have 0 or more well-defined inputs.
3. Output − An algorithm should have 1 or more well-defined outputs and should
match the desired output.
4. Finiteness − Algorithms must terminate after a finite number of steps.
5. Feasibility − This should be feasible with the available resources.
6. Independent − An algorithm should have step-by-step directions, which should
be independent of any programming code.
How to Write an Algorithm?
There are no well-defined standards for writing algorithms. Rather, it is problem
and resource-dependent. Algorithms are never written to support a particular
programming code.
As we know that all programming languages share basic code constructs like
loops (do, for, while), flow-control (if-else), etc. These common constructs can be used
to write an algorithm. 0
We write algorithms in a step-by-step manner, but it is not always the case. Algorithm
writing is a process and is executed after the problem domain is well-defined. That is,
we should know the problem domain, for which we are designing a solution.
.png)
.png)
.png&description=Data Structures & Algorithms){kind=link}
0 Comments