# Data Structure (I) - 02 Arrays
> PART (I) - 02
> Other parts in this series $\rightarrow$ [Data Structure - Syllabus ](/bU7575BKTwmwkvmJ5742xA)
> All the code in this part $\rightarrow$ [Array](https://github.com/Benny0w0Liu/Data-Structure-Learning/tree/main/Array)
# Array as ADT
* **A set of pairs <index, value>** where for each value of index (索引) there is a corresponding value.
* Index set is a finite ordered set of one or more dimensions.
For example:
* {0,...,n-1} for one dimension.
* {(0,0), (0,1),(0,2),(1,0),(1,1),...,(3,2)...} for two dimensions.
## constructor
Need a constant size.
## operations
* Sets the value of index i to v
* Gets the value of index i
# Implementation
Um... I think we all know that how to do that in C and C++(`int arr[n]`), so we will just start with example:D
# Application(Using C++)
## Polynomial
### 1st way
To store a polynomial function we can use array. To do that, firstly, we need the highest degree of function, then, we can store the coefficient of each degrees.

| degree | $x^0$ | $x^1$ | $x^2$ | $x^3$ | $x^4$ |
| -------- | -------- | -------- |-------- |-------- |-------- |
| coefficient | 12 |7 |9 |13 |3 |

Polynomial function = $3x^4+13x^3+9x^2+7x^1+12$
* Example : [C++ Code](https://github.com/Benny0w0Liu/Data-Structure-Learning/blob/main/Array/1_01_Polynomial.cpp?ts=4)
### 2nd way
We can also use 2d array to store the function, it is more efficiently when most of coefficients are 0.
e.g.
Polynomial function = $3x^4+12$
Then we can store it as:
| degree |coefficient|
| -------- | -------- |
|4|3|
|0|12|
* Example : [C++ Code](https://github.com/Benny0w0Liu/Data-Structure-Learning/blob/main/Array/1_02_Polynomial.cpp)

## Matrix
There are two ways to store the a matrix.
### 1st way
Using 2D array(What we use to do)
For example: $3\times4$ matrix

|| Column 0 | Column 1 |Column 2|Column 3|
| --- | --- | --- |--- |--- |
|Row 0|1|0|0|0|
|Row 1|0|0|7|0|
|Row 2|0|0|0|0|
* Example : [C++ Code](https://github.com/Benny0w0Liu/Data-Structure-Learning/blob/main/Array/2_01_Matrix.cpp?ts=4)
### 2nd way
The second way is expecially useful for sprase matrix (稀疏矩陣). It only store the nonzero values and the position of them. Take the 1st example, the table will be like:
Row| Column |Value|
--- | --- |---
|0|0|1|
|1|2|7|
* Example : [C++ Code](https://github.com/Benny0w0Liu/Data-Structure-Learning/blob/main/Array/2_02_Matrix.cpp?ts=4)
## String in C/C++
If you are unfamiliar with string in C/C++, here you go $\rightarrow$ [Videos](https://www.youtube.com/playlist?list=PLqjW-ORyj-hLKFq_ESmFpXDnaLKaTCMio) & [C++ Week 03](/QtqztVJGTe6odqw_omzMFA)
> ### String Matching Problem
> * Given a text string T of length n and a pattern string P of length m, the exact string matching problem is to find all occurrences of P in T.
> * Example: T="AGCTTGCTA" P="GCT"
> * Applications:
> * Searching keywords in a file (Text Editor)
> * Searching engines (Google)
> * Database searching (GenBank)
### KMP Algorithm for String Matching
* Proposed by Knuth, Morris and Pratt
* Time complexity: O(m+n)

{%youtube V5-7GzOfADQ %}
[the video](https://www.youtube.com/watch?v=V5-7GzOfADQ)
* Example : [C++ Code](https://github.com/Benny0w0Liu/Data-Structure-Learning/blob/main/Array/3_String_KMP.cpp?ts=4)