数据结构讲义第1章

《数据结构讲义第1章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构吴润秀南昌工程学院第1页2010-9-1数据结构的教学要求是：学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。数据结构的教学目的是：能将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与此同时，通过算法训练提高学生的思维能力；通过程序设计的技能训练学生的综合应用能力，提高学生的专业素质。第2页2010-9-1参考文献:《数据结构》（Ｃ语言版），李益明，电子工业出版社，２００６年《算法设计与实验题解》，王晓东，电子工业出版社，２

2、００７年第3页2010-9-1第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章动态存储管理第九章查找第十章排序目录第4页2010-9-11.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析目录第一章绪论第5页2010-9-11.1什么是数据结构计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示信息的处理而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用

3、程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。也就是“数据结构”学科形成和发展的背景。第6页2010-9-1众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？下面请看几个例子：第7页2010-9-1例1、电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1，b1)(a2，b

4、2)…(an，bn)其中ai，bi(i=1，2…n)分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。第8页2010-9-1算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数据的结构，直接影响算法的选择和效率。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，

5、bi)，1≤i≤n数据结构还要提供每种结构类型所定义的各种运算的算法。第9页2010-9-1例2：图书馆的书目检索系统自动化问题当你想借阅一本参考书但不知道书库中是否有的时候；或者，当你想找某一方面的参考书而不知图书馆内有哪些这方面的书时，你都需要到图书馆去查阅图书目录卡片。在图书馆内有各种名目的卡片：有按书名编排的、有按作者编排的、还有按分类编排的，等等。若利用计算机实现自动检索，则计算机处理的对象便是这些目录卡片上的书目信息。列在一张卡片上的一本书的书目信息可由登录号、书名、作者名、分类号、出版单位和出版时间等若干项组成，每一本书都有唯一的

6、一个登录号，但不同的书目之间可能有相同的书名、或者有相同的作者名或者有相同的分类号。由此，在书目自动检索系统中可以建立一张按登录号顺序排列的书目文件和三张分别按书名、作者名或分类号顺序排列的索引表。第10页2010-9-1001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02………...高等数学001,003,...理论力学002,...线性代数004,……...樊映川001,...华罗庚003,...栾汝书004,...……L002,...S001,003,...……以登入号为顺序的书目文件以

7、书名索引以作者名索引以分类号索引在这类管理的数学模型中，计算机处理的对象之间通常存在着的是一种最简单的线性关系，这类数学模型可称谓线性的数据结构。第11页2010-9-1例3：计算机和人对奕问题计算机之所以能和人对奕是因为有人对奕的策略事先存入计算机。由于对奕的过程是在一定规则下随机进行的，所以，为使计算机能灵活对奕就必须对对奕过程中所有可能发生的情况以及相应的对策都考虑周全，并且，一个“好”的棋手在对奕时不仅要看棋盘当时的状态，还应能预测棋局发展的趋势，甚至最后结局。因此，在对奕问题中，计算机操作的对象是对奕过程中可能出现的棋盘状态——称为格

8、局。第12页2010-9-1图：井字棋对奕“树”(a)棋盘格局示例；(b)对奕树的局