计算机软件基础习题.ppt
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。,1.回文是指正读和反读都相同的字符序列，如“abba”,“abdba”均是回文，“good”不是回文。编写一个算法判定给定的字符串是否为回文。,算法描述1,将字符串的一半字符压入栈中，再将其依次弹出与字符串的另一半字符做比较，如果相同则为回文，不相同则不是。这里要考虑串长是奇偶两种情况。,Int Text(char*s)int lenth=strlen(s);/计算字符串长度Int i,j,k;If(lenth%2=0)/长度为偶数i=lenth/2;for(j=0;j=0;j-)/依次弹出与后半串比较k=pop(sj);if(k!=si+)break;if(j0)return 1;/是回文return 0;,else/长度为奇数i=lenth/2;for(j=0;j=0;j-)k=pop(sj);/依次弹出if(k!=si+)/进行比较break;if(j0)return 1;/是回文return 0;,算法描述2,先将整串字符压入栈，后将倒序方法用已知字符串的每个字符依次与出栈字符相比。,int text(char*s1)char stackmax,k;Int top=-1;int i;for(i=0;i=0;i-)k=stacktop;top=top-1;if(s1i!=k)break;return 0;else return 1;,算法描述3,将已知字符串倒序赋值给另外一个字符串，比较它们整个字符串是否相等。,int text(char*s1)char*s2=new charstrlen(s1);int i;for(i=0;istrlen(s1);i+)/将字符串倒序赋值s2strlen(s1)-1-i=s1i;if(strcmp(s1,s2)return 1;else return 0;delete s2;,2.参考课件P36前序遍历二叉树的算法和程序写出后序遍历二叉树的算法及程序(非递归),算法比较,前序遍历算法1.访问根节点2.遍历左子树3.遍历右子树4.返回,后序遍历算法1.遍历左子树2.遍历右子树3.访问根节点4.返回,Void Preorder(struct node*t)struct node*p；struct node*smax;int top;top=-1;p=t;do WHILE(p!=null)printf(“%d”,p-data)；IF(p-rlink!=null)top=top+1;stop=p-rlink;p=p-llink;IF(top！=-1)p=stop;top=top-1;while(p！=null)|(top！=-1),Void Postorder(struct node*t)struct node*p，*pre；/pre保存刚访问过节点 struct node*smax;int top=-1;p=t;pre=null;While(p|top-1)/沿着左子树走到最底端 while(p!=null)top=top+1;stop=p;p=p-llink;p=stop;If(p-rlink=null)|(p-rlink=pre)/如果没有右子树或者右子树刚被访问过 printf(“%d”,p-data)；top=top-1;pre=p;p=null;Else p=p-rlink;,Void Inorder(struct node*t)struct node*p；struct node*smax;int top;top=-1;p=t;do WHILE(p!=null)/*扫描左节点*/top=top+1;stop=p;p=p-llink;IF(top=0)p=stop;/*p所指的节点为无左子树或其左 子树已经遍历过*/top=top-1;printf(“%d”,p-data)；/*访问节点*/P=p-rlink/*扫描右子树*/while(p！=null)|(top！=-1),思考习题,如何对二叉树线索化 遍历二叉树是以一定规则将二叉树的节点排成一个线性序列，得到二叉树中节点的特定序列（前序，中序，后序）。实质上是对一个非线性结构进行线性化操作，使每个节点（除第一个和最后一个）在这些线性序列中仅有一个直接前驱和直接后继。,思考习题,问题 但是二叉树作为链式的存储结构，只能找到节点的左右子树，不能得到节点在任一序列中的前趋后继，这种信息只有在遍历的动态过程中才能等到。,思考习题,解决方法增加两个标志域LTAG=0,Lchild域指向节点的左子树LTAG=1,Lchild域指向节点的前驱RTAG=0,Rchild域指向节点的右子树RTAG=1,Rchild域指向节点的后继,DATA,LTAG,RTAG,Rchild,Lchild,思考习题,提示：if(p-llink!=NULL)p-ltag=0;elsep-ltag=1;p-llink=pre;/建立P节点的左线索，指向前趋节点Preif(pre!=NULL)if(pre-rlink!=NULL)pre-rtag=0;elsepre-rtag=1;pre-rlink=p;/前趋节点Pre建立右线索，指向节点Ppre=p;/pre跟上p,以便p向后移动，保留前一次访问节点,
