C语言数据结构-链表倒数查找

矫情吗；* 2022-10-23 04:58 139阅读 0赞

# 链表倒数查找 #

已知一个带有表头结点的单链表, 假设链表只给出了头指针L。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。  
函数原型为：`int lnk_search(LinkList L, int k, ElemType* p_ele)`  
若查找成功，函数通过指针参数 p\_ele 返回该结点 data 域的值，此时函数返回 1；否则，函数返回 0。相关定义如下：

struct _lnklist{
        ElemType data;
        struct _lnklist *next;
    };
    
    typedef struct _lnklist Node;
    typedef struct _lnklist *LinkList;

提供代码

#include <stdio.h>
    #include <stdlib.h>
    #include "list.h" // 请不要删除，否则检查不通过
    
    int lnk_search(LinkList L, int k, ElemType* p_ele) {
    
    }

参考代码

/*
    链表 倒数查找
    
    已知一个带有表头结点的单链表, 假设链表只给出了头指针L。在不改变链表的前提下，
    请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。
    函数原型为：int lnk_search(LinkList L, int k, ElemType* p_ele)
    若查找成功，函数通过指针参数 p_ele 返回该结点 data 域的值，此时函数返回 1；否则，函数返回 0。相关定义如下：
    */
    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    //#include "list.h" // 请不要删除，否则检查不通过
    #define ElemType int
    
    struct _lnklist {
        ElemType data;
        struct _lnklist* next;
    };
    
    typedef struct _lnklist Node;
    typedef struct _lnklist* LinkList;
    
    int lnk_search(LinkList L, int k, ElemType* p_ele) {
        //带计数器遍历链表,得到链表长度
        int count = 1;
        LinkList tmp = L;
        int i = 0;
        while (tmp->next != NULL)
        {
            tmp = tmp->next;
            count++;
        }
        tmp = L;
        //遍历count-k次链表
        if (k > count||k<=0)
        {
            return 0;
        }
        else
        {
            for (i = 0; i < count - k; i++)
            {
                tmp = tmp->next;
            }
            *p_ele = tmp->data;
            return 1;
        }
    }
    
    LinkList creatList(int m)
    {
        LinkList Head = (LinkList)malloc(sizeof(Node) * 2);
        if (Head == NULL) return NULL;
        Head->data = m;
        Head->next = NULL;
        return Head;
    }
    void pushByEnd(LinkList L, int n)
    {
        LinkList Node = (LinkList)malloc(sizeof(Node) * 2);
        if (Node == NULL) return;
    
        while (L->next != NULL)
        {
            L = L->next;
        }
    
        L->next = Node;
        Node->data = n;
        Node->next = NULL;
    }
    
    void print(LinkList L)
    {
        while (L->next != NULL)
        {
            printf("%d ", L->data);
            L = L->next;
        }
        printf("%d ", L->data);
        printf("\n");
    }
    
    
    int main()
    {
        int k = 0;
        printf("请输入你想查找第几位的数字（正整数）:>\n");
        scanf("%d", &k);
        ElemType p_ele;
    
        printf("请输入从大到小的链表，按回车输入下一个数字，按ctrl+z结束输入:>\n");
        int m = 0;
        scanf("%d", &m);
        LinkList L = creatList(m);
        if (L == NULL) return;
        int n = 0;
        while (scanf("%d", &n) != EOF)
        {
            pushByEnd(L, n);
        }
        print(L);
        if (lnk_search(L, k, &p_ele))
        {
            printf("找到了：%d", p_ele);
        }
        else 
        {
            printf("没找到");
        }
    
        return 0;
    }
    /*
    请输入你想查找第几位的数字（正整数）:>
    2
    请输入从大到小的链表，按回车输入下一个数字，按ctrl+z结束输入:>
    9
    8
    7
    6
    5
    4
    3
    2
    1
    ^Z
    ^Z
    ^Z
    9 8 7 6 5 4 3 2 1
    找到了：2
    */