计导课设_链表练习1

于由Jray发布

大家可以到我的oj平台进行测试，账户可以自行注册

http://oj.jray.xyz/

问题 A: 实验11_4_初识链表

时间限制: 1 Sec  内存限制: 128 MB

题目描述

已知一个正整数序列，个数未知，但至少有一个元素，你的任务是建立一个单链表，并使用该链表存储这个正整数序列，然后统计这个序列中元素的最大值与最小值，计算序列全部元素之和。正整数的输入用-1作为结束标志，注意-1不算这个正整数序列中的元素（不要统计-1）。

输入

一个正整数序列，正整数序列元素的个数未知，但以输入“-1”结束，输入“-1”前至少输入一个正整数。序列中的元素范围在1—999999999之间。

输出

三个正整数，即最大值、最小值、所有元素之和。
数据最多的测试用例节点数在1000这个数量级，所有整数可以用int型存储。
请注意输入输出格式。

样例输入

1 4 99 21 50 61 32 4 -1

样例输出

The maximum,minmum and the total are:99 1 272

示例代码

/*
 * Copyright (C) Jray
 * 
 * 2020.03.01
 */

#include <stdio.h>

struct num //定义一个结点
{
    int data;
    struct num *nextPtr;
};

//函数声明
struct num *creat();
struct num *link(int amount);
struct num *find(int rank, int config);
int myscanf(int *amount);
int findmax(int amount);
int findmin(int amount);
long long sum(int amount);

//定义指向第一个结点的指针
struct num *headPtr = NULL;

int main()
{
    struct num *pre = creat();                                                                                //创造一个空结点，以便查找
    headPtr = pre;                                                                                            //指针指向第一个结点
    int amount = 0;                                                                                           //定义结点的数量并初始化
    myscanf(&amount);                                                                                         //扫描输入数值并保存
    printf("The maximum,minmum and the total are:%d %d %lld", findmax(amount), findmin(amount), sum(amount)); //输出题目所求
    return 0;
}

struct num *creat() //创造一个结点
{
    struct num *new = (struct num *)malloc(sizeof(struct num)); //动态分配一个内存
    new->nextPtr = NULL;                                        //初始化新结点的参数
    return new;                                                 //返回新结点的指针
}

struct num *link(int amount) //连接结点
{
    struct num *tmp = creat();      //创造一个结点
    find(amount, 1)->nextPtr = tmp; //找到最后一个结点，连接新结点
    return tmp;                     //返回新结点指针
}

struct num *find(int rank, int config) //查找链表的第n个，其中config==1:return pre; config==2:return cur，该题用途不大，但以后可能有用
{
    int place = 0;                                   //初始化位置
    struct num *curPtr = headPtr->nextPtr;           //创造指针指向除空结点外的第一个结点
    struct num *prePtr = headPtr;                    //创造指针指向空结点
    for (place = 0; place < rank && curPtr; place++) //沿着链表查找
    {
        prePtr = curPtr;
        curPtr = curPtr->nextPtr;
    }
    if (config == 1) //返回第n个结点的指针
    {
        return prePtr;
    }
    else
    {
        return curPtr;
    }
}

int myscanf(int *amount) //扫描数据并储存
{
    int tmp; //定义一个整数储存输入
    scanf("%d", &tmp);
    while (tmp != -1) //如果输入不为-1，新增结点，储存数据并继续扫描
    {
        link(*amount)->data = tmp; //新增结点
        (*amount)++;               //改变节点数
        scanf("%d", &tmp);         //扫描下一个数据
    }
}

int findmax(int amount) //查找最大值
{
    int place = 0;
    int max = -1;
    for (place = 1; place <= amount; place++)
    {
        int tmp = find(place, 1)->data;
        if (tmp > max || max == -1)
        {
            max = tmp;
        }
    }
    return max;
}

int findmin(int amount) //查找最小值
{
    int place = 0;
    int min = -1;
    for (place = 1; place <= amount; place++)
    {
        int tmp = find(place, 1)->data;
        if (tmp < min || min == -1)
        {
            min = tmp;
        }
    }
    return min;
}

long long sum(int amount) //计算总和
{
    int place = 0;
    int sum = 0;
    for (place = 1; place <= amount; place++)
    {
        sum += find(place, 1)->data;
    }
    return sum;
}

