数据结构c语言描述第1章

《数据结构c语言描述第1章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录第1章绪论第2章线性表第3章限定性线性表—栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第8章查找第9章内部排序第10章外部排序第1章绪论1.1什么是数据结构（定义）1.2数据结构的内容1.3算法1.4算法描述的工具1.5对算法作性能评价1.6关于学习数据结构1.1什么是数据结构（定义）1.数据（Data）　数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述。简而言之，数据就是计算机化的信息。例如对C源程序，数据概念不仅是源程

2、序所处理的数据，相对于编译程序来说，C编译程序相对于源程序是一个处理程序，它加工的数据是字符流的源程序（.c），输出的结果是目标程序(.obj)；对于链接程序来说，它加工的数据是目标程序(.obj)，输出的结果是可执行程序(.exe)，如图1.1所示。C编译程序C链接程序源程序目标程度可执行程序图1.1编译程序示意图2.数据元素（DataElement）　数据元素是组成数据的基本单位,是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。表1-1学籍表数据项学号姓名性别籍贯出生年月住址101赵红玲女河北1983.11北京…………

3、……记录3.数据对象（DataObject）数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={′A′，′B′，…，′Z′}，表1-1所示的学籍表也可看作一个数据对象。由此可看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素（如学籍表），只要性质相同，都是同一个数据对象。综上1~3所述，再分析数据概念：4.数据结构（DataStructure）数据结构是指相互之间存在一种或多种特定关系的数据元素集合，学校系

4、处研究机构教研室实验室图1.2学校组织层次结构图12534图1.3交通流量图5.数据类型(DataType)数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。数据类型中定义了两个集合，即该类型的取值范围，以及该类型中可允许使用的一组运算。例如高级语言中的数据类型就是已经实现的数据结构的实例。从这个意义上讲，数据类型是高级语言中允许的变量种类，是程序语言中已经实现的数据结构（即程序中允许出现的数据形式）。在高级语言中，整型类型可能的取值范围是-32768~+32767，可用的运算符集合为加、减、乘、除、乘方、取模（如

5、C语言中+，-，*，/，%）。6.数据抽象与抽象数据类型１）数据的抽象　计算机中使用的是二进制数，汇编语言中则可给出各种数据的十进制表示，如98.65、9.6E3等,它们是二进制数据的抽象;使用者在编程时可以直接使用,不必考虑实现细节。在高级语言中，则给出更高一级的数据抽象，出现了数据类型，如整型、实型、字符型等。到抽象数据类型出现，可以进一步定义更高级的数据抽象，如各种表、队、栈、树、图、窗口、管理器等，这种数据抽象的层次为设计者提供了更有利的手段，使得设计者可以从抽象的概念出发，从整体考虑，然后自顶向下、逐步展开，最后得到所需结果

6、。可以这样看，高级语言中提供整型、实型、字符、记录、文件、指针等多种数据类型，可以利用这些类型构造出像栈、队列、树、图等复杂的抽象数据类２）抽象数据类型(AbstractDataType)抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。抽象数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。从某种意义上讲，抽象数据类型和数据类型实质上是一个概念。整数类型就是一个简单的抽象数据类型实例。“抽象”的意义

7、在于教学特性的抽象。一个ADT定义了一个数据对象，数据对象中各元素间的结构关系，以及一组处理数据的操作。ADT通常是指由用户定义且用以表示应用问题的数据模型，通常由基本的数据类型组成，并包括一组相关服务操作。抽象数据类型是近年来计算机科学中提出的最重要的概念之一，它集中体现了程序设计中一些最基本的原则：分解、抽象和信息隐藏。一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来。图1.4用抽象数据类型指导问题求解数学模型→抽象数据类型→数据结构，恰好反应了信息结构转换的三个重要阶段，而

8、在这个转换过程中，数据结构是基础，抽象数据类型是中枢。　一个线性表的抽象数据类型的描述如下：　ADTLinear-list数据元素所有a属于同一数据对象，i=1，2，…，n,in≥0；逻辑结构所有数据元素a（i=1，2，