2、有序链表的维护【问题描述】编写一个程序，根据从标准输入接收的指令来维护和操作排序的链表（C语言、java和Python分别实现）_维护有序链表

【问题描述】

编写一个程序，根据从标准输入接收的指令来维护和操作排序的链表。链表是按顺

序维护的，这意味着链表中的数据在每次操作后都以递增的数字顺序存储。

请注意，在创建新节点时，需要使用malloc为它们分配空间；一旦不再需要任何已

分配的空间，就应该使用free将其释放。还要注意，链表不包含重复的值。

【基本要求】

链表支持两种操作指令。

插入n ：向链表中添加一个整数n。如果链表中已经存在n，则它什么也不做。 指令

格式是一个i后跟一个空格和一个整数n 。

删除n ：从链表中删除一个整数n。如果链表中不存在n，它什么也不做。 指令格式

是d后跟一个空格和一个整数n 。

在每个命令之后，程序将输出链表的长度，然后是链表的内容，按照从第一个(最

小)到最后一个(最大) 的顺序。

输入格式： 输入的每一行都包含一条指令。每行都以一个字母(或者是“i”或者是

“d”)开头，后跟一个空格，然后是一个整数。以“i”开头的一行表示该整数应该插

入链表中。以“d”开头的一行表示应从链表中删除该整数。输入i和d以外的字符程序

结束运行。

输出格式： 执行每个指令后，程序将输出一行文本，其中包含 链 表的长度、一个冒

号以及按顺序排列的 链 表元素，所有内容都用空格分隔。

程序运行操作示例：（

i或d开头的行是输入行，其他是输出行 ）

i 5

1: 5

d 3

1: 5

i 3

2: 3 5

i 500

3: 3 5 500

d 5

2: 3 500

//C语言实现：
#include <stdio.h>
#include <stdlib.h>
 
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;
 
// 创建一个新的链表节点
ListNode* createNode(int val) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}
 
// 将值插入排序链表中
void insert(ListNode** head, int val) {
    ListNode** current = head;
    while (*current != NULL && (*current)->val < val) {
        current = &((*current)->next);
    }
    if (*current == NULL || (*current)->val > val) {
        ListNode* newNode = createNode(val);
        newNode->next = *current;
        *current = newNode;
    }
}
 
// 从排序链表中删除节点
void deleted(ListNode** head, int val) {
    ListNode** current = head;
    while (*current != NULL && (*current)->val != val) {
        current = &((*current)->next);
    }
    if (*current != NULL) {
        ListNode* tmp = *current;
        *current = (*current)->next;
        free(tmp);
    }
}
 
// 打印排序链表
void print(ListNode* head) {
    int length = 0;
    ListNode* current = head;
    while (current != NULL) {
        length++;
        current = current->next;
    }
    printf("%d: ", length);
    current = head;
    while (current != NULL) {
        printf("%d ", current->val);
        current = current->next;
    }
    printf("\n");
}
// 释放链表节点动态分配的内存
void freeList(ListNode* head) {
    while (head != NULL) {
        ListNode* tmp = head;
        head = head->next;
        free(tmp);
    }
}
 
int main() {
    ListNode* head = NULL;
    char command;
    int val;
    while (1) {
        scanf("%c %d", &command, &val);
        switch(command) {
            case 'i':
                insert(&head, val);
                break;
            case 'd':
                deleted(&head, val);
                break;
            default:
                print(head);
                freeList(head);
                return 0;
        }
        //清空输入缓存区
        while(getchar() != '\n');
        print(head);
    }
}

 今天才看到了留言，更新一个C语言实现的代码；

这个程序通过标准输入接收两种指令，用字符变量command表示不同的指令：

- i 插入n：调用insert函数向排序链表中添加整数n；
- d 删除n：调用delete函数从排序链表中删除整数n。

每次读入指令后，用switch语句根据不同的指令调用相应的函数。排序链表的操作中，通过动态内存分配机制为新节点分配内存，并且在节点操作结束后及时释放相应的内存。链表长度和元素内容的打印依次调用print函数实现。

需要注意的是，由于输入指令时需要读入空格，为了防止在下一次读入指令时留下空格，需要在读取完输入后清空输入缓存区。此外，当输入指令字符不是i或d时，程序退出，并释放排序链表的所有分配内存。

//java实现：
import java.util.ArrayList;
import java.util.Scanner;
import java.util.LinkedList;
 
 
 
public class demo2 {
    //定义一个ListNode类
    static class ListNode{
        int value;
        ListNode next;
 
        public ListNode(int value,ListNode next){
            this.value = value;
            this.next = next;
        }
 
        public ListNode(int value){
            this.value = value;
        }
 
        public ListNode(){
 
        }
    }
 
