链表的尾插

在讲链表之前,我们不如抛出一个问题:

假如要创建一个电影的合集

里面只包含电影的名字;

我们当然可以创建一个结构体数组进行储存,但他想存多少就能存多少吗?

当寨被塞满了,又怎么弄嘞?

有人说可以内存分配,使用malloc函数;

我认为没错,但是那样同样站很多内存,那有没有不那么占内存又可以当结构体数组用得嘞?

答案是有的

那便是链表。

下面我就来介绍一种构造链表的方法。

链表的尾插:

首先我们要简单的介绍一下链表的构造原理;

我们首先构造一个含有数据的结构体我们命名结构体中的数据叫做数据域。

然后再在结构体里添加结构体指针叫做指针域。

看到这里有人说为啥要加指针而且要加结构体指针?

我们上面有说过结构体数组占位置。所以我们要采取一种不占位置的连接方式。

然后这种连接方式就要用到指针。

假如我们有两个代有数据的结构体连接 如图。

链表的尾插

 我们用前面的结构体的指针域指向后一个结构体。

这样的话,我们只要找到前面的一个结构体通过它的指针域便能找到下一个结构体。

然后如果我们有第三个结构体我们可以同过用第二个结构体(节点)的指针域指向的三个结构体。

现在我们思路有了。

那么怎么实现嫩?

首先我们需要一个结构体模板

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

然后我们要创建一个指针(head)做一个链表的开头。

typedef struct note{
    int data;
    struct note *next;
}node;
node *head;

然后我们就可以进行连接了

首先我们创建一个连接结构体的函数命名为last

没有返回值,所以void即可。

在函数里面我们要给于head内存用于存数据。

void last(){
    head=(node*)malloc(sizeof(node));
}

又因为head里面有存在指针所以我们要进行初始化。

不然它就是一个野指针。

我们要找到链表首先是找head对吧?

所以head是不能动的。

所以我们要建一个其他指针(p)用来代替head进行后面的操作。

假设我们要输入n个数据

我们就需要一个循环循环输入。

如果我们只有一个数据当然只要一个head就行。

但是我们需要n个数据。

但是只有head(p)显然是不能进行连接操作的

所以我们就需要另一个代有内存的结构体(r)经行连接

然后我们不能有n个数据就创建n个结构体吧?

所以(r)就要重复使用。

所以也解释了为啥要循环

思路有了直接上代码

 

typedef struct note{
    int data;
    struct note *next;
}node;
node *p,*head,*r;
int n;
void last(){
    head=(node*)malloc(sizeof(node));//为head开辟内存 
    head->next=NULL;// 初始化指针 
    p=head;//用p代替head进行操作 
    for(int i=0;i<n;i++){
        r=(node*)malloc(sizeof(node));//为r开辟内存 
        r->next=NULL;//初始化r的指针 
        scanf("%d",&r->data);//向r里输入数据 
       p->next=r;//然后p(head)的数据域指向r 
        p=p->next;//然后移动p(此处head没有移动),p便移动到了r上 
    }
}

为方便理解

这里在放一个例题

链表的尾插

 

代码如下

#include<stdio.h>
#include <stdlib.h>
typedef struct note{
    int data;
    struct note *next;
}node;
node *p,*head,*r;
int n;
void last(){
    head=(node*)malloc(sizeof(node));
    head->next=NULL;
    p=head;
    for(int i=0;i<n;i++){
        r=(node*)malloc(sizeof(node));
        r->next=NULL;
        scanf("%d",&r->data);
       p->next=r;
        p=p->next;
    }
}
int main(){
    node *p1,*d;
    scanf("%d",&n);
    last();
    int x,y;
    scanf("%d %d",&x,&y);
    for(p1=head->next;;p1=p1->next){
        if((p1->data)<x||(p1->data)>y){
            printf("%d",p1->data);
            break;
        }
    }
     for(p1=p1->next;;p1=p1->next){
        if((p1->data)<x||(p1->data)>y){
            printf(" %d",p1->data);
        }
         if(p1->next==NULL)
            break;
    }
    return 0;
}

说是删除我为了偷懒只是没有输出范围里的数据

下个星期我会介绍链表的删除。

这也是链表的好处。

关于typedef我也解释不清推荐看看下面的文章

(18条消息) typedef介绍_liitdar的博客-CSDN博客_typedef

上一篇:《C语言深度剖析》第二章 符号详解 p1 C语言从入门到入土(进阶篇)


下一篇:android Fragment的数据传递