每日一题： 输出单链表倒数第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;

}