提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

数据结构实训作业(IV)

数据结构 作业 实训 IV
2023-06-13 09:15:43 时间

数据结构实训作业(IV)

于2020年11月2日2020年11月2日由Sukuna发布

二叉搜索树和排序的一些问题

第一题:判断是不是二叉排序树?

status JudgeBiTree(BiTree T)
//判断二叉树T是否为二叉排序树
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    struct BiTNode * St[100], *p;
    int top = 0; 			//置空栈
    if(T){
	    St[top++] = T;
        while(top){
	        p = St[--top]; 
            if(p->rchild != NULL){
                St[top++] = p->rchild;
                if(p->data.key>p->rchild->data.key) return NO;
            }
	        if(p->lchild != NULL){
                St[top++] = p->lchild;
                if(p->data.key<p->lchild->data.key) return NO;
            }
        }
    }
    return YES;
    /********** End **********/
}

前序遍历的非递归实现,每一次访问结点的时候就判断一下是不是满足二叉搜索树的条件,如果能成功安全退出,那就是搜索树了

第二题:线性时间复杂度的排序

想到了计数排序,开个新数组存就完事了

void sort(int a[],int n,int k)
//将a中元素递增排序
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int c[100]={0};
    int ranked[100]={0};
    for (int i = 0; i < n ; i++){
        c[a[i]]++;
    }
    for (int i = 1; i < k+1; ++i)
        c[i] += c[i-1];
    for (int i = n-1; i >= 0; --i)
        ranked[--c[a[i]]] = a[i];
    for (int i = 0; i < n; i++){
        a[i]=ranked[i];
    }
    /********** End **********/
}

第二题:查找中位数

快速排序

void swap (int *a,int *b){
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}

int partition(int L[],int low,int high)
{
	int i,num=low;
	for(i=low+1;i<=high;i++)
	{
		if(L[i]<L[low])
		{
			swap(&L[i],&L[num+1]);
			num++;
		}
	}
	swap(&L[low],&L[num]);
	return num;
}
int MidValue(int a[],int n)
//求a的中位数
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int low=0,high=n-1,pos;
    int mid=n/2;
    while(1){
        pos=partition(a,low,high);
		if(pos==mid)
			break;
		else if(pos>mid)
			high=pos-1;
		else low=pos+1;
    }
    if(n%2) return a[mid];
    else return (a[mid]+a[mid-1])/2;
    /********** End **********/
}

如果是偶数,怎么样怎么样,如果是奇数,怎么样怎么样……

相关文章