数据结构面试之二——双向链表表、循环链表、有序链表的常见操作

二、双向链表

双向链表的建立是在单链表的基础上,多了一个指向前驱的指针back。其他的操作类似,注意点就是在双向链表的操作,尤其插入、删除操作中需要修改两个指针的指向,一个是back指针,一个是next指针。

1.双向链表的构建【前面插入】

构建双向链表注意点:1)修改first指针(头指针)的指向。2)修改back、next指针。

//反向表头插入,从前面插入...

template<typename Type>
nodeType<Type>*doublyLinkedList<Type>::buildListBackward()
{
       nodeType<Type> *newNode;
 
       int num;
       cout << " Enter a list of integer end with -999." << endl;
       cin >> num;
 
       while(num != -999)
       {
              //..add
              newNode = new nodeType<Type>;
              newNode->info = num;
              newNode->next = NULL;
              newNode->back = NULL;
             
              if(first == NULL)
              {
                     first = newNode;
              }
              else
              {
                     newNode->next = first;
                     first->back = newNode;
                     first = newNode;
              }
 
              cin >> num;
       }
       return first;
}

2.双向链表的插入节点【此处考虑插入后保证有序,直接插入排序】

节点的插入同单链表,依然需要考虑多种因素。分以下几类:

1)双向链表为空,“提示信息”并返回。

2)双向链表非空,待插入节点的元素值小于first节点,需要修改first指针。

3)双向链表非空,待插入节点的元素值为链表中间的节点,需修改back、next指向。

4)双向链表非空,待插入节点在最末尾节点以后,修改最末节点的指针。

//双向不循环链表
template<typename Type>
voiddoublyLinkedList<Type>::insertNode(const Type& insertItem)  //new
{
nodeType<Type> *current;
nodeType<Type> *trailCurrent;
nodeType<Type> *newNode;
bool found = false;
 
newNode = new nodeType<Type>;
newNode->info = insertItem;
newNode->next = NULL;
newNode->back = NULL;
 
//case 1: 空表
if(first == NULL)
{
        first = newNode;
}
else
{
        current = first;
        while( current != NULL)
        {
               if( current->info >= insertItem )
               {
                      found = true;
                      break;
               }
               else
               {
                      trailCurrent = current;
                      current = current->next;
               }
        }
 
        //case 2: 第一个节点
        if(current == first)
        {
               current->next = newNode;
               newNode->back = current;
        }
        else
        {
               //case 3: 中间节点
               if(current != NULL)
               {
                      newNode->next = trailCurrent->next;
                      current->back = newNode;
                      trailCurrent->next = newNode;
                      newNode->back = trailCurrent;
               }
               else  //case 4:最后一个节点前
               {
                      trailCurrent->next = newNode;
                      newNode->back = trailCurrent;
               }//end case 4
        }
}
}

3.双向链表的删除节点

同样需要考虑以下几点:

1) 链表为空,“提示信息”并返回。

2) 链表非空,查找删除的元素在链表是否存在。是的话,found=true;否的话,found=false。

3) 如果没有找到包含查找元素的节点,“错误提示”并返回。

4) 如果找到,主要节点位置。如果是头节点或末尾节点主要修改first指针,及节点的back、next指向;如果不是头节点或者末尾节点就是中间节点,主要back、next的指向,完成插入。

template<typename Type>
void doublyLinkedList<Type>::deleteNode(constType& deleteItem)   //new
{
  nodeType<Type> *current = new nodeType<Type>;
  nodeType<Type> *trailCurrent;
  bool found = false;
        
  //case 1: 空表
  if(first == NULL)
  {
         cout << "The List is NULL!" << endl;
         exit(1);
  }
  else
  {
         current = first;
         while( current != NULL)
         {
                if( current->info == deleteItem )
                {
                       found = true;
                       break;
                }
                else
                {
                       trailCurrent = current;
                       current = current->next;
                }
         }
 
         if(found)
         {
                //case 2: 第一个节点
                if(current == first)
                {
                       first = current->next;
                       delete current;
                }
                else
                {
                       //case 3: 中间节点
                       if(current != NULL)
                       {
                              if(current->next != NULL)  //case3.1:要删除的是中间节点.
                              {
                                     trailCurrent->next =current->next;
                                     current->next->back = trailCurrent;
                                     delete current;
                              }
                              else
                              {
                                     trailCurrent->next = NULL;//case3.2:要删除的为最后一个节点.
                                     delete current;
                              }
                       }
               
                }// end else
         }// end if
         else
         {
                cout << "The elem " <<deleteItem << " is not Exist in the List!" << endl;//case 4: 链表中无此节点.
         }
  }//end else
}//end

三、循环链表

循环链表能保障从每一个节点出发都能检索链表。即:last指针的指向不再为空,而是指向了first(头结点)。

循环链表在构建链表、查找元素、插入、删除、操作中要注意修改末尾节点指针的指向,保证链表的循环。

1.前插式构建循环链表

【思路】:每次在first指针前面插入节点;插入每个节点后注意修改last->link的指向。

