ds-1《数据结构C++版》PPT及练习答案

数据结构

徐虹/Jxgl/HomePage/Default.asp说明总学时：

64(学时)=50（课时）+14（实验）行课时间:第1~13周周学时:平均每周4学时上机安排待定考试时间：课程结束上机安排13级计算机数媒专业1、2班指导老师:时间：5-11周地点:计算机学院机房教材与参考书王红梅,胡明,王涛.数据结构（C++版）第2版.清华大学出版社万健，《数据结构实用教程》（C++版），电子工业出版社严蔚敏，《数据结构》，清华大学出版社CliffordA.Shaffer,《数据结构与算法分析》，电子工业出版社SartajSahni,《数据结构、算法与应用》,机械工业出版社严蔚敏，《数据结构题集》，清华大学出版社3.课程的内容与组织1.数据结构的研究对象课程简介数据是现实世界的数字化研究数据在计算机中的表示、关联、存储与处理方法2.课程的性质与定位数据组织与结构是计算机科学最基本内容，是人才信息素质的脊梁培养数据抽象能力，算法设计能力以及构造算法思维方法基本概念、基本结构、基本技术三层次用C++描述算法，突出算法实质例题、习题、典型题例、实习范例、课程设计全方位训练1.数据结构的研究对象

我们生活在一个物质的世界，计算机工作者又面对着数字的世界，如果将物质世界中的事与物数字化，那么它们在计算机中的表现均为数据。这些数据来源于现实，表征着具体的意义，而且在计算机中有着统一的表示方法，因而成为被计算机程序处理的符号集合。研究数据在计算机中的表示方法、关联方法、存储方法以及在其上的典型处理方法，就构成了数据结构课程的主要内容。

2.《数据结构》课程的性质与地位由于数据是计算机处理的对象，使用计算机的过程就是对数据进行加工处理的过程，因而数据的组织与结构被确立为计算机科学中最为基本内容。80年代初,《数据结构》课程就已成为国内计算机专业教学计划中的核心课程。

人类解决问题的思维方式可分为推理方式和算法方式两大类。推理方式凭借公理系统思维方法通过数学训练得到。算法方式则是凭借构造性思维，从具体操作规范入手，通过操作过程的构造实施来解决特定问题。

数据结构的学习过程，是算法构造性思维方法的训练过程，技能培养的重要程度不亚于知识传授。本门课程教学难点在于让学生理解、习惯算法构造思维方法。培养学生的数据抽象能力，算法设计能力以及创造性思维方法，才能够举一反三、触类旁通，从而达到应用知识解决复杂问题的目的。

数据结构是重要的专业基础课，是计算机科学的核心课程，是计算机理论与技术的重要基石。该课程在大学二年级下学期开设，具有承上启下的重要作用，既要对前一年学习的软件技术进行总结提高，又要为后续专业课程提供基础。它贯通始终，是计算机科学与技术人才素质培养框架中的中坚课程，对学生的软件开发能力培养有至关重要的作用，将为学生今后的专业生涯打下牢固基础。2.《数据结构》课程的性质与地位3.课程的内容与组织以抽象数据类型为中心，采用面向对象的新观点，将教学内容分为基本概念、基本结构、基本算法三个层次，并贯穿了计算机科学中的一些重要的问题求解技术，符合认知规律。使用熟悉的标准C++作为算法描述的语言，使之与大多数院校讲授的第一语言衔接，便于将读者的注意力集中在算法的理解上。这就使数据结构的表示得以简化，突出了算法表示的实质。例题、习题、典型题例、实习范例、课程设计全方位训练4.成绩计算平时成绩:30%

考勤+作业+半期考试+上机+实验报告+课堂表现考试成绩:70%学生的考核资格按下述原则审查：

学生有以下情况之一者，不能参加课程成绩考核，该课程的考核成绩以零分处理。在确定学籍处理、授予学士学位时，该门课程以考核不及格门次参加统计。全期旷课累计达该课程教学时数五分之一（含五分之一）以上者；全期缺交该课程任课教师布置作业三分之一（含三分之一）以上者；或全期所交该课程作业，虽达到任课教师布置作业三分之二以上，但所交作业的准确度、整洁度有二分之一不合格者；全期缺做该课程实习、实验或缺交实习、实验报告达三分之一（含三分之一）以上者；或全期参加该课程实习、实验，所交实习、实验报告都在三分之二以上，但有二分之一不合格者；未经批准或未办理选课手续，擅自修读该门课程者。目录

第一章：绪论第二章：线性表第三章：栈和队列第四章：串、数组和广义表第五章：树第六章：图第七章：查找

