编译程序相当于两种语言系统之间的“翻译”。用高级语言编写的源程序只有经过编译程序的“翻译”，变成了目标程序，计算机才可以识别和运行。编译程序有两种“翻译”方式，一种是图7-8所示的完整的翻译后再执行的方式，完成这种翻译工作的程序称作编译程序。解释程序与编译程序的区别是，解释程序在翻译过程中不产生目标程序，而是边翻译边执行源程序本身。这种边翻译边执行的工作方式的最大缺点是效率太低，最大优点是简单易实现。......
2023-11-18
计算机导论：数据结构基本概念
【摘要】：计算机进行数据输入和数据输出时使用的最小单位称为数据元素。书号、书名、作者名、状态等称为数据元素的数据项。如何表示现实世界中的各种不同的数据元素模型，如何在程序设计中实现各种不同的数据元素模型，是数据结构要讨论的主要问题。为了使读者理解数据结构的基本概念，我们以图书信息计算机管理问题的软件设计为例来进行说明。数据结构主要有数据的逻辑结构、数据的存储结构以及对数据元素的操作。
描述客观事物的数字、字符、图像、声音等所有能输入到计算机中并能被计算机接受的符号称为数据。
计算机进行数据输入和数据输出时使用的最小单位称为数据元素。例如，在图书馆图书的计算机管理问题中，一本图书的描述数据由书号、书名、作者名、状态等组成，一本书的这些数据在输入或输出时必须作为一个整体进行，所以这个问题的数据元素就由书号、书名、作者名、状态等数据组成。书号、书名、作者名、状态等称为数据元素的数据项。
程序是计算机可以理解和执行的求解问题的操作步骤。现实世界中的问题是用数据元素来描述的。现实世界中的问题类型有很多种，描述现实世界问题的数据元素模型也必然有很多种。如何表示现实世界中的各种不同的数据元素模型，如何在程序设计中实现各种不同的数据元素模型，是数据结构要讨论的主要问题。
为了使读者理解数据结构的基本概念，我们以图书信息计算机管理问题的软件设计为例来进行说明。要用计算机来管理图书馆图书的借阅，需要分析和建立图书数据的模型。对于图书借阅问题来说，数据元素由书号、书名、作者名、状态（状态有未借出状态、已借出状态等）等组成。所有数据元素应组织成一种一个数据元素后接另一个数据元素的结构。任何一次借阅的计算机管理过程实际就是对其中某一个数据元素的某一个（或某几个）数据项数据值的修改过程。例如，某个读者要在图书馆借阅一本由作者名为朱战立，书名为《计算机导论》的书，计算机的管理方法是：在图书信息文件中查找是否存在作者名为朱战立，书名为《计算机导论》的书，如果不存在，则告诉读者图书馆没有这本书，处理过程结束；如果存在，则检查该数据元素的状态数据项是否为已借出状态，如果是已借出状态（假设每种书只有一本），则告诉读者该书已借出，处理过程结束；如果该数据元素的状态是未借出状态，则把该数据元素的状态修改为已借出状态，并从书架上找出该书，把它借给读者，处理过程结束。
在图书馆图书的计算机管理问题中，图书数据的组织模型为线性表。在线性表中，每个数据元素只有一个惟一的前驱数据元素和一个惟一的后继数据元素。线性表是一种最简单的数据结构模型。按线性表模型组织的数据，允许对其中任意一个数据元素进行修改操作。由于这样的数据模型是从逻辑概念上考虑的数据模型，所以这样的数据模型称为数据的逻辑结构。
对于图书馆图书的计算机管理问题，还要考虑逻辑结构的线性表怎样具体存储在计算机中。对于图书信息表，我们可以用一个数值足够大的数组来具体存放，用数组具体存储图书信息表的示意图见图8-1。其中，最后一列数值为0表示未借出状态，数值为1表示已借出状态。该数组存放在内存中一段地址连续的存储单元中。在图8-1中，图书信息表中的数据元素是按逻辑次序在内存中连续存放的，即逻辑意义上在前面的数据元素存放在数组的前面位置，逻辑意义上在后面的数据元素存放在数组的后面位置。数据模型在计算机内存的存储方式称为数据的存储结构。由于用数组方式存储的存储结构在内存中是顺序存储的，所以这种存储结构称为顺序存储结构。因此，图书信息表的数组存储结构也称为图书信息表的顺序存储结构。
图8-1 用数组存储图书信息表(www.chuimin.cn)
对于逻辑结构的图书信息表，我们还可以用链接的方式在计算机中具体存储，链接方式图书信息表的存储示意见图8-2（a）。其中，箭头指示出下一个数据元素在内存中的存储位置。符号“
”表示链接到此结束。图书信息表的链接方式存储简称链表。链表中的一个数据元素和相应的勾链（称为指针）称为结点。在链表中，数据元素的逻辑次序是靠勾链来实现的。链表中每个结点在内存中的存储位置由操作系统根据当前运行的计算机的内存使用情况临时分配。链表在内存中的一个具体存储位置示意见图8-2（b）。显然，在链接方式存储的图书信息表中，数据元素并不是按其逻辑次序顺序存放的，而是靠勾链来指示下一个数据元素的存储单元地址的。链接方式的存储结构称为链式存储结构。
图8-2 用链接方式存储图书信息表
（a）链接方式的图书信息表；（b）链表在内存中的存放示意
对于图书馆图书的计算机管理问题来说，图书信息表的存储结构不同，算法的实现方法必然不同。例如，任何一次图书借阅管理过程首先需进行所借阅或归还图书的查找，若图书信息表采用数组来存储，那么，为了提高查找算法的效率，我们可以先按图书的书号对该数组进行排序，然后可以按折半查找算法来设计图书的查找算法。但是，若图书信息表采用链式存储结构来存储，那么，就不能用折半查找算法来设计查找算法，因为在链式存储结构下，每一个结点的地址都是当前运行计算机的操作系统临时分配的，因此，我们无法计算出链表中最中间结点在内存中的存储地址。
总结上面的讨论可以归纳出，任何问题的软件设计都包括数据结构的设计。数据结构主要有数据的逻辑结构、数据的存储结构以及对数据元素的操作。对于相同的问题，若存储结构不同，则实现操作的算法也不同。
本章后面三节将概要介绍数据的逻辑结构、数据的存储结构和不同存储结构下操作的实现方法。
有关计算机导论的文章
- 详细阅读
-
计算机导论-探索Web的基本概念详细阅读
WWW是由非常庞大的、世界范围内的文档集合而成的，这些文档简称为页面或网页。Web的出现极大地扩展了网络的应用范围，丰富了网络的内容，方便了人们对网络的使用。Web页面也称作网页，Internet上许许多多的网页采用超链接的方式链接在一起。所谓超链接，是引导浏览者从一个Web页面直接跳转到另一个Web页面的URL字符串。在一个文本形式的Web页面中，若包含了至少一个超链接字符串，则这样的文本称为超文本。Web页面是通过浏览器来浏览和观察的。......
2023-11-18
-
计算机导论：数据通信基本概念详细阅读
在数据通信中，产生或发送数据的一端称为信源，接收数据的一端称为信宿。在传递数据的过程中，信道传递的电信号可能受到干扰，如电磁波等的干扰。图9-6为数据通信系统的总体模型。模拟信号是随时间连续变化的信号。模拟信号的主要参数有幅度、相位和频率。以模拟信号或者数字信号传输的数字数据称为数据通信。模拟通信基本模型如图9-8所示。而模拟信号进行传送时，信号的失真问题比较严重。......
2023-11-18
- 详细阅读
-
计算机导论（第2版）：数据结构与顺序存储详细阅读
数据元素也称元素、结点、顶点、记录。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。该方法的基本思想是，根据数据元素的关键字直接计算出该结点的存储地址。......
2023-11-25
- 详细阅读
-
计算机导论：探讨计算机用户道德详细阅读
“黑客”最初是用来称呼那些试图测试计算机程序能力极限的计算机用户。但后来当某些人尝试非法访问计算机系统时，新闻媒体就用“黑客”来称呼那些试图未经授权对计算机系统进行访问的人。“黑客”的行为是错误的，一些对计算机知识有着深入了解的人，为了展示自己的才能，实现自我价值，或被利益诱惑而成为“黑客”，并对一些政府部门或企业的内网进行攻击，这些都是违法的行为。......
2023-11-25
-
计算机硬件结构概述-计算机导论详细阅读
通过第2章和第3章的讨论，我们对计算机硬件的基本结构有了更深一步的了解，图3-6给出了计算机硬件基本结构的概念框图。控制总线的控制信号一般都来自于CPU中的控制器。图3-4给出的CPU的基本构成中也有数据的传送通道，因为CPU是由拇指大小的一个芯片构成的，所以图3-4中的CPU内的数据传送通道称为片内总线。......
2023-11-18
相关推荐