数据结构面试之一——单链表常见操作

单链表常见操作

题注:

《程序员面试宝典》有相关习题,但思路相对不清晰,排版有错误,本文对此参考相关书籍和自己观点进行了重写,供大家参考。

1.查找链表元素

Step1:置查找标记bfound=false;判断链表是否为空,是,提示“不能查找空链表”;否,进入step2。

Step2:从链表头开始查找,判断(当前点的info是否与待查找元素值相等&&指针未指向末尾),是,“查找结束,bfound=true”,否,继续查找。

Step3:判断bfound= = true,是,“提示查找成功”,否,“提示查找失败”。

/查找单链表元素
template<typename Type>
void linkedlistType<Type>::search(const Type& searchItem)
{
       nodeType<Type> *current;
       bool found = false;
 
       if(first == NULL)                                          //1.空链表
       {
              cout << "WARNING: Can not search an empty list!" << endl;
              return;
       }
       else
       {
              current = first;
              while(!found && current != NULL)
              {
                     if(current->info == searchItem)
                     {
                            found = true;
                            break;
                     }
                     else
                     {
                            current = current->link;
                     }
              }
              if(found)
              {
                     cout << searchItem << " was found in the List! " << endl;
              }
              else
              {
                     cout << searchItem << " was not found in the List! " << endl;
              }
       }
}

2.删除链表元素值

Step1:置查找标记bfound=false; 判断链表是否为空,是,提示“不能对空链表进行删除操作”;否,进入step2。

Step2:判断待删除元素值是否与头节点元素值相等,是,调整头节点指针;否,进入step3。

Step3:判断链表中是否存在该元素,否,“提示元素不存在”;是,进入step4。

Step4:判定要删除元素是否与末尾节点元素值相等,是,调整末尾last指针;否,此时为中间节点,需要调整trailCurrent和Current指针的指向。

//删除单链表元素
template<typename Type>
void linkedlistType<Type>::deleteNode(const Type& deleteItem)
{
       nodeType<Type> *tempNode = new nodeType<Type>;
       nodeType<Type> *current = new nodeType<Type>;
       nodeType<Type> *trailCurrent = new nodeType<Type>;
       bool found;
      
       //链表为空 case1
       if(first == NULL)
       {
              cout << "Can not delete an empty List!" << endl;
       }
       else
       {
              if( first->info == deleteItem )
              {
                     //要删除的也是第一个节点(仅一个节点,或不止一个节点) case2
                     tempNode = first;
                     first = first->link;
                     if(first == NULL)
                     {
                            last = NULL;
                     }                         
                     delete tempNode;
              }
              else
              {
                     //先查找,后判断... case3
                     found = false;
                     trailCurrent = first;
                     current = first->link;
 
                     while((!found) && (current != NULL))
                     {
                            if(deleteItem  != current->info)
                            {
                                   trailCurrent = current;
                                   current = current->link;
                            }
                            else
                            {
                                   found = true;
                            }
                     }
 
                     if(found)
                     {
                            //能找到...
                            trailCurrent ->link = current->link;
 
                            if(current == last)
                            {
                                   last = trailCurrent; //case 3a
                            }
                            delete current;         //case 3b
                     }
                     //不存在该点...case4
                     else
                     {
                            cout << "The deleteItem is not Exist in the List! " << endl;
                     } //end else
              }//end else
       }//end else
      
}// end deleteNode

3.单链表逆置[迭代实现]

Step1:判断链表是否为空,是,提示“不能对空链表进行逆置操作“;否,进入Step2;

Step2:从第2个节点开始,依次将每个节点插入到第一个节点的前面,判断指针是否指向了链表尾部,是,返回头指针结束;否,继续迭代后面的链表元素。

template<typename Type>
nodeType<Type>* linkedlistType<Type>::reverseList()   //逆置单链表
{
       if(first == NULL)
       {
              cout << "Can't reverse empty List!" << endl;
       }
       else
       {
              nodeType<Type>* p = first;
              nodeType<Type>* q = p->link;
 
              while(q != NULL)
              {
                     p->link = q->link;
                     q->link = first;
                     first = q;
                     q = p->link;
              }
       }
       return first;
}

4.单链表排序[直接插入排序]

思路:分为以下几种情况:

1)  单链表为空;

2)  单链表非空,但仅含一个元素,无需排序已经有序;

3)  待插入元素小于头结点的元素;

4)  待插入元素为前已有序的中间的元素值;

5)  待插入的元素前所有元素都比其小,直接插到末尾。

分别用lastInOrder记录已经有序的最后一个节点,firstOutOfOrder第一个尚未排序(正待参与)排序的节点。current用于记录循环的节点,trailCurrent记录current前的节点。

