0

我正在开发这个程序，我必须编写一个使用双向链表实现的排序列表模板。SortedList.cpp 是给我的，其中包含测试床主体。我应该在 SortedList.h 文件中实现模板。

该模板有一个 Insert、Delete 和 Print 函数、一个默认构造函数和 Big 3。将 Print 函数的内容复制到您自己的模板中：

// Implementation of Print function
int i = 1;
Node * p = list;
while ( p != NULL )
{
    cout << "Node " << i << ": " << p->data << endl;
    p = p->next;
    i++;
}

我确实写了 SortedList.h，但是当我将我的输出与正确的输出进行比较时，我发现它不匹配。

这是 SortedList.h：

// SortedList.h list template implemented using doubly linked list.
#ifndef SORTEDLIST_H_
#define SORTEDLIST_H_
# include <iostream>
using namespace std;
// struct defining the node of the linked list
template <typename T>
struct Node {
    T data;
    Node<T> *next, *pre;
};
// class which defines the linked list
template <typename T>
class SortedList {
private:
    Node<T> *head;
public:
    // default constructor
    SortedList<T>()
    {
        head = NULL;
    }
    // fucntion Insert to insert the node at the end of the list
    void Insert(T n)
    {
        Node<T> *newNode = new Node<T>;
        newNode->data = n;
        newNode->next = NULL;
        newNode->pre = NULL;
        if (head == NULL)
        {
            head = newNode;
        }
        else if (head->data > n)
        {
            Node<T>* temp = head;
            head = newNode;
            newNode->next = temp;
            temp->pre = head;
        }
        else {
            Node<T> *temp = head;
            Node<T> *prev = NULL;
            bool inserted = false;
            while (temp != NULL)
            {
                if (temp->data > n)
                {
                    //Node* _temp = temp;
                    newNode->pre = temp->pre;
                    newNode->next = temp;
                    temp->pre = newNode;
                    if (newNode->pre != NULL)
                    {
                        newNode->pre->next = newNode;
                    }
                    inserted = true;
                    break;
                }
                prev = temp;
                temp = temp->next;
            }
            if (!inserted)
            {
                newNode->pre = prev;
                prev->next = newNode;
            }
        }
    }
    // function to delete the node with the data n
    void Delete(T n)
    {
        if (head == NULL)
        {
            return;
        }
        else {
            if (head->data == n)
            {
                Node<T> *temp = head;
                head = head->next;
                if (head != NULL)
                    head->pre = NULL;
                delete(temp);
            }
            else {
                Node<T> *temp = head->next;
                while (temp != NULL)
                {
                    if (temp->data == n)
                    {
                        {
                            temp->pre->next = temp->next;
                            if (temp->next != NULL)
                                temp->next->pre = temp->pre;
                        }
                        Node<T>* toDelete = temp;
                        temp = temp->pre;
                        if (toDelete != NULL)
                            delete(toDelete);
                    }
                    temp = temp->next;
                }
            }
        }
    }
    // function to print the list
    void Print()
    {
        if (head == NULL)
            cout << "\n Empty list ";
        else
        {
            int i = 1;
            cout << "\n List " << endl;
            Node<T> **temp = &head;
            while ((*temp) != NULL)
            {
                cout << " Node " << i << ":" << (*temp)->data << endl;
                temp = &((*temp)->next);
                i++;
            }
        }
    }
};
#endif /* SORTEDLIST_H_ */
// End of Sorted.h

