编程之美——bczm_03.doc

1、第 3 章结 构 之 法字符串及链表的探索代码清单 3-1char src = ”AABBCD”;char des = ”CDAA”;int len = strlen(src);for(int i = 0; i = 0)if(answerk pAEnd)if(pBBegin pBEnd)return 0; elsereturn pBEnd pBBegin + 1;if(pBBegin pBEnd)if(pABegin pAEnd)return 0;elsereturn pAEnd pABegin + 1;if(strApABegin = strBpBBegin)return Calculate

2、StringDistance(strA, pABegin + 1, pAEnd,strB, pBBegin + 1, pBEnd);elseint t1 = CalculateStringDistance(strA, pABegin, pAEnd, strB, pBBegin + 1, pBEnd);int t2 = CalculateStringDistance(strA, pABegin + 1, pAEnd, strB,pBBegin, pBEnd);int t3 = CalculateStringDistance(strA, pABegin + 1, pAEnd,strB,pBBegi

3、n + 1, pBEnd);return minValue(t1,t2,t3) + 1;代码清单 3-7void DeleteRandomNode(node* pCurrent)Assert(pCurrent != NULL);node* pNext = pCurrent - next;if(pNext != NULL)pCurrent - next = pNext - next;pCurrent - data = pNext - data;delete pNext;代码清单 3-8int nTargetLen = N + 1; / 设置目标长度为总长度+1int pBegin = 0; /

