【趣学C语言和数据结构100例】

问题描述

71.设线性表 L=(a1. a2. a.....2.an-1.an.)采用带头结点的单链表保存，请设计一个空间复杂度为 O(1)且时间上尽可能高效的算法，使得单链表 A 分解为两个带头节点的单链表 A 和 B.使得 A 中含有原表中序号为奇数的元素，B 表中含有原表中序号为偶数的元素，且保持,素顺序不变。

72.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。

73.设计一个求结点x在二叉树中的双亲结点的算法

74.求二叉树的深度(递归算法)

75.二叉树存储形式为(lchild.data.rchild),给出求二叉树得大关键值的算法。

代码分析

==71.按奇偶分链表==
分析：传入2个链表A和B ，并且AB都改变，则函数名为：void 函数名(LiukList &A,LiukList &B);先对B创造节点。pre负责A，r负责B。p为工作指针。使p指向第一个节点，定义一个计数节点，如果i为偶数，则使pre跳过当前节点，令r为当前节点，并更新r的位置，更新p的位置。如果为计数，则使pre指向p,并且更新p的位置。在B的最后加入NULL。

==72.交换二叉树中所有结点左右子树==

//二叉树的数据结构:
//常用: T->lchild T->rchild T->data

typedef int DataType;
typedef struct Bstnode {
   
    DataType data;
    struct Bstnode *lchild, *rchild;
} Bstnode, *Bstree;

分析：无返回值，并且传入数T，故函数名为void swap(Bitree T);定义节点用于交换时的中间值。Lnode *p;如果T存在，则进行交换，否则跳过。在交换时，先进行递归swap(T->lchild);左右子树，然后再利用temp交换左右子树的节点。

==73.结点x在二叉树中的双亲结点==
分析：传入树和节点x，故函数名为void parent(Bitree T,char x)如果T存在，先左和右节点一样不，一样的话输出。如果左和右节点都比一样，则利用递归在parent(T->lchild, x)在左子树中查找。同理，在右子树中查找，可以找到结点x在二叉树中的双亲结点。

==74.二叉树的深度，用递归==
分析：传入树，故函数名为int 函数名(Bitree T)如果T为0，则返回0.否则进行计算。定义x和y用来记录左子树和右子树的深度，选择深度大的，并且进行进行+1，为返回值。左子树和右子树的深度用递归 函数名(T->lchild)可以得到 函数返回值。

==75.求二叉树得大关键值==
分析：返回值为int型+传入树，故函数名为int 函数名(Bitree L);如果T为0，则返回0.否则进行计算。定义x和y用来记录左子树和右子树的得大关键值,先得到两个的最大值，返回T本身和最大值中大的值。左子树和右子树的深度用递归 函数名(T->lchild)可以得到 函数返回值。

代码实现

#include<stdio.h>
int main(){
   
//    71.设线性表 L=(a1. a2. a.....2.an-1.an.)采用带头结点的单链表保存，请设计一个空间复杂度为 O(1)且时间上尽可能高效的算法，使得单链表 A 分解为两个带头节点的单链表 A 和 B.使得 A 中含有原表中序号为奇数的元素，B 表中含有原表中序号为偶数的元素，且保持,素顺序不变。
void func(Linklist &A,Linklist &B){
   
    B=(Linklist)mallocc(sizeof(Lnode));
    Lnode *p=A->next,*pre=A,*R=b;
    int i=1;
    while(p){
   
        if(i%2==0){
   
            pre->next=p->next;
            r->next=p;
            r=p;
            p=pre->next;
        }else{
   
            pre=p;
            p=p->next;
        }
        i++;
    }
    r->next=NULL;
} 
//    72.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。
typedef int DataType;
typedef struct Bitnode{
   
    DataType  data;
    struct Bitnode *lchild,*rchild;
}Bitnode,*Bitree;

void swap(Bitree T){
   
    Bitnode *p;
    if(T){
   
        swap(T->lchild);
        swap(T->rchild);

        p=T-lchild;
        T-lchild=T-rchild;
        T-rchild=P;
    }
}    

//    73.设计一个求结点x在二叉树中的双亲结点的算法
void parent(Bitree T,char x){
   
    if(T){
   
        if(T->lchild->data==x){
   
            printf("%c的双亲%c",x,T->data);
        }
        if(T->rchild->data==x){
   
            printf("%c的双亲%c",x,T->data);
        }
        parent(T->lchild,x);
        parent(T->rchild,x);

    }
}

//    74.求二叉树的深度(递归算法)
int Depth(Bitree T)
    if(T){
   
        int ldepth=Depth(T->lchild);
        int rdepth=Depth(T->rchild);
        if(ldepth>repth){
   
            return ldepth+1;
        }else{
   
            return rdepth+1;
        }    
    }else{
   
        return 0;
    }
}

//    75.二叉树存储形式为(lchild.data.rchild),给出求二叉树得大关键》值得算法。
int get_max(Bitree T)
    if(T){
   
        int maxl=get_max(T->lchild);
        int maxr=get_max(T->rchild);
        int max=maxl>maxr?maxl:maxr;
        return max>T->data?max:T->data;    
    }else{
   
        return 0;
    }
}    

    return 0;
}

总结

本文介绍了五个数据结构问题及其C语言实现，这些问题涉及链表和二叉树的操作，包括按奇偶分解链表、交换二叉树的左右子树、查找二叉树中某个节点的双亲节点、计算二叉树的深度以及求二叉树的最大关键值。这些算法不仅在理论上具有重要意义，而且在实际应用中也非常广泛。

按奇偶分解链表的问题要求我们将一个带头结点的单链表分解为两个子链表，其中一个包含原表中序号为奇数的元素，另一个包含序号为偶数的元素。这个问题的解决关键在于正确地遍历链表并根据条件将节点分配到两个不同的链表中。

交换二叉树中所有结点左右子树的问题要求我们对二叉树的每个节点都进行左右子树的交换。这个问题可以通过递归的方式解决，先递归地对左右子树进行交换，然后再交换当前节点的左右子树。

查找二叉树中某个节点的双亲节点的问题要求我们在给定的二叉树中找到某个节点的双亲节点。这个问题的解决需要递归地遍历二叉树，检查每个节点的左右子节点是否为目标节点。

计算二叉树的深度的问题要求我们找出给定二叉树的最大深度。这个问题可以通过递归的方式解决，递归地计算左右子树的深度，然后取两者的最大值并加一。

求二叉树的最大关键值的问题要求我们在给定的二叉树中找到最大的关键值。这个问题同样可以通过递归的方式解决，递归地比较左右子树和当前节点的值，取最大值。

这些算法的实现不仅展示了C语言在处理链表和树结构时的能力，也体现了算法设计的基本思想，如递归、遍历和条件判断。通过这些算法的学习，我们可以更好地理解数据结构和算法的基本概念，提高解决实际问题的能力。

总的来说，这些算法问题不仅锻炼了编程能力，也加深了对数据结构和算法的理解。通过这些问题的解决，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。这些算法的掌握对于计算机专业的学生和软件开发人员来说都是非常重要的。通过这些练习，我们可以逐步提高自己的编程技能，为将来的学习和工作做好准备。