template<typename Type>
void cycleList<Type>::bulidCycListBackward() //前插构造循环链表.
{
        Type newItem;
        while(cin >> newItem, newItem != -999)
        {
               nodeType<Type>* newNode = newnodeType<Type>;
               newNode->info = newItem;
               newNode->link = NULL;
 
               if(first == NULL)
               {
                      first = newNode;
                      last = newNode;
                      first->link = first;
                      last->link = first;
               }
               else
               {
                      newNode->link = first;
                      last->link = newNode;
                      first = newNode;
               }
        }
        cout << "输入完毕!" << endl;
}

2. 循环链表插入元素[后插入]

【思路】:同构造循环链表,每次在last指针后面插入节点;插入每个节点后注意修改last->link的指向。

//只在last末尾插入
template<typename Type>
voidcycleList<Type>::insertCycList(const Type& newItem)
{
nodeType<Type> *newNode = new nodeType<Type>;
newNode->info = newItem;
newNode->link = NULL;
 
if(first == NULL)        //链表为空...
{
        first = newNode;
        last = newNode;
        first->link = first;
        last->link = first;
}
else                   //链表非空...
{
        last->link = newNode;
        newNode->link = first;
        last = newNode;
}
cout << newItem << "was inserted!" <<endl;
}

3.删除循环链表节点

考虑到是否为空链表、删除元素在链表中不存在、及节点存在(节点的位置可能为共分头、中间、尾),所以分为以下5种情况分别处理。:

//case1:链表为空。
//case2:链表非空,删除节点为头节点。
//case3:链表非空,删除节点为尾节点。
//case4:链表非空,删除节点为中间节点。
//case5:链表非空,不存在=deleteItem的节点。
template<typename Type>
voidcycleList<Type>::delCycList(const Type& deleteItem)
{
nodeType<Type> *current = new nodeType<Type>;
nodeType<Type> *trailCurrent = new nodeType<Type>;
nodeType<Type> *temp ;
bool found = false;
 
if( first == NULL )
{
        cout << "The List is Empty!" << endl;//case1
        return;
}
if( first->info == deleteItem )      //case2
{
        temp = new nodeType<Type>;
        temp = first;
        first = first->link;
        last->link = first;
        cout << "The node has" << deleteItem<< " was deleted! " << endl;
        delete temp;
        return;
}
else                                             //cas3,case4.需要查找后定位。
{
        current = first->link;
        while( !found && current != first)
        {
               if( current->info == deleteItem )
               {
                      found = true;
                      break;
               }
               else
               {
                      trailCurrent = current;
                      current = current->link;
               }
        }// end while
 
        if(found)
        {    
               temp = new nodeType<Type>;
               if(current == last)                        //case3
               {
                      temp = last;
                      trailCurrent->link = last->link;       //last->link = first
                      last = trailCurrent;
               }
               else
               {
                      temp = current;
                     trailCurrent->link= current->link;
               }
               cout << "The Elem : " <<deleteItem << " was deleted! " << endl;
               delete temp;
        }
        else
        {
               cout << "The Elem : " <<deleteItem << " was not Exist in the List! " << endl;
        }
}//end else
}

四、有序链表

注意:此处有序链表无非是在之前的一、单链表的操作的基础上,在插入元素的时候,按顺序插入,考虑的排序。

为了体现有序的特点,特通过递归实现了有序链表的逆序打印。关于有序链表或者链表的非递归实现,可以通过栈实现。下一节会分析并实现。

1.有序链表的插入

考虑以下三种情况:

1) 当前链表为空;

2) 当前链表非空,要插入的元素值小于头结点的元素值;

3) 当前链表非空,要插入的元素值大于头结点的元素值,可以考虑找到第一个大于其的元素则停止搜索,插入其前即可。

template<typename Type>
void orderedLinkedListType<Type>::insertNode(constType& newItem)
{
nodeType<Type>* current;
nodeType<Type>* trailCurrent;
nodeType<Type>* newNode;
 
bool found = false;
 
newNode = new nodeType<Type>;
newNode->info = newItem;
newNode->link = NULL;
 
if(first == NULL)                           //case1:链表为空.
{
        first = newNode;
        last = first;
}
else
{
        current = first;                     
        while( !found && current != NULL)       //循环查找
        {
               if(current->info >= newItem)
               {
                      found = true;
                      break;
               }
              else
               {
                      trailCurrent = current;
                      current = current->link;
               }
        }//end while
 
        //first 特殊处理..
        if(current == first)                //case2:新插入的元素小于first节点的元素值..
        {
               newNode->link = first;         
               first = newNode;
        }
        else //其他..
        {
               newNode->link = current;       //case3:新插入的节点在非first位置
               trailCurrent->link = newNode;
        }
}//end else
}

2.      递归实现有序链表的逆序打印

template<typename Type>
voidorderedLinkedListType<Type>::printListReverse() const   //逆序打印.
{
     reversePrint(first);
     cout << endl;
}
 
//递归实现单链表的逆序打印.
template<typename Type>
voidorderedLinkedListType<Type>::reversePrint(nodeType<Type>* current)const  //逆序打印
{
if(current != NULL)
{
        reversePrint(current->link);
        cout << current->info << "\t";
}
}

作者:铭毅天下

原文:https://blog.csdn.net/laoyang360/article/details/7866886

上一篇:UVa 10520【递推 搜索】


下一篇:常见的几种语言C,C#,JAVA,Python的运行原理