🔑【数据结构】之绪论

绪论

c和c+语言基础

答题

1. 综合题：三段式模式，即算法分析、代码实现、复杂度分析
2. 变量：在用到的地方加上一句注释，说明某某变量之前已经定义即可。

指针

1. 指针：指针变量里面装的是变量的地址，可以找出这个变量在内存中的位置int *a=&b;
2. *a就是取变量b的内容，&b就是取变量b的地址，语句a=&b;就是将变量b的地址存于a中。
3. 指针型在考研中用的最多的就是和结构型结合起来构造结点（如链表、二叉树的结点等）

链表结点

链表结点的构造型定义如下

    tpyedef struct Node
    {
        int data; //这里默认的是int型，如需其他类型可修改
        struct Node *next; //指向Node型变量的指针
    }Node;
    //next所指的结点B与结点A是属于同一结构型

二叉树结点

• 定义如下

typeddef struct BTNode
{
    int data;
    struct BTNode *lchild; //左孩子结点
    struct BTNode *rchild; //右孩子结点
}BTNode;

• 制作新二叉树结点

BTNode BT; //此为第一种
/*****************/
BTNode *BT; //此为第二种
BT=(BTNode*)malloc(sizeof(BTNode)); //要求熟练掌握
//第二种：先定义一个结点的指针BT，然后用函数malloc()来申请一个结点的内存空间，最后让指针BT指向这片空间

• 对于两种方法取分量的操作也是不同的：
  1. 对于第一种，x=BT.data;
  2. 对于第二种，x=BT->data; ，(*BT).data与BT->data是等价的
  3. 一般来说，用结构体变量直接取分量，其操作用“ . ”，用指向结构体变量的指针来取分量，其操作用“ -> ”。
• 申请动态数组空间的方法，可以一次申请一组结点

int *p;
p=(int *)malloc(n * sizeof(int));//不同之处尽在与sizeof运算符前要乘以 n

关于typedef 和#define

• typedef用的最多的地方就在结构体的定义过程中
• #define用来定义，但在作答时在用到变量前加上注释说明已经定义即可

函数传参

• 整型变量：变量本身并不会发生改变，需要采用指针
• 数组：将数组作为参数传入函数，函数就是对传入的数组本身进行操作
• 二维数组作为参数的函数定义方法如下：

void f(int x[][maxSize],int n) //第二个参数n，指用来说明将来要传进参数加工的数组元素的个数，并不是指数组的总长度
{
    ...;
}

时间复杂度与空间复杂度

时间复杂度

• 定义：将算法中基本操作的执行次数作为算法时间复杂度的度量
• 常用的比较关系：
  O($1$)<=O($\log_2(n)$)<=O($n$)<=O($n\log_2(n)$)<=O($n^2$)<=O($n^3$)<=...<=O($n^k$)<=O($2^n$)
• 多数情况下取最深层循环内的语句所描述的操作为基本操作

空间复杂度

• 算法空间复杂度指算法在运行时所需存储空间的量度

基本概念

数据结构的基本概念

1. 数据：数据是对客观事物的表示
2. 数据元素：数据元素是数据的基本单位
3. 数据项：数据项是数据结构中讨论的最小单位，是数据记录中最基本、不可分的数据单位
4. 数据对象：数据对象是性质相同的数据元素合集，是数据的子集
5. 数据结构：数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，包括 逻辑结构、存储结构和对数据的运算
6. 数据的逻辑结构：是对数据之间关系的描述，与数据的存储结构无关，同一逻辑结构可以有多种存储结构，逻辑结构主要分为：
   1. 线性结构
      简单的说，线性结构是一个数据元素的有序集合，有以下四个基本特征：
      1. 集合中必存在唯一个“第一元素”
      2. 集合中必存在唯一个“最后一个元素”
      3. 除最后一个元素外，其他数据元素均有唯一“后继”
      4. 除第一个元素外，其他元素均有唯一“前驱”
         数据结构中，线性结构是指数据元素之间存在着“一对一”的线性关系的数据结构
   2. 非线性结构
      与线性结构不同，非线性结构中的结点存在一对多的关系，可以细分为树形结构和图形结构
7. 数据的物理结构：数据的物理结构又称为存储结构，是数据的逻辑结构在计算机中的表示（又称映像），包括数据元素的表示和关系的表示。数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像
8. 数据结构常用的四种存储方法：
   1. 顺序存储方法：逻辑上相邻的结点存储在物理位置山相邻的储存单元中，结点之间的逻辑关系由存储单元的邻接关系来体现
   2. 链式存储方法：不要求逻辑上相邻的结点在物理位置上相邻，逻辑关系由指针字段表示
   3. 索引存储方法：存储结点信息时除建立存储结点信息外，还建立附加的索引表来标示结点的地址
   4. 散列存储方法：根据结点的关键字通过散列函数直接计算出该结点的存储地址，本质上是顺序存储方法的扩展

算法的基本概念

1. 算法：由基本运算及规定的运算顺序所构成的完整解题步骤，或看成按照要求设计好的有限的确切计算序列
2. 算法特性：
   1. 有穷性
   2. 确定性
   3. 输入
   4. 输出
   5. 可行性
3. 算法的设计目标
   1. 正确性
   2. 可读性
   3. 健壮性
   4. 高效率与低存储量需求