北京邮电大学计算机学院大一下计导课链表作业——链表排序、匹配、交换、归并、拆分

写给后来者

亲爱的北京邮电大学计算机学院的学妹/学弟们：

​ 如果你看到了这篇博客，很有可能的是你在做大一下学期的第一次计算机导论作业。

没错，以我对学院这个破OJ的了解，这份作业还会存在很多年，祸害造福一代又一代的北邮人。

你们中的大部分人也许会和我们中的大部分人一样，苦恼地来csdn上搜索可用的C代码，于是我特地大慈大悲地贡献出我的代码，留待一年或数年后的诸君发掘。

​                                          AryCra_07

免责声明：该项作业会记入最后考核成绩中，因此禁止一切形式的抄袭行为。

博主享有本代码的所有著作权，欢迎你采纳我的思路并改写我的烂代码。

代码如下：

//A
#include 
#include 
#include 

int n, Array[10100];

struct node{ //链表结点
    int data;
    struct node *next;
    int min , max , total;
};

//创建链表（关键函数）
struct node *create(int Array[], int n) {
    struct node *p, *pre, *head; //pre保存当前结点的前驱结点，head是头结点
    head = (struct node *) malloc(sizeof(struct node)); //创建头结点
    head->next = NULL; //头结点不需要数据域，指针域初始为NULL
    head->min = 0x3f3f3f3f;
    head->max = -1;
    head->total = 0;
    pre = head; //记录pre为head
    for (int i = 0; i < n; ++i) {
        p = (struct node *) malloc(sizeof(struct node)); //新建结点
        //将Array[i]赋给新建的结点作为数据域，也可以scanf输入
        p->data = Array[i];
        p->next = NULL; //新结点的指针域设为NULL
        p->max = p->data > pre->max ? p->data : pre->max;
        p->min = p->data < pre->min ? p->data : pre->min;
        p->total = p->data + pre->total;
        pre->next = p; //前驱结点的指针域设为当前结点的地址
        pre = p; //把当前结点赋值给pre，作为下一个结点的前驱结点
    }
    head->max = pre->max;
    head->min = pre->min;
    head->total = pre->total;
    return head; //返回头结点指针
}

int main() {
    int x = 0, i = 0;
    while (1) {
        scanf("%d", &x);
        if (x == -1)
            break;
        Array[i++] = x;
    }
    struct node *L = create(Array, i); //L是头结点

    printf("The maximum,minmum and the total are:%d %d %d ", L->max, L->min, L->total);


    return 0;
}


//B
#include
#include

typedef struct node {
    int data;
    struct node *next;
    int cnt;
} Node;

Node *create() {
    Node *head, *cur, *last, *emptyHead = NULL;
    int x = 0, y = 0;
    emptyHead = (Node *) malloc(sizeof(Node));
    head = (Node *) malloc(sizeof(Node));
    emptyHead->data = 0;
    emptyHead->cnt = 0;
    emptyHead->next = head;
    scanf("%d", &x);
    head->data = x;
    last = head;
    while (~scanf("%d", &x)) {
        if (x == -1) {
            break;
        }
        cur = (Node *) malloc(sizeof(Node));
        cur->data = x;
        cur->next = NULL;
        cur->cnt = last->cnt + 1;
        last->next = cur;
        last = cur;
    }
    last->next = NULL;
    emptyHead->cnt = last->cnt;

    return emptyHead;
}

void print(Node *head) {
    int i = 0, j = 0, k = 0;
    Node *p = head;
    printf("The new list is:");
    while (p->next != NULL) {
        printf("%d ", p->next->data);
        p = p->next;
    }
}

void sort(Node *head) {
    Node *cur = NULL, *pre = NULL, *last = NULL, *temp = NULL;
    while (last != head->next) {
        temp = head;
        cur = head->next->next;
        pre = head->next;
        while (pre->next != last) {
            if (pre->data > cur->data) {
                pre->next = cur->next;
                temp->next = cur;
                cur->next = pre;
            } else {
                pre = pre->next;
            }
            cur = pre->next;
            temp = temp->next;
        }
        last = pre;
    }
}

int main() {
    Node *head = create();
    sort(head);
    print(head);
    return 0;
}

//C
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

int n, Array[10100];

typedef struct node{ //链表结点
    int data;
    struct node *next;
    int min , max , total;
}Node;

