Karen - Dstr notes

Data Structure Overview

Fundamental Concepts

A computer is a programmable data processor that accepts input in various forms, processes it according to a programmed sequence of instructions, and generates desired output. The core components crucial for this process include:

• Program: A sequence of instructions designed to achieve a specific task or solve a problem.

• Software: A collective term for programs that fulfill user needs, including applications, operating systems, and utilities.

• Hardware: The physical machinery and electronic components that execute the instructions provided by software, including CPUs, memory, storage devices, and input/output devices.

Program Development Life Cycle

The development of software follows a structured process known as the Program Development Life Cycle (PDLC), which typically includes the following steps:

1. Define the Problem: Create a precise problem statement outlining the issue at hand or the objective to be accomplished.

2. Select an Algorithm: Choose the most suitable algorithm that can effectively solve the problem, considering performance and resource constraints.

3. Develop Code: Write the actual code based on the selected algorithm, utilizing a programming language appropriate for the task.

4. Testing and Debugging: Thoroughly test the code for errors, ensuring that it performs as expected; debug any issues that arise during testing.

5. Documentation: Maintain comprehensive documentation of the process, findings, and code to aid future reference and facilitate maintenance.

Introduction to Data Structures

Programming often requires the storage and manipulation of different types of information. This necessity leads to the creation of data structures, which are organized formats for storing and managing data.

• Variables: Basic units for storing information; each variable can hold a single data entity like an integer or string. However, using a lone variable may not efficiently solve more complex problems, necessitating the implementation of data structures.

Data Types

Data types can be classified into two main categories:

• Atomic Data: This refers to single, indivisible entities (e.g., integer, character) that cannot be broken down into smaller components.

• Composite Data: These are data types that can be decomposed into subfields (e.g., records containing multiple attributes about a student).

Built-in Data Types Include:

• Primitive Types: Basic data types such as character (char), short (short), integer (int), and long (long).

• Floating-point Types: Data types for representing real numbers, including float, double, and long double.

• Structured Types: More complex data arrangements such as arrays, structures, unions, and classes that allow the aggregation of different data types.

Abstract Data Types (ADT)

An ADT encapsulates data and provides declarations of data types along with implementations of operations. This encapsulation hides the complexities from users while allowing data manipulation. Common examples of ADTs include:

• Lists: Ordered collections of items.

• Queues: Collections that follow the FIFO (First In First Out) principle.

• Stacks: Collections that follow the LIFO (Last In First Out) principle.

Algorithms

An algorithm is a set of well-defined, simple steps or instructions aimed at achieving a particular result. The efficiency of algorithms is measured using Big O notation, which helps categorize them based on their performance:

• O(1): Constant time, independent of input size.

• O(n): Linear time, directly proportional to input size.

• O(n^2): Quadratic time; performance degrades quadratically with an increase in input size.

Fundamental Concepts of Programming (Part 1)

C programming involves various commands and preprocessor directives that typically begin with #, providing instructions for the compiler before actual code compilation.

Syntax for the Main Function:

int main() {
    // body of function
    return 0;
}

Control Structures Include:

• Selection Control: Used for making decisions (e.g., if, else, switch statements).

• Repetition Control: Used for executing repetitive tasks (e.g., while loops, for loops, do...while loops).

Functions

Functions provide modularity and reusability in programming. A function is defined by three main components:

• Type: The return data type (such as void, int, etc.).

• Name: A unique identifier for the function.

• Parameter List: The inputs provided to the function, which can be passed by value or reference.

Arrays

An array is a collection of fixed-size components that all share the same data type. The structure allows for efficient storage and manipulation of data.

• Syntax: dataType arrayName[size];

• Accessing Elements: arrayName[index], where indexing starts at 0 (0-based indexing).

• Initialization: Arrays can be initialized at the time of declaration.

Two-Dimensional Arrays

A two-dimensional array extends the concept of a simple array, organizing data into a grid format characterized by rows and columns.

• Syntax Example: dataType arrayName[rows][columns];

Classes and Objects (Part 2)

In object-oriented programming, classes serve as blueprints for creating objects that encapsulate data and functionalities. A class is defined by the following:

class ClassName {
public:
    // public members
private:
    // private members
};

• Constructors: Special member functions called automatically when an object is instantiated. They are used to initialize the object's attributes.

Dynamic Memory and Pointers

Pointers are variables that store memory addresses, enabling efficient memory manipulation. They must be initialized before use to avoid pointing to random memory locations. Dynamic memory allocation allows the program to manage memory effectively for objects and arrays, using operators new and delete to allocate and deallocate memory as needed.

Linked Lists (Part 1)

Linked lists consist of a sequence of nodes that are linked together by pointers, facilitating efficient insertion and deletion of elements. Each node contains:

• Data: The information stored in the node.

• Link: A pointer to the next node in the sequence.

• Basic operations include: Insertion, deletion, and traversal of nodes.

Improvements to Linked Lists

Techniques can be employed to enhance linked lists, including:

• Efficient Insertions: Techniques for inserting elements at the end of the list without traversing through it entirely.

• Reverse Printing: Methods for printing nodes in reverse order without using additional memory structures.

Stacks and Queues

Stacks and queues are fundamental data structures that manage collections of items:

• Stack: Implements a LIFO (Last In First Out) approach. Key operations are:

  • push: Add an element to the top.

  • pop: Remove the top element.

  • top: Access the top element without removing it.

• Queue: Implements a FIFO (First In First Out) approach. Key operations involve:

  • Adding (enqueue) and deleting (dequeue) elements from different ends of the structure.

Trees and Graphs

Trees are hierarchical data structures composed of nodes connected via edges. Important properties of trees include:

• Root: The top node of the tree.

• Parent/Child relationships: Nodes can have zero or more children.

• Leaf Nodes: Nodes that do not have any children.

• Binary Trees: A specific type of tree structure with at most two children per node, involving traversal methods such as pre-order, in-order, and post-order.

Graphs

Graphs represent relationships between entities and consist of:

• Vertices: The individual items or nodes.

• Edges: The connections between these nodes.

Graph Terminology Includes:

• Degree of Nodes: The number of edges connected to a vertex.

• Adjacency Matrix: A square matrix used to represent a finite graph, indicating whether pairs of vertices are adjacent.

• Adjacency List: A collection of lists or arrays that represents which vertices are adjacent to each vertex.

Graph Algorithms

Several algorithms help manipulate and work with graphs, including:

• Traversal methods: Such as Depth First Search (DFS) and Breadth First Search (BFS), used to visit all the vertices.

• Shortest Path Algorithms: Algorithms that determine the optimal path between two vertices within a graph.

• Minimum Spanning Tree Algorithms: These, such as Kruskal's and Prim's algorithms, find a subset of edges that connects all vertices together while minimizing the total edge weight.