第八章：内部排序第一章绪论数据结构的有关概念算法和算法分析程序设计的实质是什么?数据表示：将数据存储在计算机（内存）中数据处理：处理数据，设计方案（算法）数据结构问题起源于程序设计

利用计算机求解问题的一般过程?计算机不能分析问题并产生问题的解决方案，必须由人来分析问题，确定问题的解决方案，编写程序，然后让计算机执行程序最终获得问题的解。1.1什么是数据结构数据结构的引论例1图书馆的书目检索系统自动化问题在书目自动检索系统中可以建立一张按等录顺序号排列的书目文件和三张分别按书名、作者名和分类号顺序排列的索引表，如下所示：001002003004高等数学理论力学高等数学线形代数樊映川罗远祥华罗庚栾汝书S01L01S01S02高等数学理论力学线形代数001,003,…002,…004,…LS002,001,003特点：计算机按某个特定的要求进行查询.处理对象之间存在一种简单的线形关系,这类模型可以称为简单的线形数据结构.按书名排列樊映川华罗庚栾汝书001,003,004,按作者排列按索引号排列例2:计算机和人的对弈问题对奕的过程是在一定的规则下随机进行的,因此,计算机必须对对弈过程之中可能发生的情况以及相应的对策都考虑周全.这个关系不是线形的,从一个棋盘可以派生出几个格局,如下图:

“树根”是对奕开始之前的棋盘格局,而所有的“叶子”是可能出现的结局,对奕的过程就是从树根沿树叉到达某个叶子的过程.******************(a)棋盘格式示例(b)井字棋对弈树的局部*例3七巧板涂色问题

如何表示区域之间的邻接关系？结论：综合上面三个例子,描述这类非数值计算性问题的数学模型不再是数学方程,而是诸如表、树和图之类的数据结构.数据结构定义:

数据结构是一门非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科.数据结构的地位

《数据结构》是计算机科学中一门综合性的专业基础课。可以认为数据结构是介于数学、计算机硬件、计算机软件三者之间的一门核心课程。1.2基本概念数据（Data)

客观事物的符号表示，能输入到计算机中并被计算机中程序处理的符号的总称。数据元素(Dataelement)

数据的基本单位，可由数据项组成。数据类型(DataType)

是和数据结构密切相关的一个概念，在高级语言中，用以刻画（程序）操作对象的特性。是一个值的集合和定义在这个值集上的一组操作的总称。数据对象(DataObject)

性质相同的数据元素的集合，是数据的子集。数据结构(DataStructure)