//创建链表（关键函数）
struct node *create(int Array[], int n) {
    struct node *p, *pre, *head; //pre保存当前结点的前驱结点，head是头结点
    head = (struct node *) malloc(sizeof(struct node)); //创建头结点
    head->next = NULL; //头结点不需要数据域，指针域初始为NULL
    head->min = 0x3f3f3f3f;
    head->max = -1;
    head->total = 0;
    pre = head; //记录pre为head
    for (int i = 0; i < n; ++i) {
        p = (struct node *) malloc(sizeof(struct node)); //新建结点
        //将Array[i]赋给新建的结点作为数据域，也可以scanf输入
        p->data = Array[i];
        p->next = NULL; //新结点的指针域设为NULL
        p->max = p->data > pre->max ? p->data : pre->max;
        p->min = p->data < pre->min ? p->data : pre->min;
        p->total = p->data + pre->total;
        pre->next = p; //前驱结点的指针域设为当前结点的地址
        pre = p; //把当前结点赋值给pre，作为下一个结点的前驱结点
    }
    head->max = pre->max;
    head->min = pre->min;
    head->total = pre->total;
    return head; //返回头结点指针
}
void jg(Node *first, Node *second) {
    Node *nowA = first->next, *nowB = second->next, *hereA = first->next;
    while (hereA!=NULL && nowB != NULL) {
        if(hereA->data == nowB->data) {
            hereA = hereA->next;
            nowB = nowB->next;
        } else{
            nowA = nowA->next;
            hereA = nowA;
            nowB = second->next;
        }
    }
    if(nowB == NULL) {
        printf("ListB is the sub sequence of ListA.");
    } else{
        printf("ListB is not the sub sequence of ListA.");
    }
}

void Del(Node *A) {
    Node* start = NULL, *end = A;
    while (end->next != NULL) {
        start = end;
        end =end->next;
        free(start);
    }
}
void bubbleSort(int a[], int n){
    for(int i = 0; i < n-1; ++i)  //遍历n-1次
        for(int j = 0; j < n-i-1; ++j)  //j小于的就是越来越小的递归边界，不过为什么是n-i-1而不是n-i呢
            if(a[j]>a[j+1]){
                int tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;  //如果你熟悉c++，可以调用swap函数来交换数字。


            }
}

int main() {
    int x = 0, i = 0;
    while (1) {
        scanf("%d", &x);
        if (x == -1)
            break;
        Array[i++] = x;
    }
    struct node *A = create(Array, i); //L是头结点
    memset(Array, 0, sizeof Array);
    x = 0, i = 0;
    while (1) {
        scanf("%d", &x);
        if (x == -1)
            break;
        Array[i++] = x;
    }
    struct node *B = create(Array, i);
    jg(A, B);
    Del(A);
    Del(B);
    return 0;
}

//D
#include "stdio.h"
#include "stdlib.h"
#include "string.h"

int n, Array[10100];

typedef struct node { //链表结点
    int data;
    struct node *next;
    int min, max, total;
} Node;

//创建链表（关键函数）
struct node *create(int Array[], int n) {
    struct node *p, *pre, *head; //pre保存当前结点的前驱结点，head是头结点
    head = (struct node *) malloc(sizeof(struct node)); //创建头结点
    head->next = NULL; //头结点不需要数据域，指针域初始为NULL
    head->min = 0x3f3f3f3f;
    head->max = -1;
    head->total = 0;
    pre = head; //记录pre为head
    for (int i = 0; i < n; ++i) {
        p = (struct node *) malloc(sizeof(struct node)); //新建结点
        //将Array[i]赋给新建的结点作为数据域，也可以scanf输入
        p->data = Array[i];
        p->next = NULL; //新结点的指针域设为NULL
        p->max = p->data > pre->max ? p->data : pre->max;
        p->min = p->data < pre->min ? p->data : pre->min;
        p->total = p->data + pre->total;
        pre->next = p; //前驱结点的指针域设为当前结点的地址
        pre = p; //把当前结点赋值给pre，作为下一个结点的前驱结点
    }
    head->max = pre->max;
    head->min = pre->min;
    head->total = pre->total;
    return head; //返回头结点指针
}

void jg(Node *first, Node *second) {
    Node *nowA = first->next, *nowB = second->next, *hereA = first->next;
    while (hereA != NULL && nowB != NULL) {
        if (hereA->data == nowB->data) {
            hereA = hereA->next;
            nowB = nowB->next;
        } else {
            nowA = nowA->next;
            hereA = nowA;
            nowB = second->next;
        }
    }
    if (nowB == NULL) {
        printf("ListB is the sub sequence of ListA.");
    } else {
        printf("ListB is not the sub sequence of ListA.");
    }
}

