数据结构（嵌入式）

学习方法：听+多思考+多敲代码

核心：把一些复杂的数据进行分类，代码更加具有层次性。

学习意义：提高编程能力，程序可复用性，可维护性，可读性强。? ? ? ? ??

一：数据结构的引例

一：什么是数据结构

一：基本概念

数据：即信息的载体，能够输入到计算机并且能被计算机识别，存储和处理的符号总称。

数据元素：数据的基本单位，称之为记录，有若干基本项（字段，域，属性）的组成，有点类似于结构体。

产品编号	产品名称	规格	出厂日期
0001	CT	22	2000/08

? ? 计算机的处理对象已经不单纯是数值了

? ? 数据结构研究计算机数据间的关系包含逻辑结构和储存结构以及其操作（数据之间的运算）

? ? 语言只是一个工具，数据结构理论上可以凌驾于语言之上。数据结构出现的比语言早

? ? ? ? ? ? ? ? ? 姓名	项目1	项目2	项目3
? ?丁三	? A	F	G
? ?张三	? C	?D?
? ?王五	? C	?E	?H

三：染色问题：（可以用来解决比赛时间安排问题）

二?数据结构研究计算机数据间的关系

一：数据的逻辑结构

? ??? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? 线性结构 （一对一）? ? ? ? ? ? ? ? ? ? ? ? ??层次关系 （一对N）? ? ? ? ? 网状关系（N对N）

? 数据的逻辑结构表示数据运算之前的抽象关系，按照每一个元素可能具有的前趋数和后继数将逻辑结构分为“线性结构”和“非线性结构”两大类。

? ? 集合：数据元素除属于同一个集合以外没有任何关系。

? ? 线性结构：一个对一个，线性表，栈，队列

? ? 树形结构：一个对多个，如树

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

? ? 图状结构：多个对多个（网状结构）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

学习技巧：找一个数据的前趋和后继

二：数据的存储结构

? 存储结构：研究逻辑结构在计算机中的具体实现方法。

? 顺序存储：将数据结构中各元素按照其逻辑顺序存放于储存器中一片连续的存储空间中。如C语言中的数组。其储存方式如下表所示，容易推导后续元素的位置。

L0元素一

L0+m元素二

L0+2m元素三

L0+3m元素四

L0+4m元素五

? 链式存储：将数据结构中各元素分不到存储器的不不同点，用地址（或者链指针）的方式建立他们之间的联系。

? ?索引存储：在存储数据的同时，建立一个附加的索引表，即索引存储结构=数据文件+索引表

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

散列存储：根据数据元素的特殊字段（关键字key），计算出数据元素的存放地址，然后数据元素按地址存放。（ip地址）地址通过计算得到

模块化编程的好处：

1）结构清晰? 2）调试容易（调试小程序比大程序方便很多）3）软件复用性强（易重复操作）

二：逻辑结构——表，栈，队列

一：线性表

一：表的基础知识

定义：是包含若干数据元素的一个线性序列记为：L=(a0，.....an-1）

表示结构L可以用二元组表示L=(D,R）

其中D是数据元素的集合，R是关系集合

实例：设有一个顺序表L={1.2.3.4.5.6}他们的关系如下图

则使用一个二元组来描述L=(D,R)

? ? D={1.2.3.4.5.6}(n=6)? ?数据元素集合

? ? R={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>}? ?关系集合

线性表的特征：1.对于非空表，a0是表头无前驱；

? ? ? ? ? ? ? ? ? ? ? ? ? 2.an-1是表尾，无后继；

? ? ? ? ? ? ? ? ? ? ? ? ?3：对于其他的每一个元素ai有且仅有一个直接前驱和直接后继

补：?<2,3> 2是3的前驱，3是2的后继

线性表的存储：

? ? ? ? ? ?若将线性表L=(a0，.....an-1）中各元素一次存储于计算机一片连续的存储空间。设Loc（ai）为ai的地址，若已知每一个元素占d个单元，则可以推出每一个数据的位置。

L0元素一

L0+m元素二

L0+2m元素三

L0+3m元素四

L0+4m元素五

存储特点：1：逻辑上相邻的元素，存储位置也是相邻的

? ? ? ? ? ? ? ? ? 2 ：对数据元素存取很容易进行查找

? ? ? ? ? ? ? ? ??3：存储密度高

缺点：对于表的插入删除的时候比较耗时。

适用与需经常读取而不需要修改太多。

二：表的简单数组实现

在C语言中可以借助于一维数组来描述线性表的顺序存储结构

顺序储存的储存结构表示

#define N 100  //一共可以存储100个元素
typedef int date_t;  //对int起了一个别名
typedef struct 
{

  date_t date[N];  //表的存储空间
  int last；//表的下表

}sqlist,*sqlink;

顺序表的实现：

? ? 若将线性表L=(a0，.....an-1）基本运算

数据结构三个文件（模块化编程）：

sqlist.h 写数据结构的定义? ?sqlist.c 运算的视线? ?test.c 直接调用.h给的文件

? ? ??

好处:1）结构非常清晰

? ? ? ? ?2）软件复用性很好（可以不断重复调用）直接调用.h文件

? ? ? ? ?3）可以把.c文件进行加密保护? ? ? ?

1）建立一个空表

三：顺序表的功能实现

//sqlist.h
typedef int data_t;
#define N 128
struct sqlist_t
{
    data_t data[N];
    int  last;

};

typedef struct sqlist_t  sqlist;//简化书写 直接把qlist_t这个结构体只用一个就可以了
typedef struct sqlist_t  *sqlink;
//在未重定义之前 定义一个结构体是这样的  struct sqlist_t l；重定义了以后是这样的 sqlist i；

//简便写法，就是把全部的写一起
/*typedef struct sqlist_t
{
    data_t data[N];
    int last;
    
}sqlist,*sqlink;
*/

//简单线性表运算部分 
sqlink list_create();//创建一个线性表  反馈一个线性表的指针    

int list_clear(sqlink L);//清空线性表

int list_locate(sqlink L,data_t value);//定位寻找元素

int list_insert(sqlink L,data_t value,int pos);//替换这些元素

sqlist.c
#include<sqlist.h>
sqlink list_create()//创建一个线性表  反馈一个线性表的指针
{
    return NULL;
}
int list_clear(sqlink L)//清空线性表
{
     
      return 0;
}
int list_locate(sqlink L,data_t value)//定位寻找元素
{
       return 0;
}
int list_insert(sqlink L,data_t value,int pos)
{
      return 0;
}

? ? ? ? ? ??