《软件技术基础》实验指导（含答案）(6)

scanf( loc=blksearch(r,idx,key,idxN); if(loc!=-1) printf(查找到，是第%d个记录。\n else printf(记录查找不到！\n}

//分块查找

int blksearch(record r[],index idx[],keytype k,int n) { int i,low=0,high=n-1,mid,bh,find=0; //折半查找索引表 while(low<=high&&!find) { mid=(low+high)/2; if(kidx[mid].key)low=mid+1; else { high=mid-1; find=1; } } if(low

实验八：第2题

//判断二叉排序树的程序代码 #include #include #include

//二叉链表的结构类型定义 const int maxsize=1024; typedef int keytype; typedef struct node { keytype key; struct node *lchild,*rchild; }bitree;

bitree*creattree();

void preorder(bitree*);

 

26

void inorder(bitree*);

void main() { bitree*pb; pb=creattree(); preorder(pb); printf( inorder(pb); printf(是二叉排序树！\n}

//二叉树的建立 bitree*creattree() { keytype x; bitree*Q[maxsize]; int front,rear; bitree*root,*s; root=NULL; front=1;rear=0; printf(按层次输入二叉排序树的整型结点数据，0表示虚结点，-1表示结束：\n scanf(输入0表示虚结点，-1表示结束 while(x!=-1) { s=NULL; if(x!=0) { s=(bitree*)malloc(sizeof(bitree)); s->key=x; s->lchild=NULL; s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1)root=s; else { if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s; else Q[front]->rchild=s; if(rear%2==1)front++; } scanf( } return root; }

//二叉树的输出

 

27

void preorder(bitree*p) { if(p!=NULL) { printf( if(p->lchild!=NULL||p->rchild!=NULL) { printf( preorder(p->lchild); if(p->rchild!=NULL) printf( preorder(p->rchild); printf( } } }

//判断二叉排序树 keytype k=-32768; void inorder(bitree*p) { if(p!=NULL) { inorder(p->lchild); if(p->key>k) k=p->key; else { printf(不是二叉排序树！\n exit(0); } inorder(p->rchild); } }

28