C++编程入门(二) 互动版

在线工具推荐: Three.js AI纹理开发包 - YOLO合成数据生成器 - GLTF/GLB在线编辑 - 3D模型格式在线转换 - 可编程3D场景编辑器

神马是链表

这一节要学习链表了, 要学习链表了, 要学习链表了 !!! 重要的事情说三遍。

链表是一种重要的数据结构,跟数组很相似。那为什么会出现链表呢?这就要从数组的缺点说起:

上图数组a前四个元素是从大到小排序的,要把a[2]和a[3]中的值往后挪,再把7赋值给a[2]才能5个元素都从大到小排列。操作将是:把a[2]的值临时存储在变量b中,把4赋值给a[4],把6赋值给a[3],把b(也就是8)赋值给a[2]。这里就可以看出来了,数组的插入和删除的操作需要移动其他的元素。当数组长度很大时,移动就很耗费时间了。用链表就不会这么麻烦了。下图展示了什么是链表:

链表也由多个结构变量组成,每个结构变量叫一个节点。重要的是每个节点中都有一个成员是指针,它指向下一个节点,这样就能串起来,像链子一样,所以叫做链表。

链表通常由一个称为头指针的指针变量指向首节点,首节点中有一个指针指向第2个节点,最后一个节点的指针为空指针NULL,表示链表结束了。

链表的插入操作,只需要改变指针的指向就行了。还是上例中的把节点5插入到节点2和节点3之间,操作如下图所示:

首先,把节点2的指针保存在临时指针变量p中,再让节点2指向节点5,把临时变量p赋值给节点5的指针,节点5的指针就指向节点3了,最后节点4的指针赋值为NULL,就完成了。不需要其他元素的移动。

链表的实现

按照上述说明,链表要包括两部分,一部分用来放数据,剩下一个是指针,指向下一个节点。下面我们就建立一个student类型的节点:

#include <iostream>
using namespace std;
struct student{
    int id;
    char name[20];
    float score;
    student \*next;
};
void main()
{
    student *head;
    student stu1={1,"xiaoming",59.5,NULL},stu2={2,"angelababy",61,NULL},stu3={3,"xiaohong",99,NULL};
    head=&stu1;
    stu1.next=&stu2;
    stu2.next=&stu3;
}

第3行开始是student类型的定义,注意第7行是指向student类型的指针,用于把节点串起来的。

第11行定义student类型的指针,从名字可以看出来我们把它作为头指针。第12行是新建了3个student类型的对象,把对象串起来之后,就成了链表,每个对象都叫做这个链表的一个节点。新建的3个student对象的指针成员都为NULL,这是链表还没串起来,我们只是把一个个节点做好了,下面就要将他们串起来了。

第13到15行就是串起来的操作,头指针指向第一个节点stu1,stu1的指针next指向第2个节点stu2,stu2的指针next指向第3个节点stu3,stu3的指针next还是NULL,说明链表到头了。

串起来之后,我们就可以通过head指针访问到链表的每个节点

在右侧代码框中编写程序:写一个建立链表的函数createList,先提示用户先输入学生的个数,然后循环输入学生的信息。(不会吗?下一节给你答案!)