笔试面试--数据结构

freedomfanye 2020-04-19

==================================链表==================================

1. 找一个链表中倒数第k个结点(假设原链表肯定有多余k个结点)

假设整个链表有x个结点,用两个指针即可找到倒数第k个,示意图如下:

笔试面试--数据结构

先用一个指针a遍历到第k个 ;然后a、b指针同时开始往后,直到指针a结束,则b在这段时间里走过了x-k个结点,也就是倒数第k个结点

typedef struct {
    int data;
    Node *next;
}Node;

Node *findKthToTail(Node *head,int k)
{
    //假设链表不为空,且有多于k个结点
    Node *fast = head;
    Node *slow = head;
    for(int i=0;i<k;i++) {
        if(fast == NULL) {
            return NULL;
        }
        fast = fast->next;
    }
    while(fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

2. 单链表排序

3. 两个单链表求交、并、差

4. 单链表反转

Node是结点结构体类型:有数据域elemType data和指针域Node *next
第一个结点就是有效结点
Node *head = initSingleList();
//.....加入了很多新元素进去
reverseSingleList(&head); //或head = reverseSingleList(&head);

Node *reverseSingleList(Node **head)
{
    if(NULL == *head || NULL == (*head)->next) {
        return *head;
    }
    Node *a = *head;
    Node *b = a->next;
    Node *c = NULL;
    (*head)->next = NULL;
    while(NULL != b) {
        c = b->next;
        b->next = a;
        a = b;
        b = c;
    }
    *head = a;
    return a;
}

==================================二叉树==================================

1. 结点数量相关问题

(1)不同度结点的关系

(2)计算结点总数

https://www.cnblogs.com/taoXiang/p/12324454.html

(3)树深度

https://www.cnblogs.com/taoXiang/p/12324454.html

2. 二叉树形状推导

(1)已知前序遍历和中序遍历

前序:ABDHIEJKCFLMGNO

中序:HDIBJEKALFMCNGO

还原:

  分块,区分哪一块是左边的、哪一块是右边的:

    【A B DHI EJK C FLM GNO】

    【HDI B JEK A LFM C NGO】

  ①根据前序,A是最上面的结点,根据中序,则【HDI B JEK】为A左侧结点,【LFM C NGO】为A右侧结点

  笔试面试--数据结构

     ②分析A左侧这部分,右侧类似

  分析【B DHI EJK】【HDI B JEK】,B是根,【DHI】为B左侧结点,【JEK】为B右侧结点

  分析【C FLM GNO】【LFM C NGO】,C是根,【FLM】为C左侧,【GNO】为C的右侧结点

  笔试面试--数据结构

  ③

    分析【DHI】【HDI】,D是根,H为D左侧点,I为D右侧点

    分析【EJK】【JEK】,E为根,J为E左侧点,K为E右侧点

    分析【FLM】【LFM】,F为根,L为F左侧点,M为F右侧点

    分析【GNO】【NGO】,G为根,N为G左侧点,O为G右侧点

  笔试面试--数据结构

(2)已知后序遍历和中序遍历

后序:HIDJKEBLMFNOGCA

中序:HDIBJEKALFMCNGO

(3)已知后序遍历和前序遍历

无法推断

相关推荐