嵌入式系统软件设计中的数据结构

第一章

散列存储:依据数据元素的关键字直接计算出该元素的存储位置，基本思想在于：以数据元素的关键字K为自变量，通过一个确定的函数关系（散列函数），计算出相应的函数值，把这个值作为数据元素的存储地址，将数据元素存入该地址所指的存储位置上。

算法的特征：有穷性、确定性、可行性、有输入、有输出;
算法的高效率体现在对于算法的执行时间要尽可能的短，对于存储空间的占用要尽可能的少，即做到既省时又省空间。

算法的时间复杂度， \(T(n) = O(f(n))\)
一般来说，f(n)是和算法执行次数增长率相同（理解为算法执行次数表达式中最快上升的函数项）的关于n的函数，特例，交换两变量值有三个语句：

temp = i; i = j; j = temp;

执行时间是一个与n无关的常数，其算法的时间复杂度是常数阶，则 \(T（n） = O(1)\)
算法的空间复杂度
算法的存储空间指的是算法执行过程中所需要的最大存储空间。算法执行过程中需要的存储空间包括三个部分：输入数据所占空间；程序本身所占空间（不同算法之间不会有很大差别）；辅助变量所占空间和额外占用空间（重点分析）；定义算法的空间复杂度为：\(S（n）= O(g(n))\) ，随着问题的规模增大，算法运行所需要的空间增长率和\(g(n)\)的增长率相同。

嵌入式系统比较流行的定义是，以应用为中心，以计算机技术为基础，软件硬件可裁剪，适应应用系统对功能、可靠性、成本、体积、功耗严格要求的专用计算机系统。高档嵌入式系统CPU为32位以上，信息处理量比较大，但是价格昂贵，低档嵌入式系统为16位以下（主要是8位），在生产中用的比较多，适用于

• 数据规模较小、采用简单数据结构（线性表）
• 采用RAM资源占用较少的算法（可能导致算法效率下降，能实现功能）
• 采用程序代码简单的算法，可以减小ROM开销

第二章 线性表 — 最简单、最常用的一种线性结构

线性表是\(n\)个数据元素的有限序列，记为(\(a_{1},a_{2},…,a_{n}\))，其基本运算包括：置空表、求长度、取节点、定位、插入、删除。

顺序表
顺序表是将线性表中的节点按照逻辑顺序（逻辑顺序和物理顺序一致）依次存放在一组地址连续的存储单元中，一般情况下，线性表中的所有节点的类型是相同的，即每个节点占用的空间是相同的。在编程之前，可事先分配一个足够的连续内存空间\(max * L\)，其中，\(L\)是节点的大小，\(max\)是最大的节点数；例，用一维数组及结构体来定义顺序表

#define max 1024

typedef int datatype; //定义节点元素的数据类型
typedef struct
{
    datatype data[max]; //第一个节点是data[0]
    int last; //最后一个节点的下标
}sequencelist;

顺序表的插入操作：(在第i个节点处插入x)

int insert(sequencelist *L, datatype x, int i)
{
    int j; 
    if( L-> last >= max)
    {
        return(0);  //空间溢出
    }
    else if( i < 1 || i > L -> last + 2 ) // 判断i是不是合法 
    {
        return(0); //插入位置非法
    }
    else 
    {
        for (j = L->last; j >= i - 1; j++ ) // 第i个数在表中的下标为i-1
        {
            L -> data[j+1] = L -> data[j];
        }
        L -> data[i-1] = x;
        L -> last = L -> last + 1;
    }
    return(1); //插入成功，返回1
}

顺序表的删除操作：（删除第i个节点）

int delate(sequencelist *L, int i)
{
    int j;
    if(L->last > max)
    {
        return(0); // 空间溢出
    }
    else if (i < 0 || i > L-> last + 1)
    {
        return(0);//非法删除
    }
    else
    {
        for( j = i; j <= last; j++ )
        {
            L->data[j-1] = L->data[j];
        }
        L->last = L->last - 1;
    }
    return(1);
}

顺序表的优点在于能够方便地存取表中的任意一个点，但是，除了其运算不方便，运算效率较低之外，由于其所占空间必须是连续空间，节点数并不固定，预先分配空间的时候难以确定合适的内存，容易造成内存不足或者内存浪费。