上往建站提供服务器空间服务商，百度快照排名，网站托管，百度推广运营,致力于设计外包服务与源代码定制开发，360推广，搜狗推广,增加网站的能见度及访问量提升网络营销的效果,主营：网站公司,百度推广公司电话,官网搭建服务,网站服务企业排名,服务器空间,英文域名等业务，专业团队服务，效果好。

张北网站优化【张北开通400电话】张北网站搭建、张北微信公众号推文外包、张北开通京东拼多多设计、张北淘宝装修

河北省张家口市张北县地处河北省西北部，内蒙古高原南缘的坝上地区，境域东西109公里，南北67公里，东南部与崇礼区交界，桦皮岭为全县最高点，海拔2128米；北、中部地势平坦，向西北渐低，安固里淖为最低点，海拔1300米。全县总面积4185平方公里，辖18个乡镇、366个行政村、1167个自然村，总人口37.2万人。居民以汉族为主，占总人口的98%，还有蒙古族、回族、满族等。张北县是离京津地区最近的高原地区，夏天气候凉爽是避暑胜地。

张北县被列为第一批国家新型城镇化综合试点地区。 [1]  2019年11月，入选第二批节水型社会建设达标县（区）名单。 [2]  2020年2月29日，退出贫困县序列，正式脱贫“摘帽”。 [3]  2020年12月，入选河北省数字乡村试点地区名单。

和树一样，表也是计算机程序中最基础的数据模型之一。从某种意义上讲，表就是树的简化形式，因为大家可以将表视为每个左子节点都是叶子节点的二叉树。不过，表还能表示其他一些方面，这些方面与我们之前了解的关于树的那些情况不同。例如，我们将要谈论对表的操作，比如压入和弹出，这是没法用树来模拟的；而且要探讨字符串，这种特殊而重要的表需要它们自己的数据结构。

6.1　本章主要内容

6.2节介绍了与表有关的术语。本章其余部分将介绍以下主题。

• 表的基本操作（6.3节）。

• 由链表数据结构（6.4节）和数组数据结构（6.5节）实现的抽象表。

• 栈：只能从一端插入和删除的表（6.6节）。

• 队列：从一端插入从另一端删除的表（6.8节）。

• 字符串和用来表示字符串的特殊数据结构（6.10节）。

此外，我们还将详细研究表的两类应用。

• 运行时栈，C语言以及其他多种语言用来实现递归函数的方法（6.7节）。

• 找出两个字符串最长公共子序列的问题，及其通过“动态规划”（或者说填表）算法得出的解决方案（6.9节）。

6.2　基本术语

表是由0个或多个元素组成的有限序列。如果这些元素全是T 类型的，那么就说该类型的表是“T 表”。因此，就有整数表、实数表、结构体表、整数表的表，等等。一般可以预期列表的元素都是某一类型的。不过，因为一种类型可以是多种类型的联合，所以单一“类型”的限制是可以绕开的。

表通常表示为用逗号分隔表中各元素，并用一对圆括号将这些元素括起来，如

(a1,a2,…,an)

其中ai 都是表中的元素。

在某些情况下，我们将不会把逗号和括号写出来。特别要说的是，我们将要研究字符串，也就是由字符组成的表。字符串一般不会写上逗号或其他分隔符号，而且不会用括号括起来。字符串的元素通常都是用等宽字体表示的。foo就是由3个字符组成的表，其中第一个字符为f，而第二和第三个字符都是o。

示例 6.1

下面是一些表的例子。

1. 小于20的质数按照从小到大的顺序组成的表：

(2，3，5，7，11，13，17，19)

2. 稀有气体元素按照原子量从小到大的顺序排列组成的表：

(氦，氖，氩，氪，氙，氡)

3. 平年各月天数组成的表：

(31，28，31，30，31，30，31，31，30，31，30，31)

这个例子提醒我们，同一元素可以在某个表中出现多次。

示例 6.2

一行文本是表的另一个例子。组成这行文本的单个字符就是表中的元素，所以该表就是个字符串。该字符串通常会包含若干空字符，而且一行文本的最后一个字符通常是“换行”符。

再举一个例子，文档也可视作表。这种情况下，表中的元素就是文本行。因此，文档就是由表作为元素组成的表，具体说来这些作为元素的表都是字符串。

示例 6.3

n 维空间中的点可以表示为由n 个实数构成的表。例如，单位正方体的顶点可以表示为图6-1所示的三元组。各表中的3个元素表示作为正方体8个角（“顶点”）之一的点的坐标。第一个元素表示x 坐标（水平方向），第二个表示y 坐标（向页内方向），第三个表示z 坐标（垂直方向）。

图 6-1　表示为三元组的单位正方体顶点

6.2.1　表的长度

表的长度是指元素在表中出现的次数。如果表中元素数为0，那么就说该表为空表。我们用希腊字母ε（音“伊普西龙”）表示空表。还可以用一对不包含任何内容的圆括号()表示空表。谨记，长度是按位置计算而不是按不同符号计算的，所以在表中出现k 次的某一符号可以为表增加长度k 。

示例 6.4

示例6.1中表(1)的长度是8，而表(2)的长度是6。表(3)的长度为12，因为每个月都要占据一个位置。而表中只有3个元素这一事实对表的长度来说是无关紧要的。

6.2.2　表的部分

如果表非空，那么它就是由称为表头（head）的第一个元素，以及称为尾部（tail）的表中其余部分组成的。例如，示例6.1中表(2)的表头就是“氦”，而该表的尾部则由其余5个元素组成：

(氖，氩，氪，氙，氡)

元素和长度为1的表

谨记，表的表头是个元素，而表的尾部却是表。此外，我们不应该将表的表头（假如为a）与只包含一个元素a 的长度为1的表（通常会写为带括号的(a)）混淆。如果元素a 是T 类型的，那么表(a)就是“T 表”类型的。

如果不能认识到这种区别，就可能在用数据结构实现表时造成编程错误。例如，我们可以用互相链接的单元表示表，这些单元通常是结构体，具有存放T 类型元素的element字段，以及存放指向下一单元的指针的next字段。那么元素a 就是T 类型的，而表(a)则是具有存放着a的element字段和存放着NULL的next字段的单元。

如果有表L=(a1,a2,…,an)，则对满足1≤i≤j≤n 的i 和 j 来说，(ai ,ai+1,…,aj )是L 的子表。也就是说，子表是由从某个位置i 开始到某个位置j 结束的所有元素组成的。还可以说空表ε 是任何表的子表。

表L=(a1,a2,…,an)的子序列是指从L 中剔除0个或多个元素后形成的表。剩下的这些元素，也就是构成子序列的这些元素，必须按照与出现在L 中相同的顺序排列，不过子序列的元素在L 中不一定是连续的。请注意，ε 和表L 本身总是L 的子序列，而且L 的子表也是L 的子序列。

张北网站优化【张北开通400电话】张北网站搭建、张北微信公众号推文外包、张北开通京东拼多多设计、张北淘宝装修

上往建站提供搭建网站，域名注册，官网备案服务，网店详情页设计，企业网店，专业网络店铺管理运营全托管公司咨询电话，服务器空间，微信公众号托管，网页美工排版,致力于域名申请，竞价托管，软文推广，全网营销,提供标准级专业技术保障，了却后顾之忧,主营：虚拟主机，网站推广，百度竞价托管，网站建设，上网建站推广服务，网络公司有哪些等业务，专业团队服务，效果好。

服务热线：400-111-6878 手机微信同号:18118153152（各城市商务人员可上门服务）