p=p->next;j++;
}
if(p->next==NULL||j>i-1) return ERROR;
q=p->next;
p->next=q->next ;
*s=q->data;
free(q);
return OK;
}/*listDelete*/
4、栈得基本操作函数:
int InitStack(SqStack *S); //构造空栈
int StackEmpty(SqStack *S);//判断栈空
int Push(SqStack *S,ElemType e);//入栈
int Pop(SqStack *S,ElemType *e);//出栈
函数conversion实现十进制数转换为八进制数,请将函数补充完整。
void conversion(){
InitStack(S);
scanf(“%d”,&N);
while(N){
Push(S,N%8) ;
N=N/8;
}
while( !StackEmpty(S) ){
Pop(S,&e);
printf(“%d”,e);
}
}//conversion
5、函数实现串得模式匹配算法。
int index_bf(sqstring*s,sqstring *t,int start){ int i=start-1,j=0;
while(ilen&&jlen)
if(s->data[i]==t->data[j]){
i++;j++;
}else{
i= i-j+1 ;j=0;
}
if(j>=t->len)
return i-t->len+1 ;
else
return -1;
}}/*listDelete*/
6、二叉树后序遍历递归算法
void function(Bitree *t){
if(p!=NULL){
function(p->lchild);
function(p->rchild);
printf(“%d”,p->data);
}
}
7、编写求一棵二叉树中结点总数得算法。
答案: (以先序遍历得方法为例)
void count_preorder(Bitree *t, int *n)
{
if(t!=NULL)
{*n++;
count_preorder(t->lchild);
count_preorder(t->lchild); }
}
8、函数InOrderTraverse(Bitree bt)实现二叉树得中序遍历。
void InOrderTraverse(BiTree bt){
if( bt!=NULL ){
InOrderTraverse(bt->lchild);
printf(“%c”,bt->data);
InOrderTraverse(bt->rchild) ;
}
9、函数depth实现返回二叉树得高度。
int depth(Bitree *t){
if(t==NULL)
return 0;
else{
hl=depth(t->lchild);
hr= de pth(t->rchild) ;
if( hl>hr )
return hl+1;
else
return hr+1;
}
}
10、交换二叉树结点左右子树得递归算法
Bitree *function(Bitree *bt){
Bitree *t,*t1,*t2;
if(bt==NULL)
t=NULL;
else{
t=(Bitree *)malloc(sizeof(Bitree));
t->data=bt->data;
t1=function(bt->left);
t2=function(bt->right);
t->left=t2;
t->right=t1;
}
return(t);
}
11、已知二叉树得先序遍历序列为ABCDEFGH,中序遍历序列为CBEDFAGH,画出二叉树。
答案:二叉树形态
