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

大纲

数据结构、算法
数据结构：
           1.  线性表：序次表、链表（单向链表，单向循环链表，双向链表，双向循环链表）、栈（序次栈，链式栈）、队列（循环队列，链式队列）
           2.  树：二叉树、遍历、创建
算法：
           查询方法、排序方式

为什么要学数据结构？

     1.C语言是学习怎样写步伐，数据结构是学习怎样简便高效的写步伐
      2.假如遇到一个现实标题，必要写代码实现相应功能，必要办理两个标题：
          （1）.怎样表达数据间的逻辑关系以及怎么存储到盘算机当中？
                         数据结构：数据的逻辑结构以及存储操纵
                         数据：不再是单纯的数字，而是类似于一个聚集的概念
                         结构：数据之间的关系
         （2）.接纳什么方法去办理？
                               接纳算法去办理
数据结构+算法=步伐
一丶数据结构

1.概念

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

         数据：不再是单一的数值，而是类似于聚集的概念

         数据元素：是数据的根本单元，由多少个数据项构成
         数据项：是数据的最小单元，形貌数据元素信息
         数据元素又叫节点

3.结构

3.1逻辑结构

数据元素并不是独立存在的，他们之间存在着某种关系（接洽或结构）。
元素和元素之间的关系：
线性关系：
     线性关系 ---》 线性结构 ---》一对一 ----》线性表：序次表、链表、栈、队列
条理关系：
     条理关系 ---》 树形结构 ---》一对多 --- 》 树：二叉树
网状结构：
     网状关系 ---》 图状结构 ---》 多对多 ---》图

3.2存储结构

数据的逻辑结构在盘算机中的具体表现（数据的运算）
序次存储：
特点：内尺一连，随机存取，每个元素占用较少
实现：数组
链式存储：
特点：内存不一连，通过指针实现
链表实现：通过界说结构体，内里是数据域和指针域

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

复制代码

索引存储：
在存储数据的同时，创建一个附加的索引表。

也就是索引存储结构 = 索引表 + 存数据的文件
可以进步查找速率，特点检索速率快，但是占用内存多，删除数据文件要实时更改索引表。

散列存储： 
          数据在存储的时间与关键码之间存在某种对应关系
          存的时间按照对应关系存
          取的时间按照对应关系取
4.操纵

          增、删、改、查二丶算法

1.概念

  算法就是办理标题的头脑方法，数据结构就是算法的根本
2.算法的筹划

算法的筹划：取决于数据的逻辑结构
算法的实现：依靠于数据的存储结构
3.算法的特点

有穷性：步调是有限的
确定性：每一个步调都有明白的寄义，无二义性
可行性：在规定时间内可以完成
输入
输出
4.评价算法的优劣

        准确性 ：包管算法可以准确实现功能

        易读性 ：容易被解读
        坚固性 : 容错处置惩罚
        高效性 ：实行服从，算法实行快慢容易受到盘算机性能的影响，不可以作为评判算法高效性的尺度，这通过可实行语句重复实行次数来衡量算法是否高效 。(时间复杂度)
        低存储性 ： 占用空间少

5.时间复杂度

            算法的可重复实行语句实行的次数,通常时间复杂度用一个标题规模函数来表达

            T(n) = O(f(n))
            T(n) //标题规模的时间函数
            n //标题规模，输入量的巨细
            O //时间数量级
            f(n) //算法的可实行语句重复实行的次数 用标题规模n的某个函数f(n)来表达

盘算大O的方法

            (1)根据标题规模n写出表达式 f(n)
            (2)  只保存最高项，别的项舍去
            (3)  假如最高项系数不为1，除以最高项系数
            (4)  假如有常数项，将其置为1 //当f(n)的表达式中只有常数项的时间，故意义 f(n) = 8

如：f(n)=8 ->O(1)
       f(n) = 3n^5 + 2n^3 + 6*n^6 + 10->O（n^6）
6.空间复杂度

算法占用的空间巨细。一样平常将算法的辅助空间作为衡量空间复杂度的尺度。

算法占用的存储空间包罗：
   1.输入输出数据所占空间
   2.算法本身所占空间
   3.额外必要的辅助空间