计导课设_链表练习2

于由Jray发布

实验11_9_链表归并

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

题目描述

已知有两个递增的正整数序列A和B，序列中元素个数未知，同一序列中不会有重复元素出现，有可能某个序列为空。现要求将序列B归并到序列A中，且归并后序列A的数据仍然按递增顺序排列。如果序列B中某些数据在序列A中也存在，则这些数据所在节点仍然留在序列B中，而不被归并到序列A中；否则这些数据所在节点将从序列B中删除，添加到序列A中。
要求：
建立两个单链表A、B用于存储两个正整数序列，然后按照题目的要求，将链表B中的元素归并到链表A中。在归并的过程中，不要释放B中的节点空间、然后建立新节点，而要改变指针的指向，使元素从B中删除并添加到A中。正整数序列按照递增顺序输入，用-1作为结束标志，注意-1不算这个正整数序列中的元素（不要统计-1）。在程序结束前要释放链表A、B中的所有节点。

输入

依次输入两个递增的正整数序列A和B，序列元素的个数未知，但以输入“-1”结束，每个正整数序列占一行。

输出

处理后的链表A中的元素，占一行；然后是处理后的链表B中的元素，占一行。每行的每个元素后有一个空格，注意最后一个元素后只有换行符，如果某个链表为空则，则输出“There is no item in X list.”
数据最多的测试用例节点数在100这个数量级，所有整数可以用int型存储。
请注意输入输出格式。

样例输入

Sample 1:
1 3 4 5 6 7 -1
2 3 6 8 9 10 11-1

Sample 2:
-1
-1

样例输出

Sample 1:
The new list A:1 2 3 4 5 6 7 8 9 10 11
The new list B:3 6

Sample 2:
There is no item in A list.
There is no item in B list.

示例代码

/*
 * Copyright (C) Jray
 * 
 * 2020.03.10
 */
 
#include <stdio.h>
#include <stdlib.h>
 
typedef struct listnode
{
    int data;
    struct listnode *next;
} LISTNODE;
 
int myfree();
int init();
LISTNODE *creat();
int myscanf(LISTNODE *nowheadPtr);
int myprint(int list);
LISTNODE *find(int place, LISTNODE *nowheadPtr, int config);
int insert(int listtoinsert, int inpreplace, int outplace);
int merge();
LISTNODE *headPtr[2]; //创造一个长度为2的headPtr的指针数组
 
int main(void)
{
    init();
    myscanf(headPtr[0]);
    myscanf(headPtr[1]);
    merge();
    myprint(0);
    myprint(1);
    myfree();
    //system("pause");
    return 0;
}
 
int myfree()
{
    LISTNODE *acur = headPtr[0];
    LISTNODE *bcur = headPtr[1];
    LISTNODE *tmp;
    while (acur)
    {
        tmp = acur;
        acur = acur->next;
        free(tmp);
    }
    while (bcur)
    {
        tmp = bcur;
        bcur = bcur->next;
        free(tmp);
    }
}
 
int init() //初始化头节点和空结点
{
    int i;
    for (i = 0; i < 2; i++) //循环处理两个链表的头节点
    {
        headPtr[i] = creat(); //初始化空结点
    }
}
 
LISTNODE *creat() //创造一个结点
{
    LISTNODE *pre = (LISTNODE *)malloc(sizeof(LISTNODE *)); //为pre分配内存
    pre->data = 0;                                          //使pre初值为0
    pre->next = NULL;                                       //使pre指向NULL
    return pre;                                             //返回pre的地址
}
 
int myscanf(LISTNODE *nowheadPtr) //扫描创建链表
{
    int data;
    LISTNODE *curPtr = nowheadPtr;
    scanf("%d", &data);
    while (data != -1)
    {
        curPtr->next = creat();
        curPtr = curPtr->next;
        curPtr->data = data;
        scanf("%d", &data);
    }
    return 0;
}
 
int myprint(int list)
{
    LISTNODE *curPtr = headPtr[list]->next;
    if (curPtr)
    {
        if (list == 0)
        {
            printf("The new list A:");
        }
        else
        {
            printf("The new list B:");
        }
    }
    else
    {
        if (list == 0)
        {
            printf("There is no item in A list.");
        }
        else
        {
            printf("There is no item in B list.");
        }
    }
    while (curPtr)
    {
        printf("%d ", curPtr->data);
        curPtr = curPtr->next;
    }
    printf("\n");
    return 0;
}
 
