1、2023-4-27华侨大学数学系 黄建新 数据结构（C语言版本）严蔚敏 吴伟民 编著2023-4-27华侨大学数学系 黄建新前前 言言 o二十一世纪是科学技术高速发展的信息时代，而计算机是处理信息的主要工具，因此，人们已经认识到，计算机知识已成为人类当代文化的一个重要组成部分。o 计算机科学技术以惊人的速度向前发展，它的广泛应用已从传统的数数值计算值计算领域发展到各种非数值计算非数值计算领域。在非数值计算领域里，数据处理的对象已从简单的数值发展到一般的符号，进而发展到具有一定结构的数据。在这里，面临的主要问题是：针对每一种新的应用领域的处理对象，如何选择合适的数据表示（结构），如何有效地组织计
2、算机存贮，并在此基础上又如何有效地实现对象之间的“运算”关系。传统的解决数值计算的许多理论、方法和技术已不能满足解决非数值计算问题的需要，必须进行新的探索。数据结构就是研究和解决这些问题的重要基础理论。因此，“数据结构”课程已成为计算机类专业的一门重要专业基础课。2023-4-27华侨大学数学系 黄建新 第1章 绪论2023-4-27华侨大学数学系 黄建新o 因此，再把电子数字计算机简单地看作是进行数值计算的工具，把数据仅理解为纯数值性的信息，就显得太狭隘了。现代计算机科学的观点，是把计算机程序处理的一切数值的、非数值的信息，乃至把计算机程序处理的一切数值的、非数值的信息，乃至程序统称为数据程
3、序统称为数据（Data），而电子计算机则是加工处理数据（信息）的工具。o由于数据的表示方法和组织形式直接关系到程序对数据的处理效率，而系统程序和许多应用程序的规模很大，结构相当复杂，处理对象又多为非数值性数据。因此，单凭程序设计人员的经验和技巧已难以设计出效率高、可靠性强的程序。于是，就要求人们对计算机程序加工的对象进行系统的研究，即研究数据的特性以及数据之间存研究数据的特性以及数据之间存在的关系在的关系数据结构（数据结构（Date Structure）。2023-4-27华侨大学数学系 黄建新o四种基本基本结构：（1）集合：结构中的数据元素之间除了“同属于一个集合”的关 系外，别无其他关系。
4、（2）线性结构线性结构：结构中的数据元素之间存在一个对一个的关系。如：图书馆的书目检索系统 （3）树形结构树形结构：结构中的数据元素存在一个对多个的关系。如：计算机和人对奕问题 工厂的组织管理 （4）图状结构图状结构：结构中的数据元素存在多个对多个的关系。如：多叉路口的交通灯管理问题 最短路径问题 同一个逻辑结构可以有不同的内部存储结构；反之，数据的存同一个逻辑结构可以有不同的内部存储结构；反之，数据的存储结构一定要映像数据之间的逻辑关系储结构一定要映像数据之间的逻辑关系。数据结构的形式定义：数据结构是一个二元组 data_structure=(D,S)其中：D是数据元素的有限集，S是D上关系
5、的有限集。2023-4-27华侨大学数学系 黄建新例1 一种结构 lineority=(K,R）K=k1,k2,k3,k4,k5,k6,k7 R=r r=,则有：k3-k1-k5-k6-k4-k2-k7 一种线性结构例2 tree=(K,R)K=01,02,03,04,05,06,07,08 R=r r=,树形结构 2023-4-27华侨大学数学系 黄建新 例3 graph=(K,R)K=01,02,03,04,05,06 R=r r=,图形结构 数据的逻辑结构分类：数据的逻辑结构 线性结构 非线性结构 线性表 树形结构 图 一般线性表 特殊线性表 线性表推广 树 二叉树 有向图 无向图 线性
6、表 栈 队列 串 数组 广义表 2023-4-27华侨大学数学系 黄建新 数据的物理结构方面 二种类型：顺序存储结构和非顺序存储结构 顺序存储结构顺序存储结构：逻辑上相邻的数据元素存储在物理位置上相比邻 的存储单元里，其关系由存储单元的邻接关系来 体现（向量、数组）。非顺序存储结构非顺序存储结构：数据元素在计算机内任意位置上存放，其关系 用指针来链接，称为链式存储结构-链表。按指针个数分为：单链表、双向链表、多重链表 索引存储结构索引存储结构：按（地址关键字）的偶对集合，关键字是唯一标 识结点；地址指出该结点的存储地址。散列存储结构散列存储结构：根据结点关键字来直接算出该结点的存储地址。202
7、3-4-27华侨大学数学系 黄建新 抽象数据类型（Abstract Data Type,ADT)是指一个数学模型以及定义在该模型上的一组操作，它仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。一个含抽象数据类型的软件模块通常应包含定义、表示和实现三个部分。抽象数据类型的三元组表示 (D S P),其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT抽象数据类型名 数据对象：数据关系：基本操作：ADT抽象数据类型名 其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为：基本操作名（参数表）初始条件：操作结果：2023-4-27华侨大学数学系 黄建新 基本操
8、作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。例 抽象数据类型三元组的定义：ADT Triplet 数据对象：D=e1,e2,e3|e1,e2,e3属于Elemset 数据关系：R1=,基本操作：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元的值。例1:+x;s=0;时间复杂度O(1)例2:forI=1;I=n
9、;+I+x;s+=x;时间复杂度为O(n)例3：for(j=1;j=n;+j)for(k=1;k=n;+k)+x;s+=x;时间复杂度为O(n2)2023-4-27华侨大学数学系 黄建新 情况1 当a中初始序列为自小到大有序时，基本操作的执行次数为0。情况2 当a中初始序列为自大至小有序时，基本操作的执行次数为n(n-1)/2。情况3 计算平均值 假设a中初始输入数据可出现n!种的排列次序的概率相等，则起泡排序的平均时间复杂度Targ(n)=O(n2)。在很多情况下，各种输入数据集出现的规律难以确定，算法的平均时间复杂度也就难以确定。因此，常用的办法是讨论算法在最坏情况下的时间复杂度。2、空间复杂度 空间复杂度是算法所需存储空间的量度，记作：S(n)=O(f(n)其中n为问题的规模（或大小）。nnTnT)(*)(nnT2)(nnnT)(nm)(n
