《数据结构与算法 C语言版》—— 第2章 线性表

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

2.2线性表的顺序表示与实现 2.2.1线性表的顺序表示 线性表的顺序存储是指在内存中用一组地址连续的存储单元依次存储线性表的数据元素,用这种存储方式存储的线性表称为顺序表.顺序表中数据元素之间的逻辑关系通过其"存储位置相邻"来表示,如图21所示. 如果顺序表的数据元素是按照递增或递减顺序存放的,则称其为有序顺序表.假设线性表的每个数据元素需占用l个存储单元,其第一个元素的存储地址,即数组的基地址记为LOC(a1),则线性表中第i个数据元素的存储地址LOC(ai)为LOC(ai)=L

2.1线性表的定义 2.1.1线性表的概念 线性表是一种线性结构.简言之,一个线性表是由n个数据元素构成的有限序列.线性表中的数据元素可以是一个数或一个字符,也可以是由若干数据项组成的记录,甚至可以是更复杂的信息.也就是说,线性表中的数据元素可以是任意类型的,但必须是相同类型的.通常将n个数据元素构成的线性表记为:(a1,a2,-,ai-1,ai,ai+1,-,an).其中,n称为线性表的表长,当n=0时称为空表.线性表中的数据元素之间存在着顺序关系,其中ai-1是ai的前驱,ai是ai-1的后

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

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

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

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

3.7小结 本章介绍了两种特殊的线性表:栈和队列,主要内容如下. (1)栈 栈是限定仅在表尾(栈顶)进行插入(进栈)或删除(出栈)的线性表,又称后进先出的线性表.栈有两种存储表示:顺序表示(顺序栈)和链式表示(链栈). 栈的主要操作是进栈和出栈. 对于顺序栈的进栈和出栈要注意判断栈满或栈空,栈满和栈空的条件与栈顶指针的指向有关.本书中栈顶指针指向栈顶元素,栈满的条件是Stop>=Sstacksize-1,栈空的条件是Stop=-1.有的教材中栈顶指针指向栈顶的下一个元素时,栈满和栈空的条件

第3章 栈 与 队 列 栈和队列是在软件设计中常用的两种数据结构,它们的逻辑结构与线性表相同.其特点在于操作受到了限制:栈按"后进先出"的规则进行操作,队列按"先进先出"的规则进行操作.故称它们为操作受限制的线性表.