7-9 单向链表2 分数 25 作者 wangxiu 单位 福州大学 编程实现：输入一个正整数 repeat (0<repeat<10)，做 repeat 次下列运算： 输入一个正整数 n(0<n<=9)和一组(n个)整数，建立一个单向链表，再输入一个整数 x，将链表中最后一个与x相等的整数删除。 输入输出示例：括号内为说明 输入样例: 3 (repeat=3) 5 (数据的个数n=5) 1 2 4 3 7 (5个整数) 4 (待删除整数x=4) 5 (数据的个数n=5) 2 1 5 7 5 (5个整数) 5 (待删除整数x=5) 3 (数据的个数n=3) 1 2 4 (3个整数) 100 (待删除整数x=100) 输出样例: size=4:1 2 3 7 size=4:2 1 5 7 size=3:1 2 4

这道题目是一个链表的基础操作，可以按照如下步骤实现：

1. 定义一个链表节点结构体，包含一个整数值和一个指向下一个节点的指针。

2. 定义一个链表结构体，包含一个指向头节点的指针和链表的长度。

3. 实现链表的初始化函数，创建一个空链表。

4. 实现链表的插入函数，将一个新的节点插入到链表的末尾。

5. 实现链表的删除函数，删除链表中最后一个与给定值相等的节点。

6. 在主函数中，依次读入repeat、n、n个整数、x，然后按照题目要求进行链表操作。

7. 最后输出链表的长度和节点值即可。

下面是具体的实现代码：

相关问题

7-1 单向链表2 分数 25 作者 wangxiu 单位 福州大学 编程实现：输入一个正整数 repeat (0<repeat<10)，做 repeat 次下列运算： 输入一个正整数 n(0<n<=9)和一组(n个)整数，建立一个单向链表，再输入一个整数 x，将链表中最后一个与x相等的整数删除。 输入输出示例：括号内为说明 输入样例: 3 (repeat=3) 5 (数据的个数n=5) 1 2 4 3 7 (5个整数) 4 (待删除整数x=4) 5 (数据的个数n=5) 2 1 5 7 5 (5个整数) 5 (待删除整数x=5) 3 (数据的个数n=3) 1 2 4 (3个整数) 100 (待删除整数x=100) 输出样例: size=4:1 2 3 7 size=4:2 1 5 7 size=3:1 2 4

下面是符合要求的 C++ 代码：

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(NULL) {}
};

Node* createList(int n) { // 创建链表
    Node* head = new Node(0);
    Node* cur = head;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        Node* node = new Node(x);
        cur->next = node;
        cur = node;
    }
    return head->next;
}

Node* deleteNode(Node* head, int x) { // 删除节点
    Node* dummy = new Node(0);
    dummy->next = head;
    Node* prev = dummy;
    Node* cur = head;
    while (cur) {
        if (cur->val == x) {
            prev->next = cur->next;
            delete cur;
            return dummy->next;
        }
        prev = cur;
        cur = cur->next;
    }
    return dummy->next;
}

void printList(Node* head) { // 输出链表
    int cnt = 0;
    while (head) {
        if (cnt > 0) cout << " ";
        cout << head->val;
        head = head->next;
        ++cnt;
    }
    cout << endl;
    cout << "size=" << cnt << ":";
}

int main() {
    int repeat;
    cin >> repeat;
    while (repeat--) {
        int n, x;
        cin >> n;
        Node* head = createList(n);
        cin >> x;
        head = deleteNode(head, x);
        printList(head);
    }
    return 0;
}

这个程序先读入 repeat，表示有 repeat 组数据需要处理。每组数据首先读入 n，然后调用 createList 函数创建链表。接着读入 x，调用 deleteNode 函数删除链表中最后一个与 x 相等的节点。最后调用 printList 函数输出链表。

编程实现：输入一个正整数 repeat (0<repeat<10)，做 repeat 次下列运算：\n输入一个正整数 n(0<n<=9)和一组(n个)整数，建立一个单向链表，再输入一个整数 x，将链表中

### 回答1：
的所有值为 x 的节点删除，最后输出删除后的链表。

实现思路：

1. 定义一个链表节点结构体，包含一个整型数据域和一个指向下一个节点的指针域。

2. 定义一个函数 createList，用于创建一个长度为 n 的单向链表，并返回链表的头节点指针。

3. 定义一个函数 deleteNode，用于删除链表中所有值为 x 的节点。

4. 在主函数中，先输入 repeat，然后循环 repeat 次，每次输入 n 和 n 个整数，调用 createList 函数创建链表，再输入 x，调用 deleteNode 函数删除链表中所有值为 x 的节点，最后输出删除后的链表。

代码实现：

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

// 链表节点结构体
struct ListNode {
int val;
struct ListNode *next;
};

