当前课程知识点:程序设计基础 >  第八章 非文本数据处理 >  8.1 将数据组织成链表 >  8.1.2 代码讲解

返回《程序设计基础》慕课在线视频课程列表

8.1.2 代码讲解在线视频

8.1.2 代码讲解

下一节:8.1.3 链表遍历与释放

返回《程序设计基础》慕课在线视频列表

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.1.1 什么是程序?什么是语言?

--1.1.2 什么是程序设计?

--1.1.3 计算机发展史

-1.2 买菜问题

--1.2.1 问题描述

--1.2.2 程序的基本结构

-1.3 数学运算

--1.3.1 数学运算符

--1.3.2 数学函数

-1.4 补充说明

--1.4.1 编程环境的下载与安装

--1.4.2 程序基本结构中的含义

--1.4.3 格式与风格

-1.5 总结

--1.5 总结

-程设论道

--程设论道

-师生问答

--师生问答一:怎样学好程序设计

--师生问答二:语言选择

--师生问答三:关于函数

-第一章 编程初步--语法自测

第二章 变量与代数思维

-2.1 关于超级计算器的几点思考

--2.1.1 关于超级计算器的几点思考

-2.2 电子秤模拟 — 背景介绍及需求分析

--2.2.1 电子秤模拟 — 背景介绍及需求分析

-2.3 电子秤模拟 — 代码实现

--2.3.1 电子秤模拟 — 代码实现

-2.4 变量定义与变量类型

--2.4.1 变量定义与变量类型

-2.5 猜数游戏与数据表示

--2.5.1 猜数游戏与数据表示

-2.6 关于变量的讨论

--2.6.1 变量的初始值

--2.6.2 变量类型

--2.6.3 变量内存单元地址

--2.6.4 存“变量地址”的变量——指针

--2.6.5 指针的 读/写 操作

--2.6.6 指针的 加/减 操作

--公告

-2.7 变量体现的计算思维

--2.7.1 变量体现的计算思维

-程设论道

--程设论道

-师生问答

--师生问答

-第二章 变量与代数思维--语法自测

第三章 逻辑推理与枚举解题

-3.1 谁做的好事——语义表示

--3.1.1 谁做的好事——语义表示

-3.2 谁做的好事——真假检查

--3.2.1 谁做的好事——真假检查

-3.3 谁做的好事——循环枚举

--3.3.1 谁做的好事——循环枚举

-3.4 谁是嫌疑犯——多重循环枚举

--3.4.1 谁是嫌疑犯——多重循环枚举

-3.5 谁是嫌疑犯——破案线索表示

--3.5.1 谁是嫌疑犯——破案线索表示

-3.6 谁是嫌疑犯——用二进制枚举

--3.6.1 谁是嫌疑犯——用二进制枚举

-程设论道

--程设论道一

--程设论道二

--程设论道三

-师生问答

--师生问答一:字符与ASCII码表

--师生问答二:其他循环语句、运算符优先级与变量作用域

-第三章 逻辑推理与枚举解题--语法自测

第四章 筛法与查找

-4.1 插花游戏

--4.1.1 问题提出(求素数)

--4.1.2 函数初探

--4.1.3 运行演示

-4.2 筛法

--4.2.1 筛法思路

--4.2.2 数组的定义

--4.2.3 代码翻译

--4.2.4 运行演示

--4.2.5 小朋友数人数

--4.2.6 运行演示

--4.2.7 韩信点兵

-4.3 线性查找

--4.3.1 扑克查找问题

--4.3.2 扑克查找问题代码翻译

--4.3.3 最小值问题

--4.3.4 最小值问题代码翻译

-4.4 折半查找

--4.4.1 提问

--4.4.2 折半查找思路

--4.4.3 折半查找代码翻译

--4.4.4 折半查找运行演示

-4.5 排序问题

--4.5.1 插入排序

--4.5.2 选择排序

--4.5.3 函数写法

--4.5.4 运行演示

-4.6 总结

--4.6.1 总结

-程设论道

--程设论道一:数组与编码思维

