数据结构面试之二——双向链表表、循环链表、有序链表的常见操作
题注:《面试宝典》有相关习题,但思路相对不清晰,排版有错误,作者对此参考相关书籍和自己观点进行了重写,供大家参考。
二、双向链表
双向链表的建立是在单链表的基础上,多了一个指向前驱的指针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"; } }