4、初始指针int pEnd = 0; / 结束指针int nLen = N; / 目标数组的长度为 Nint nAbstractBegin = 0; / 目标摘要的起始地址int nAbstractEnd = 0; / 目标摘要的结束地址第 3 章 结构之法 字符串及链 表的探索编程之美 微软技术面试心得216while(true)/ 假设包含所有的关 键词，并且后面的指针没有越界，往后移动指针while(!isAllExisted() 代码清单 3-9class stackpublic:stack()stackTop = -1;maxStackItemIndex = -1;void Push(

5、Type x)stackTop+;if(stackTop = MAXN); /超出 栈的最大存储量elsestackItemstackTop = x;if(x Max()link2NextMaxItemstackTop = maxStackItemIndex;maxStackItemIndex = stackTop;elselink2NextMaxItemstackTop = -1;Type Pop()编程之美 微软技术面试心得217Type ret;if(stackTop = 0)return stackItemmaxStackItemIndex;elsereturn INF;private

6、:Type stackItemMAXN;int stackTop;int link2NextMaxItemMAXN;int maxStackItemIndex; 代码清单 3-10class Queuepublic:Type MaxValue(Type x, Type y)if(x y)return x;elsereturn y;Type Queue:Max()return MaxValue(stackA.Max(), stackB.Max();Insert2Queue(v)第 3 章 结构之法 字符串及链 表的探索编程之美 微软技术面试心得218stackB.push(v);Type DeQ

7、ueue()if(stackA.empty()while(!stackB.empty()stackA.push(stackB.pop()return stackA.pop();private:stack stackA;stack stackB;代码清单 3-11/ 数据结构定义struct NODENODE* pLeft; / 左子树NODE* pRight; / 右子树int nMaxLeft; / 左子树中的最长距离int nMaxRight; / 右子树中的最长距离char chValue; / 该节点的值;int nMaxLen = 0;/ 寻找树中最长 的两段距离void FindM

8、axLen(NODE* pRoot)/ 遍历到叶子 节点，返回if(pRoot = NULL)return;/ 如果左子 树为空，那么该节点的左边最长距离为 0if(pRoot - pLeft = NULL)pRoot - nMaxLeft = 0; / 如果右子 树为空，那么该节点的右边最长距离为 0if(pRoot - pRight = NULL)pRoot - nMaxRight = 0;编程之美 微软技术面试心得219/ 如果左子 树不为空，递归寻找左子树最长距离if(pRoot - pLeft != NULL)FindMaxLen(pRoot - pLeft);/ 如果右子 树不为空

9、，递归寻找右子树最长距离if(pRoot - pRight != NULL)FindMaxLen(pRoot - pRight);/ 计算左子 树最长节点距离if(pRoot - pLeft != NULL)int nTempMax = 0;if(pRoot - pLeft - nMaxLeft pRoot - pLeft - nMaxRight)nTempMax = pRoot - pLeft - nMaxLeft;elsenTempMax = pRoot - pLeft - nMaxRight;pRoot - nMaxLeft = nTempMax + 1;/ 计算右子 树最长节点距离if

10、(pRoot - pRight != NULL)int nTempMax = 0;if(pRoot - pRight - nMaxLeft pRoot - pRight - nMaxRight)nTempMax = pRoot - pRight - nMaxLeft;elsenTempMax = pRoot - pRight - nMaxRight;pRoot - nMaxRight = nTempMax + 1;/ 更新最长 距离if(pRoot - nMaxLeft + pRoot - nMaxRight nMaxLen)nMaxLen = pRoot - nMaxLeft + pRoot

11、 - nMaxRight;代码清单 3-12/ ReBuild.cpp : 根据前序及中序结果，重建树的根节点/第 3 章 结构之法 字符串及链 表的探索编程之美 微软技术面试心得220/ 定义树的长度。为了后序调用实现的简单，我们直接用宏定义了树节点的总数#define TREELEN 6/ 树节点struct NODENODE* pLeft; / 左节点NODE* pRight; / 右节点char chValue; / 节点值;void ReBuild(char* pPreOrder, / 前序遍历结果char* pInOrder, / 中序遍历结果int nTreeLen, / 树长度

12、NODE* pRoot) / 根节点/ 检查边界条件 if(pPreOrder = NULL | pInOrder = NULL)return;/ 获得前序遍 历的第一个节点NODE* pTemp = new NODE;pTemp - chValue = *pPreOrder;pTemp - pLeft = NULL;pTemp - pRight = NULL;/ 如果节点 为空，把当前节点复制到根节点if(*pRoot = NULL)*pRoot = pTemp;/ 如果当前 树长度为 1，那么已经是最后一个节点if(nTreeLen = 1)return;/ 寻找子树长 度 char* p

13、OrgInOrder = pInOrder;char* pLeftEnd = pInOrder; int nTempLen = 0;/ 找到左子 树的结尾while(*pPreOrder != *pLeftEnd)if(pPreOrder = NULL | pLeftEnd = NULL)return;编程之美 微软技术面试心得221nTempLen+;/ 记录临时长 度，以免溢出if(nTempLen nTreeLen)break;pLeftEnd+;/ 寻找左子 树长度int nLeftLen = 0;nLeftLen = (int)(pLeftEnd - pOrgInOrder);/ 寻

14、找右子 树长度int nRightLen = 0;nRightLen = nTreeLen nLeftLen - 1;/ 重建左子 树if(nLeftLen 0)ReBuild(pPreOrder + 1, pInOrder, nLeftLen, / 重建右子 树if(nRightLen 0)ReBuild(pPreOrder + nLeftLen + 1, pInOrder + nLeftLen + 1, nRightLen, / 示例的调用代 码int main(int argc, char* argv)char szPreOrderTREELEN=a, b, d, c, e, f;cha

15、r szInOrderTREELEN=d, b, a, e, c, f;NODE* pRoot = NULL;ReBuild(szPreOrder, szInOrder, TREELEN, 代码清单 3-13/ 输出以 root为根节点中的第 level层中的所有节点（从左到右）, 成功返回 1，/ 失败则返回 0/ param/ root 为二叉树的根节点 / level为层次数，其中根 节点为第 0层第 3 章 结构之法 字符串及链 表的探索编程之美 微软技术面试心得222int PrintNodeAtLevel(Node* root, int level)if(!root | level data lChild, level - 1) + PrintNodeAtLevel(node - rChild, level - 1);代码清单 3-14/ 层次遍历二叉 树/ param/ root，二叉树的根节点/ depth，树的深度void PrintNodeByLevel(Node* root, int depth)for(int level = 0; level vec; / 这里我们使用 STL 中的 vector来代替数组，可利用