1*访问临界资源*.避免优先级倒置(Priority Inversion)：
1，计数信号量可记录信号量释放的次数, SEM_FOREVER)， 而不会死锁
semGive(sem_ID)。
其实质是.只能由已经获取了互斥信号量的任务去释放它
semGive(sem_ID).互斥信号量只能用于互斥操作semaphore options */ ，可以用来监视某一资源的使用状况。
2
/。其不同点在于*访问临界资源*。
4。
如果一个任务task1试图删除一个已经被保护起来的任务task2.互斥信号量不支持semFlush()操作可以实现安全删除
}
funA()
{
semTake(sem_ID；在执行semGive()操作之后，并抢占了task1的CPU。这种现象就是先级倒置就可以避免倒置.Deletion Safety(安全删除)
使用，直到task2解除保护（释放掉具有删除保护的互斥信号量）才能完成删除工作。
SEM_INVERSION_SAFE不能与SEM_Q_FIFO配对，此时的表现是低优先级task在高优先级的task2前执行
}
funB()
{
semTake(sem_ID，隐含执行taskUnsafe()操作，隐含执行了taskSafe()操作
}
五．Counting Semaphores（计数信号量）
计数信号量与二进制信号量都可以用于任务之间的同步与互斥：semId = semMCreate(SEM_Q_FIFO SEM_DELETE_SAFE)递归访问。
应用方向：
在上图中。
3，task1的优先级提升与task2一样：在Task对互斥信号量执行semTake()操作并成功占有该信号量之前。
使用semId = semMCreate(SEM_Q_PRIORITY SEM_INVERSION_SAFE)！
2，task2等待task1的资源
funB()
，于是处于Pend状态, SEM_FOREVER)，task1则将被阻塞起来。
此时.递归访问
[c-sharp] view plaincopy
InitFun()
{
sem_ID = semMCreate(…)，至到task2执行完成
)
区别.中断服务程序(ISR)不可以释放(semGive())互斥信号量。
3
A
AARH
arithmetical average roughness height
算术平均粗糙高度
AASHTO
American Association of State Highway and Transportation Officials
美国州际高速路及运输官方协会
ABS
acrylonitrile-butadiene-styrene
丙烯腈-丁二烯-苯乙烯共聚物
AC
alternating current
交流电
AC
asbestos cement
石棉水泥
ACF
advanced certified final
先期确认
ACI
American Concrete Institute
美国混凝土协会
ACP
asbestos cement pipe
石棉水泥管
AE
acoustic emission
声发射
AET
acoustic emission testing
声发射检测
AFC
approved for construction
批准用于施工
AFD
approved for design
批准用于设计
AFP
approved for planning
批准用于规划布置
AGA
American Gas Association
美国燃气协会
AI
aggressive index
侵蚀性指数
ANSI
American National Standards Institute
美国国家标准协会
API
American Petroleum Institute
美国石油学会
APWA
American Public Works Association
美国公共工程协会
ARV
air release valve
放气阀
ASA
American Shotcrete Association
美国喷射混凝土协会
ASCE
American Society of Civil Engineers
美国土木工程师协会
ASTM
American Society for Testing and Materials
美国材料试验协会
ASTT
Australian Society of Trenchless Tech
nology
澳大利亚非开挖协会
ATM
atmosphere
大气压
AWWA
American Water Works Association
美国自来水工业协会
B
BB
bolted bonnet
螺栓连接的阀盖
BC
bolted cap
螺栓连接的阀帽
BE
beveled end
坡口端
BEP
both ends plain
两端平
BET
both ends thread
两端带螺纹
BOD
biological oxygen demand
生物耗氧量
BOP
bottom of pipe
管底
BP
brick pipe
砖砌管道
BW
butt welded
对焊的
C
CAB
cellulose acetate butyrate
乙酸丁酸纤维素
CAD
computer aided design
计算机辅助设计
CATT
Center for advancement of Trenchless Technologies（CATT）at the University of Waterloo
滑铁卢大学非开挖研究中心
CBS
controlled boring system
控制钻孔系统
CCFRPM
centrifugally cast fiberglass reinforced polymer mortar pipe
离心浇注纤维玻璃增强聚酯水泥管
CCM
cut and cover method
明挖法
CCN
client change notice
用户变更通知
CCP
concrete cylinder pipe
钢筒混凝土管
CCTV
closed-circuit television
闭路电视
CF
certified final
最终确认
CFA
continuous flight auger
长螺旋
CFM
cubic feet per minute
立方英尺/分钟
CFP
close-fit pipe
紧密配合管
CI
cast iron
铸铁
CIGMAT
Center for Innovative Grouting Materials and Technology（CIGMAT）at University of Houston
休斯顿大学新型注浆材料及工艺中心
CIP
cast iron pipe
铸铁管
CIPP
cured-in-place pipe
原位修复管道法，翻转内衬管法
CL
centerline
中心线
CM
compaction method
挤土铺管法
CMOM
Capacity，Management，Operation，and Maintenance
能力，管理，经营，维护
COD
chemical oxygen demand
化学需氧量
COD
continue on drawing
接续图
CP
concrete pipe
混凝土管
CPE
chlorinated polyether
氯化聚醚
CPP
close profile pipe
波纹增强管
CPT
cone penetration test
圆锥静力触探试验
CPVC
chlorinated polyvinyl chloride
氯化聚氯乙烯
CRT
cathode ray tube
阴极射线管
CS
carbon steel
碳素钢
CSAMT
controlled source audio frequency magnetotellurics
可控源音频大地电磁测深法
CSO
combined sewer overflow
混合污水系统的溢流口
CSTT
China Society for Trenchless Technology
中国地质学会非开挖技术专业委员会
CT
computerized tomography
层析成像
CUGB
China University of Geosciences（Beijing）
中国地质大学（北京）
CUIRE
Center for Underground Infrastructure Research and Education at Michigan State University
密歇根州立大学地下设施研究与教育中心
CV
combination valve
组合阀
D
D&R
deformed and reformed
变形再复原法
DAI
data analysis and interpretation
数据分析与解释
DCCA
Directional Crossing Contractors Association
定向穿越承包商协会
DHD
downhole drilling
孔底钻进
DILONG
南京地龙非开挖工程技术有限公司
DIP
ductile iron pipe
球墨铸铁管
DIPRA
Ductile Iron Pipe Research Association
柔性铸铁管研究协会
DMT
dilatometer test
扁铲侧胀试验
DN
nominal diameter
标称直径，管径
DR
dimension ratio
尺度比
DRILLTO
深圳钻通工程机械有限公司
DSP
digital signal processing
数字信号处理
DSSS
design specification summary sheet
设计指标汇总表
DWF
dry weather flow
干旱流量
DWI
dry weather inflow
干旱流入量
DW/TXS
德威土行孙工程机械有限公司
E
ECH
epoxy chloropropane，epichlorohydrin
环氧氯丙烷
ECP
embedded cylinder pipe
埋置式钢筒管
EF
earliest finish
最早完成时间
EFW
electro-fusion welding，electric fusion welding
电熔焊
EL
elevation
标高
ELCB
earth leakage circuit breaker
漏电断路器
EMS
electromagnetic suspension
电磁悬浮
EMT
electromagnetic telemetry
电磁遥测
EPA
U.S.Environmental Protection Agency
美国环保局
EPB
earth pressure balance
土压平衡
EPBM
earth pressure balance machine
土压平衡掘进机
EPDM
ethylene-propylene-diene-monomer
乙烯-丙烯-二烯烃-单体
EPR
ethylene propylene rubber
乙丙橡胶
EPS
earth pressure shield
土压平衡盾构
ER
epoxy resin
环氧树脂
ERF
estimated repair factor
预评估维修比
ERL
estimated remaining life
估计残余寿命
ERW
electric resistance welding
电阻焊
ES
earliest start
最早开始时间
ESP
effective stress path
有效应力路径
ET
eddy current test
涡流探伤
EU
external upset
外加厚
F
F&E
fused and expanded
热熔挤扩法
F&F
fold and formed
折叠变形法
F.W.
field weld
现场焊
FDA
field data acquisition
现场数据采集
FELL
focused electrode leak location technology
聚焦电极泄漏定位技术
FEM
finite element method
有限元法
FF
flat face，full face
全平面，满平面
FGW
fusion gas welding
气熔焊
FIPP
formed-in-place pipe
现场成形管
FLCS
full line chemical stabilization
全线化学稳定法
FLG
flange
法兰
FLGD
flanged
法兰式的
FMF
female face
凹面
FOB
flat on bottom
底平
FOG
fibre optic gyroscope
光纤陀螺仪
FOT
flat on top
顶平
FRM
fiberglass reinforced mortar pipe
玻璃纤维增强水泥管
FRP
fiber glass reinforced pipe
玻璃纤维管
FRPP
fiberglass reinforced polyester pipe
玻璃纤维增强聚酯管
FTF
fitting to fitting
管件直接
G
GBM
guided boring method
导向钻进法
GBR
geotechnical baseline report
岩土基本报告
GIS
geographical information system
地理信息系统
GMAW
gas metal arc welding
金属极惰性气体保护电弧焊
GN
gunite
钢筋骨架喷射混凝土管道修复
GPR
ground penetrating radar
探地雷达
GPS
global positioning system
全球定位系统
GRC
glass reinforced concrete
玻璃增强混凝土
GRI
gas research institute
燃气研究所
GRP
glass reinforced plastic
玻璃增强塑料，玻璃钢
GWI
groundwater infiltration
地下水内渗
H
H.P.
high pressure
高压
HAB
horizontal auger boring
水平螺旋钻进
HAZ
heat affected zone
热影响区
HC
height of cover
覆土深度
HC
hose connection
软管接头
HDB
hydrostatic design basis
静水压设计指标
HDD
horizontal directional drilling
水平定向钻进
HDPE
high density polyethylene
高密度聚乙烯
HEB
horizontal earth boring
土层水平钻孔
HGL
hydraulic gradient line
水力坡度线
HH
handhole
手孔
HIC
hydrogen induced cracking
氢脆
HSE
health，safety and environment
健康，安全与环境
I
I/I，I&I
infiltration，inflow
渗入/流入，渗流量
I/I/E
infiltration/inflow/exfiltration
渗入/流入/外渗
ICG
internal condition grade
内部条件等级
ICRI
the International Concrete Repair Institute
国际混凝土修理协会
ID
inside diameter
内径
IEU
internal-external upset
内外加厚
IF
internal flush
内平式
IGSCC
intergranular stress corrosion cracking
晶界应力腐蚀裂纹
IJS
intermediate jacking station
中继间顶进站
ILR
in-line replacement
原位更换法
IS
inside screw
内螺纹
ISTT
International Society for Trenchless Technology
国际非开挖技术协会
IU
internal upset
内加厚
J
J/CS
joint/crack sealing
接头/裂纹密封
L
L.P.
low pressure
低压
L-CIPP
lateral-cured-in-place pipe
支管翻转内衬管
LCP
lined cylinder pipe
加衬钢筒管
LCP
lining with continuous pipe
连续管内衬法
LDPE
low density polyethylene
低密度聚乙烯
LED
light emitting diode
发光二极管
LEP
large end plain
大端为平的
LET
large end thread
大端带螺纹
LF
latest finish
最迟完成时间
LJF
lap joint flange
活套法兰
LOR
localized repair
局部修复（法）
LOR-CIPP
localized repair-cured-in-place pipe
局部修复-翻转内衬管法
LOR-GR
localized repair-grouting
局部修复-注浆法
LOR-IS
localized repair-internal seal
局部修复-内部密封法
LOR-RR
localized repair-robotic repair
局部修复-机器人法
L-PB
lateral-pipe bursting
支管爆管法
LPG
liquefied petroleum gas
液化石油气
LR
lateral renewal
支管更新（法）
LRI
light reflective index
光反射指数
LS
latest start
最晚开始时间
LSP
lining with segmental pipe
短管内插法，短管内衬法
LSWP
lining with spirally wound pipe
螺旋缠绕管内衬法
L-ThP
lateral-thermoformed pipe
支管热塑管修复法
L-UCL
lateral-underground coating and lining
支管地下喷涂内衬法
M
M.L.
match line
接续线
M.P.
medium pressure
中压
MAOP
maximum allowable operating pressure
最大允许工作压力
maxi-HDD
large-diameter HDD
大型水平定向钻机
MDPE
medium density polyethylene
中密度聚乙烯
MF
male face
凸面
MFL pig
magnetic flux leakage intelligent pig
漏磁智能清管器
MFP
mechanically folded pipe
机械折叠管
MH
manhole
人孔
MI
malleable iron
可锻铸铁
MIC
microbiologically induced corrosion
微生物腐蚀
midi-HDD
medium-diameter HDD
中型水平定向钻机
mini-HDD
small-diameter HDD
小型水平定向钻机
MOP
maximum operating pressure
最大工作压力
MPF
maximum pulling force
最大拖力
MPL
maximum pulling length
最大拖入长度
MSL
modified sliplining
改进内插法
MSL-PL
modified sliplining-panel lining
改进内衬法-模板内衬法
MSL-SW
modified sliplining-spiral wound
改进内衬法-缠绕法
MSTT
Midwest Society for Trenchless Technology
中西部非开挖技术协会
MT
magnetic particle test
磁粉探伤
MT
microtunneling
微型隧道
MTBM
microtunneling boring machine
微型隧道掘进机
MTM
microtunneling method
微型隧道法
MWD
measurement while drilling
随钻测量
N
NACE
National Association of Corrosion Engi
neers
美国腐蚀工程师国家协会
NASSCO
National Association of Sewer Service Company
美国国家下水道服务公司协会
NASTT
North American Society for Trenchless Technology
北美非开挖技术协会
NATM
New Austrian Tunnelling Method
新奥法
NBR
nitrile butadiene rubber
丁腈橡胶
NCP
noncylinder pipe
非圆管道
NDT
non-destructive testing
无损检测
NMR
nuclear magnetic resonance
核磁共振
NPT
American standard taper pipe thread
美国标准锥管螺纹
NRS
non-rising stem
非升杆式（暗杆）
NTP
notice to proceed
开工通知书
O
OC
open-cut
开挖
OD
outside diameter
外径
OET
one end thread
一端带螺纹
OPC
ordinary Portland cement
普通硅酸盐水泥
OPP
open profile pipe
加肋波纹管
OSHA
occupational safety and health act
职业安全与卫生条例
OSL
over-sea mean level
海平面标高
P
PA
polyamide
聚酰胺
PAP
piping arrangement plan
管道布置平面
PB
pipe bursting
爆管
PB
polybutylene
聚丁烯
PB-HY
pipe bursting-hydraulic
液压爆管法
PB-PE
pipe bursting-pneumatic
气动爆管法
PB-PS
pipe bursting-pipe splitting
裂管法
PC
polycarbonate
聚碳酸酯
PCCA
Power and Communication Contractors Association
能源与通讯承包商协会
PCCP
prestressed concrete cylinder pipe
预应力钢筒混凝土管
PCCPL
lined prestressed concrete cylinder pipe
内衬式预应力钢筒混凝土管
PCP
polymer concrete pipe
聚酯混凝土管
PCP
prestressed concrete pipe
预应力混凝土管
PE
pipe eating
吃管法
PE
plain end
平端
PE
polyethylene
聚乙烯
PFA
pulverized fuel ash
粉煤灰
PFD
process flow diagram
工艺流程图
PHPA
partially hydrolyzed polyacrylamide
部分水解聚丙烯酰胺
PID
piping and instrument flow diagram
管道及仪表流程图
PIRC
Pipeline Infrastructure Research Center（PIRC）at Pennsylvania State University
美国宾夕法尼亚州立大学管线设施研究
中心
PJ
pipe jacking
顶管
PL
panel lining
模板内衬
PMA
allowable maximum operating pressure
最大允许工作压力
PMMA
polymethyl methacrylate
聚甲基丙烯酸甲酯
PMT
pressuremeter test
旁压试验
PN
nominal pressure
公称压力
PO
polyolefin
聚烯烃
POS
point of support
支撑点
PP
polypropylene
聚丙烯
PP-B
PP-B
耐冲击共聚聚丙烯
PPI
Plastic Pipe Institute
塑料管学会
PP-R
PP-R
无规共聚聚丙烯
PR
pipe ramming
夯管，夯管法
PRC
Pipeline Research Council
管道研究委员会
PRC
polyester resin concrete
聚酯树脂混凝土
PR-HAB
pipe removal-horizontal auger boring
水平螺旋钻进管道更换法
PR-MT
pipe removal-microtunneling
微型隧道管道更换法
PR-PR
pipe removal-pipe reaming
扩孔式管道更换法
PR-PX
pipe removal-pipe extraction
抽管式管道更换法
PR-T
pipe removal-tunneling
隧道式管道更换法
PS
polystyrene
聚苯乙烯
PSR
point source repair
点状修复法
PT
liquid penetrant test
液体渗透检验
PTFE
polytetrafluoroethylene
聚四氟乙烯
PTMT
pilot tube microtunneling
先导管式微型隧道法
PVC
polyvinyl chloride
聚氯乙烯
PVC-M
modified PVC
改良PVC（改善了PVC的韧度）
PVC-O
molecularly oriented PVC
分子重排PVC
PVC-U
unplasticized polyvinyl chloride
硬聚氯乙烯
PVDF
polyvinylidene fluoride
聚偏二氟乙烯
PVDM
polyvinylidene difluoride membranes
聚偏二乙烯氟化膜
Q
QA/QC
quality assurance/quality control
质量保证/质量控制
R
RC
reinforced concrete
钢筋混凝土
RCP
reinforced concrete pipe
钢筋混凝土管
RDP
reduced diameter pipe
缩径管
regular
正规式
REG
RF
raised face
突面
RFEC/TC
remote field eddy current/transformer coupling
遥测励磁涡流/变压耦合
RII
rainfall induced infiltration
下雨渗流，雨致渗入
RJ
ring joint
环垫接头
ROP
rate of penetrate
机械钻速
RPM
reinforced plastic mortar
增强塑性砂浆
RPMP
reinforced plastic mortar pipe
增强塑性砂浆管
RQD
rock quality designation
岩石质量指标
RR
robotic repair
机器人修复法
RS
rising stem
升杆式（明杆）
RSC
ring stiffness constant
环向刚度常数
RT
radiographic test
射线检验
RTK
real time kinematic
实时动态（定位技术）
RTR
reinforced thermosetting resin
增强热固性树脂
RV
relief valve
溢流阀
S
SBR
styrene-butadiene rubber
苯乙烯-丁二烯橡胶
SCH.No.
schedule number
壁厚系列号
SCS
stress corrosion cracking
应力腐蚀裂纹，应力腐蚀开裂
SDR
standard dimension ratio
标准尺寸比
SEM
scanning electronic microscope
扫描电镜
SEP
small end plain
小端为平的
SESTT
Southeast Society for Trenchless Technology
东南部非开挖技术协会
SET
small end thread
小端带螺纹
SH
shotcrete
喷射混凝土
SL
shrinkage limit
缩限
SL
sliplining
内插法
SMAW
shielded metal arc welding
有保护的金属电弧焊
SMR
sewer manhole renewal
下水道检查井更新（法）
SOL
spray on lining
喷涂内衬
SP
steel pipe
钢管
SPG
structural performance grade
结构性能等级
SPT
standard penetration test
标准贯入试验
SR
spot repair
点状修复
SR
styrene-rubber
苯乙烯橡胶
SRF
smooth raised face
光滑突面
SRPC
sulfate resisting Portland cement
抗硫酸盐普通水泥
SRwWL
steel ribs with wooden lagging
钢架木板支护
SSB
sanitary sewer bypass
生活污水管支管
SSC
sulfide stress cracking
硫化应力裂纹，硫化应力开裂
SSES
sewer system evaluation survey
污水系统评价调查
SSET
sewer scanner and evaluation technology
下水道扫描与评价技术
SSO
sanitary sewer overflow
污水管道溢流
SSPC
Society for Protective Coating
涂层保护协会
SUE
subsurface utility engineering
地下公用设施工程
SV
safety valve
安全阀
SW
socket welded
承插焊的
SWP
spiral wound pipe
螺旋缠绕管
T
TBM
tunnel boring machine
隧道掘进机
TCM
trenchless construction method
非开挖铺管方法
threaded end
螺纹端
TEM
transient electromagnetic method
瞬变电磁法
total float
总时差
THD
threaded
螺纹的
thermoformed pipe
热塑管（法）
TLP
tunnel liner plate
隧道衬砌板
TOB
top of beam
梁顶面
TOP
top of pipe
管顶
TOS
top of support
架顶面
thermoplastic
热塑性塑料
TRB
Transportation Research Board
TE
TF
ThP
TP
运输研究董事会
TRM
trenchless renewal method
非开挖更新方法
TS
thermoset
热固性
TT
trenchless technology
非开挖技术
TTC
Trenchless Technology Center（TTC）at Louisiana Tech University
路易斯安娜大学非开挖技术中心
U
UCL
underground coating and lining
地下喷涂内衬法
UCL-CM
underground coating and lining-cement mortar
地下喷涂内衬法-水泥砂浆法
UCL-EL
underground coating and lining-epoxy lining
地下喷涂内衬法-环氧树脂喷涂法
UCL-GU
underground coating and lining-gunite
地下喷涂内衬法-压力喷浆法
UFD
utility flow diagram
公用工程流程图
UP
unsaturated polyester resin
非饱和聚酯树脂
UPVC
unplasticized polyvinyl chloride pipe
硬聚氯乙烯塑料管
UT
ultrasonic test
超声波探伤
UT
utility tunneling
公用隧道掘进法
UV
ultraviolet
紫外线
V
VCM
vendor coordinative meeting
厂商协调会
VCP
vitrified clay pipe
陶土管
VCT
vitrified clay tile
陶瓷
VCTP
vitrified clay tile pipe
陶瓷管
VOC
volatile organic compound
挥发性化合物
W
WB
welded bonnet
焊接阀盖
WEF
Water Environment Federation
水环境联合会
WNF
welding neck flange
对焊法兰
WOB
weight on bit
钻压
WQS
water quality standard
水质标准
WRC
Water Research Center
水研究中心
WST
weight sounding test
重力探测试验
WT
wall thickness
壁厚
WWTP
wastewater treatment plant
污水处理厂
通用有序平衡二叉树接口描述这套代码对用户屏蔽了复杂的二叉树的旋转操作，不区分用户的数据类型，任何数
据都可以用有序平衡二叉树来存放。我还对平衡二叉树进行了一点点扩展，在树结构里
面增加了保持线行递增（或递减）顺序的双向链表，方便使用者能够快速按序遍历所有
树节点。
这套代码需要用户直接参与的部分都用注册函数来实现，让使用者完全不需要了解
有序平衡二叉树的添加、删除或查找的过程，能够做到傻瓜式的使用。至于性能，我添
加过300万个树节点之后，树高只有22层，查找任意一个节点最多只需要22次匹配操作。
比HASH表快了很多。
这套代码还针对vxworks操作系统做了一点点扩展，其实就是判断一下当前操作系统
是否是vxworks，如果是的话就创建一个二进制信号量，如果不是就什么信号量也不创建。
目前此版本提供了如下通用接口：
1、数据结构定义
1.1、树的结构定义
typedef struct _AVL_TREE_HEADER
{
TREE_NODE *pTreeHeader
#ifdef ORDER_LIST_WANTED
TREE_NODE *pListHeader
TREE_NODE *pListTail
#endif
unsigned int count/*AVL树里的节点总数*/
int (*keyCompare)(TREE_NODE * , TREE_NODE *)
int (*free)(TREE_NODE *)
#if OS==3||OS==4 /*#if OS == VXWORKS || OS == VXWORKS_M*/
SEM_ID sem
#endif
} tAVLTree
1.2、树节点的结构定义
typedef struct _AVL_TREE_NODE
{
#ifdef ORDER_LIST_WANTED
struct _AVL_TREE_NODE *prev
struct _AVL_TREE_NODE *next
#endif
struct _AVL_TREE_NODE *tree_root
struct _AVL_TREE_NODE *left_child
struct _AVL_TREE_NODE *right_child
int bf /*平衡因子；当平衡因子的绝对值大于或等于2的时候就表示树不平衡(balance_factor)*/
}TREE_NODE
2、通用函数接口定义
2.1、avlTreeCreate
函数原型：tAVLTree *avlTreeCreate(int *keyCompareFunc,int *freeFunc)
参数描述：keyCompareFunc - 节点大小比较函数的指针，此函数需要用户自己提供，
比较函数的返回值应该是-1、0、1，(*keyCompareFunc)函数有两个参数，
分别是两个树节点，如果第二个参数所指向的树节点的值比第一个的小，
那么比较函数就应该返回-1，如果相等就是返回0，否则就是1。具体的比
较规则由用户根据所存储的数据里面的关键字来指定（当然，关键字有可
能有多个）。
freeFunc - (*freeFunc)只有一个参数，就是需要释放内存的节点的指
针，填写这个注册函数的目的是为了实现avlTreeDestroy和avlTreeFlush
这两个函数。
返回值 ：成功 - 返回指向一个树的指针
失败 - NULL
函数描述：创建一棵空的平衡二叉树，如果是vxworks操作系统的话还创建一个跟树
相关的一个二进制信号量。初始化所有指针为空指针。
2.2、avlTreeDestroy
函数原型：int avlTreeDestroy(tAVLTree *pTree)
参数描述：pTree - 指向一棵平衡二叉树的指针
返回值 ：成功 - 1
失败 - 0
函数描述：摧毁一颗平衡二叉树，释放所有树节点的内存，并且释放信号量（如果是
vxworks操作系统的话），释放pTree所指向的二叉树所占用的内存。
2.3、avlTreeFlush
函数原型：int avlTreeFlush(tAVLTree *pTree)
参数描述：pTree - 指向一棵平衡二叉树的指针
返回值 ：成功 - 1
失败 - 0
函数描述：清空一颗平衡二叉树，释放所有树节点的内存，但是并不删除平衡二叉树
2.4、avlTreeAdd
函数原型：int avlTreeAdd(tAVLTree *pTree , TREE_NODE *pInsertNode)
参数描述：pTree - 指向一棵平衡二叉树的指针
pInsertNode - 待插入的节点的指针
返回值 ：成功 - 1
失败 - 0
函数描述：往平衡二叉树中添加一个成员节点
2.5、avlTreeDel
函数原型：int avlTreeAdd(tAVLTree *pTree , TREE_NODE *pDelNode)
参数描述：pTree - 指向一棵平衡二叉树的指针
pDelNode - 待插入的节点的指针
返回值 ：成功 - 1
失败 - 0
函数描述：从平衡二叉树中删除一个树节点
2.6、avlTreeFind
函数原型：TREE_NODE *avlTreeFind(tAVLTree *pTree,TREE_NODE *pKeyNode)
参数描述：pTree - 指向一棵平衡二叉树的指针
pKeyNode - 待查找的节点的关键字
返回值 ：成功 - 查找到的节点指针
失败 - NULL
函数描述：查找一个节点
2.7、avlTreeCount
函数原型：int avlTreeCount(tAVLTree *pTree)
参数描述：pTree - 指向一棵平衡二叉树的指针
返回值 ：成功 - 当前平衡二叉树里的节点总数
失败 - 0
函数描述：获取当前树里面的所有成员节点总数
2.8、avlTreeFirst
函数原型：TREE_NODE *avlTreeFirst(tAVLTree *pTree)
参数描述：pTree - 指向一棵平衡二叉树的指针
返回值 ：成功 - 当前平衡二叉树里面的最小的成员节点的指针
失败 - NULL，只有树是空的时候才会返回NULL
函数描述：获取当前平衡二叉树里面第一个成员节点，即最小的成员节点
2.9、avlTreeLast
函数原型：TREE_NODE *avlTreeLast(tAVLTree *pTree)
参数描述：pTree - 指向一棵平衡二叉树的指针
返回值 ：成功 - 当前平衡二叉树里面的最大的成员节点的指针
失败 - NULL，只有树是空的时候才会返回NULL
函数描述：获取当前平衡二叉树里面最后一个成员节点，即最大的成员节点
2.10、avlTreeNext
函数原型：TREE_NODE *avlTreeNext(TREE_NODE *pNode)
参数描述：pTree - 指向一棵平衡二叉树的指针
返回值 ：成功 - 下一个成员节点的指针
失败 - NULL
函数描述：获取当前节点的下一个节点
2.11、avlTreePrev
函数原型：TREE_NODE *avlTreePrev(TREE_NODE *pNode)
参数描述：pTree - 指向一棵平衡二叉树的指针
返回值 ：成功 - 前一个成员节点的指针
失败 - NULL
函数描述：获取当前节点的前一个节点
2.12、AVL_TREE_LOCK
函数原型：void AVL_TREE_LOCK(tAVLTree *pTree,int timeout)
参数描述：pTree - 指向一棵平衡二叉树的指针
timeout - 等待时间
返回值 ：N/A
函数描述：此函数只有是vxworks系统才有效，目的是对树进行互斥操作，防止
多任务同时操作链表。
2.13、AVL_TREE_UNLOCK
函数原型：void AVL_TREE_UNLOCK(tAVLTree *pTree)
参数描述：pTree - 指向一棵平衡二叉树的指针
返回值 ：N/A
函数描述：此函数只有是vxworks系统才有效，目的是对树进行解除互斥操作
2.13、AVL_TREENODE_FREE
函数原型：void AVL_TREENODE_FREE(tAVLTree *pTree,TREE_NODE *pNode)
参数描述：pTree - 指向一棵平衡二叉树的指针
pNode - 需要释放的节点的指针
返回值 ：N/A
函数描述：此函数释放内存的过程采用的是注册的释放函数，释放不仅仅
只有free函数，对于一些复杂的结构设计，可能需要释放多个
不同的内存。
3、应用举例
> typedef struct _testStruct{
> TREE_NODE node /*树节点的结构一定要放在用户自定义结构的最前面，注意!*/
> int keyA /*关键字A*/
> int keyB /*关键字B*/
> int keyC /*关键字C，比方说此结构有3个关键字*/
> int userData[200]/*用户的实际数据区*/
> }tTestStruct
>
> int keyCompareFunc(TREE_NODE *p , TREE_NODE *p1)
> {
> tTestStruct *T1=NULL,*T2=NULL
>
> T1=(tTestStruct *)p
> T2=(tTestStruct *)p1
>
> if(T1->keyA <T2->keyA) return 1
> if(T1->keyA >T2->keyA) return -1
>
> if(T1->keyB <T2->keyB) return 1
> if(T1->keyB >T2->keyB) return -1
>
> if(T1->keyC <T2->keyC) return 1
> if(T1->keyC >T2->keyC) return -1
>
> return 0
> }
>
> int freeFunc(TREE_NODE *pNode)
> {
> free((void *)pNode)
> return 1
> }
>
> tAVLTree *pTree = NULL
> int main()
> {
> tTestStruct *pTest = NULL
> tTestStruct key
> int count = 0
> pTree = (tAVLTree *)avlTreeCreate
> (
> (void*)keyCompareFunc ,
> (void *)freeFunc
> )
> if(!pTree)
> {
> printf("\r\n 创建平衡二叉树失败")
> return 0
> }
>
> /*添加一个节点*/
> pTest = (tTestStruct *)malloc(sizeof(tTestStruct))
> if(!pTest)
> {
> printf("\r\n 创建树节点失败")
> return 0
> }
>
> pTest->keyA = 1
> pTest->keyB = 2
> pTest->keyC = 3
> if(!avlTreeAdd(pTree , (TREE_NODE *)pTest))
> {
> printf("\r\n 已经存在相同节点，添加失败!关键字完全匹配就表示节点完全相同")
> return 1
> }
>
> /*再添加一个节点*/
> pTest = (tTestStruct *)malloc(sizeof(tTestStruct))
> if(!pTest)
> {
> printf("\r\n 创建树节点又失败")
> return 0
> }
>
> pTest->keyA = 1
> pTest->keyB = 1
> pTest->keyC = 3 /*第二次添加的节点的关键字比较大家可以算一算*/
> if(!avlTreeAdd(pTree , (TREE_NODE *)pTest))
> {
> printf("\r\n 已经存在相同节点，添加失败!关键字完全匹配就表示节点完全相同")
> return 1
> }
>
> /*遍历有序平衡二叉树 -- 从小到大*/
> pTest = (tTestStruct *)avlTreeFirst(pTree)
> while(pTest)
> {
> /**************************
> *这里你想干嘛干嘛
> *处理pTest->userData?
> ***************************/
> pTest = (tTestStruct *)avlTreeNext(pTree)
> }
>
> /*遍历有序平衡二叉树 -- 从大到小*/
> pTest = (tTestStruct *)avlTreeLast(pTree)
> while(pTest)
> {
> /**************************
> *这里你想干嘛干嘛
> *处理pTest->userData?
> ***************************/
> pTest = (tTestStruct *)avlTreePrev(pTree)
> }
>
> /*查找某个节点*/
> key->keyA = 1
> key->keyB = 1
> key->keyC = 3
> pTest = (tTestStruct *)avlTreeFind(pTree , (TREE_NODE *)&key)
> if(pTest)
> printf("\r\n 这里应该可以查找到一条记录，就是第二个插入的节点")
>
> /*删除一个节点，我们就将上面查找到的节点删除*/
> if(!avlTreeCount(pTree , (TREE_NODE *)pTest))
> {
> printf("\r\n 如果删除失败，只能说明一个问题，树里面不存在这个节点")
> return 0
> }
>
> /*获取树的总的节点数*/
> count = avlTreeCount(pTree)
> printf("\r\n 我想现在count应该等于1，刚才我们删掉了一个节点")
>
> /*清空整棵树*/
> avlTreeFlush(pTree)
>
> /*删除整棵树，其实现在只有一颗裸树了，因为树节点都被flush掉了*/
> avlTreeDestroy(pTree)
> pTree = NULL
>
> return 1
> }
欢迎分享，转载请注明来源：夏雨云
微信扫一扫
支付宝扫一扫
评论列表（0条）