void Del(Node *A) {
    Node *start = NULL, *end = A;
    while (end->next != NULL) {
        start = end;
        end = end->next;
        free(start);
    }
}

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; ++i)  //遍历n-1次
        for (int j = 0; j < n - i - 1; ++j)  //j小于的就是越来越小的递归边界，不过为什么是n-i-1而不是n-i呢
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;  //如果你熟悉c++，可以调用swap函数来交换数字。


            }
}

void swapList(Node *A, int l1, int r1, int l2, int r2) {
    Node *fL = A, *fR = A, *sL = A, *sR = A;
    while (--l1)
        fL = fL->next;
    while (r1--)
        fR = fR->next;
    while (--l2)
        sL = sL->next;
    while (r2--)
        sR = sR->next;
    Node *tmp = fL->next;
    fL->next = sL->next;
    sL->next = tmp;
    Node *tmp1 = fR->next;
    fR->next = sR->next;
    sR->next = tmp1;
}

void swap(Node *A, Node *B) {
    Node *tmp;
    tmp = A;
    A = B;
    B = tmp;
}

int main() {
    int x = 0, i = 0;
    int l1, r1, l2, r2;
    while (1) {
        scanf("%d", &x);
        if (x == -1)
            break;
        Array[i++] = x;
    }
    scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
    struct node *A = create(Array, i); //L是头结点
    swapList(A, l1, r1, l2, r2);
    printf("The new list is:");
    A = A->next; //从第一个结点开始才有数据域
    while (A != NULL) {
        if (A->next != NULL)
            printf("%d ", A->data);
        else
            printf("%d\n", A->data);
        A = A->next;
    }
    return 0;
}

//E
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "ctype.h"


typedef struct node { //链表结点
    int data;
    struct node *next;
    int cnt;
} Node;

Node *create() {
    int x = 0;
    Node *p, *pre, *head; //pre保存当前结点的前驱结点，head是头结点
    head = (Node *) malloc(sizeof(Node)); //创建头结点
    head->next = NULL; //头结点不需要数据域，指针域初始为NULL
    head->cnt = 0;
    pre = head; //记录pre为head
    while (1) {
        scanf("%d", &x);
        if (x == -1) break;
        p = (Node *) malloc(sizeof(Node));; //新建结点
        //将Array[i]赋给新建的结点作为数据域，也可以scanf输入
        p->data = x;
        p->next = NULL; //新结点的指针域设为NULL
        pre->next = p; //前驱结点的指针域设为当前结点的地址
        pre = p; //把当前结点赋值给pre，作为下一个结点的前驱结点
    }
    return head; //返回头结点指针
}



void sort(Node *headA, Node *headB) {
    Node *temp = headB, *temp2 = headB, *first1 = headA->next, *first2 = headB->next, *pre1 = headA;
    while (first1 != NULL && first2 != NULL) {
        if (first2->data < first1->data) {
            temp2 = first2->next;
            pre1->next = first2;
            pre1 = first2;
            first2->next = first1;
            first2 = temp2;
        } else if (first1->data == first2->data) {
            temp->next = first2;
            temp = first2;
            first2=first2->next;
            pre1 = first1;
            first1 = first1->next;
        } else {
            pre1 = first1;
            first1 = first1->next;
        }
    }
    if (first2 != NULL) {
        pre1->next = first2;
    }
    //headB->next = NULL;
    temp->next = NULL;

}


void print(Node *A, Node *B) {
    if (A->next == NULL) {
        printf("There is no item in A list.\n");
    } else {
        printf("The new list A:");
        A = A->next;
        while (A != NULL) {
            if (A->next != NULL)
                printf("%d ", A->data);
            else
                printf("%d\n", A->data);
            A = A->next;
        }
    }

    if (B->next == NULL) {
        printf("There is no item in B list.\n");
    } else {
        printf("The new list B:");
        B = B->next;
        while (B != NULL) {
            if (B->next != NULL)
                printf("%d ", B->data);
            else
                printf("%d\n", B->data);
            B = B->next;
        }
    }
}

int main() {
    Node *A = create();
    Node *B = create();
    sort(A, B);
    print(A, B);
    return 0;
}

//F
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "ctype.h"


typedef struct node { //链表结点
    char data;
    struct node *next;
    int cnt;
} Node;