相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的相互关系称为结构。有下列四种基本结构：（1）集合（2）线形结构（3）树形结构（4）图状结构(网状结构）。

集合线性树图数据结构的二元组表示：Data_Structure=(D,S)其中：D是数据元素的有限集，S是D上关系的有限集数据结构类型数据的逻辑结构数据结构的形式定义：Data_Structure=[D,S,P]

其中：D是数据元素的有限集

S是上下关系的有限集

P是对数据对象的基本操作数据的物理结构（存储结构），数据结构基本操作的实现；数据的存储结构：位、元素和数据域数据结构的存储形式有：顺序存储链式存储逻辑结构例学生选课问题该问题可以用三张数据表来表示，每张表中每条记录为数据元素如表中数据元素是无序的，则数据表构成集合结构如表中数据元素是有序的，则数据表构成线性结构学生表课程表选课表学号姓名课程号课程名称学号课程号成绩S0001张三C0001数据结构S0001C000185S0002李四C0002操作系统S0001C000376S0005王五C0003编译原理S0002C000190C0004数据库原理S0002C000483S0003C000292逻辑结构例三维实体造型问题左图的机械零件可以分解成三个基本的实体模型通过布尔运算+和-操作得到右图构成了一个树型的数据结构，每一个节点为一个基本实体模型或通过布尔运算得到的复合实体模型逻辑结构例地图表示问题左图的地图经抽象可以得到右图的结构右图构成了图状的数据结构数据的物理结构例分别用顺序结构和链式结构来存储数列“10,20,30,40”数列的顺序存储结构数列的链式存储结构逻辑结构和存储结构之间的关系数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。

本书讨论非数值问题的数据组织和处理，主要内容如下：（1）数据的逻辑结构：线性表、树、图等数据结构，其核心是如何组织待处理的数据以及数据之间的关系；（2）数据的存储结构：如何将线性表、树、图等数据结构存储到计算机的存储器中，其核心是如何有效地存储数据以及数据之间的逻辑关系；（3）算法：如何基于数据的某种存储结构实现插入、删除、查找等基本操作，其核心是如何有效地处理数据；（4）常用数据处理技术：查找技术、排序技术、索引技术等。数据类型综述数据类型可以分为原子类型——值不可以分解结构类型——值由若干成分按某种结构组成。抽象数据类型（ADT）

ADT是一个值的集合和定义在这个值集上的一组操作的总称。包括：原子类型、固定聚合类型和可变聚合类型。是与具体计算机内部表示和实现方式无关的数据类型是由一个逻辑上的数学模型以及定义在该模型上的一组操作构成可以用三元组定义(D,S,P)D是数据对象S是D上的关系集P是对D的基本操作集1.3抽象数据类型的表示与实现基本概念—抽象数据类型在软件系统开发的全过程中，对客观现实中存在的事物，存在三个观察层面应用层是用户通过物理观察得到的客观事物的视图，是可以用自然语言描述的，或用图形、图像、音频、视频等物理量表达的在概念层次上的数据。逻辑层（抽象层）是从应用层次抽象出来的数据视图，利用抽象数据类型进行形式化描述。实现层明确地表示出了数据的组织与存储结构，并用某种具体的程序设计语言进行代码实现。抽象数据类型在设计ADT时，把ADT的定义、设计和实现分开来。定义部分只包含数据的逻辑结构和所允许的操作集合，一方面，ADT的使用者依据这些定义来使用ADT，即通过操作集合对该ADT进行操作；另一方面，ADT的实现者依据这些定义来完成该ADT各种操作的具体实现。抽象数据类型例ADTSet //集合的抽象数据类型{

数据对象：D＝{ai|ai∈ElemType,i=1,2,...,n,n≥0}数据关系：R={ai≠aj|ai,aj∈D}基本操作： Init() 操作结果：构造一个空的集合。 Destroy() 操作结果：销毁集合。 IsEmpty() 操作结果：判断集合是否为空，如为空，则返回TRUE；

否则返回FALSE。

Insert(e) 操作结果：在集合中加入一个元素。如元素已存在，

返回FALSE；否则返回TRUE。

Remove(e) 操作结果：在集合中移除一个元素。如元素存在，

则返回TRUE；否则返回FALSE。 IsMember(e) 操作结果：判断在集合中是否存在元素。 FindFirst(&e) 操作结果：找到集合中的第一个元素。

如成功，返回TRUE；如果集合为空，返回FALSE抽象数据类型例 FindFirst(&e) 操作结果：找到集合中的第一个元素。

如成功，返回TRUE；如果集合为空，返回FALSE FindNext(&e) 初始条件：已经执行过FindFirst或FindNext操作

操作结果：在上一次查找的前提下，找到集合中的下

一个元素；如成功，返回TRUE；如上次查找已到最后

一个元素，返回FALSE。

Union(s) 操作结果：与另一个集合s做并运算，返回并集。 Intersection(s)操作结果：与另一个集合s做交运算，返回交集。 Difference(s) 操作结果：与另一个集合s做差运算，返回差集。}数据操作描述数据的基本操作：

插入：在数据结构的指定位置添加新的数据元素。

删除：去掉数据结构中某个指定的数据元素。

更新：改变数据结构中某个数据元素的值。

查找：在数据结构中寻找某个满足特定要求的数据元素。

排序：重新安排数据元素的逻辑顺序关系，使之值按从小到大或从大到小的顺序排列。操作的分类加工型操作——操作改变了（操作之前的）结构的值。引用型操作——不改变值，只是查询或求得结构的值。操作的描述

语言的描述预定义常量和类型

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0Status是函数的类型，其值是函数结果状态代码

typedefintStatus;数据结构的表示用类型定义（typedef）描述，数据元素类型约定为ElemType，可以是C语言中任何数据类型。基本操作的算法用以下形式函数来描述函数类型函数名（函数参数表）

{

//算法说明语句序列

}//函数名

C++中操作的描述赋值语句循环语句选择语句注释结束语句输入和输出语句逻辑运算约定

用C++描述算法函数形式函数类型函数名(形参及类型说明){

函数语句部分return(表达式值)；

}函数中的形式参数有两种传值方式若为一般变量名，则为单向传值参数，若在变量前面增加“&”符号，则为双向传地址参数。例如有一个函数为voidswap(&i,&j,k)，则i，j为双向传地址参数，k为单向传值参数。函数的说明部分与函数的实现部分分离在C++中，用函数来描述算法时，为使之与面象对象的程序设计相匹配，一般将函数的说明部分与函数的实现部分分离