问题 B: 实验11_10_链表排序

时间限制: 1 Sec  内存限制: 128 MB

题目描述

已知一个正整数组成的无序序列，个数未知，但至少有一个元素，你的任务是建立一个单链表，并使用该链表存储这个正整数序列，然后将这个链表进行排序，使得排序后的链表为递增序列。正整数的输入用-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

示例代码

/*
 * Copyright (C) Jray
 * 
 * 2020.03.01
 */

#include <stdlib.h>
#include <stdio.h>

struct num //定义一个结点
{
    int data;
    struct num *nextPtr;
};

//函数声明
struct num *creat();
struct num *link(int amount);
struct num *find(int rank, int config);
int myscanf(int *amount);
int myswap(int a, int b);
int mysort(int amount);
int myprint(int amount);
int findMin(int startLoc, int endLoc);

//定义指向第一个结点的指针
struct num *headPtr = NULL;

int main()
{
    struct num *pre = creat(); //创造一个空结点，以便查找
    headPtr = pre;             //指针指向第一个结点
    int amount = 0;            //定义结点的数量并初始化
    myscanf(&amount);          //扫描输入数值并保存
    mysort(amount);
    myprint(amount);
    return 0;
}


int mysort(int amount)
{
    int i;
    for (i = 0; i < amount - 1; i++)
    {
        int min = findMin(i, amount);
        myswap(i, min);
    }
    return 0;
}

int findMin(int startLoc, int endLoc)
{
    int i, xiabiao = startLoc;
    int min = find(startLoc, 2)->data;
    for (i = startLoc; i < endLoc; i++)
    {
        if (find(i, 2)->data < min)
        {
            min = find(i, 2)->data;
            xiabiao = i;
        }
    }
    return xiabiao;
}

int myfree(int amount)
{
    int i;
    for (i = amount; i > 0; i++)
    {
        free(find(i, 2));
    }
    free(headPtr->nextPtr);
    free(headPtr);
}

int myprint(int amount)
{
    int i;
    printf("The new list is:");
    for (i = 0; i < amount; i++)
    {
        printf("%d ", find(i, 2)->data);
    }
}

struct num *creat() //创造一个结点
{
    struct num *new = (struct num *)malloc(sizeof(struct num)); //动态分配一个内存
    new->nextPtr = NULL;                                        //初始化新结点的参数
    return new;                                                 //返回新结点的指针
}

struct num *link(int amount) //连接结点
{
    struct num *tmp = creat();      //创造一个结点
    find(amount, 1)->nextPtr = tmp; //找到最后一个结点，连接新结点
    return tmp;                     //返回新结点指针
}

struct num *find(int rank, int config) //查找链表的第n个，其中config==1:return pre; config==2:return cur，该题用途不大，但以后可能有用
{
    int place = 0;                                   //初始化位置
    struct num *curPtr = headPtr->nextPtr;           //创造指针指向除空结点外的第一个结点
    struct num *prePtr = headPtr;                    //创造指针指向空结点
    for (place = 0; place < rank && curPtr; place++) //沿着链表查找
    {
        prePtr = curPtr;
        curPtr = curPtr->nextPtr;
    }
    if (config == 1) //返回第n个结点的指针
    {
        return prePtr;
    }
    else
    {
        return curPtr;
    }
}

int myscanf(int *amount) //扫描数据并储存
{
    int tmp; //定义一个整数储存输入
    scanf("%d", &tmp);
    while (tmp != -1) //如果输入不为-1，新增结点，储存数据并继续扫描
    {
        link(*amount)->data = tmp; //新增结点
        (*amount)++;               //改变节点数
        scanf("%d", &tmp);         //扫描下一个数据
    }
}

int myswap(int a, int b)
{
    struct num *acur = find(a, 2);
    struct num *apre = find(a, 1);
    struct num *bcur = find(b, 2);
    struct num *bpre = find(b, 1);
    struct num *tmp1 = apre->nextPtr;
    struct num *tmp2 = acur->nextPtr;
    if (tmp2 == bcur)
    {
        tmp2 = acur;
    }
    apre->nextPtr = bpre->nextPtr;
    bpre->nextPtr = tmp1;
    acur->nextPtr = bcur->nextPtr;
    bcur->nextPtr = tmp2;
    return 0;
}

