头插法
定义:输入的数据次序生成的链表节点次序相反,例如:按1,2,3顺序进行头插之后,最终排序却变成了3,2,1。简而言之就是逆序插入。
定义图解:
代码图解:
代码:(使用头插法建立单链表)
Linklist head_insert(Linklist &L){
LNode *s;
int x;
L=(Linklist*)malloc(sizeof(LNode));
L->next=NULL;
scanf("%d",&x);
while(x!=NULL){
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
s->next=L->next;
L->next=s;
scanf("%d",&x);
}
return L;
}
小结:头插通常应用于逆置。
头插防断链,如何理解?
分析:如图所示,若要将链表B头插进链表A中,此时p->next更改为A->next了,如果没有r指针,当头插完p当前所指结点后,B链表就断了,那么就无法将剩下的B链表结点插入到A链表中了,所以需要一个r指针,始终指向p的下一个结点,即r=p->next。
代码图解:
尾插法
定义:输入的数据次序生成的链表节点次序相同,例如:按1,2,3顺序进行头插之后,最终排序还是1,2,3。简而言之就是顺序插入。
定义图解:
代码图解:
代码:(使用尾插法建立单链表)
Linklist tail_insert(Linklist &L){
LNode *s;
int x;
Node *r=L;
L=(Linklist*)malloc(sizeof(LNode));
scanf("%d",&x);
while(x!=NULL){
s=(LNode*)malloc(sizeof(LNode));
s->data=x;
r->next=x;
r=s;
scanf("%d",&x);
}
r->next=NULL;
return L;
}
尾插法的特点:在表尾放置一个指针,不断都标记表尾。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)