C语言写单链表的创建、释放、追加(即总是在最后的位置增加节点)

c/c++

浏览数:241

2019-7-8

AD:资源代下载服务

昨天周末给学妹讲了一些指针的知识,本来我对指针就是似懂非懂的状态,

经过昨天一讲,我对指针的学习就更深刻了果然给别人讲课也是学习的一个方法。

加上最近复习数据结构,发现我的博客里没有链表的博文,所以趁这时候加上一篇。

在此之前,我们先谈一下我要说的一些基本知识:

①函数参数为什么是双指针?

我们先写一下这么一个程序:

# include<stdio.h>
void Gai(int m)
{
    m=5;
}
int main(void)
{
    int a=1;
    Gai(a);
    printf("%d\n",a);
    return 0;
} 

那么我们可以得知,输出a的值是1,为什么我调用了函数,把a传进去,并没有变成5呢?这就是关键所在。

我总结一下,形参m只是实参a的一个赋值的变量,形参我们都知道是函数调用时候才分配内存单元,

当函数调用完毕后,形参就会被干掉了,所以上面程序可以这么理解:定义一个a变量,它的值为1,

当把a作为实参传进Gai这个函数时,系统会定义一个变量m,并且把a的值“1”赋给了m,然后又执行m=5。

所以,到整个程序结束,m=5,a=1,所以a的值根本就没有发生改变。

所以说,在main函数里,若想通过函数来改变变量的值,那是不可能的。

接下来我们把程序修改一下:

# include<stdio.h>
void Gai(int * m)
{
  *m=5;
}
int main(void)
{
  int a=1;
  Gai(&a);
  printf("%d\n",a);
  return 0;
}

通过运行后我们可以看到a的值此时变成了“5”。所以,我们可以总结:

若一个变量想通过函数来改变本身的值,将本身作为参数传递是不成功的,

只有传递本身的指针(地址)才能达到这样的效果。

所以后面我们创建链表时,传递的是双指针,这就是为什么参数是双指针的原因。

因为我之前也一直不明白,直到我昨天给学弟学妹们讲课的时候,我才恍然大悟,所以我也算很笨了,

所以在这里给大家总结一下,因为我在别的博客里,看到也有挺多人不理解为什么是双指针,现在希望能够帮助大家更容易理解一些。

②每一个变量的内存单元中都有自己的地址

为了好理解,我画图把它绑在一块,虽然可能物理结构上不是长这样,但逻辑上是长这样的,比如
    

int a=2; 

 int * p = &a;   

所以说,只要是变量它都会有自己的地址(指针),即使是指针变量。

然后,指针它就是用来存地址的,只有两部分,一部分是附带自己的地址,一部分是存别人的地址

③指针就是地址,地址就是指针,指针类型的变量它的值只用来装指针。

为什么我会说这句话呢。因为之前,在昨天为止,我那么久,居然一直都理解错了,也怪我太笨了哈哈。比如说定义了节点类型

typedef struct n
{
int data; //数据域
struct n * next; //指针域
} Node;

然后 Node * L;  我一直以为L是长这样子的

原来不是!!!  它不是!!  害死我了,以前我可纠结了好久了!!!太蠢了哈哈!!

原来我一直以为什么类型的指针就长什么样!!

不是的,其实它是什么类型的指针它就存什么样的地址。

所以L其实是长这样的:

 

总之这个坑,如果你们已经会的,可以笑一下我,如果也一样像我一样掉坑的,

希望看到这里后能及时填坑。这个大大大大大的坑,嗨呀,气死了。都怪以前没认真学指针。

以上就是今天的预备知识,接下来就开始学习单链表的简单操作了。我会用图来结合,

因为我一直强调图和代码结合,这样才能学好数据结构,这样才能对数据结构有形象的想法,

当然大神都是直接理解的,我就比较菜,就挖掘了自己的学习方法,嘿嘿。

单链表我采用了头指针和头结点的结构。

这次单链表的操作可能有些不一样,但原理都是一样的,或者说,把图理解了,代码也就理解了;

/*
参数:头指针的指针(双指针)
作用:初始化链表,使头指针指向一个新结点,
          这个新节点就是头结点
*/
void InitHead(Node * *pHead)

/*
参数:头指针,其实也是头指针的拷贝
作用:释放整个链表
*/
void Free_list(Node * pHead)

/*
参数:头指针,一个值
作用:往链表的末段追加val
*/
void append(Node * pHead,int val)

/*
参数:头指针
作用:遍历输出链表(跳过头结点)
*/
void Showlist(Node * pHead)

(一)初始化链表 

void InitHead(Node * *pHead) //为链表生成头结点 使头指针指向头结点
{
  *pHead = (Node *)malloc(sizeof(Node));
  if(*pHead == NULL)
  {
    printf("头结点分配失败,程序终止! \n");
    exit(-1);
  }
  (*pHead)->next=NULL;
}

在main函数里面定义:  Node * L = NULL; //定义一个指针,指向Node类型,其实也就是整个链表的头指针 

         然后调用       InitHead(&L); 

 图解如下:

*pHead = (Node *)malloc(sizeof(Node)); 

其实*PHead就是头指针L的值了,加*号就代表指针的值,也就是图中右边的部分。

