Data Structure

Introduction

Data

Define: The set of all the symbols can be processed or stored by a computer Example: A data set in a classroom = { desk 1, desk 2,…chair 1, chair2…,stud 1, stud 2,…}

Data Element

Define: The term data element is an atomic unit of data that has:

1. An identification such as a data element name
2. A clear data element definition

Example: desk i; chair j; project n…

Data item

Define: One smallest indivisible data units

!!! One data element consists of one or many data items.

Data Object

Define: The collection of data elements with same features.

Example: Data Object 1: ={ desk 1, desk 2,…};

Data Object 2: ={ chair 1, chair 2,…};

Data Object 3: ={ stud 1, stud 2,…};

On Data Object3, The data of a student is a set of {ID, FirstName, LastName, age}, in a list of student, the list of age = {12, 13, 12, …}, then ->

Data Element:age

Data item: 12

Structure

Relationships between data elements

Data Structure

A set of data elements with structure

Data Structure can be defined is math

Data Structure = (D, R)

D: the set of Data elements

R: the Relationships of the data elements

DS is formed by two sets:

1. Data element set
2. Relationship set

Class of Structure

1. logic structure -> {Set, Linear, Tree, Graph}
2. Physical structure -> Such as a Linear structure use sequence structure or Linked structure ?

About algorithm

1. Algorithm design depends on logical structure(Like in math)
2. Algorithm implementation depends on how to store the DS physical structure

Data Type

Define: A data type is a collection of objects and a set of operations that act on those objects.

Example:int, double … and std::vector<>, std::map<> …

Abstract Data Type (ADT)

Define:An abstract data type(ADT) is a data type that is organized in such a way that the specification of the objects and the operations on the objects is separated from the representation of the objects and the implementation of the operations.

Conclusion: Consider only the mathematical level, not the actual computer structure

Mathematical definition of ADT：

1. D：Data object , the set of the data elements
2. S：the structure on the object D
3. P：Operations performed on the object

Example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

/*
Data Object, Data relation, Operations
*/
class Complex {
private: //Data Object
    real;
    image;
    //Data relation:real part and image part in a complex
public://Operations
    Add(Complex Other);
    GetRead();
    //.....
}

Kind of parameters

1. Value parameter
2. Reference parameter (in c++ is &)

Summary

1. DS = Data elements + Relationships of data elements
2. Data structures + Algorithms = Program
3. ADT = DS + Operations