问题 C: 实验11_11_链表匹配

时间限制: 1 Sec  内存限制: 128 MB

题目描述

已知两个由正整数组成的无序序列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.

示例代码

/*
 * Copyright (C) Jray
 * 
 * 2020.03.01
 */

#include <stdlib.h>
#include <stdio.h>

struct num //定义一个结点
{
    int data;
    struct num *nextPtr;
};

//函数声明
struct num *creat();
struct num *link(int amount);
struct num *find(int rank, int config);
int myscanf(int *amount);
int myswap(int a, int b);
int myprint(int amount);
struct num *creat2();
struct num *link2(int amount);
struct num *find2(int rank, int config);
int myscanf2(int *amount);
int myswap2(int a, int b);
int myprint2(int amount);
int check(int amount1, int amount2);

//定义指向第一个结点的指针
struct num *headPtr1 = NULL;
struct num *headPtr2 = NULL;

int main()
{
    struct num *pre = creat(); //创造一个空结点，以便查找
    headPtr1 = pre;            //指针指向第一个结点
    int amount1 = 0;           //定义结点的数量并初始化
    myscanf(&amount1);         //扫描输入数值并保存

    struct num *pre2 = creat2(); //创造一个空结点，以便查找
    headPtr2 = pre2;             //指针指向第一个结点
    int amount2 = 0;             //定义结点的数量并初始化
    myscanf2(&amount2);          //扫描输入数值并保存
    if (check(amount1, amount2))
    {
        printf("ListB is the sub sequence of ListA.");
    }
    else
    {
        printf("ListB is not the sub sequence of ListA.");
    }
    return 0;
}

int check(int amount1, int amount2)
{
    int i, j;
    int flag = 0;
    for (i = 0; i < amount1 && !flag; i++)
    {
        flag = 1;
        for (j = 0; j < amount2 && flag; j++)
        {
            if (i >= amount1 - j)
            {
                flag = 0;
            }
            else
            {
                int a = find(i + j, 2)->data;
                int b = find2(j, 2)->data;
                if (a != b)
                {
                    flag = 0;
                }
            }
        }
    }
    return flag;
}

int myfree(int amount)
{
    int i;
    for (i = amount; i > 0; i++)
    {
        free(find(i, 2));
    }
    free(headPtr1->nextPtr);
    free(headPtr1);
}

int myprint(int amount)
{
    int i;
    printf("The new list is:");
    for (i = 0; i < amount; i++)
    {
        printf("%d ", find(i, 2)->data);
    }
}

struct num *creat() //创造一个结点
{
    struct num *new = (struct num *)malloc(sizeof(struct num)); //动态分配一个内存
    new->nextPtr = NULL;                                        //初始化新结点的参数
    return new;                                                 //返回新结点的指针
}

struct num *link(int amount) //连接结点
{
    struct num *tmp = creat();      //创造一个结点
    find(amount, 1)->nextPtr = tmp; //找到最后一个结点，连接新结点
    return tmp;                     //返回新结点指针
}

struct num *find(int rank, int config) //查找链表的第n个，其中config==1:return pre; config==2:return cur，该题用途不大，但以后可能有用
{
    int place = 0;                                   //初始化位置
    struct num *curPtr = headPtr1->nextPtr;          //创造指针指向除空结点外的第一个结点
    struct num *prePtr = headPtr1;                   //创造指针指向空结点
    for (place = 0; place < rank && curPtr; place++) //沿着链表查找
    {
        prePtr = curPtr;
        curPtr = curPtr->nextPtr;
    }
    if (config == 1) //返回第n个结点的指针
    {
        return prePtr;
    }
    else
    {
        return curPtr;
    }
}

int myscanf(int *amount) //扫描数据并储存
{
    int tmp; //定义一个整数储存输入
    scanf("%d", &tmp);
    while (tmp != -1) //如果输入不为-1，新增结点，储存数据并继续扫描
    {
        link(*amount)->data = tmp; //新增结点
        (*amount)++;               //改变节点数
        scanf("%d", &tmp);         //扫描下一个数据
    }
}

