写一个链表MakeEmpty()

Sure, here is the implementation for the MakeEmpty() function for a singly linked list in C++:

void MakeEmpty(ListNode* head) {
ListNode* current = head->next;
ListNode* next;
head->next = nullptr;
while (current != nullptr) {
next = current->next;
delete current;
current = next;
}
}

This function deallocates all the nodes in the linked list and sets the head pointer to nullptr to indicate an empty list.

相关问题

用C++，设有两条有序链表（即 data 域元素的关键字由前往后不断增大），试设计算法，将这两 条链表合并为一条新的有序链表，原链表不变。两条链表中 data 域关键字相同的元素只选 取一个存储到新的有序链表中，不同的元素都存储到新的有序链表中。 要求： ➢ 直接编写链表的友元函数完成该功能。 ➢ 链表的 data 域可存储用户自定义类对象。 ➢ 编写测试 main()函数测试线性表的正确性

#include <iostream>
using namespace std;

template<class T>
class Node{
public:
    T data; //数据域
    Node<T> *next; //指针域
    Node(const T &x, Node<T> *n = NULL){ //构造函数
        data = x;
        next = n;
    }
    Node(){next = NULL;} //构造函数
    ~Node(){} //析构函数
};

template<class T>
class List{
public:
    List(){head = new Node<T>; head->next = NULL;} //构造函数
    ~List(){makeEmpty();} //析构函数
    void makeEmpty(); //置空函数
    Node<T> *getHead() const{return head;}
    int Length() const; //求长度函数
    Node<T> *Search(const T &x) const; //查找函数
    Node<T> *Locate(int i) const; //定位函数
    bool getData(int i, T &x) const; //取数据函数
    void setData(int i, const T &x); //设置数据函数
    bool Insert(int i, const T &x); //插入函数
    bool Remove(int i, T &x); //删除函数
    bool IsEmpty() const{return head->next == NULL;} //判断是否为空
    bool IsFull() const{return false;} //判断是否为满
    void Sort(); //排序函数
    void Reverse(); //逆置函数
    void Merge(List<T> &list); //合并函数
    void Print() const; //输出函数
    friend void TestList(); //测试函数
private:
    Node<T> *head; //头指针
};

template<class T>
void List<T>::makeEmpty(){ //置空函数
    Node<T> *p = head->next, *q;
    head->next = NULL;
    while(p != NULL){
        q = p->next;
        delete p;
        p = q;
    }
}

template<class T>
int List<T>::Length() const{ //求长度函数
    Node<T> *p = head->next;
    int len = 0;
    while(p != NULL){
        len++;
        p = p->next;
    }
    return len;
}

template<class T>
Node<T> *List<T>::Search(const T &x) const{ //查找函数
    Node<T> *p = head->next;
    while(p != NULL && p->data != x)
        p = p->next;
    return p;
}

template<class T>
Node<T> *List<T>::Locate(int i) const{ //定位函数
    if(i < 0) return NULL;
    Node<T> *p = head;
    int j = -1;
    while(p != NULL && j < i){
        j++;
        p = p->next;
    }
    return p;
}

template<class T>
bool List<T>::getData(int i, T &x) const{ //取数据函数
    if(i < 0) return false;
    Node<T> *p = Locate(i);
    if(p == NULL) return false;
    else{
        x = p->data;
        return true;
    }
}

template<class T>
void List<T>::setData(int i, const T &x){ //设置数据函数
    if(i < 0) return;
    Node<T> *p = Locate(i);
    if(p == NULL) return;
    else p->data = x;
}

template<class T>
bool List<T>::Insert(int i, const T &x){ //插入函数
    Node<T> *p = Locate(i - 1);
    if(p == NULL) return false;
    else{
        Node<T> *q = new Node<T>(x, p->next);
        p->next = q;
        return true;
    }
}

template<class T>
bool List<T>::Remove(int i, T &x){ //删除函数
    Node<T> *p = Locate(i - 1);
    if(p == NULL || p->next == NULL) return false;
    else{
        Node<T> *q = p->next;
        x = q->data;
        p->next = q->next;
        delete q;
        return true;
    }
}

template<class T>
void List<T>::Sort(){ //排序函数（冒泡排序）
    Node<T> *p = head->next, *q;
    T temp;
    while(p != NULL){
        q = p->next;
        while(q != NULL){
            if(p->data > q->data){
                temp = p->data;
                p->data = q->data;
                q->data = temp;
            }
            q = q->next;
        }
        p = p->next;
    }
}

template<class T>
void List<T>::Reverse(){ //逆置函数
    Node<T> *p = head->next, *q;
    head->next = NULL;
    while(p != NULL){
        q = p->next;
        p->next = head->next;
        head->next = p;
        p = q;
    }
}

