基本信息
编辑推荐
在计算机科学技术的各个领域，选择合适的数据结构都是一个重要问题。通过数据结构与算法的学习，读者能进一步提高软件设计与程序编写的能力.提高应用计算机技术解决宴际问题的能力。
《数据结构与算法》是根据《高等学校计算机科学与技术专业公共核心知识体系与课程》的指导思想编写而成的.涵盖了"数据结构"公共核心课程的知识单元。
《数据结构与算法》以基本数据结构和算法设计策略为知识单元.系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法书中分为数据结构和算法两大部分其中，数据结构部分（第1～4章）按数据元素之间存在的对应关系进行划分，分为表示一对一关系的线性表表示一对多关系的树以及表示多对多关系的图和广义表：算法部分（第5～7章）以查找和排序算法作为常用算法.所以该部分由算法设计策略、查找和排序组成。
内容简介
作译者
吴跃，四川省学术和技术带头人、国务院政府特殊津贴专家、教育部计算机科学与技术专业教学指导委员会委员、四川省教学名师、四川省高等学校省级教学团队计算机专业核心课程教学团队带头人。从事数据结构与算法课程的教学工作20余年，主持了国家863、教育部博士点基金、国防重点和省科技攻关等十余项科研项目，发表学术论文70余篇，获省部级科研奖5项、国家级教学成果奖2项，已编著出版《计算机操作系统》教材一部。
目录
出版者的话
序 言
前 言
教学建议
第1章 绪论1
1.1 计算机问题求解过程1
1.2 迷宫问题2
1.3 数据结构4
1.3.1 数据结构研究的内容4
1.3.2 数据结构概念6
1.4 算法10
1.4.1 算法概念及特性10
1.4.2 算法描述11
1.4.3 算法分析12
1.5 本章小结14
1.6 习题14
第2章 线性表16
2.1 线性表16
2.1.1 线性表的定义16
2.1.2 线性表的顺序存储20
序 言
前 言
教学建议
第1章 绪论1
1.1 计算机问题求解过程1
1.2 迷宫问题2
1.3 数据结构4
1.3.1 数据结构研究的内容4
1.3.2 数据结构概念6
1.4 算法10
1.4.1 算法概念及特性10
1.4.2 算法描述11
1.4.3 算法分析12
1.5 本章小结14
1.6 习题14
第2章 线性表16
2.1 线性表16
2.1.1 线性表的定义16
2.1.2 线性表的顺序存储20
前言
什么是数据结构？数据结构又有什么作用？什么是算法？算法又有哪些行之有效的基本策略？什么是程序设计的基础？程序设计的能力又可以从哪些方面去提高？这是计算机专业的学生在学习中经常感到困惑的问题，也是利用计算机解决具体应用问题的程序员需要明白的问题，还是计算机教育工作者应该深思的问题。弄清楚了这些基本问题，以及它们之间的相互关系，无论是对学生的学习、教师的施教还是程序员的应用，都具有重要的意义和极大的帮助。早在1976年，著名的计算机科学家、Pascal程序设计语言之父、结构化程序设计首创者、1984年图灵奖获得者沃斯(Niklaus Wirth)就提出了Algorithms + Data Structures = Programs（算法＋数据结构＝程序），在这个著名的公式中，“+”生动地表达了算法和数据结构的相互作用，是程序设计的精髓；“=”言简意赅地刻画了算法和数据结构是构成计算机程序的两个关键要素。我们认为，程序设计包括算法、数据结构和程序设计语言三部分。算法是求解问题的过程描述;数据结构是对所要求解问题中的数据的存储和算法策略实现的支持；程序设计语言是使用计算机求解问题，是在计算机上实现算法和数据结构。本书是根据《高等学校计算机科学与技术专业公共核心知识体系与课程》的指导思想编写而成的。本书共七章，分为数据结构和算法两大部分。其中，数据结构部分（第1～4章）按数据元素之间存在的对应关系进行划分，分为表示一对一关系的线性表、表示一对多关系的树以及表示多对多关系的图和广义表，可以以线性表作为基本数据结构，从多个方向和层面上进行拓广，引出线性表的各类变形，将栈、队列、串视为线性表的特例，将数组、广义表、树和图视为线性表的扩展，如图1所示；算法部分（第5～7章）以查找和排序算法作为常用算法，所以该部分由算法设计策略、查找和排序组成。图1数据结构关联图
各章具体内容如下：第1章绪论，由吴跃编写。该章通过迷宫问题给出了数据结构的两大用途：存放要处理的数据和实现算法策略。该章还定义了数据结构的概念和相关术语，给出了算法和算法分析的概念。第2章线性表，由尚明生编写。线性表表示数据元素之间一对一的关系。本章以线性表作为基本数据结构，从多个方向和层面进行拓广：引出线性表的各类变形，将栈、队列、串视为线性表的特例，将数组视为线性表在维数上的扩展。第3章树，由陈端兵编写。树表示数据元素之间一对多的关系。本章以二叉树的性质、存储结构和遍历算法为基础，逐步拓展到二叉树的各类变形、树和森林以及树的变形。最后举例说明了树的应用。第4章图和广义表，由李树全编写。图和广义表表示数据元素之间多对多的关系。本章分别介绍了图和广义表的概念、存储结构和遍历算法，并给出了图的经典应用。第5章算法设计策略，由李树全编写。本章分别介绍了直接法、分治法、贪心法、动态规划法、回溯法、分支限界法6大类算法的设计策略、思想、应用特点和步骤，并举例说明了这些算法策略的应用。第6章查找，由尚明生编写。在许多应用中都需要查找，可以将其视为一类基本而常用的算法，本章分别介绍了顺序表、索引表和散列表上的查找算法。第7章排序，由陈端兵编写。和查找一样，在许多应用中也都需要排序，可以将其视为一类基本而常用的算法，本章分别介绍了插入、交换、选择、归并和基数5大类排序算法。掌握了基本数据结构和算法策略，有助于选择和设计适合应用的数据结构，有助于设计更高效的算法，有助于提高编程能力。本书每章都有学习目标，还配有一定量的填空题、选择题、简答题和算法设计题，供读者练习。最后，让我们一起一页一页地翻开这本丰富多彩的书，像一只漫游在数据结构这棵大树上的小虫，去领略各类数据结构的功用和风采，去品味各种算法策略的精妙和乐趣，去夯实计算机专业的基础，去提高编程的能力，去收获学习的果实。编者2009年11月第1章绪论本章结合迷宫问题介绍利用计算机求解实际问题的过程，引入数据结构的基本概念和基本术语，讲解数据结构的发展、数据结构和算法的关系以及算法的描述方法，讲解算法复杂度的基本度量标准。通过本章的学习，让学生对数据结构有一个感性的认识，了解数据结构在解决实际问题中的应用，掌握数据结构的基本概念与表示，掌握算法的描述方法和算法时间复杂度的计算方法。第2章线性表本章开始介绍线性表的逻辑结构、基本操作方法和基本算法，讲解线性表的顺序存储结构及其基本操作方法和算法实现，讲解线性表的链式存储结构及其基本操作方法和算法实现，最后介绍线性表的几种典型应用。21节的重点是让学生在了解线性表的基本表示和操作的基础上，掌握线性表的应用编程。栈和队列是线性表的扩展，在实际程序设计中有重要的应用，22节和23节介绍栈的逻辑结构、表示和实现以及队列的逻辑结构及其链式和顺序存储结构，重点讲解栈和队列的几种实际应用编程，让学生了解数据结构在解决实际问题中的应用。数组也可以看作线性表的扩展。24节的重点是让学生了解数组的顺序存储结构，稀疏矩阵的压缩存储、三元组表表示及稀疏矩阵转置、加法及乘法的实现，数组的应用——迷宫问题的编程实现。第3章树本章介绍二叉树的基本概念及基本性质、二叉树的存储结构和二叉树的基本操作（包括二叉树的遍历及其应用、二叉树的线索化），应重点掌握二叉树的三种遍历方式及基本应用。在此基础上，了解二叉树的变形（包括二叉排序树以及二叉排序树的查找、插入、删除等操作，二叉平衡树及其基本调整方法），重点掌握二叉排序树的查找、插入和删除操作；了解树和森林的基本概念和存储结构、树和森林的基本操作；了解树的变形（主要包括四叉树、八叉树、B树以及23树），以及在这些树上的查找、插入、删除操作；了解树的基本应用（包括赫夫曼编码、算术表达式的求值、堆排序以及树在决策分析中的应用），重点掌握赫夫曼树及赫夫曼编码、堆排序的过程及算法实现。第4章图和广义表本章介绍图的基本概念，让学生了解图在现实中的一些应用。应掌握图的常用存储结构，包括邻接矩阵、邻接表、邻接多重表、十字链表这四种存储结构；掌握图的基本遍历算法；掌握图的生成树算法、拓扑排序、关键路径和最短路径算法；掌握广义表的基本概念与存储表示，了解广义表的基本运算。通过本章的学习，进一步提高数据结构的应用能力、算法设计能力和编程能力。第5章算法设计策略数据结构与算法设计技术是密切相关的，为设计好的算法，选择适当的数据结构是非常重要的。应了解算法分析的基本方法；掌握穷举法、递推法和迭代法这三种基本算法；重点掌握分治法、贪心法、回溯法这三种基本算法；对动态规划法、分支限界法作一般性的了解。通过本章的学习，增进程序设计的技巧，进一步提高分析问题和解决问题的能力。第6章查找本章介绍顺序表的基本概念和查找算法。应掌握顺序查找和二分查找，了解查找算法的性能分析方法；对索引表的顺序查找、二分查找作一般性的了解；掌握散列表的基本概念，掌握不同的散列函数构造方法和冲突处理方法。第7章排序在本章中，应掌握排序的基本概念和定义；掌握插入排序、交换排序、选择排序和归并排序算法及复杂度分析；了解基数排序算法及复杂度分析；掌握各种排序算法的性能比较，包括时间复杂度、空间复杂度和稳定性。本书的总学时数为56学时，线性表、树和算法设计策略这三章内容相对较多，教师可以根据实际学时数对讲解内容作适当的调整。本书各章最后都附有习题，教师可以根据情况，给学生留一些基本的和中等难度的习题作为课外作业。如有时间，也可以安排1至2次习题课。在习题课上可以由教师讲解以前课外作业中普遍存在的问题，也可以安排稍难一些的习题让学生在课上做出解答，然后由教师指导进行讨论，最后得出正确且较好的答案。数据结构与算法课程课内上机为8学时，可考虑将上机实验的内容放在线性表、树和图的应用这三个部分，其他上机内容可以让学生在课外完成。
各章具体内容如下：第1章绪论，由吴跃编写。该章通过迷宫问题给出了数据结构的两大用途：存放要处理的数据和实现算法策略。该章还定义了数据结构的概念和相关术语，给出了算法和算法分析的概念。第2章线性表，由尚明生编写。线性表表示数据元素之间一对一的关系。本章以线性表作为基本数据结构，从多个方向和层面进行拓广：引出线性表的各类变形，将栈、队列、串视为线性表的特例，将数组视为线性表在维数上的扩展。第3章树，由陈端兵编写。树表示数据元素之间一对多的关系。本章以二叉树的性质、存储结构和遍历算法为基础，逐步拓展到二叉树的各类变形、树和森林以及树的变形。最后举例说明了树的应用。第4章图和广义表，由李树全编写。图和广义表表示数据元素之间多对多的关系。本章分别介绍了图和广义表的概念、存储结构和遍历算法，并给出了图的经典应用。第5章算法设计策略，由李树全编写。本章分别介绍了直接法、分治法、贪心法、动态规划法、回溯法、分支限界法6大类算法的设计策略、思想、应用特点和步骤，并举例说明了这些算法策略的应用。第6章查找，由尚明生编写。在许多应用中都需要查找，可以将其视为一类基本而常用的算法，本章分别介绍了顺序表、索引表和散列表上的查找算法。第7章排序，由陈端兵编写。和查找一样，在许多应用中也都需要排序，可以将其视为一类基本而常用的算法，本章分别介绍了插入、交换、选择、归并和基数5大类排序算法。掌握了基本数据结构和算法策略，有助于选择和设计适合应用的数据结构，有助于设计更高效的算法，有助于提高编程能力。本书每章都有学习目标，还配有一定量的填空题、选择题、简答题和算法设计题，供读者练习。最后，让我们一起一页一页地翻开这本丰富多彩的书，像一只漫游在数据结构这棵大树上的小虫，去领略各类数据结构的功用和风采，去品味各种算法策略的精妙和乐趣，去夯实计算机专业的基础，去提高编程的能力，去收获学习的果实。编者2009年11月第1章绪论本章结合迷宫问题介绍利用计算机求解实际问题的过程，引入数据结构的基本概念和基本术语，讲解数据结构的发展、数据结构和算法的关系以及算法的描述方法，讲解算法复杂度的基本度量标准。通过本章的学习，让学生对数据结构有一个感性的认识，了解数据结构在解决实际问题中的应用，掌握数据结构的基本概念与表示，掌握算法的描述方法和算法时间复杂度的计算方法。第2章线性表本章开始介绍线性表的逻辑结构、基本操作方法和基本算法，讲解线性表的顺序存储结构及其基本操作方法和算法实现，讲解线性表的链式存储结构及其基本操作方法和算法实现，最后介绍线性表的几种典型应用。21节的重点是让学生在了解线性表的基本表示和操作的基础上，掌握线性表的应用编程。栈和队列是线性表的扩展，在实际程序设计中有重要的应用，22节和23节介绍栈的逻辑结构、表示和实现以及队列的逻辑结构及其链式和顺序存储结构，重点讲解栈和队列的几种实际应用编程，让学生了解数据结构在解决实际问题中的应用。数组也可以看作线性表的扩展。24节的重点是让学生了解数组的顺序存储结构，稀疏矩阵的压缩存储、三元组表表示及稀疏矩阵转置、加法及乘法的实现，数组的应用——迷宫问题的编程实现。第3章树本章介绍二叉树的基本概念及基本性质、二叉树的存储结构和二叉树的基本操作（包括二叉树的遍历及其应用、二叉树的线索化），应重点掌握二叉树的三种遍历方式及基本应用。在此基础上，了解二叉树的变形（包括二叉排序树以及二叉排序树的查找、插入、删除等操作，二叉平衡树及其基本调整方法），重点掌握二叉排序树的查找、插入和删除操作；了解树和森林的基本概念和存储结构、树和森林的基本操作；了解树的变形（主要包括四叉树、八叉树、B树以及23树），以及在这些树上的查找、插入、删除操作；了解树的基本应用（包括赫夫曼编码、算术表达式的求值、堆排序以及树在决策分析中的应用），重点掌握赫夫曼树及赫夫曼编码、堆排序的过程及算法实现。第4章图和广义表本章介绍图的基本概念，让学生了解图在现实中的一些应用。应掌握图的常用存储结构，包括邻接矩阵、邻接表、邻接多重表、十字链表这四种存储结构；掌握图的基本遍历算法；掌握图的生成树算法、拓扑排序、关键路径和最短路径算法；掌握广义表的基本概念与存储表示，了解广义表的基本运算。通过本章的学习，进一步提高数据结构的应用能力、算法设计能力和编程能力。第5章算法设计策略数据结构与算法设计技术是密切相关的，为设计好的算法，选择适当的数据结构是非常重要的。应了解算法分析的基本方法；掌握穷举法、递推法和迭代法这三种基本算法；重点掌握分治法、贪心法、回溯法这三种基本算法；对动态规划法、分支限界法作一般性的了解。通过本章的学习，增进程序设计的技巧，进一步提高分析问题和解决问题的能力。第6章查找本章介绍顺序表的基本概念和查找算法。应掌握顺序查找和二分查找，了解查找算法的性能分析方法；对索引表的顺序查找、二分查找作一般性的了解；掌握散列表的基本概念，掌握不同的散列函数构造方法和冲突处理方法。第7章排序在本章中，应掌握排序的基本概念和定义；掌握插入排序、交换排序、选择排序和归并排序算法及复杂度分析；了解基数排序算法及复杂度分析；掌握各种排序算法的性能比较，包括时间复杂度、空间复杂度和稳定性。本书的总学时数为56学时，线性表、树和算法设计策略这三章内容相对较多，教师可以根据实际学时数对讲解内容作适当的调整。本书各章最后都附有习题，教师可以根据情况，给学生留一些基本的和中等难度的习题作为课外作业。如有时间，也可以安排1至2次习题课。在习题课上可以由教师讲解以前课外作业中普遍存在的问题，也可以安排稍难一些的习题让学生在课上做出解答，然后由教师指导进行讨论，最后得出正确且较好的答案。数据结构与算法课程课内上机为8学时，可考虑将上机实验的内容放在线性表、树和图的应用这三个部分，其他上机内容可以让学生在课外完成。
序言
近20年里，计算机学科有了很大的发展，人们普遍认为，“计算机科学”这个名字已经难以涵盖该学科的内容，因此，改称其为计算学科（Computing Discipline）。在我国本科教育中，1996年以前曾经有计算机软件专业和计算机及应用专业，之后被合并为计算机科学与技术专业。2004年以来，教育部计算机科学与技术专业教学指导分委员会根据我国计算机专业教育和计算学科的现状，为更好地满足社会对计算机专业人才的需求，发布了《高等学校计算机科学与技术专业发展战略研究报告暨专业规范（试行）》（以下简称《规范》），提出在计算机科学与技术专业名称之下，构建计算机科学、计算机工程、软件工程和信息技术四大专业方向。《规范》中四大专业方向的分类，在于鼓励办学单位根据自己的情况设定不同的培养方案，以培养更具针对性和特色的计算机专业人才。
为配合《规范》的实施，落实中央“提高高等教育质量”的精神，我们规划了“面向计算机科学与技术专业规范系列教材”。本系列教材面向全新的计算学科，针对我国高等院校逐步向新的计算机科学与技术专业课程体系过渡的趋势编写，在知识选择、内容组织和教学方法等方面满足《规范》的要求，并与国际接轨。本套教材具有以下几个特点：
（1） 体现《规范》的基本思想，满足其课程要求。为使教材符合我国高等院校的教学实际，编委会根据《规范》的要求规划本套教材，广泛征集在国内知名高校中从事一线教学和科研工作、经验丰富的优秀教师承担编写任务。
（2） 围绕“提高教育质量”的宗旨开发教材。为了确保“精品”，本系列教材的出版不走盲目扩大的路子，每本教材的选题都将由编委会集体论证，并由一名编委担任责任编委，最大程度地保证这套教材的编写水准和出版质量。
（3） 教材内容的组织科学、合理，体系得当。本套教材的编写注重研究学科的新发展和新成果，能够根据不同类型人才培养需求，合理地进行内容取舍、组织和叙述，还精心设计了配套的实验体系和练习体系。
（4） 教材风格鲜明。本套教材按4个专业方向统一规划，分批组织，陆续出版。教材的编写体现了现代教育理念，探讨先进的教学方法。
（5） 开展教材立体化建设。根据需要配合主教材的建设适时开发实验教材、教师参考书、学生参考书、电子参考资料等教辅资源，为教学实现多方位服务。
我们衷心希望本系列教材能够为我国高等院校计算机科学与技术等专业的教学作出贡献，欢迎广大读者广为选用。
为配合《规范》的实施，落实中央“提高高等教育质量”的精神，我们规划了“面向计算机科学与技术专业规范系列教材”。本系列教材面向全新的计算学科，针对我国高等院校逐步向新的计算机科学与技术专业课程体系过渡的趋势编写，在知识选择、内容组织和教学方法等方面满足《规范》的要求，并与国际接轨。本套教材具有以下几个特点：
（1） 体现《规范》的基本思想，满足其课程要求。为使教材符合我国高等院校的教学实际，编委会根据《规范》的要求规划本套教材，广泛征集在国内知名高校中从事一线教学和科研工作、经验丰富的优秀教师承担编写任务。
（2） 围绕“提高教育质量”的宗旨开发教材。为了确保“精品”，本系列教材的出版不走盲目扩大的路子，每本教材的选题都将由编委会集体论证，并由一名编委担任责任编委，最大程度地保证这套教材的编写水准和出版质量。
（3） 教材内容的组织科学、合理，体系得当。本套教材的编写注重研究学科的新发展和新成果，能够根据不同类型人才培养需求，合理地进行内容取舍、组织和叙述，还精心设计了配套的实验体系和练习体系。
（4） 教材风格鲜明。本套教材按4个专业方向统一规划，分批组织，陆续出版。教材的编写体现了现代教育理念，探讨先进的教学方法。
（5） 开展教材立体化建设。根据需要配合主教材的建设适时开发实验教材、教师参考书、学生参考书、电子参考资料等教辅资源，为教学实现多方位服务。
我们衷心希望本系列教材能够为我国高等院校计算机科学与技术等专业的教学作出贡献，欢迎广大读者广为选用。
媒体评论
“数据结构”是计算机科学技术专业的一门基础理论课程，是计算机学科的核心课程之一。在计算机科学技术的各个领域，选择合适的数据结构都是一个重要问题。通过数据结构与算法的学习，读者能进一步提高软件设计与程序编写的能力，提高应用计算机技术解决实际问题的能力。
本书是根据《高等学校计算机科学与技术专业公共核心知识体系与课程》的指导思想编写而成的，涵盖了《数据结构》公共核心课程的知识单元。
本书以基本数据结构和算法设计策略为知识单元，系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法。书中分为数据结构和算法两大部分。其中，数据结构部分（第1~4章）按数据元素之间存在的对应关系进行划分，分为表示一对一关系的线性表、表示一对多关系的树以及表示多对多关系的图和广义表；算法部分（第5~7章）以查找和排序算法作为常用算法，所以该部分由算法设计策略、查找和排序算法组成。
本书为教师配有电子教案和习题答案，可登录华章网站（www.hzbook.com)下载。
本书是根据《高等学校计算机科学与技术专业公共核心知识体系与课程》的指导思想编写而成的，涵盖了《数据结构》公共核心课程的知识单元。
本书以基本数据结构和算法设计策略为知识单元，系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法。书中分为数据结构和算法两大部分。其中，数据结构部分（第1~4章）按数据元素之间存在的对应关系进行划分，分为表示一对一关系的线性表、表示一对多关系的树以及表示多对多关系的图和广义表；算法部分（第5~7章）以查找和排序算法作为常用算法，所以该部分由算法设计策略、查找和排序算法组成。
本书为教师配有电子教案和习题答案，可登录华章网站（www.hzbook.com)下载。
书摘
性表的存储方式除了常用的顺序存储外，链式存储也是一种常见的方式。本小节将介绍一般线性表的几种链式存储实现方式，如单链表、带头结点的单链表、循环链表等。
线性表的链式存储是指用一组任意的存储单元（可以连续也可以不连续）存储线性表中 的数据元素。数据元素在存储空间表示时通常称为结点。
前面讨论的顺序表用物理位置上的相邻关系来表示结点之间的逻辑关系，这使得可以随机存取表中任一指定位置的数据元素，但同时导致插入和删除运算进行大量的数据元素移动。采用线性表的链式存储结构能解决这个问题，基于它的插入和删除运算不需要移动数据元素，从而使得时间复杂度从顺序表的0（2）变为0（1）。
在链式存储结构中，为了反映数据元素之间的逻辑关系，每个结点不仅要存放数据元素本身，还需要一些额外的存储空间来存放和它有关系的数据元素的地址，即需要存放指向其他元素的指针（或链）。称指向第一个结点的指针为头指针，一个链表由头指针唯一确定。一旦知道头指针，就可以沿着指针访问其他数据元素。
可以根据不同的标准对链表进行分类。例如，根据结点中指针数量的多少，可以将链表分为单链表、双向链表和多重链表；根据是否在链表的第一个元素前附加额外的结点，可以将链表分为带头结点的链表和不带头结点的链表；根据头指针是指向第一个结点还是最后一个结点，可以将链表分为带头指针的链表和带尾指针的链表等等。
在链式存储结构中，由于线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致，因此在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式称为顺序存取方式。因此，链式存储结构失去了随机存取数据元素的功能，但换来了操作的方便性：进行插入和删除时无需移动数据元素。
……
线性表的链式存储是指用一组任意的存储单元（可以连续也可以不连续）存储线性表中 的数据元素。数据元素在存储空间表示时通常称为结点。
前面讨论的顺序表用物理位置上的相邻关系来表示结点之间的逻辑关系，这使得可以随机存取表中任一指定位置的数据元素，但同时导致插入和删除运算进行大量的数据元素移动。采用线性表的链式存储结构能解决这个问题，基于它的插入和删除运算不需要移动数据元素，从而使得时间复杂度从顺序表的0（2）变为0（1）。
在链式存储结构中，为了反映数据元素之间的逻辑关系，每个结点不仅要存放数据元素本身，还需要一些额外的存储空间来存放和它有关系的数据元素的地址，即需要存放指向其他元素的指针（或链）。称指向第一个结点的指针为头指针，一个链表由头指针唯一确定。一旦知道头指针，就可以沿着指针访问其他数据元素。
可以根据不同的标准对链表进行分类。例如，根据结点中指针数量的多少，可以将链表分为单链表、双向链表和多重链表；根据是否在链表的第一个元素前附加额外的结点，可以将链表分为带头结点的链表和不带头结点的链表；根据头指针是指向第一个结点还是最后一个结点，可以将链表分为带头指针的链表和带尾指针的链表等等。
在链式存储结构中，由于线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致，因此在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式称为顺序存取方式。因此，链式存储结构失去了随机存取数据元素的功能，但换来了操作的方便性：进行插入和删除时无需移动数据元素。
……
