第1章数据结构0.ppt-新闻动态.pptVIP

数据结构 孙爽滋 前言 计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题： 信息的表示 信息的处理 而信息的表示和存储又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。 　 数据结构 * * 什么是数据结构 众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看下面的例子。 例 电话号码查询系统 编一个查询某个城市或单位的私人电话号码的程序。要求对任意给出的一个姓名，若该人有电话号码，则迅速找到其电话号码；否则指出该人没有电话号码。 例1电话号码查询系统 要解此问题首先构造一张电话号码登记表。表中每个结点(元素)存放两个数据项： 姓名和电话号码。 要写出好的查找算法，取决于这张表的结构及存储方式。 最简单的方式是将表中结点（元素）顺序地存储在计算机中。查找时从头开始依次查对姓名，直到找出正确的姓名或是找遍整个表均没有找到为止。 这种查找算法对于一个不大的单位或许是可行的，但对一个有成千上万私人电话的城市就不实用了。 例1电话号码查询系统 若这张表是按姓氏排列的，则可另造一张姓氏索引表，采用如图所示的存储结构。 ??  那么查找过程是先在索引表中查对姓氏，然后根据索引表中的地址到电话号码登记表中核查姓名，这样查找登记表时就无需查找其它姓氏的名字了。因此，在这种新的结构上产生的查找算法就更为有效。 分析下面文字的含义： 漆黑的头发没有麻子脚不大周正 演绎１ 漆黑的头发，没有麻子，脚不大，周正。 结论：描述一个古代美人！ ??  演绎２ 漆黑的头发没有，麻子，脚不大周正。 结论：描述了一个古代丑女人，还是个瘸子。 结论 两个不同的演绎表现为不同的结果，一个是古代美人，一个确实古代丑女人，原因只是文字的不同组合造成！ 也就是说：相同的文字（数据）经过不同的组合（结构）会得到不同的结果，这就是我们要介绍的数据结构：数据及其之间的关系（结构）。 国家等级考试大纲要求 1. 算法的基本概念；算法复杂度的概念和意义（时间复 杂度与空间复杂度）。2. 数据结构的定义；数据的逻辑结构与存储结构；数据 结构的图形表示；线性结构与非线性结构的概念。3. 线性表的定义；线性表的顺序存储结构及其插入与删 除运算。4. 栈和队列的定义；栈和队列的顺序存储结构及其基本 运算。5. 线性单链表、双向链表与循环链表的结构及其基本运 算。6. 树的基本概念；二叉树的定义及其存储结构；二叉树 的前序、中序和后序遍历。7. 顺序查找与二分法查找算法；基本排序算法（交换类 排序，选择类排序，插入类排序）。 * *