//创建链表（关键函数）
struct node *create() {
    struct node *p, *pre, *head; //pre保存当前结点的前驱结点，head是头结点
    head = (struct node *) malloc(sizeof(struct node)); //创建头结点
    head->next = NULL; //头结点不需要数据域，指针域初始为NULL
    head->cnt = 0;
    pre = head; //记录pre为head
    while (1) {
        char x[5];
        scanf(" %s", x);
        if (x[0] == '-' && x[1] == '1') {
            break;
        }
//        printf("%s I fuck you\n",x);
        p = (Node *) malloc(sizeof(Node));
        p->cnt = pre->cnt + 1;
        p->data = x[0];
        p->next = NULL;
//        printf("%c I fuck you\n",p->data);
        pre->next = p;
        pre = p;
    }
    head->cnt = p->cnt;
    return head; //返回头结点指针
}

void SortYourMother(Node *head) {
    Node *current = NULL, *previous = NULL, *last = NULL, *temp = NULL;
    if (head->next == NULL) {
        return;
    }
    while (last != head->next)//保证能正确退出循环，并且每一次都从head开始排序同时避免了成员<2的情况
    {
        temp = head;
        current = head->next->next;
        previous = head->next;
        while (previous->next != last)//这里避免了成员<3的情况
        {
            if (previous->data > current->data) {
                temp->next = current;//这一步相当于把成员一的next指向了成员三的地址
                previous->next = current->next;//这一步可以看做把成员二的next指向了三成员的next所指向的地址（成员四所在的地址）
                current->next = previous;//这把成员三的next指向了成员二所在的地址
            } else {
                previous = previous->next;//这一步没写在下面和上面是为了保证在碰到更大的数之后让pre-next连接着目前最小的数字
            }
            current = previous->next;
            temp = temp->next;
        }
        last = previous;
    }
}

void fuckYouCProgram(Node *L) {
    if (L->cnt == 0) {
        printf("There is no item in A list.");
        printf("There is no item in B list.");
        printf("There is no item in C list.");
        return;
    } else {
        Node *A, *B, *C, *preA, *pA, *preB, *pB, *preC, *pC;
        int cntA, cntB, cntC;
        A = (Node *) malloc(sizeof(Node));
        B = (Node *) malloc(sizeof(Node));
        C = (Node *) malloc(sizeof(Node));
        A->next = NULL;
        B->next = NULL;
        C->next = NULL;
        A->cnt = B->cnt = C->cnt = 0;
        preA = A;
        preB = B;
        preC = C;
        while (L->next != NULL) {
            L = L->next;
            char c = L->data;
            if (isalpha(c)) {
                pA = (Node *) malloc(sizeof(Node));
                pA->data = L->data;
                pA->cnt = preA->cnt + 1;
                pA->next = NULL;
                preA->next = pA;
                preA = pA;
            } else if (isdigit(c)) {
                pB = (Node *) malloc(sizeof(Node));
                pB->data = L->data;
                pB->cnt = preB->cnt + 1;
                pB->next = NULL;
                preB->next = pB;
                preB = pB;
            } else {
                pC = (Node *) malloc(sizeof(Node));
                pC->data = L->data;
                pC->cnt = preC->cnt + 1;
                pC->next = NULL;
                preC->next = pC;
                preC = pC;
            }
        }
        int sbA = preA->cnt;
        int sbB = preB->cnt;
        int sbC = preC->cnt;
        SortYourMother(A);
        SortYourMother(B);
        SortYourMother(C);
        if (sbA) {
            printf("The list A is: ");
            A = A->next;
            while (A != NULL) {
                if (A->next != NULL)
                    printf("%c ", A->data);
                else
                    printf("%c\n", A->data);
                A = A->next;
            }
        } else {
            printf("There is no item in A list.\n");
        }
        if (sbB) {
            printf("The list B is: ");
            B = B->next;
            while (B != NULL) {
                if (B->next != NULL)
                    printf("%c ", B->data);
                else
                    printf("%c\n", B->data);
                B = B->next;
            }
        } else {
            printf("There is no item in B list.\n");
        }
        if (sbC) {
            printf("The list C is: ");
            C = C->next;
            while (C != NULL) {
                if (C->next != NULL)
                    printf("%c ", C->data);
                else
                    printf("%c\n", C->data);
                C = C->next;
            }
        } else {
            printf("There is no item in C list.\n");
        }
    }
}


void Del(Node *A) {
    Node *start = NULL, *end = A;
    while (end->next != NULL) {
        start = end;
        end = end->next;
        free(start);
    }
}


int main() {
    Node *L = create();
    fuckYouCProgram(L);
    return 0;
}

向前，向前，向前。