2018-979

2018-979-软学

1.第一题

• 在Head为头指针的单链表中查找结点DATA域值为K的结点
• 并将该结点与其前驱结点（如果存在）交换位置

void jiaohuan(LinkList Head,int K){
    LNode *pre = Head,*p = Head -> next;
    if(p != NULL && p -> data == K){
        //如果第一个就对
        pre -> next = p -> next;
        p -> next = pre;
        return true;
    }
    p = p -> next;
    if(p != NULL){
        //之后的元素
        if(p -> data == K){
            pre -> next -> next = p -> next;
            p -> next = pre -> next;
            pre -> next = p;
            return true;
        }else{
            p = p -> next;
            pre = pre -> next;
        }
    }
    return false;
    
}

2.第二题

• 给定二叉树的根指针为Root
• 对二叉树自下而上、自左而右的层次遍历

typedef struct BiTNode{
    int data;                        //数据域
    struct BiTNode *lchild, *rchild;  //左、右孩子指针
}BiTNode, *BiTree;
void bianli(BiTree Root){
    BiTree Stack[MaxSize];
    int top = -1;//栈初始化
    BiTree Queue[MaxSize];
    int front,rear = -1;
    BiTree p = Root;
    if(p != NULL){
        Stack[++top] = p;
    }
    while(p != NULL || top != -1){
        
        if(p -> lchild != NULL){
            Stack[++top] = p -> lchild;
        }
        if(p -> rchild != NULL){
            Stack[++top] = p -> rchild;
        }else{
            p = Stack[top--];
            Queue[++rear] = p;
        }
        p = p -> lchild;
    }
    return Queue;
}

3.第三题

• 长度为n的数组A
• 已知前$m(m<n)$个元素按升序有序排列，后$n-m$个元素按降序有序排列
• 编写算法在$O(n)$时间内对数组A的元素按降序排序

int* Sort(int A[]){
    int C[];
    int low = m-1,high = m,i = 0;
    while(low >= 0 && high < n){
        if(A[high].data >= A[low.data]){
            C[i] = A[high];
            high++;
            i++;
        }else{
            C[i] = A[low];
            low--;
            i++;
        }
    }
    while(high < n){
        C[i] = A[high];
        high++;
        i++;
    }
    while(low >= 0){
        C[i] = A[low];
        low--;
        i++;
    }
    return C;
}