基于Transpose方法的自组织列表实现逻辑问题求助

我正尝试基于Transpose方法实现自组织列表，流程为：从文本文件读取单词，重组为词对（句子中第一个词与第二个词配对，第二个词作为下一对的第一个词），之后通过Transpose方法将高频词对移至列表前端。

词对生成代码 #

ifstream textfile; 
textfile.open("thecat.txt"); 
string word, first, second; 
LinkedList *list = new LinkedList(); 
int flag = 0; 

while(!textfile.eof()){

  getline(textfile, line); 
  //cout << line << endl; 

  //remove punctuation, remove if from algorithm library 
  line.erase(remove_if(line.begin(), line.end(), ::ispunct), line.end()); 

  //make everything lowercase 
  transform(line.begin(), line.end(), line.begin(), ::tolower); 
  //cout << line << endl; 

  //break line into words 
  istringstream iss(line);


  while(iss >> word){

     // cout << word << endl; 

      if(!isStopWord(word, stopwords)){

          if(flag == 0){
  
            first = word; 
            //cout << first; 
          }else{

            
            second = word; 
            
            //create a new node with first and second word for search 
           
            
             Node *current = new Node(first, second); 
            
             list->insert(current);  
            
            first = word; //assign next word as first word for next node 

            
          }
  
          flag = 1;              
        
      } 
   
  }

 list->print();

}


textfile.close();

Transpose方法代码 #

bool transpose(Node *newNode){

//pointer for current node
 Node *current = head; 
  //pointer for previous node
 Node *prev = NULL; 
 //pointer for node before previous node
Node *prev_prev = NULL; 

//while there are nodes left to search through 
while(current != NULL){

//If the current node is equivalent to the new node being read in 
if(current->first == newNode->first && current->second == newNode->second){

  //if the node two behind the current node is not empty 
  if(prev_prev != NULL){

    //re-arrange elements
    prev_prev->next = current; 
    prev->next = current->next; 
    current->next = prev; 
  }else if(prev != NULL){

    prev->next = current->next; 
    current->next = prev; 
    head = current; 
}
    return true; 
}

  prev_prev = prev; 
  prev = current; 
  current = current->next; 
}

return false; 
 }

遇到的异常 #

原本想实现“若transpose返回false则将该词对节点插入列表末尾”的逻辑，但调用位置不同出现三种异常：

• 在最内层while循环的insert语句后调用：列表仅插入5个元素就中断；
• 在外部while循环的flag=1之前调用：频繁出现重复词对；
• 在最外层while循环的print语句上下调用：无任何效果。

问题分析与修复方案 #

核心逻辑错误 #

1. 调用时机颠倒：当前先插入节点再调用transpose，导致重复节点生成，且移动逻辑混乱。正确流程应为：先调用transpose查找词对是否存在，存在则移动，不存在才插入新节点。
2. 文件读取逻辑错误：while(!textfile.eof())会导致最后一行重复处理，应改为while(getline(textfile, line))。
3. Transpose方法遗漏边界处理：未处理目标节点已是头节点的情况，此时无需任何操作。
4. 内存泄漏：临时生成的匹配节点未在找到时释放。

修复后的代码片段 #

修改词对生成的内层循环

string line;
// 修复文件读取逻辑
while(getline(textfile, line)){
    line.erase(remove_if(line.begin(), line.end(), ::ispunct), line.end());
    transform(line.begin(), line.end(), line.begin(), ::tolower);
    istringstream iss(line);

    while(iss >> word){
        if(!isStopWord(word, stopwords)){
            if(flag == 0){
                first = word;
                flag = 1;
            }else{
                second = word;
                // 创建临时节点用于查找匹配
                Node *tempNode = new Node(first, second);
                // 先尝试查找并移动
                bool found = list->transpose(tempNode);
                if(!found){
                    // 不存在则插入末尾
                    list->insert(tempNode);
                }else{
                    // 已存在，释放临时节点避免内存泄漏
                    delete tempNode;
                }
                first = word;
            }
        }
    }
    list->print();
}
textfile.close();

修复Transpose方法

bool transpose(Node *targetNode){
    Node *current = head;
    Node *prev = NULL;
    Node *prev_prev = NULL;

    while(current != NULL){
        if(current->first == targetNode->first && current->second == targetNode->second){
            // 目标已是头节点，无需移动
            if(prev == NULL){
                return true;
            }
            // 目标是第二个节点，与头节点交换
            if(prev_prev == NULL){
                prev->next = current->next;
                current->next = prev;
                head = current;
            }else{
                // 目标是中间节点，与前一个节点交换
                prev_prev->next = current;
                prev->next = current->next;
                current->next = prev;
            }
            return true;
        }
        prev_prev = prev;
        prev = current;
        current = current->next;
    }
    return false;
}

确保insert方法正确插入到末尾

// LinkedList类的insert方法示例
void insert(Node *newNode){
    if(head == NULL){
        head = newNode;
    }else{
        Node *temp = head;
        while(temp->next != NULL){
            temp = temp->next;
        }
        temp->next = newNode;
    }
    newNode->next = NULL;
}

关键说明 #

• 每次生成词对时，先通过临时节点匹配列表中的已有节点，避免重复插入；
• Transpose方法仅在找到节点时执行一次交换（符合自组织列表的Transpose策略：每次访问将节点前移一位）；
• 修复文件读取逻辑，避免重复处理最后一行；
• 及时释放临时节点，防止内存泄漏。

内容的提问来源于stack exchange，提问作者LearnMEprogram