    public static void main(String[] args) {
        //把输入的字符串分割成可处理的两部分
        LinkedList<Integer> list = new LinkedList<>();
 
        while (true) {
            Scanner sc = new Scanner(System.in);
            String s = sc.nextLine();
            //分别拿到指令和数据
            String[] s1 = s.split(" ");
            char c = s1[0].charAt(0);
            int x = Integer.parseInt(s1[1]);
            //通过指令进行对应操作
            switch (c) {
                case 'I' :
                case 'i' : {
                    for (int i = 0; i < list.size(); i++) {
                        if (list.get(i).equals(x)){
                            Object a = x;
                            list.remove(a);
                        }
                    }
                    list.add(x);
                    list.sort(null);
 
                    System.out.print(list.size()+":");
                    for (int i = 0; i < list.size(); i++) {
                        System.out.print(" "+list.get(i));
                    }
                    System.out.println();
                    break;
                }
                case 'D':{}
                case 'd': {
                    Object a = x;
                    list.remove(a);
                    System.out.print(list.size()+":");
                    for (int i = 0; i < list.size(); i++) {
                        System.out.print(" "+list.get(i));
                    }
                    System.out.println();
                    break;
                }
                default : System.out.println("您输入的格式有误，请重新输入！");
            }
        }
    }
}

 在该java程序中先定义了一个链表结构体`ListNode`，包括节点的值和指向下一个节点的指针。然后，按照题目要求，实现了链表结构的插入和删除操作，结构很好理解。

//利用Java内置`LinkedList`实现：
 
import java.util.ArrayList;
import java.util.Scanner;
import java.util.LinkedList;
 
 
@SuppressWarnings("all")
public class demo2 {
 
    public static void main(String[] args) {
        //把输入的字符串分割成可处理的两部分
        LinkedList<Integer> list = new LinkedList<>();
 
        while (true) {
            Scanner sc = new Scanner(System.in);
            String s = sc.nextLine();
            //分别拿到指令和数据
            String[] s1 = s.split(" ");
            char c = s1[0].charAt(0);
            int x = Integer.parseInt(s1[1]);
            //通过指令进行对应操作
            switch (c) {
                case 'I' :
                case 'i' : {
                    for (int i = 0; i < list.size(); i++) {
                        if (list.get(i).equals(x)){
                            Object a = x;
                            list.remove(a);
                        }
                    }
                    list.add(x);
                    list.sort(null);
 
                    System.out.print(list.size()+":");
                    for (int i = 0; i < list.size(); i++) {
                        System.out.print(" "+list.get(i));
                    }
                    System.out.println();
                    break;
                }
                case 'D':{}
                case 'd': {
                    Object a = x;
                    list.remove(a);
                    System.out.print(list.size()+":");
                    for (int i = 0; i < list.size(); i++) {
                        System.out.print(" "+list.get(i));
                    }
                    System.out.println();
                    break;
                }
                default : System.out.println("您输入的格式有误，请重新输入！");
            }
        }
    }
}

 上述代码使用了Java内置的`LinkedList`实现相应功能。

#Python实现：
 
#定义一个链表类,内部存储val和next
class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
#初始化链表头节点
class LinkedList:
    def __init__(self):
        self.head = None
 
#插入数字方法
    def insert(self, n : int):
        if not self.head:
            self.head = Node(n)
            return
 
        if n < self.head.val:
            node = Node(n)
            node.next = self.head
            self.head = node
        elif n > self.head.val:
            p = self.head
            while p.next and n > p.next.val:
                p = p.next
            if not p.next or n < p.next.val:
                node = Node(n)
                node.next = p.next
                p.next = node
 
#删除数字方法
    def delete(self, n: int):
        if not self.head:
            return
 
        if self.head.val == n:
            self.head = self.head.next
            return
 
        p = self.head
        while p.next and p.next.val != n:
            p = p.next
        if p.next and p.next.val == n:
            p.next = p.next.next
 
#打印此链表
    def print_list(self):
        p = self.head
        values = []
        while p:
            values.append(str(p.val))
            p = p.next
        print(len(values), ":", " ".join(values))
 
 
if __name__ == "__main__":
    linked_list = LinkedList()
    while True:
        try:
            line = input().strip()
            if not line:
                continue
            tokens = line.split()
            if tokens[0] == "i":
                linked_list.insert(int(tokens[1]))
            elif tokens[0] == "d":
                linked_list.delete(int(tokens[1]))
            else:
                break
            linked_list.print_list()
        except EOFError:
            break

在Python代码中，首先定义了 `Node` 类，表示链表的节点。然后定义了 `LinkedList` 类，表示链表，它包括了插入、删除和打印链表的方法。在插入操作中，如果链表为空，将新值插入到链表头部；如果插入值小于当前链表头节点的值，则将新值插入到链表头部；否则，查找需要插入的位置，并在该位置插入新值。在删除操作中，如果链表为空或者只有一个元素，则直接从链表中删除该元素；否则，查找需要删除的元素并从链表中删除。打印链表时，遍历链表并输出每个节点的值。

在主函数中，通过读取标准输入来获取用户输入，并调用相应的方法来处理链表。当用户输入非法字符时，程序结束运行。