ds18b20二叉树搜索算法.docx
《ds18b20二叉树搜索算法.docx》由会员分享，可在线阅读，更多相关《ds18b20二叉树搜索算法.docx（11页珍藏版）》请在冰点文库上搜索。
ds18b20二叉树搜索算法
1单总线技术
单总线技术搜索ROM的过程是主设备获取单总线上从器件的注册码的过程，是一种简单的三步操作过程的重复，即先读一位，其次读该位的反码，然后再写一位，选中其中的一部分器件（详见参考文献[1]）。
重复执行这三步操作，可获得设备注册码其余各位。
根据每两次读的数据可作如下判断：
00：
总线上有器件，且它们的注册码在该位既有“1”，也有“0”；
01：
总线上器件的注册码在该位是“1”；
10：
总线上器件的注册码在该位是“0”；
11：
总线上没有器件。
2二叉树搜索算法
二叉树（binarytree）是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成，且左子树和右子树有严格的区分。
遍历一棵二叉树就是按某种次序系统地访问二叉树上的所有结点，并且每个结点只允许访问一次。
遍历运算的关键在于访问结点的次序，应保证二叉树上每个结点均被访问且仅被访问一次（详见参考文献[2]）。
3 二叉树搜索算法的应用
根据多个单总线器件注册码所构成的数据结构和二叉树的特点，可认为单总线上所有器件注册码构成了一个深度为64的二叉树（相关资料见参考文献[2]），在遍历二叉树的过程中可根据读取的两次数据判断结点是左子结点、右子结点还是叶子结点，即：
00：
表示既存在左子结点，也存在右子结点，该位有“0”，也有“1”；
01：
表示只存在左子结点，该位为“0”；
10：
表示只存在右子结点，该位为“1”。
11：
表示不存在子结点，也就说明没有从器件挂接在总线上。
在遍历二叉树时，记录所走的路径和搜索到的叶子结点数,可以得到从器件的注册码和从器件数量。
第一次搜索从器件的注册码时，如果左子结点和右子结点都存在，需要记录该分叉结点的深度，并沿左子树的方向向下搜索，当搜索深度达到64时，获得一个从器件的注册码，并取出该搜索路径最后的分叉结点的深度，然后主器件执行第二次搜索过程。
在该搜索过程中，如果结点的深度值小于最后一个分叉结点的深度，则发送上次搜索到的在最后一个分叉结点前的注册码的相应位；如果结点的深度值等于最后一个分叉结点的深度，则发送上次搜索到的在最后一个分叉结点处发送的数据的反码，并且删除该分叉结点的记录，如在后面的搜索中遇到分叉结点，同样需要记录分叉结点的深度。
这样，每搜索到一个深度为64的叶子结点，就会得到一个从器件的注册码，一直搜索到记录中没有分叉结点为止。
//============================================================
// 工程名称:
DS18B20
// 功能描述:
DS18B20底层for89s52
// 日期:
2009.7.4~6
//
//============================================================
#include
#include
#include
#defineucharunsignedchar
#defineuint unsignedint;
unsignedchar ID0,ID1,ID2,ID3,ID4,ID5,ID6,ID7;//传感器2
//ucharserial1[8];
ucharserial[3][8];
ucharread_bit[64];
//ucharflag=0;
externterm;
sbitDQ=P1^7; //ds18b20数据端口
//ucharterm;
//ROM操作指令////////////////////////////////////////////////////////////////
//读ROM
#define READ_ROM 0x33
//匹配ROM
#define MATCH_ROM 0x55
//跳过ROM
#define SKIP_ROM 0xcc
//搜索ROM
#define SEARCH_ROM 0xf0
//告警搜索
#define ALARM_SEARCH 0xec
//存储器操作指令
//写暂存存储器
#define WRITE_SCRATCHPAD 0x4e
//读暂存存储器
#define READ_SCRATCHPAD 0xbe
//复制暂存存储器
#define COPY_SCRATCHPAD 0x48
//温度变换
#define CONVERT_TEMPERATURE 0x44
//重新调出
#define RECALL_EPROM 0xb8
//读电源
#define READ_POWER_SUPPLY 0xb4
//////////////////////////////////////////////////////////////////////////////////////
/*************************************************************************************/
voiddelay（unsignedinti）//延时函数
{
while（i--）;
}
/***************************************************************************************/
//18b20初始化函数
voidInit_DS18B20（void）
{
unsignedcharx=0;
DQ=1; //DQ复位
delay（8）; //稍做延时
DQ=0; //单片机将DQ拉低
delay（80）;//精确延时大于480us
DQ=1; //拉高总线
delay（10）;
x=DQ; //稍做延时后如果x=0则初始化成功x=1则初始化失败
delay（5）;
}
//18b20初始化函数
voidInit_DS18B201（void）
{
unsignedcharx=0;
DQ=1; //DQ复位
delay（8）; //稍做延时
DQ=0; //单片机将DQ拉低
delay（80）;//精确延时大于480us
DQ=1; //拉高总线
delay（10）;
x=DQ; //稍做延时后如果x=0则初始化成功x=1则初始化失败
delay（5）;
}
//读一个字节
unsignedcharReadOneChar（void）
{ unsignedchari,j;
unsignedchartemp=0;
//EA=0;
for（i=0;i<8;i++）
{ DQ=0; _nop_（）;_nop_（）;
DQ=1; j=8;while（--j）;
j=DQ;
temp>>=1;
if（j）temp|=0x80;
j=25;while（--j）;/*waitforrestoftimeslot*/
}
//EA=1;
return（temp）;
}
//写一个字节
voidWriteOneChar（unsignedcharval）
{ unsignedchari,j;
unsignedchartemp;
for（i=0;i<8;i++） /*writesbyte,onebitatatime*/
{ temp=val&0x01;
DQ=0;
if（temp）DQ=1;
val>>=1;
j=25;while（--j）;
DQ=1;
}
// return
（1）;
}
//写一个字节
voidWriteOneChar1（unsignedcharval）
{ unsignedchari,j;
unsignedchartemp;
for（i=0;i<8;i++） /*writesbyte,onebitatatime*/
{ temp=val&0x01;
DQ=0;
if（temp）DQ=1;
val>>=1;
j=25;while（--j）;
DQ=1;
}
// return
（1）;
}
//写一位
voidWriteOneBit（ucharbitval）
{ unsignedchari;
DQ=0;
if（1==bitval&0x01）DQ=1;//returnDQhighifwrite1
i=25;while（--i）;
DQ=1;
}
//读一位
unsignedcharReadOneBit（）
{ unsignedchari,c;
DQ=0;
_nop_（）;
_nop_（）;
DQ=1;
i=8;
while（--i）;
c=（unsignedchar）DQ;
i=25;while（--i）;
return（c）;//returnvalueofDQline
}
/*
voidReadId（） //只有一个时读ROM信息
{
Init_DS18B20（）;
WriteOneChar（0x33）; //只有一个时读ROM信息
ID0=ReadOneChar（）;
ID1=ReadOneChar（）;
ID2=ReadOneChar（）;
ID3=ReadOneChar（）;
ID4=ReadOneChar（）;
ID5=ReadOneChar（）;
ID6=ReadOneChar（）;
ID7=ReadOneChar（）;
}
voidMatcnId（）
{
Init_DS18B20（）;
WriteOneChar（0x33）;
ID0=ReadOneChar（）;
ID1=ReadOneChar（）;
ID2=ReadOneChar（）;
ID3=ReadOneChar（）;
ID4=ReadOneChar（）;
ID5=ReadOneChar（）;
ID6=ReadOneChar（）;
ID7=ReadOneChar（）;
}*/
////////////////////////////
voidMatchRom（void）
{ unsignedchari;
Init_DS18B20（）;
WriteOneChar（MATCH_ROM）;
for（i=0;i<8;i++）
{
WriteOneChar（serial[2][i]）;
}
/* switch（term）
{
case1:
for（i=0;i<8;i++）
{
WriteOneChar（serial[1][i]）;
}
case2:
for（i=0;i<8;i++）
{
WriteOneChar（serial[2][i]）;
}
} */
}
///////////////////////////////////////////////////////////////////////
//读取温度，为9位
unsignedcharReadTemperature（void）
{
unsignedchara=0;
unsignedcharb=0;
unsignedchart=0;
//floattt=0;
Init_DS18B20（）;
WriteOneChar（0xCC）;//跳过读序号列号的操作
WriteOneChar（0x44）;//启动温度转换
delay（250）;
delay（250）;
delay（250）;
delay（250）;
Init_DS18B20（）;
MatchRom（）;
//WriteOneChar（0xCC）;//跳过读序号列号的操作
WriteOneChar（0xBE）;//读取温度寄存器等（共可读9个寄存器）前两个就是温度
a=ReadOneChar（）;
b=ReadOneChar（）;
b<<=4;
b+=（a&0xf0）>>4;
t=b;
//tt=t*0.0625;
//t=tt*10+0.5;//放大10倍输出并四舍五入
return（t）;
}
///////////////////////////////////////////////SearchRom///////////////////////////////////////
voidFindSerial（） //查ds18b20注册号
{
ucharn;
ucharj=0;//存读取的位
//ucharm=0;
uchark=0;
uchark1=1;//存64位8组中第几组
ucharrecord=64;
//ucharend=0;
ucharks=0;//已搜索器件注册码中一位
ucharmm=0;//8组中第几组的第几位
ucharnn=0;//复制serial,循环8次
ucharRSearch;
Init_DS18B201（）;//复位单总线
WriteOneChar1（SEARCH_ROM）;//发搜索命令
while
（1）
{
for（n=1;n<65;n++）//读深度为64的二叉树
{
k=（n-1）/8; //每8位放到数组中
j=ReadOneBit（）;
j=j<<1;
j=j|ReadOneBit（）;
serial[k1][k]=serial[k1][k]>>1;
if（j==0x02） //第一次为1，第二次为0
{
serial[k1][k]=serial[k1][k]|0x80;//存该位1
WriteOneBit
（1）;//发送1
read_bit[n]=0;
}
if（j==0x01） //第一次为0，第二次为1
{
serial[k1][k]=serial[k1][k]&0x7f;//存该位0
WriteOneBit（0）;//发送0
read_bit[n]=0;
}
if（j==0x00） //两次都为0，记录分叉点
// if（j==0x03）//forproteus
{
if（n{
ks=（serial[（k1-1）][k]>>（（n-1）%8））&0x01;/*发前一个已搜索器件注册码*/
WriteOneBit（ks）;
serial[k1][k]=serial[k1][k]|0x80;//存该位
if（ks==0）{serial[k1][k]=serial[k1][k]&0x7f;}
read_bit[n]=1;//记录
}
elseif（n>record）//深度是大于record所标记的
{
WriteOneBit（0x00）;
read_bit[n]=1;//记录
serial[k1][k]=serial[k1][k]&0x7f;
}
else
{
ks=（n-1）/8;mm=（n-1）%8;
nn=serial[（k1-1）][ks]>>mm;
if（（nn&0x01）==1）
{
serial[k1][ks]=serial[k1][ks]&0x7f;
WriteOneBit（0x00）;
}
if（（nn&0x01）==0）
{
serial[k1][ks]=serial[k1][ks]|0x80;
WriteOneBit（0x01）;
}
read_bit[n]=0;//清记录
}
}
}
//for（nn=0;nn<8;nn++）
// {serial1[nn]=serial[nn];}
if（n>64）
{
for（RSearch=64;RSearch>0;RSearch--）//从末尾搜索记录
{
if（read_bit[RSearch]!
=0）
{
record=RSearch;
n=1;
read_bit[RSearch]=0;
// flag=1;
break;
}
else
{record=0;}//清记录
}
}
if（record!
=0）//如有分叉点，重新搜索
{
Init_DS18B20（）;
// flag=1;
WriteOneChar（SEARCH_ROM）;//发搜索命令
k1+=1;
}
else
{break;}
}
}
升级会员 