顺序表的逆置vs单链表的逆置 带图解 众多方法汇总"/>
顺序表的逆置vs单链表的逆置 带图解 众多方法汇总
最近学习顺序表跟单链表,发现题目很多相似的东西,把题目中的东西提炼一下,做个两个表的逆置操作的算法总结,冲鸭~
*顺序表相对高效的算法 时间复杂度0(n),空间复杂度0(1)
*算法思想:扫描顺序表l的前半部分元素,对于元素l.data[i] (0<=i<=l.length/2),将其余后半部分对应元素l.data[l.length-i-1]进行交换
void Reverse1(Sqlist &L){
Elemtype temp;
for(i=0;i<length/2;i++){
temp=L.data[i];
L.data[i]=L.data[L.length-i-1];
L.data[L.length-i-1]=temp;
}
}
**带头结点的单链表就地逆置(1)
解法一:将头结点摘下,然后从第一结点开始,依次前插入到头结点的后面(头插法),直到最后一个结点为止。
void Reverse2(LinkList &L)
{LNode *p,*r;//p为工作指针,r为p的后继以防断链p=L->next;//从第一个元素结点开始L->next=NULL;//先将头结点L的next域置为NULLwhile(p!=NULL)//依次将元素结点摘下{r=p->next;//暂存p的后继p->next=L->next;//将p结点插入到头结点之后L->next=p;p=r;}return L;
}
**带头结点的单链表就地逆置(2)
*解法二:**通过若干操作将指针反转达到逆置的目的。
假设pre、p和r指向3个相邻的结点,如上图。pre之前的结点的指针都已经调整完毕,它们的next指针都指向其原前驱结点。现在令p结点的next域指向pre结点,注意到一旦调整指针的指向后,p的后继结点的链就断开了,为此用r来指向原p结点的后继结点。
处理第一个结点时,将其next域置为NULL,。处理最后一个结点后,将头结点的指针指向它。
void Reserve3(LinkList &L)
{LNode *pre,*p=L->next,*r=p->next;p->next=NULL;//处理第一个结点while(r!=NULL)//r为空,则说明p为最后一个结点{pre=p;//依次遍历p=r;r=r->next;p->next=pre;//指针反转}L->next=p;//处理最后一个结点return L;
}
解法三:还可以借助一个栈来实现,每经过一个结点时,将该结点放入栈中。
暂时还是小白?,不会写栈,到时候会的时候再来补写先把递归部分写了。
void R_Print(LinkList L){
if(L->next!=NULL){
R_Print(L->next);
}
print(L->data);
}
加油,早日升级成为数据结构算法大神吧
更多推荐
顺序表的逆置vs单链表的逆置 带图解 众多方法汇总
发布评论