LISTNODE *find(int place, LISTNODE *nowheadPtr, int config)
{
    int i;
    LISTNODE *prePtr = nowheadPtr;
    LISTNODE *curPtr = prePtr->next;
    for (i = 0; i < place && curPtr; i++)
    {
        prePtr = curPtr;
        curPtr = curPtr->next;
    }
    if (place == -1)
    {
        curPtr = nowheadPtr;
        prePtr = NULL;
    }
    if (config == 0)
    {
        return prePtr;
    }
    else
    {
        return curPtr;
    }
}
 
int myswap(int list, int a, int b, int c, int d)
{
    LISTNODE *apre = find(a, headPtr[list], 0);
    LISTNODE *acur = find(a, headPtr[list], 1);
    LISTNODE *bcur = find(b, headPtr[list], 1);
    LISTNODE *cpre = find(c, headPtr[list], 0);
    LISTNODE *ccur = find(c, headPtr[list], 1);
    LISTNODE *dcur = find(d, headPtr[list], 1);
    LISTNODE *tmp1 = bcur->next;
    apre->next = ccur;
    bcur->next = dcur->next;
    if (cpre == bcur)
    {
        dcur->next = acur;
    }
    else
    {
        dcur->next = tmp1;
        cpre->next = acur;
    }
    return 0;
}
 
int insert(int listtoinsert, int inpreplace, int outplace)
{
    LISTNODE *preout = find(outplace, headPtr[abs(1 - listtoinsert)], 0);
    LISTNODE *out = preout->next;
    preout->next = out->next;
    LISTNODE *pre = find(inpreplace, headPtr[listtoinsert], 1);
    out->next = pre->next;
    pre->next = out;
    return 0;
}
 
int merge()
{
    int i, j;
    LISTNODE *b;
    LISTNODE *a;
    b = find(0, headPtr[1], 1);
    for (j = 0; b; j++, b = find(j, headPtr[1], 1))
    {
        int flag = 1;
        a = find(0, headPtr[0], 1);
        for (i = 0; a && a->data <= b->data; i++, a = find(i, headPtr[0], 1))
        {
            if (a->data == b->data)
            {
                flag = 0;
            }
             
        }
        if (flag)
        {
            insert(0, i - 1, j);
            j--;
        }
    }
}

实验11_15_拆分链表

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

题目描述

已知有一个乱序的字符序列L，序列中的字符可能是英文字母、数字字符或其它字符，字符的个数未知，每个字符之间用空格分开。字符序列用“-1”作为输入结束标志，这里你要把-1当做一个字符串对待，并且不算作字符序列中的元素。如下即为一个合法的字符序列：“a c 3 b a d 6 , & j m 8 7 2 V -1”。你的任务是将这个字符序列拆分为三个独立的序列A、B和C，其中序列A存放序列L中的字母，序列B存放序列L中的数字，序列C存放序列L中的其他字符，然后，将序列A、B和C分别按照ASCII码的大小关系进行升序排序。最终序列L将变为空序列。
要求：
建立四个单链表，分别存储序列L、A、B、C中的元素。字符序列的输入用“-1”作为结束标志。建立链表L时，建议使用scanf(“%s”,s);来读取字符序列中的字符，即把单独的字符看做一个字符串读取。当L建立后，你要按照问题描述中所述，将L拆分为A、B、C三个链表，然后对每个链表都进行排序，这部分的操作都应该是对指针进行修改，而不是删除节点与建立新节点。在程序结束前要释放链表A、B、C中的所有节点。

输入

一个乱序的字符序列，序列元素的个数未知，以输入“-1”结束，输入“-1”前可能没有其它元素，每个字符序列占一行。

输出

链表A中的元素，占一行；然后是链表B中的元素，占一行。最后是链表C中的元素，占一行。每行的每个元素后有一个空格，注意最后一个元素后只有换行符，如果某个链表为空则，则输出“There is no item in X list.”
数据最多的测试用例节点数在100这个数量级。
请注意输入输出格式。

样例输入

Sample 1:
a c 3 b a d 6 , & j m 8 7 2 V -1

Sample 2:
z m v 1 a K 2 m p 9 a 0 a d -1

样例输出

Sample 1:
The list A is: V a a b c d j m
The list B is: 2 3 6 7 8
The list C is: & ,