int myswap(int a, int b)
{
    struct num *acur = find(a, 2);
    struct num *apre = find(a, 1);
    struct num *bcur = find(b, 2);
    struct num *bpre = find(b, 1);
    struct num *tmp1 = apre->nextPtr;
    struct num *tmp2 = acur->nextPtr;
    if (tmp2 == bcur)
    {
        tmp2 = acur;
    }
    apre->nextPtr = bpre->nextPtr;
    bpre->nextPtr = tmp1;
    acur->nextPtr = bcur->nextPtr;
    bcur->nextPtr = tmp2;
    return 0;
}

int myfree2(int amount)
{
    int i;
    for (i = amount; i > 0; i++)
    {
        free(find(i, 2));
    }
    free(headPtr2->nextPtr);
    free(headPtr2);
}

int myprint2(int amount)
{
    int i;
    printf("The new list is:");
    for (i = 0; i < amount; i++)
    {
        printf("%d ", find(i, 2)->data);
    }
}

struct num *creat2() //创造一个结点
{
    struct num *new = (struct num *)malloc(sizeof(struct num)); //动态分配一个内存
    new->nextPtr = NULL;                                        //初始化新结点的参数
    return new;                                                 //返回新结点的指针
}

struct num *link2(int amount) //连接结点
{
    struct num *tmp = creat();       //创造一个结点
    find2(amount, 1)->nextPtr = tmp; //找到最后一个结点，连接新结点
    return tmp;                      //返回新结点指针
}

struct num *find2(int rank, int config) //查找链表的第n个，其中config==1:return pre; config==2:return cur，该题用途不大，但以后可能有用
{
    int place = 0;                                   //初始化位置
    struct num *curPtr = headPtr2->nextPtr;          //创造指针指向除空结点外的第一个结点
    struct num *prePtr = headPtr2;                   //创造指针指向空结点
    for (place = 0; place < rank && curPtr; place++) //沿着链表查找
    {
        prePtr = curPtr;
        curPtr = curPtr->nextPtr;
    }
    if (config == 1) //返回第n个结点的指针
    {
        return prePtr;
    }
    else
    {
        return curPtr;
    }
}

int myscanf2(int *amount) //扫描数据并储存
{
    int tmp; //定义一个整数储存输入
    scanf("%d", &tmp);
    while (tmp != -1) //如果输入不为-1，新增结点，储存数据并继续扫描
    {
        link2(*amount)->data = tmp; //新增结点
        (*amount)++;                //改变节点数
        scanf("%d", &tmp);          //扫描下一个数据
    }
}

int myswap2(int a, int b)
{
    struct num *acur = find2(a, 2);
    struct num *apre = find2(a, 1);
    struct num *bcur = find2(b, 2);
    struct num *bpre = find2(b, 1);
    struct num *tmp1 = apre->nextPtr;
    struct num *tmp2 = acur->nextPtr;
    if (tmp2 == bcur)
    {
        tmp2 = acur;
    }
    apre->nextPtr = bpre->nextPtr;
    bpre->nextPtr = tmp1;
    acur->nextPtr = bcur->nextPtr;
    bcur->nextPtr = tmp2;
    return 0;
}

问题 D: 实验11_13_链表交换

时间限制: 1 Sec  内存限制: 128 MB

题目描述

已知一个正整数序列，序列元素个数未知，但至少有两个元素，你的任务是建立一个单链表用于存储这个正整数序列。然后实现交换此链表中任意指定的两段，第一段为[s1,t1]，第二段[s2,t2]。s1、t1、s2、t2代表链表的第几个节点，且满足s1<=t1，s2<=t2，t1<s2，s2一定小于等于链表节点的总个数。正整数的输入用-1作为结束标志，注意-1不算这个正整数序列中的元素（不要统计-1）。最后将链表的全部节点释放。

输入

输入一个正整数序列，以输入“-1”结束，序列中元素个数未知，但输入“-1”前至少输入两个正整数。然后是四个整数，即为s1、t1、s2、t2。

输出

经过处理后的新链表，每个元素后有一个空格，注意最后一个元素后只有换行符。
数据最多的测试用例节点数在100这个数量级，所有整数可以用int型存储。
请注意输入输出格式。

