单链表常见操作
题注:
《程序员面试宝典》有相关习题,但思路相对不清晰,排版有错误,本文对此参考相关书籍和自己观点进行了重写,供大家参考。
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
版权声明:本文为博主原创文章,转载请附上博文链接!