本章節主要是關于數據結構一些基本概念的介紹。
[TOC]
*****
# 數據結構的基礎知識
## 幾個概念
1. **數據**（data）是對客觀事物的符號表示，是指所有能夠輸入到計算機并被計算機程序識別和處理的符號的集合。
2. **數據元素**（data elment）是數據的基本單位。一個數據元素可由若干**數據項**（data item）組成。數據項是數據元素不可分割的最小單位。如果將某個班級所有學生信息看作一組數據，這組數據由若干個學生記錄（數據元素）組成，而每個記錄則有學號、姓名、性別等數據項組成。
3. **數據對象**（data object）是性質相同的數據元素的集合，是數據的一個子集。
4. **數據結構**（data structure）是相互之間存在一種或多種特定關系的數據元素的集合。數據結構包括三方面的內容：**邏輯結構、存儲結構和數據的運算**。數據的邏輯結構與存儲結構是密不可分的兩個方面，一個算法的設計取決于所選定的邏輯結構，而算法的實現依賴于所采用的存儲結構。
## 數據結構
### 邏輯結構
邏輯結構指數據元素之間的邏輯關系。數據的邏輯結構分為線性結構和非線性結構。線性表是典型的線性結構；集合、樹、圖是典型的非線性結構。
1. 線性結構 結構中的數據元素之間只存在一對一的關系——線性表。
2. 集合 結構中的數據元素之間除了“同屬于一個集合”的關系外，無其他關系。
3. 樹形結構 結構中的數據元素之間存在一對多的關系。
4. 圖形結構 結構中的數據元素之間存在多對多的關系。
### 存儲結構
存儲結構指數據結構在計算機中的表示（又稱映像），又稱物理結構。包括數據元素的表示和關系的表示。數據的存儲結構主要有順序存儲、鏈式存儲、索引存儲和散列存儲。
#### 1.順序存儲
將邏輯上相鄰的數據元素存儲在物理位置上也相鄰的存儲單元里。數據元素之間的關系由存儲單元的鄰接關系表示。順序存儲的優點：可以實現數據元素的隨機存取（在編程語言中通過數組實現），占用存儲空間最少。
順序存儲的缺點：只能使用一整塊相鄰的存儲單元，易產生較多碎片（可能比1kb還小，無法利用），造成空間浪費。
#### 2.鏈式存儲
不需要將邏輯上相鄰的數據元素存儲在物理位置是也相鄰的存儲單元里，借助指示元素存儲地址的指針表示數據元素之間的邏輯關系。
鏈式存儲的優點是不會產生碎片現象，能充分利用存儲空間。
鏈式存儲的缺點是每個指針需占用額外的存儲空間，且只能按照指針指示關系進行元素的存取。
#### 3.索引存儲
通過建立索引表來指示元素。
優點是檢索速度快。缺點是增加了額外的索引表占用較多存儲空間。
#### 4.散列存儲
通過哈希（Hash）函數計算元素的存儲地址，又稱Hash存儲。
優點是檢索、增加和刪除元素的速度都很快。缺點是哈希函數取得不好可能導致存儲空間沖突，要解決空間沖突則增加了額外的時間和空間花費。
### 數據的運算
包括運算的定義和實現。定義指示我們選出邏輯結構，實現指示我們通過存儲結構指出運算的具體操作步驟。
*****
# C語言的一些基礎知識
## 一個最簡單的C程序
```c
#include <stdio.h>
int main(){
printf("Hello C.");
return 0;
}
```
## 注釋
注釋是給人看的，解釋某行代碼或某幾行代碼。計算機遇到注釋符號 `/**/` `//` 便不作理會其注釋內容。
多行注釋 `/* 這里寫注釋內容 */`
單行注釋 `// 這里寫注釋內容`
## 變量與賦值語句
變量是存儲數據的“盒子”。在C語言中，要使用變量需先聲明變量，如下：
```c
int var; // 定義一個名叫var的變量
```
int 是C中的整型數據類型。變量要使用，需初始化，雞必須給變量賦一個值，如下：
```c
int var;
var = 100; // 給變量var賦初值為100
```
## 類型定義typedef與結構體
定義順序表：
```c
typedef struct{
int data[MAXSIZE]; // 數據域
int length; // 順序表當前長度
}SeqList;
```
## 選擇語句
1、條件語句 if
```c
// if型
if(表達式){
語句;
}
// if···else型
if(表達式){
語句;
}
else{
語句;
}
// if···else if···else型
if(表達式){
語句;
}
else if(表達式){
語句;
}
...
else{
語句;
}
```
2、開關語句switch
```c
switch {
case 條件1: 語句1; break;
case 條件2: 語句2; break;
...
case 條件n： 語句n; break;
default: 語句n+1;
}
```
## 循環語句
1、for循環語句
```c
for(賦初值表達式序列; 條件; 修改表達式序列){
語句;
}
```
2、while循環語句
```c
while(條件){
語句;
}
```
3、do-while循環語句
```c
do {
語句;
}while(條件);
```
## 輸入輸出
輸入 `scanf([格式串],變量1,...,變量n)`
輸出 `printf([格式串],表達式1,...,表達式n)`
*****
# 算法分析
## 算法（Algorithm）
算法是對特定問題求解步驟的一種描述。它是指令的有限序列，其中每一條指令表示一個或多個操作。
## 算法的特性
1. 有窮性 算法須在有窮步之后結束，且每一步均在有窮時間內完成。
2. 確定性 算法中的每一條指令含義必須是確切的。且，對于相同的輸入只能得到相同的輸出。
3. 可行性 一個算法是可行的，它一定能夠解決所描述的問題。
4. 輸入 一個算法有零個或多個輸入。
5. 輸出 一個算法有一個或多個輸出。這些輸出同輸入有某些特定的關系。
## 算法設計要求
1. 正確性 設計的算法應當能夠正確地解決待解問題。
2. 可讀性 設計的算法應當便于人們閱讀與理解。
3. 健壯性 設計的算法應當能夠應對非法輸入數據。
4. 效率與低存儲量需求 設計的算法執行所花的時間應盡量短，所耗費的存儲空間應盡量少。
## 算法效率的度量
通過時間復雜度與空間復雜度描述。
1.時間復雜度 T(n) = O(f(n)；n是問題規模。
2.空間復雜度 S(n) = O(g(n))
