当前课程知识点:程序设计基础 > 第八章 非文本数据处理 > 8.1 将数据组织成链表 > 8.1.2 代码讲解
那在这个代码里头呢 最开始的几行
实际上呢是必要的一些头文件的这种包含
然后我们紧接着定义了两个结构类型
一个是在前一讲里头已经学习过的
Time_t 这种结构类型 它存储了
6个整数分别代表年月日然后是时分秒
下一个结构类型呢是node这个结构类型
它里头存储了四个变量 第一个变量呢是tm
就是刚才说的这个时间结构类型的这种变量
第二个呢是用户的编号 第三个呢是用户的操作
是login还是logout这样的一个字符串
最后一个就是刚刚讨论到的
是一个指针它专门用来指下一个
这样的结构变量 它存放在什么地方
把那个地址值存放到next的域里头去
那我们看看这个主程序里头的代码
前面跟上一章是一样的
定义了一个fin这样的流对像
它对应的文件名是log.txt
这是一个ifstream
然后下面是新内容了 然后我们定义了一个指针
叫做head也就是链表的头这样的一个变量
它现在呢没有内容所以呢它现在是空的
接下来跟我们上一章也是一样的
通过一个while循环去判断这个文件有没有结束
如果没有结束呢就去读数据
下面我们来看whlie循环的循环体
最开始呢是一个字符类型的tmp
这个跟前一讲是一样的 接下来是一个新的语句
从内存里头动态分配一个接点这么大的内存空间
用来保存从文件里头读入的这种数据
那下面的几行呢跟前一章里头所学到的数据的
从文件里头读取的语句是类似的
只不过呢在上一章里头我们读取的数据
是读到临时的变量里去了
在这一章里头我们是把它读到
刚刚分配出来的那个节点data里头去了
所以大家可以看代码里头是
fin>>data->tm.year
这样一系列的写法 在这里头呢特别介绍一下
由于这个data它是一个结构类型的指针
所以在访问它的数据成员的时候
我们不能用点得用一个箭头
其实就是键盘上的减号加上一个大于号组成的
这个中间不能有空格 通过这种方式就可以把
文件里头的数据读到data这个指针
所指的空间里头去 然后大家注意看下面的这两行
是把现在新分配的保存了从文件
刚读进的内容的节点 添加到链表里头去
我们现在呢是采取的类似动画里头那种方法
把它加到链表的头上去 那怎么加头上去呢
我们想一想刚才在动画里头的那个动作
是小朋友去抓住新来的小朋友的衣服
然后这个新的小朋友再去抓领队的衣服
所以对应过来在我们代码里头就是
新来的这个data它的next去等于原来的head
也就是原来的队伍的头要去抓这个data的衣服
所以我们写到代码里头就是
data的next等于head
head原来指向什么地方呢
现在由data的next去指向它 这是第一步
第二步让head因为现在新加进来一个data嘛
让head再去指向这个data这种变量
所以这样的两句呢就完成了
把data这样的一个内存单元
链接到链表的头部的这个任务
大家可以在草稿纸上画出这个图
就能看到这个的确是完成了
添加节点到链表头部的这样的工作
这两步的顺序是不能颠倒的 一颠倒就会出错误
那好既然一个新的内容读到节点里去了
节点也放到链表里去了
那么就可以进行下一个记录的读取
所以这个while循环就转回去到了开头
再读下面的记录的内容
然后周而复始直到这个文件读完
这个链表就在不断的增长
像我们游戏里头小朋友越来越多越来越多
链表呢也会越来越长越来越长
这就是我们把链表这个概念引入之后
数据读取之后是怎么来组织它的
那么这样的一个读取的过程当中
那我们知道这个数据是一行一行读进来的
链表呢也是不断的变化的
所以为了让大家更好的来理解
这个程序运行的时候的一些变化过程
那我们这里头再结合数据的读写代码片段
以及呢 我们画一个示意图
那么几个方面的信息综合起来
一起来看一看数据是如何被组织成为一个链表的
大家请看这个屏幕上的显示
那首先呢我们文件打开之后
现在是预备读第一行 这第一行是
2015年4月21号的一条记录对吧
那么在代码里头我们可以看到
这个时候定义了一个node的指针变量head
它开始赋的初值是空
也就是我们在右下角看到的
有一个head的变量它有它的存储空间
这个时候存储空间存的值是一个空
是一个null 然后我们进入到循环
读取数据的这个循环体里头去
声明了一个新的指针变量data
然后呢它被创建出来new node
这是我们前几讲里已经介绍过的一个运算符
那也就是在屏幕的右下方 我们可以看到
出现了一个方框 这个就代表我们在内存里头
画了一片单元出来了 这个正好是对应的
然后下面是读取这一行的数据
那为了屏幕上显示方便
我是把它分成了好几条语句
实际上呢它可以连成一条语句写下去
那么通过读取它
我们可以看到在右下角的这个区域里头
这个数据的区域的内容已经发生了变化
由于这个内容比较长我就截取了中间的一部分
大家可以看到是8点0分33秒
这个用户的ID的编号的前几位是3773这样子的
那么前后我各自省掉了一些
这就是从文件里头读入了这些信息
接着我们到了把它添加到链表里去的
这个代码部分 那它是写的data的next=head
也就是我们刚才看到的那个新分配出来的
这个空间 它的next的这个域等于空
所以我们可以看到 出现一个红色的null
就表示把head这个变量里头存储着的
null这个值 赋给了data的next的域里头去了
所以我们可以看到 在data的内存空间里头
出现了一个红色的null就是这么来的
接下来一条语句是head=data
那这什么意思呢 就是head的这个变量的值
等于data这个指针的地址值
所以是data这个变量所存储的实际上是
一个地址值 把这个值再赋给head
所以我们就可以看到是这个内存单元的
地址值 存放到了head里头去了
我们这个示意图上就是在head框框里头
写了一个&符号 就表示了那个内存空间的
地址送到了head这个变量里头存储起来了
这就是head=data的这种含义
好了 这样呢我们这个一次循环就执行完了
下面就准备进行下一步的这种读取
我们从屏幕的上方可以看到
这个文件已经准备好了
预备我们去读下一行了
那么回过头来我们去读取这个数据之后
这个时候呢上面的这个红色的框框
代表文件的这个读写的这个位置
继续的往前推进到第三行 而屏幕的右方呢
就出现了刚才你先读进来的数据
它所生成的这种节点
我们可以看到它是8点15分35秒
用户的ID呢前四位是1173
这个是读进来了也生成了这样一个节点
那么它的next呢我示意性的写了一个&1
那么根据代码里头我们知道
读完数据之后马上就是把它添加到链表里头去
就是那个两条语句
data->next=head head=data
那么这两条语句执行起来就是
data->next=head
也就是&1这个域 它的指针值会指向
前面已经分配好的那个内存的空间
就是我们现在看到的这个箭头
然后是head=data也就是head变量的值要更新了
原来head里头存的是第一块内存的地址值
所以它的箭头是指向第一块内存的
现在呢要把它更新成head=data
就是新分配出来的那个单元的地址
所以呢这个指针就会发生变化
于是呢指向新分配的单元
这一轮循环又完成了
接下来我们把第三行的记录又读进来
生成了一个新的节点
我们可以看到它是8点34分57秒
这样的一个用户登录的时间
用户的编号是9fcf
那么同理它的这个&2就是它的next域
那我们也让它去执行data->next=head的时候
就会指向前面你那个新的head
就是上一轮的时候我们head已经发生变化了
其实指向第二个内存块了
所以这个时候&2是指向了第二个内存块的头
接下来head=data
于是head的内容再次发生变化
就是我们第三块内存的地址
存放到head变量里去了 这一轮又结束了
再接着下一轮新产生一个内存块
然后呢文件的位置往前移动
next去指向head
然后head去指向新的data
于是一个新的节点又被串了进来
继续读下一个
这是一个读入的是9点08分29秒的一个数据
那么同理它的next也会指向现在的这个head
然后head再次更新
这个时候我们这一轮又结束了
再继续往下这个数据很长了
我们就用点点点表示了
那么可见9点11分03秒这个数据已经读进来了
也生成了一个内存里头的一个节点
然后它的id5就是那个next域
再一次的等于head的值
也就是现在head所指的那个地址
所以这个时候大家可以看到
这个蓝颜色的线跟那个&5黑颜色的线
实际上是指向同一个地方
这就是data->next=head它带来的效果
接下来head=data
于是head内容再一次发生更改
指向了新生成的这个接点
好了我们后面就不再一一去演示
大家可以从屏幕上看到 当你从head出发
你可以看到这个里头的6个节点
它们真的是通过指针依次串起来了
我们的示意图里头可以看到好几根这种箭头
那么把它串起来就变成了一个链表
而head这个变量恰好就指向了
链表的第一个节点 而我们最开始
放进去的那个节点 此时此刻它是队伍的尾巴
就是在最尾巴后头 所以这个跟我们前面
小朋友玩游戏的时候是一样的
所有的新到的这个小朋友都是
加在这个领队的后面 他是变成了新的第一名
我们现在的数据组织成链表的时候
也采取了这种类似的方法
-1.1 基础知识
-1.2 买菜问题
-1.3 数学运算
-1.4 补充说明
-1.5 总结
--1.5 总结
-程设论道
--程设论道
-师生问答
-第一章 编程初步--语法自测
-2.1 关于超级计算器的几点思考
-2.2 电子秤模拟 — 背景介绍及需求分析
-2.3 电子秤模拟 — 代码实现
-2.4 变量定义与变量类型
-2.5 猜数游戏与数据表示
-2.6 关于变量的讨论
--公告
-2.7 变量体现的计算思维
-程设论道
--程设论道
-师生问答
--师生问答
-第二章 变量与代数思维--语法自测
-3.1 谁做的好事——语义表示
-3.2 谁做的好事——真假检查
-3.3 谁做的好事——循环枚举
-3.4 谁是嫌疑犯——多重循环枚举
-3.5 谁是嫌疑犯——破案线索表示
-3.6 谁是嫌疑犯——用二进制枚举
-程设论道
--程设论道一
--程设论道二
--程设论道三
-师生问答
-第三章 逻辑推理与枚举解题--语法自测
-4.1 插花游戏
-4.2 筛法
-4.3 线性查找
-4.4 折半查找
--4.4.1 提问
-4.5 排序问题
-4.6 总结
--4.6.1 总结
-程设论道
--程设论道二:筛法
-师生问答
-第四章 筛法与查找--语法自测
-5.1 阶乘
-5.2 排序
-5.3 矩阵填充
-5.4 分书与八皇后
-5.5 青蛙过河
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答一
--师生问答二
-第五章 分治思想与递归--语法自测
-6.1 兔子数列问题
-6.2 分鱼问题
-6.3 橱窗的插花问题
-6.4 最长公共子序列问题
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答
-第六章 递推与动态规划--语法自测
-7.1 统计记录总数
-7.2 统计活跃用户数
-7.3 统计在线时长
--7.3.2 结构
-7.4 总结
--7.4.1 总结
-程设论道
--程设论道
-师生问答
--师生问答
-第七章 文本数据处理--语法自测
-8.1 将数据组织成链表
-8.2 提高链表访问效率 —— 哈希链表
-8.3 以二进制文件存储链表
-程设论道
--程设论道一
--程设论道二
-师生问答
--师生问答
-第八章 非文本数据处理--语法自测
-9.1 自动售卖程序
-9.2 配制水果信息
-9.3 指定界面语言
-程设论道
--程设论道
-师生问答
--师生问答
-第九章 可配置的程序设计--语法自测