下载文档原格式
第一章绪论第一节什么是数据结构？估猜以下软件的共性：学生信息管理、图书信息管理、人事档案管理。
数学模型：用符号、表达式组成的数学结构，其表达的内容与所研究对象的行为、特性基本一致。
信息模型：信息处理领域中的数学模型。
数据结构：在程序设计领域，研究操作对象及其之间的关系和操作。
忽略数据的具体含义，研究信息模型的结构特性、处理方法。
第二节概念、术语一、有关数据结构的概念数据：对客观事物的符号表示。
例：生活中还有什么信息没有被数字化？身份证，汽车牌号，电话号码，条形代码……数据元素：数据的基本单位。
相当于"记录"。
一个数据元素由若干个数据项组成，相当于"域"。
数据对象：性质相同的数据元素的集合。
数据结构：相互之间存在特定关系的数据集合。
四种结构形式：集合、线性、树形、图(网)状形式定义：(D，S，P)D：数据元素的集合(数据对象)S：D上关系的有限集P：D上的基本操作集逻辑结构：关系S描述的是数据元素之间的逻辑关系。
存储结构：数据结构在计算机中的存储形式。
顺序映象、非顺序映象、索引存储、哈希存储逻辑结构与存储结构的关系：逻辑结构：描述、理解问题，面向问题。
存储结构：便于机器运算，面向机器。
程序设计中的基本问题：逻辑结构如何转换为存储结构？二、有关数据类型的概念数据类型：值的集合和定义在该值集上的一组操作的总称。
包括：原子类型、结构类型。
抽象数据类型(ADT)：一个数学模型及该模型上的一组操作。
核心：是逻辑特性，而非具体表示、实现。
课程任务：学习ADT、实践ADT。
如：线性表类型、栈类型、队列类型、数组类型、广义表类型、树类型、图类型、查找表类型……实践指导：为了代码的复用性，采用模块结构。
如：C中的头文件、C++中的类第三节 ADT的表示与实现本教材中，算法书写习惯的约定。
数据元素类型ElemType：int,float,char, char[] ……引用参数 &算法：void add(int a,int b,int &c) { c=a+b; }程序：void add(int a,int b,int *p_c){ *p_c=a+b; }第四节算法的描述及分析一、有关算法的概念算法：特定问题求解步骤的一种描述。
数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。
换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。
包括数值、字符、声数据元素是组成数据的基本单位一个数据元素可由若干个数据项组成（）数据对象是性质相同的数据元素的集合，是数据的一个子集。
…}，字母字符数据对象是集合象。
由此可看出，不论数据元素集合是无限集（如整数集）Data Structure）数据元素相互之间的关系称为结构（ Structure ），有四种基本结构。
集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。
线性结构：结构中的数据元素之间存在着一对一的线性关系。
图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。
为数据结构的有限集，S是D上关系的有限集。
表示复数的虚部。
存储结构（又称物理结构）是逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括据元素的表示和关系的表示形式化描述：要存入机器中，建立一从，使S（D逻辑结构与存储结构的关系为：数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。
按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，(Data Type)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称合，即该类型的取值范围，以及该类型中可允许使用的一组运算。
例如高级语言中的数据类型就是已经实现的从这个意义上讲，数据类型是高级语言中允许的变量种类，计算机中使用的是二进制数，汇编语言中则可给出各种数据的十进制表示，如二进制数据的抽象; 使用者在编程时可以直接使用据抽象，出现了数据类型，(Abstract Data Type)）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。
抽象数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。
《数据结构》讲义什么是数据结构计算机解题步骤：建立数学模型——设计解此数学模型的算法——编制程序——进行测试调整——解答。
其中建立数学模型的实质：找出操作对象之间的关系。
例1. 图书馆书目检索——对应线性关系例2. 博奕树——对应树型关系例3. 交叉路口交通灯管理——对应图状结构。
数据结构是一门研究非数值计算的程序设计问题中（地计算机的操作对象及它们之间的关系和操作等的学科。
位）数据结构的基本概念和术语1. 数据（Data）数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。
换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。
包括数值、字符、声音、图象等。
2. 数据元素（Data Element）数据元素是组成数据的基本单位, 是数据集合的个体，在计算机中通常作为一个逻辑整体进行考虑和处理。
一个数据元素可由若干个数据项组成（Data Item）。
3. 数据对象（Data Object）数据对象是性质相同的数据元素的集合，是数据的一个子集。
例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={′A′，′B′，…，′Z′}，表1-1所示的学籍表也可看作一个数据对象。
由此可看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素（如学籍表），只要性质相同，都是同一个数据对象。
综上1~3所述，再分析数据概念：4. 结构（Data Structure）数据元素相互之间的关系称为结构（ Structure ），有四种基本结构。
(1) 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。
(2) 线性结构：结构中的数据元素之间存在着一对一的线性关系。
(3) 树形结构：结构中的数据元素之间存在着一对多的层次关系。
(4) 图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。
《数据结构》讲义数据结构是计算机科学和编程中非常重要的概念之一。
它是指在计算机中存储和组织数据的方法和原则。
一、介绍数据结构在计算机科学领域中具有重要的地位。
它涉及到如何存储和组织数据，以便于对其进行检索和操作。
数据结构可以分为两种基本类型：线性结构和非线性结构。
线性结构包括数组、链表、栈和队列，而非线性结构包括树和图。
二、线性结构1. 数组数组是一种用来存储多个相同类型的元素的数据结构。
它具有固定长度和连续的内存空间。
数组可以通过索引访问元素，可以快速地插入和删除元素，但是其长度固定不变。
2. 链表链表是一种由节点组成的数据结构，每个节点都包含一个值和指向下一个节点的指针。
链表可以在任意位置插入和删除节点，但是访问节点的时间复杂度较高。
3. 栈栈是一种具有特定操作限制的线性结构。
它遵循“先进后出”的原则，即最后插入的元素最先被访问和删除。
栈可以用来实现递归、回溯和表达式求值等功能。
4. 队列队列也是一种具有特定操作限制的线性结构。
它遵循“先进先出”的原则，即最先插入的元素最先被访问和删除。
队列可以用来实现任务调度、缓冲区等功能。
三、非线性结构1. 树树是一种由节点组成的非线性结构。
它包含一个根节点和多个子节点，每个节点可以有任意数量的子节点。
树可以用来表示层次关系、排序和搜索等功能。
2. 图图是一种由节点和边组成的非线性结构。
节点表示实体，边表示节点之间的关系。
图可以用来表示网络、关系和路径等信息。
四、常用数据结构在实际编程中，还有一些常用的数据结构：1. 哈希表：通过哈希函数将元素映射到不同的位置，实现快速的查找和插入操作。
2. 堆：一种特殊的树结构，可以快速找到最大或最小的元素。
3. 二叉搜索树：一种有序的二叉树，可以高效地进行搜索和插入操作。
五、应用场景数据结构在实际开发中有广泛的应用场景，包括但不限于以下几个方面：1. 数据库系统中的索引结构：为了快速检索数据，数据库系统使用各种数据结构来组织数据。
数据结构基础讲义在计算机科学领域中，数据结构是一门极其重要的基础课程。
它就像是一座桥梁，连接着程序设计和算法分析，为我们解决各种实际问题提供了有力的工具。
接下来，让我们一起走进数据结构的世界，探索其中的奥秘。
一、什么是数据结构简单来说，数据结构就是数据的组织方式和存储结构。
我们在编程中处理的数据，比如整数、字符串、数组等，都需要以某种特定的方式进行组织和存储，以便能够高效地进行操作和处理。
打个比方，我们要整理一个书架上的书籍。
如果随意摆放，找书的时候就会很麻烦。
但如果按照一定的规则，比如按照作者的姓氏字母顺序或者书籍的类别进行排列，那么找书就会变得容易很多。
同样的道理，在计算机中，合理的数据结构可以让我们更快地访问、修改和处理数据。
二、常见的数据结构类型1、数组数组是一种最简单、最常见的数据结构。
它是一组具有相同数据类型的元素的有序集合。
在内存中，数组的元素是连续存储的，这使得我们可以通过索引快速访问到特定位置的元素。
例如，如果我们有一个整数数组｀int arr5 ＝｛10, 20, 30, 40, 50}｀，要访问第三个元素，只需要使用｀arr2` 就可以得到 30。
然而，数组也有它的局限性。
一旦数组的大小被定义，就很难动态地改变。
而且，插入和删除元素的操作可能会比较复杂，因为需要移动大量的元素。
2、链表链表则是一种动态的数据结构。
它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
链表的优点是插入和删除操作相对简单，只需要修改指针即可。
但访问特定位置的元素就没有数组那么高效了，因为需要从头节点开始逐个遍历。
3、栈栈是一种特殊的线性表，它遵循“后进先出”（Last In First Out，LIFO）的原则。
想象一下叠盘子，最后放上去的盘子总是最先被拿走，这就是栈的工作方式。
在程序中，栈常用于函数调用、表达式求值等场景。
4、队列与栈相反，队列遵循“先进先出”（First In First Out，FIFO）的原则。
《数据结构》讲义第一章：绪论课程：数据结构课题：第一章 1.1—1.4小节（共4个课时）1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表现与实现1.4 算法和算法分析目的要求：理解数据、数据元素、数据项的概念；掌握逻辑结构和存储结构的关系；理解算法的基本概念；学会分析算法的时间复杂性和空间复杂性。
新课重点、难点：数据、数据元素、数据项、时间复杂性和空间复杂性教学方法：课堂讲解、例题演示，课件演示教学内容及过程：……………………………第1-2课时……………………………计算机的应用不再局限于科学计算，更多地用于控制，管理，数据处理等非数值计算的处理工作。
计算机加工处理的对象：数值，字符，表格，图形声音，图象等具有一定结构的数据。
进行程序设计时必须分析待处理的对象的特性及各对象之间存在的关系———产生背景。
子集。
例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={′A′，′B′，…，′Z′}，表1-1所示的学籍表也可看作一个数据对象。
由此可看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素（如学籍表），只要性质相同，都是同一个数据对象。
综上1~3所述，再分析数据概念：4. 结构（Data Structure）数据元素相互之间的关系称为结构（ Structure ），有四种基本结构。
(1) 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。
(2) 线性结构：结构中的数据元素之间存在着一对一的线性关系。
(3) 树形结构：结构中的数据元素之间存在着一对多的层次关系。
(4) 图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。
线性结构——线性表、栈、队、字符串、数组、广义表非线性结构——树、图数据结构的形式定义：数据结构是一个二元组 Data_structure=(D,S) 。
其中：D为数据结构的有限集，S是D上关系的有限集。
例：复数结构Complex=(C,R)其中：C为含两个实数的集合{c1,c2}；R={P}， P是集合C上的一种关系，P={<c1,c2>}，<c1,c2>为有序偶，c1表示复数的实部，c2表示复数的虚部。
存储结构存储结构（又称物理结构）是逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。
形式化描述：D要存入机器中，建立一从D的数据元素到存储空间M单元的映象S，D→M，即对于每一个d，d ∈D, 都有唯一的m∈M，使S（D）=m, 同时这个映象必须明显或隐含地体现关系R。
逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身的映象。
逻辑结构是数据结构的抽象，存储结构是数据结构的实现，两者综合起来建立了数据元素之间的结构关系。
顺序映象（顺序存储结构）顺序结构用元素在存储器中的相对位置表示数据元素之间的逻辑关系。
非顺序映象（非顺序存储结构）非顺序映像借助指示元素存储地址的指针表示元素之间的逻辑关系。
一维数组来描述顺序存储结构，用指针来描述链式存储结构。
运算的集合数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。
按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。
数据类型(Data Type)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。
数据类型中定义了两个集合，即该类型的取值范围，以及该类型中可允许使用的一组运算。
例如高级语言中的数据类型就是已经实现的数据结构的实例。
从这个意义上讲，数据类型是高级语言中允许的变量种类，是程序语言中已经实现的数据结构（即程序中允许出现的数据形式）。
在高级语言中，整型类型可能的取值范围是-32 768~+32 767，可用的运算符集合为加、减、乘、除、取模（如C语言中+， -， *， /， %）。
抽象数据类型１）数据的抽象计算机中使用的是二进制数，汇编语言中则可给出各种数据的十进制表示，如98.65、 9.6E3等, 它们是二进制数据的抽象; 使用者在编程时可以直接使用, 不必考虑实现细节。
在高级语言中，则给出更高一级的数据抽象，出现了数据类型，如整型、实型、字符型等。
到抽象数据类型出现，可以进一步定义更高级的数据抽象，如各种表、队、栈、树、图、窗口、管理器等，这种数据抽象的层次为设计者提供了更有利的手段，使得设计者可以从抽象的概念出发，从整体考虑，然后自顶向下、逐步展开，最后得到所需结果。
可以这样看，高级语言中提供整型、实型、字符、记录、文件、指针等多种数据类型，可以利用这些类型构造出像栈、队列、树、图等复杂的抽象数据类型。
２）抽象数据类型 (Abstract Data Type)抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。
抽象数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。
从某种意义上讲，抽象数据类型和数据类型实质上是一个概念。
整数类型就是一个简单的抽象数据类型实例。
“抽象”的意义在于教学特性的抽象。
一个ADT定义了一个数据对象，数据对象中各元素间的结构关系，以及一组处理数据的操作。
ADT 通常是指由用户定义且用以表示应用问题的数据模型，通常由基本的数据类型组成，并包括一组相关服务操作。
抽象数据类型是近年来计算机科学中提出的最重要的概念之一，它集中体现了程序设计中一些最基本的原则：分解、抽象和信息隐藏。
一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来。
数学模型→抽象数据类型→数据结构，恰好反应了信息结构转换的三个重要阶段，而在这个转换过程中，数据结构是基础，抽象数据类型是中枢。
一个线性表的抽象数据类型的描述如下：ADT Linear-list数据元素所有ai属于同一数据对象，i=1，2，…，n, n≥0；逻辑结构所有数据元素ai（i=1，2，…，n-1）存在次序关系<ai，ai+1>，ai无前趋，an无后继；操作设L为Linear-list:Initial(L): 初始化空线性表;Length(L): 求线性表的表长;Get(L, i): 取线性表的第i个元素；Insert(L, i, b): 在线性表的第i个位置插入元素b；Delete(L, i): 删除线性表的第i个元素。
３）抽象数据类型实现第一种情况：传统的面向过程的程序设计。
第二种情况：“包”、“模型”的设计方法。
第三种情况：面向对象的程序设计（Object Oriented Programming，简称OOP）。
４） ADT的定义ADT的定义格式不唯一, 我们采用下述格式定义一个ADT:ADT 抽象数据类型名{数据对象: <数据对象的定义>数据关系: <结构关系的定义>基本操作: <基本操作的定义>}ADT 抽象数据类型名其中数据对象和结构关系的定义采用数学符号和自然语言描述, 而基本操作的定义格式为:操作名称 (参数表)初始条件: <初始条件描述>操作结果: <操作结果描述>关于参数传递参数表中的参数有两种：第一种参数只为操作提供待处理数据, 又称值参；第二种参数既能为操作提供待处理数据, 又能返回操作结果，也称变量参数。
操作前提描述了操作执行之前数据结构和参数应满足的条件, 操作结果描述操作执行之后, 数据结构的变化状况和应返回结果。
ADT可用现有计算机语言中已有的数据类型, 即固有数据类型来表示和实现。
不同语言的表示和实现方法不尽相同，如ADT中“返回结果的参数”， PASCAL语言用“变参” 实现, C++语言通过“引用型参数”实现, 而C语言用“指针参数”实现。
用标准C语言表示和实现ADT描述时，主要包括以下两个方面:(1) 通过结构体将int、 float等固有类型组合到一起, 构成一个结构类型, 再用typedef为该类型或该类型指针重新起一个名字。
(2) 用C语言函数实现各操作。
基本操作主要有以下几种：(1) 插入：在数据结构中的指定位置上增添新的数据元素；(2) 删除：删去数据结构中某个指定数据元素；(3) 更新：改变数据结构中某个元素的值，在概念上等价于删除和插入操作的组合；(4) 查找：在数据结构中寻找满足某个特定要求的数据元素（的位置和值)；(5) 排序：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使数据元素按值由小到大或由大到小的次序排列。
结构化的开发方法与面向对象的开发方法的不同点，结构化的开发方法是面向过程的开发方法，首先着眼于系统要实现的功能。
从系统的输入和输出出发，分析系统要实现的功能，用自顶向下、逐步细化的方式建立系统的功能结构和相应的程序模块结构。
一旦程序功能需要修改，就会涉及多个模块，修改量大，易于出错，并会引起程序的退化。
作业1：1：理解和掌握几个重要的基本概念：数据结构；抽象数据类型等；2：理解和运用四种逻辑结构；并进行合理的划分。
……………………………第3-4课时……………………………1．3 抽象数据类型的表示和实现(1) 预定义常量和类型。
本书中用到以下常量符号，如True、 False、MAXSIZE 等，约定用如下宏定义预先定义：＃ define TRUE 1＃ define FALSE 0＃ define MAXSIZE 100＃ define OK 1＃ define ERROR 0(2) 本书中所有的算法都以如下的函数形式加以表示，其中的结构类型使用前面已有的定义。
［数据类型］函数名（［形式参数及说明］）{ 内部数据说明；执行语句组；} /*函数名*/函数的定义主要由函数名和函数体组成，函数体用花括号“{”和“}”括起来。
函数中用方括号括起来的部分如“［形式参数］”为可选项，函数名之后的圆括号不可省略。
(3) 赋值语句。
1、简单赋值;（1）〈变量名〉=〈表达式〉，它表示将表达式的值赋给左边的变量；（2）〈变量〉++，它表示变量加1后赋值给变量；（3）〈变量〉--，它表示变量减1后赋值给变量。
2、串联赋值#;〈变量1〉=〈变量2〉=〈变量3〉=…=〈变量k〉=〈表达式〉；3、成组赋值#;（〈变量1〉，〈变量2〉，〈变量3〉，…, 〈变量k〉)=（〈表达式1〉，〈表达式2〉，〈表达式3〉，…, 〈表达式k〉）；〈数组名1〉［下标1］［下标2］=〈数组名2〉［下标1］［下标2］；4、条件赋值;〈变量名〉=〈条件表达式〉？〈表达式1〉: 〈表达式2〉；(4) 条件选择语句。
