هياكل البيانات والمصفوفات

Introduction to Data Structures

• Data structures are ways to organize information in a computer to efficiently retrieve and use it.
• Data structures are important for designing both structural and functional aspects of a program.
• A program is composed of an algorithm and a data structure.
• An algorithm is a step-by-step procedure to solve a particular task.

Course Outlines

• The courses will cover stacks, queues, general lists, search algorithms in lists (linear and binary search, and their mathematical analysis), binary search trees, and an introduction to graphs.
• Implementations will include array-based and linked-based approaches.

What is a Computer Program?

• To understand data structures, one must know what a computer program is.
• A computer program takes input, performs some operations (processing), and produces output.

Definition

• A data structure is an organization of information (data) in computer memory to improve efficiency of algorithms.
• Examples include queues, stacks, linked lists, heaps, dictionaries, and trees.

3 steps in the study of data structures

• Logical or mathematical description of the structure.
• Implementation of the structure on a computer.
• Quantitative analysis of the structure, including memory needs and processing time.

Data Organization

• Different ways to organize data exist (e.g., arrays, linked lists, trees).
• The best choice of data structure depends on how well it mirrors real-world relationships and how easily it allows the data to be processed. Data structure examples are arrays, linked lists, trees etc.

Issues

• Data structures often have issues regarding space requirements, and the efficiency of operations (insertion, retrieval, deletion).

What Data Structure to Use

• Data structures are used to handle input and output effectively and efficiently.
• Examples include arrays, linked lists, queues and stacks

Why Data Structures?

• Data structures are critical for efficient storage and retrieval of data in a computer.

Definition (revisited)

• Data structures define the logical relationships among data elements.
• They are important for ways to organize data in a way that handles not only the individual elements but also the relationships between them.

Introduction

• Data structures affect the design of both structural and functional aspects of a program.
• A program = algorithm + data structure.
• An algorithm is a step-by-step procedure to solve a specific problem.

Algorithms

• An algorithm is a step-by-step procedure for calculations.
• An algorithm is an effective method represented as a finite list of well-defined instructions for solving a problem.

Algorithm (revisited)

• Algorithms define instructions for carrying out particular tasks.
• The data structure is the means for organizing the data according to its logical relationships.
• Selecting the appropriate data structure determines the success of a program.

Data Structure Classification

• Primitive/Non-primitive: Basic building blocks/constructed from primitives.
• Homogeneous/Heterogeneous: All data elements of the same type/different types.
• Static/Dynamic: Memory allocated at compile time/run time.
• Linear/Non-linear: Elements have a sequence/no inherent sequence.

Classification of Data Structures (revisited)

• Data structures are classified into two broad categories: primitive and non-primitive data structures.
• Primitive data structures are basic building blocks like integers, floats, characters, and pointers, that the computer directly operates on.
• Non-primitive data structures are constructed from primitive data structures to organize and handle data more sophistically, including lists, stacks, queues, trees, and graphs.

Primitive Data Structure

• These are basic elements handled by machine instructions.
• Examples include integers, floating-point numbers, characters, strings, and pointers..

Non-Primitive Data Structure

• These are derived from primitive structures.
• These structures deal with heterogeneous or homogeneous collections of data items.
• Examples include lists, stacks, queues, trees, and graphs

Non Primitive Data Structure (revisited)

• Examples of non-primitive data structures include lists, stacks, queues, trees, and graphs.
• Efficient design of non-primitive data structures factors in operations that will be performed against the structure.

Operations on Data Structures

• Common operations on data structures include creation, selection, updating, searching, sorting, merging, and destruction/deletion.

Differences

• Primitive data structures are basic, built-in language elements (like int, float).
• Non-primitive structures are complex, built from primitives to link various data elements (e.g., arrays, linked lists, trees).

Arrays

• Arrays store elements of the same data type in contiguous memory locations.
• One-dimensional arrays have a single index to access elements.
• Two-dimensional arrays use row and column indexes, offering a tabular structure.

One-Dimensional Arrays

• Declaring an array specifies the data type, array name, and size.
• Example: int x[5];
• Initializing an array with values: int x[5]={10,20,30,40,50};

Accessing Array Elements

• Elements are accessed using their index (starting from 0).
• Example: X[2] (accesses the third element).

Multi-Dimensional Arrays

• Declaring/initializing: int y[2][3] = {{10,20,30},{40,50,60}}; .

Sorting Arrays

• Sorting arranges data in a specific order (ascending or descending)..
• Sorting techniques like Bubble Sort, Insertion Sort, and Selection Sort utilize different approaches to rearrange elements for easier searching in a sorted array

Sorting Efficiency

• The efficiency of sorting techniques is measured by execution time and space consumed.
• Different sorting algorithms perform better depending on various parameters.

Sorting Techniques

• Sorting techniques, such as bubble sort, insertion sort, and selection sort, vary in their efficiency.

Bubble Sort

• Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order (i.e., unsorted).
• It continues until no swaps are needed. This process makes the largest elements ‘bubble’ towards the end of the list

Insertion Sort

• Insertion Sort is a relatively simple algorithm that gradually builds a sorted array one element at a time. This is typically efficient when dealing with a smaller dataset that consists of a small number of data values.

Selection Sort

• Selection sort is another simple sorting method that works by repeatedly selecting the minimum element from the unsorted portion of the array and placing it at the beginning.

Complexity Analysis

• Bubble sort has O(n2) time complexity in both the average and the worst case.
• Insertion sort has O(n2) time complexity in the average and worst cases, but can be more efficient in the best case.
• Selection has same time complexity of O(n^2) with all different cases.

Additional Sorting Methods (Insertion and Selection)

• Insertion sort and selection sort are simple, but not optimally efficient to use for extremely large datasets
• The space complexity of these sorting algorithms is O(1), as they typically only use extra space for a temporary variable during swapping operations.

هذا الاختبار يناقش الهياكل المختلفة للبيانات، بما في ذلك المصفوفات وأنواعها. سيتم اختبار معرفتك بعمليات إدخال البيانات، حذفها، والفرق بين المصفوفات والقوائم المرتبطة. استعد لاختبار معلوماتك حول تصميم البيانات وإدارتها.