当前位置：首页 > article >正文

链表？-＞？（以尾插法说明，附头插法）

article 2024/11/30 8:34:08

这篇文章做一些关于初学链表的一些问题的解答。

我知道有些朋友只是需要一份完整的关于链表的代码，我会附在后面，大家直接划到最后就好。

一、创建链表

(1

相信所有搜索过链表创建的朋友都看过这样一行：

struct Line* head = (struct Line*)malloc(sizeof(struct Line));

什么感受？我第一次看到这比命都长的一行我直接就想放弃了。没关系啊，现在我来详细解答：

1.涉及到的一个函数和一个运算符我们先提取出来malloc( )和sizeof( )

malloc( )：

这是一个动态分配内存的函数，就例如一个班有40名同学，我就需要开辟出一个空的教室刚好能坐下40名同学，并且要把这个教室的位置告诉我。那这样就很明显了，我需要传入的参数就是告诉这个函数我需要多大的空间，那返回给我的就肯定不是什么return 0，而是一个地址，也就是指针来告诉这个空间的位置。

注意：malloc返回的指针类型是一个无类型指针(void *)，后面要考！！！

sizeof( )：

这是一个计算占用内存大小的运算符，就例如我告诉他3班，他就能自动说明3班的人数是40人。那这样也很明显了，我需要传入的参数就是一个类型，那返回给我的就是一个告诉我空间大小的整形数，比如

int //4个字节
char //1个字节

2.类型

前面的malloc返回的是一个无类型指针(void *)，但是等号左边定义的类型却是结构体指针(struct Line*)，那这样怎么办呢？我需要malloc( )给我传回的地址，但指针类型不一样又会报错。欸！指针就算类型不一样，但是占用的字节却是一样的，我只需要强制转换就行了！

/*给部分还没学类型转换的朋友补充一下
一般转换方法有3种：
强制转换 C
转换构造函数 C++
构造函数 C++
这里我们只需要用到强制转换
*/
int a=1;
double b=3.0;
int c;
c=a+b;
/*这样必定报错，很简单，你这又是int又是double，最后加起来还要是个int
那我们改一下：
*/
c=a+(int)b;
/*这样我们就强制把b从double类型转换成了int类型就没问题了*/

我们直接通过强制转换把无类型指针(void *)转换成需要的结构体指针类型(struct Line*)。

3.struct Line和struct Line*

其中struct Line只在sizeof里面出现过，这是因为，我们需要开辟的大小是我们定义的结构体的大小，而不是一个地址的大小，就例如，struct Line是一个教室本身，是存在的一片空间，但struct Line*只是这个教室的位置的信息，你可以用代号表达、用文字表达，而我们的代码语言选择用指针表达这一信息。

4.总结

这行代码的意思就是：

告诉sizeof( )一个struct Line类型计算占用空间，返回出的这个空间的大小交由malloc( )去开辟出这个大小空间，并返回出这个空间的位置，但是因为指针类型不同，用到了强制转换类型，最后赋值给head指针的这样一件事。

(2

->

这个符号熟悉吧？但是其实这个符号的解释网上是不容易的。

1.

这个只会出现在定义了结构体且还定义了结构体指针之后。

2.

如果我们需要调用结构体指针指向的结构体中的一个对象，我们该怎么做呢？

struct Line
{
    int data
    struct Line* next
};

struct Line A;
struct Line* B;

/*如果我们要调用A中的data，我们会怎么做?*/
int num1 = A.data;

/*如果我们要调用B中的data呢?*/
int num2 = (*B).data;
int num3 = B->data
/*也就是说如果定义的是结构体指针，以上两种方式相同*/

3.总结

->是一个结构指针调用该结构体中对象的方式

意思是用->左边的指针指向结构体，再调用结构体中右边的那个对象。

注：我们将如上B->data看作一个整体，这个整体就是data。下面哪个是对data赋值，哪个是调用data的值？

B->data = n;
n = B->data;

答案的顺序就是提问的顺序。

(3

1.关于头指针head（仅针对我这种写法）

struct Line* head = (struct Line*)malloc(sizeof(struct Line));
struct Line* p;
p=head;

这里只有head开辟出了一片存放结构体的空间，也就是说，现在head指向的结构体已经创建好了，但！p指针没有，p只是一个空指针，在复制后p才指向了与head相同的结构体。

其次，我这种写法head指针指向的结构体data没有实际意义，因为它不会存放任何你所输入的数据，这个我马上解释。

for(int i = 0; i < k; i++) //k是链表需要存放的数据的个数
{
    struct Line* s = (struct Line*)malloc(sizeof(struct Line)); 
    int my_data = 0; //my_data是你需要存放的一个数据
    std::cin >> my_data; //向my_data输入数据，相当于scanf()
    s->data=my_data;
    s->next=NULL;
    p->next=s;
    p=s;
}

我们存放数据的操作全在循环中进行，但是你会惊讶的发现，我们重新定义了一个结构体指针s并且为它开辟了一个新的结构体，并且现在才开始存放数据。

这样看来head以及head指向的结构体似乎没有什么存在的意义：

但是我这样做是为了保护head指向的结构体的稳定，就冲这一句话你就懂得head的重要性了，我们无论增删改查这个结构体，我们都需要先遍历结构体（也就是查找链表中的某个数据），遍历就需要从head指向的结构体开始逐个查找下一个，也正因如此head指针除非不再需要这个链表，否则无论如何都不能动它，也就是只能调用它，千万不能为它赋值。

2.关于p指针

p指针需要让它动起来才能发挥作用。p指针就像机械硬盘的那个磁头，而链表就是磁盘，磁头在磁盘上逐个遍历查找数据，而p指针在链表上逐个遍历查找数据。

因为链表的特性，p指针不能跳跃查找，只能逐个查找，遍历链表，也就是说运气不好甚至要遍历完整个链表。

p指针遍历方式：

p=head->next; //还记得吧，之前说的head指向的结构体不存放任何数据，所以赋值到head的下一个

/*第1种*/
for(int i = 0; i < k-1; i++)
{
    p=p->next;
}
int need = p->data; //need就是第k个数据

/*第2种*/
while(p->next!=NULL) //这里我后面在是s指针处解释
{
    p=p->next;
}
//遍历整个链表

3.关于s指针

首先，s指针定义的全部是存放数据的结构体。

其次，s指针在循环中定义！！！所以每次完成一次循环s不再存在，但每次s指向的结构体都挂在了链表上不会消失。千万不要忽视这个，确实很简单，但重要。

其实大家对s指针最不理解的应该是这一段

s->data=my_data;
s->next=NULL;
p->next=s;
p=s;

接下来，我拆开给各位朋友解释：

s->data=my_data; //第1行

向这一次循环时开辟的结构体中的data赋值；

s->next=NULL; //第2行

向这一次循环时开辟的结构体中的next指针赋值为NULL；

p->next=s; //第3行

理解这一句话千万不能想循环才进行第1次！要想这是第n次。

现在我告诉你，p指针指向的是这一次循环的上一次循环开辟结构体。等下解释。

那么这一行也就很好理解了，给p指向的结构体赋值s，那不就是把新开辟的结构体挂在p指向的结构体后面嘛。

p=s; //第4行

有了对第3行的说明，这一句也就显而易见了，为了保持创建链表时每一次p都指向链表的尾端（创建的s在实现第3句时都还没有挂在链表的尾端，而实现第3句挂上后又马上实现第4句重新让p指向链表尾端）

这也是上一句遗留的解释的原因。

(4 动画解释

二、代码

（1 尾插法输出按输入顺序

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

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

int main()
{
    int num=0;
    printf("请输入您需要插入的数据个数:");
    scanf("%d",&num);

    struct Line* head = (struct Line*)malloc(sizeof(struct Line));
    struct Line* p;
    p = head;

    for(int i = 0; i < num; i++)
    {
        struct Line* s = (struct Line*)malloc(sizeof(struct Line));

        int n=0;
        printf("请输入第%d个数:",i+1);
        scanf("%d",&n);

        s->data = n;
        s->next = NULL;
        p->next = s;
        p = s;
    }
/*以上为创建链表部分*/

    p = head->next;
    for(int i = 0; i < num; i++)
    {
        printf("第%d个数是:%d\n",i+1,p->data);
        p = p->next;
    }
/*此部分为输出链表所有数据*/
}

（2 头插法输出按输入倒序

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

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

int main()
{
    int num = 0;
    printf("请输入您需要插入的数据个数:");
    scanf("%d", &num);

    struct Line* tail = (struct Line*)malloc(sizeof(struct Line));
    struct Line* p;
    p = tail;

    tail->next = NULL;

    for (int i = 0; i < num; i++)
    {
        struct Line* s = (struct Line*)malloc(sizeof(struct Line));

        int n = 0;
        printf("请输入第%d个数:", i + 1);
        scanf("%d", &n);

        s->data = n;
        s->next = p;
        p = s;
        tail = s;
    }
    /*以上为创建链表部分*/

    for (int i = 0; i < num; i++)
    {
        printf("第%d个数是:%d\n", i + 1, p->data);
        p = p->next;
    }
    /*此部分为输出链表所有数据*/
}

根据这个性质可以实现一些函数题的逆序输出。

查看全文

http://www.kler.cn/a/415374.html