数据结构第一章

数据结构（C语言版本）

9/21/2023前言传统的数值计算领域发展到非数值计算领域从简单的数值发展到一般的符号，进而发展到具有一定结构的数据。针对每一种新的应用领域的处理对象，如何选择合适的数据表示（结构），如何有效地组织计算机存贮，并在此基础上又如何有效地实现对象之间的“运算”关系。传统的解决数值计算的许多理论、方法和技术已不能满足解决非数值计算问题的需要，必须进行新的探索。数据结构就是研究和解决这些问题的重要基础理论。因此，“数据结构”课程已成为计算机类专业的一门重要专业基础课。计算机应用数据处理的对象目前面临的主要问题9/21/2023第1章绪论[目的]介绍数据结构中常用的基本概念和术语以及学习数据结构的意义。[要求]了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。[重点]了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系。[难点]算法复杂度的分析方法。9/21/20231.1引言

众所周知，二十世纪四十年代，电子数字计算机问世的直接原因是解决弹道学的计算问题。早期，电子计算机的应用范围，几乎只局限于科学和工程的计算，其处理的对象是纯数值性的信息，通常，人们把这类问题称为数值计算。近三十年来，电子计算机的发展异常迅猛，这不仅表现在计算机本身运算速度不断提高、信息存储量日益扩大、价格逐步下降，更重要的是计算机广泛地应用于情报检索、企业管理、系统工程等方面，已远远超出了科技计算的范围，而渗透到人类社会活动的一切领域。与此相应，计算机的处理对象也从简单的纯数值性信息发展到非数值性的和具有一定结构的信息。9/21/2023因此，再把电子数字计算机简单地看作是进行数值计算的工具，把数据仅理解为纯数值性的信息，就显得太狭隘了。现代计算机科学的观点，是把计算机程序处理的一切数值的、非数值的信息，乃至程序统称为数据（Data），而电子计算机则是加工处理数据（信息）的工具。由于数据的表示方法和组织形式直接关系到程序对数据的处理效率，而系统程序和许多应用程序的规模很大，结构相当复杂，处理对象又多为非数值性数据。因此，单凭程序设计人员的经验和技巧已难以设计出效率高、可靠性强的程序。于是，就要求人们对计算机程序加工的对象进行系统的研究，即研究数据的特性以及数据之间存在的关系——数据结构（DateStructure）。9/21/20231.2数据结构的发展简史及其在计算机科学中所处的地位发展史：1、“数据结构”作为一门独立的课程在国外是从1968年才开始设立的。2、1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。9/21/2023地位：“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。9/21/2023

1.3什么是数据结构

计算机解决一个具体问题时，大致需要经过下列几个步骤：首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法（Algorithm），最后编出程序、进行测试、调整直至得到最终解答。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。运算是由计算机来完成，这就要设计相应的插入、删除和修改的算法。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。直观定义：数据结构是研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。9/21/20231.4基本概念和术语1．数据

数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。例如，一个个人书库管理程序所要处理的数据可能是一张如表1-1所示的表格。9/21/2023

表1-1个人书库9/21/20232．结点结点也叫数据元素，它是组成数据的基本单位。在程序中通常把结点作为一个整体进行考虑和处理。例如，在表1-1所示的个人书库中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位来考虑，故该数据由10个结点构成。一般情况下，一个结点中含有若干个字段（也叫数据项）。例如，在表1-1所示的表格数据中，每个结点都有登录号、书号、书名、作者、出版社和价格等六个字段构成。字段是构成数据的最小单位。9/21/20233．逻辑结构结点和结点之间的逻辑关系称为数据的逻辑结构。在表1-1所示的表格数据中，各结点之间在逻辑上有一种线性关系，它指出了10个结点在表中的排列顺序。根据这种线性关系，可以看出表中第一本书是什么书，第二本书是什么书，等等。4．存储结构数据在计算机中的存储表示称为数据的存储结构。在表1-1所示的表格数据在计算机中可以有多种存储表示，例如，可以表示成数组，存放在内存中；也可以表示成文件，存放在磁盘上，等等。9/21/20235．数据处理数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。在早期，计算机主要用于科学和工程计算，进入八十年代以后，计算机主要用于数据处理。据有关统计资料表明，现在计算机用于数据处理的时间比例达到80%以上，随着时间的推移和计算机应用的进一步普及，计算机用于数据处理的时间比例必将进一步增大。9/21/20236．数据结构（DataStructure）数据结构是研究数据元素（DataElement）之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。为了叙述上的方便和避免产生混淆，通常我们把数据的逻辑结构统称为数据结构，把数据的物理结构统称为存储结构（StorageStructure）。9/21/2023四种基本数据结构：（1）集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。（2）线性结构：结构中的数据元素之间存在一个对一个的关系。如：图书馆的书目检索系统（3）树形结构：结构中的数据元素存在一个对多个的关系。如：计算机和人对奕问题工厂的组织管理（4）图状结构：结构中的数据元素存在多个对多个的关系。如：多叉路口的交通灯管理问题最短路径问题

