电子商务网站建设 代码,江阴网站设计,专业网站设计服务在线咨询,wordpress询价管理【内容简介】本文整理数据结构#xff08;C语言版#xff09;相关内容的复习笔记#xff0c;供各位朋友借鉴学习。本章内容更偏于记忆和理解#xff0c;请读者们耐心阅读。 数据结构教程 绪论#xff08;上#xff09; 本节学习目标 1.1 基本概念 1.2 抽象数据类型的表示… 【内容简介】本文整理数据结构C语言版相关内容的复习笔记供各位朋友借鉴学习。本章内容更偏于记忆和理解请读者们耐心阅读。 数据结构教程 · 绪论上 本节学习目标 1.1 基本概念 1.2 抽象数据类型的表示与实现 本节学习目标
熟悉数据结构相关的一些概念和术语了解如何书写抽象数据类型的形式定义
1.1 基本概念
下面我们简要介绍一下数据结构相关的一些概念和术语这在之后的学习过程中都经常会用到。
1、数据data是所有能输入到计算机中并被计算机程序处理的符号的总称。例如声音、图像、字符串等等。
2、数据元素data system是数据的基本单位。例如下面这张“图”中由许多圆圈组成这些圆圈就可以认为是数据元素。 3、数据项data item是组成数据元素的单位也是数据的不可分割的最小单位。例如书籍的目录对于这本书而言是一个数据元素目录中每一章的信息章名、页码等就是一个数据项。
4、数据对象data object是性质相同的数据元素的集合是数据的一个子集。例如整数数据对象是集合 N {0,1,-1,2,-2,···}。
以上是数据的一些详细概念。而我们着重要学习的数据结构data structure是相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的关系称为结构structure。一般而言数据元素之间存在以下 4 种基本结构
集合结构中的数据元素之间除了“同属于一个集合”之外没有其它关系。线性结构结构中的数据元素之间存在一个对一个的关系。树形结构结构中的数据元素之间存在一个对多个的关系。图状结构或网状结构结构中的数据元素之间存在多个对多个的关系。 数据的定义方式并不唯一除上述之外还有一种形式定义数据结构是一个二元组
Data_Structure { DS }
其中D 是数据元素的有限集S是D上存在的关系的有限集。这样的说法比较抽象我们举个例子 【例1】现在我们需要编写一个公司职工管理系统那么我们首先需要构思这个系统中的数据结构。假设这个公司有 1 个董事长1 个总经理和 3 个员工那么这个公司的职工之间存在的关系是董事长管理总经理总经理管理员工。则可以定义如下的数据结构 Group ( PR ) 其中P 包含这个公司的所有职员 R { R1R2 } R1 { 董事长总经理 } R2 { 总经理员工1总经理员工2总经理员工3 }。 上述定义仅仅只是一种从对象的角度抽象出来的数学模型。结构定义中的“关系”描述为数据元素之间的逻辑关系因此又称为数据的逻辑结构。
但是为了在计算机中实现对其的操作还需要研究在计算机中如何来表示一个数据结构。数据结构在计算机中的表示称为数据的物理结构又称为存储结构。它包括数据元素的表示以及关系的表示。在计算机中表示信息的最小单位是二进制数的一位叫做位bit。由若干个位组成的位串表示一个数据元素通常称为元素或结点例如用 8 位二进制数表示一个字符。
数据元素之间的关系在计算机中有两种不同的表示方法顺序映像和非顺序映像并由此得到两种不同的存储结构顺序存储结构和链式存储结构。
顺序映像的特点是借助元素在存储器中的相对位置来表示逻辑关系例如假设用 2 个字长的位串表示一个实数则相邻 4 个字长的位串可以表示一个复数。而对于非顺序映像而言通常通过指针来指示元素存储地址从而将数据元素之间的逻辑关系表示出来。如下图所示 而存储结构可以分别用“一维数组”来描述顺序存储结构用“指针”描述链式存储结构。
数据类型data type是和数据结构密切相关的一个概念。它包括了一个值的集合和定义在这个值集上的一组操作的总称。例如C语言中的整型变量其值集为某个区间上的整数定义在上面的操作为加、减、乘、除和取模等算术运算。根据“值”的不同数据类型可分为两类一类是不可分解的原子类型例如实数一类是由若干成分按某种结构组成可以分解的结构类型例如数组。
1.2 抽象数据类型的表示与实现
抽象数据类型abstract data type简称 ADT是指一个数学模型以及定义在该模型上的一组操作。也就是说只要这个数据类型的逻辑特性不发生变化就不影响它在外部的使用类似我们常说的“面向对象的设计”原则。
一个含抽象数据类型的软件模块通常应包含定义、表示和实现 3 个部分。由于抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。按照其值的不同特性可以分为原子类型、固定聚合类型、可变聚合类型。后两者分别代表组成值的成分数量一定或是可变。
与数据结构的形式定义类似抽象数据类型可用以下三元组表示( DSP )。其中D 是数据对象S 是 D 上的关系集P 是对 D 的基本操作集。具体来书写可以如下
ADT 抽象数据类型名 {数据对象数据对象的定义数据关系数据关系的定义基本操作基本操作的定义
} ADT 抽象数据类型名
其中数据对象和数据关系的定义用伪码描述基本操作的定义格式为
基本操作名参数表初始条件初始条件描述操作结果操作结果描述
基本操作有两种参数赋值参数只为操作提供输入值引用参数以 打头除了提供输入值以外还将返回操作结果。 【例2】一个抽象数据类型三元组的定义 ADT Triplet { 数据对象D {e1, e2, e3 | e1, e2, e3 属于这个集合} 数据关系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 已存在i 1,2,3。 操作结果用 e 返回 T 中第 i 个元素的值。 ... } ADT Triplet 继续阅读下一篇点击跳转【C语言版】数据结构教程一绪论下
