Scribd
Upload
2K views8 pages

Data Structures Using C and C++ Notes

This document provides an introduction to data structures. It defines data structures as a way to store and organize data in a computer so that it can be used efficiently. There are different types of data structures including linear structures like arrays, stacks and queues, and non-linear structures like trees and graphs. The performance of algorithms using these data structures depends on factors like time complexity, which measures how long an algorithm takes to run based on the size of the input data, and space complexity, which measures how much memory is used. Common time complexities include constant, logarithmic, linear, quadratic and exponential time. Choosing the appropriate data structure and algorithm is important for designing efficient programs.

Uploaded by

aman deeptiwari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2K views8 pages

Data Structures Using C and C++ Notes

This document provides an introduction to data structures. It defines data structures as a way to store and organize data in a computer so that it can be used efficiently. There are different types of data structures including linear structures like arrays, stacks and queues, and non-linear structures like trees and graphs. The performance of algorithms using these data structures depends on factors like time complexity, which measures how long an algorithm takes to run based on the size of the input data, and space complexity, which measures how much memory is used. Common time complexities include constant, logarithmic, linear, quadratic and exponential time. Choosing the appropriate data structure and algorithm is important for designing efficient programs.

Uploaded by

aman deeptiwari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
  • Introduction to Data Structure
  • Classification of Data Structures
  • Algorithms

BCA : I

BCA-S202T: Data Structure using C and C++

Poorva Sanjay Sabnis.


Assistant Professor-I
Unit 1
Introduction to Data Structure

Basic concepts of Data Structure:


A data structure is a way of storing data in a computer so that it can be used
efficiently and it will allow the most efficient algorithm to be used. The choice of
the data structure begins from the choice of an abstract data type(ADT). A
well-designed data structure allows a variety of critical operations to be
performed, using as few resources, both execution time and memory space, as
possible. Data structure introduction refers to a scheme for organizing data, or
in other words, it is an arrangement of data in computer's memory in such a
way that it could make the data quickly available to the processor for
required calculations.

A data structure should be seen as a logical concept that must address two
fundamental concerns.
1. First, how the data will be stored, and
2. Second, what operations will be performed on it?

As data structure is a scheme for data organization so the functional definition of a


data structure should be independent of its implementation. The functional
definition of a data structure is known as ADT (Abstract Data Type) which is
independent of implementation. The way in which the data is organized affects the
performance of a program for different tasks.

BCA-S202T: DS
Computer programmers decide which data structures to use based on the
nature of the data and the processes that need to be performed on that data.
Some of the more commonly used data structures include lists, arrays, stacks,
queues, heaps, trees, and graphs.

Classification of Data Structures:


Data structures can be classified as-
 Simple data structure
 Compound data structure
 Linear data structure
 Non-linear data structure

BCA-S202T: DS
Simple Data Structure: Simple data structure can be constructed with the help of
primitive data structure. A primitive data structure used to represent the standard
data types of any one of the computer languages. Variables, arrays, pointers,
structures, unions, etc. are examples of primitive data structures.

Compound Data structure: Compound data structure can be constructed with the
help of any one of the primitive data structure and it is having a specific
functionality. It can be designed by user. It can be classified as
 Linear data structure
 Non-linear data structure

Linear data structures can be constructed as a continuous arrangement of data


elements in the memory. It can be constructed by using array data type. In the
linear Data Structures the relationship of adjacency is maintained between the
data elements.

Operations applied on linear data structure:


The following list of operations applied on linear data structures.
1. Add an element
2. Delete an element
3. Traverse
4. Sort the list of elements
5. Search for a data element For example Stack, Queue, Tables, List, and Linked
Lists.

BCA-S202T: DS
Non-linear Data Structure:
Non-linear data structure can be constructed as a collection of randomly distributed
set of data item joined together by using a special pointer (tag). In non-linear Data
structure the relationship of adjacency is not maintained between the data items.

Array:
In computer science, the obvious way to store an ordered collection of items is as
an array. Array items are typically stored in a sequence of computer memory
locations, but to discuss them, we need a convenient way to write them down on
paper. We can just write the items in order, separated by commas and enclosed by
square brackets. Thus,
[1; 4; 17; 3; 90; 79; 4; 6; 81]
is an example of an array of integers. If we call this array a, we can write it as:
a = [1; 4; 17; 3; 90; 79; 4; 6; 81]
This array has 9 items, and hence we say that its size is 9. In everyday life, we
usually start counting from 1. When we work with arrays in computer science,
however, we more often (though not always) start from 0. Thus, for our array a, its
positions are 0; 1; 2; : : : ; 7; 8.