--程设论道二:筛法

-师生问答

--师生问答一:函数与面向过程编程

--师生问答二:数组的下标越界

-第四章 筛法与查找--语法自测

第五章 分治思想与递归

-5.1 阶乘

--5.1.1 阶乘问题

--5.1.2 递归解法

--5.1.3 递归小结

-5.2 排序

--5.2.1 归并排序——总体思路

--5.2.2 归并排序——思路分解

--5.2.3 归并排序——代码解说

--5.2.4 快速排序——总体思路

--5.2.5 快速排序——代码解说

--5.2.6 排序总结

-5.3 矩阵填充

--5.3.1 矩阵填充问题

--5.3.2 代码解说

-5.4 分书与八皇后

--5.4.1 问题描述

--5.4.2 问题分析——共性

--5.4.3 问题分析——区别

--5.4.4 解题准备——二维数组

--5.4.5 解题准备——递归设计

--5.4.6 代码解说——分书问题

--5.4.7 代码解说——八皇后问题

-5.5 青蛙过河

--5.5.1 问题描述

--5.5.2 问题分析——简单情况

--5.5.3 问题分析——复杂情况

--5.5.4 问题分析——一般情况

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答一

--师生问答二

-第五章 分治思想与递归--语法自测

第六章 递推与动态规划

-6.1 兔子数列问题

--6.1.1 问题描述

--6.1.2 按大小兔子分别递推

--6.1.3 按总数递推

--6.1.4 不用数组递推

-6.2 分鱼问题

--6.2.1 问题描述

--6.2.2 从A到E递推

--6.2.3 从E到A递推

-6.3 橱窗的插花问题

--6.3.1 问题描述

--6.3.2 题意理解与分析

--6.3.3 用枚举思想解题

--6.3.4 采用递推的优化算法

--6.3.5.1 采用动态规划算法—优化分析

--6.3.5.2 采用动态规划算法—递推代码

--6.3.5.3 采用动态规划算法—计算过程

--6.3.5.4 采用动态规划算法—输出方案

--6.3.6 动态规划总结

-6.4 最长公共子序列问题

--6.4.1 问题描述与理解

--6.4.2 问题分析

--6.4.3.1 动态规划解题(1)

--6.4.3.2 动态规划解题(2)

--6.4.3.3 动态规划代码

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答

-第六章 递推与动态规划--语法自测

第七章 文本数据处理

-7.1 统计记录总数

--7.1.1 问题分析

--7.1.2 读文件操作

-7.2 统计活跃用户数

--7.2.1 问题分析

--7.2.2 字符串

--7.2.3 程序翻译与演示

-7.3 统计在线时长

--7.3.1 问题分析

--7.3.2 结构

--7.3.3 程序翻译与演示

--7.3.4 写文件操作

-7.4 总结

--7.4.1 总结

-程设论道

--程设论道

-师生问答

--师生问答

-第七章 文本数据处理--语法自测

第八章 非文本数据处理

-8.1 将数据组织成链表

--8.1.1 链表的基本概念

--8.1.2 代码讲解

--8.1.3 链表遍历与释放

-8.2 提高链表访问效率 —— 哈希链表

--8.2.1 简单的哈希算法

--8.2.2 算法实现

-8.3 以二进制文件存储链表

--8.3.1 二进制文件的操作方法

--8.3.2 代码讲解

-程设论道

--程设论道一

--程设论道二

-师生问答

--师生问答

-第八章 非文本数据处理--语法自测

第九章 可配置的程序设计

-9.1 自动售卖程序

--9.1.1 提出问题与初步设计

--9.1.2 细化实现订单处理

--9.1.3 使程序更健壮

-9.2 配制水果信息

--9.2.1 提出问题与设计文件格式

--9.2.2 实现订单处理功能

-9.3 指定界面语言

--9.3.1 提出问题与命令行参数

--9.3.2 实现程序功能

-程设论道

--程设论道

-师生问答

--师生问答

-第九章 可配置的程序设计--语法自测

8.1.2 代码讲解笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。