[数据结构与算法]2021-10-27

链表的尾插法和头插法

头插法

链表其实和数组是差不多的(自己理解)，数组是提前申请好内存而链表是边输入边加内存，所以链表能够更好的利用内存空间。

指针包括数据域和指针域 数据域用来存储数据 指针域用来存储下一个指针的位置

1.首先我们先申请一个头结点head 然后申请一个p节点来代替head的使用

2.确定好输入n

3.在申请一个中间节点s 输入s->data 并让s->next=NULL

4.(重点) 这意思是将p节点和s节点连接起来

p->next相当于在链表中申请一个空间

然后p=s将p移动到s位置 而此时 head中的data依然是0(这边已经给附初始值为10)

循环之后又申请一个新的节点在赋值给p然后一直移动

简单的说就是申请一个新的节点插在head后边而head不发生改变

#include<stdio.h>
#include<stdlib.h>

struct node{
    int data;
    struct node *next;
};

int main()
{
    int n;
    scanf("%d",&n);
    struct node* head = (struct node*)malloc(sizeof(struct node));
    head->next = NULL;
    struct node* p;
    head->data=10;
    p=head;
    
    for(int i=0;i<n;i++)
    {
        struct node* s = (struct node*)malloc(sizeof(struct node));
        
        scanf("%d",&s->data);
        
        s->next=NULL;
        
        p->next=s;
        
        p=s;
    }
    
    p=head;
    printf("%d ",p->data);
    while(p->next!=NULL)
    {
        printf("%d ",p->next->data);//跳过heada的data也就是10
        p=p->next;
    }
    return 0;
}

输出

头插法

头插法和尾插法是一样的

1.首先我们先申请一个头结点head 这边不用申请p节点来代替head了

2.确定好输入n

3.在申请一个中间节点s 输入s->data 并让s->next=NULL

4.(重点) 这意思是将head节点和s节点的next都指向NULL

像这样

然后head在指向s head->next=s;

然后就重复操作就好

#include<stdio.h>
#include<stdlib.h>

struct node{
    int data;
    struct node *next;
};


int main()
{
    int n;
    scanf("%d",&n);
    struct node* head = (struct node*)malloc(sizeof(struct node));
    head->next = NULL;
    struct node* p;
    head->data=10;
    p=head;
    
    for(int i=0;i<n;i++)
    {
        struct node* s = (struct node*)malloc(sizeof(struct node));
        
        scanf("%d",&s->data);
        
        s->next=NULL;
        
        s->next = head->next;
        head->next = s;
        
    }
    
    p=head;
    printf("%d ",p->data);
    while(p->next!=NULL)
    {
        printf("%d ",p->next->data);
        p=p->next;
    }
    return 0;
}

输出