开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 游戏 > 模拟服务器 > 查看源码
KScriptSet.cpp
资源名称：SwordOnline.rar　[点击查看]
上传用户：dzyhzl
上传日期：2019-04-29
资源大小：56270k
文件大小：25k
源码类别：

模拟服务器

开发平台：

C/C++

KScriptSet.cpp：源码内容
  1. //---------------------------------------------------------------------------
  2. // Sword3 Engine (c) 1999-2000 by Kingsoft
  3. // 
  4. // File: KScriptEngine.cpp
  5. // Date: 2001-9-11 10:33:35
  6. // Code: Romandou
  7. // Desc: 脚本集合控制基类
  8. //---------------------------------------------------------------------------
  9. #include "KWin32.h"
  10. #include "KDebug.h"
  11. #include "KScriptSet.h"
  12. //---------------------------------------------------------------------------
  13. // 函数: KScriptSet::KScriptSet
  14. // 功能:
  15. // 返回:
  16. //---------------------------------------------------------------------------
  17. KScriptSet::KScriptSet()
  18. {
  19. m_nKeyStyle = KEY_STRING;
  20. m_pRootList = NULL;
  21. m_pLestRecent = NULL;
  22. m_pMostRecent = NULL;
  23. }
  25. KScriptSet::KScriptSet(int Key_Style)
  26. {
  27. if (Key_Style == KEY_NUMBER || Key_Style == KEY_STRING)
  28. m_nKeyStyle = Key_Style;
  29. else 
  30. {
  31. m_nKeyStyle = KEY_STRING;
  32. printf("UnKnown ScriptSet KeyStyle:[%d]. So Set Key As Default KeyStyle KEY_STRING.n", Key_Style);
  33. }
  34. m_pRootList = NULL;
  35. m_pLestRecent = NULL;
  36. m_pMostRecent = NULL;
  37. }
  40. //---------------------------------------------------------------------------
  41. // 函数: KScriptSet::~KScriptSet
  42. // 功能:
  43. // 返回:
  44. //---------------------------------------------------------------------------
  45. KScriptSet::~KScriptSet()
  46. {
  47. TScript * pTScript = NULL;
  48. TScript * pDelTScript = NULL;
  49. pTScript = m_pLestRecent;
  51. while(pTScript)
  52. {
  53. pDelTScript =  pTScript;
  54. pTScript = pTScript->pMoreRecent;
  55. DeleteScript(pDelTScript->szKey);
  56. }
  58. }
  60. //---------------------------------------------------------------------------
  61. // 函数: KScriptSet::GetScript
  62. // 功能:
  63. // 参数: char * szKey     //该脚本的关键字
  64. // 参数: BOOL nNeedCreate //当未在链表中找到时是否需要直接新建
  65. // 参数: BOOL nNeedUpdateRecent //是否需要更新Recent表，重新排序
  66. // 返回: KScript * 
  67. //---------------------------------------------------------------------------
  68. KScript * KScriptSet::GetScript(char * szKey, BOOL nNeedCreate = 1, BOOL nNeedUpdateRecent = 1)
  69. {
  70. if (szKey == NULL ) return NULL;
  71. KScript * pScript = NULL;
  72. TScript * pTScript = NULL;
  73. TScript * pGetTScript = NULL;
  76. BOOL nResult = 0;
  78. if (m_nKeyStyle != KEY_STRING)
  79. {
  80. printf("The ScriptSet's Key Is Not a String. So Can Not Find A CorrRespond Script.n");
  81. return NULL;
  82. }
  86. if (m_pRootList == NULL) 
  87. {
  88. if ((pScript = CreateScript(szKey, GetInitStackSize(szKey))) == NULL) 
  89. return NULL;
  91. pGetTScript = new TScript;
  92. if (pGetTScript == NULL) 
  93. return NULL;
  95. // 初始化Recent表
  96. pGetTScript->pLessRecent = NULL;
  97. pGetTScript->pMoreRecent = NULL;
  98. pGetTScript->pLeftChild = NULL;
  99. pGetTScript->pRightChild = NULL;
  100. pGetTScript->pScript = pScript;
  101. pGetTScript->pParent = NULL;
  103. strcpy(pGetTScript->szKey, szKey);
  104. m_pRootList = pGetTScript;
  105. m_pLestRecent = pGetTScript;
  106. m_pMostRecent = pGetTScript;
  108. return pScript;
  110. }
  112. pTScript = BTSearch(m_pRootList, m_pRootList, szKey, &nResult);
  114. if (nResult == 0)
  115. {
  116. if (nNeedCreate)//当查找不到时，是否需要建立一个
  117. {
  118. KScript * pNewScript;
  119. if ( (pNewScript = CreateScript(szKey, GetInitStackSize(szKey)) ) == NULL )
  120. {
  121. printf("Can not Create Script Instance ,Mayby No Memorys.n");
  122. return NULL;
  124. }
  125. pGetTScript = BTInsert(pTScript, szKey);
  126. if (pGetTScript == NULL) return NULL;
  127. pGetTScript->pScript = pNewScript;
  128. }
  129. else 
  130. return NULL;//不需要建立的话，就返回空值
  133. }
  134. else
  135. pGetTScript = pTScript;
  137. if (nNeedUpdateRecent) //如果需要更新Recent表，则更新
  138. UpdateRecent(nResult, pGetTScript);
  140. return pGetTScript->pScript;
  141. }
  143. KScript * KScriptSet::GetScript(DWORD nKey, BOOL nNeedCreate = 1, BOOL nNeedUpdateRecent = 1)
  144. {
  146. KScript * pScript = NULL;
  147. TScript * pTScript = NULL;
  148. TScript * pGetTScript = NULL;
  150. BOOL nResult = 0;
  152. if (m_nKeyStyle != KEY_NUMBER)
  153. {
  154. printf("The ScriptSet's Key Is Not a Number. So Can Not Find A CorrRespond Script.n");
  155. return NULL;
  156. }
  158. if (m_pRootList == NULL) 
  159. {
  160. if ((pScript = CreateScript(nKey, GetInitStackSize(nKey))) == NULL) 
  161. return NULL;
  163. pGetTScript = new TScript;
  164. if (pGetTScript == NULL) 
  165. return NULL;
  167. // 初始化Recent表
  168. pGetTScript->pLessRecent = NULL;
  169. pGetTScript->pMoreRecent = NULL;
  170. pGetTScript->pLeftChild = NULL;
  171. pGetTScript->pRightChild = NULL;
  172. pGetTScript->pScript = pScript;
  173. pGetTScript->pParent = NULL;
  175. strcpy(pGetTScript->szKey, "");
  176. pGetTScript->nKey = nKey;
  178. m_pRootList = pGetTScript;
  179. m_pLestRecent = pGetTScript;
  180. m_pMostRecent = pGetTScript;
  182. return pScript;
  184. }
  186. pTScript = BTSearch(m_pRootList, m_pRootList, nKey, &nResult);
  188. if (nResult == 0)
  189. {
  190. if (nNeedCreate)//当查找不到时，是否需要建立一个
  191. {
  192. KScript * pNewScript;
  193. if ( (pNewScript = CreateScript(nKey, GetInitStackSize(nKey)) ) == NULL )
  194. {
  195. printf("Can not Create Script Instance ,Mayby No Memorys.n");
  196. return NULL;
  198. }
  199. pGetTScript = BTInsert(pTScript, nKey);
  200. if (pGetTScript == NULL) return NULL;
  201. pGetTScript->pScript = pNewScript;
  202. }
  203. else 
  204. return NULL;//不需要建立的话，就返回空值
  207. }
  208. else
  209. pGetTScript = pTScript;
  211. if (nNeedUpdateRecent) //如果需要更新Recent表，则更新
  212. UpdateRecent(nResult, pGetTScript);
  214. return pGetTScript->pScript;
  215. }
  217. //---------------------------------------------------------------------------
  218. // 函数: KScriptSet::UpdateRecent
  219. // 功能: 更新Recent表
  220. // 参数: BOOL bExistedScirpt  是否pGetTScript是个早已存在的脚本对象
  221. // 参数: TScript pGetTScript  最新使用的脚本对象
  222. // 返回: void 
  223. //---------------------------------------------------------------------------
  224. void KScriptSet::UpdateRecent(BOOL bExistedScript, TScript *pGetTScript)
  225. {
  226. BOOL nResult  = bExistedScript;
  228. if (nResult == 0)//新生成的脚本
  229. {
  230. if (m_pRootList == NULL)//第一个结点
  231. {
  232. pGetTScript->pLessRecent = NULL;
  233. pGetTScript->pMoreRecent = NULL;
  234. m_pMostRecent = pGetTScript;
  235. m_pLestRecent = pGetTScript;
  236. }
  237. else
  238. {
  239. pGetTScript->pLessRecent = m_pMostRecent;
  240. pGetTScript->pMoreRecent = NULL;
  241. m_pMostRecent->pMoreRecent = pGetTScript;
  243. }
  245. }
  246. else //使用的是已存在的脚本
  247. {
  249. if (pGetTScript->pLessRecent == NULL && pGetTScript->pMoreRecent == NULL)
  250. {
  251. return ;
  252. }
  254. if (pGetTScript == m_pLestRecent)//该结点在链表的末尾
  255. {
  256. if (pGetTScript->pMoreRecent)//是否不只一个结点
  257. {
  259. m_pLestRecent = pGetTScript->pMoreRecent;//设置m_pLestRecent
  260. m_pLestRecent->pLessRecent = NULL;
  263. pGetTScript->pMoreRecent = NULL;
  264. pGetTScript->pLessRecent = m_pMostRecent;
  265. m_pMostRecent->pMoreRecent = pGetTScript;
  267. }
  270. }
  271. else if (pGetTScript == m_pMostRecent)//在头结点上
  272. {
  274. }
  275. else
  276. {
  278. pGetTScript->pMoreRecent->pLessRecent = pGetTScript->pLessRecent;
  279. pGetTScript->pLessRecent->pMoreRecent = pGetTScript->pMoreRecent;
  281. pGetTScript->pLessRecent = m_pMostRecent;
  282. pGetTScript->pMoreRecent = NULL;
  283. m_pMostRecent->pMoreRecent = pGetTScript;
  285. }
  286. }
  289. m_pMostRecent = pGetTScript;//设置m_pMostRecent
  290. }
  295. //---------------------------------------------------------------------------
  296. // 函数: KScriptSet::SearchScript
  297. // 功能:
  298. // 参数: char * szKey
  299. // 返回: BOOL 
  300. //---------------------------------------------------------------------------
  301. TScript *  KScriptSet::SearchScript(char * szKey, BOOL * pnResult)
  302. {
  303. TScript * pTScript;
  304. if (m_pRootList == NULL)
  305. return NULL;
  307. pTScript = BTSearch(m_pRootList, m_pRootList, szKey, pnResult  );
  308. return pTScript;
  309. }
  311. //---------------------------------------------------------------------------
  312. // 函数:  KScriptSet::SearchScript
  313. // 功能:
  314. // 参数: DWORD nKey
  315. // 参数: BOOL * pnResult
  316. // 返回: TScript * 
  317. //---------------------------------------------------------------------------
  318. TScript *  KScriptSet::SearchScript(DWORD nKey, BOOL * pnResult)
  319. {
  320. TScript * pTScript;
  321. if (m_pRootList == NULL)
  322. return NULL;
  324. pTScript = BTSearch(m_pRootList, m_pRootList, nKey, pnResult);
  325. return pTScript;
  326. }
  329. //---------------------------------------------------------------------------
  330. // 函数:  KScriptSet::CreateScript
  331. // 功能: 新建脚本实例，为虚函数，由派生类负责建立
  332. // 参数: char * szKey
  333. // 参数: int StackSize
  334. // 返回: KScript * 
  335. //---------------------------------------------------------------------------
  336. KScript *  KScriptSet::CreateScript(char * szKey , int StackSize)
  337. {
  338. return NULL;
  339. }
  341. //---------------------------------------------------------------------------
  342. // 函数:  KScriptSet::CreateScript
  343. // 功能:
  344. // 参数: DWORD nKey
  345. // 参数: int StackSize
  346. // 返回: KScript * 
  347. //---------------------------------------------------------------------------
  348. KScript *  KScriptSet::CreateScript(DWORD nKey , int StackSize)
  349. {
  350. return NULL;
  351. }
  353. //---------------------------------------------------------------------------
  354. // 函数: KScriptSet::DeleteScript
  355. // 功能:
  356. // 参数: char * szKey
  357. // 返回: BOOL 
  358. //---------------------------------------------------------------------------
  359. BOOL KScriptSet::DeleteScript(char * szKey)
  360. {
  361. BOOL nResult = FALSE;//查找的结果
  362. TScript * pTScript;//查找返回的指针
  363. pTScript = SearchScript(szKey, &nResult);
  365. if (nResult && pTScript) //在链表中找到了该关键字
  366. {
  367. if (pTScript->pScript)
  368. pTScript->pScript->Exit();
  370. if (pTScript->pLessRecent == NULL  && pTScript->pMoreRecent == NULL)//全部为空，即只有一个结点
  371. {
  372. m_pMostRecent = NULL;
  373. m_pLestRecent = NULL;
  374. //if (m_pRootList == pTScript) 
  375. // m_pRootList = NULL;
  376. return DeleteScript(pTScript);
  377. }
  379. else if (!(pTScript->pLessRecent && pTScript->pMoreRecent))//有一个为空
  380. {
  382. if (pTScript->pLessRecent)
  383. {
  384. pTScript->pLessRecent->pMoreRecent = NULL;
  386. if (m_pMostRecent == pTScript)
  387. m_pMostRecent = pTScript->pLessRecent;
  390. }
  391. else
  392. {
  393. pTScript->pMoreRecent->pLessRecent = NULL;
  395. if (m_pLestRecent == pTScript)
  396. m_pLestRecent = pTScript->pMoreRecent;
  399. }
  402. return DeleteScript(pTScript);
  403. }
  404. else//全实
  405. {
  406. pTScript->pLessRecent->pMoreRecent = pTScript->pMoreRecent;
  407. pTScript->pMoreRecent->pLessRecent = pTScript->pLessRecent;
  409. if (m_pMostRecent == pTScript)
  410. m_pMostRecent = pTScript->pLessRecent;
  412. if (m_pLestRecent == pTScript)
  413. m_pLestRecent = pTScript->pMoreRecent;
  415. return DeleteScript(pTScript);
  416. }
  417. }
  418. else
  419. return FALSE;
  421. return TRUE;
  422. }
  424. //---------------------------------------------------------------------------
  425. // 函数: KScriptSet::DeleteScript
  426. // 功能:
  427. // 参数: DWORD nKey
  428. // 返回: BOOL 
  429. //---------------------------------------------------------------------------
  430. BOOL KScriptSet::DeleteScript(DWORD nKey)
  431. {
  432. BOOL nResult = FALSE;//查找的结果
  433. TScript * pTScript;//查找返回的指针
  434. pTScript = SearchScript(nKey, &nResult);
  436. if (nResult && pTScript) //在链表中找到了该关键字
  437. {
  438. if (pTScript->pScript)
  439. pTScript->pScript->Exit();
  441. if (pTScript->pLessRecent == NULL  && pTScript->pMoreRecent == NULL)//全部为空，即只有一个结点
  442. {
  443. m_pMostRecent = NULL;
  444. m_pLestRecent = NULL;
  446. return DeleteScript(pTScript);
  447. }
  449. else if (!(pTScript->pLessRecent && pTScript->pMoreRecent))//有一个为空
  450. {
  452. if (pTScript->pLessRecent)
  453. {
  454. pTScript->pLessRecent->pMoreRecent = NULL;
  456. if (m_pMostRecent == pTScript)
  457. m_pMostRecent = pTScript->pLessRecent;
  460. }
  461. else
  462. {
  463. pTScript->pMoreRecent->pLessRecent = NULL;
  465. if (m_pLestRecent == pTScript)
  466. m_pLestRecent = pTScript->pMoreRecent;
  469. }
  472. return DeleteScript(pTScript);
  473. }
  474. else//全实
  475. {
  476. pTScript->pLessRecent->pMoreRecent = pTScript->pMoreRecent;
  477. pTScript->pMoreRecent->pLessRecent = pTScript->pLessRecent;
  479. if (m_pMostRecent == pTScript)
  480. m_pMostRecent = pTScript->pLessRecent;
  482. if (m_pLestRecent == pTScript)
  483. m_pLestRecent = pTScript->pMoreRecent;
  485. return DeleteScript(pTScript);
  486. }
  487. }
  488. else
  489. return FALSE;
  491. return TRUE;
  492. }
  496. //---------------------------------------------------------------------------
  497. // 函数: KScriptSet::DeleteScript
  498. // 功能:
  499. // 参数: TScript * pTScript
  500. // 返回: BOOL 
  501. //---------------------------------------------------------------------------
  502. BOOL KScriptSet::DeleteScript(TScript * pTScript)
  503. {
  505. if (pTScript == NULL)
  506. return FALSE;
  507. TScript * pDelTScript;
  509. pDelTScript = BTDelete(pTScript, &m_pRootList, m_nKeyStyle);
  510. return TRUE;
  511. }
  512. //---------------------------------------------------------------------------
  513. // 函数: KScriptSet::InsertScript
  514. // 功能:
  515. // 参数: char * szKey
  516. // 参数: KScript * pScript
  517. // 返回: BOOL 
  518. //---------------------------------------------------------------------------
  519. TScript*  KScriptSet::InsertScript(char * szKey)
  520. {
  521. BOOL nResult = 0;
  522. TScript * pTScript = NULL;
  523. //TScript * pNewTScript = NULL;
  524. pTScript = BTSearch(m_pRootList, m_pRootList, szKey, &nResult);
  526. if (nResult == 1)
  527. {
  528. printf("Have Exist This Key In TScript Setsn");
  529. return NULL;
  531. }
  532. else if (nResult == 0)
  533. return BTInsert(pTScript, szKey);
  534. else return NULL;
  535. }
  537. //---------------------------------------------------------------------------
  538. // 函数: KScriptSet::InsertScript
  539. // 功能:
  540. // 参数: DWORD nKey
  541. // 返回: TScript*  
  542. //---------------------------------------------------------------------------
  543. TScript*  KScriptSet::InsertScript(DWORD nKey)
  544. {
  545. BOOL nResult = 0;
  546. TScript * pTScript = NULL;
  547. //TScript * pNewTScript = NULL;
  548. pTScript = BTSearch(m_pRootList, m_pRootList, nKey, &nResult);
  550. if (nResult == 1)
  551. {
  552. printf("Have Exist This Key In TScript Setsn");
  553. return NULL;
  555. }
  556. else if (nResult == 0)
  557. return BTInsert(pTScript, nKey);
  558. else return NULL;
  559. }
  563. //---------------------------------------------------------------------------
  564. // 函数: KScriptSet::GetScriptStackSize
  565. // 功能:
  566. // 参数: char * szKey
  567. // 返回: int 
  568. //---------------------------------------------------------------------------
  569. int KScriptSet::GetInitStackSize(char * szKey)
  570. {
  571. return 0;
  572. }
  574. //---------------------------------------------------------------------------
  575. // 函数: KScriptSet::GetScriptStackSize
  576. // 功能:
  577. // 参数: DWORD nKey
  578. // 返回: int 
  579. //---------------------------------------------------------------------------
  580. int KScriptSet::GetInitStackSize(DWORD nKey)
  581. {
  582. return 0;
  583. }
  586. //---------------------------------------------------------------------------
  587. // 函数: KScriptSet::ListScriptsKey
  588. // 功能:
  589. // 返回: void 
  590. //---------------------------------------------------------------------------
  591. DWORD  KScriptSet::ListScriptsKey()
  592. {
  593. return BTPreorder(m_pRootList);
  594. }
  596. DWORD  KScriptSet::ListRecent(int order = 0)
  597. {
  598. TScript * pTScript;
  599. DWORD nCount = 0;
  601. if (order == 0)
  602. {
  603. pTScript = m_pMostRecent;
  605. while(pTScript)
  606. {
  607. // printf("%sn",pTScript->szKey);
  608. pTScript = pTScript->pLessRecent;
  609. nCount ++;
  610. }
  611. return nCount;
  613. }
  614. else
  615. {
  616. pTScript = m_pLestRecent;
  618. while(pTScript)
  619. {
  620. // printf("%sn",pTScript->szKey);
  621. pTScript = pTScript->pMoreRecent;
  622. nCount ++;
  623. }
  624. return nCount;
  626. }
  628. }
  631. BOOL KScriptSet::Run(char * szKey)
  632. {
  633. return TRUE;
  634. }
  636. BOOL KScriptSet::Run(DWORD nKey)
  637. {
  638. return TRUE;
  639. }
  642. BOOL KScriptSet::RunFunction(char * szKey, char * szFuncName, char * szFormat, ...)
  643. {
  644. return TRUE;
  645. }
  648. BOOL KScriptSet::RunFunction(DWORD nKey, char * szFuncName, char * szFormat, ...)
  649. {
  650. return TRUE;
  651. }
  654. //---------------------------------------------------------------------------
  655. // 函数: BTSearch
  656. // 功能: 查找是否存在指定的关键字的二叉树结点，如果存在则*pResult = 1,返回相应指针；
  657. // 否则的话*pResult = 0,返回最接近的指针（该指针对今后插入有用）
  658. // 参数: TScript * pParentTScript 为递归调用传入父结点
  659. // 参数: TScript * pTScript
  660. // 参数: char * szKey 关键点
  661. // 参数: BOOL * pResult 指向是否找到该结点的标志
  662. // 返回: TScript * 
  663. //---------------------------------------------------------------------------
  664. TScript * BTSearch(TScript * pParentTScript, TScript * pTScript, char * szKey, BOOL * pResult)
  665. {
  667. if (pTScript == NULL || pParentTScript == NULL)
  668. {
  669. *pResult = FALSE;
  670. return pParentTScript;
  671. }
  673. int nResult = strcmp(szKey, pTScript->szKey);
  675. if (nResult == 0)
  676. {
  677. *pResult = TRUE;
  678. return pTScript;
  679. }
  680. else if (nResult > 0)
  681. return BTSearch(pTScript, pTScript->pRightChild, szKey, pResult);
  682. else
  683. return BTSearch(pTScript, pTScript->pLeftChild, szKey, pResult);
  685. }
  688. //---------------------------------------------------------------------------
  689. // 函数: BTSearch
  690. // 功能:
  691. // 参数: TScript * pParentTScript
  692. // 参数: TScript * pTScript
  693. // 参数: DWORD nKey
  694. // 参数: BOOL * pResult
  695. // 返回: TScript * 
  696. //---------------------------------------------------------------------------
  697. TScript * BTSearch(TScript * pParentTScript, TScript * pTScript, DWORD nKey, BOOL * pResult)
  698. {
  700. if (pTScript == NULL || pParentTScript == NULL)
  701. {
  702. *pResult = FALSE;
  703. return pParentTScript;
  704. }
  707. if (nKey == pTScript->nKey)
  708. {
  709. *pResult = TRUE;
  710. return pTScript;
  711. }
  712. else if (nKey > pTScript->nKey)
  713. return BTSearch(pTScript, pTScript->pRightChild, nKey, pResult);
  714. else
  715. return BTSearch(pTScript, pTScript->pLeftChild, nKey, pResult);
  717. }
  721. //---------------------------------------------------------------------------
  722. // 函数: BTInsert
  723. // 功能: 以pTScrpt为父，插入以szKey为关键点的结点
  724. // 参数: TScript *pTScript 
  725. // 参数: char * szKey
  726. // 返回: TScript * 返回插入的结点
  727. //---------------------------------------------------------------------------
  728. TScript * BTInsert(TScript *pTScript, char * szKey)
  729. {
  730. TScript * pNewTScript = new TScript;
  731. int nResult = 0;
  732. if (pNewTScript == NULL)
  733. return NULL;
  735. pNewTScript->pLeftChild = NULL;
  736. pNewTScript->pParent = NULL;
  737. pNewTScript->pRightChild = NULL;
  738. strcpy(pNewTScript->szKey,szKey);
  740. nResult = strcmp(szKey, pTScript->szKey);
  742. if (nResult == 0)
  743. return NULL;
  744. //根据大小确定左子还是右子
  745. if (nResult > 0)
  746. {
  747. pTScript->pRightChild = pNewTScript;
  748. pNewTScript->pParent = pTScript;
  749. }
  750. else 
  751. {
  752. pTScript->pLeftChild = pNewTScript;
  753. pNewTScript->pParent = pTScript;
  754. }
  755. return pNewTScript;
  757. }
  759. //---------------------------------------------------------------------------
  760. // 函数: BTInsert
  761. // 功能:
  762. // 参数: TScript *pTScript
  763. // 参数: DWORD nKey
  764. // 返回: TScript * 
  765. //---------------------------------------------------------------------------
  766. TScript * BTInsert(TScript *pTScript, DWORD nKey)
  767. {
  768. TScript * pNewTScript = new TScript;
  769. int nResult = 0;
  770. if (pNewTScript == NULL)
  771. return NULL;
  773. pNewTScript->pLeftChild = NULL;
  774. pNewTScript->pParent = NULL;
  775. pNewTScript->pRightChild = NULL;
  776. pNewTScript->nKey = nKey;
  779. if (nKey == pTScript->nKey)
  780. return NULL;
  781. //根据大小确定左子还是右子
  782. if (nKey > pTScript->nKey)
  783. {
  784. pTScript->pRightChild = pNewTScript;
  785. pNewTScript->pParent = pTScript;
  786. }
  787. else 
  788. {
  789. pTScript->pLeftChild = pNewTScript;
  790. pNewTScript->pParent = pTScript;
  791. }
  792. return pNewTScript;
  794. }
  799. //---------------------------------------------------------------------------
  800. // 函数:  BTDelete
  801. // 功能: 删除结点
  802. // 参数: TScript * pTScript
  803. // 参数: TScript ** ppRootTScript
  804. // 返回: TScript * 
  805. //---------------------------------------------------------------------------
  806. TScript *  BTDelete(TScript * pTScript, TScript ** ppRootTScript, int nKeyStyle)
  807. {
  808. TScript * pFindTScript;
  809. if (pTScript == NULL)
  810. return NULL;
  812. if (pTScript->pLeftChild == NULL && pTScript->pRightChild == NULL)//该结点没有左右子
  813. {
  814. if (*ppRootTScript == pTScript)
  815. {
  816. *ppRootTScript = NULL;
  817. }
  818. else
  819. {
  820. int nResult ;
  822. if (nKeyStyle == KEY_STRING)
  823. {
  824. nResult = strcmp(pTScript->szKey, pTScript->pParent->szKey);
  825. }
  826. else
  827. {
  828. if (pTScript->nKey < pTScript->pParent->nKey)
  829. nResult = -1;
  830. else
  831. nResult = 1;
  833. }
  836. if (nResult < 0)//小于
  837. pTScript->pParent->pLeftChild = NULL;
  838. else
  839. pTScript->pParent->pRightChild = NULL;
  841. }
  843. delete pTScript;
  844. return NULL;
  845. }
  847. else if (!(pTScript->pLeftChild && pTScript->pRightChild))//只有单子时
  848. {
  849. if (pTScript == *ppRootTScript)
  850. {
  851. if (pTScript->pLeftChild)
  852. {
  853. *ppRootTScript = pTScript->pLeftChild;
  854. pTScript->pLeftChild->pParent = NULL;
  855. }
  856. else
  857. {
  858. *ppRootTScript = pTScript->pRightChild;
  859. pTScript->pRightChild->pParent = NULL;
  860. }
  861. delete pTScript;
  862. return NULL;
  863. }
  866. int nResult ;
  868. if (nKeyStyle == KEY_STRING)
  869. {
  870. nResult = strcmp(pTScript->szKey, pTScript->pParent->szKey);
  871. }
  872. else
  873. {
  874. if (pTScript->nKey < pTScript->pParent->nKey)
  875. nResult = -1;
  876. else
  877. nResult = 1;
  879. }
  882. if (nResult < 0)//在父的左边
  883. {
  885. if (pTScript->pLeftChild)//只有左子
  886. {
  887. pTScript->pParent->pLeftChild = pTScript->pLeftChild;
  888. pTScript->pLeftChild->pParent = pTScript->pParent;
  889. }
  890. else
  891. {
  892. pTScript->pParent->pLeftChild = pTScript->pRightChild;
  893. pTScript->pRightChild->pParent = pTScript->pParent;
  894. }
  896. delete pTScript;
  898. }
  899. else 
  900. {
  901. if (pTScript->pLeftChild)//只有左子
  902. {
  903. pTScript->pParent->pRightChild = pTScript->pLeftChild;
  904. pTScript->pLeftChild->pParent = pTScript->pParent;
  905. }
  906. else
  907. {
  908. pTScript->pParent->pRightChild = pTScript->pRightChild;
  909. pTScript->pRightChild->pParent = pTScript->pParent;
  910. }
  911. delete pTScript;
  913. } 
  916. return NULL;
  918. }  
  919. else//有全子 
  920. {
  922. //if (strcmp(pTScript, pTScript->pParent) < 0)//在父的左面
  923. {
  925. pFindTScript = BTFindLess(pTScript->pLeftChild);
  927. if (pFindTScript)
  928. {
  930. //第一部分：处理该结点有左子时，对左子进行指向的改变
  931. //该结点仍有左子
  932. if (pFindTScript->pLeftChild)
  933. {
  934. //当发现所将要替代的结点正是它的左子时，将原来的关系不将变化；否则按正常思路改变
  935. if (pFindTScript != pTScript->pLeftChild)
  936. {
  937. pFindTScript->pParent->pRightChild = pFindTScript->pLeftChild;
  938. pFindTScript->pLeftChild->pParent = pFindTScript->pParent;
  939. }
  940. }
  941. else
  942. {
  943. if (pFindTScript != pTScript->pLeftChild)
  944. {
  945. pFindTScript->pParent->pRightChild = NULL;
  946. }
  948. }
  950. //第二部分：改变替换结点链结，实现与原结点相同。
  951. //处理当该替换的结点为删除结点的左子的特殊情况
  952. if (pFindTScript == pTScript->pLeftChild)
  953. {
  954. //其左子不用交代，保持原状
  955. pTScript->pRightChild->pParent = pFindTScript;
  957. //其左子不用交代,保持原状
  958. pFindTScript->pRightChild = pTScript->pRightChild;
  959. pFindTScript->pParent = pTScript->pParent;
  961. }
  962. else
  963. {
  965. pTScript->pLeftChild->pParent = pFindTScript;
  966. pTScript->pRightChild->pParent = pFindTScript;
  969. pFindTScript->pLeftChild = pTScript->pLeftChild ; 
  970. pFindTScript->pRightChild = pTScript->pRightChild;
  971. pFindTScript->pParent = pTScript->pParent;
  973. }
  976. //第三部分   删除结点之父结点链结
  978. if (*ppRootTScript == pTScript)
  979. {
  980. *ppRootTScript = pFindTScript;
  981. pFindTScript->pParent = NULL;
  982. }
  983. else 
  984. {
  986. int nResult ;
  988. if (nKeyStyle == KEY_STRING)
  989. {
  990. nResult = strcmp(pTScript->szKey, pTScript->pParent->szKey);
  991. }
  992. else
  993. {
  994. if (pTScript->nKey, pTScript->pParent->nKey)
  995. nResult = -1;
  996. else
  997. nResult = 1;
  999. }
  1002. if (nResult < 0)//在父的左面
  1003. {
  1004. pTScript->pParent->pLeftChild = pFindTScript;
  1005. }
  1006. else
  1007. {
  1008. pTScript->pParent->pRightChild = pFindTScript;
  1009. }
  1010. }
  1013. delete pTScript;
  1014. return pFindTScript;
  1015. }
  1016. else
  1017. return NULL;
  1018. }
  1020. }
  1023. }
  1025. //---------------------------------------------------------------------------
  1026. // 函数: BTFindLess
  1027. // 功能:
  1028. // 参数: TScript * pTScript
  1029. // 返回: TScript * 
  1030. //---------------------------------------------------------------------------
  1031. TScript * BTFindLess(TScript * pTScript)
  1032. {
  1033. if (pTScript == NULL)
  1034. return NULL;
  1036. if (pTScript->pRightChild == NULL )
  1037. return pTScript;
  1038. else
  1039. return BTFindLess(pTScript->pRightChild);
  1042. }
  1044. //---------------------------------------------------------------------------
  1045. // 函数: BTPreorder
  1046. // 功能:
  1047. // 参数: TScript * pTScript
  1048. // 返回: DWORD  
  1049. //---------------------------------------------------------------------------
  1050. DWORD  BTPreorder(TScript * pTScript)//中序遍历
  1051. {
  1052. static DWORD nCount = 0;
  1053. if (pTScript != NULL)
  1054. {
  1056. BTPreorder(pTScript->pLeftChild);
  1057. //printf("nKey [%d%sn", pTScript->szKey);
  1058. nCount ++;
  1059. BTPreorder(pTScript->pRightChild);
  1060. }
  1061. return nCount;
  1063. }