# CE2002-A Data Structure

## Array

## Stack

## Queue

## Linked list

## Tree

## Heap

# Chapter01 - Basic Concepts

1. Requirements
2. Analysis
3. Design
4. Refinement and coding
5. Verification

## **Intro to Algorithm**
1. Sort
2. Compare
3. Search
4. Recursive

## **Data Abstraction**

### Struct

It's the collections of the elements whose data types need not be the same. -> They are explicitly defined.

struct student {
    char last_name;
    int student_id;
    char grade;
}

### Abstract data type(ADT).

implementation-independent.
1. Creator/Constructor
2. Transformers
3. Observers/Reporters

**The symbol `::=` -> should be read as "is defined as".**

## **Performance analysis**

* Fixed space requirements.
* The component refers to space requirements that do not depend on the number and size of the program's inputs and outputs.
* Variable space requirements.
* $S(P) = c +S_{p}(I)$

> $S_{abc}(I) = 0$
> ``` c
> /* Three inputs, this function has only fixed space requirements. */
> float abc(float a, float b, float c) {
> return a + b + b * c + (a + b - c) / (a + b) + 4.00;
> }
> ```

/*  */
float sum(float list[], int n) {
    float tempSum = 0;
    int i;

    for (i = 0; i < n; i++) 
        tempSum += list[i];
    
    return tempSum;
}

### Time complexity

#### Magic square

# Chapter02 - Arrays and Structures

## Arrays

<index, value>

## Structures and Unions

permits the data to vary in type.

/* Both are the same */

typedef struct humanBeing {
  char name[10];
  int age;
  float salary;
};

typedef struct {
  char name[10];
  int age;
  float salary;
} humanBeing;

`struct {int i, j; flaot a, b;};` `struct {int i; int j; flaot a; float b;};`

### Self-Referential Structure

typedef struct list {
  char data;
  List *link;
} List;

## The Polynomial Abstract Data Type

EX:

$A(x) = 3 x^{20} + 2x^{5} + 4$ and $B(x) = x^{4} + 10 x^{3} + 3x^{2} + 1$

$A(x) + B(x) = \sum (a_i + b_i) x^i$

$A(x)B(x) = \sum ((a_i x^i)\sum b_j x^j)$

this is the ordered list
### ADTs

1. finding the length of the list
2. reading the items in a list from left to right
3. retrieving the ith item from the list
4. replacing the item from the ith position of the list
5. inserting the new item in the ith position of the list
6. deleting an item from the ith position of a list.

## The Sparse Matrix

finding representations that let us efficiently perform the operations.

## Matrix Multiplication

for (i = 0; i < rows_a; i++)
  for (j = 0; j < cols_b; j++) {
    sum = 0;

    for (k = 0; k < cols_a; k++) {
      sum += (a[i][k] * b[k][j]);
      d[i][j] = sum;
    }
  }