2013年全国数据整理加强(3)

2013年全国数据整理加强

}
else if (i==n-1) //根结点无右子树，遍历序列的1—n-1是左子树
{p->rchild=null;
s.lvl=++R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);
}
else //根结点有左子树和右子树
{s.lvl=++R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);//左子树有关信息入队列
s.lvl=++R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);//右子树有关信息入队列
}
while (!empty(Q)) //当队列不空，进行循环，构造二叉树的左右子树
{ s=delqueue(Q); father=s.f;
for (i=s.l; i<=s.h; i++)
if (in[i]==level[s.lvl]) break;
p=(bitreptr)malloc(sizeof(binode)); //申请结点空间
p->data=level[s.lvl]; p->lchild=null; p->rchild=null; //填写该结点数据
if (s.lr==1) father->lchild=p;
else father->rchild=p； //让双亲的子女指针指向该结点
if (i==s.l)
{p->lchild=null; //处理无左子女
s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s);
}
else if (i==s.h)
{p->rchild=null; //处理无右子女
s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);
}
else{s.lvl=++R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);//左子树有关信息入队列
s.lvl=++R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); //右子树有关信息入队列
}
}//结束while (!empty(Q))
return(p);
}//算法结束

7、设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。
typedef struct node {int data; struct node *next;}lklist;
void intersection(lklist *ha,lklist *hb,lklist *&hc)
{
lklist *p,*q,*t;
for(p=ha,hc=0;p!=0;p=p->next)
{ for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;
if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;}
}
}

8、数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。
void union(int A[],B[],C[],m,n)
//整型数组A和B各有m和n个元素，前者递增有序，后者递减有序，本算法将A和B归并为递增有序的数组C。
{i=0; j=n-1; k=0;// i，j，k分别是数组A,B和C的下标，因用C描述，下标从0开始
while(i<m && j>=0)
if(a[i]<b[j]) c[k++]=a[i++] else c[k++]=b[j--];
while(i<m) c[k++]=a[i++];
while(j>=0) c[k++]=b[j--];
}算法结束
4、要求二叉树按二叉链表形式存储。15分
（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。
BiTree Creat() //建立二叉树的二叉链表形式的存储结构
{ElemType x；BiTree bt;
scanf(“%d”,&x); //本题假定结点数据域为整型
if(x==0) bt=null;
else if(x>0)
{bt=(BiNode *)mal
loc(sizeof(BiNode));
bt->data=x; bt->lchild=creat(); bt->rchild=creat();
}
else error(“输入错误”)；
return(bt);
}//结束 BiTree
int Judg