同一个逻辑结构可以有不同的内部存储结构；反之，数据的存储结构一定要映像数据之间的逻辑关系。数据结构的形式定义：数据结构是一个二元组data_structure=(D,S)其中：D是数据元素的有限集，S是D上关系的有限集。

9/21/2023例1一种结构lineority=(K,R）K={k1,k2,k3,k4,k5,k6,k7}R={r}r={<k3,k1>,<k1,k5>,<k5,k6>,<k6,k4>,<k4,k2>,<k2,k7>}则有：k3->k1->k5->k6->k4->k2->k7一种线性结构例2tree=(K,R)K={01,02,03,04,05,06,07,08}R={r}r={<01,02>,<01,03>,<02,04>,<02,05>,<03,06>,<03,07>,<07,08>}树形结构

9/21/2023例3graph=(K,R)K={01,02,03,04,05,06}R={r}r={<01,02>,<02,01>,<01,04>,<04,01>,<02,03>,<02,06>,<06,02>,<05,03>,<03,04>,<04,03>}图形结构数据的逻辑结构分类：数据的逻辑结构线性结构非线性结构线性表树形结构图一般线性表特殊线性表线性表推广树二叉树有向图无向图线性表栈队列串数组广义表

9/21/2023数据的物理结构方面二种类型：顺序存储结构和非顺序存储结构

顺序存储结构：逻辑上相邻的数据元素存储在物理位置上相比邻的存储单元里，其关系由存储单元的邻接关系来体现（向量、数组）。

非顺序存储结构：数据元素在计算机内任意位置上存放，其关系用指针来链接，称为链式存储结构-链表。按指针个数分为：单链表、双向链表、多重链表

索引存储结构：按（地址关键字）的偶对集合，关键字是唯一标识结点；地址指出该结点的存储地址。

散列存储结构：根据结点关键字来直接算出该结点的存储地址。9/21/20237．数据类型数据类型是一个值的集合和定义在这个值上的一组操作的总称。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。9/21/2023三元组表示(DSP)抽象数据类型（AbstractDataType,ADT)一个数学模型以及定义在该模型上的一组操作，它仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。数据对象D上的关系集对D的基本操作集9/21/2023两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。ADT抽象数据类型名{数据对象：<数据对象的定义>数据关系：<数据关系的定义>基本操作：<基本操作的定义>}ADT抽象数据类型名其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：基本操作名（参数表）初始条件：<初始条件描述>操作结果：<操作结果描述>9/21/2023ADTTriplet{数据对象：D={e1,e2,e3|e1,e2,e3属于Elemset}数据关系：R1={<e1,e2>,<e2,e3>}基本操作：InitTriplet(&T,v1,v2,v3)操作结果：构造了三元组T,元素e1,e2,和e3分别被赋以参数v1,v2和v3的值。DestroyTriplet(&T)操作结果：三元组T被销毁。Get（T,I,&e)初始条件：三元组T已存在，1<=i<=3操作结果：用e返回T的第i元的值。}例抽象数据类型三元组的定义：9/21/2023简单地说就是解决特定问题的方法.数值算法解决数值问题的算法如求解数值积分，求解线性方程组、求解代数方程、求解微分方程等。非数值算法解决非数值问题的算法如排序算法、查找算法、插入算法、删除算法、遍历算法等。数值算法和非数值算法并没有严格的区别。递归算法和非递归算法8．算法从理论上讲，任何递归算法都可以通过循环，堆栈等技术转化为非递归算法。9/21/20231.5算法和算法的描述本书中“算法”和“程序”是通用的。1.5.1算法算法是执行特定计算的有穷过程。特点动态有穷确定性输入输出可行性算法和程序的区别9/21/2023

1.5.2算法的描述

一个算法可以用自然语言、数字语言或约定的符号来描述，也可以用计算机高级程序语言来描述，如Pascal语言、C语言或伪代码等。本书选用C语言作为描述算法的工具。现简单说明C语言的语法结构如下：9/21/20231．预定义常量和类型：#defineTRUE1；#defineFALSE-1；#defineERRORNULL；1.5.2算法的描述

本书选用C语言作为描述算法的工具。现简单说明C语言的语法结构如下：9/21/20232．函数的形式[数据类型]函数名（[形式参数]）[形式参数说明；]{内部数据说明；执行语句组；}/*函数名*/9/21/20233．赋值语句