数据结构——创建一个带头节点的单链表(C语言)

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

写在前面

最近正在学习数据结构中的单链表看书(《数据结构(第二版)》下称课本)的时候理解的挺快的。直到自己敲的时候才发现笔者看懂的只是书上的类C语言且个人觉得书上的各个基本操作的实现表现得较为简略导致自己去实现的时候一塌糊涂。笔者认为最难的是创建单链表后结点数据在其中的存储以及结点之间逻辑关系的存储。

写此博客录笔者实现单链表的历程。此篇是第一篇也是第一步创建带头结点的单链表,且可输入数据。

注:笔者刚上大一学习c语言没多久内容比较基础表达没那么专业到位更多的是帮助自己记录思路,如有错误欢迎指正。

实现

思路

创建结构体变量

定义一个链表

创建头结点

创建新结点

打印链表

具体步骤文末有具体代码及运行效果

创建结构体

typedef struct node

{

int data;//数据域

struct node *next//指针域

}LNode*LinkList//命名原因如下出自课本

笔者的理解LNode表示结点个数不限LinkList表示指向头结点的指针仅有一个。

此时结构体变量创建完成。

定义一个链表

LNode* list;

定义一个LNode类型的list指针变量用于在函数之间的传递以储存单链表的每一次改动。

创建头结点

list=createhead()//创建的头结点赋值给list链表

LNode* createhead()

{

LinkList L;//创建头指针

L=(LinkList)malloc(sizeof(LinkList));//为头结点开辟空间L作为头指针指向这块空间

L->next=NULL;//空链表的尾指针指向空

return L;//将L返回

}

此时list为一个有头结点的空链表。

创建新结点

createnode(list);//将list传进去此时list是个指针传的是单链表的首地址在函数内部就可改变它

void createnode(LinkList L)//此处将形参命名为L且类型为LinkList意在提示我们传过来的是指

//向头结点的指针

{

//开辟新结点

LNode* new=LNode*malloc(sizeof(LNode));

//安置new的数据域

int data1;

printf("请输入要放入的值");

scanf("%d",&data1);

new->data=data1;

//安置new的指针域此处使用前插法后有解释以及后插法的具体实现

new->next=L->next;//L的指针域赋值给new即new指向NULL

L->next=new;//L指向new

}

//由下图不难看出其关系

至此一个可以存储数据及逻辑关系的单链表已创建完成。

*****下面解释一下前插法与后插法的区别

首先要明确一点每次将单链表传到函数内部单链表都是从头结点开始访问各个元素的这取决于单链表的有序存储结构。

前插法每次进去新的结点都是插在头结点后面成为新的首元结点而链表的访问又是从头结点开始的则使用前插法会比较方便。

而后插法每次都要插在尾结点的后面成为新的尾结点。这就需要我们每次调用时都找到当前尾结点的所在之处。故需要加入一个函数实现遍历的功能。

后插法版本的createnode

void createnode(list)

{

LNode* new=LNode*malloc(sizeof(LNode));

//安置new的数据域

int data1;

printf("请输入要放入的值");

scanf("%d",&data1);

new->data=data1;

//安置new的指针域此处使用后插法

LNode *tail;//t用来遍历,tail定位尾指针

tail=search(L);

tail->next=new;

new->next=NULL;

tail=new;

}

由下图不难看出。

LNode* search(LinkList L)

{

LNode *p=L;

while(p->next)

p=p->next;

return p;

}

*以下细微差距第二种方法会让tail为nullptr造成非法访问*

*逻辑上没有太大问题但是仔细分析是有问题的*

打印链表

即遍历

void print(LinkList L)

{

LNode *p=L->next;//不指向L因为L的数据域没数据就不必输出

while(p)

{

printf("%d",p->data);

p=p->next;

}

此时单链表的创建已全部完成以下是顺序完整的代码用前插法演示

typedef struct node
{
    struct node* next;
    int data;
}LNode,*LinkList;
#include <stdio.h>
#include <stdlib.h>
LNode* createhead()
{
    LinkList L = (LinkList)malloc(sizeof(LinkList));
    L->next = NULL;
    return L;
}
void createnode(LinkList L)
 {
        LNode* new = (LNode*)malloc(sizeof(LNode));
        int data1;
        printf("请输入要放入的值");
        scanf("%d", &data1);
        new->data = data1;
        new->next = L->next;
        L->next = new;
}
void print(LinkList L)
{
    
        LNode* p = L->next;
        while (p)
        {
            printf("%d\n", p->data);
            p = p->next;
        }
    
}
int main()
{
    LNode* list;
    list = createhead();
    while (1)//此处加入死循环看看是否已经构建起单链表的逻辑结构了
    {
        createnode(list);
        print(list);
    }
}