站在入门者角度理解链表—创建
初学链表的时候反反复复研读课本还是生涩难懂,个人认为最重要的是理解,理解,理解。看过很多前辈的博客,受益匪浅,感谢****平台,但有些好文章需要在理解的基础上去研读。这篇博客是对自己理解的一个梳理,也可以作为初学者入门的借鉴,初次创作,不足之处还请各位多多赐教。
首先要弄懂链表,一定要先掌握结构体指针等基础内容。这里就不讲解这一部分,接下来视为您已经很好地掌握了结构体指针这部分内容。我们已经学过数组,但是如果加入的元素个数超过了数组大小时,便不能将内容完全保存。这时就希望有一种储存方式能够自动扩大——链表。
万事开头难
理解掌握如何创建链表,接下来的插入、删除等等就不难懂。我们先看下创建好的链表图(上图),便于后面理解。链表中有头结点(头指针变量 head),这个指针变量保存的是一个地址,指向的是头节点(也就是说头指针指向一个变量,这个变量称作元素)。链表中每一个元素(节点)包括数据部分与指针部分(data与next),next指向下一个元素,最后一个元素的指针指向NULL(表示地址为空)。可以想象成铁链,一环扣一环。
到这里,你心里大概有了对链表的感性的认识,那现在你要问了,我们如何实现呢?别急,我们先理解如何构造这么一个元素(也就是节点的data与next放在哪里呢?),这里就要用结构体了。话不多说,先看代码:
typedef struct student
{
//下面name与number就是data部分
char name[10];
int number;
//这是next指针部分
struct student* next;
}Linklist;
请看上面的代码,如果你C语言学的不扎实你又要问typedef什么意思,这里说下,typedef是将struct student 结构体类型重新定义为Linklist类型。在以后的代码中看到Linklist你就要知道它是一个student的结构体,也可以说 Linklist代替了struct student目的为了简化代码,便于阅读。那指针为什么是 结构体类型呢? 因为它要指向的类型也是 struct student 的类型。
接下来我们就要认识几个在创建链表时要用到的函数:
malloc函数:
原型是:void *malloc(unsigned int size),功能是在内存中动态地分配一块size大小的内存空间,然后会返回一个指针,该指针指向分配的内存空间,如果出现错误返回NULL。
calloc函数:
原型是:void *calloc(unsigned n,unsigned size),功能是动态分配n个长度为size的连续存储空间数组。然后会返回一个指针,该指针指向分配的内存空间,如果出现错误返回NULL。
free函数:
原型是: void free (void *prt),功能是使用由指针ptr指向的内存区,使得部分内存区可以被其他变量使用。ptr是最近一次调用calloc或者malloc返回的值。free无返回值。(你可以理解为它是用来释放空间的函数)
相关的函数已经介绍完了,什么?还不懂!没关系,后面用到再来看。现在就要正式启动我们浩瀚的工程了——如何建立动态的链表。
在程序运行中从无到有地建立起一个链表,即一个一个分配节点的内存空间,然后输入节点中的数据建立节点间的相连关系(核心)
接下来是围绕这个核心思路去创建我们的链表,这里有几个关键词可以牢记:一个一个,分配,输入,建立关系。后面我们就围绕这几个关键词来进行创建。
我们的故事背景是:创建一个班级里的学生作为节点的链表,然后将学生信息打印出来。
首先要创建节点结构(上面我们已经讲过,不多说,看代码!)
typedef struct student
{
char name[10];
int number;
struct student* next;
}Linklist;
然后定义一个create的函数,用来创建链表,该函数会返回头指针。(看代码解释)
int count;
Linklist* Create() //这个函数是要返回 链表指针的,所以类型要是Linklist*
{
Linklist *head=NULL; //头指针一开始指向NULL
Linklist *last,*p; //这里定义了两个指针,last指向最后那个节点,p是新创建出来的,它要被链接
count=0; //初始化链表长度
p=(Linklist*)malloc(sizeof(Linklist));//这里就用到了分配空间的函数,sizeof是获取一个
//Linklist类型的数据的内存大小,强制转换为链表指针
last=p; //第一个节点也是最后一个节点,last指向它
//这里就是输入数据给第一个节点
printf("please first enter name,then number!");
scanf("%s",&p->name);
scanf("%d",&p->number);
//当输入number学号为0时就结束链表的创建
while(p->number!=0)
{
count++;
if(count==1) //第一次新加的节点,只会被执行一次
{
p->next=NULL;//我们让新增加的节点的指针指向空
last=p; //新增加的变成最后一个节点,让last指向新增节点
head=p; //头指针指向第一个节点
}
else //否则:接下来还要增加节点(显然不是第一个了)这里先跳过else里面的代码
//回头在反过来读
{
p->next=NULL;//因为p是新增加的节点(也就是最后一个节点)所以指向空
last->next=p;//last是上一个的最后的节点,也就是新增节点的前面一个,让她指向新增节点
last=p; //新增节点已经进来了,那么它将成为最后一个节点,last指向它
}
p=(Linklist*)malloc(sizeof(Linklist));//又新增了一个节点
//又是同样的输入数据,接下来就返回到else里面的代码
printf("please first enter name,then number!");
scanf("%s",&p->name);
scanf("%d",&p->number);
}
free(p);//前面提到了,用来释放没有用到的空间,知道就行
return head;//一定要返回指针,它是一个链表的开始,头,首领。有了它,后面的士兵(节点)就任由
// 我们差遣
}
这样做,已经创建好了一个学生链表。什么?你不知道怎么用它。好吧,接下来,我们使用链表然后打印出来一些data里面的信息。(输出链表)
//注意:读代码从main开始
void Print(Linklist *head)
{
Linklist *item=head; //循环用的临时指针,从首领开始
int index=1; //定义节点序号
printf("------The LinkList has %d members-----\n",count);
while(item!=NULL) //不是最后一个节点就打印
{
printf("the NO %d member is:\n",index);
printf("the name is :%s\n",item->name);
printf("the number is:%d\n",item->number);
item=item->next; //指向下一个节点
index++; //序号自增
}
}
int main()
{
Linklist *head; //这个就是我们刚才说的链表的首领,头头,已经定义好了
head=Create(); //调用刚才千辛万苦创建的函数,返回首领 指针
Print(head); //传入的是 首领指针
return 0;
}
运行截图:
现在你可以松一口气了,我们已经完成了创建链表,使用链表,接下去你还要继续学习到链表的相关操作,例如(插入操作,删除操作,等等)。博主水平不高,难免有疏忽,错误,还望各位前辈,同行改正赐教,谢谢!哎呀,食堂快没菜了,博主该去吃饭了。后续更新 。。。