malloc会申请一个结点,然后返回结点的首地址,其实这个新生成的结点是没有名字的,

为了方便理解,我们管它叫x  图解如下:

至于PHead?哈哈,等这个函数结束后,它就被会干掉了,所以到头来,它只为他人作了嫁衣,不过这也正是它存在的意义。

如果传递的是单指针的话,pHead作为盗版的头指针指向了那个新生成的结点,

然后函数结束后,它们的状态分别是:L  依然存在,什么也没变化。 pHead,被干掉,彻彻底底的没了,

至于新生成的结点,则是孤零零的在内存区里瑟瑟发抖,等待有缘人来指向它,

所以这就是为什么要用双指针的理由。用了双指针,L指向了新生成的结点,PHead被干掉,皆大欢喜。

(二)释放链表

void Free_list(Node * pHead) //释放链表
{
  Node * p;
  while(pHead != NULL)
  {
    p = pHead;
    pHead = pHead->next;
    free(p);
    p = NULL;
  }
}

因为在链表中生成的新节点是用malloc的,所以要用free把它回收,malloc和free是一夫一妻。

在这种小程序或许不free也没什么太大的问题,但以后做项目时如果不回收就麻烦大了,所以养成free的习惯。

图解如下:

 之后p就会变成 

然后free(p)就是把p指向的那个结点,也就是图中的头结点,给干掉,

而pHead也被函数结束后干掉,而L只拿着一个head的地址但却找不到人了;

这里的图是只有一个头结点时的释放,但即使有多个结点,也是一样的做法,你们可以自己画图模拟一下,加深记忆。

(三)向链表末端追加元素

void append(Node * pHead,int val)
{
  Node * r=pHead;
  Node * pNew = (Node *)malloc(sizeof(Node)); //生成新节点
  if(pNew == NULL)
  {
    printf("新节点分配失败,程序终止! \n");
    exit(-1);
  }
  pNew->data=val;
  pNew->next=NULL;

  while(r->next != NULL) //让尾指针循环直到最后一个节点
  {
   r=r->next;
  }
  r->next=pNew;
  r=pNew;
}

这个代码太长,有点难画图,我尽量吧,图示如下:

然后定义一个指针r,把pHead复制过去

为了方便理解,我把所有新生成的结点都叫做x。

 然后定义一个PNew指针指向新生成的结点x;然后赋值,并置为NULL

其实pNew->data就是x.data

然后这一句代码

while(r->next != NULL) //让尾指针循环直到最后一个节点
{
  r=r->next;
}

这是为了让r指针指向最后一个结点,

为什么是 r->next != NULL  而不是 r!=NULL; 这里是有区别的,因为我这种追加的方法是属于后插法。

总之就是根据图来写代码

r->next是这个

而r是这个

所以判断的时候,应该判断的是链表中的next;而不是判断r有没有指向谁;

接下来就是最后的连起来了。

r->next=pNew;
r=pNew;

r->next=pNew;//为什么这里它们明明是指向了PNew,但图中却指向x呢?

我这么理解不懂对不对,一个指针指向了一个结点,那么这个指针就相当于这个结点了

然后最后一个

(四)遍历输出链表

void Showlist(Node * pHead)
{
  pHead=pHead->next; //跳过头结点输出
  while(pHead!=NULL)
  {
    printf("%d ",pHead->data);
    pHead=pHead->next;
  }
}

最后一个就不画图了,相信大家也能看懂。

至此,整篇文章应该写完了。啧啧啧啧,去吃饭了。

有错请在下方评论,咱们一起进步。

谢谢~

 忘了贴完整代码了,测试你们自己测试一下,我这里测试结果无误

# include<stdio.h>
# include<stdlib.h>
typedef struct n
{
    int data;             //数据域
    struct n * next;   //指针域
} Node;
void InitHead(Node * *pHead)  //为链表生成头结点 使头指针指向头结点
{
    *pHead = (Node *)malloc(sizeof(Node));
    if(*pHead == NULL)
    {
        printf("头结点分配失败,程序终止! \n");
        exit(-1);
    }
    (*pHead)->next=NULL;
}
void Free_list(Node * pHead)  //释放链表
{
    Node * p;
    while(pHead != NULL)
    {
        p = pHead;
        pHead = pHead->next;
        free(p);
        p = NULL;
    }
}
void append(Node * pHead,int val)
{
    Node * r=pHead;
    Node * pNew = (Node *)malloc(sizeof(Node));  //生成新节点
    if(pNew == NULL)
    {
        printf("新节点分配失败,程序终止! \n");
        exit(-1);
    }
    pNew->data=val;
    pNew->next=NULL;

    while(r->next != NULL)  //让尾指针循环直到最后一个节点
    {
        r=r->next;
    }

    r->next=pNew;
    r=pNew;

}
void Showlist(Node * pHead)
{
    pHead=pHead->next; //跳过头结点输出
    while(pHead!=NULL)
    {
        printf("%d ",pHead->data);
        pHead=pHead->next;
    }
}

int main(void)
{
    Node * L = NULL;
    InitHead(&L);
    append(L,1);
    append(L,4);
    append(L,7);
    append(L,9);
    append(L,332);
    append(L,6);
    append(L,235);
    Showlist(L);
    Free_list(L);
    L=NULL;
    return 0;
}

  

作者:yellowgg