每日一题: 输出单链表倒数第K个结点值(法1)
题目
输出单链表 倒数第K个结点值
【问题描述】输入一个单向链表,输出该链表中倒数第k个结点,链表的最后一个结点是倒数第1个节点。
【输入形式】输入第一位为K值,其后接一串以空格分隔的整型值。
【输出形式】输出为倒数第K个结点的值,若无,则输出Not Found
【样例输入】3 13 45 54 32 1 4 98 2
【样例输出】4
【样例说明】K值为3,则输出链表倒数第3个结点的值,为4;数据输入间以空格隔开
【评分标准】本题要综合输出正确性及使用的数据结构。需由输入数据构建单链表。不使用链表的将不得分。
源代码
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> typedef struct node { int data; struct node* next; }SLinkNode; void InitList(SLinkNode*& L) { L = (SLinkNode*)malloc(sizeof(SLinkNode)); L->next = NULL; } void InsElem(SLinkNode* L, int n) { SLinkNode* p = L; SLinkNode* s = p->next; while (s != NULL) { p = p->next; s = s->next; } InitList(s); s->data = n; p->next = s; } int GetElem(SLinkNode* L, int i) { int j = 0; SLinkNode* p = L; if (i <= 0) return 0; while(p!=NULL && j<i) { j++; p = p->next; } if (p == NULL) return 0; else { printf("%d", p->data); return 1; } } int main() { SLinkNode* L; InitList(L); int k, n, j; j = 0; scanf_s("%d", &k); while (getchar() != '\n') { scanf_s("%d", &n); InsElem(L, n); j++; } k = j - k + 1; if (!GetElem(L, k)) { printf("Not Found"); } return 0; }
思路解析
#define _CRT_SECURE_NO_WARNINGS
/*这是一个预处理指令,用于禁用某些编译器的警告信息。具体来说,它禁用了使用不安全函数的警告信息。如果不加这个指令,当你使用一些被认为不安全的函数时,编译器会给出警告信息,但是加上这个指令后,编译器就不会再给出这些警告信息了。*/
#include<stdio.h> //C语言的头文件
#include<stdlib.h> //C++样式
typedef struct node
{ //单链表结点声明
int data;
struct node* next;
}SLinkNode;
void InitList(SLinkNode*& L)
{ //初始化线性表
L = (SLinkNode*)malloc(sizeof(SLinkNode));
L->next = NULL; //为空表
}
void InsElem(SLinkNode* L, int n)
{
SLinkNode* p = L;
SLinkNode* s = p->next; //设置两个指针
while (s != NULL)
{
p = p->next;
s = s->next;
} //两个指针前后遍历链表
InitList(s); //初始化链表
s->data = n;
p->next = s;
}
int GetElem(SLinkNode* L, int i)
{ //查找第i个元素
int j = 0; //计数
SLinkNode* p = L; //设置指针
if (i <= 0)
return 0; //需找元素不符合要求
while(p!=NULL && j<i) //链表不为空
{
j++;
p = p->next;
} //遍历
if (p == NULL) //链表为空
return 0;
else //不为空,则遍历输出值
{
printf("%d", p->data);
return 1;
}
}
int main()
{
SLinkNode* L; //结点声明
InitList(L); //初始化链表
int k, n, j; //记录 首位 输入的数据 计数
j = 0; //计数
scanf_s("%d", &k); //用户输入首个数据
while (getchar() != '\n')
{ //将其他数据一次插入链表
scanf_s("%d", &n);
InsElem(L, n);
j++;
}
k = j - k + 1; //依照原序计算出正序的逆序位数
if (!GetElem(L, k))
{
printf("Not Found");
}
return 0;
}