《数据结构与算法 C语言版》—— 第1章 绪论

前言 "数据结构"是计算机程序设计的重要理论技术基础,是计算机学科的核心课程,也是计算机专业考研的必考课程,同时已成为其他理工科专业的热门课程.学好该课程,不仅对学习后续算法设计.数值分析.操作系统.编译原理等课程有很大帮助,而且在实际中有广泛的用途. 数据结构主要研究数据的各种组织形式以及建立在这些结构之上的各种运算的实现.它不仅为用计算机语言进行程序设计提供了方法性的理论指导,还在一个更高的层次上总结了程序设计的常用方法和常用技巧. "数据结构"课程的特点是概念

3.1栈 3.1.1栈的抽象数据类型定义 栈(stack)是限定仅在表尾进行插入或删除操作的线性表.表尾端称为栈顶,表头端称为栈底.不含元素的栈称为空栈.由于后进栈的元素先出栈,所以栈又称为后进先出(Last In First Out,LIFO)的线性表. 在日常生活中,有很多后进先出的例子.例如,铁路调度站火车的进出是后进先出,人们脱衣服是后穿先脱等.在程序设计中,也常用栈这样的数据结构,实现与保存数据相反的顺序来使用这些数据. 栈的操作有栈的初始化.判空.进栈.出栈及取栈顶元素等.下面给出栈

1.1数据结构的研究对象 自然界中的许多问题是可以用数学工具进行描述的.例如,造桥中的受力问题可描述为线性方程,人口增长的情况可描述为微分方程.但更多的非数值计算问题无法用数学方程加以描述.因此,解决这类问题的关键不再是数学分析和计算方法,而是要设计出合适的数据结构,才能有效地解决问题.请看以下列举的具体问题.例1学生信息检索系统.当我们需要查找某个学生的有关信息或某个专业的情况时,只要建立了相应的数据结构,按照某种算法编写了程序,就可以实现计算机自动检索.由此,可以在学生信息检索系统中建立一个

1.4数据类型与抽象数据类型 1.4.1数据类型 数据类型是和数据结构密切相关的一个概念,它最早出现在高级程序语言中,用以刻画(程序)操作对象的特性.在用高级程序语言编写的程序中,每个变量.常量或表达式都有一个它所属的确定的数据类型.类型显式或隐含地规定了在程序执行期间变量或表达式所有可能的取值范围,以及在这些值上允许进行的操作.因此,数据类型是一个值的集合和定义在此集合上的一组操作的总称.例如,C语言中的整型变量,其值为某个区间上的整数(依赖于机器),定义在其上的操作为加.减.乘.除和取模等算

1.5算法与算法分析 算法与程序设计和数据结构密切相关.简单地说,算法是解决问题的策略.规则.方法.算法的具体描述形式很多,但计算机程序是对算法的一种精确描述,而且可在计算机上运行.数据结构的操作的实现方法就是一个算法问题,但该问题是针对数据结构的,是在给定的数据结构上进行的.下面从算法的特性.算法描述.算法性能分析与度量等方面对算法进行介绍. 1.5.1算法 算法(algorithm)是对特定问题求解步骤的一种描述,是指令的有限序列.其中,每个指令表示一个或多个操作.一个算法必须满足以下五个重

1.8小结 本章介绍了数据结构的研究对象.基本概念与术语.数据类型和抽象数据类型,以及算法.算法的设计原则.算法效率的衡量方法等.主要内容如下.(1)数据结构的研究对象数据结构是一门讨论"描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现"的学科.数据结构的内容包括3个"层次"的5个"要素",如表13所示.(2)基本概念与术语简单地说,数据就是计算机操作的对象的总称.数据元素是数据的基本单位,它是数据中的一个"

2.6小结 线性表是整个数据结构课程的重要基础,本章的主要内容如下.一个线性表是由n个数据元素构成的有限序列,其特点是数据元素之间存在着线性关系.在计算机中表示这种关系的两种不同的存储结构是顺序存储结构(顺序表)和链式存储结构(链表).1顺序表顺序表是在内存中用一组地址连续的存储单元依次存储线性表的数据元素,借助数组来实现.顺序表中数据元素之间的逻辑关系通过其"存储位置相邻"来表示.对于顺序表,主要有初始化.建立.销毁.插入.删除.按值查找等基本操作.插入和删除操作约需移动一半的元素

2.3线性表的链式表示与实现 线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻,因此可以随机存取表中任一元素,它的存储位置可用一个简单.直观的公式来表示.然而,从另一方面来看,这个特点也造成了这种存储结构的弱点:在作插入或删除操作时,需移动大量元素.本节我们将讨论线性表的另一种表示方法--链式存储结构,其特点是用一组地址任意的存储单元存储线性表中的数据元素.由于它不要求逻辑上相邻的元素在物理位置上也相邻,因此它没有顺序存储结构所具有的弱点,但同时也失去了顺序表随机存取的特点

3.3栈与递归实现 3.3.1递归的定义 栈还有一个重要应用是在程序设计语言中实现递归.一个直接调用自己或通过一系列的调用语句间接调用自己的函数,称为递归函数.其中直接调用自己的函数称为直接递归.间接调用自己的函数称为间接递归. 递归是算法设计中最重要的手段.它通常把一个大型的复杂问题转化为一个与原问题相似的规模较小的问题来求解.下面是常见的使用递归的三种情况. (1)定义是递归的 现实中,有许多定义是递归定义的,以n!为例来说明,其定义如下: fact(n)=1n=0//递归终止条件 n*fa