作者：李廷元 付茂洺 何元清
出版社：中国铁道出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
计算机软件技术基础试读：
前言
PREFACE
本书按照教育部高等学校大学计算机课程教学指导委员会提出的“三个层次五门课”系列课程体系设置的第二层次的一门基础理论课的课程大纲编写而成。通过本书的学习，学生会对计算机软件设计所需的基本知识和技巧有一个全面的认识，为软件设计开发工作打下坚实的基础。
学习本书需要学习一门计算机编程语言作为先导课程，推荐C语言。针对非计算机专业的理工科学生，着重介绍了数据结构、计算机操作系统、软件工程和数据库技术等方面的基础理论知识。一方面涵盖尽可能多的专业知识以提高学生对计算机软件开发的专业素养，一方面增加与全国计算机考级考试二级考试的契合度，做到技能提高和考证通过两不耽误。内容力求由浅入深，通俗易懂，简明扼要，注重实用技术。
本书共4章，第1章数据结构，主要讲述算法与数据结构的基本概念及常用的典型数据结构与算法，包括链表、队列、栈、数组等线性数据结构，二叉树、哈夫曼树等树形数据结构和简单的图形数据结构。在算法方面，结合数据结构讲述了查找与排序算法。第2章计算机操作系统，主要介绍操作系统的几大管理功能：处理器管理、存储管理、作业管理、设备管理与文件管理。第3章软件工程，介绍软件工程的概念、常用开发模型以及新型软件工程技术。第4章数据库技术，主要介绍数据库的基本概念与技术，包括数据库的基础知识、数据库的数据模型、结构化查询语言、数据库设计以及新型数据库技术。
本书内容简明清晰、重点突出、实例丰富、图文并茂，并结合每章内容给出了习题，以达到通过练习巩固每章所学知识的目的。
洺本书由李廷元、付茂、何元清任主编，高大鹏、戴蓉、张欢任副主编。其中，李廷元、高大鹏、涂磊编写了第1洺章，付茂、张欢编写了第2章，戴蓉编写了第3章，何元清、张欢编写了第4章，刘晓东、王欣、张选芳主审。
本书在编写和出版过程中得到了许多老师的热情支持和帮助，在此对他们一并表示诚挚的谢意！
由于编者水平有限，加之时间仓促，书中难免存在疏漏和不足之处，恳请同行和读者不吝赐教。
编者2017年2月第1章数据结构
从第一台电子计算机诞生到现在的70多年中，计算机的应用领域从单纯的科学计算扩展到情报检索、信息管理、工业生产、数据库应用等方面，处理对象也从原来的数值计算发展到对非数值数据的处理，而非数值数据不仅数据量大，而且类型繁多复杂，因此需要首先考虑这些数据量大且关系复杂的数据如何组织的问题，这正是数据结构的研究内容。
本章首先介绍数据结构的基本概念，然后重点介绍了数据结构中的线性结构和非线性结构，最后介绍了数据的查找和排序。1.1数据结构的基本概念
计算机软件离不开程序设计，而程序设计的两大基础是算法和数据结构，“程序=算法+数据结构”的概念已经广为人知。计算机软件加工处理的对象是数据，而数据具有一定的组织结构，因此数据结构就是研究数据的逻辑结构、存储结构及其运算的一门科学。1.1.1 数据结构的研究内容及其重要性
数据结构是组织和访问数据的系统方法。自从1946年第一台计算机ENIAC问世以来，计算机已经在各个领域得到了广泛的应用。用计算机处理问题，首先需要把客观对象抽象为某种形式的数据，然后设计对这些数据进行处理的算法，由计算机执行设计好的算法，最后获得问题的处理结果。著名计算机科学家Niklaus Wirth在其经典著作《数据结构+算法=程序》中，认为程序其实就是数据在特定的表示方式和结构的基础上对抽象算法的具体描述，说明了数据结构的重要性。
在计算机应用的早期，计算机主要应用于科学计算，要解决的问题侧重于数值计算，处理的对象相对较为简单，如对整数、实数进行算术运算、逻辑运算等，此时用一些变量或数组等足以表示要解决的问题。但随着计算机从早期的数值计算扩展到非数值计算领域，如管理信息系统、受控热核聚变、人工智能模拟、工业过程实时控制、卫星遥感遥测及气象等领域，数据的处理对象日益复杂和多样化，处理的数据呈海量式增长，有关数据结构的研究内容已经成为编译系统、操作系统、数据库管理系统及其他系统程序和一些应用系统的重要基础。
1968年，美国唐纳德·克努特（Donald E. Knuth）教授出版了其名著《计算机程序设计艺术》第一卷《基本算法》，首次系统地阐述了数据结构的主要内容，即数据的逻辑结构、存储结构以及对数据进行操作的各种算法。到20世纪70年代中期和80年代初，各种有关数据结构的著作大量问世，我国于20世纪70年代末开始设置数据结构的相关课程，现在数据结构不仅是计算机科学与技术专业的核心课程，同时也是很多计算机应用相关专业的一门重要的选修课或必修课，因此掌握数据结构的知识对于我们进一步进行高效率的计算机程序开发非常重要。1.1.2 数据结构的基本概念和术语
①数据（Data）：是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中、能被计算机程序识别和处理的符号的集合。数据又可分为数值性数据和非数值性数据两大类。数值性数据如整数、实数、复数等，一般用于工程和科学计算等；非数值性数据如字符、字符串、文字、图形、语音等。
②数据元素（Data Element）：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
③数据项（Data Item）：是具有独立含义的最小标识单位。有时，一个数据元素可由若干数据项组成。如整数集合中，10就可以称为是一个数据元素。又如在一个关系型数据库中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。
④数据对象（Data Object）：数据的子集。数据对象是具有相同性质的数据成员（数据元素）的集合。如整数数据对象N={0，1，2，…}，英文字母数据对象LETTER={'A'，'B'，…，Z'}。
⑤数据类型（Data Type）：是一个值的集合以及在这些值上定义的一组操作的总称。
⑥结构（Structure）：数据元素相互之间的关系称为结构，有以下4种类型的基本结构。
● 集合结构：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。
● 线性结构：结构中的数据元素之间存在一对一的关系。
● 树状结构：结构中的数据元素之间存在一对多的关系。
● 图状结构或网状结构：结构中的数据元素之间存在多对多的关系。
以上4种类型的基本结构如图1-1所示。
图1-1 4种类型的基本结构
⑦数据结构（Data Structure）：相互之间存在一种或多种特定关系的数据元素的集合。
数据结构的定义虽然没有统一的标准，但是它包括以下3方面的内容：逻辑结构、存储结构和对数据的操作。为了增加对数据结构的认识，举一个实例，如表1-1所示。
表1-1是一个班级学生的成绩表（也称成绩数据库），同时，它也构成一个数据结构。它由很多记录（数据元素）组成，每个元素又由多个数据列（字段、数据项）组成。那么这张表的逻辑结构是怎么样的呢？我们分析数据结构都是从结点（其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但指的是同一个东西）之间的关系来分析的，对于这个表中的任意一个记录（结点），它只有一个直接前驱和一个直接后继（前驱、后继就是前相邻、后相继的意思），整个表只有一个开始结点和一个终端结点。所有这些就构成了这个表的逻辑结构，亦即逻辑结构就是数据元素之间的逻辑关系。
表1-1 学生成绩表
数据的逻辑结构通常分两大类：线性结构和非线性结构。
①线性结构：其特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点最多只有一个直接前驱和一个直接后继。线性表就是一个典型的线性结构。
②非线性结构：其逻辑特征是该结构中一个数据元素可能有多个直接前驱和直接后继。非线性结构中最普遍的是图结构。
数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后间关系的信息。数据的存储结构有时也称为数据的物理结构，它是逻辑结构在计算机存储器中的物理实现。
表1-1中的数据元素在计算机中可以采取不同的存储方式：①将数据元素连续存放在一片内存单元中；②将数据元素随机地存放在不同的内存单元中，再用指针将这些数据元素链接在一起。这两种存储方式就形成两种不同的存储结构。
常用的数据存储结构有以下4种基本形式：
1）顺序存储
该方法把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元中，数据元素间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构（Sequential Storage Structure），通常借助程序语言的数组来实现。顺序存储方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。
2）链式存储
该方法不要求逻辑上相邻的数据元素在物理位置上也相邻，数据元素间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（Linked Storage Structure），通常借助于程序语言的指针类型来实现。
3）索引存储
该方法通常在存储数据元素信息的同时，还建立附加的索引表。索引表由若干索引项组成。若每个数据元素在索引表中都有一个索引项，则该索引表称为稠密索引（Dense Index）。若一组数据元素在索引表中只对应一个索引项，则该索引表称为稀疏索引（Spare Index）。索引项的一般形式是“（关键字，地址）”。关键字是能唯一标识一个数据元素的数据项。稠密索引中索引项的地址表示数据元素所在的存储位置；稀疏索引中索引项的地址表示一组数据元素的起始存储位置。
4）散列存储
该方法的基本思想是：根据数据元素的关键字直接计算该数据元素的存储地址。
以上4种基本存储方法既可单独使用，也可组合起来对数据结构进行存储。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时间和空间要求。
除了逻辑结构和物理结构外，数据结构的第三个内容是对数据的操作（运算），如一张表格，如何进行查找、增加、修改、删除记录等操作？这也就是数据的运算，它不仅仅是指加减乘除算术运算，在数据结构中，这些运算常常涉及算法问题。
算法（Algorithm）是对特定问题求解步骤的一种描述，由有限的指令序列组成，可完成某项特定的任务。为了保证正确地处理数据，学习数据结构必然要学习算法。要理解数据结构本身，重要的是理解实现数据结构操作的算法。算法和数据结构是相辅相成、缺一不可的两个方面。数据结构是算法处理的对象，也是设计算法的基础。一个具体问题的数据在计算机中往往可以采用多种不同的数据结构来表示；一个计算过程的实现又常常有多种可用的算法。因此，选择什么样的算法和数据结构就成为实现程序过程中最重要的一个课题。（1）算法的5个重要特性
①有穷性：一个算法必须在执行有穷步之后结束。
②确定性：算法的每一个步骤，必须是确切地定义的。
③输入：一个算法有零个或多个输入。
④输出：一个算法有一个或多个输出。
⑤可行性：算法中执行的任何计算步都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。
有的书把算法的特性中的输入/输出特性又称为“有足够的情报”，是指有足够条件的“输入”能让算法得到结果，这个情报也包括了结果。（2）算法的两种基本要素
算法由数据对象的运算和操作、算法的控制结构两种基本要素组成。
①算法中对数据的运算和操作：算法实际上是按解题要求，从环境中能进行的所有操作中选择合适的操作所组成的一组指令序列。即算法是由计算机能够处理的操作所组成的指令序列。
②算法的控制结构：在算法中，操作的执行顺序又称算法的控制结构，一般的算法控制结构有3种：顺序结构、选择结构和循环结构。（3）算法设计的基本方法
①列举法：基本思想是，根据提出的问题，列举出所有可能的情况，并用问题中给定的条件检验哪些是满足条件的，哪些是不满足条件的。
②归纳法：基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。
③递推：是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果。本质也是一种归纳，递推关系式通常是归纳的结果。
④递归：在解决一些复杂问题时，为了降低问题的复杂程序，通常是将问题逐层分解，最后归结为一些最简单的问题。分为直接递归和间接递归两种方法。
⑤减半递推技术：减半递推即将问题的规模减半，然后，重复相同的递推操作。
⑥回溯法：是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。（4）算法分析
在使用算法对特定的问题进行求解时，往往涉及对算法的分析。算法分析（Algorithm Analysis）是指对算法的执行时间和所需内存空间的估算。同一问题的求解往往可以使用不同的算法。通过算法分析可以比较两个算法的效率高低。
①算法的时间复杂度：执行一个算法所花费的时间代价。当要解决的问题的规模以某种单位由1增至n时，对应算法所耗费的时间也以某种单位由f（1）增至f（n）。此时称该算法的时间复杂度为f（n）。
②算法的空间复杂度：执行一个算法所需占用的空间代价。当要解决的问题的规模以某种单位由1增至n时，对应算法所需占用的空间也以某种单位由g（1）增至g（n）。此时称该算法的空间复杂度为g（n）。
③问题的规模：指的是算法要解决的问题所要处理的数据量的大小。例如，对n个记录进行排序，n就是问题的规模。再例如，求n阶矩阵的转置矩阵，n也可以看作是问题的规模。时间单位一般规定为一个简单语句（如赋值语句、条件判断语句等）所用的时间。空间单位一般规定为一个简单变量（如整型、字符型、浮点型等）所占用的存储空间大小。
要全面地分析一个算法，应考虑该算法在最坏情况下的代价、最好情况下的代价、平均情况下的代价。然而，要全面准确地分析每一个算法是相当困难的，一般考虑这个算法在最坏情况下的代价。在多数情况下，只要得到一个估计值就足够了。
在描述算法分析的结果时，通常采用O表示法：即某个算法的时间代价（或空间代价）为O（f（n）），如果存在正常数c和n ，当问0题的规模n≥n 时，该算法的时间代价（或空间代价）为T（n）≤c·0f（n），这时也称该算法的时间（或空间）代价的增长率为f（n）。这种说法意味着，当n充分大时，该算法的复杂度不大于f（n）的一个常数倍。
采用O表示法简化了时间复杂度和空间复杂度的度量，其基本思想是关注复杂性的数量级，而忽略数量级的系数，这样在分析算法的复杂度时，可以忽略零星变量的存储空间和个别语句的执行时间，重点分析算法的主要代价。
常见的时间复杂度按数量级递增排列依次为常数阶O（1）、对数阶O（log n）、线性阶O（n）、线性对数阶O（n log n）、平方22阶O（n 2 ）、立方阶O（n 3 ）、k次方阶O（n k ）、指数阶O（2 n ）。
理解了逻辑结构、存储结构以及对数据的操作3个问题，即可理解数据结构的概念。
在不引起混淆的情况下，通常将数据的逻辑结构简称为数据结构，但要清楚的是，数据结构研究的不仅仅是数据的逻辑结构，还包含对数据的存储结构以及数据的操作的研究。1.1.3 数据结构、数据类型和抽象数据类型
数据结构用来反映一个数据的内部构成，即一个数据由哪些数据元素构成，以什么方式构成，呈什么结构。数据结构包括逻辑上的数据结构和物理上的数据结构。逻辑上的数据结构反映数据元素之间的逻辑关系，物理上的数据结构反映数据元素在计算机内的存储方式。数据结构是数据存在的形式。
数据按照数据结构分类，具有相同数据结构的数据属同一类。同一类数据的全体称为一个数据类型。在高级程序设计语言中，数据类型用来说明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。为了解题的需要，根据数据结构的种类，高级语言定义了一系列的数据类型。不同的高级语言所定义的数据类型不完全相同，例如，C++语言所定义的数据类型如图1-2所示。
图1-2 C++的数据类型
其中，基本数据类型对应于简单的数据结构，非基本数据类型对应于复杂的数据结构。在复杂的数据结构中，允许数据元素本身具有复杂的数据结构，因而，非基本数据类型允许复合嵌套。指针类型对应于数据结构中数据元素之间的关系，表面上属基本数据类型，实际上都指向复杂的数据元素即构造数据类型中的数据，因此这里没有把它划入基本数据类型中，而是把它划入非基本数据类型中。
数据结构反映数据内部的构成方式，常常用一个结构图来描述：数据中的每一项，数据元素被看作一个结点，并用方框或圆圈表示，数据元素之间的关系用带箭头的连线表示。如果数据元素本身又有它自身的结构，则结构出现嵌套。这里的嵌套还允许是递归的嵌套。
指针数据的引入使构造各种复杂的数据结构成为可能。
按照数据结构中的数据元素之间的关系，数据结构有线性与非线性之分。在非线性数据结构中又有层次与网状之分。由于数据类型是按照数据结构划分的，因此一类数据结构对应一种数据类型。数据类型按照该类型中的数据所呈现的结构也有线性与非线性之分和层次与网状之分。一个数据变量在高级语言中的类型说明必须是该变量所具有的数据结构所对应的数据类型。
抽象数据类型（Abstract Data Type，ADT）是带有一些操作的数据元素的集合，是一种描述用户和数据间接口的抽象模型，ADT的主要功能是简单而明确地描述数据结构的操作。此处的“抽象”意味着应该从与实现方法无关的角度去研究数据结构。抽象数据类型为用户提供了一种定义数据类型的手段，其关键的两个要素为数据的结构以及在该结构上相应的操作的集合。
引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的应用隔开，使它们相互独立。对于抽象数据类型的描述，除了必须描述它的数据结构外，还必须描述定义在它上面的运算（过程或函数）。抽象数据类型上定义的过程和函数以该抽象数据类型的数据所应具有的数据结构为基础。
下面的各节将讨论一些基本抽象数据类型。所谓基本，只是相对而言，这些数据类型是最基本、最简单的，并且是实现其他抽象数据类型的基础。
在后面的内容中我们将了解到表、栈、队列、串、树、图等常见的基本抽象数据类型的ADT操作以及这些操作用不同数据描述方法的具体实现。1.2线性结构
线性结构是数据结构中最简单且最常用的一种数据结构。线性结构的基本特点是数据元素有序并且是有限的。
线性结构包括以下几种常见的数据类型：线性表、栈、队列、数组、串等。1.2.1 线性表
线性表（Linear List）是n（n≥0）个相同类型的元素a ，a ，01a ，a ，…，a 所构成的有限线性序列，通常表示为（a ，a ，23n01a ，a ，…，a ），其中，n为线性表的长度。a （0≤i≤n）是线性23ni表中第i个序号的数据元素。a 是抽象表示符号，在不同的情况下含i义不同。例如，一个整数序列（7，8，9，10，11，12，34）是一个线性表，表中每一个元素a 均为整数，表长为7。i
以上每个数据元素包括一个数据项，而1.1.2节中的学生成绩表数据，对于每一位学生student1、student2、student3…每个数据元素均包括多个数据项。
1.线性表的概念
简单地说，线性表就是n个数据元素的有限序列。线性表具有如下特点：存在唯一的被称为“第一个”的数据元素；存在唯一的被称为“最后一个”的数据元素；除第一个数据元素之外，线性表中的每个数据元素均只有一个前驱；除最后一个数据元素之外，线性表中的每个数据元素均只有一个后继。
在线性表中，一个元素可以由若干数据项组成，在这种情况下的数据元素称为记录，而含有大量记录的线性表又称为文件。线性表中元素的个数n定义为线性表的长度，n≥0。
同一个线性表中的元素必定具有相同特性，即属于同一数据对象，相邻数据元素之间存在序偶关系，即数据元素是“一个接一个地排列在一起”：（a ，…，a ，a ，a ，…，a ）1i-1ii+1n
其中，a 为a 的直接前驱，a 为a 的直接后继，a 是第i个i-1ii+1ii元素，称i为数据元素a 在线性表中的位序。i
线性表是相当灵活的一种数据结构，如长度可根据需要增减，元素也可以增删。
线性表的基本操作有以下几种：
①Initiate（L）{初始化}：设定一个空的线性表。
②Length（L）{求表长}：对给定的线性表L，函数返回值为其数据元素的个数。
③Get（L，i）{取元素}：若给定的数据元素序号i满足1≤i≤Length（L），则函数返回值为给定线性表L的第i个元素a ，否则返回i空元素。
④Locate（L，x）{定位}：对给定值，若线性表L中存在某个数据元素a 等于x，则函数返回索引号最小的i的值；若L中不存在等于x的i数据元素，则函数返回一个特殊值（比如-1），以说明不存在的位置。
⑤Insert（L，i，x）{插入}：对给定的线性表L，若索引号i满足1≤i≤Length（L）+1，则在线性表的第i个位置上插入一个新的数据元素x，使原来表长度为n的线性表变为表长为n+1的线性表，并使函数返回值为true，否则函数返回值为false。
⑥Delete（L，i）{删除}：对给定的线性表，若索引号i满足1≤i≤Length（L），则把线性表中第i个元素a 删除，使原来表长为n的线性i表变成表长为n-1的线性表，并使函数返回值为true，否则函数返回值为false。
对于线性表的其他有关操作，如线性表的合并、排序等操作，都可以通过以上基本操作来实现。
2.线性表的抽象数据类型的定义
上述是线性表抽象数据类型的定义，其中只是一些基本操作，也可以更复杂，如将两个线性表合并等。
3.线性表的顺序存储结构及其实现——顺序表
线性表的存储结构有多种类型，如顺序存储结构和链式存储结构，因此线性表可以采用使用顺序存储结构的顺序表和有序顺序表来实现，也可以采用链式存储结构的单链表、双链表和循环链表等来实现。（1）顺序表的定义
①顺序存储结构：即把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元中的方法。
②顺序表（Sequential List）：用顺序存储结构实现的线性表简称顺序表。按数据元素的值无序或有序存放，顺序表又可分为无序顺序表和有序顺序表两种。（2）数据元素的存储地址
设线性表中所有数据元素的类型相同，则每个数据元素所占用的存储空间大小也相同。当把线性表的数据元素存入存储空间后，称这样的一种存储空间为一个“结点”。假设表中每个结点占用c个存储单元，并设表中第一个结点a 的存储地址（简称基地址）是Loc（a 1 ），那么结点a 的存储地址Loc（a ）可通过下式计算：1ii
Loc（a ）=Loc（a ）+（i-1）×c （1≤i≤n）i1
在顺序表中，每个结点a 的存储地址是该结点在表中的位置i的i线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址，因此顺序表是一种随机存取存储的结构。（3）顺序表类型定义
①除了用数组这种顺序存储的类型存储线性表的元素外，顺序表还应该用一个变量来表示线性表的长度属性，因此用结构体类型来定义顺序表类型。
②存放线性表结点的数组空间的大小ListSize应仔细选值，使其既能满足表结点的数目动态增加的需求，又不至于浪费存储空间。
③由于C语言中数组的下标从0开始，所以若L是SeqList类型的顺序表，则线性表的开始结点a 和终端结点a 分别存储在L.data[0]和1nL.Data[L.length-1]中。
④若L是SeqList类型的指针变量，则a 和a 分别存储在L-1n>data[0]和L->data[L->length-1]中。（4）顺序表的特点
顺序表是用顺序存储结构实现的线性表，具有以下优点：
①存储方式简单：几乎所有的程序设计语言都支持数组，因此用一维数组表示顺序表是最简单的实现方式。数组的下标可以看作数据元素的相对地址，因此在顺序表中逻辑上相邻的数据元素，其物理位置也相邻。
②顺序表便于随机访问，访问效率高。顺序表第i个元素的地址可表示为：
Loc（a ）=Loc（a ）+（i-1）×c （1≤i≤n）i1
因此，只要知道顺序表的首地址和每个数据元素所占存储单元的大小即可求出第i个数据元素的地址。
但顺序表也具有一些缺点：
①扩充不方便：顺序表一般采用数组实现，而定义数组时必须指明大小，该大小一旦确定，在程序运行过程中一般不允许修改，因此对于表中数据元素个数需要增加的情况，存储空间不易扩充。
②插入和删除操作不方便：由于顺序表一般采用数组实现，因此在顺序表中插入或删除某个数据元素时，需要移动数组中的元素，从而占用较大的存储空间和较多的运行时间，致使插入和删除效率低。（5）顺序表上实现的基本运算
①表的初始化：
②求表长：
③取表中第i个结点：
④插入：
a.插入运算的逻辑描述：线性表的插入运算是指在表的第i（1≤i≤n+1）个位置上，插入一个新结点x，使长度为n的线性表：（a ，…，a ，a ，…，a ）1i-1in
变成长度为n+1的线性表：（a ，…，a ，x，a ，…，a ）1i-1in
由于向量空间大小在声明时已确定，当L-＞length≥ListSize时，表空间已满，不可再进行插入操作；当插入位置i的值为i＞n或i＜1时为非法位置，不可进行正常插入操作。
b.顺序表插入操作过程：在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n，n-1，…，i上的结点，依次后移到n+1，n，…，i+1位置上，空出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，不需要移动结点，直接将x插入表的末尾。
c.具体算法描述如下：
d.算法分析：
● 问题的规模：表的长度L->length（设值为n）是问题的规模。
● 移动结点的次数由表长n和插入位置i决定。
● 算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1。当i=n+1时，移动结点次数为0，即算法在最好情况下时间复杂度是O（1）；当i=1时，移动结点次数为n，即算法在最坏情况下时间复杂度是O（n）。
4.线性表的链式存储结构及其实现——链表（1）链式存储结构
由于顺序表存在占用连续存储空间且不易动态扩充以及插入和删除操作效率低的缺点，对于数据元素个数动态变化，需要频繁插入和删除操作的应用场合，必须考虑其他存储结构，例如链式存储结构。采用链式存储结构的线性表简称链表（Linked List）。链表的具体存储结构表示为：
①用一组任意存储单元存放线性表的数据元素（这组存储单元既可以是连续的，也可以是不连续的）。
②采用链式存储结构的线性表中，数据元素的逻辑次序和物理次序不一定相同。为了能正确表示数据元素间的逻辑关系，在存储每个数据元素（a ）值（Data）的同时，还必须存储指示其后继数据元i素（a ）的地址（或位置）信息，称为指针（Pointer）或链i+1（Link），这两部分组成一个结构体，称为一个“结点”，其结构如图1-3所示。
图1-3 单链表的结点结构
链式存储结构是最常用的存储方式之一，不仅可用来表示线性表，还可用来表示各种非线性的数据结构（如树、图等），其存储结构灵活多样，包括单链表、循环链表和双链表等，其特点是对线性表进行插入和删除运算时不需要移动数据元素，且允许表长任意扩充。（2）单链表的结点结构
采用链式存储结构的线性表，每一个数据元素占一个结点（Node）。一个结点由两个域组成，一个域存放数据元素data，称为数据域，其数据类型由应用问题决定；另一个域存放一个指向该链表中下一个结点的指针next，称为指针域，它给出了下一个结点的开始存储地址。
图1-3中data域为存放结点值的数据域，next域为存放结点的直接后继的地址（位置）的指针域（链域）。链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起，每个结点只有一个链域的链表称为单链表。【例1-1】 一个线性表（a ，a ，a ，…，a ）的单链表结012n-1构如图1-4所示，其中，first为指向单链表中第一个结点的指针，last为指向单链表中最后一个结点的指针。
图1-4 单链表的结构（3）头指针head和终端结点指针域的表示
单链表中每个结点的存储地址是存放在其前驱结点的next域中的，而开始结点（a ）无前驱，为了让开始结点也具有前驱，可以0另设一个结点，该结点的data域不存放值，其next域指向开始结点（a ），这个结点称为“头结点”，再设一个头指针head指向头结0点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。头指针名是head的链表可称为表head。终端结点无后继，故终端结点的指针域为空，即NULL，或者简记为∧，如图1-5所示。
图1-5 带头结点的单链表（4）单链表类型描述
由于单链表中所有结点的存储结构都相同，当需要向线性表中新增加一个数据元素时，只需要申请一个结点的存储空间，向该结点的data域存入数据元素的值，再把该结点插入链表中即可。单链表的结点类型描述如下：
5.单链表的运算（1）建立单链表
假设线性表中结点的数据类型是字符，逐个输入这些字符型的结点，并以换行符'\n'为输入条件结束标志符。动态地建立单链表的常用方法有如下两种：
①头插法建立单链表。
算法思路：从一个空表开始，重复读入数据，生成新结点，将读入的数据存放在新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。该方法生成的链表的结点次序与输入顺序相反。具体算法实现如下：
②尾插法建立单链表。
算法思路：从一个空表开始，重复读入数据，生成新结点，将读入数据存放在新结点的数据域中，然后将新结点插入到当前链表的表尾，直到读入结束标志为止。尾插法建立链表时，头指针固定不动，故必须设立一个搜索指针，向链表右边延伸，则整个算法中应设立三个链表指针，即头指针head、搜索指针r、申请单元指针s。尾插法最先得到的是头结点，生成的链表的结点次序与输入顺序相同。具体算法实现如下：（2）单链表的插入运算
在单链表中插入一个结点时，仅需要修改指针而不需要移动元素，如此能高效地实现插入操作。例如，要在单链表（a ，a ，a 01 ，…，a ）的数据a 结点之前插入一个新元素x，插入操作如图2n-1i1-6所示。
图1-6 插入操作
要在带头结点的单链表head中第i个数据元素之前插入数据元素x，首先需要在单链表中寻找到第i-1个结点并用指针p指示，然后申请一个由指针s指示的结点空间，并置x为其数据域值，最后修改第i-1个结点的指针指向x结点，并使x结点的指针指向第i个结点，其插入过程如图1-7所示。
图1-7 在单链表中插入结点示意图
单链表插入算法如下：
若单链表中有n个结点，插入位置i允许的取值范围为1≤i≤n+1。当i=n+l时，即为在链尾插入一个结点，算法中用条件（p！=NULL&&j 如果希望删除链表中第i个结点，应当先让第i-1个结点的指针域指向第i+1个结点，通过重新拉链，把第i个结点从链表中分离出来，然后再删去，如图1-8所示（注意：图中×表示该指针关系不再存在。）。 图1-8 删除结点 要在带头结点的单链表head中删除第i个结点，首先计数寻找第i个结点并使指针p指向其前驱第i-1个结点，再删除第i个结点并释放被删除的结点空间，其操作过程如图1-9所示。 图1-9 在单链表中删除结点示意图 单链表删除算法如下： 与插入算法不同的是，删除算法中用条件（p->next ！=NULL&&j 插入算法和删除算法的时间复杂度均为O（n）。这是因为链式存储结构不是随机存储结构，即不能直接读取单链表中的某个结点，而是从单链表的头结点开始一个一个地计数寻找。因此，虽然在单链表中插入或删除结点时不需要移动别的数据元素，但算法中寻找单链表的第i-1个或第i个结点的时间复杂度为O（n）。 6.循环链表 循环链表（Circular Linked List）是另一种形式的链式存储结构，是单链表的一种特殊情况，即单链表中最后一个结点的next指针不为空（NULL），而是指向了表的前端，即循环链表是一种首尾相接的链表。（1）循环链表 ①单循环链表：是另一种形式的表示线性聚集的链表，其结点结构与单链表相同，不同的是，单循环链表中表尾结点的指针域NULL改为指向表头结点或开始结点即可，如图1-10所示。 ②多重链的循环链表：将表中结点链在多个环上。 图1-10 单循环链表（2）带头结点的单循环链表 循环链表与单链表一样，可以有表头结点，这样能够简化链表操作的实现，统一空表与非空表的运算，如图1-11所示。 注意： 判断空链表的条件是head==head->next。 图1-11 带表头结点的循环链表（3）仅设尾指针的单循环链表 用尾指针last表示的单循环链表对开始结点a 和终端结点a 的0n-1查找时间都是O（1），而表的操作常常是在表的首尾位置上进行。因此，实际情况是多采用尾指针表示单循环链表。带尾指针的单循环链表如图1-12所示。 图1-12 带尾指针的单循环链表 注意： 判断空链表的条件为last==last->next。（4）循环链表的特点 循环链表的特点是无须增加存储量，循环链表的运算与单链表类似，但在涉及链头与链尾处理时稍有不同。在循环链表中检查指针current是否达到链表的链尾时，不是判断current→next==NULL，而是判断current→next==first。 例如，在实现循环链表的插入运算时，如果是在表的最前端插入，则必须改变链尾最后一个结点的指针域的值，这就需要沿链表搜索到最后一个结点。如果给出的存储指针不放在链头而放在链尾，实现插入和删除运算就会更方便，如图1-13所示。 图1-13 插入操作【例1-2】 在链表上实现将两个线性表（a ，a ，…，a ）和01n-1（b ，b ，…，b ）连接成一个线性表（a ，…，a ，b ，…，01m-10n-10b ）的运算。m-1 分析：若在单链表或头指针表示的单循环表上进行此连接操作，都需要遍历第一个链表，找到结点a ，然后将结点b 链到a 的后n1n面，其执行时间是O（n）。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O（1）。相应的算法如下： 注意： 循环链表中没有NULL指针。 涉及遍历操作时，其终止条件不再像非循环链表那样需判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。在单链表中，从一个已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其他结点。而在单循环链表中，从任意一个结点出发都可以访问到表中所有的结点，这一优点使某些运算在单循环链表上易于实现。 7.双链表 单链表要搜索一个指定结点的前驱结点十分不易，因为结点中只有一个指示直接后继的指针域，由此从某个结点出发只能顺指针往后查其他结点。若要寻找结点的直接前驱，则需从表头指针出发。如果在一个应用问题中，经常要求指针向前驱和后继方向移动，为保证移动的时间复杂度达到最小，就必须采用双向链表表示。双向链表中每个结点的结构如图1-14所示。 图1-14 双链表的结点结构 其中： ①在双向链表的每个结点中应有两个链接指针作为它的数据成员，prior指示它的前驱结点，next指示它的后继结点。 ②双向链表的每个结点至少有3个域。双向链表是指在前驱和后继方向都能游历（遍历）的线性链表。 双向链表通常采用带表头结点的循环链表形式。（1）双向链表的结点结构 双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还要增加一个指向其直接前驱的指针域prior，如图1-15所示。
试读结束[说明：试读内容隐藏了图片]