// 创建链表
struct ListNode* createList(int n) {
struct ListNode *head = NULL, *tail = NULL;
for (int i = 0; i < n; i++) {
int val;
scanf("%d", &val);
struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = val;
node->next = NULL;
if (head == NULL) {
head = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
}
return head;
}

// 删除节点
void deleteNode(struct ListNode* head, int x) {
struct ListNode *prev = NULL, *curr = head;
while (curr != NULL) {
if (curr->val == x) {
if (prev == NULL) {
head = curr->next;
} else {
prev->next = curr->next;
}
free(curr);
curr = prev == NULL ? head : prev->next;
} else {
prev = curr;
curr = curr->next;
}
}
}

int main() {
int repeat;
scanf("%d", &repeat);
for (int i = 0; i < repeat; i++) {
int n, x;
scanf("%d", &n);
struct ListNode *head = createList(n);
scanf("%d", &x);
deleteNode(head, x);
while (head != NULL) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
return 0;
}

### 回答2：
这道题目要实现的是链表操作的基本内容，主要是对链表的建立与节点的插入。首先，我们需要了解链表的基本概念。链表是一种常见的数据结构，它由一个个节点组成，每个节点包含数据和指向下一节点的指针。链表有单向链表和双向链表之分，单向链表指每个节点只有向后指向的指针，而双向链表每个节点有指向前一个和后一个节点的指针。

在实现过程中，我们需要定义一个链表节点类，包含数据和指向下一个节点的指针。然后再定义一个链表类，包含新增、插入、删除、遍历等相关方法。下面是此题的具体实现：

在每一次循环中，先输入n和n个整数，然后根据这些数据建立链表。可以使用链表类中的addFirst（）方法，将输入的n个整数依次插入到头节点后面。接着，输入一个整数x，再用链表类中的add（）方法将x插入到链表的任意位置。最后，输出完整链表。

下面是完整代码实现：

class Node(object):
    def __init__(self, data=None):
        self.data = data
        self.next = None


class LinkedList(object):
    def __init__(self):
        self.head = Node()

    def addFirst(self, data):
        new_node = Node(data)
        new_node.next = self.head.next
        self.head.next = new_node

    def append(self, data):
        new_node = Node(data)
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = new_node

    def add(self, pos, data):
        if pos < 0:
            print("Error: invalid position!")
            return
        new_node = Node(data)
        cur = self.head
        count = 0
        while count < pos and cur.next:
            cur = cur.next
            count += 1
        if count == pos:
            new_node.next = cur.next
            cur.next = new_node
        else:
            print("Error: invalid position!")

    def remove(self, data):
        cur = self.head
        while cur.next:
            if cur.next.data == data:
                cur.next = cur.next.next
                return
            cur = cur.next
        print("Error: the data is not in the linked list!")

    def size(self):
        count = 0
        cur = self.head
        while cur.next:
            count += 1
            cur = cur.next
        return count

    def search(self, data):
        cur = self.head
        while cur.next:
            if cur.next.data == data:
                return True
            cur = cur.next
        return False

    def show(self):
        cur = self.head
        while cur.next:
            print(cur.next.data, end=' ')
            cur = cur.next
        print("")


repeat = int(input("请输入 repeat 的值："))
for i in range(repeat):
    n = int(input("请输入 n 的值："))
    list = LinkedList()
    for j in range(n):
        data = int(input("请输入第 %d 个整数：" % (j + 1)))
        list.addFirst(data)
    x = int(input("请输入要插入的整数："))
    pos = int(input("请输入要插入的位置："))
    list.add(pos, x)
    print("插入后，链表内容为：")
    list.show()

总之，这道题目其实是想让我们掌握链表的基本操作，如何创建节点，如何在链表中插入和删除节点等。通过这道题目的练习，我们不仅可以提高编程能力，还可以加深对链表的理解和应用。

### 回答3：
这道题需要实现如下两个过程：

1. 建立单向链表

当输入一个正整数 n 和一组整数时，需要建立一个单向链表。可以先定义一个节点结构体，包括整数值和指向下一个节点的指针。通过读入 n 个整数，依次构造节点，并将它们连接起来，形成一个单向链表。

2. 插入整数 x

当输入一个整数 x 时，需要将其插入到刚才建立的链表中。可以先遍历链表，寻找一个节点 p，使得 p 的值小于 x，p 的下一个节点 q 的值大于 x。然后构造一个新节点，并将其插入到 p 和 q 之间。

下面是完整的代码实现：

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

// 定义节点结构体
struct Node {
int value;
struct Node* next;
};

// 建立单向链表
struct Node* make_list(int n) {
struct Node* head = NULL;
struct Node* prev = NULL;
int i;
for (i = 0; i < n; ++i) {
int value;
scanf("%d", &value);
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->value = value;
node->next = NULL;
if (prev == NULL) {
head = node;
} else {
prev->next = node;
}
prev = node;
}
return head;
}

// 插入整数 x
void insert(struct Node* head, int x) {
struct Node* p = head;
while (p != NULL) {
if (p->next == NULL || p->next->value > x) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->value = x;
node->next = p->next;
p->next = node;
break;
}
p = p->next;
}
}

int main() {
int repeat;
scanf("%d", &repeat);
int i;
for (i = 0; i < repeat; ++i) {
int n;
scanf("%d", &n);
struct Node* head = make_list(n);
int x;
scanf("%d", &x);
insert(head, x);
struct Node* p = head;
while (p != NULL) {
printf("%d ", p->value);
p = p->next;
}
printf("\n");
}
return 0;
}