The element in the 8th position is 81, and we use the notation a[8] to denote this
element. More generally, for any integer i denoting a position, we write a[i] to
denote the element in the ith position. This position i is called an index (and the
plural is indices). Then, in the above example, a[0] = 1, a[1] = 4, a[2] = 17, and so
on.

It is worth noting at this point that the symbol = is quite overloaded. In


mathematics, it stands for equality. In most modern programming languages, =
BCA-S202T: DS
denotes assignment, while equality is expressed by ==. We will typically use = in
its mathematical meaning, unless it is written as part of code or pseudo-code.

We say that the individual items a[i] in the array a are accessed using their index i,
and one can move sequentially through the array by incrementing or decrementing
that index, or jump straight to a particular item given its index value. Algorithms
that process data stored as arrays will typically need to visit systematically all the
items in the array, and apply appropriate operations on them.

Algorithms:

Structure and Properties of Algorithm:


An algorithm has the following structure
1. Input
2. Step2: Assignment
3. Step3: Decision
4. Step4: Repetitive
5. Step5: Output

An algorithm is endowed with the following properties:


1) An algorithm must terminate after a finite number of steps.
2) Definiteness: The steps of the algorithm must be precisely defined or
unambiguously specified.
3) Generality: An algorithm must be generic enough to solve all problems of a
particular class.

BCA-S202T: DS
4) Effectiveness: The operations of the algorithm must be basic enough to be
put down on pencil and paper. They should not be too complex to warrant
writing another algorithm for the operation.
5) Input-Output: The algorithm must have certain initial and precise inputs, and
outputs that may be generated both at its intermediate and final steps.

Different Approaches to Design an Algorithm:


An algorithm does not enforce a language or mode for its expression but only
demands adherence to its properties.

Practical Algorithm Design Issues:


[Link] save time (Time Complexity): A program that runs faster is a better program.
[Link] save space (Space Complexity): A program that saves space over a
competing program is considerable desirable.

Efficiency of Algorithms: The performances of algorithms can be measured on the


scales of time and space. The performance of a program is the amount of
computer memory and time needed to run a program. We use two
approaches to determine the performance of a program. One is analytical and the
other is experimental. In performance analysis we use analytical methods,
while in performance measurement we conduct experiments.

 Time Complexity: The time complexity of an algorithm or a program is a


function of the running time of the algorithm or a program. In other
words, it is the amount of computer time it needs to run to
completion.

BCA-S202T: DS
 Space Complexity: The space complexity of an algorithm or program is a
function of the space needed by the algorithm or program to run to
completion. The time complexity of an algorithm can be computed either by
an empirical or theoretical approach. The empirical or posteriori testing
approach calls for implementing the complete algorithms and executing
them on a computer for various instances of the problem. The time taken by
the execution of the programs for various instances of the problem are
noted and compared. The algorithm whose implementation yields the
least time is considered as the best among the candidate algorithmic
solutions.

Analyzing Algorithms: Suppose M is an algorithm, and suppose n is the size of the


