數(shù)據(jù)結構練習題4
1. 編一C程序,它能根據(jù)輸入的二叉樹中序和后序序列來構造該二叉樹,并能輸出該二叉樹的前序序列和該二叉樹的度為2的結點的個數(shù)并能判斷該二叉樹是否為二叉排序樹(若是輸出Yes;否則輸出No)。(輸入次序是:表示中序序列的字母串、表示后序序列的字母串)。
(注:程序的可執(zhí)行文件名必須是 e1.exe,存于你的賬號或其debug目錄下。)
#include stdio.h
#include malloc.h
#include string.h
void exit(int);
#define MAX 100
typedef struct node{
char d;
struct node *lchild,*rchild;
}Tnode;
void MKTree(char in[],int is,int ie,char post[],int posts,int poste,Tnode **r)
{
int i;
if(is ie||posts poste)
*r=NULL;
else{
*r=malloc(sizeof(Tnode));
(*r)- d=post[poste];
for(i=is;i =ie;i++)
if(post[poste]==in[i])
{
MKTree(in,is,i-1,post,posts,posts+i-is-1, (*r)- lchild);
MKTree(in,i+1,ie,post,posts+i-is,poste-1, (*r)- rchild);
break;
}
if(i ie){
printf(“Error:input contain an error !\n”);
exit(9);
}
}
}
void BST(char in[],int is,int ie)
{
int i;
if(is==ie)
printf(“yes\n”);
else
{
for(i=is;i =ie;i++)
{
if(in[i] in[i+1])
continue;
else
break;
}
if(i==ie)
printf(“YES\n”);
else
printf(“NO\n”);
}
}
void preorder(Tnode *r)
{
if(r)
{
printf(“%c”,r- d);
preorder(r- lchild);
preorder(r- rchild);
}
}
int seconde(Tnode *r)
{
if(r==NULL)
return 0;
else
if((r- lchild)!=NULL (r- rchild)!=NULL)
return 1;
else
return seconde(r- lchild)+seconde(r- rchild);
}
void main()
{
Tnode *r;
char post[MAX],in[MAX];
printf(“input inorder and postorder !\n”);
gets(in);
gets(post);
MKTree(in,0,strlen(in)-1,post,0,strlen(post)-1, r);
printf(“the preorder is as follows:\n”);
preorder(r);
printf(“\n there are %d seconde in the tree \n”,seconde(r));
printf(“if the tree is BST:\n”);
BST(in,0,strlen(in)-1);
}
2.編一C程序,它能讀入一串整數(shù)(以-9999為結束標記),再以與輸入次序相反的次序輸出這串整數(shù)(輸入、出時,兩個相鄰的整數(shù)用空格隔開)。
(注:程序的可執(zhí)行文件名必須是 e2.exe,存于你的賬號或其debug目錄下。)
#include stdio.h
#define max 10000
main()
{
int a[max];
int n=0,i,d;
printf(“please enten tne number:\n”);
do{
scanf(“%d”, d);
if(d==-9999)
break;
n++;
a[n]=d;
}while(9);
for(i=n;i 0;i——)
printf(“%4d”,a[i]);
printf(“\n”);
}
數(shù)據(jù)結構練習題5
1. 編一C程序,它能讀入一個大寫英文字母串(字母個數(shù)不多于100,字母兩兩不同),并構造以這些字母為關鍵字的二叉排序樹,再輸出該二叉排序樹的后序序列和頁結點個數(shù)。
(注:程序的可執(zhí)行文件名必須是 e1.exe,存于你的賬號或其debug目錄下,否則無成績)
2. 編一C程序,它能讀入兩組整數(shù)(每組整數(shù)都以-9999為結束標記,-9999不算在內。個數(shù)都不大于1000),并以從小到大的次序輸出既在第一組整數(shù)中也在第二組整數(shù)中的所有整數(shù)(同一個整數(shù)不能輸出兩次)。(輸入時,兩個相鄰的整數(shù)用空格隔開)。
(注:程序的可執(zhí)行文件名必須是 e2.exe,存于你的賬號或其debug目錄下,否則無成績)
#include stdio.h
void paixu(int r[],int n)
{
int i,j,k;
int exchange;
for(i=0;i =n;i++)
{
exchange=0;
for(j=n-1;j =i;j——)
if(r[j+1] r[j])
{
k=r[j+1];
r[j+1]=r[j];
r[j]=k;
exchange=1;
}
if(!exchange)
break;
}
}
int jiaoji(int m[],int n[],int l[],int countaa,int countbb)
{
int w,x,y;
int i=0,j=0,k=0;
for(w=0;w =countaa;w++)
{
for(x=w+1;x =countaa;x++)
{
if(m[w]==m[x])
{
countaa——;
for(y=x;y =countaa;y++)
{
m[y]=m[y+1];
}
x——;
}
}
}
while(i =countaa)
{
for(j=0;j =countbb;j++)
{
if(m[i]==n[i])
{
l[k]=m[i];
k++;
break;
}
}
i++;
}
return k;
}
void main()
{
int a[1000],b[1000],c[2000];
int excange=0,i,countA,countB,countC;
printf(“請輸入數(shù)組a: \n”);
for(i=0;i =1000;i++)
{
scanf(“%d”, a[i]);
if(a[i]==-9999)
break;
}
countA=i-1;
paixu(a,countA);
printf(“請輸入數(shù)組b: \n”);
for(i=0;i =1000;i++)
{
scanf(“%d”, b[i]);
if(b[i]==-9999)
break;
}
countB=i-1;
paixu(b,countB);
countC=jiaoji(a,b,c,countA,countB);
printf(“\n\n”);
for(i=0;i =countC-1;i++)
printf(“%d”,c[i]);
printf(“\n”);