嵌入式学习day17（数据结构）

大纲

为什么要学数据结构？

     1.C语言是学习如何写程序，数据结构是学习如何简洁高效的写程序
      2.如果遇到一个实际问题，需要写代码实现相应功能，需要解决两个问题：
          （1）.如何表达数据间的逻辑关系以及怎么存储到计算机当中？
                         数据结构：数据的逻辑结构以及存储操作
                         数据：不再是单纯的数字，而是类似于一个集合的概念
                         结构：数据之间的关系
         （2）.采用什么方法去解决？
                               采用算法去解决

数据结构+算法=程序

一丶数据结构

1.概念

          数据的逻辑结构，存储结构及操作（数据的运算）

2.数据

3.结构

3.1逻辑结构

数据元素并不是独立存在的，他们之间存在着某种关系（联系或结构）。

元素和元素之间的关系：
线性关系：
     线性关系 ---》 线性结构 ---》一对一 ----》线性表：顺序表、链表、栈、队列
层次关系：
     层次关系 ---》 树形结构 ---》一对多 --- 》 树：二叉树
网状结构：
     网状关系 ---》 图状结构 ---》 多对多 ---》图

3.2存储结构

数据的逻辑结构在计算机中的具体体现（数据的运算）

顺序存储：
特点：内尺连续，随机存取，每个元素占用较少
实现：数组

链式存储：
特点：内存不连续，通过指针实现
链表实现：通过定义结构体，里面是数据域和指针域

#include<stdio.h>
struct node
{
    int data;//数据域，存放节点要保存的地址
    struct node *next;//指针域，指向下一个节点的地址（类型为结构体指针）
};
int main(int argc, char const *argv[])
{   //定义三个节点
    struct node A={1,NULL};
    struct node B={2,NULL};
    struct node C={3,NULL};
    //连接三个节点
    A.next=&B;//连接A和B节点，让A中的指针域保存B的地址
    B.next=&C;//连接B和C节点，让B中的指针域保存C的地址
    printf("%d\n",A.data);//打印A中的数据域
    printf("%d\n",(A.next)->data);//打印B中的数据域
    printf("%d\n",(A.next)->next->data);//打印C中的数据域
    return 0;
}

索引存储：

散列存储： 

          数据在存储的时候与关键码之间存在某种对应关系
          存的时候按照对应关系存
          取的时候按照对应关系取

4.操作

二丶算法

1.概念

  算法就是解决问题的思想方法，数据结构就是算法的基础

2.算法的设计

算法的设计：取决于数据的逻辑结构
算法的实现：依赖于数据的存储结构

3.算法的特点

有穷性：步骤是有限的
确定性：每一个步骤都有明确的含义，无二义性
可行性：在规定时间内可以完成
输入
输出

4.评价算法的好坏

如：f(n)=8 ->O(1)
       f(n) = 3n^5 + 2n^3 + 6*n^6 + 10->O（n^6）

6.空间复杂度