第二部分数据结构
概述
数据结构是计算机专业基础课程之一，是十分重要的核心课程。计算机的所有系统软件和应用软件都要用到各种类型的数据结构。要想更好运用计算机来解决实际问题，仅仅学习计算机语言而缺乏数据结构知识是远远不够的，瑞士著名的计算机专家沃思(N.Writh)曾经说过：“算法+数据结构=程序”。可见有了程序设计的基本知识，掌握了一种程序设计语言，并不一定就能设计出比较好的程序，解决比较复杂的实际问题，还必须掌握数据结构及算法设计的基本知识。
数据（Data）
数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。
随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图像和声音等。数据元素（Data Element）
数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录。一个数据元素可以由若干个数据项（也称为字段、域、属性）组成。数据项是具有独立含义的最小标识单位。
为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。
【例1.1】学生成绩表，见下表。
注意：在表中指出数据元素、数据项、开始结点和终端结点等概念
数据结构（Data Structure）
数据结构指的是数据之间的相互关系，即数据的组织形式。
1．数据结构一般包括以下三方面内容：
①数据元素之间的逻辑关系，也称数据的逻辑结构（Logical Structure）；
数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构(Storage Structure)
数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。
③数据的运算，即对数据施加的操作。
数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。
所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。
（1）逻辑结构
表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（Immediate Predecessor））最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（Immediate Successor））也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。例如，表中"马二"所在结点的直接前趋结点和直接后继结点分别是"丁一"和"张三"所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。
（2）存储结构
该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？
（3）数据的运算
在上面的学生成绩表中，可能要经常查看某一学生的成绩；当学生退学时要删除相应的结点；进来新学生时要增加结点。究竟如何进行查、删除、插入，这就是数据的运算问题。搞清楚了上述三个问题，也就弄清了学生成绩表这个数据结构。
2．数据的逻辑结构分类
在不产生混淆的前提下，常将数据的逻辑结构简称为数据结构。数据的逻辑结构有两大类：（1）线性结构
线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
线性表是一个典型的线性结构。栈、队列、串等都是线性结构。
字符串是什么数据结构（2）非线性结构
非线性结构的逻辑特征是：一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。
第一章线性表
“线性表”是指由有限多个类型相同的数据元素组成的集合，它有以下的特点：
(1)有唯一的头结点(即第一个数据元素)和尾结点(即最后一个数据元素)；
(2)除结点外，集合中的每个数据元素均只有一个前驱；
(3)除尾结点外，集合中的每一个数据元素均只有一个后继。
“线性表”是一种运用非常广范的数据结构。
例一、某旅馆有100个房间，以1到100编号，第一个服务员来了，他将所有的房门都打开，第二个服务员再把所有编号是2的倍数的房门都关上，第三个服务员对编号是3的倍数的房门原来开的关上，原来关上的打开，此后的第四，五...服务员均照此办理。问第100个服务员走进后，有哪几扇门是开着的。
Program lt7_1_1；
var door：array[1..100] of boolean； 1到100号房门状态，false--关，true--开
i，j：integer；
begin
fillchar(door，sizeof(door)，true)；第一个服务员打开全部房门
for i：=2 to 100 do                                      i表示服务员号码
for j：=1 to 100 div i do
door[i*j]：=not door[i*j]；对房号为i的倍数的房门进行相反处理
write('The code of opening door is ： ')；
for i：=1 to 100 do
if door[i] then write(i，' ')；
end.
【算法分析】(1)这里用door[1..100]来存储1到100号房门的开关状态，即是一种线性表，其中：door[1]可以看成是头结点，而door[100]是尾结点；同时由于数组在内存中是按顺序占有一片连续的内存空间，因此这种存储结构即是顺序存储结构。
(2)这里用布尔变量true和false分别表示开和关两种状态，对某一房门进行相反处理时只要取反(not)即可，比如：若door[10]为false，not door[10]则为true。
【练习一】
1、求1987乘幂的尾数：
M和N是自然数，N>M>=1，而1987^M与1987^N的末三位数相同，求最小的M和N。【算法分析】本题只须记录1987的乘幂的末三位数，故不必高精度计算；
(1)用数组]存储1987的1至n次幂的末三位数；
(2)n的初始值为2，计算1987的n次幂的末三位数，并和1987的1至n-1次幂进行比较，若无相等的，则n=n+1，重复(3)；否则，第一次到相等的，即是所求的m，n值。2、一个特殊的数列：
写出两个1，然后在它们中间插入2成为121，下一步是在任意两个相邻的和数为3的数之间插入3，成为13231；再下一步又在任意两个相邻的和数为4的数之间插入4，成为1432341，...，由键盘输入N(1<=N<=9)，求出用上面方法构造出来的序列，其最后插入的数为N。
【算法分析】字符串也可以看做是一个特殊的线性表，本题初始串是11，对应N=1时的情况；然后在串中寻相应的位置，依次插入2，3，...，K。
3、求序列的第300项：
把所有3的方幂及互不相等的3的方幂和排列成一个递增序列：1，3，4，9，10，12，13，...，求这个序列的第300项。
【算法分析】本题可以用一个线性表来记录这个递增的序列，通过递推可以将整个序列构造出来。方法如下：
(1)数组a存放线性表，t为尾指针，b存放3的幂，初始时t=1，b=1；
(2)将b放入表尾，尾指针加1；a[t]←b；t←t+1；
(3)将b依次与1至t-1的元素相加，按顺序放入表尾；
(4)重复(2)，(3)，直至第300项放入表中。
第二章指针与链表
一、静态存贮和动态存贮
1、静态存储
程序中的变量一经说明，计算机操作系统就会在内存空间中分配相应的存贮单元，其中变量名是存贮单元的地址，而变量的值是存贮单元的内容，且该存贮单元自始至终都被该变量所占用，直到程序结束。如果变量是局部变量，那么在它的作用域内，一经说明也占有一定的存贮单元，直到退出其作用域为止。
这样的变量，在程序执行过程中，不能随时使用随时分配存贮空间，也不能在程序执行的过程中，释放这些空间。也就是说，一旦给这些变量分配存贮空间，无论程序是否还需要使用，它们都要占用一定的存贮空间，以便给用户存贮数据。我们称具有这样特点的存贮为静态存贮，它所对应的变量称为静态变量。如字符类型、数组类型、记录类型等。这类变量的优点是存贮方便，查容易，可以通过一个简单的公式随机存取表中的任一元素，逻辑关系上相邻的两个元素在物理位置上也是相邻的，很容易到前趋与后继元素；缺点是在线性表的长度不确定时，必须分配足够大的存储空间，经常浪费了宝贵的存储资源；而线性表的容量一经定义确定后就难以扩充；在插入和删除线性表的元素时，需要移动大量的元素，时间效率也比较差。
2、动态存贮
在程序执行过程中，通过向操作系统申请存贮空间或释放存贮空间的命令，达到动态管理计算机的存贮空间，以保证存贮空间的充分利用。存贮空间可以随时申请、随时释放，这样的存贮方式称为动态存贮，其变量称为动态变量。指针变量即为动态变量。
动态存储所需要的空间可以是不连续的，这样有利于充分利用零散的小空间。但缺无法用O（1）的时间实现存取了。如何用这些零散的空间存储数组这些大规模数据呢？如何表示这些数据之间的逻辑关系呢？为了表示这些物理存储单元之间的逻辑关系，对于每个数据元素来说，除了要存储它本身的信息（
数据域data）外，还要存储它的直接后继元素的存储位置（指针域，一般用link或next表示）。我们往往把这两部分信息合在一起称为一个“结点node”。 N个结点链接在一起就构成了一个链表。N=0时，称为空链表。同时，为了按照逻辑顺序对链表中的元素进行各种操作，我们需要定义一个变量用来存储整个链表的第一个结点的物理位置，这个变量称为“头指针，一般用H或head表示”。也可以把头指针定义成一个结点，称为“头结点”，头结点的数据域可以不存储任何信息，也可以存储线性表的长度等附加信息，头结点的指针域（头指针）存储指向第一个结点的指针，若线性表为空表，则头结点的指针域为空（NIL）。由于最后一个元素没有后继，所以线性表中最后一个结点的指针域为空（NIL）。由于此链表中的每个结点都只包含一个指针域，故称为“线性链表或单向链表”。
二、指针类型与指针变量
1．指针类型和指针变量的说明
type  指针类型标识符= ^基类型名；        {基类型不能为文件类型}
var 指针变量名：指针类型标识符；
2．申请存储单元            {动态申请、空间大小由指针变量的基类型决定} new(指针变量名)；      {PASCAL标准过程}
3．指针变量的赋值
指针变量名：=NIL；      {初始化，暂时不指向任何存储单元}
如何表示和操作指针变量？不同于简单变量（如A：=0；），PASCAL规定用“指针变量名^”的形式引用指针变量（如P^：=0；）。区分如下图所示：
如计算机执行下面的程序段时：NEW（H）；H^:=123；NEW（H）；H^:=234；内存示意图如下（阴影部分表示该单元已被占用）：
4．相同基类型的指针变量之间可以进行相互赋值。如有下面的程序段，可以画出右边的示意图：
var p1,p2:^integer;
new(p1);new(p2);
p1^:=90;p2^:=80;
p1:=p2;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。