定义单链表类，完成单链表的相关操作:。\n\n(1)显示输出一个已经生成的链表\n\n(2)对一个空表插入链表项，插入的新表被放在链表的头部，即前插入；\n\n(3)对一个空表追加链表项，追加的新链表项被放在表尾

这是一个关于定义单链表类，完成单链表相关操作的问题。

(1) 显示输出一个已经生成的链表

(2) 对一个空表插入链表项，插入的新表被放在链表的头部，即前插入；

(3) 对一个空表追加链表项，追加的新链表项被放在表尾。

相关问题

用c++定义单链表类，完成单链表的相关操作： (1) 显示输出一个已经生成的链表； (2) 对一个空表插入链表项，插入的新表被放在链表的头部，即前插入； (3) 对一个空表追加链表项，追加的新链表项被放在表尾部； (4) 两个链表相连接，既将一个链表接在另一个链表的尾部； (5) 将一个链表的数据项逆向输出； (6) 求一个链表的数据项数即长度。 提示：首先定义链表项类，包含一个int类型数据域和指针域；然后再定义单链表类，并链表类作为链表项类的友元类，来完成上述的单链表类相关操作

以下是用 C++ 定义的单链表类，实现了题目所要求的各种操作：

#include <iostream>

using namespace std;

// 链表项类
class ListNode {
public:
    int val;
    ListNode* next;

    ListNode(int val = 0, ListNode* next = nullptr) {
        this->val = val;
        this->next = next;
    }
};

// 单链表类
class LinkedList {
private:
    ListNode* head;
    int size;

public:
    LinkedList() {
        head = nullptr;
        size = 0;
    }

    ~LinkedList() {
        ListNode* p = head;
        while (p != nullptr) {
            ListNode* q = p->next;
            delete p;
            p = q;
        }
    }

    // 显示输出链表
    void display() {
        ListNode* p = head;
        while (p != nullptr) {
            cout << p->val << " ";
            p = p->next;
        }
        cout << endl;
    }

    // 在链表头插入新项
    void insertFront(int val) {
        ListNode* p = new ListNode(val, head);
        head = p;
        size++;
    }

    // 在链表尾追加新项
    void append(int val) {
        if (head == nullptr) {
            head = new ListNode(val);
        } else {
            ListNode* p = head;
            while (p->next != nullptr) {
                p = p->next;
            }
            p->next = new ListNode(val);
        }
        size++;
    }

    // 将另一个链表连接到本链表尾部
    void concatenate(LinkedList& other) {
        if (head == nullptr) {
            head = other.head;
        } else {
            ListNode* p = head;
            while (p->next != nullptr) {
                p = p->next;
            }
            p->next = other.head;
        }
        size += other.size;
        other.head = nullptr;
        other.size = 0;
    }

    // 将链表逆序输出
    void reverse() {
        ListNode* p = head;
        ListNode* q = nullptr;
        while (p != nullptr) {
            ListNode* r = p->next;
            p->next = q;
            q = p;
            p = r;
        }
        head = q;
    }

    // 求链表长度
    int getSize() {
        return size;
    }
};

下面是一个测试程序，可以用来验证上述单链表类的各种操作是否正确：

int main() {
    LinkedList lst1;
    lst1.append(1);
    lst1.append(2);
    lst1.append(3);
    lst1.display(); // 1 2 3

    lst1.insertFront(0);
    lst1.display(); // 0 1 2 3

    LinkedList lst2;
    lst2.append(4);
    lst2.append(5);
    lst2.append(6);
    lst2.display(); // 4 5 6

    lst1.concatenate(lst2);
    lst1.display(); // 0 1 2 3 4 5 6

    lst1.reverse();
    lst1.display(); // 6 5 4 3 2 1 0

    cout << lst1.getSize() << endl; // 7

    return 0;
}

设计一算法，实现将一个递减的数组 A[0..n-1]和一个带头结点的递增单链表B合并成一个带头结点的递增链表C。已知单链表的数据定义为： struct SingleLink{ ElemType data; SingleLink *next; }; 请用函数原型： SingleLink *LinkAAndB( ElemType A[], int n, SingleLink *B); 数组A和要链接的单链表B通过函数参数传递，n是数组的规模。函数返回值是生成的链表。

可以回答这个问题。算法如下：

SingleLink *LinkAAndB( ElemType A[], int n, SingleLink *B){
SingleLink *C = new SingleLink; // 创建头结点
C->next = NULL; // 初始化为空链表
SingleLink *p = C; // p指向链表C的尾结点
int i = ;
while(B->next != NULL && i < n){ // 遍历链表B和数组A
if(B->next->data < A[i]){ // 如果B的下一个结点的值小于A[i]，则将B的下一个结点插入到C中
SingleLink *q = B->next;
B->next = q->next;
q->next = p->next;
p->next = q;
p = q;
}else{ // 否则将A[i]插入到C中
SingleLink *q = new SingleLink;
q->data = A[i];
q->next = p->next;
p->next = q;
p = q;
i++;
}
}
// 将剩余的元素插入到C中
while(B->next != NULL){
SingleLink *q = B->next;
B->next = q->next;
q->next = p->next;
p->next = q;
p = q;
}
while(i < n){
SingleLink *q = new SingleLink;
q->data = A[i];
q->next = p->next;
p->next = q;
p = q;
i++;
}
return C;
}