单链表之头插法_单链表头插法

1、前言：

什么是头插法？说白了头插法就是新增节的点总是插在头节点后面，然后大家可能会有疑惑，什么是新增节点，什么是头节点呢，下面请听俺娓娓道来。。。

2、预前准备：

头节点：一个队伍通常需要有一个标杆，就也是站在第一排举旗的那个人，头节点就相当于那个举旗的人，它不需要存放数据，只需起到标杆的作用，下面用 L 来表示头节点。

新增节点：相当于后面的小兵，手里需要拿着装备（数据域）和用来指向下一个小兵的位置（指针域），下面用 P 来表示新增节点。

数据域：用来存放用户的数据。

指针域：用来指向下一个节点的地址，注意是地址，而不是下一个节点的指针域。

p->next=p 与 p=p->next区别：p->next=p表示节点p的下一个节点还是p,如果链表只有p节点,那么这样就变成了一个循环链表
p=p->next表示修改指针p的位置,把p指向原来的下一个节点。

头插法的插入过程：

A

那么怎么实现呢？

3、实现过程

首先需要创建一个头节点，用来当标杆。

L = (LiskList)malloc(sizeof(LNode)) 

目的是在计算机内存中开辟一块LNode大小的空间，用来存放数据与指针。在Java 或 C++中就是 L = new LNode

最开始头节点的指针域不指向任何节点P（也就是指向NULL），即 L->next = NULL,数据域不存放任何数据，如图

开辟一块用来存放数据的节点P

P = (LiskList)malloc(sizeof(LNode))

当有元素插入时，将头节点的指针域放到新节点P后（P的指针域），如图：

P -> data = an
P -> next = L -> next //这里的 L->next是指头节点后面的所有节点，所以不能用 P->next = NULL来替代

然后将新节点P放在头节点后面，怎么接呢？

这么接，将新节点的地址赋值给头节点的指针域

L-> next = p

这样就完成了第一个节点的插入，之后节点的插入都是这样，为了看得更明显，咱们再接着插入第二个节点，怎么插呢？

同理在开辟一块内存空间用来存放数据，为了方便，这块空间的名字还叫P。

P = (LiskList)malloc(sizeof(LNode))

将 an-1 放在新开辟节点P的数据域中。

P -> data = an-1

现在链表的情况如图，头节点与an所在的节点相连着，an-1所在的节点还未连接。

然后我们将头节点后面所有的节点（目前只有an所在的节点）都接在新增节点P（an-1所在的节点）的后面。

并且因为an所在的节点的地址存放在L->next中，所以只需将L->next的值赋给P->next，这样便把an节点接到了an-1的后面

P->next = L->next

最后还需要将P节点插入到头节点的后面，之后循环如此这样便实现了头插过程。

L->next = P

 

4、代码实现：

//头插法创建单链表
LNode* List_HeadCreate(LNode* L,int a[],int n){
    LNode *s;//新增节点
    L = (LNode*)malloc(sizeof(LNode)); //为L开辟一处空间，或者在主函数中开辟也可以
    L->next = NULL;
    for(int i=0;i<n;i++){
        s = (LNode*)malloc(sizeof(LNode));
        s->data = a[i];//将新增节点存放上数据
        s->next = L->next;//连接s的后继
        L->next = s;//连接s的前驱
    }
    return L;
}

如果创建懂了那么插入、删除操作也就理解了。

5、完整代码：

#include<stdio.h>
#include <stdlib.h>
//define a struct 
//定义一个结构体，也就是节点
typedef struct Node {
	int data;                    // 存储链表数据
	struct Node *next;     		//  存储结点的地址
}LNode,*LinkList;
 
 
//头插法创建单链表
LNode* List_HeadCreate(LNode* L,int a[],int n){
    LNode *s;//新增节点
    L = (LNode*)malloc(sizeof(LNode)); //为L开辟一处空间，或者在主函数中开辟也可以
    L->next = NULL;
    for(int i=0;i<n;i++){
        s = (LNode*)malloc(sizeof(LNode));
        s->data = a[i];//将新增节点存放上数据
        s->next = L->next;//连接s的后继
        L->next = s;//连接s的前驱
    }
    return L;
}
 
//头插法插入元素
LNode* List_HeadInsert(LNode* head,int i,int num){ //插入元素到第i个位置,插入数num
    LNode *P;
    LNode *Q;
    P = head;//创建临时头节点
    int j = 0;
    while(j<i-1 && P!=NULL){  //寻找插入位置的前驱节点
        P =  P->next;
        j++;
    }
    if(j == i-1 && P!=NULL){  //头插法插入
        Q = (LNode*)malloc(sizeof(LNode));//创建将要插入的节点
        Q->data = num;
        Q->next = P->next;//第一步，连接Q的后继
        P->next = Q;//第二步，连接Q的前驱
    }
    return head;//返回链表首地址
}
 
//头插法删除指定位置元素
LNode* List_HeadDelete(LNode* L,int i) //删除第i个位置元素
{
    LNode* P;
    LNode* Q;
    P = L;
    int j=0;
    while (j<i-1 && P)
    {
        /* code */
        P = P->next;
        j++;
    }
    if(j == i-1 && P){
        Q = P->next;
        P->next = P->next->next;
        free(Q);
    }
    return L;
}
 
//主函数，给链表赋值并打印出链表
void main(){
    int arr[] = {1,2,3,4,5};
    int n = 5;
    LNode *L = NULL;
    L = List_HeadCreate(L,arr,sizeof(arr)/sizeof(arr[0]));
    L = List_HeadInsert(L,3,500);
    L = List_HeadDelete(L,6);
    while(L->next!=NULL){
        printf(" %d ",L->next->data);//算上头节点一共六个节点，并且头节点数据域为NULL，所以输出的第一个值应该为 L->next->data
        L = L->next;
    }
}

 

其中：

LNode *和 LinkList是等价的，只是要注意下面这样的变量声明：
LinkList P,Q; /*P,Q都是指针*/
LNode *P,Q;/*只有P是指针*/

6、、指针和引用的区别？

1、本质区别

本质： 指针指向一块内存，它的内容是所指内存的地址；而引用则是某块内存的别名，引用不改变指向

2、指针和引用作为函数参数进行传递时的区别
（1）指针传递参数本质上是值传递的方式，它所传递的是一个地址值。值传递过程中，被调函数的形式参数作为被调函数的局部变量处理，即在栈中开辟了内存空间以存放由主调函数放进来的实参的值，从而成为了实参的一个副本。值传递的特点是被调函数对形式参数的任何操作都是作为局部变量进行，不会影响主调函数的实参变量的值。
（2）引用传递过程中，被调函数的形式参数也作为局部变量在栈中开辟了内存空间，但是这时存放的是由主调函数放进来的实参变量的地址。被调函数对形参的任何操作都被处理成间接寻址，即通过栈中存放的地址访问主调函数中的实参变量。正因为如此，被调函数对形参做的任何操作都影响了主调函数中的实参变量。

 

看没看懂都点个赞呗 ~~~