编程题,希冀题型解析

  • 题目详情

【问题描述】输入一个单向链表，输出该链表中倒数第k个结点，链表的最后一个结点是倒数第1个节点。

【输入形式】输入第一位为K值，其后接一串以空格分隔的整型值。
【输出形式】输出为倒数第K个结点的值，若无，则输出Not Found

【样例输入】3 13 45 54 32 1 4 98 2
【样例输出】4
【样例说明】K值为3，则输出链表倒数第3个结点的值，为4；数据输入间以空格隔开
【评分标准】本题要综合输出正确性及使用的数据结构。需由输入数据构建单链表。不使用链表的将不得分。

  • 题目主要步骤

1.创建并初始化链表
2.接收数据，并判断如何结束数据输入
3.遍历节点查找数据
4.输出查找的数据

  • 创建链表
typedef int datatype;
typedef struct node{
    datatype num;
    struct node *next;
}list;

初始化只需要将头节点的指针指向NULL就可以了

  • 接收数据并判断结束

以往的题是要求输入i,for循环i次判断输入结束，但本题并不能使用这种方法，这样就要求我们使用其他途径
要让scanf结束输出，我们可以用到"EOF"

Q1：什么是EOF?

EOF，为End Of File的缩写，通常在文本的最后存在此字符表示资料结束
在C语言中，或更精确地说成C标准函数库中表示文件结束符（end of
file）。在while循环中以EOF作为文件结束标志，这种以EOF作为文件结束标志的文件，必须是文本文件。在文本文件中，数据都是以字符的ASCII代码值的形式存放。我们知道，ASCII代码值的范围是0~127，不可能出现-1，因此可以用EOF作为文件结束标志。
————————————————
版权声明：本文为CSDN博主「一个奔跑的C」的原创文章，遵循CC 4.0
BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/henu1710252658/article/details/83040281

综上我们可以知道EOF值为-1，代表“结束”
实际运用如下

while(scanf("%d",&n) != EOF)
{
    your_code();
}

意思是当输入不为EOF时，永远执行your_code()
在windows系统下，scanf可以键入ctrl+z实现输入EOF
Linux系统下则是ctrl+d

  • 查找数据

题目要求查找倒数k位的数据，但单链表只能顺次遍历，这时候我们可以使用头插法，即让新数据永远放在第一位

const int i = 1;//本句写在main里
//i为插入的位置，x为插入的数据 
void insert(list *head, int i, datatype x)
{
    int j = 0;
    list *p;
    list *s;
    p = head;
    while(p->next != NULL && j < i-1)//判断插入位置 
    {
        p = p->next;
        j++;
    }
    if(p != NULL)
    {
        s = (list *)malloc(sizeof(list));//申请空间储存新数据 
        s->num = x;
        s->next = p->next;//s保存p的数据 
        p->next = s;//s成为p的下一个节点，即s插入到p前面 
    }
}

这段代码我沿用的其他程序的代码，因为没有做特殊优化，感兴趣的朋友可以自行将int i简化掉

  • 输出
//输出结果 
int output(list *head,int k)
{
    int j = 1;//计数器 
    list *p;
    p = head->next;//p指向第一个数据 
    while(p != NULL)//如果p存在数据 
    {
        if(j == k)//如果找到相应位置 
        {
            printf("%d\n",p->num);//输出数据 
            return 1;//返回1表示成功 
        }
        else
        {
            p = p->next;//否则遍历。继续找 
            j++;
        }
    }
    printf("Not Found\n");//遍历结束时j依然不等于k，查找失败 
    return 0;//返回0表示失败 
}

常规代码

源代码下载

倒数k.c
code by WWQ

作者：WWQ

This is just a placeholder img.