计算机软件基础讲义.doc

《计算机软件基础讲义.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第—部分数据结构第一章绪论计算机应用相当普遍，计算机的应用已不再局限于科学计算，而更多用于控制、管理及数据处理等非数值计算的处理工作。与此相应，计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据，这就给程序设计带来一些新的问题。为了编写出一个好的程序，必须分析待处理的对象的特性以及各处理对象之间存在的关系。这就是数据结构学科形成和发展的背景。1.1数据结构一般来说，用计算机解决一个问题时，需要经过如下几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个对此数学模型进行操作的算法，最后编写出程序直至得到解答。例l

2、：图书馆的书目检索系统。当你想借阅一本参考书时，你需要到图书馆去查阅图书目录卡片。如果利用计算机实现自动检索，则计算机处理的对象便是这些目录卡片上的书目信息，列在卡片上的一本书的书目信息可由登录号、书名、作者名、分类号、出版单位和出版时间等各项组成。每一本书都有唯一的一个登录号。在书目自动检索系统中建立一张按登录号顺序排列的书目文件，如图1.1，这个文件就是书目自动检索系统中的数学模型。计算机的主要操作就是按照某个特定要求(如给定书名)对书目文件进行查询。…001002003004高等数学理论力学高等数学线性代数……樊映川罗远祥华罗庚栾汝书图1

3、.1…S01L01S01S02………………………1.2基本概念1.2.1数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。如数值、字符串、图像、声音都是数据。1.2.2数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理单位，通常—个数据元素可由若干个数据项组成。如书目文件中一本书的书目信息就是一个数据元素。书目信息中的每一项(如书名、作者名)为一个数据项，数据项是不可分割的最小单位。1.2.3数据对象是性质相同的数据元素的集合，是数据的子集。1.2.4数据结构简单的说，是相互之

4、间存在一种或多种特定关系的数据元素的集合。数据结构没有一个明确的定义，它包括三个要素：1.数据的逻辑结构1数据的逻辑结构抽象地反映数据元素之间的逻辑关系，而不管这种逻辑关系在计算机中是如何表示的。数据的逻辑结构分为线性结构和非线性结构。若各个数据元素之间的逻辑关系可以用一个线性序列简单的表示出来，则称之为线性结构，否则称为非线性结构。如书目文件中ai表示一个数据元素，书目文件可表示成（a1,a2,a3……an），所以它是一个线性结构。如图二：数据元素之间的逻辑关系不能用一个线性序列表示出来，所以数据的逻辑结构是非线性结构。a1图二2.数据的存储结构a

5、2a3数据的存储结构是逻辑结构在计算机存储器里的实现。数据的逻辑结构在存储器中的映像应包括数据元素自身值和数据元素之间关系的表示。这样在存储器中，某个结点有两个域，一个是存放自身值的域，用标识符info表示这个域;另一个是存放该结点与其它结点关系的域，用标识符1ink表示这个域。3.数据的运算数据的运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构上进行。数据的各种逻辑结构都有相应的运算，常用的运算有检索、插入、删除、更新和排序等。1.3主要的数据存储方式数据之间的逻辑关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，相应的得到两种

6、不同的存储结构：顺序存储结构和链式存储结构。1.3.1顺序存储结构把逻辑上相邻的数据元素存储在物理上相邻的存储单元里。特点：只有信息域，没有指针域。可以通过计算直接确定第i个结点的存储地址。L0×L−i−+1=Li−11)(，其中L0是第一个结点的存储地址，m是每个结点所占用的存储单元数。插入操作和删除操作不方便。1.3.2链式存储结构链式存储结构就是每个结点至少包括一个指针域，用指针来体现数据元素之间的逻辑关系。特点：除了有信息域，还有指针域；逻辑上相邻，物理上不必相邻；插人操作和删除操作方便。1.4C语言简介22.1线性表第二章线性表1

7、.定义线性表的逻辑结构是n个数据元素的有限序列，(a1,aa2,3⋅⋅⋅⋅⋅⋅an)，其中n≥0，n=0称为空表，a1称为始结点，an称为终结点，其余的结点ai有且仅有一个后继结点ai+1，有且仅有一个前趋结点ai−1。2.线性表具有以下特性（1）线性表中所有数据元素，其性质是相同的，即数据类型是一致的。（2）数据元素之间的相对位置是线性的。3.对线性表经常进行的一些操作(l)查找操作�查找第i个结点�查找值为x的结点(2)插入操作�在线性表的第i个结点前面插入一个新结点�在线性表的第i个结点后面插入一个新结点�在线性表的值为x的结点前面插入

8、一个新结点�在线性表的值为x的结点后面插入一个新结点(3)修改操作�用新结点替换线性表中的第i