# 資料結構 期中重點整理 ch2

###### tags: `資料結構` `複習用` `高科大`

:::spoiler **文章目錄**
[TOC]
:::

## ADT資料型態和C++ Class類別

### C++裡面的四個元件
>1. class name 類別名稱

>2. data members 靜態資料成員

資料由類別組成。

>3. member function動態 成員函式

設定運算集()可以應用在類別的物件中。

>4. levels of program access程式存取之層次
1. public 公開的
2. protected 保護的 ==公開+私有，部分人能拿取==
3. private 私有的 ==決定誰可以碰到他==

EX.

### 建構子
>建構子(函式)名稱要跟類別名稱相同。
D

class Teacher
{
    int rate;
    Teacher(int rate)
    {
        this.rate=rate;
    }
}

### 運算子多載Operator Overloading

<!-- >考慮運算子 == ，==通常用來檢查兩個資料項目是否相等，實作==的硬體演算法因運算元型態不同而有所不同。 -->


>運算子（比如+，=或==）被當作多型函式，它們的行為隨著其參數類型的不同而不同。

### ADT of Array
>每個值對應索引配置中，可以隨意拿東西跟放東西。
><index,value>

>舉例一維陣列(畫圖)

>舉例多維陣列(畫圖)

### 陣列尋找Mapping
A[i][j]=A[0][0]+i*4+j

### Java陣列
>Java利用一維陣列，模擬出多維陣列。
dimensional

### 線性串列/有序串列
O(1)，O(n)翻譯

element

### Linear List Operation操作/運算

1. Length(L)長度
2. Retrieve 索引、擷取
3. Indexof 指數
4. Delete 刪除
5. Insert 插入/新增
6. Modify 修改

### Polynomial多項式
f(x)=x^8-10x^5+3x^3+1.5

terms 項目=>x次方有幾個
Coefficients 係數
Non-negative integer exponent非負整數 指數/冪(次方) 8,5,3,0

>多項式為了節省空間

### Polynomial Representation 多項式的表示法
a(x)=2^1000+1

| | 0 | 1 | 2 |
| ------ | --- |:----:| --- |
| a_coef 係數 | 2(有2項) | 2 | 1 |
| a_exp 次方 | | 1000 | 0 |

b_coef 有4項 2 1 係數

b_exp 1000 0 次方


O(m+n)全部需要的時間複雜度

### Appending New Term 增加擴充減少 比較有[效率]

### Sparse Matrices 稀疏矩陣
>只有少部分有值，剩下幾乎都是0。
舉例:
Matrix=>table of values

1. 計算速度更快
2. 節省儲存空間
3. ?

浪費空間用此=>

### 陣列表示法
>多維度的陣列，通常由一維陣列通過列主序或行主序實現。

### 列主序 Mapping對映
>通過每列收集元素將其轉換成一維陣列y。

>在一列中，有左至右收集元素。

>每列從上至下收集

>We get y={a,b,c,d, e,f,g,h ,i,j,k,l}

### 行主序 Mapping對映
>通過每行收集元素將其轉換成一維陣列y。

>在一行中，有上至下收集元素。

>每行從左至右收集

>We get y={a,e,i ,b,f,j ,c,g,k ,d,h,i}

### Matrix 矩陣
>多個值的表

>通常用於 手機照片、人臉辨識、影像的辨視處理

>一個 M*N 的矩陣式由 M 列 N 行元素排列成的矩形陣列

#### 陣列跟矩陣的差別
>有行和列，但編號從1開始，而不是從0開始

>使用x(i,j)，不用x[i][j]

>我們可以使用2維陣列表示一個矩陣。

### Lexicographical order字典排序
>又稱，辭典、辭法順序、字典排序、字典順序、辭典產品。

### Memory Mapping記憶對映 (從2維到1維)
A[i][j]=A[0][0]+(i * 4 + j)
A[i][j]=A[0][0]+(i + j * 4)

### Memory Mapping(計算)

### String字串
>通常用字串表示字元陣列。

>一般字串操作包含 比較、字串連接、複製插入、字串比對，輸出等。

>null=>直到\0為止停下。

### 背
strcat ,strncat
strcmp
後續打

### 字串比對 問題
>兩個字串 T 和 P，找出 T 當中是否有一段字串正好是 P，並且找出位置。

### 字串專有名詞
#### Substring子字串
S1,3=>字串的1~3
S0,4=>字串的0~4
取該index的值

#### Subsequence子序列
>一串資料中其中一部分的資料。

>某串序列將不需要的資料，移除後得到的新序列。

<a class="btn btn-primary" href="https://hackmd.io/@chiaoshin369/dataTest1">**<** 上一個 資料結構 期中重點整理 ch1 </a> <a class="btn btn-primary" href="https://hackmd.io/@chiaoshin369/dataTest2" role="button"> 下一個 期中考重點整理 **>**</a>