c++ - 将节点添加到双向链表时遇到问题

Question

您好，我正在尝试制作一个双向链表以将单个数字存储为双向链表的节点，然后将它们加在一起并打印出来以供家庭作业使用。我在让它工作时遇到了很多麻烦，并将我的问题追溯到我的添加节点函数，因为它们没有正确更新指针。例如，在 AddToFront() 函数上，我无法理解如何让 prev 指针工作并指向它后面的节点。

我不能使用 STL，必须自己实现 LL，以防有人疑惑。谢谢!

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>

using namespace std;

/////// PART A
template <class T>
class List {
private:
    struct Node {
        T data;
        Node *next;
        Node *prev;
    };
    Node *front, *current, *rear;

public:
    List();
    ~List();
    void AddtoFront (T newthing);
    void AddtoRear (T newthing);
    bool FirstItem (T & item);
    bool LastItem (T & item);
    bool NextItem (T & item);
    bool PrevItem (T & item);
};

template <class T>
List<T>::List() {
  front = NULL;  current = NULL; rear = NULL;
}
template <class T>
List<T>::~List() {

}

template <class T>
void List<T>::AddtoFront (T newthing) {
    if (front == NULL) {
        Node *temp;
        temp = new Node;
        temp->data = newthing;
        temp->next = front;
        temp->prev = NULL;
        front = temp;
    } else {
        Node *temp;
        temp = new Node;
            front->prev = temp;
        temp->data = newthing;
        temp->next = front;
        temp->prev = NULL;
        front = temp; 
    }
}

template <class T>
void List<T>::AddtoRear (T newthing) {
    if (rear == NULL) {
        Node *temp;
        temp = new Node;
        temp->data = newthing;
        temp->prev = rear;
        temp->next = NULL;
        rear = temp;
    } else {
        Node *temp;
        temp = new Node;
            rear->next = temp;
        temp->data = newthing;
        temp->prev = rear;
        temp->next = NULL;
        rear = temp;
    }
}

template <class T>
bool List<T>::FirstItem (T & item) {
    if (front == NULL) { return false; }
    current = front;
    item = front->data;
    return true;
}

template <class T>
bool List<T>::LastItem (T & item) {
    if (rear == NULL) { return false; }
    current = rear;
    item = rear->data;
    return true;
}

template <class T>
bool List<T>::NextItem (T & item) {
    if (current != NULL) current = current->next;
    if (current == NULL) { return false; }
    item = current->data;
    return true;
}

template <class T>
bool List<T>::PrevItem (T & item) {
    if (current == NULL) { return false; }
    if (current->prev != NULL) current = current->prev;
    item = current->data;
    return true;
}

/////// PART B
class BigNumber {
private:
//complete here...
//include here a List of integers, or shorts etc
    List<int>L;

public:
//complete here...
//what methods do you need?
//e.g., ReadFromString, PrintBigNumber, AddBigNumbers
    BigNumber();
    ~BigNumber();
    void ReadFromString(char * decstring);
    void PrintBigNumber();
    void AddBigNumbers(BigNumber B1, BigNumber B2);
};

BigNumber::BigNumber(){
// anything here?
}

BigNumber::~BigNumber(){
//you can keep that empty
}

void BigNumber::ReadFromString (char * decstring ) {
    //read a string, adding a new node per digit of the decimal string
    // To translate 'digits' to integers: myinteger=decstring[index]-48
    //You need to use the AddtoFront()
    int temp;
    for (unsigned i=0; i < strlen(decstring); ++i) {
        //cin >> decstring[i];
        temp = decstring[i]-48;
        //L.AddtoFront(temp);
        L.AddtoRear(temp);
        //cout <<"Number added!" <<endl;
    }
}

void BigNumber::PrintBigNumber () {
//complete here, print the list (i.e., use FirstItem() and NextItem() )
    int val;
    if (L.FirstItem(val)) {
        cout << val;
    } else {
        cout << "print failed";
    }
    //if (L.FirstItem(val)) { cout << "true-first";} else { cout <<"false-first";};
    //if (L.LastItem(val)) { cout << "true";} else { cout <<"false";};
    //L.FirstItem(val);
    //cout << val;
    /*while (L.PrevItem(val)){

            cout << val;
            //cout <<"Print error!Value not here.";
    }*/
}

void BigNumber::AddBigNumbers(BigNumber B1,BigNumber B2){
//complete here.
//use FirstItem(), NextItem() and AddNode()
//to add two big numbers, what do you have to do? Be careful about the carry
//Remember to add the last carry, the resulting number can have one more digit than B1 or B2
}

/////// PART C

BigNumber B1, B2, RES;

int main (int argc, char ** argv) {
  //use command line arguments
  if(argc!=3){printf("usage: executable number1 number2\n");exit(0);}
  B1.ReadFromString(argv[1]);
  B2.ReadFromString(argv[2]);
  //print
  cout << endl<< "Add the following numbers " << endl;
  B1.PrintBigNumber();
  cout << " + ";
  B2.PrintBigNumber();
  cout << " = " << endl;
  //compute the addition
  RES.AddBigNumbers(B1,B2);
  //print the result
  RES.PrintBigNumber();
  cout << endl;
  return 0;
}

编辑:我在 AddToFront() 和 AddToRear() 中分别添加了一行。这是在正确的轨道上吗？

Answer 1

AddtoFront 还需要更新 front 的 prev 指针。也就是说，你目前正在做

temp -> front <-> rest_of_list

在需要的地方

temp <-> front <-> rest_of_list.

此外，您可能会注意到 AddtoFront 中的 if 语句的两个分支是相同的...:)