广义表的案例教学研究

付勇智

[摘 要] 以广义表为例，探讨在数据结构教学中，如何抓住知识运用这个主题，激发学生的学习兴趣，提高数据结构抽象能力。

[关 键 词] 广义表；json格式；数据抽象

[中图分类号] G712 [文献标志码] A [文章编号] 2096-0603（2018）28-0116-01

一、概述

程序设计的主要任务就是数据表示和处理，数据表示又可以分为数据建模和数据的机内表示。数据建模即抽象出数据逻辑结构，是指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与它们在计算机中的存储位置无关。数据的机内表示分为数据元素的机内表示和关系的机内表示，即数据的物理结构，数据元素的机内表示一般是把数据元素中各个数据项组织成一个节点，放在一块连续的

内存、数据元素之间关系的机内表示一般采用顺序、链接、索引、散列等多种存储形式。常用的存储形式有顺序存储形式和链式存储形式。数据结构课程主要是研究数据的逻辑结构与数据的物理结构。

多年的教学实践中发现，学生很难把数据结构的知识与程序

设计联系起来，用的最多的就是数组与链表，而这只是数据元素之间关系的机内表示。几乎不会把实际问题抽象形成数据结构的课程中学到的各种典型结构。

本文选择软件开发中经常用的json结构与广义表的关系研究，探讨在广义表的教学中如何做到使学生学以致用。

二、广义表

广义表是一种特殊的线性表，与线性表不同，广义表的元素可以是一个简单值，也可以是一个广义表。广义表一般表示为，LS={a，b，c，…，A，B，C，…}，其中小写字母表示单个元素，大写一个广义表，可以看出广义表是一种嵌套表。

在软件开发中，很多事物都适合用广义表进行描述与存储。例如，中國有很多省就可以这样描述：中国=（“中国”，省1，省2，…）；每个省又是一个线性表：省=（“名称”，市1，市2…），等等。

广义表中各个子广义表的结构与长度可能都不同，所以一般

都用链式存储结构，而且可能是异构节点的链表。如果用顺序存储，就要考虑定长，或者为子广义表定义一个开始或结束标志。

由于广义表的复杂性，加上各个语言的语法元素没有直接的

语法元素对应，学生就不太愿意学。

三、Json

Json的元素可以是三种类型：

1.简单值。 字符串、数值、布尔值和null。

2.对象。 对象表示一组有序的键值对，每个值可以是简单数据类型值，也可以是复杂数据类型的值。

3.数组。 数组是一种复杂数据类型，表示一组有序值的列表，数组值可以是简单值、对象或数组。

下面是中国行政区结构的json表示，包含json对象、json

数组。

{

{“name”："中国"，“province”：[{“name”："黑龙江"，“cities”：{“city”：["哈尔滨"，"大庆"] }}，{“name”："广东"，“cities”：{“city”：["广州"，"深圳"，"珠海"] }}…]

}

四、案例设计

结合学生熟悉的现实场景，充分考虑广义表与json的基本特

征，在教学中我们选择了学校这个对象，一个学校有许多系，一个系有许多班级，每个班有许多学生的应用案例。

该案例的json就是：

学校={“名称”：“学校名称”，

“系”：[{“名称”：“系1”，

“班”：[{“名称”：“班1”，[“学生1”，“学生2”，…]}， {“名称”：“班2”，[“学生1”，“学生2”，…]}，…]}，

{“名称”：”系2” ，

”班”：[{“名称”：“班1”，[“学生1”，“学生2”，…]}， {“名称”：“班1”，[“学生1”，“学生2”，…]}，…]}，…]}

把信息进行抽象得到的广义表描述如下：

学校=（“学校名称”，“系1”，“系2”，…）

系=（“系名”，“班1”，“班2”，…）

班=（“班号”，“学生1”，“学生2”，…）

至此，学生就可以通过课堂学到的广义表的存储方式，理解json结构是如何存储的。现在许多内存数据库，用的就是json结构描述对象，进而通过这样的抽象，学生也理解了一种面向对象数据库存储方式。

五、效果

近几年教学实践，这样使学生理论联系实际，很容易也很愿意学习广义表了。

参考文献：

[1]严蔚敏，吴为民.数据结构[M].清华大学出版社，2002（2）.

[2][美]巴塞特.JSON必知必会[M].人民邮电出版社，2016.