PTA-数据结构求链式线性表的倒数第K项

冷不防 2022-05-10 02:03 143阅读 0赞

7-24 求链式线性表的倒数第K项 （20 分）

给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第K个位置上的数字。

### 输入格式: ###

输入首先给出一个正整数K，随后是若干正整数，最后以一个负整数表示结尾（该负数不算在序列内，不要处理）。

### 输出格式: ###

输出倒数第K个位置上的数据。如果这个位置不存在，输出错误信息`NULL`。

### 输入样例: ###

4 1 2 3 4 5 6 7 8 9 0 -1

### 输出样例: ###

思路：设两个指针p\_left与p，先让p移动到第k个元素节点，p\_left指向首元素节点。之后，p走到尾节点时，p\_left正好走到倒数第k个节点。注意特殊情况，如节点数量小于k时的处理。

//库函数头文件包含
    #include<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    
    //函数状态码定义
    #define TRUE        1
    #define FALSE       0
    #define OK          1
    #define ERROR       0
    #define INFEASIBLE -1
    #define OVERFLOW   -2
    
    typedef int  Status;
    typedef int ElemType;
    typedef struct LNode{
        ElemType data;
        struct LNode* next;
    }LNode,*Linklist;
    
    Status ReadList(Linklist L)
    {
        Linklist p = L;
        ElemType e;
        while(scanf("%d",&e)!=EOF && e>=0)
        {
            Linklist pNew = (Linklist)malloc(sizeof(LNode));
            if(!pNew)
                exit(OVERFLOW);
            pNew->data = e;
            pNew->next = NULL;
            p->next = pNew;
            p = p->next;
        }
        return OK;
    }
    
    void PrintLastK(Linklist L,int k)
    {
        Linklist p_Left = L;
        Linklist p = L;
        int i=0;
        for(i=0;i<k;i++)
        {
            p = p->next;
            if(!p)
                break;
        }
        if(!p)
            printf("NULL\n");
        else
        {
            while(p)
            {
                p = p->next;
                p_Left = p_Left->next;
            }
            printf("%d\n",p_Left->data);
        }
    }
    
    int main()
    {
        Linklist L;
        L = (Linklist)malloc(sizeof(LNode));
        if(!L)
            exit(OVERFLOW);
        L->next = NULL;
    
        int k;
        scanf("%d",&k);
        ReadList(L);
        PrintLastK(L,k);
        return 0;
    }