0.3 指针和单链表在线视频

同学们，大家好

我是云南大学信息学院的教师孔兵

这一节我们介绍c语言当中

重要的派生数据类型---指针

通过c语言的学习我们知道

指针是一个变量

它同样需要分配一块存储空间

它的特点是它存储的内容是一个内存地址

指明内存当中的某个位置

这里我们要强调

指针是有类型的

指针总是由某一个类型所派生的

这点对我们理解指针的操作非常重要

首先看一例子

例子中声明了两个指向整型的指针p1和p2

第一句中

用一个取地址运算符把i1的地址赋值给p1

地址是300

所以p1中现在存着地址300

同理，p2存的110这样的一个地址

关注一下最后一个赋值语句

它的作用我们是清楚的

把p1所指的变量赋值给p2所指的变量

怎么理解*p1这个操作是如何实现呢

前面我们说过

变量的本质是内存的一块存储空间

这块空间才是变量

这样就可以理解*p1这个操作了

p1的内容指明了内存中一个起始地址

p1的类型说明了空间的大小

那么作为整型指针

*p1这个操作就是确定了

从起始地址开始的4个字节的空间

4个字节的空间就是一个整型变量的大小

就是一个整型变量

*p1赋值给*p2本质上就是2个整型变量的赋值

下面讨论指针使用当中的一些语法问题

在图中我们首先定义了一个结构体

包含两个成员x和y

用typedef给这个结构体取了一个类型名spot

随后我们又定义了一个结构体

它也包含两个成员，data和next

其中data的类型就是spot

这里有一个结构体的嵌套定义

在结构体中包含了另外一个结构体

next是一个指向struct Lnode的指针

指向自己本身的这个类型

后面的讨论中

我们就是依赖这个指针形成单链表

同样用typedef给这个结构体取了一个类型名叫Lnode

另外

定义了一个指向这样

结构体的指针类型的名字，linklist

下面我们声明几个变量

一个是linklist类型的变量p和q

它们是两个指向struct Lnode这样结构体的指针

声明了一个整型变量x1

两个Lnode的结构体变量e1和e2

下面关注操作当中的一些语法问题

首先看一下通过指向结构体的指针来使用结构体的成员

这里用到箭头操作符

如图所示，假设p是指向一个结构体空间的指针

结构体空间当中包含data和next两个成员

我们可以通过箭头操作符来存取结构体当中的成员

比如说q->date赋值给p->data

请同学注意

当使用箭头操作符来存取结构体成员的时候

箭头的左边一定是一个指向结构体空间的指针

箭头的右边一定是结构体成员的名字

其次是通过变量使用结构体的成员

e1是一个结构体的变量

可以通过点操作符来使用结构体的成员

e1.data被赋值e2.data

同样要强调的是

点操作符的前面一定是一个结构体的变量

点操作符的后面一定是一个结构体成员的名字

第2个赋值语句中

我们提到过p->data表示的是结构体当中data这部分

它描述了结构体的一个成员

或者准确的说，它描述了data对应的存储空间

这块空间本身是一个spot类型的结构体变量

所以通过点操作符可以存取它的成员x

再看一下对x的另一种存取方式

p是指向结构体的指针

根据刚才的讨论

*p是代表p所指的那一块存储空间

通过p中的地址给出这块空间的起始

通过p的类型知道这块空间的大小

那么*p确定了一块结构体的存储空间

本质意义上来说

*p就是一个结构体的变量

所以我们可以通过*p加点操作符

存取结构体中的一个成员data

同样道理

我们可以继续通过点x来操作data内部的一个成员x

好了，同学们

我们现在已经讲解了指针概念

下面我们将讲解单链表

在程序中获取数据存储空间的办法有两种

一种是静态声明，一种是动态申请

静态声明我们是比较熟悉的

就是通过数据类型加名字声明变量

用变量名来存取这块存储空间

动态申请是在程序执行的过程中

通过malloc函数来申请一块存储空间

因为是在程序执行的过程当中通过函数来申请空间

所以我们无法给这块空间命名

能使用它的唯一的方式就是通过指向这块空间的指针

当多次动态申请多块空间的时候

这些空间就需要组织起来

单链表是比较合适的组织方式

首先看一下定义

我们定义了一个结构体

包含两个成员date和next

data是整型，next是指向结构体自身的指针

typedef给这个结构体起了个类型名LNode

然后定义了一个指向结构体的指针类型名linklist

在后续讨论中

我们把这样的结构体称为单链表中的一个节点

节点图示的话，我们就把它画成两个部分

如图所示，第1个是data这个成员

第2个是next成员

随后声明了三个linklist类型的指针head，p和q

我们先看一下单链表的形态

单链表由多个节点组成

链表中第一个节点称为头节点

头节点不存数据

在链表中加一个头节点会给链表上的操作实现一些便利

我们后面会讨论

我们用指针head指向这个头节点

后续操作中我们可以通过head找到链表的头节点

这个指针是链表的标志

链表节点中都有一个指向自身的指针next

从图中我们可以看到

头节点的next存着地址200

200是链表第2个节点的地址

也就是说可以通过头节点的next找到链表的第2个节点

同理，可以通过第2个节点的next找到第3个

这样依次类推

可以找到链表中最后一个节点

对最后一个节点来说

因为没有后面的节点了

它的next为空，代表链表结束了

通过上面的描述我们看到

链表每个节点附设一个指针

用这个指针指向下一个节点

用这样的方式把节点串联起来

形成了我们所谓的单链表

把动态申请的节点组织了起来

为了图示更直观，在后面的讨论当中

我们用一个箭头来表示地址

链表的样子如图所示

下面讨论一下怎么来建立单链表

建立单链表可以分为两个步骤

一是创建头节点，二是通过循环

每次循环生成一个节点

随后把这个节点插入到已经创建的链表中

逐渐形成单链表

首先是创建头节点

先用malloc函数申请头节点的存储空间

malloc函数有一个参数

以字节个数标明需要申请空间的大小

这里是申请一个Lnode类型的节点

我们用sizeof来求得Lnode类型的字节数

如果申请成功

malloc函数会返回申请空间的起始地址

我们用linklist强制类型转换

把它转化为指向Lnode类型的指针

随后赋值给head指针

前面我们说过head指向头节点

是链表的标志

接着给头节点的next赋值空指针

完成头节点的创建

这个时候，链表中只有头节点

还没有其他的内容

为了后续节点插入的方便

我们使用一个指针p

p始终指向当前已经创建好的链表的最后一个节点

目前链表中还没有其它节点

头节点既是第1个节点也是最后一个节点

所以，目前p也指向它，p被赋值head

下面我们通过循环生成链表中其余节点

每次生成一个节点后

都把它插入到当前链表的表尾

成为目前链表的最后一个节点

这种创建链表的方法称为尾插法

我们观察第一次循环

进入循环以后，申请一个节点

用指针q指向它

随后，给节点成员data赋一个值

把指针next赋值为空

完成节点初始化

因为p指向当前已创建链表的最后一个节点

那么新节点插入以后应该作为它的下一个节点

所以p->next被赋值q

让最后一个节点的指针指向新建立的这个节点

这个节点插入以后

它就变成了当前已创建链表的最后一个节点

为了下次插入的方便，p被赋值q

让p指向新插入的节点

不断循环这个过程n次

就可以创建一个长度为n的带头节点的单链表

好了，同学们

我们今天的课程就到这里

下节课再见