《计算机软件基础习题.ppt》由会员分享，可在线阅读，更多相关《计算机软件基础习题.ppt（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：查询、排序、插入、删除、修改等数据的运算：查询、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：1.回文是指正读和反读都相同的字符序列，如“abba”,“abdba”均是回文，“good”不是回文。编写一个算法判定给定的字符串是否为回文。算法描述1将字符串的一半字符压入栈中，再将其依次
2、弹出与字符串的另一半字符做比较，如果相同则为回文，不相同则不是。这里要考虑串长是奇偶两种情况。IntText(char*s)intlenth=strlen(s);/计算字符串长度Inti,j,k;If(lenth%2=0)/长度为偶数i=lenth/2;for(j=0;j=0;j-)/依次弹出与后半串比较k=pop(sj);if(k!=si+)break;if(j0)return1;/是回文return0;else/长度为奇数i=lenth/2;for(j=0;j=0;j-)k=pop(sj);/依次弹出if(k!=si+)/进行比较break;if(j0)return1;/是回文return
3、0;算法描述2先将整串字符压入栈，后将倒序方法用已知字符串的每个字符依次与出栈字符相比。inttext(char*s1)charstackmax,k;Inttop=-1;inti;for(i=0;i=0;i-)k=stacktop;top=top-1;if(s1i!=k)break;return0;elsereturn1;算法描述3将已知字符串倒序赋值给另外一个字符串，比较它们整个字符串是否相等。inttext(char*s1)char*s2=newcharstrlen(s1);inti;for(i=0;idata)；IF(p-rlink!=null)top=top+1;stop=p-rlin
4、k;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)/如果没有右子树或者右子树刚被访问过 pri
5、ntf(“%d”,p-data)；top=top-1;pre=p;p=null;Else p=p-rlink;VoidInorder(structnode*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-rli
6、nk /*扫描右子树扫描右子树*/while(p！=null)|(top！=-1)思考习题如何对二叉树线索化如何对二叉树线索化遍历二叉树是以一定规则将二叉树的节点排成一个线性序列，得到二叉树中节点的特定序列（前序，中序，后序）。实质上是对一个非线性结构进行线性化操作，使每个节点（除第一个和最后一个）在这些线性序列中仅有一个直接前驱和直接后继。思考习题问题问题但是二叉树作为链式的存储结构，只能找到节点的左右子树，不能得到节点在任一序列中的前趋后继，这种信息只有在遍历的动态过程中才能等到。思考习题解决方法解决方法增加两个标志域LTAG=0,Lchild域指向节点的左子树LTAG=1,Lchild域
7、指向节点的前驱RTAG=0,Rchild域指向节点的右子树RTAG=1,Rchild域指向节点的后继DATALTAGRTAGRchildLchild思考习题提示提示：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向后移动，保留前一次访问节点向后移动，保留前一次访问节点