1单链表常见操作.docx
- 文档编号:12636351
- 上传时间:2023-06-06
- 格式:DOCX
- 页数:15
- 大小:17.29KB
1单链表常见操作.docx
《1单链表常见操作.docx》由会员分享,可在线阅读,更多相关《1单链表常见操作.docx(15页珍藏版)》请在冰点文库上搜索。
1单链表常见操作
数据结构面试之一——单链表常见操作
题注:
《程序员面试宝典》有相关习题,但思路相对不清晰,排版有错误,本文对此参考相关书籍和自己观点进行了重写,供大家参考。
1.查找链表元素
Step1:
置查找标记bfound=false;判断链表是否为空,是,提示“不能查找空链表”;否,进入step2。
Step2:
从链表头开始查找,判断(当前点的info是否与待查找元素值相等&&指针未指向末尾),是,“查找结束,bfound=true”,否,继续查找。
Step3:
判断bfound==true,是,“提示查找成功”,否,“提示查找失败”。
/查找单链表元素
template
voidlinkedlistType
:
search(constType&searchItem)
{
nodeType
boolfound=false;
if(first==NULL)//1.空链表
{
cout<<"WARNING:
Cannotsearchanemptylist!
"< return; } else { current=first; while(! found&¤t! =NULL) { if(current->info==searchItem) { found=true; break; } else { current=current->link; } } if(found) { cout< "< } else { cout< "< } } } 2.删除链表元素值 Step1: 置查找标记bfound=false;判断链表是否为空,是,提示“不能对空链表进行删除操作”;否,进入step2。 Step2: 判断待删除元素值是否与头节点元素值相等,是,调整头节点指针;否,进入step3。 Step3: 判断链表中是否存在该元素,否,“提示元素不存在”;是,进入step4。 Step4: 判定要删除元素是否与末尾节点元素值相等,是,调整末尾last指针;否,此时为中间节点,需要调整trailCurrent和Current指针的指向。 //删除单链表元素 template voidlinkedlistType : deleteNode(constType&deleteItem) { nodeType nodeType nodeType boolfound; //链表为空case1 if(first==NULL) { cout<<"CannotdeleteanemptyList! "< } else { if(first->info==deleteItem) { //要删除的也是第一个节点(仅一个节点,或不止一个节点)case2 tempNode=first; first=first->link; if(first==NULL) { last=NULL; } deletetempNode; } 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;//case3a } deletecurrent;//case3b } //不存在该点...case4 else { cout<<"ThedeleteItemisnotExistintheList! "< }//endelse }//endelse }//endelse }//enddeleteNode 3.单链表逆置[迭代实现] Step1: 判断链表是否为空,是,提示“不能对空链表进行逆置操作“;否,进入Step2; Step2: 从第2个节点开始,依次将每个节点插入到第一个节点的前面,判断指针是否指向了链表尾部,是,返回头指针结束;否,继续迭代后面的链表元素。 template nodeType : reverseList()//逆置单链表 { if(first==NULL) { cout<<"Can'treverseemptyList! "< } else { nodeType nodeType while(q! =NULL) { p->link=q->link; q->link=first; first=q; q=p->link; } } returnfirst; } 4.单链表排序[直接插入排序] 思路: 分为以下几种情况: 1) 单链表为空; 2) 单链表非空,但仅含一个元素,无需排序已经有序; 3) 待插入元素小于头结点的元素; 4) 待插入元素为前已有序的中间的元素值; 5) 待插入的元素前所有元素都比其小,直接插到末尾。 分别用lastInOrder记录已经有序的最后一个节点,firstOutOfOrder第一个尚未排序(正待参与)排序的节点。 current用于记录循环的节点,trailCurrent记录current前的节点。 template voidlinkedlistType : sortList()//单链表排序 { nodeType nodeType nodeType nodeType lastInOrder=first; //case1,表为空. if(first==NULL) { cout<<"Can'tSortofemptyList! "< return; } //case2,表不为空,但表长为1,仅含1个元素. if(first->link==NULL) { cout<<"TheListWasAlreadyordered! "< return; } while(lastInOrder->link! =NULL) { firstOutOfOrder=lastInOrder->link; //case3,要插入的元素小于第1个元素. if(firstOutOfOrder->info { lastInOrder->link=firstOutOfOrder->link; firstOutOfOrder->link=first; first=firstOutOfOrder; } else { trailCurrent=first; current=first->link; while(current->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; }//endelse }//endelse }//endwhile } 5.单链表在不知道链表长度的前提下求链表中间节点的值。 思路: 分以下几种情况: 1) 链表为空; 2) 链表非空,但仅有一个或两个节点;可以直接返回第一个节点的元素值。 3) 链表非空,但含有三个或三个以上的节点,可以通过定义两个指针,一个指针的跳步为2次的时候,另一个指针的跳步为1次,当跳至结尾时,另一个节点恰好在中间位置。 //不知道表长的前提下求单链表中间元素 template TypelinkedlistType : midValOfList() { nodeType nodeType if(first==NULL)//case1,没有节点 { cout<<"链表为空! "< return-1; } elseif(first->link==NULL||first->link->link==NULL)//case2,仅一个节点或两个节点. { returnfirst->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; }//endif } }//endwhile returnhalfCurrent->info; }//endelse } 6.单链表建立 思路: 单链表的建立可分为根据插入新节点的位置的不同而分为两种,1: 在链表末尾插入元素的建立方式;2: 在链表前面插入元素建立链表的方式。 对应1末尾插入分为两步: Step1: 如果当前链表为空,则置first=last=newNode;否则,进入Step2。 Step2: 插入新结点元素,修改last指针。 对于2链表first指针前插入: 主要需要保证插入元素后,修正first节点即可。 //正向末尾插入 template nodeType : buildListForward() { nodeType intnum; cout<<"Enteralistofintegerendwith-999."< cin>>num; while(num! =-999) { //..add newNode=newnodeType newNode->info=num; newNode->link=NULL; if(first==NULL) { first=newNode; last=newNode; } else { last->link=newNode; last=newNode; } cin>>num; } returnfirst; } //反向表头插入,从前面插入... template nodeType : buildListBackward() { nodeType intnum; cout<<"Enteralistofintegerendwith-999."< cin>>num; while(num! =-999) { //..add newNode=newnodeType newNode->info=num; newNode->link=first; first=newNode; cin>>num; } returnfirst; } 7.单链表的测量长度 思路: 链表的长度等效为节点个数,指针非空则循环判断即可。 //求解链表长度 template intlinkedlistType : length() { intcount=0; nodeType current=first; while(current! =NULL) { count++; current=current->link; } returncount;//节点个数等效为长度. } 8.单链表的插入 思路: 链表的插入也同链表的建立一样分为前向、后向插入两种形式,注意first、last指针的指向问题。 //在前面插入 template voidlinkedlistType : insertFirst(constType&newItem) { //lastnouse. nodeType newNode->info=newItem; newNode->link=first;//在前面加入... first=newNode; } //在后面插入元素... template voidlinkedlistType : insertLast(constType&newItem) { nodeType newNode->info=newItem; newNode->link=NULL;//在后面加入... if(first==NULL) { first=newNode; last=newNode; } else { last->link=newNode; last=newNode; } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 单链表 常见 操作
![提示](https://static.bingdoc.com/images/bang_tan.gif)