计算机软件基础习题ppt课件.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<=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)return 1;//是回文return 0;}else //长度为奇数{i=lenth/2;for(j=0;j<=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)return 1;//是回文return 0;}}算法描画2•先将整串字符压入栈，后将倒序方法用知字符串的每个字符依次与出栈字符相比。

int text (char *s1){ char stack[max],k;Int top=-1;int i;for(i=0; i=0;i--){k=stack[top]; top=top-1; if(s1[i]!=k){ break; return 0;} else return 1;}}算法描画3•将知字符串倒序赋值给另外一个字符串，比较它们整个字符串能否相等int text (char *s1){ char *s2=new char[strlen(s1)];int i;for(i=0; idata)；• 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)||(top！ = -1)) •}•Void Postorder (struct node *t)•{ struct node *p，*pre；//pre保管刚访问过节点• struct node *s[max];• int top=-1; • p=t;•pre=null;•While(p||top>-1)• { //沿着左子树走到最底端• while(p!=null)• { top=top+1;• s[top]=p;• p=p->llink;• }• p=s[top];• 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 *s[max];• int top; • top=-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)||(top！ = -1)) •}思索习题•如何如何对二叉二叉树线索化索化• 遍遍历二叉二叉树是以一定是以一定规那么将二叉那么将二叉树的的节点排成一个点排成一个线性序列，得到二叉性序列，得到二叉树中中节点点的特定序列〔前序，中序，后序〕。

本的特定序列〔前序，中序，后序〕本质上是上是对一个非一个非线性构造性构造进展展线性化操作，性化操作，使每个使每个节点〔除第一个和最后一个〕在点〔除第一个和最后一个〕在这些些线性序列中性序列中仅有一个直接前有一个直接前驱和直接后和直接后继   思索习题•问题问题•     但是二叉树作为链式的存储构造，只能但是二叉树作为链式的存储构造，只能找到节点的左右子树，不能得到节点在任找到节点的左右子树，不能得到节点在任一序列中的前趋后继，这种信息只需在遍一序列中的前趋后继，这种信息只需在遍历的动态过程中才干等到历的动态过程中才干等到思索习题•处理方法处理方法•添加两个标志域添加两个标志域•LTAG=0,Lchild域指向节点的左子树域指向节点的左子树•LTAG=1,Lchild域指向节点的前驱域指向节点的前驱•RTAG=0,Rchild域指向节点的右子树域指向节点的右子树•RTAG=1,Rchild域指向节点的后继域指向节点的后继DATALTAGRTAGRchildLchild思索习题•提示：提示：                                   if(p->llink!=NULL)•           p->ltag=0;•else•{•p->ltag=1;•p->llink=pre;•} //建立建立P节点的左线索，指向前趋节点节点的左线索，指向前趋节点Pre•if(pre!=NULL)•{•if(pre->rlink!=NULL)•pre->rtag=0;•else•{•pre->rtag=1;•pre->rlink=p;•}//前趋节点前趋节点Pre建立右线索，指向节点建立右线索，指向节点P•}•pre=p;//pre跟上跟上p,以便以便p向后挪动，保管前一次向后挪动，保管前一次访问节点访问节点•。