数据结构复习(2012)(4)

if(p==NULL)

return 1; QueueInit(Q);

QueueIn(Q,p); // 初始化队列，根结点指针入队 while(!QueueEmpty(Q)) { p=QueueOut(Q);

if (p->lchild && !tag)

QueueIn(Q,p->lchild); // 左孩子入队

else

if (p->lchild)

return 0; // 前边已有结点为空，本结点不空

else

tag=1;

// 首次出现结点为空

if (p->rchild && !tag)

QueueIn(Q,p->rchild); // 右孩子入队 else

if (p->rchild)

return 0;

else

tag=1;

}

return 1; }

3. 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。 解：

bool BisortTree(BiTree T,BiTree &PRE) // PRE为指向当前访问结点的前驱的指针

int last=0, flag=1; // last是全局变量，用来记录前驱结点值，只要每个结点都比前趋大就行 int IsBSTree(Bitree T) // 判断二叉树T是否二叉排序树，是则返回1，否则返回0 {

if (T->lchild && flag)

IsBSTree(T->lchild); if (T->data

flag=0; // 与其中序前驱相比较, flag=0表示当前结点比直接前驱小，则立即返回

last=T->data;

if (T->rchild && flag)

IsBSTree (T->rchild); return flag; }

4．对有序表R[0]至R[n-1]进行二分查找，查找成功时返回记录在表中的位置；查找失败时

显示：―没有找到！‖，试编写此程序。 解：void BinSearch()

{int R[MAXLEN],i,low,high,mid,n,x; char ch;

cout<< \请输入要查找的数据: \ cin>> x ; low=0; high= n-1 ; while (low<=high) { mid=(low+high)/2 ;

if (R[mid]>x) else

if (R[mid]

low=mid+1;

else

break;

}

if ( low>high )

{ cout<< \没有找到！\ if (R[mid]

cout<< \要找的数据\在第\的位置上\

mid++ ;

cout<< \可将此数插入到\的位置上。\ high=mid-1;

else

}

5．以单链表作为存储结构实现直接插入排序算法。 解： void InsertList (List head)

{ Lnode *p, * pprev,q,*qprev, *current;

if (!head) return;

pprev=head; p=head->next;

while (p)

{ q=head; qprev=NULL;

while(q->keykey) // 查找插入位置 { qprev=q; q=q->next; }

if (q= =p) // p最大，无须插入 { pprev=p; p=p->next;} else

{ current=p; p=p->next;

pprev->next=p; current->next=q;

if (q= =head) // 插在表头

head=current;

else // 插在中间某个位置上 qprev->next=current; }

} }

6. 编程：设计一个函数修改冒泡排序过程以实现双向冒泡排序。

提示：双向冒泡排序是每一趟通过每两个相邻的关键字进行比较，产生最小和最大的元素。 解：

void dbubble (SeqList r)

{ int i,j,t,b;

while(b) { b=0;

for (j=n-i+1;j>=i+1;j--) // 由底向上 if (r[j].key

r[j-1]=t; }

for (j=i+1;jr[j+1].key) {b=1; t=r[j]; r[j]=r[j+1]; r[j+1]=t; } i++; } }