input data. Clearly the complexity f(n) of M increases as n increases. It is usually
the rate of increase of f(n) with some standard functions. The most common
computing times areO(1), O(log2n), O(n), O(n log2n), O(n2), O(n3), O(2n

BCA-S202T: DS

Common questions

Powered by AI

Linear data structures organize data in a sequential manner, which means that elements are adjacent to each other in memory. This sequential arrangement allows for straightforward operations like traversal, insertion, deletion, and searching. Examples include arrays, stacks, and queues . In contrast, non-linear data structures do not follow this sequence, allowing data elements to have multiple relationships. This results in more complex navigation paths and operations. Examples of non-linear data structures include trees and graphs, where adjacency is not necessarily maintained in memory order .

Designing an effective and efficient algorithm involves several key considerations: it must have clear and precise steps (definiteness), end after a finite number of steps (termination), be general enough to solve all problems of a particular class (generality), and have operations that are basic and implementable (effectiveness). Furthermore, efficiency is measured in terms of time complexity (how quickly an algorithm runs) and space complexity (how much memory it utilizes). Choosing optimal strategies for these metrics is vital to ensuring the algorithm's performance in practical applications .

In computer science, array indexing typically starts from 0, whereas everyday counting usually begins from 1. This 0-based indexing means that the first element of an array is accessed with index 0 (a[0]), making it fundamentally different from how elements would be numbered in daily life. This distinction is important for programming because it affects loop control structures and array operations, requiring programmers to adjust their logic accordingly to avoid off-by-one errors, which are a common source of bugs .

The choice of a data structure critically affects the efficiency of algorithms because it determines how data is stored, accessed, and manipulated. A well-chosen data structure allows operations to be performed using minimal resources, such as time and memory space. This choice begins with selecting an appropriate Abstract Data Type (ADT), which defines the logical form and operations on the data regardless of its implementation. ADTs provide a consistent interface and help programmers abstract away low-level details, enabling them to focus on high-level design and efficiency .

Time complexity and space complexity are crucial metrics in evaluating an algorithm's performance. Time complexity refers to the amount of time an algorithm takes to complete relative to the size of its input (n), expressed using Big O notation (e.g., O(n), O(log n)). Space complexity measures the amount of memory used during the algorithm's execution. Both impact performance, as a time-intensive algorithm might be unsuitable for time-critical applications, while a space-intensive algorithm might be impractical due to memory constraints. Considering both metrics helps in selecting the most appropriate algorithm for a specific computational environment .

The arrangement of data in memory for arrays significantly influences the efficiency of operations performed on them such as accessing, inserting, and deleting elements. Arrays store elements in contiguous memory locations, allowing quick access via indices. This contiguous layout simplifies traversal through iteration and enables direct access to any element using its index, contributing to fast retrieval time. For example, the operation a[i] can quickly retrieve the ith element of an array due to its known offset in memory .

An algorithm must terminate after a finite number of steps to ensure that it provides a solution in a predictable amount of time. This termination is crucial for proving the algorithm's correctness and reliability in delivering results. It also relates to algorithmic definiteness, which demands that each step in the process be clearly and unambiguously defined to avoid infinite loops or undefined behavior. Together, these properties ensure that an algorithm is both correct and practical in real-world applications .

Simple data structures are built from primitive data types and have a basic, straightforward organization, such as integers, floats, or characters. Compound data structures, however, can be more complex and are constructed using multiple simple data types, allowing them to represent more sophisticated data arrangements like lists, trees, and graphs. A programmer might opt for compound structures when dealing with complex data relationships or when efficiency in data management is required, whereas simple structures might be chosen for their simplicity and ease of use in straightforward tasks .

Utilizing a well-designed data structure directly influences a program's memory usage and execution time. Efficient data structures optimize storage by minimizing required memory while ensuring quick access and manipulation of data, thus reducing overall execution time. Poor data structure choices may lead to excessive use of resources, slowing down operations like searching or sorting. Hence, selecting the appropriate data structure for given tasks is crucial to balance resource usage and achieve optimal performance .

Analytical approaches to measuring algorithm performance involve using mathematical methods to estimate time and space complexity based on algorithm structure. This approach allows for theoretical analysis and prediction of performance across different input sizes without executing the algorithm. Experimental approaches, on the other hand, involve implementing the algorithm and testing it on various inputs to measure actual performance metrics empirically. Analytical methods are good for a broad understanding of efficiency, while experimental methods provide practical insights into real-world performance .

BCA : I BCA-S202T: Data Structure using C and C++ Poorva Sanjay Sabnis. Assistant Professor-I
BCA-S202T: DS Unit 1 Introduction to Data Structure Basic concepts of Data Structure: A data structure is a way of
BCA-S202T: DS Computer programmers decide which data structures to use based on the nature of the data an
BCA-S202T: DS Simple Data Structure: Simple data structure can be constructed with the help of primitive data structu
BCA-S202T: DS Non-linear Data Structure: Non-linear data structure can be constructed as a collection of randomly d
BCA-S202T: DS denotes assignment, while equality is expressed by ==. We will typically use = in its mathematical meanin
BCA-S202T: DS 4) Effectiveness: The operations of the algorithm must be basic enough to be put down on pencil and paper
BCA-S202T: DS  Space Complexity: The space complexity of an algorithm or program is a function of the space needed by

You might also like