|
头插法
定义：输入的数据次序生成的链表节点次序相反，例如：按1,2,3顺序进行头插之后，最终排序却变成了3,2,1。简而言之就是逆序插入。 定义图解：  代码图解：  代码：（使用头插法建立单链表）
Linklist head_insert(Linklist &L){
//准备工作
LNode *s; // s是指向待插入结点的指针
int x; // 传入结点中data的值
L=(Linklist*)malloc(sizeof(LNode));
// ❤创建L链表,
//malloc()函数为动态申请空间
//(Linklist*)为强制转化为Linklist类型
L->next=NULL; // L链表的头结点置空
scanf("%d",&x);
//以下核❤
while(x!=NULL){ // 输入的值不为空，就可以进行头插了
s=(LNode*)malloc(sizeof(LNode)); // 题目没给结点，所以需要申请
s->data=x; // s是个指针，需要指向一个值才能进行头插
s->next=L->next; // 头插法核❤
L->next=s;
scanf("%d",&x);
}
return L; // 头插完成，返回最终的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; // s为指向待插入结点的指针
int x; // 传入新结点s中的data值
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; //s尾插进链表，r不断标记尾结点
scanf("%d",&x);
}
r->next=NULL; // 单链表最后一个结点置空
return L;
}
尾插法的特点：在表尾放置一个指针，不断都标记表尾。
|