HZOJ Logo WT01_4段浩杰的博客

博客

可以背诵的链表(c语言)——创建、插入、遍历、删除、反转

2021-05-03 08:22:01 By WT01_4段浩杰

前言

delete_nodereverse函数的返回值类型可以自行修改。

输入格式

第一行输入为一个正整数 m(1 ≤m≤100),代表一共有 mm 个操作。

接下来一共输入 m 行,每行首先输入一个整数 tt,代表着以下几种操作:

  • t = 1,代表执行插入操作,此时还需输入两个整数 a 和 b(0 ≤ a,b≤100),代表在位置 a 上插入值为 b 的元素,成功插入输出success,否则输出failed
  • t = 2,代表执行遍历操作,此时程序顺序输出链表的所有元素。
  • t = 3,代表执行删除操作,此时还需输入一个整数 a(0≤a≤100),表示删除位置 a 上的元素,如果成功删除则输出success,否则输出failed
  • t = 4,代表执行反转链表的操作,在执行了反转操作之后,还会有其他的操作来验证你的程序是否正确的完成了链表的反转。

    输出格式

    输出的结果取决于每组输入的数据。在遍历输出链表时,每个元素后面跟一个空格。对于操作 1 和操作 3,操作成功输出success,否则输出failed。每次操作的输出各占一行。

样例输入

9
1 0 1
1 0 2
1 0 3
2
4
2
3 3
3 0
2

样例输出

success
success
success
3 2 1
1 2 3
failed
success
2 3
#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
    int data;
    struct Node *next;
}Node, *LinkedList;

LinkedList insert(LinkedList head, Node *node, int index) {
    if (head == NULL) {
        if (index != 0) {
            printf("failed\n");
            return head;
        }
        head = node;
        printf("success\n");
        return head;
    }
    if (index == 0) {
        node->next = head;
        head = node;
        printf("success\n");
        return head;
    }
    Node *current_node = head;
    int count = 0;
    while (current_node->next != NULL && count < index - 1) {
        current_node = current_node->next;
        count++;
    }
    if (count == index - 1) {
        node->next = current_node->next;
        current_node->next = node;
        printf("success\n");
        return head;
    }
    printf("failed\n");
    return head;
}

void output(LinkedList head) {
    if (head == NULL) {
        return;
    }
    Node *current_node = head;
    while (current_node != NULL) {
        printf("%d ", current_node->data);
        current_node = current_node->next;
    }
    printf("\n");
}

LinkedList delete_node(LinkedList head, int index) {
    if(head == NULL){
        printf("failed\n");
        return head;
    }
    Node *current_node = head;
    int count = 0;
    if(index == 0){
        head = head->next;
        free(current_node);
        printf("success\n");
        return head;
    }
    while(current_node->next != NULL && count < index - 1){
        current_node = current_node->next;
        count++;
    }
    if(count == index - 1 && current_node->next != NULL){
        Node *delete_node = current_node->next;
        current_node->next = delete_node->next;
        free(delete_node);
        printf("success\n");
        return head;
    }
    printf("failed\n");
    return head;
}

LinkedList reverse(LinkedList head) {
    if(head == NULL){return head;}
    Node *next_node,*current_node;
    current_node = head->next;
    head->next = NULL;
    while(current_node != NULL){
        next_node = current_node->next;
        current_node->next = head;
        head = current_node;
        current_node = next_node;
    }
    return head;
}

void clear(LinkedList head) {
    Node *current_node = head;
    while (current_node != NULL) {
        Node *delete_node = current_node;
        current_node = current_node->next;
        free(delete_node);
    }
}

int main() {
    LinkedList linkedlist = NULL;
    int m,t,a,b;
    scanf("%d",&m);
    for(int i = 0; i < m; i++){
        scanf("%d",&t);
        if(t == 1){
            scanf("%d%d",&a,&b);
            Node *node = (Node *)malloc(sizeof(Node));
            node->data = b;
            node->next = NULL;
            linkedlist = insert(linkedlist,node,a);   
        }
        if(t == 2){
            output(linkedlist);
        }
        if(t == 3){
            scanf("%d",&a);
            linkedlist = delete_node(linkedlist,a);
        }
        if(t == 4){
            linkedlist = reverse(linkedlist);
        }
    }
    clear(linkedlist);
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。