Sample 2:
The list A is: K a a a d m m p v z
The list B is: 0 1 2 9
There is no item in C list.

示例代码

/*
 * Copyright (C) Jray
 * 
 * 2020.03.11
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct listnode
{
    char data[5];
    struct listnode *next;
} LISTNODE;
 
int init(int num);
LISTNODE *creat();
int myscanf(int list);
int myprintf(int list);
LISTNODE *find(int list, int place, int config);
int split();
int merge(int in_list, int out_list, int out_place);
int myfree();
 
LISTNODE *headPtr[4];
 
int main()
{
    init(4);
    myscanf(0);
    split();
    myprintf(1);
    myprintf(2);
    myprintf(3);
    myfree();
    //system("pause");
    return 0;
}
 
int myfree()
{
    LISTNODE *tmp1, *tmp2;
    int i;
    for (i = 0; i < 4; i++)
    {
        tmp1 = headPtr[i];
        while (tmp1)
        {
            tmp2 = tmp1;
            tmp1 = tmp1->next;
            free(tmp2);
        }
    }
    return 0;
}
 
int init(int num)
{
    int i;
    for (i = 0; i < num; i++)
    {
        headPtr[i] = creat();
    }
    return 0;
}
 
LISTNODE *creat()
{
    LISTNODE *pre = (LISTNODE *)malloc(sizeof(LISTNODE *));
    pre->next = NULL;
    return pre;
}
 
int myscanf(int list)
{
    LISTNODE *nowPtr = headPtr[list];
    char data[5];
    scanf("%s", data);
    while (strcmp(data, "-1"))
    {
        nowPtr->next = creat();
        nowPtr = nowPtr->next;
        strcpy(nowPtr->data, data);
        scanf("%s", data);
    }
    return 0;
}
 
int myprintf(int list)
{
    char listname;
    switch (list)
    {
    case 1:
        listname = 'A';
        break;
    case 2:
        listname = 'B';
        break;
    case 3:
        listname = 'C';
        break;
    default:
        break;
    }
    if (headPtr[list]->next)
    {
        printf("The list %c is:", listname);
        LISTNODE *nowPtr = headPtr[list]->next;
        while (nowPtr)
        {
            printf(" %s", nowPtr->data);
            nowPtr = nowPtr->next;
        }
    }
    else
    {
        printf("There is no item in %c list.", listname);
    }
    printf("\n");
    return 0;
}
 
LISTNODE *find(int list, int place, int config)
{
    int i;
    LISTNODE *curPtr = headPtr[list]->next;
    LISTNODE *prePtr = headPtr[list];
    for (i = 0; i < place && curPtr; i++)
    {
        prePtr = curPtr;
        curPtr = curPtr->next;
    }
    switch (config)
    {
    case 0:
        return prePtr;
 
    case 1:
        return curPtr;
    }
}
 
int split()
{
    LISTNODE *nowPtr = headPtr[0]->next;
    while (nowPtr)
    {
        if ((nowPtr->data[0] >= 'a' && nowPtr->data[0] <= 'z') || (nowPtr->data[0] >= 'A' && nowPtr->data[0] <= 'Z'))
        {
            merge(1, 0, 0);
        }
        else if(nowPtr->data[0] >= '0' && nowPtr->data[0] <= '9')
        {
            merge(2, 0, 0);
        }
        else
        {
            merge(3, 0, 0);
        }
        nowPtr = headPtr[0]->next;
    }
}
 
int merge(int in_list, int out_list, int out_place)
{
    LISTNODE *curPtr = headPtr[in_list]->next;
    LISTNODE *prePtr = headPtr[in_list];
    int data = find(out_list, out_place, 1)->data[0];
    int conti = 1;
    while (curPtr && conti)
    {
        if (curPtr->data[0] < data)
        {
            prePtr = curPtr;
            curPtr = curPtr->next;
        }
        else
        {
            conti = 0;
        }
    }
    LISTNODE *outPtr = find(out_list, out_place, 1);
    find(out_list, out_place, 0)->next = outPtr->next;
    outPtr->next = prePtr->next;
    prePtr->next = outPtr;
    return 0;
}
分类： OJ代码
标签：

相关文章

OJ代码

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

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

OJ代码

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

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

OJ代码

计导课设_链表练习1

大家可以到我的oj平台进行测试，账户可以自行注册 http://oj. 阅读更多…