我得到的输出：

   1: 
   2:  List 
   3:  Node 1: 
   4:  Node 2: 
   5:  Node 3: 
   6:  Node 4: 
   7:  Node 5: 
   8:  Node 6: 
   9:  Node 7: 
  10:  Node 8: 
  11:  Node 9: 
  12:  Node 10:!
  13:  Node 11:a
  14:  Node 12:a
  15:  Node 13:e
  16:  Node 14:e
  17:  Node 15:e
  18:  Node 16:g
  19:  Node 17:g
  20:  Node 18:h
  21:  Node 19:h
  22:  Node 20:i
  23:  Node 21:i
  24:  Node 22:i
  25:  Node 23:i
  26:  Node 24:l
  27:  Node 25:n
  28:  Node 26:n
  29:  Node 27:o
  30:  Node 28:r
  31:  Node 29:r
  32:  Node 30:r
  33:  Node 31:s
  34:  Node 32:s
  35:  Node 33:s
  36:  Node 34:s
  37:  Node 35:s
  38:  Node 36:t
  39:  Node 37:t
  40:  Node 38:t
  41:  Node 39:t
  42:  Node 40:t
  43:  Node 41:t
  44:  Node 42:v
  45:  Node 43:v
  46:  Node 44:y
  47:  Node 45:y
  48: Which one do you want to delete?
  49: Which one do you want to delete?
  50: Which one do you want to delete?
  51: Which one do you want to delete?
  52: Which one do you want to delete?
  53: Which one do you want to delete?
  54: 
  55:  List 
  56:  Node 1: 
  57:  Node 2: 
  58:  Node 3: 
  59:  Node 4: 
  60:  Node 5: 
  61:  Node 6: 
  62:  Node 7: 
  63:  Node 8: 
  64:  Node 9: 
  65:  Node 10:!
  66:  Node 11:e
  67:  Node 12:e
  68:  Node 13:e
  69:  Node 14:g
  70:  Node 15:g
  71:  Node 16:h
  72:  Node 17:h
  73:  Node 18:l
  74:  Node 19:n
  75:  Node 20:n
  76:  Node 21:o
  77:  Node 22:r
  78:  Node 23:r
  79:  Node 24:r
  80:  Node 25:s
  81:  Node 26:s
  82:  Node 27:s
  83:  Node 28:s
  84:  Node 29:s
  85:  Node 30:t
  86:  Node 31:t
  87:  Node 32:t
  88:  Node 33:t
  89:  Node 34:t
  90:  Node 35:t
  91:  Node 36:v
  92:  Node 37:v
  93:  Node 38:y
  94:  Node 39:y
  95: 
  96:  List 
  97:  Node 1:3.14

这是我应该得到的正确输出：

1: Node 1:  
   2: Node 2: !
   3: Node 3: a
   4: Node 4: e
   5: Node 5: g
   6: Node 6: h
   7: Node 7: i
   8: Node 8: l
   9: Node 9: n
  10: Node 10: o
  11: Node 11: r
  12: Node 12: s
  13: Node 13: t
  14: Node 14: v
  15: Node 15: y
  16: Which one do you want to delete?
  17: Which one do you want to delete?
  18: Which one do you want to delete?
  19: Which one do you want to delete?
  20: Which one do you want to delete?
  21: Which one do you want to delete?
  22: Node 1:  
  23: Node 2: !
  24: Node 3: e
  25: Node 4: g
  26: Node 5: h
  27: Node 6: l
  28: Node 7: n
  29: Node 8: o
  30: Node 9: r
  31: Node 10: s
  32: Node 11: t
  33: Node 12: v
  34: Node 13: y
  35: Node 1: 3.14

谁能告诉我我做错了什么？

谢谢

4

1 回答 1

0

该Delete函数有一个奇怪的不对称性：如果要删除的元素是第一个元素，则该函数只删除该单个元素；否则它会删除所有出现的元素。

例如：

SortedList<char> l;

l.Insert('z');
l.Insert('z');
l.Insert('a');
l.Insert('a');
l.Insert('x');
l.Insert('x');
// l == {'a','a', 'x', 'x', 'z', 'z'}

现在：

l.Delete('z');
// l = {'a','a', 'x', 'x'}

所有的事件'z'都消失了。

尽管：

l.Delete('a');
// l = {'a', 'x', 'x'}

只删除一个元素。

这解释了你得到的不同结果。

你应该改变：

if (head->data == n)
{
  Node<T> *temp = head;
  head = head->next;
  if (head != NULL)
    head->pre = NULL;
  delete(temp);
}

处理多个删除。

于 2017-11-03T14:42:01.750 回答