BUPT2018级计算机院OJ习题与个⼈解答[链表⼀][附加测试样
例]
Name: The Answer Of OJ Of BUPT SCS[LinkList 1][附加测试样例]
Author: Chengmin Zhang
Date: 2019-03-21 WED
Title: 链表⼀
测试样例下载（点击下⽅蓝字）
Questions List:
A.实验11_4_初识链表
B.实验11_10_链表排序
C.实验11_11_链表匹配
D.实验11_13_链表交换
A.实验11_4_初识链表
运⾏时间限制: 1000 运⾏内存限制: 65536
参考答案运⾏时间: 5 参考答案运⾏内存: 796
题⽬描述:
已知⼀个正整数序列，个数未知，但⾄少有⼀个元素，你的任务是建⽴⼀个单链表，并使⽤该链表存储这个正整数序列，然后统计这个序列中元素的最⼤值与最⼩值，
计算序列全部元素之和。正整数的输⼊⽤ -1作为结束标志，注意-1不算这个正整数序列中的元素（不要统计 -1）。
输⼊与输出要求:
输⼊⼀个正整数序列，正整数序列元素的个数未知，但以输⼊“-1”结束，输⼊“-1”前⾄少输⼊⼀个正整数。
序列中的元素范围在1—999999999之间。输出三个正整数，即最⼤值、最⼩值、所有元素之和。
数据最多的测试⽤例节点数在1000这个数量级，所有整数可以⽤int型存储。请注意输⼊输出格式。
输⼊样例
1 4 99 21 50 61 3
2 4 -1
输出样例
The maximum,minmum and the total are:99 1 272
参考代码
#include <stdio.h>
#include <stdlib.h>
// 1 Define the Node struct (the Body of the LinkList)
typedef struct Node {
int number;
struct Node *next;
} Node;
// 2 Define the LinkList struct (the Head of the LinkList)
// Including the headPtr and the length of linkList
typedef struct LinkList {
struct Node *next;
int length;
} LinkList;
// 3 InitTheLinkList
/
/ FunctionName: InitTheLinkList
// ParameterList: LinkList *linkList
// ReturnValue: void
void InitTheLinkList(LinkList *linkList) {
linkList->length = 0;
Node *headNode = (Node *)malloc(sizeof(Node));
linkList->next = headNode;
headNode->number = 0;
headNode->next = NULL;
}
// 4 Input Array Thourgh scanf(!!USING THE Iterative Method!!)
/
/ FunctionName: InputLinkListByScanf
sort of link什么意思// ParameterList: LinkList *linkList, Node *lastNode
// ReturnValue: Node *newlastNode (if input equals -1 then return NULL) // Explaination: The number input will be set in the end of linkList Node *InputLinkListByScanf(LinkList *linkList, Node *lastNode) {
Node *newlastNode = (Node *)malloc(sizeof(Node));
newlastNode->next = NULL;
scanf("%d", &newlastNode->number);
if (newlastNode->number == -1) {
return NULL;
} else {
lastNode->next = newlastNode;
linkList->length += 1;
InputLinkListByScanf(linkList, newlastNode);
}
}
// 5 Print the LinkList
// FunctionName: PrintLinkList
// ParameterList: LinkList *linkList
// ReturnValue: void
void PrintLinkList(LinkList *linkList) {
Node *node = linkList->next;
node = node->next;
if (node == NULL) {
printf("The linkList is empty!\n");
linkList->length = 0;
return;
}
for (int i = 0; i < linkList->length; i++) {
printf("%d ", node->number);
node = node->next;
}
}
// 6 Return the MAX MIN SUM of LinkList
// FunctionName: TheMAXMINSUMofLinkList
/
/ ParameterList: LinkList *linkList
// ReturnValue: int *array
int *TheMAXMINSUMofLinkList(LinkList *linkList) {
int *theReturnArray = (int *)malloc(sizeof(int) * 3);
for (int i = 0; i < 3; i++)
theReturnArray[i] = 0;
Node *node = linkList->next;
node = node->next;
if (node == NULL) {
printf("The linkList is empty!\n");
linkList->length = 0;
return theReturnArray;
}
theReturnArray[1] = node->number;
for (int i = 0; i < linkList->length; i++) {
if (node->number > theReturnArray[0]) {
theReturnArray[0] = node->number;
}
if (node->number < theReturnArray[1]) {
theReturnArray[1] = node->number;
}
theReturnArray[2] += node->number;
node = node->next;
}
return theReturnArray;
}
// 7 Clear the LinkList
// FunctionName: ClearLinkList
// ParameterList: LinkList *linkList
// ReturnValue: void
void ClearLinkList(LinkList *linkList) {
Node *node = linkList->next;
node = node->next;
Node *nextNode;
while (node) {
nextNode = node->next;
free(node);
node = nextNode;
}
free(linkList->next);
}
int main() {
LinkList linkList;
InitTheLinkList(&linkList);
InputLinkListByScanf(&linkList, );
// PrintLinkList(&linkList);
int *theReturn = TheMAXMINSUMofLinkList(&linkList);
printf("The maximum,minmum and the total are:%d %d %d\n", theReturn[0],
theReturn[1], theReturn[2]);
ClearLinkList(&linkList);
return 0;
}
B.实验11_10_链表排序
题⽬描述运⾏时间限制: 1000 运⾏内存限制: 65536
参考答案运⾏时间: 6 参考答案运⾏内存: 792
问题描述：
问题描述：已知⼀个正整数组成的⽆序序列，个数未知，但⾄少有⼀个元素，你的任务是建⽴⼀个单链表，并使⽤该链表存储这个正整数序列，然后将这个链表进⾏排序，使得排序后的链表为递增序列。
正整数的输⼊⽤-1作为结束标志，注意-1不算这个正整数序列中的元素（不要统计-1）。
在排序的过程中，你可以⾃⼰选择排序算法（冒泡排序、选择排序等），但必须是通过修改结点的指针域来进⾏排序，⽽不是对结点的数据域进⾏修改。程序结束后要释放所有节点占据的空间。
输⼊与输出要求：
输⼊⼀个元素个数未知的正整数序列，以输⼊“-1”结束，输⼊“-1”前⾄少输⼊⼀个正整数。输出经过排序后的链表，每个元素后有⼀个空格，注意最后⼀个元素后只有换⾏符。
数据最多的测试⽤例节点数在1000这个数量级，所有整数可以⽤int型存储。请注意输⼊输出格式。
输⼊样例
49 38 65 97 76 13 27 49 -1
输出样例
The new list is:13 27 38 49 49 65 76 97
参考代码
#include <stdio.h>
#include <stdlib.h>
// 1 Define the Node struct (the Body of the LinkList)
typedef struct Node {
int number;
struct Node *next;
} Node;
// 2 Define the LinkList struct (the Head of the LinkList)
/
/ Including the headPtr and the length of linkList
typedef struct LinkList {
struct Node *next;
int length;
} LinkList;
// 3 InitTheLinkList
// FunctionName: InitTheLinkList
// ParameterList: LinkList *linkList
// ReturnValue: void
void InitTheLinkList(LinkList *linkList) {
linkList->length = 0;
Node *headNode = (Node *)malloc(sizeof(Node));
linkList->next = headNode;
headNode->number = 0;
headNode->next = NULL;
}
// 4 Input Array Thourgh scanf(!!USING THE Iterative Method!!)
// FunctionName: InputLinkListByScanf
// ParameterList: LinkList *linkList, Node *lastNode
// ReturnValue: Node *newlastNode (if input equals -1 then return NULL)
// Explaination: The number input will be set in the end of linkList
Node *InputLinkListByScanf(LinkList *linkList, Node *lastNode) {
Node *newlastNode = (Node *)malloc(sizeof(Node));
newlastNode->next = NULL;
scanf("%d", &newlastNode->number);
if (newlastNode->number == -1) {
return NULL;
lastNode->next = newlastNode;
linkList->length += 1;
InputLinkListByScanf(linkList, newlastNode);
}
}
// 5 Print the LinkList
/
/ FunctionName: PrintLinkList
// ParameterList: LinkList *linkList
// ReturnValue: void
void PrintLinkList(LinkList *linkList) {
Node *node = linkList->next;
node = node->next;
if (node == NULL) {
printf("The linkList is empty!\n");
linkList->length = 0;
return;
}
for (int i = 0; i < linkList->length; i++) {
printf("%d ", node->number);
node = node->next;
}
putchar('\n');
}
// 6 Sort The Linklist with Bubble Sort
// FunctionName: SortLinklist
// ParameterList: LinkList *linkList
// ReturnValue: void
void SortLinklist(LinkList *linkList, Node *theFrontOfStartNode, int *sortTime, int *turns) {
if (*sortTime > linkList->length - *turns - 1) {
return;
}
Node *currentNode1 = theFrontOfStartNode->next;
Node *currentNode2 = currentNode1->next;
if (currentNode1->number > currentNode2->number) {
currentNode1->next = currentNode2->next;
currentNode2->next = currentNode1;
theFrontOfStartNode->next = currentNode2;
}
*sortTime += 1;
SortLinklist(linkList, theFrontOfStartNode->next, sortTime, turns);
}
// 7 Clear the LinkList
// FunctionName: ClearLinkList
// ParameterList: LinkList *linkList
// ReturnValue: void
void ClearLinkList(LinkList *linkList) {
Node *node = linkList->next;
node = node->next;
Node *nextNode;
while (node) {
nextNode = node->next;
free(node);
node = nextNode;
}
free(linkList->next);
}
// 0 int main
int main() {
LinkList linkList;
InitTheLinkList(&linkList);
InputLinkListByScanf(&linkList, );
for (int i = 0; i < linkList.length; i++) {
int j = 1;
SortLinklist(&linkList, , &j, &i);
}
printf("The new list is:");
PrintLinkList(&linkList);
ClearLinkList(&linkList);
return 0;
}
C.实验11_11_链表匹配
运⾏时间限制: 1000 运⾏内存限制: 65536
参考答案运⾏时间: 5 参考答案运⾏内存: 796
问题描述：已知两个由正整数组成的⽆序序列A、B，每个序列的元素个数未知，但⾄少有⼀个元素。你的任务是判断序列B是否是序列A的连续⼦序列。假设B是“1
9 2 4 18”，A是“33 64 1 9 2 4 18 7”，B是A的连续⼦序列；假设B是“1 9 2 4 18”，A是“33 1 9
64 2 4 18 7”，B不是A的连续⼦序列。
要求：
建⽴两个单链表A、B⽤于存储两个正整数序列，然后按照题⽬的要求，判断链表B是否是链表A的连续⼦序列。正整数的输⼊⽤-1作为结束标志，注意-1不算这个正整数序列中的元素（不要统计-1）。在程序结束前要释放链表A、B中的所有节点。
输⼊与输出要求：
依次输⼊两个乱序的正整数序列A、B，序列中元素个数未知，但每个序列⾄少有⼀个元素，并以输⼊“-1”结束，每个序列占⼀⾏。如果序列B是序列A的连续⼦序列，则输出“ListB is the sub sequence of ListA.”，否则输出“ListB is not the sub sequence of ListA.”。数据最多的测试⽤例节点数在100这个数量级，所有整数可以⽤int型存储。请注意输⼊输出格式。
输⼊样例
Sample 1:
5 4 3 2 1 -1
3 2 1 -1
Sample 2:
1 2 3 4 5 6 7 8 9 -1
1 2 3 4 5 6 7 8 0 -1
输出样例
Sample 1: ListB is the sub sequence of ListA.
Sample 2: ListB is not the sub sequence of ListA.
参考代码
#include <stdio.h>
#include <stdlib.h>
// 1 Define the Node struct (the Body of the LinkList)
typedef struct Node {
int number;
struct Node *next;
} Node;
// 2 Define the LinkList struct (the Head of the LinkList)
// Including the headPtr and the length of linkList
typedef struct LinkList {
struct Node *next;
int length;
} LinkList;
// 3 InitTheLinkList
// FunctionName: InitTheLinkList
// ParameterList: LinkList *linkList
// ReturnValue: void
void InitTheLinkList(LinkList *linkList) {
linkList->length = 0;
Node *headNode = (Node *)malloc(sizeof(Node));
linkList->next = headNode;
headNode->number = 0;
headNode->next = NULL;
}
// 4 Input Array Thourgh scanf(!!USING THE Iterative Method!!)
// FunctionName: InputLinkListByScanf
// ParameterList: LinkList *linkList, Node *lastNode
// ReturnValue: Node *newlastNode (if input equals -1 then return NULL)
// Explaination: The number input will be set in the end of linkList
Node *InputLinkListByScanf(LinkList *linkList, Node *lastNode) {
Node *newlastNode = (Node *)malloc(sizeof(Node));
newlastNode->next = NULL;
scanf("%d", &newlastNode->number);
if (newlastNode->number == -1) {
return NULL;
} else {
lastNode->next = newlastNode;
linkList->length += 1;
InputLinkListByScanf(linkList, newlastNode);
}
}
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论