本章节主要是关于数据结构一些基本概念的介绍。
[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))