template<class T>
void List<T>::Merge(List<T> &list){ //合并函数
    Node<T> *a = head->next, *b = list.getHead()->next, *c = head;
    while(a != NULL && b != NULL){
        if(a->data < b->data){
            c->next = a;
            a = a->next;
            c = c->next;
        }
        else if(a->data > b->data){
            c->next = b;
            b = b->next;
            c = c->next;
        }
        else{
            c->next = a;
            a = a->next;
            b = b->next;
            c = c->next;
        }
    }
    if(a != NULL)
        c->next = a;
    else if(b != NULL)
        c->next = b;
}

template<class T>
void List<T>::Print() const{ //输出函数
    Node<T> *p = head->next;
    while(p != NULL){
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

void TestList(){ //测试函数
    List<int> L1, L2;
    int a[5] = {1, 3, 5, 7, 9}, b[5] = {2, 4, 6, 8, 10};
    for(int i = 0; i < 5; i++)
        L1.Insert(i, a[i]);
    for(int i = 0; i < 5; i++)
        L2.Insert(i, b[i]);
    cout << "L1: ";
    L1.Print();
    cout << "L2: ";
    L2.Print();
    L1.Merge(L2);
    cout << "L1 after merge: ";
    L1.Print();
}

int main(){
    TestList();
    return 0;
}

以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(不设头指针)。试编写相应的置空队列、判断队列是否为空、入队和出队 等算法。

### 回答1：

#include<iostream>
using namespace std;

struct Node{
    int data;
    Node* next;
};

class Queue{
public:
    Queue(){
        rear = new Node;
        rear->next = rear;
    }

    ~Queue(){
        Node* p = rear->next;
        while(p != rear){
            Node* q = p;
            p = p->next;
            delete q;
        }
        delete rear;
    }

    bool isEmpty(){
        return rear->next == rear;
    }

    void makeEmpty(){
        Node* p = rear->next;
        while(p != rear){
            Node* q = p;
            p = p->next;
            delete q;
        }
        rear->next = rear;
    }

    void enQueue(int x){
        Node* p = new Node;
        p->data = x;
        p->next = rear->next;
        rear->next = p;
        rear = p;
    }

    int deQueue(){
        if(isEmpty()){
            cout<<"Queue is empty."<<endl;
            exit(1);
        }
        else{
            Node* p = rear->next->next;
            int x = rear->next->data;
            delete rear->next;
            rear->next = p;
            if(p == rear) rear = rear->next;
            return x;
        }
    }

private:
    Node* rear;
};

int main(){
    Queue q;
    q.enQueue(1);
    q.enQueue(2);
    q.enQueue(3);
    cout<<q.deQueue()<<endl;
    cout<<q.deQueue()<<endl;
    cout<<q.deQueue()<<endl;
    q.enQueue(4);
    q.enQueue(5);
    cout<<q.deQueue()<<endl;
    cout<<q.deQueue()<<endl;
    q.makeEmpty();
    cout<<q.isEmpty()<<endl;
    return 0;
}

### 回答2：
以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点的算法如下：

置空队列的算法：
1. 创建一个空的循环链表，并在头结点上设置一个指针rear，指向NULL。
2. 如果rear指针不为空，则将rear指针置为NULL。

判断队列是否为空的算法：
1. 如果rear指针为空，则队列为空；否则，队列非空。

入队的算法：
1. 输入要插入的元素elem。
2. 创建一个新的结点newNode，并将elem保存到newNode的数据域中。
3. 如果rear指针为空，表示队列为空，则将newNode的指针域指向自身，同时将rear指针指向newNode。
4. 如果rear指针不为空，则将newNode的指针域指向rear指针指向的结点的指针域，然后将rear指针指向newNode。
5. 更新rear指针指向的结点的指针域，使其指向newNode。

出队的算法：
1. 如果rear指针为空，表示队列为空，则无法进行出队操作。
2. 如果rear指针指向的结点的指针域指向rear指针本身，表示队列中只有一个元素，则将rear指针置为NULL。
3. 否则，将rear指向的结点的指针域指向rear指针指向的结点的指针域。

以上是利用带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点的算法。

### 回答3：
以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(不设头指针)。可以通过以下算法实现相关操作：

1. 置空队列算法：
首先创建一个指向头结点的指针rear，将其指向自身即可。

2. 判断队列是否为空算法：
判断队尾指针rear是否指向自身，如果指向自身则说明队列为空。

3. 入队算法：
首先创建一个新的结点node，并将其数据设置为待入队的元素值。
如果队列为空，即rear指向自身，将rear指向node即可。
否则，将node的next指针指向rear的下一个结点，再将rear的next指针指向node，并将rear指向node。

4. 出队算法：
首先判断队列是否为空，如果为空，则无法出队，输出错误信息。
否则，将rear的next指针指向其下一个结点的下一个结点，即删除队尾元素所在的结点。
接着判断删除后队列是否为空，若不为空，则将rear指针指向删除后的队尾元素。

通过上述算法，可以实现带头结点的循环链表表示队列的置空、判断是否为空、入队和出队等操作。这样设计可以实现高效、方便的队列操作，并且不需要每次都遍历整个队列来查找队尾元素。