样例输入

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

样例输出

The new list is:4 5 6 7 2 3 1 8 9 10

示例代码

/*
 * Copyright (C) Jray
 * 
 * 2020.03.01
 */

#include <stdlib.h>
#include <stdio.h>

struct num //定义一个结点
{
    int data;
    struct num *nextPtr;
};

//函数声明
struct num *creat();
struct num *link(int amount);
struct num *find(int rank, int config);
int myscanf(int *amount);
int myswap(int a, int b, int c, int d);
int myprint(int amount);

//定义指向第一个结点的指针
struct num *headPtr = NULL;

int main()
{
    struct num *pre = creat(); //创造一个空结点，以便查找
    headPtr = pre;             //指针指向第一个结点
    int amount = 0;            //定义结点的数量并初始化
    myscanf(&amount);          //扫描输入数值并保存
    int a, b, c, d;
    scanf("%d %d %d %d", &a, &b, &c, &d);
    myswap(a - 1, b - 1, c - 1, d - 1);
    myprint(amount);
    return 0;
}

int myfree(int amount)
{
    int i;
    for (i = amount; i > 0; i++)
    {
        free(find(i, 2));
    }
    free(headPtr->nextPtr);
    free(headPtr);
}

int myprint(int amount)
{
    int i;
    printf("The new list is:");
    for (i = 0; i < amount; i++)
    {
        printf("%d ", find(i, 2)->data);
    }
}

struct num *creat() //创造一个结点
{
    struct num *new = (struct num *)malloc(sizeof(struct num)); //动态分配一个内存
    new->nextPtr = NULL;                                        //初始化新结点的参数
    return new;                                                 //返回新结点的指针
}

struct num *link(int amount) //连接结点
{
    struct num *tmp = creat();      //创造一个结点
    find(amount, 1)->nextPtr = tmp; //找到最后一个结点，连接新结点
    return tmp;                     //返回新结点指针
}

struct num *find(int rank, int config) //查找链表的第n个，其中config==1:return pre; config==2:return cur，该题用途不大，但以后可能有用
{
    int place = 0;                                   //初始化位置
    struct num *curPtr = headPtr->nextPtr;           //创造指针指向除空结点外的第一个结点
    struct num *prePtr = headPtr;                    //创造指针指向空结点
    for (place = 0; place < rank && curPtr; place++) //沿着链表查找
    {
        prePtr = curPtr;
        curPtr = curPtr->nextPtr;
    }
    if (config == 1) //返回第n个结点的指针
    {
        return prePtr;
    }
    else
    {
        return curPtr;
    }
}

int myscanf(int *amount) //扫描数据并储存
{
    int tmp; //定义一个整数储存输入
    scanf("%d", &tmp);
    while (tmp != -1) //如果输入不为-1，新增结点，储存数据并继续扫描
    {
        link(*amount)->data = tmp; //新增结点
        (*amount)++;               //改变节点数
        scanf("%d", &tmp);         //扫描下一个数据
    }
}

int myswap(int a, int b, int c, int d)
{
    struct num *apre = find(a, 1);
    struct num *acur = find(a, 2);
    struct num *bcur = find(b, 2);
    struct num *cpre = find(c, 1);
    struct num *ccur = find(c, 2);
    struct num *dcur = find(d, 2);
    struct num *tmp1 = bcur->nextPtr;
    apre->nextPtr = ccur;
    bcur->nextPtr = dcur->nextPtr;
    if (cpre == bcur)
    {
        dcur->nextPtr = acur;
    }
    else
    {
        dcur->nextPtr = tmp1;
        cpre->nextPtr = acur;
    }

    return 0;
}
分类： OJ代码
标签：

相关文章

OJ代码

北邮计算机学院2020年大一CPU模拟大作业示例（多核版）

由于多线程的原因，每一次的运行结果都快可能不同，所以只需逻辑正确即可， 阅读更多…

OJ代码

北邮计算机学院2020年大一CPU模拟大作业示例（单核版）

多核版示例及输出已更新 https://www.jray.xyz/in 阅读更多…

OJ代码

计导课设_链表练习2

实验11_9_链表归并 时间限制: 1 Sec  内存限制: 128 阅读更多…