欢迎来到天天文库
浏览记录
ID:57034532
大小:44.50 KB
页数:16页
时间:2020-07-27
《计算机软件基础习题课课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
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<=i-1;j++)//将前半串字符依次压栈push(s[j]);for(j=i-1;j>=0;j--)//依次弹出与后半串比较{k=pop(s[j]);if(k!=s[i++])break;}if(j<0)return1;//是回文return0;}else//长度为奇数{i=lenth/2;for(j=0;j
3、<=i-1;j++)//将前半串入栈push(s[j]);i++;//越过串中间字符for(j=i-1;j>=0;j--){k=pop(s[j]);//依次弹出if(k!=s[i++])//进行比较break;}if(j<0)return1;//是回文return0;}}算法描述2先将整串字符压入栈,后将倒序方法用已知字符串的每个字符依次与出栈字符相比。inttext(char*s1){charstack[max],k;Inttop=-1;inti;for(i=0;i4、op+1;stack[top]=s1[i];//入栈}for(i=strlen(s1)-1;i>=0;i--){k=stack[top];top=top-1;if(s1[i]!=k){break;return0;}elsereturn1;}}算法描述3将已知字符串倒序赋值给另外一个字符串,比较它们整个字符串是否相等。inttext(char*s1){char*s2=newchar[strlen(s1)];inti;for(i=0;i5、1-i]=s1[i];if(strcmp(s1,s2))return1;elsereturn0;delete[]s2;}2.参考课件P36前序遍历二叉树的算法和程序写出后序遍历二叉树的算法及程序(非递归)算法比较前序遍历算法1.访问根节点2.遍历左子树3.遍历右子树4.返回后序遍历算法1.遍历左子树2.遍历右子树3.访问根节点4.返回VoidPreorder(structnode*t){structnode*p;structnode*s[max];inttop;top=-1;p=t;do{WHILE(p!=nu6、ll){printf(“%d”,p->data);IF(p->rlink!=null){top=top+1;s[top]=p->rlink;}p=p->llink;}IF(top!=-1){p=s[top];top=top-1;}}while((p!=null)7、8、(top!=-1))}VoidPostorder(structnode*t){structnode*p,*pre;//pre保存刚访问过节点structnode*s[max];inttop=-1;p=t;pre=null;While(p9、10、top>-11、1){//沿着左子树走到最底端while(p!=null){top=top+1;s[top]=p;p=p->llink;}p=s[top];If((p->rlink==null)12、13、(p->rlink==pre)){//如果没有右子树或者右子树刚被访问过printf(“%d”,p->data);top=top-1;pre=p;p=null;}Elsep=p->rlink;}}VoidInorder(structnode*t){structnode*p;structnode*s[max];inttop;top=-14、1;p=t;do{WHILE(p!=null)/*扫描左节点*/{top=top+1;s[top]=p;p=p->llink;}IF(top>=0){p=s[top];/*p所指的节点为无左子树或其左子树已经遍历过*/top=top-1;printf(“%d”,p->data);/*访问节点*/P=p->rlink/*扫描右子树*/}while((p!=null)15、16、(top!=-1)
4、op+1;stack[top]=s1[i];//入栈}for(i=strlen(s1)-1;i>=0;i--){k=stack[top];top=top-1;if(s1[i]!=k){break;return0;}elsereturn1;}}算法描述3将已知字符串倒序赋值给另外一个字符串,比较它们整个字符串是否相等。inttext(char*s1){char*s2=newchar[strlen(s1)];inti;for(i=0;i5、1-i]=s1[i];if(strcmp(s1,s2))return1;elsereturn0;delete[]s2;}2.参考课件P36前序遍历二叉树的算法和程序写出后序遍历二叉树的算法及程序(非递归)算法比较前序遍历算法1.访问根节点2.遍历左子树3.遍历右子树4.返回后序遍历算法1.遍历左子树2.遍历右子树3.访问根节点4.返回VoidPreorder(structnode*t){structnode*p;structnode*s[max];inttop;top=-1;p=t;do{WHILE(p!=nu6、ll){printf(“%d”,p->data);IF(p->rlink!=null){top=top+1;s[top]=p->rlink;}p=p->llink;}IF(top!=-1){p=s[top];top=top-1;}}while((p!=null)7、8、(top!=-1))}VoidPostorder(structnode*t){structnode*p,*pre;//pre保存刚访问过节点structnode*s[max];inttop=-1;p=t;pre=null;While(p9、10、top>-11、1){//沿着左子树走到最底端while(p!=null){top=top+1;s[top]=p;p=p->llink;}p=s[top];If((p->rlink==null)12、13、(p->rlink==pre)){//如果没有右子树或者右子树刚被访问过printf(“%d”,p->data);top=top-1;pre=p;p=null;}Elsep=p->rlink;}}VoidInorder(structnode*t){structnode*p;structnode*s[max];inttop;top=-14、1;p=t;do{WHILE(p!=null)/*扫描左节点*/{top=top+1;s[top]=p;p=p->llink;}IF(top>=0){p=s[top];/*p所指的节点为无左子树或其左子树已经遍历过*/top=top-1;printf(“%d”,p->data);/*访问节点*/P=p->rlink/*扫描右子树*/}while((p!=null)15、16、(top!=-1)
5、1-i]=s1[i];if(strcmp(s1,s2))return1;elsereturn0;delete[]s2;}2.参考课件P36前序遍历二叉树的算法和程序写出后序遍历二叉树的算法及程序(非递归)算法比较前序遍历算法1.访问根节点2.遍历左子树3.遍历右子树4.返回后序遍历算法1.遍历左子树2.遍历右子树3.访问根节点4.返回VoidPreorder(structnode*t){structnode*p;structnode*s[max];inttop;top=-1;p=t;do{WHILE(p!=nu
6、ll){printf(“%d”,p->data);IF(p->rlink!=null){top=top+1;s[top]=p->rlink;}p=p->llink;}IF(top!=-1){p=s[top];top=top-1;}}while((p!=null)
7、
8、(top!=-1))}VoidPostorder(structnode*t){structnode*p,*pre;//pre保存刚访问过节点structnode*s[max];inttop=-1;p=t;pre=null;While(p
9、
10、top>-
11、1){//沿着左子树走到最底端while(p!=null){top=top+1;s[top]=p;p=p->llink;}p=s[top];If((p->rlink==null)
12、
13、(p->rlink==pre)){//如果没有右子树或者右子树刚被访问过printf(“%d”,p->data);top=top-1;pre=p;p=null;}Elsep=p->rlink;}}VoidInorder(structnode*t){structnode*p;structnode*s[max];inttop;top=-
14、1;p=t;do{WHILE(p!=null)/*扫描左节点*/{top=top+1;s[top]=p;p=p->llink;}IF(top>=0){p=s[top];/*p所指的节点为无左子树或其左子树已经遍历过*/top=top-1;printf(“%d”,p->data);/*访问节点*/P=p->rlink/*扫描右子树*/}while((p!=null)
15、
16、(top!=-1)
此文档下载收益归作者所有