数据结构基础(9) --单链表的设计与实现(2)之高级操作

链表的链接:

将第二条链表的所有内容链接到第一条链表之后, 其完整实现代码与解析如下:

?

//链表的链接
template 
  
   
void MyList
   
    ::concatenate(const MyList
    
      &list) { if (isEmpty())//如果自己的链表为空 { first = list.first; return ; } else if (list.isEmpty()) //如果第二条链表为空 { return ; } Node
     
       *endNode = first->next; //找到第一条链表的末尾节点 while (endNode->next != NULL) { endNode = endNode->next; } //找到第二条链表的第一个真实元素 Node
      
        *secondListNode = (list.first)->next; //注意: 需要将第二个链表中的元素值copy出来 //不能直接将第二条链表的表头链接到第一条链表的表尾 //不然在析构函数回收内存时会发生错误(即:同一段内存释放两次) while (secondListNode != NULL) { Node
       
         *newNode = new Node
        
         (secondListNode->data); newNode->next = NULL; endNode->next = newNode; //两条链表同时前进 endNode = endNode->next; secondListNode = secondListNode->next; } }
        
       
      
     
    
   
  

?

链表的反转:

基本思想:

遍历一遍链表，利用一个辅助指针(此处为指针r)，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。

//链表的反转
template 
  
   
void MyList
   
    ::invort() { if (!isEmpty()) { //p指向正向链表的第一个真实节点 //随后, p也会沿正方向遍历到链表末尾 Node
    
      *p = first->next; //q会成为倒向的第一个真实节点 //首先将q设置为NULL: 保证反向之后 //最后一个元素的指针域指向NULL, 以表示链表结束 Node
     
       *q = NULL; while (p != NULL) { Node
      
        *r = q; //暂存q当前指向的节点 //q后退(沿着正向后退) q = p; //p前进(沿着正向前进), 保证p能够始终领先q一个位置 p = p -> next; //将指针逆向反转 //注意:一点要保证这条语句在p指针移动之后运行, //不然p就走不了了...(因为q改变了指针的朝向) q -> next = r; } //此时q成为反向链表的第一个真实元素 //但是为了维护像以前一样的first指针指向一个无用的节点(以使前面的操作不会出错) //于是我们需要将first的指针域指向q first->next = q; } }
      
     
    
   
  

链表打印:

重载MyList的<<运算符, 输出链表所有元素, 以供测试之用

//显示链表中的所有数据(测试用)
template 
  
   
ostream &operator<<(ostream &os, const MyList
   
     &list) { for (Node
    
      *searchNode = list.first -> next; searchNode != NULL; searchNode = searchNode -> next) { os << searchNode -> data; if (searchNode -> next != NULL) //尚未达到链表的结尾 cout << " -> "; } return os; }
    
   
  

附-测试代码:

int main()
{
    cout << "------------ 1 ------------" << endl;
    MyList
  
    first;
    for (int i = 0; i < 5; ++i)
    {
        first.insert(i+1, i+1);
    }
    first.remove(5);

    MyList
   
     second; for (int i = 0; i < 5; ++i) { second.insert(i+6, i+1); } second.insertFront(5); second.insert(88, 7); cout << "Before concatenate..." << endl; cout << "first: " << first << endl; cout << "second: " << second << endl; cout << "After concatenate..." << endl; first.concatenate(second); cout << "first: " << first << endl; cout << "second: " << second << endl; cout << "\n------------ 2 ------------" << endl; MyList
    
      chList; for (char ch = '0'; ch <= '9'; ++ ch) { chList.insertFront(ch); } cout << "Before invort..." << endl; cout << chList << endl; cout << "After invort..." << endl; chList.invort(); cout << chList << endl; cout << "After remove('5')..." << endl; chList.remove('5'); cout << chList << endl; cout << "\n------------ 3 ------------" << endl; MyList
     
       dList; dList.insert(1.1, 1); dList.insertFront(2.2); cout << dList << endl; return 0; }
     
    
   
  

?