template<typename Type>
void linkedlistType<Type>::sortList()     //单链表排序
{
       nodeType<Type>* current;
       nodeType<Type>* trailCurrent;
       nodeType<Type>* lastInOrder;
       nodeType<Type>* firstOutOfOrder;
 
       lastInOrder = first;
 
       //case1,表为空.
       if(first == NULL)
       {
              cout << "Can't Sort of empty List!" << endl;
              return;
       }
 
       //case2,表不为空,但表长为1,仅含1个元素.
       if(first->link == NULL)
       {
              cout << "The List Was Already ordered!" << endl;
              return;
       }
 
       while(lastInOrder->link != NULL)
       {
              firstOutOfOrder = lastInOrder->link;    
              //case3,要插入的元素小于第1个元素.
              if(firstOutOfOrder->info < first->info)
              {
                     lastInOrder->link = firstOutOfOrder->link;
                     firstOutOfOrder->link = first;
                     first = firstOutOfOrder;
              }
              else
              {    
                     trailCurrent = first;
                     current = first->link;
                     while(current->info < firstOutOfOrder->info)
                     {
                            trailCurrent = current;
                            current = current->link;
                     }
 
                     //case4,要插入的元素在前已有序元素的中间.
                     if(trailCurrent != lastInOrder)
                     {
                            lastInOrder->link = firstOutOfOrder->link;
                            firstOutOfOrder->link = current;
                            trailCurrent->link = firstOutOfOrder;
                     }
                     else
                     {
                            //case5,要插入的元素大于最后一个已经有序的元素.
                            lastInOrder = lastInOrder->link;
                     }//end else
              }//end else
       }//end while
}

5.单链表在不知道链表长度的前提下求链表中间节点的值。

思路:分以下几种情况:

1)  链表为空;

2)  链表非空,但仅有一个或两个节点;可以直接返回第一个节点的元素值。

3)  链表非空,但含有三个或三个以上的节点,可以通过定义两个指针,一个指针的跳步为2次的时候,另一个指针的跳步为1次,当跳至结尾时,另一个节点恰好在中间位置。

//不知道表长的前提下求单链表中间元素

template<typename Type>
Type linkedlistType<Type>::midValOfList()         
{
       nodeType<Type> *current;
       nodeType<Type> *halfCurrent;
 
       if(first == NULL)                                //case1,没有节点
       {
              cout << "链表为空!" << endl;
              return -1;
       }
       else if(first->link == NULL || first->link->link == NULL) //case2,仅一个节点或两个节点.
       {
              return first->info;
       }
       else                                   //case3,含有三个或三个以上的节点.
       {
              current = first;
              halfCurrent = current;
 
              while(current->link != NULL)
              {
                     current = current->link;
                     if(current->link != NULL)
                     {
                            if(current->link != NULL)
                            {
                                   halfCurrent = halfCurrent->link;
                                   current = current->link;
                            }//end if
                     }
              }//end while
              return halfCurrent->info;
       }//end else
}

6.单链表建立

思路:单链表的建立可分为根据插入新节点的位置的不同而分为两种,1:在链表末尾插入元素的建立方式;2:在链表前面插入元素建立链表的方式。

对应1末尾插入分为两步:

Step1:如果当前链表为空,则置first=last=newNode;否则,进入Step2。

Step2:插入新结点元素,修改last指针。

对于2链表first指针前插入:主要需要保证插入元素后,修正first节点即可。

//正向末尾插入
template<typename Type>
nodeType<Type>* linkedlistType<Type>::buildListForward()
{
       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->link = NULL;
 
              if(first==NULL)
              {
                     first = newNode;
                     last = newNode;
              }
              else
              {
                     last->link = newNode;
                     last = newNode;
              }
              cin >> num;
       }
       return first;
}
 
//反向表头插入,从前面插入...
template<typename Type>
nodeType<Type>* linkedlistType<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->link = first;
              first = newNode;
              cin >> num;
       }
       return first;
}

7.单链表的测量长度

思路:链表的长度等效为节点个数,指针非空则循环判断即可。

//求解链表长度
template<typename Type>
int linkedlistType<Type>::length()
{
       int count = 0;
       nodeType<Type> *current;
       current = first;
 
       while(current != NULL)
       {
              count++;
              current = current->link;
       }
       return count; //节点个数等效为长度.
}

8.单链表的插入

思路:链表的插入也同链表的建立一样分为前向、后向插入两种形式,注意first、last指针的指向问题。

//在前面插入
template<typename Type>
void linkedlistType<Type>::insertFirst(const Type& newItem)
{
       //last no use.
       nodeType<Type> *newNode = new nodeType<Type>;
       newNode->info = newItem;
       newNode->link = first;   //在前面加入...
       first = newNode;
}
 
//在后面插入元素...
template<typename Type>
void linkedlistType<Type>::insertLast(const Type& newItem)
{
       nodeType<Type> *newNode = new nodeType<Type>;
       newNode->info = newItem;
       newNode->link = NULL;   //在后面加入...
 
       if(first == NULL)
       {
              first = newNode;
              last = newNode;
       }
       else
       {
              last->link = newNode;
              last = newNode;
       }
}

后续陆续会有栈、队列、二叉树、图、排序、查找等的相关分析,希望大家关注!


作者:铭毅天下
来源:CSDN
原文:https://blog.csdn.net/laoyang360/article/details/7858469
版权声明:本文为博主原创文章,转载请附上博文链接!

上一篇:数据结构之线性表(顺序表、单链表、双链表)(四)


下一篇:redis哨兵