详情
本书共分10章，采用C++语言编写，但不使用类，保证学习C语言的人也能看懂。第1章讲解基础知识，介绍数据结构基础和算法复杂性计算方法。第2～5章介绍线性结构；第6章介绍树形结构；第7章介绍图形结构；第8～9章介绍数据结构基本应用；第10章介绍数据结构高级应用。各章包含大量图解，结合实例讲解数据结构的基本操作，力求通俗易懂。
书名：趣学数据结构
ISBN：978-7-115-51383-0
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 陈小玉
责任编辑 张 爽
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
本书从趣味故事引入算法复杂性计算及数据结构基础内容，涵盖线性结构、树形结构和图形结构，包括链表、栈和队列、树和图的应用等。本书内容还涉及数据结构的基本应用（包括各种查找、排序等）和高级应用（包括优先队列、并查集、B-树、B+树和红黑树等）。通过大量图解将抽象数据模型简单通俗化，语言表述浅显易懂，并结合有趣的实例帮助读者轻松掌握数据结构。
本书可作为程序员的学习用书，也适合没有太多编程经验但又对数据结构有强烈兴趣的初学者使用，同时也可作为高等院校计算机、数学及相关专业的师生用书，或学科竞赛的辅导用书和培训学校的教材。
2017年8月，本着让更多的人轻松学习算法的初心，我写作了第一本书《趣学算法》，该书在出版后受到广大读者一致好评，在一年内重印了10次，并输出了繁体版的版权。一位读者对我说，读这本书读到“停不下来”，我又何尝不是呢？写书写到“停不下来”，这是作者和读者的巨大共鸣！在交流学习算法的同时，越来越多的学生反映数据结构晦涩难懂，问我能不能写一本《趣学数据结构》。说实在的，写书是一项极其繁重的工作，每一句话，每一个图，都需要精心琢磨。正在我犹豫不决之际，一件事情坚定了我写作本书的信心。
如果你关注计算机专业招聘试题，会发现越是大型公司，问的问题越基础，有的甚至问你什么是栈和队列，反而一些小公司会关心你做过什么系统。从关注点的不同可以看出，大公司更注重基础扎实和发展潜力，而小公司希望你立刻能够为其干活。可以这样比喻：小公司喜欢细而长的竹子，大公司更喜欢碗口粗的竹笋。
我曾经推荐一个学生到某知名公司，没多久，学生向我说了应聘的事情：“我介绍我开发了企业管理系统、在线商城系统等，没想到他问我使用了什么数据结构和算法，我懂很多技术，那么多功能我都实现了，他不问，却问我使用了什么数据结构和算法，你说搞笑不？数据结构和算法我早就忘了，我会开发软件还不行吗？”人力资源总监也反馈过来意见：“很搞笑，这个学生做了不少系统，却说根本没用到数据结构和算法。”
既然双方都觉得这是一件搞笑的事情，那么我们就摊开来看，数据结构到底是什么。
当我们遇到一个实际问题时，首先需要解决两件事：
（1）如何将数据存储在计算机中；
（2）用什么方法和策略解决问题。
前者是数据结构，后者是算法。只有数据结构没有算法，相当于只把数据存储到计算机中，而没有有效的方法去处理，就像一幢只有框架的烂尾楼；若只有算法，没有数据结构，就像沙漠里的海市蜃楼，只不过是空中楼阁罢了。
数据是一切能输入计算机中的信息的总和，结构是指数据之间的关系。数据结构就是将数据及其之间的关系有效地存储在计算机中并进行基本操作。算法是对特定问题求解步骤的一种描述，通俗讲就是解决问题的方法和策略。
在遇到一个实际问题时，要充分利用自己所学的数据结构，将数据及其之间的关系有效地存储在计算机中，然后选择合适的算法策略，并用程序高效地实现。这就是Niklaus Wirth教授所说的：“数据结构+算法＝程序”。
高校的计算机专业为本科生都开设了数据结构课程，它是计算机学科知识结构的核心和技术体系的基石，在研究生考试中也是必考科目。随着科学技术的飞速发展，数据结构的基础性地位不仅没有动摇，反而因近年来算法工程师的高薪形势，而得到了业内空前的重视。很多人认为基本的数据结构及操作已经在高级语言（如C++、Java语言）中封装，栈、队列、排序、优先队列等都可以直接调用库函数，学会怎么调用就好了，为什么要重复“造轮子”？那么到底有没有必要好好学习数据结构呢？
先看学习数据结构有什么用处。
（1）学习有效存储数据的方法。很多学生在学习数据结构时，问我要不要把单链表插入、删除背下来？要不合上书就不会写了。我非常诧异，为什么要背？理工科技术知识很少需要记忆的，是用的，用的！学习知识不能只靠死记硬背，更重要的是学习处理问题的方法。如何有效地存储数据，不同的数据结构产生什么样的算法复杂性，有没有更好的存储方法提高算法的效率？
（2）处理具有复杂关系的数据。现实中很多具有复杂关系的数据无法通过简单的库函数调用实现。如同现在很多芯片高度集成，完全不需要知道芯片内部如何，直接使用就行了。但是，如果在现实中遇到一个复杂问题，现有的芯片根本无法解决，或者一个芯片只能完成其中一个功能，而我们需要的是完成该复杂问题的一个集成芯片，这时就需要运用所学的数据结构知识来高效处理具有复杂关系的数据。
（3）提高算法效率。很多问题的基础数据结构运行效率较低，需要借助高级数据结构或通过改进数据结构来提高算法效率。
通过学习数据结构，更加准确和深刻地理解不同数据结构之间的共性和联系，学会选择和改进数据结构，高效地设计并实现各种算法，这才是数据结构的精髓。
网络上太多的同学吐槽被“虐”，如“滔滔江水连绵不绝”，数据结构太难了！真的很难吗？其实数据结构只是讲了3部分内容：线性结构、树和图。到底难在哪里呢？我通过调查，了解到数据结构难学大概有以下4个原因。
（1）无法接受它的描述方式。数据结构的描述大多是抽象的形式，我们习惯了使用自然语言表达，难以接受数据结构的抽象表达。不止一个学生问我，书上的“ElemType”到底是什么类型？运行时怎么经常提示错误。它的意思就是“元素类型”，只是这样来描述，你需要什么类型就写什么类型，例如int。这样的表达方式会让不少人感到崩溃。
（2）不知道它有什么用处。尽管很多人学习数据结构，但目的各不相同。有的人是应付考试，有的人是参加算法竞赛需要，而很多人不太清楚学习数据结构有什么用处，迷迷糊糊看书、做题、考试。
（3）体会不到其中的妙处。由于教材、教师等各种因素影响，很多学生没有体会到数据结构处理数据的妙处，经常为学不会而焦头烂额，学习重在体会其中的乐趣，有乐趣才有兴趣，兴趣是最好的驱动力。
（4）语言基础不好。我一直强调先看图解，理清思路，再上机。可还是有很多同学已经理解了思路后，因为缺少main函数，输入/输出格式不对，缺少括号等各种语言问题卡壳，而这一切都被戴上了“数据结构太难了”的大帽子。
在讲学习秘籍之前，我们首先了解一下数据结构学习的3种境界。
（1）会数据结构的基本操作。学会各种数据结构的基本操作，即取值、查找、插入、删除等，是最基础的要求。先看图解，理解各种数据结构的定义，操作方法，然后看代码，尝试自己动手上机运行，逐渐掌握基本操作。在初学时，要想理解数据结构，一定要学会画图。通过画图形象表达，能更好地体会其中的数据结构关系。因此，初学阶段学习利器是：画图、理解、画图。
（2）会利用数据结构解决实际问题。在掌握了书中的基本操作之后，就可以尝试利用数据结构解决一些实际问题了。先学经典应用问题的解决方法，体会数据结构的使用方法，再做题，独立设计数据结构解决问题。要想熟练应用就必须做大量的题，在做题的过程中体会其中的方法。最好进行专项练习，比如线性表问题、二叉树问题、图问题。这一阶段的学习利器是：做题、反思、做题。
（3）熟练使用和改进数据结构，优化算法。这是最高境界了，也是学习数据结构的精髓所在，单独学习数据结构是无法达到这种境界的。数据结构与算法相辅相成，需要在学习算法的过程中慢慢修炼。在学习算法的同时，逐步熟练应用、改进数据结构，慢慢体会不同数据结构和算法策略的算法复杂性，最终学会利用数据结构改进和优化算法。这一阶段已经在数据结构之上，可以通过在ACM测试系统上刷各种算法题，体会数据结构在算法设计中的应用。这一阶段的学习利器是：刷题、总结、刷题。
本书具有五大特色。
（1）完美图解，通俗易懂。学习数据结构最好的办法就是画图、画图、画图。本书中的每一个基本操作和演示都有图解，有了图解，一切就都变得简单，迎刃而解。
（2）实例丰富，简单有趣。本书结合大量实例，讲述如何利用数据结构解决实际问题，使复杂难懂的问题变得简单有趣，给读者带来巨大的阅读乐趣，使读者在阅读中不知不觉地学会数据结构知识，体会数据结构的妙处。
（3）深入浅出，透析本质。本书采用简洁易懂的代码描述，抓住本质，通俗描述及注释使代码更加易懂。本书不仅对数据结构设计和操作描述全面细致，而且有复杂性分析过程。
（4）实战演练，循序渐进。本书在每一个数据结构讲解清楚后，进行实战演练，使读者在实战中体会数据结构的设计和操作，增强自信，从而提高了读者独立思考、自己动手实践的能力。丰富的练习题和思考题及时检验对所学知识的掌握情况，为读者从小问题出发，逐步解决大型复杂性问题奠定基础。
（5）网络资源，技术支持。本书为读者提供本书所有范例程序的源代码、练习题以及答案解析，这些源代码可以自由修改编译，以符合自己的需要。本书提供源代码执行、调试说明书，提供博客、QQ群技术支持，为读者答疑解惑。
本书包括10章。
本书的每一章中都有大量图解，并给出数据结构的基本操作，最后结合实例帮助读者巩固相关知识点，力求学以致用、举一反三。
写一本书是一项极其琐碎、繁重的工作，尽管我已经竭力使本书和网络支持接近完美，但仍然可能存在很多漏洞和瑕疵。欢迎读者提供关于本书的反馈意见，因为对本书的意见和建议有利于我们改进和提高，以帮助更多的读者。如果对本书有什么意见和建议，或者有问题需要帮助，可以加入QQ群887694770，也可以致信rainchxy@126.com，我将不胜感激。
感谢我的家人和朋友在本书编写过程中提供的大力支持。感谢人民邮电出版社的张爽编辑认真负责促成本书的早日出版，感谢提供宝贵意见的同事们，感谢提供技术支持的同学们。感恩遇到这么多良师益友！
本书由异步社区出品，社区（https://www.epubit.com/）为您提供相关资源和后续服务。
本书提供范例程序源代码，请在异步社区本书页面中点击
，跳转到下载界面，按提示进行操作即可。注意：为保证购书读者的权益，该操作会给出相关提示，要求输入提取码进行验证。
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎您将发现的问题反馈给我们，帮助我们提升图书的质量。
当您发现错误时，请登录异步社区，按书名搜索，进入本书页面，点击“提交勘误”，输入勘误信息，点击“提交”按钮即可。本书的作者和编辑会对您提交的勘误进行审核，确认并接受后，您将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
我们的联系邮箱是contact@epubit.com.cn。
如果您对本书有任何疑问或建议，请您发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果您有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区在线提交投稿（直接访问www.epubit.com/selfpublish/submission即可）。
如果您是学校、培训机构或企业，想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果您在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请您将怀疑有侵权行为的链接发邮件给我们。您的这一举动是对作者权益的保护，也是我们持续为您提供有价值的内容的动力之源。
“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT技术图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT技术图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。
“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社近30年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、AI、测试、前端、网络技术等。
异步社区
微信服务号
1.1 数据结构基础知识
1.2 算法复杂度
1.3 一棋盘麦子
1.4 神奇魔鬼序列
1.5 本章要点
著名的瑞士科学家Niklaus Wirth教授提出：数据结构+算法＝程序。数据结构是程序的骨架，算法是程序的灵魂。
学习数据结构首先从认识以下几个概念开始。
数据是指所有能输入到计算机中的描述客观事物的符号，包括文本、声音、图像、符号等。我们经常使用的“扫一扫”的二维码，也是数据。
数据元素是数据的基本单位，也称节点或记录，如图1-1所示。
图1-1 数据元素
数据项表示有独立含义的数据最小单位，也称域。若干个数据项构成一个数据元素，数据项是不可分割的最小单位，如图1-1所示的“86”。
数据对象是指相同特性的数据元素的集合，是数据的一个子集。
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
数据结构是带“结构”的数据元素的集合，“结构”是指数据元素之间存在的关系。数据结构研究的问题是将带有关系的数据存储在计算机中，并进行相关操作。数据结构包含逻辑结构、存储结构和运算三个要素。
逻辑结构是数据元素之间的关系，存储结构是数据元素及其关系在计算机中的存储方式。例如，小明和小勇是表兄弟，这是他们之间的逻辑关系；他们在教室里面的位置是他们的存储结构。无论他们的座位怎样安排，是挨着坐，还是分开坐，都不影响他们的表兄弟关系。
逻辑结构：数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题中抽象出来的数学模型。
数据结构的逻辑结构共有以下4种。
（1）集合——数据元素间除“同属于一个集合”外，无其他关系。
集合中的元素是离散、无序的，就像鸡圈中的小鸡一样，可以随意走动，它们之间没有什么关系，唯一的亲密关系就是在同一个鸡圈里，如图1-2所示。数据结构重点研究的是数据之间的关系，而集合中的元素是离散的，没有什么关系。因此，集合虽然是一种数据结构，但在数据结构书中不讲，在离散数学的集合论部分有重点讲述。
图1-2 集合
（2）线性结构——一个对一个，如线性表、栈、队列、数组、广义表。
线性结构就像穿珠子，是一条线，不会分叉，如图1-3所示。有唯一的开始和唯一的结束，除了第一个元素外，每个元素都有唯一的直接前驱（前面那个）；除了最后一个元素外，每个元素都有唯一的直接后继（后面那个）。
图1-3 线性结构
（3）树形结构——一个对多个，如树。
树形结构就像一棵倒立的树，树根可以发出多个分支，每个每支也可以继续发出分支，树枝和树枝之间是不相交的，如图1-4所示。
图1-4 树形结构
（4）图形结构——多个对多个，如图、网。
图形结构就像我们经常见到的地图，任何一个节点都可能和其他节点有关系，就像一张错综复杂的网，如图1-5所示。
图1-5 图形结构
存储结构：数据元素及其关系在计算机中的存储方式。
存储结构可以分为4种：顺序存储、链式存储、散列存储和索引存储。很多数据结构类书籍只介绍了前两种基本的存储结构，这里加上后两种，以便读者了解。
（1）顺序存储
顺序存储是指逻辑上相邻的元素在计算机内的存储位置也是相邻的。例如，张小明是哥哥，张小波是弟弟，他们的逻辑关系是兄弟，如果他们住的房子是前后院，也是相邻的，就可以说他们是顺序存储，如图1-6所示。
图1-6 兄弟两家前后相邻
顺序存储采用一段连续的存储空间，将逻辑上相邻的元素存储在连续的空间内，中间不允许有空。顺序存储可以快速定位第几个元素的地址，但是插入和删除时需要移动大量元素，如图1-7所示。
图1-7 顺序存储
（2）链式存储
链式存储是指逻辑上相邻的元素在计算机内的存储位置不一定是相邻的。例如，哥哥张小明因为工作调动去了北京，弟弟仍然在郑州，他们的位置是不相邻的，但是哥哥有弟弟家的地址，很容易可以找到弟弟，就可以说他们是链式存储，如图1-8所示。
图1-8 哥哥有弟弟家地址
链式存储就像一个铁链子，一环扣一环才能连在一起。每个节点除了数据域，还有一个指针域，记录下一个元素的存储地址，如图1-9所示。
图1-9 链式存储
（3）散列存储
散列存储，又称哈希（Hash）存储，由节点的关键码值决定节点的存储地址。用散列函数确定数据元素的存储位置与关键码之间的对应关系，如图1-10所示。
图1-10 散列存储
例如，假设散列表的地址范围为0～9，散列函数为H(key)=key%10。输入关键码序列：（24,10,32,17,41,15,49），构造散列表，如图1-11所示。
24%10=4：存储在下标为4的位置。
10%10=0：存储在下标为0的位置。
32%10=2：存储在下标为2的位置。
17%10=7：存储在下标为7的位置。
41%10=1：存储在下标为1的位置。
15%10=5：存储在下标为5的位置。
49%10=9：存储在下标为9的位置。
图1-11 散列表
散列存储可以通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。如果有冲突，则有多种处理冲突的方法。
（4）索引存储
索引存储是指除建立存储节点信息外，还建立附加的索引表来标识节点的地址。索引表由若干索引项组成。如果每个节点在索引表中都有一个索引项，则该索引表称为稠密索引。若一组节点在索引表中只对应于一个索引项，则该索引表称为稀疏索引。索引项的一般形式是关键字、地址，如图1-12所示。
图1-12 索引存储
在搜索引擎中，需要按某些关键字的值来查找记录，为此可以按关键字建立索引，这种索引称为倒排索引。为什么称为倒排索引呢？因为正常情况下，都是由记录来确定属性值的，而这里是根据属性值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。带有倒排索引的文件称为倒排索引文件，又称为倒排文件。倒排文件可以实现快速检索，索引存储是目前搜索引擎最常用的存储方法，如图1-13所示。
图1-13 倒排索引
抽象数据类型（Abstract Data Type，ADT）是将数据对象、数据对象之间的关系和数据对象的基本操作封装在一起的一种表达方式，它和工程中的应用是一致的。在工程项目中，开始编程之前，首先列出程序需要完成的功能任务，先不用管具体怎么实现，实现细节在项目后期完成，一开始只是抽象出有哪些基本操作。把这些操作项封装为抽象数据类型，等待后面具体实现这些操作。而其他对象如果想调用这些操作，只需要按照规定好的参数接口调用，并不需要知道具体是怎么实现的，从而实现了数据封装和信息隐藏。在C++中可以用类的声明表示抽象数据类型，用类的实现来实现抽象数据类型的具体操作。
抽象数据类型可以用以下的三元组来表示。
ADT抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
} ADT抽象数据类型名
例如，线性表的抽象数据类型的定义：
ADT List{
数据对象：D={ai|ai∈Elemset, i=1,2,…,n,n
0}
数据关系：R={<ai−1,ai>|ai−1,ai∈D, i=2,…,n}
基本操作：
InitList(&L)
操作结果：构造一个空的线性表L
DestroyList(&L)
初始条件：线性表已存在
操作结果：销毁线性表L
ClearList(&L)
初始条件：线性表已存在
操作结果：置线性表L为空表
ListEmpty(L)
初始条件：线性表已存在
操作结果：若线性表L为空表，则返回TRUE，否则返回FALSE
ListLenght(L)
初始条件：线性表已存在
操作结果：返回线性表L数据元素个数
GetElem(L, i, &e)
初始条件：线性表已存在（1
iListLenght(L)）
操作结果：用e返回线性表L中第i个数据元素的值
locatElem(L, e, comare())
初始条件：线性表已存在，comare()是数据元素判定函数
操作结果：返回线性表L中第1个与e满足关系comare()的数据元素的位序
PriorElem(L, cur_e, &pre_e)
初始条件：线性表已存在
操作结果：若cur_e是线性表L的数据元素，且不是第一个，则用pre_e返回它
的前驱，否则操作失败，pre_e无定义
NextElem(L, cur_e, &next_e)
初始条件：线性表已存在
操作结果：若cur_e是线性表L的数据元素，且不是第最后一个，则用next_e返
回它的后继，否则操作失败，next_e无定义
ListInsert(&L, i, e)
初始条件：线性表已存在（1iListLenght(L)+1）
操作结果：在线性表L中第i个数据元素之前插入新元素e，L长度加1
ListDelete(&L, i, &e)
初始条件：线性表已存在（1iListLenght(L)）
操作结果：删除线性表L中第i个数据元素，用e返回其值，L长度减1
ListTraverse(L, visit())
初始条件：线性表已存在
操作结果：依次对线性表L的每个数据元素调用visit()函数，一旦visit()失败，
则操作失败
}ADT List
（1）为什么要使用抽象数据类型？
抽象数据类型的主要作用是数据封装和信息隐藏，让实现与使用相分离。数据及其相关操作的结合称为数据封装。对象可以对其他对象隐藏某些操作细节，从而使这些操作不会受到其他对象的影响，这就是信息隐藏。抽象数据类型独立于运算的具体实现，使用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据，实现了信息隐藏。
（2）为什么很多书中没有使用抽象数据类型？
既然抽象数据类型符合工程化需要，可以实现数据封装和信息隐藏，为什么很多数据结构书中的程序并没有使用抽象数据类型呢？因为很多人觉得数据结构难以理解，学习起来非常吃力，因此仅仅将数据结构的基本操作作为重点，把每一个基本操作讲解清楚，使读者学会和掌握数据结构的基本操作，便完成了数据结构书的基本任务。在实际工程中，需要根据实际情况融会贯通，灵活运用，这是后续话题。目前要掌握的就是各种数据结构的基本操作，本书也将基本操作作为重点讲述，并结合实例讲解数据结构的应用。
数据结构和算法相辅相成，密不可分，在学习数据结构之前，首先要了解什么是算法、好算法的衡量标准，以及算法复杂度的计算方法。
首先看一道某跨国公司的招聘试题。
写一个算法，求下面序列之和：
−1，1，−1，1，…，(−1)n
当你看到这个题目，你会怎么想？使用for语句或while循环？
先看算法1-1。
//算法1-1
sum=0;
for(i=1;i<=n;i++)
sum=sum+pow(-1,n); //即(-1)^n这段代码可以实现求和运算，但是为什么不这样算呢？
再看算法1-2。
//算法1-2
if(n%2==0) //判断n是不是偶数，%表示求余数
sum=0;
else
sum=-1;有的读者看到算法1-2后恍然大悟，原来可以这样啊！这不就是高斯那种将两个数结合成对的算法吗？
一共50对数，每对之和均为101，那么总和为：
(1+100) × 50＝5050
1787年，小高斯10岁，用了几分钟的时间算出了结果，而其他孩子却要算很长时间。
可以看出，算法1-1需要运行n次加法，如果n=10 000，就要运行10 000次，而算法1-2只需要运行1次！是不是有很大差别？
问：高斯的方法我也知道，但遇到类似的题还是……我用的笨办法也是算法吗？
答：是算法。
算法是指对特定问题求解步骤的一种描述。
算法只是对问题求解方法的一种描述，它不依赖于任何一种语言，可以用自然语言、C、C++、Java、Python等描述，也可以用流程图、框图来表示。为了更清楚地说明算法的本质，我们一般去除了计算机语言的语法规则和细节，采用“伪代码”来描述算法。“伪代码”介于自然语言和程序设计语言之间，它更符合人们的表达方式，容易理解，但不是严格的程序设计语言，如果要上机调试，则需要转换成标准的计算机程序设计语言才能运行。
算法具有以下特性。
（1）有穷性：算法是由若干条指令组成的有穷序列，总是在执行若干次后结束，不可能永不停止。
（2）确定性：每条语句有确定的含义，无歧义。
（3）可行性：算法在当前环境条件下可以通过有限次运算实现。
（4）输入和输出：有零个或多个输入，一个或多个输出。
问：嗯，第二种方法的确算得挺快的，但我写了一个算法，怎么知道它好不好？
“好”算法的标准如下。
（1）正确性：指算法能够满足具体问题的需求，程序运行正常，无语法错误，并能够通过典型的软件测试，达到预期需求规格。
（2）易读性：算法遵循标识符命名规则，简洁、易懂，注释语句恰当、适量，方便自己和他人阅读，并便于后期调试和修改。
（3）健壮性：算法对非法数据及操作有较好的反应和处理。例如，在学生信息管理系统中，登记学生年龄时，21岁误输入为210岁，系统应该提示出错。
（4）高效性：指算法运行效率高，即算法运行所消耗的时间短。算法时间复杂度就是算法运行需要的时间。现代计算机一秒能计算数亿次，因此不能用秒来具体计算算法消耗的时间。由于相同配置的计算机进行一次基本运算的时间是一定的，我们可以用算法基本运算的执行次数来衡量算法的效率。因此将算法基本运算的执行次数作为时间复杂度的度量标准。
（5）低存储性：指算法所需要的存储空间低。尤其是像手机、平板电脑这样的嵌入式设备，算法如果占用空间过大，则无法运行。算法占用的空间大小称为空间复杂度。
除了前3条基本标准外，我们对好的算法的评判标准就是高效性、低存储性。
问：前3条都好办，但时间复杂度怎么算呢？
时间复杂度：算法运行需要的时间，一般将算法基本运算的执行次数作为时间复杂度的度量标准。
看算法1-3，并分析这一算法的时间复杂度。
//算法1-3
sum=0; //运行1次
total=0; //运行1次
for(i=1;i<=n;i++) //运行n+1次，最后依次判断条件不成立，结束
{
sum=sum+i; //运行n次
for(j=1;j<=n;j++) //运行n*(n+1)次
total=total+i*j; //运行n*n次
}把算法所有语句的运行次数加起来，即1+1+n+1+n+n×(n+1)+n×n，可以用一个函数T(n)表达：
T(n)=2n2+3n+3
当n足够大时，如n=105时，T(n)=2×1010+3×105+3，我们可以看到算法运行时间主要取决于第一项，后面的基本可以忽略不计。
如果用极限来表示，则为：
，c为不等于0的常数
如果用时间复杂度渐进上界表示，如图1-14所示。
图1-14 时间复杂度渐进上界
从图1-15可以看出，当nn0时，T(n)cf (n)，当n足够大时，T(n)和f (n)近似相等，因此我们用О(f (n))来表示时间复杂度渐近上界，通常用这种表示法衡量算法时间复杂度。算法1-3的时间复杂度渐进上界为О(f (n))＝О(n2)，如果用极限来表示，则为：
还有渐近下界符号Ω(T(n)cf (n))，如图1-15所示。
图1-15 时间复杂度渐进下界
从图1-16中可以看出，当nn0时，T(n)cf (n)，当n足够大时，T(n)和f (n)近似相等，因此用Ω(f (n))来表示时间复杂度渐近下界。
渐近精确界符号Θ(c1f (n)T(n)c2f (n))，如图1-16所示。
图1-16 时间复杂度渐进精确界
从图1-3中可以看出，当nn0时，c1f (n)T(n)c2f (n)，当n足够大时，T(n)和f (n)近似相等，这种两边逼近的方式，更加精确近似，时间复杂度渐近精确界用Θ(f (n))来表示。
我们通常使用时间复杂度渐近上界О(f (n))来表示时间复杂度。
看算法1-4，并分析算法的时间复杂度。
//算法1-4
i=1; //运行1次
while(i<=n) //可假设运行x+1次
{
i=i*2; //可假设运行x次
}算法1-4乍一看无法确定while 及i = i*2运行了多少次，这时可假设运行了x次，每次运算后i值为2,22,23,…,2x，当i=n时结束，即2x=n时结束，则x=log2n，那么算法1-4的运算次数为1+2log2n，时间复杂度渐进上界为О(f (n))=О(log2n)。
问题规模：即问题的大小，是指问题输入量的多少。一般来讲，算法的复杂度和问题规模有关，规模越大，复杂度越高。复杂度一般表示为关于问题规模的函数，如问题规模为n，时间复杂度渐进上界表示为О(f (n))。
语句频度：语句重复执行的次数。
在算法分析中，渐进复杂度是对算法运行次数的粗略估计，大致反映问题规模增长趋势，而不必精确计算算法的运行时间。在计算渐进时间复杂度时，可以只考虑对算法运行时间贡献大的语句，而忽略那些运算次数少的语句，循环语句中处在循环内层的语句往往是运行次数最多的，即语句频度最多的语句，该语句对运行时间贡献最大。比如，在算法1-3中，total=total+i*j是对算法贡献最大的语句，只计算该语句的运行次数即可。
注意：不是每个算法都能直接计算运行次数。
例如算法1-5，在a[n]数组中顺序查找x，返回其下标i，如果没找到，则返回−1。
//算法1-5
findx(int x) //在a[n]数组中顺序查找x
{
for(i=0;i<n;i++)
{
if(a[i]==x)
return i; //返回其下标i
｝
return -1;
}算法1-5很难计算该程序到底执行了多少次，因为执行次数依赖于x在数组中的位置。如果第一个元素就是x，则执行1次（最好情况）；如果最后一个元素是x，则执行n次（最坏情况）；如果分布概率均等，则平均执行次数为
（平均情况）。
有些算法（如排序、查找、插入等）可以分为最好情况、最坏情况和平均情况分别求算法渐进复杂度，但我们考查一个算法通常考查其最坏情况，而不是最好情况，最坏情况对衡量算法的好坏具有实际的意义。在现实生活中，我们做什么事情，也会考虑最坏会怎样，最好会怎样，但最坏情况对决策有关键作用。
问：我明白了，那空间复杂度应该就是算法占多大存储空间了？
空间复杂度：算法占用的空间大小。一般将算法的辅助空间作为衡量空间复杂度的标准。
空间复杂度的本意是指算法在运行过程中占用了多少存储空间，算法占用的存储空间包括如下。
（1）输入/输出数据所占空间。
（2）算法本身所占空间。
（3）额外需要的辅助空间。
输入/输出数据占用的空间是必需的，算法本身占用的空间可以通过精简算法来缩减，但这个压缩的量是很小的，可以忽略不计。而在运行时使用的辅助变量所占用的空间，即辅助空间是衡量空间复杂度的关键因素。
算法1-6将两个数交换，并分析其空间复杂度。
//算法1-6
swap(int x,int y) //x与y交换
{
int temp;
temp=x; // temp为辅助空间 ①
x=y; ②
y=temp; ③
}两数的交换过程如图1-17所示。
图1-17 两数的交换过程
图1-17中的步骤标号与算法1-6中的语句标号一一对应，该算法使用了一个辅助空间temp，空间复杂度为О(1)。
注意：在递归算法中，每一次递推需要一个栈空间来保存调用记录，因此空间复杂度需要计算递归栈的辅助空间。
看算法1-7，计算n的阶乘，并分析其空间复杂度。
//算法1-7
fac(int n) //计算n的阶乘
{
if(n<0) //小于零的数无阶乘值
{
printf("n<0,data error!");
return -1;
}
else if(n==0||n==1)
return 1;
else
return n*fac(n-1);
}阶乘是典型的递归调用问题，递归包括递推和回归。递推首先将原问题不断分解成子问题，直到达到结束条件，返回最近子问题的解；然后逆向逐一回归，最终到达递推开始的原问题，返回原问题的解。
思考：例如，求5的阶乘，程序将怎样计算呢？
5的阶乘递推和回归过程如图1-18和图1-19所示。
图1-18 5的阶乘递推过程
图1-19 5的阶乘回归过程
图1-18和图1-19的递推和回归过程是我们从逻辑思维上推理，并以图的方式形象表达出来的。计算机内部是怎样处理的呢？计算机使用一种称为“栈”的数据结构，它类似于一个放一摞盘子的容器，每次放进去一个，拿出来的时候只能从顶端拿一个，不允许从中间插入或抽取，因此称为“后进先出”（Last In First Out，LIFO）。
5的阶乘递推（进栈）过程的形象表达如图1-20所示，实际递归中传递的是参数地址。
图1-20 5的阶乘递推（进栈）过程
5的阶乘回归（出栈）过程的形象表达如图1-21所示。
图1-21 5的阶乘回归（出栈）过程
从图1-20和图1-21的进栈和出栈过程中可以很清晰地看到，首先一步步把子问题压进栈，直到得到返回值，再一步步出栈，最终得到递归结果。在运算过程中，使用了n个栈空间作为辅助空间，因此阶乘递归算法的空间复杂度为О(n)。算法1-7中的时间复杂度也为О(n)，因为n的阶乘仅比n−1的阶乘多了一次乘法运算，fac(n)=n*fac(n−1)，如果用T(n)表示fac(n)的时间复杂度，那么：
有一个古老的传说：有一位国王的女儿不幸落水，水中有很多鳄鱼，国王情急之下下令：“谁能把公主救上来，就把女儿嫁给他。”很多人纷纷退让，一个勇敢的小伙子挺身而出，冒着生命危险把公主救了上来。国王一看他是个穷小子，想要反悔，说：“除了女儿，你要什么都可以。”小伙子说：“好吧，我只要一棋盘的麦子。您在第一个格子里放一粒麦子，在第二个格子里放2粒，在第3个格子里放4粒，在第4个格子里放8粒，依次类推，每一格子里的麦子粒数都是前一格的两倍。把这64个格子都放好了，我就要这么多。”国王听后哈哈大笑，觉得农夫的要求很容易满足，满口答应。结果国王把全国的麦子都拿来，也填不完这64格……国王无奈，只好把女儿嫁给了这个小伙子。
解析
如上所述，棋盘上64个格子究竟要放多少粒麦子？
把每一个格子放的麦子数加起来，总和为S，则：
S=1+21+22+23+…+263
（1-1）
把式（1-1）等号两边都乘以2，等式仍然成立：
2S=21+22+23+…+263+264
（1-2）
式（1-2）减去式（1-1），则：
S=264−1 =18 446 744 073 709 551 615
据专家统计，每个麦粒的平均重量约41.9mg，那么这些麦粒的总重量是：
18 446 744 073 709 551 615×41.9=772 918 576 688 430 212 668.5（mg）
≈7 729（亿吨）
全世界人口按60亿算，每人可以分得128吨！
我们称这样的函数为爆炸增量函数。想一想，如果你的算法时间复杂度是О(2n)会怎样？随着n的增长，这个算法会不会爆掉？你也许经常见到有些算法调试没问题，运行一段也没问题，但关键的时候“死机”。例如，在线考试系统，50人考试没问题，100人考试也没问题，如果10 000人考试怎么样？
注：“死机”就是计算机不能正常工作了，包括一切原因导致出现的“死机”。计算机主机出现意外故障而“死机”，一些数据库“死锁”，服务器的某些服务意外停止运行，也可以称为“死机”。
常见的算法时间复杂度如下。
（1）常数阶：常数阶算法运行的次数是一个具体的常数，如5、20、100等。常数阶算法时间复杂度通常用О(1)表示，比如算法1-6，它的运行次数为4，就是常数阶，用О(1)表示。
（2）多项式阶：很多算法时间复杂度是多项式，通常用О(n)、О(n2)、О(n3)等表示。比如算法1-3就是多项式阶。
（3）指数阶：指数阶时间复杂度运行效率极差，程序员往往像躲恶魔一样避开它，常见的有О(2n)、О(n!)、О(nn)等，对待这样的算法要慎重。
（4）对数阶：对数阶时间复杂度运行效率较高，常见的有О(logn)、О(nlogn)等，如算法1-4所示。
常见时间复杂度函数曲线如图1-22所示。
图1-22 常见函数增量曲线
从图1-22可以看出，指数阶增量随着x的增加急剧增加，而对数阶增加缓慢。它们之间的关系如下：
О(1)< О(logn)< О(n)< О(nlogn)
< О(n2)< О(n3)< О(2n) < О(n!)< О(nn)
我们在设计算法时要注意算法复杂度增量的问题，尽量避免爆炸增量。
假设第一个月有一对刚诞生的兔子，第二个月进入成熟期，第三个月开始生育兔子，而一对成熟的兔子每月会生一对兔子，兔子永不死去。那么，由一对初生兔子开始，12个月后会有多少对兔子呢？M个月后又会有多少对兔子呢？
兔子数列即斐波那契数列。“斐波那契数列”的发明者是意大利数学家列昂纳多•斐波那契（Leonardo Fibonacci，1170—1250）。他的籍贯是比萨，因此被人称作“比萨的列昂纳多”。1202年，他撰写了《算盘全书》一书。该书是一部较全面的初等数学著作，向欧洲系统地介绍了印度-阿拉伯数码及其演算法则，介绍了中国的“盈不足术”；引入了负数；研究了一些简单的一次同余式组。斐波那契还著有《象限仪书》与《精华》，还写了几何学专著《几何实习》。
（1）问题分析
我们不妨拿新出生的一对兔子分析：
第1个月，兔子①没有繁殖能力，所以还是1对。
第2个月，兔子①进入成熟期，仍然是1对。
第3个月，兔子①生了一对小兔②，于是这个月共有2对（1+1=2）兔子。
第4个月，兔子①又生了一对小兔③，因此共有3对（1+2=3）兔子。
第5个月，兔子①又生了一对小兔④，在第3个月出生的小兔②也生下了一对小兔⑤，因此共有5对（2+3=5）兔子。
第6个月，兔子①②③各生下了一对小兔，新生3对兔子加上原先的5对兔子，这个月共有8对（3+5=8）兔子。
……
为了表达得更清楚，我们用图来表示新生兔子、成熟期兔子、生育期兔子，兔子的繁殖过程，如图1-23所示。
图1-23 兔子繁殖过程
这个数列有十分明显的特点，即从第3个月开始，当月的兔子数=上月兔子数+当月新生兔子数，而当月新生的兔子正好是上上月的兔子数。因此，前面相邻两项之和，构成了后一项，即：
当月的兔子数=上月兔子数+上上月的兔子数
斐波那契数列如下：
1，1，2，3，5，8，13，21，34，…
递归式表达式如下：
那么我们该怎么设计算法呢？
答：哈哈，这太简单了，用递归很快就算出来了！
（2）算法设计
首先按照递归表达式设计一个递归算法，见算法1-8。
//算法1-8
Fib1(int n)
{
if(n<1)
return -1;
if(n==1||n==2)
return 1;
return Fib1(n-1)+Fib1(n-2);
}写得不错。算法设计完成后，我们有3个问题。
（3）算法验证分析
第一个问题毋庸置疑，算法1-8是完全按照递推公式写出来的，正确性没有问题。那么算法复杂度呢？假设T(n)表示计算Fib1(n)所需要的基本操作次数，那么：
n=1时，T(n)=1；
n=2时，T(n)=1；
n=3时，T(n)=3；//调用Fib1(1)、Fib1(0)和执行一次加法运算Fib1(1)+Fib1(0)
因此，n>2时要分别调用Fib1(n−1)、Fib1(n−2)和执行一次加法运算。
n>2时，T(n)= T(n−1)+ T(n−2)+1；
递归表达式和时间复杂度T(n)之间的关系如下。
由此可得：
T(n)F(n)
那么F(n)怎么计算呢？
斐波那契数列通项为：
当n趋近于无穷时，
由于T(n)F(n)，这是一个指数阶的算法！
如果我们今年计算出了F(100)，那么明年才能算出F(101)，多算一个斐波那契数需要一年的时间，爆炸增量函数是算法设计的噩梦！算法1-8的时间复杂度属于爆炸增量函数，这在算法设计时是惟恐避之不及的，那么我们能不能改进它呢？
（4）算法改进
既然斐波那契数列每一项是前两项之和，我们为什么不记录前两项的值？这样只需要一次加法运算就可以得到当前项，时间复杂度会不会更好一点？我们用数组试试看，见算法1-9。
//算法1-9
Fib2(int n)
{
if(n<1)
return -1;
int *a=new int[n+1];//定义一个长度为n+1的数组，0空间未用
a[1]=1；
a[2]=1;
for(int i=3;i<=n;i++)
a[i]=a[i-1]+a[i-2];
return a[n];
}很明显，算法1-9时间复杂度为О(n)。算法仍然是按照F(n)定义的，所以正确性没有问题，而时间复杂度却从算法1-8的指数阶降到了多项式阶，这是算法效率的巨大突破之一！
算法1-9使用了一个辅助数组记录中间结果，因此空间复杂度也为О(n)。其实我们只需要得到第n个斐波那契数，中间结果只是为了下一次使用，根本不需要记录。因此我们可以采用迭代法进行算法设计，见算法1-10。
//算法1-10
Fib3(int n)
{
int i,s1,s2;
if(n<1)
return -1;
if(n==1||n==2)
return 1;
s1=1;
s2=1;
for(i=3;i<=n;i++)
{
s2=s1+s2; //辗转相加法
s1=s2-s1; //记录前一项
}
return s2;
}迭代过程如下。
初始值：s1=1; s2=1;
当前解 记录前一项
i=3时 s2= s1+s2=2 s1= s2−s1=1
i=4时 s2= s1+s2=3 s1= s2−s1=2
i=5时 s2= s1+s2=5 s1= s2−s1=3
i=6时 s2= s1+s2=8 s1= s2−s1=5
…… …… ……
算法1-10使用了几个辅助变量，迭代辗转相加，每次记录前一项，时间复杂度为О(n)，但空间复杂度降到了О(1)。
问题的进一步讨论：我们能不能继续降阶，使算法时间复杂度更低呢？实际上，斐波那契数列时间复杂度还可以降到对数阶О(logn)，有兴趣的读者可以查阅相关资料。想想看，我们把一个算法从指数阶降到多项式阶，再降到对数阶，这是一件多么振奋人心的事！
本章的内容要点如下。
（1）基本概念：数据、数据元素、数据项和数据结构。
（2）数据结构包含逻辑结构、存储结构和运算三个要素，如图1-24所示。
图1-24 数据结构主要内容
（3）时间复杂度的衡量标准及渐近上界符号О(f (n))表示。
（4）衡量算法的好坏通常会考查算法的最坏情况。
（5）空间复杂度只计算辅助空间。
（6）递归算法的空间复杂度要计算递归使用的栈空间。
2.1 顺序表
2.2 单链表
2.3 双向链表
2.4 循环链表
2.5 线性表的应用
2.6 线性表学习秘籍
线性表是由n（n0）个相同类型的数据元素组成的有限序列，它是最基本、最常用的一种线性结构。顾名思义，线性表就像是一条线，不会分叉。线性表有唯一的开始和结束，除了第一个元素外，每个元素都有唯一的直接前驱：除了最后一个元素外，每个元素都有唯一的直接后继，如图2-1所示。
图2-1 前驱和后继
注意：为了描述方便，本书中提到的前驱和后继均代指直接前驱和直接后继。
线性表有两种存储方式：顺序存储和链式存储。采用顺序存储的线性表称为顺序表，采用链式存储的线性表称为链表。链表又分为单链表、双向链表和循环链表，本章将分别予以详述。
顺序表采用顺序存储方式，即逻辑上相邻的数据在计算机内的存储位置也是相邻的。顺序存储方式，元素存储是连续的，中间不允许有空，可以快速定位第几个元素，但是插入和删除时需要移动大量元素。根据分配空间方法不同，顺序表可以分为静态分配和动态分配两种方法。
顺序表最简单的方法是使用一个定长数组data[]存储数据，最大空间为Maxsize，用length记录实际的元素个数，即顺序表的长度。这种用定长数组存储的方法称为静态分配。静态顺序表如图2-2所示。
图2-2 静态顺序表
顺序表的静态分配结构体定义，如图2-3所示。采用静态分配方法，定长数组需要预先分配一段固定大小的连续空间，但是在运算的过程中，如合并、插入等操作，容易超过预分配的空间长度，出现溢出。解决静态分配的溢出问题，可以采用动态分配的方法。
图2-3 顺序表静态分配定义
在程序运行过程中，根据需要动态分配一段连续的空间（大小为Maxsize），用elem记录该空间的基地址（首地址），用length记录实际的元素个数，即顺序表的长度。动态顺序表如图2-4所示。采用动态存储方法，在运算过程中，如果发生溢出，可以另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储空间的目的。
图2-4 动态顺序表
顺序表的动态分配结构体定义，如图2-5所示。
图2-5 顺序表动态分配定义
结构体定义的解释说明如下。
问题1：使用typedef有什么用处？
问题2：为什么使用ElemType作为数据类型？
解答如下。
问题1：typedef是C/C++语言的关键字，用于给原有数据类型起一个别名，在程序中可以等价使用，语法规则如下。
typedef类型名称 类型标识符;“类型名称”为已知数据类型，包括基本数据类型（如int、float等）和用户自定义数据类型（如用struct自定义的结构体）。
“类型标识符”是为原有数据类型起的别名，需要满足标识符命名规则。就像给某个人起一个小名或绰号一样，如《水浒传》中李逵的绰号“黑旋风”，大家听到“黑旋风”就知道是李逵。
使用typedef有什么好处呢？
给复杂的结构体类型起一个别名，这样就可以使用这个别名等价该结构体类型，在声明该类型变量时就方便多了。
例如，不使用typedef的顺序表定义：
struct SqList {
int *elem; //顺序表的基地址
int length; //顺序表的长度
};如果需要定义一个顺序表，需要写：
struct SqList L; //定义时需要加上struct(c需要，C++不需要)，L为顺序表的名字使用typedef的顺序表定义：
typedef struct {
int *elem; //顺序表的基地址
int length; //顺序表的长度
}SqList;如果需要定义一个顺序表，需要写：
SqList L; //不需要写struct，直接用别名定义例如，在程序中使用这样的语句：
typedef int ElemType; //给int起个别名ElemType在程序中，假如有n个地方用到了ElemType类型，如果现在处理的数据变为字符型了，那么就可以将上面类型定义中的int直接改为char。
typedef char ElemType;这样只需要修改类型定义，不需要改动程序中的代码。如果不使用typedef类型定义，就需要把程序中n个用到int类型的地方全部改为char类型。如果某处忘记修改，就会产生错误。
问题2：使用ElemType是为了让算法的通用性更好，因为使用线性表的结构体定义后，并不清楚具体问题处理的数据是什么类型，不能简单地写成某一种类型。结合typedef使用，可以提高算法的通用性和可移植性。
以int型元素为例，如果使用顺序表的动态分配结构体定义，就可以直接将ElemType写成int。
typedef struct{
int *elem; //顺序表的基地址
int length; //顺序表的长度
}SqList;也可以使用类型定义，给int起个别名：
typedef int ElemType; //给int起个别名ElemType，两者等价
typedef struct{
ElemType *elem; //顺序表的基地址
int length; //顺序表的长度
}SqList;显然，后一种定义的通用性和可移植性更好，当然第一种定义也没有错。
下面以动态分配空间的方法为例，分别介绍顺序表的初始化、创建、取值、查找、插入、删除等基本操作。
初始化是指为顺序表分配一段预定义大小的连续空间，用elem记录这段空间的基地址，当前空间内没有任何数据元素，因此元素的实际个数为0。假设我们已经预定义了一个最大空间数Maxsize，那么就用new分配大小为Maxsize的空间，分配成功会返回空间的首地址，分配失败会返回空指针。
初始化后的顺序表如图2-6所示。
代码实现
bool InitList(SqList &L) //构造一个空的顺序表L
{ //L前面加&表示引用参数，函数内部的改变跳出函数后仍然有效
//如果不加&，函数内部的改变在跳出函数后便会无效
L.elem=new int[Maxsize]; //为顺序表动态分配Maxsize个空间
if(!L.elem) return false; //分配空间失败
L.length=0; //顺序表长度为0
return true;
}图2-6 顺序表初始化
顺序表创建是向顺序表中输入数据，输入数据的类型必须与类型定义中的类型一致。
算法步骤
1）初始化下标变量i=0，判断顺序表是否已满，如果是则结束；否则执行第2步。
2）输入一个数据元素x。
3）将数据x存入顺序表的第i个位置，即L.elem[i]=x，然后i++。
4）顺序表长度加1，即L.length++。
5）直到数据输入完毕。
完美图解
1）输入元素：5。将数据元素5存入顺序表的第0个位置，即L.elem[0]=5，然后i++，如图2-7所示。
图2-7 顺序表（存入元素5）
2）输入元素：3。将数据元素3存入顺序表的第1个位置，即L.elem[1]=3，然后i++，如图2-8所示。
图2-8 顺序表（存入元素3）
3）输入元素：9。将数据元素9存入顺序表的第2个位置，即L.elem[2]=9，然后i++，如图2-9所示。
图2-9 顺序表（存入元素9）
代码实现
bool CreateList(SqList &L) //创建一个顺序表L
{ //L加&表示引用类型参数，函数内部的改变跳出函数仍然有效
//不加&则在内部改变时，跳出函数后无效
int x,i=0；
cin>>x;
while(x!=-1)//输入-1时结束，也可以设置其他的结束条件
{
if(L.length==Maxsize)
{
cout<<"顺序表已满！"
return false;
}
cin>>x;//输入一个数据元素
L.elem[i++]=x; //将数据存入第i个位置，然后i++
L.length++; //顺序表长度加1
cin>>x; //输入一个数据元素
}
return true;
}顺序表中的任何一个元素都可以立即找到，称为随机存取方式。例如，要取第i个元素，只要i值是合法的（1iL.length），那么立即就可以找到该元素。由于下标是从0开始的，因此第i个元素，其下标为i−1，即对应元素为L.elem[i−1]，如图2-10所示。
图2-10 顺序表（取值）
注意：位序是指第几个元素，位序和下标差1。
代码实现
bool GetElem(SqList L,int i,int &e)
{
if(i<1||i>L.length) return false;
//判断i值是否合理，若不合理，则返回false
e=L.elem[i-1]; //第i-1个单元存储着第i个数据
return true;
}在顺序表中查找一个元素e，可以从第一个元素开始顺序查找，依次比较每一个元素值。如果相等，则返回元素位置（位序，即第几个元素）；如果查找整个顺序表都没找到，则返回−1。例如，在图2-11的顺序表中，查找元素8，查找到其下标为5，返回位序为6。
图2-11 顺序表（查找）
代码实现
int LocateELem(SqList L,int e)
{
for(i=0;i<L.length;i++)
if(L.elem[i]==e) return i+1; //下标为i，实际为第i+1个元素
return -1; //如果没找到，则返回-1
}算法复杂度分析
如果顺序表的表长为n，即n=L.length，那么可以分最好、最坏和平均3种情况分析顺序表查找算法的复杂性。
因此，假设每个关键字查找的概率均等，顺序表查找算法的平均时间复杂度为O(n)。
在顺序表中第i个位置之前插入一个元素e，需要从最后一个元素开始，后移一位……直到把第i个元素也后移一位，然后把e放入第i个位置，如图2-12所示。
图2-12 顺序表（插入）
算法步骤
1）判断插入位置i是否合法（1iL.length+1），可以在第一个元素之前插入，也可以在第L.length+1个元素之前插入。
2）判断顺序表的存储空间是否已满。
3）将第L.length至第i个元素依次向后移动一个位置，空出第i个位置。
4）将要插入的新元素e放入第i个位置。
5）表长加1，插入成功返回true。
完美图解
例：在图2-13的顺序表中的第5个位置之前插入一个元素9。
图2-13 顺序表
插入过程如下。
1）移动元素。从最后一个元素（下标为L.length−1）开始后移一位，移动元素过程如图2-14～图2-17所示。
图2-14 元素后移过程1
图2-15 元素后移过程2
图2-16 元素后移过程3
图2-17 元素后移过程4
2）插入元素。此时第5个位置空出来，将要插入的新元素9放入第5个位置，表长加1，如图2-18所示。
图2-18 插入元素9
代码实现
bool ListInsert_Sq(SqList &L,int i ,int e)
{
if(i<1 || i>L.length+1) return false; //i值不合法
if(L.length==Maxsize) return false; //存储空间已满
for(int j=L.length-1;j>=i-1;j--)
L.elem[j+1]=L.elem[j]; //从最后一个元素开始后移，直到第i个元素后移
L.elem[i-1]=e; //将新元素e放入第i个位置
L.length++; //表长加1
return true;
}算法复杂度分析
可以在第1个位置之前插入，也可以在第2个位置之前……第n个位置之前，第n+1个位置之前插入，一共有n+1种情况，每种情况移动元素的个数是n−i+1。把每种情况移动次数乘以其插入概率pi并求和，即为平均时间复杂度。如果插入概率均等，即每个位置的插入概率均为1/(n+1)，则平均时间复杂度为：
因此，假设每个位置插入的概率均等，顺序表插入算法平均时间复杂度为O(n)。
在顺序表中删除第i个元素，需要把该元素暂存到变量e中，然后从i+1个元素开始前移……直到把第n个元素也前移一位，即可完成删除操作，如图2-19所示。
算法步骤
1）判断删除位置i是否合法（1iL.length）。
2）将欲删除的元素保存在e中。
3）将第i+1至第n 个元素依次向前移动一个位置。
4）表长减1，删除成功，返回true。
图2-19 删除元素
完美图解
例：从图2-20的顺序表中删除第5个元素。
图2-20 顺序表
删除过程如下。
1）移动元素。首先将待删除元素2暂存到变量e中，以后可能有用，如果不暂存，将会被覆盖。然后从第6个元素开始前移一位，移动元素过程如图2-21～图2-23所示。
图2-21 元素后移过程1
图2-22 元素后移过程2
图2-23 元素后移过程3
2）表长减1，删除元素后的顺序表如图2-24所示。
图2-24 顺序表（删除元素后）
代码实现
bool ListDelete_Sq(SqList &L,int i, int &e)
{
if(i<1||i>L.length) return false; //i值不合法
e=L.elem[i-1]; //将欲删除的元素保存在e中
for (int j=i;j<=L.length-1;j++)
L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移
L.length--; //表长减1
return true;
}算法复杂度分析
顺序表元素删除一共有n种情况，每种情况移动元素的个数是n−i。把每种情况移动次数乘以其删除概率pi并求和，即为平均时间复杂度。假设删除每个元素的概率均等，即每个元素的删除概率均为1/n，则平均时间复杂度为：
因此，假设每个元素删除的概率均等，顺序表删除算法平均时间复杂度为O(n)。
顺序表的优点：操作简单，存储密度高，可以随机存取，只需要O(1)的时间就可以取出第i个元素。
顺序表的缺点：需要预先分配最大空间，最大空间数估计过大或过小会造成空间浪费或溢出。插入和删除操作需要移动大量元素。
在实际问题中，如果经常需要插入和删除操作，则顺序表的效率很低。为了克服该缺点，可以采用链式存储。
链表是线性表的链式存储方式。逻辑上相邻的数据在计算机内的存储位置不一定相邻。那么怎么表示逻辑上的相邻关系呢？
可以给每个元素附加一个指针域，指向下一个元素的存储位置，如图2-25所示。
图2-25 单链表的存储方式
从图2-25中可以看出，每个节点包含两个域：数据域和指针域。数据域存储数据元素，指针域存储下一个节点的地址，因此指针指向的类型也是节点类型。每个指针都指向下一个节点，都是朝一个方向的，这样的链表称为单向链表或单链表。
单链表的节点结构体定义，如图2-26所示。
图2-26 单链表的节点结构体定义
定义了节点结构体之后，就可以把若干个节点连接在一起，形成一个单链表，如图2-27所示。
图2-27 单链表
是不是像一个铁链，一环扣一环地连在一起？如图2-28所示。
图2-28 铁链
不管这个铁链有多长，只要找到它的头，就可以拉起整个铁链。因此，只要给这个单链表设置一个头指针，这个链表中的每个节点就都可以找到了，如图2-29所示。
图2-29 单链表
有时为了操作方便，还会给链表增加一个不存放数据的头节点（也可以存放表长等信息），如图2-30所示。
图2-30 单链表（带头节点）
带有头节点的链表就像是给铁链加了钥匙扣，如图2-31所示。
图2-31 铁链（加了钥匙扣）
有的书中还提到了首元节点，即第一个数据元素节点。其实完全没必要混淆视听，只需要知道头指针、头节点就可以了。
在顺序表中，想找第i个元素，可以立即通过L.elem[i−1]找到，想找哪个就找哪个，称为随机存取。但是在单链表中，想找第i个元素就没那么容易，必须从头开始，按顺序一个一个找，一直数到第i个元素，称为顺序存取。
下面以带头节点的单链表为例，讲解单链表的初始化、创建、取值、查找、插入、删除等基本操作。
单链表的初始化是指构建一个空表。先创建一个头节点，不存储数据，然后令其指针域为空，如图2-32所示。
图2-32 单链表的初始化
代码实现
bool InitList_L(LinkList &L)//构造一个空的单链表L
{
L=new LNode; //生成新节点作为头节点，用头指针L指向头节点
if(!L)
return false; //生成节点失败
L->next=NULL; //头节点的指针域置空
return true;
}创建单链表分为头插法和尾插法两种，头插法是指每次把新节点插到头节点之后，其创建的单链表和数据输入顺序正好相反，因此也称为逆序建表。尾插法是指每次把新节点链接到链表的尾部，其创建的单链表和数据输入顺序一致，因此也称为正序建表。
我们先讲头插法建表。头插法每次把新节点插入到头节点之后，创建的单链表和数据输入顺序相反。
完美图解
1）初始状态。初始状态是指初始化后的空表，只有一个头节点，如图2-33所示。
图2-33 单链表（空表）
2）输入数据元素1，创建新节点，把元素1放入新节点数据域，如图2-34所示。
图2-34 新节点（元素1）
s=new LNode; //生成新节点s
cin>>s->data; //输入元素值赋给新节点的数据域3）头插操作，插入头节点的后面，插入过程如图2-35所示。
图2-35 插入（第一个节点）
4）输入数据元素2，创建新节点，把元素2放入新节点数据域，如图2-36所示。
图2-36 新节点（元素2）
5）头插操作，插入头节点的后面，如图2-37所示。
图2-37 插入（第二个节点）
赋值解释
假设赋值之前节点的地址及指针，如图2-38所示。
图2-38 赋值之前的节点
赋值语句两端，等号的右侧是节点的地址，等号的左侧是节点的指针域。
① s->next=L->next：L->next存储的是下一个节点地址“9630”，将该地址赋值给s->next指针域，即s节点的next指针指向1节点，如图2-39所示。
图2-39 执行第一个赋值语句后
② L->next=s：将s节点的地址“2046”赋值给L->next指针域，即L节点的next指针指向s节点，如图2-40所示。
图2-40 执行第二个赋值语句后
修改指针顺序
为什么要先修改后面那个指针呢？
因为一旦修改了L节点的指针域指向s，那么原来L节点后面的节点就找不到了，因此修改指针是有顺序的。
修改指针的顺序原则：先修改没有指针标记的那一端，如图2-41所示。
图2-41 指针修改（有顺序）
如果要插入节点的两端都有标记，例如，再定义一个指针q指向L节点后面的节点，那么先修改哪个指针都无所谓了，如图2-42所示。
图2-42 指针修改（无顺序）
6）拉直链表之后，如图2-43所示。
图2-43 插入2节点后
7）继续依次输入数据元素3、4、5、6、7、8、9、10，头插法创建的单链表如图2-44所示。可以看出，头插法创建的单链表与数据输入顺序正好相反。
图2-44 头插法创建的单链表（逆序）
代码实现
void CreateList_H(LinkList &L)//头插法创建单链表
{
int n; //输入n个元素的值，建立到头节点的单链表L
LinkList s; //定义一个指针变量
L=new LNode;
L->next=NULL; //先建立一个带头节点的空链表
cout<<"请输入元素个数n：" <<endl;
cin>>n;
cout<<"请依次输入n个元素：" <<endl;
cout<<"头插法创建单链表..." <<endl;
while(n--)
{
s=new LNode; //生成新节点s
cin>>s->data; //输入元素值赋值给新节点的数据域
s->next=L->next;
L->next=s; //将新节点s插入头节点之后
}
}接下来，我们讲尾插法建表。尾插法每次把新节点链接到链表的尾部，其创建的单链表和数据输入顺序一致。
完美图解
尾插法每次把新节点链接到链表的尾部，因此需要一个尾指针永远指向链表的尾节点。
1）初始状态。初始状态是指初始化后的空表，只有一个头节点，设置一个尾指针r指向该节点，如图2-45所示。
图2-45 单链表（空表）
2）输入数据元素1，创建新节点，把元素1放入新节点数据域，如图2-46所示。
s=new LNode; //生成新节点s
cin>>s->data; //输入数据元素赋值给新节点的数据域图2-46 新节点（元素1）
3）完成尾插操作，插入尾节点的后面，如图2-47所示。
图2-47 插入（第一个节点）
赋值解释
① s->next=NULL：s节点的指针域置空。
② r->next=s：将s节点的地址赋值给r节点的指针域，即将新节点s插入尾节点r之后。
③ r=s：将s节点的地址赋值给r，即r指向新的尾节点s。
4）输入数据元素2，创建新节点，把元素2放入新节点数据域，如图2-48所示。
图2-48 新节点（元素2）
5）完成尾插操作，插入尾节点的后面，如图2-49所示。
图2-49 插入（第二个节点）
6）继续依次输入数据元素3、4、5、6、7、8、9、10，尾插法创建的单链表如图2-50所示。可以看出，尾插法创建的单链表与数据输入顺序一致。
图2-50 尾插法创建的单链表（正序）
代码实现
void CreateList_R(LinkList &L)//尾插法创建单链表
{
//输入n个元素的值，建立带表头节点的单链表L
int n;
LinkList s, r;
L=new LNode;
L->next=NULL; //先建立一个带头节点的空链表
r=L; //尾指针r指向头节点
cout<<"请输入元素个数n：" <<endl;
cin>>n;
cout<<"请依次输入n个元素：" <<endl;
cout<<"尾插法创建单链表..." <<endl;
while(n--)
{
s=new LNode;//生成新节点
cin>>s->data; //输入元素值赋给新节点的数据域
s->next=NULL;
r->next=s;//将新节点s插入尾节点r之后
r=s;//r指向新的尾节点s
}
}单链表的取值不像顺序表那样可以随机访问任何一个元素，单链表只有头指针，各个节点的物理地址是不连续的。要想找到第i个节点，就必须从第一个节点开始按顺序向后找，一直找到第i个节点。那么具体怎么做呢？
注意：链表的头指针不可以随意改动！
一个链表是由头指针来标识的，一旦头指针改动或丢失，这个链表就不完整或找不到了。想想看，你拉着铁链子的一头，另一头绑着水桶，到井里打水，如果你手一松，链子掉到井里，就找不到了。所以链表的头指针是不能随意改动的，如果需要用指针移动，可定义一个指针变量进行移动。
算法步骤
1）先定义一个p 指针，指向第一个元素节点，用j作为计数器，j=1。
2）如果p不为空且j<i，则p指向p的下一个节点，然后j加1，即：p=p->next; j++。
3）直到p为空或者j=i停止。p为空，说明没有数到i，链表就结束了，即不存在第i个节点；j=i，说明找到了第i个节点。
完美图解
1）p指针指向第一个元素节点，j=1，如图2-51所示。
图2-51 取值过程1
2）p指针指向第二个元素节点，j=2，如图2-52所示。
图2-52 取值过程2
3）p指针指向第i个元素节点，j=i，如图2-53所示。
图2-53 取值过程3
代码实现
bool GetElem_L(LinkList L,int i,int &e)//单链表的取值
{
//在带头节点的单链表L中查找第i个元素
//用e记录L中第i个数据元素的值
int j;
LinkList p;
p=L->next; //p指向第一个数据节点
j=1; //j为计数器
while(j<i&&p) //顺着链表向后扫描，直到p指向第i个元素或p为空
{
p=p->next; //p指向下一个节点
j++; //计数器j加1
}
if(!p||j>i) //i值不合法，i＞n或i<=0
return false;
e=p->data; //取第i个节点的数据域
return true;
}在一个单链表中查找是否存在元素e，可以定义一个p指针，指向第一个元素节点，比较p指向节点的数据域是否等于e。如果相等，查找成功，返回true；如果不等，则p指向p的下一个节点，继续比较，如果p为空，查找失败，返回false，如图2-54所示。
图2-54 查找
代码实现
bool LocateElem_L(LinkList L,int e) //在带头节点的单链表L中查找值为e的元素
{
LinkList p;
p=L->next;
while(p&&p->data!=e)//沿着链表向后扫描，直到p为空或p所指节点数据域等于e
p=p->next; //p指向下一个节点
if(!p)
return false; //查找失败，p为NULL
return true;
}如果要在第i个节点之前插入一个元素，则必须先找到第i−1个节点，想一想：为什么？
单链表只有一个指针域，是向后操作的，不可以向前操作。如果直接找到第i个节点，就无法向前操作，把新节点插入第i个节点之前。实际上，在第i个节点之前插入一个元素相当于在第i−1个节点之后插入一个元素，因此先找到第i−1个节点，然后将新节点插在其后面即可。
算法步骤
1）定义一个p指针，指向头节点，用j作为计数器，j=0。
2）如果p不为空且j<i−1，则p指向p的下一个节点，然后j加1，即：p=p->next; j++。
3）直到p为空或j >=i−1停止。
4）p为空，说明没有数到i−1，链表就结束了，即i＞n+1，i值不合法；j >i−1说明i＜1，此时i值不合法，返回false。如果j=i−1，说明找到了第i−1个节点。
5）将新节点插到第i−1个节点之后。
完美图解
假设已经找到了第i−1个节点，并用p指针指向该节点，s指向待插入的新节点，则插入操作如图2-55所示。
图2-55 插入
赋值解释
① s->next=p->next：将p节点后面的节点地址赋值给s节点的指针域，即s节点的next指针指向p后面的节点。
② p->next=s：将s节点的地址赋值给p节点的指针域，即p节点的next指针指向s节点。
是不是有似曾相识的感觉？
前面讲的前插法建链表，就是每次将新节点插到头节点之后，现在是将新节点插到第i−1个节点之后。
bool ListInsert_L(LinkList &L,int i,int e)//单链表的插入
{
//在带头节点的单链表L中第i个位置之前插入值为e的新节点
int j;
LinkList p,s;
p=L;
j=0;
while(p&&j<i-1) //查找第i-1个节点，p指向该节点
{
p=p->next;
j++;
}
if(!p||j>i-1) //i＞n+1或者i＜1
return false;
s=new LNode; //生成新节点
s->data=e; //将数据元素e放入新节点的数据域
s->next=p->next; //将新节点的指针域指向第i个节点
p->next=s; //将节点p的指针域指向节点s
return true;
}删除一个节点，实际上是把这个节点跳过去。根据单向链表向后操作的特性，要想跳过第i个节点，就必须先找到第i−1个节点，否则是无法跳过去的。删除操作如图2-56所示。
图2-56 删除
赋值解释
p->next=q->next的含义是将q节点的下一个节点地址赋值给p节点的指针域。
对这些有关指针的赋值语句，很多读者不理解，容易混淆。在此说明一下，等号的右侧是节点的地址，等号的左侧是节点的指针域，如图2-57所示。
图2-57 赋值解释
在图2-57中，假设q节点的下一个节点地址为1013，该地址存储在q->next里面，因此等号右侧的q->next的值为1013。把该地址赋值给p节点的next指针域，把原来的值2046覆盖掉，这样p->next也为1013，相当于把q节点跳过去了。赋值之后，如图2-58所示，然后用delete q释放被删除节点的空间。
图2-58 赋值之后
代码实现
bool ListDelete_L(LinkList &L, int i) //单链表的删除
{
//在带头节点的单链表L中，删除第i个位置
LinkList p, q;
int j;
p=L;
j=0;
while((p->next)&&(j<i-1)) //查找第i-1个节点，p指向该节点
{
p=p->next;
j++;
}
if(!(p->next)||(j>i-1))//当i>n或i<1时，删除位置不合理
return false;
q=p->next; //临时保存被删节点的地址以备释放空间
p->next=q->next; //将q节点的下一个节点地址赋值给p节点的指针域
delete q; //释放被删除节点的空间
return true;
}在单链表中，每个节点除存储自身数据之外，还存储了下一个节点的地址，因此可以轻松访问下一个节点，以及后面的所有后继节点。但是，如果想访问前面的节点就不行了，再也回不去了。例如，删除节点q时，要先找到它的前一个节点p，然后才能删掉q节点，单向链表只能向后操作，不可以向前操作。如果需要向前操作，该怎么办呢？
还有另外一种链表——双向链表。
单链表只能向后操作，不可以向前操作。为了向前、向后操作方便，可以给每个元素附加两个指针域，一个存储前一个元素的地址，另一个存储下一个元素的地址。这种链表称为双向链表，如图2-59所示。
图2-59 双向链表
从图2-59中可以看出，双向链表每个节点包含3个域：数据域和两个指针域。两个指针域分别存储前后两个元素节点的地址，即前驱和后继，因此指针指向的类型也是节点类型。
双向链表的节点结构体定义，如图2-60所示。
图2-60 双向链表的节点结构体定义
下面以带头节点的双向链表为例，讲解双向链表的初始化、创建、取值、查找、插入、删除操作。
双向链表初始化是指构建一个空表。先创建一个头节点，不存储数据，然后令其前后两个指针域均为空，如图2-61所示。
图2-61 双向链表初始化
代码实现
bool InitList_L(DuLinkList &L)//构造一个空的双向链表L
{
L=new DuLNode; //生成新节点作为头节点，用头指针L指向头节点
if(!L)
return false; //生成节点失败
L->prior=L->next=NULL; //头节点的两个指针域置空
return true;
}创建双向链表也可以用头插法和尾插法。头插法创建的链表和输入顺序正好相反，称为逆序建表；尾插法创建的链表和输入顺序一致，称为正序建表。
完美图解
头插法建双向链表的过程如下。
1）初始状态是指初始化后的空表，只有一个头节点，前后两个指针域均为空，如图2-62所示。
图2-62 双向链表（空表）
2）输入数据元素1，创建新节点，把元素1放入新节点数据域，如图2-63所示。
图2-63 创建新节点（元素1）
s=new DuLNode; //生成新节点s
cin>>s->data; //输入元素值赋值给新节点的数据域3）头插操作，插入头节点的后面，如图2-64所示。
① s->next=L->next; ② L->next=s; ③ s->prior=L
图2-64 插入（元素1）
4）输入数据元素2，创建新节点，把元素2放入新节点数据域，如图2-65所示。
图2-65 新节点（元素2）
5）头插操作，插入头节点的后面，如图2-66所示。
① s->next=L->next; ② L->next->prior=s; ③ s->prior=L; ④ L->next=s;
图2-66 插入（元素2）
赋值解释
① s->next=L->next：将L节点后面的节点（后继）地址赋值给s节点的指针域，即s节点的next指针指向L的后继节点。
② L->next->prior=s：将s节点的地址赋值给L的后继节点的prior指针域，即L的后继节点的prior指针指向s节点。
③ s->prior=L：将L节点的地址赋值给s节点的prior指针域，即s节点的prior指针指向L节点。
④ L->next=s：将s节点的地址赋值给L节点的指针域，即L节点的next指针指向s节点。
注意：赋值语句的右侧是一个地址，左侧是一个节点的指针域。
修改指针顺序的原则：先修改没有指针标记的那一端，如图2-67所示。
图2-67 修改指针顺序
如果要插入节点的两端都有标记，例如再定义一个指针q指向第1个节点，那么先修改哪个指针都无所谓。实际上，只需要将④语句放在最后修改即可，①②③语句顺序无要求。
拉直链表之后，如图2-68所示。
图2-68 插入并拉直后
6）继续依次输入数据元素3、4、5，头插法创建的双向链表如图2-69所示。
图2-69 头插法创建的双向链表
代码实现
void CreateDuList_H(DuLinkList &L)//头插法创建双向链表
{
//输入n个元素的值，建立到头节点的单链表L
int n;
DuLinkList s; //定义一个指针变量
L=new DuLNode;
L->prior=L->next=NULL; //先建立一个带头节点的空链表
cout<<"请输入元素个数n：" <<endl;
cin>>n;
cout<<"请依次输入n个元素：" <<endl;
cout<<"头插法创建单链表..." <<endl;
while(n--)
{
s=new DuLNode; //生成新节点s
cin>>s->data; //输入元素值赋值给新节点的数据域
if(L->next) //如果L后面有节点，则修改其后面节点的prior指针，
//否则只修改后面3个指针即可
L->next->prior=s;
s->next=L->next;
s->prior=L;
L->next=s; //将新节点s插入头节点之后
}
}尾插法建双向链表和尾插法建单链表类似，需要有一个尾指针，不再赘述。
双向链表的取值、查找和单链表的一样，此处不再赘述。
单链表只有一个指针域，是向后操作的，不可以向前处理，因此单链表如果在第i个节点之前插入一个元素，就必须先找到第i−1个节点。在第i个节点之前插入一个元素相当于把新节点放在第i−1个节点之后。而双向链表不需要，因为有两个指针，可以向前后两个方向操作，直接找到第i个节点，就可以把新节点插入第i个节点之前。注意：这里假设第i个节点是存在的，如果第i个节点不存在，而第i−1个节点存在，还是需要找到第i−1个节点，将新节点插入第i−1个节点之后，如图2-70所示。
① p->prior->next=s; ② s->prior=p->prior; ③ s->next=p; ④ p->priotr=s;
图2-70 插入
赋值解释
① p->prior->next=s：s节点的地址赋值给p的前驱节点的next指针域，即p的前驱的next指针指向s。
② s->prior=p->prior：p的前驱的地址赋值给s节点的prior指针域，即s节点的prior指针指向p的前驱。
③ s->next=p：p节点的地址赋值给s节点的next指针域，即s节点的next指针指向p节点。
④ p->prior=s：s节点的地址赋值给p节点的prior指针域，即p节点的prior指针指向s节点。
因为p的前驱无标记，一旦修改了p节点的prior指针，p的前驱就找不到了，因此，最后修改这个指针。实际上，只需要将④语句放在最后修改即可，①②③语句顺序无要求。
修改指针顺序的原则：先修改没有指针标记的那一端。
代码实现
bool ListInsert_L(DuLinkList &L, int i, int &e)//双向链表的插入
{
//在带头节点的单链表L中第i个位置之前插入值为e的新节点
int j;
DuLinkList p, s;
p=L;
j=0;
while(p&&j<i) //查找第i个节点，p指向该节点
{
p=p->next;
j++;
}
if(!p||j>i)//i＞n+1或者i＜1
return false;
s=new DuLNode; //生成新节点
s->data=e; //将新节点的数据域置为e
p->prior->next=s;
s->prior=p->prior;
s->next=p;
p->prior=s;
return true;
}删除一个节点，实际上是把这个节点跳过去。在单向链表中，必须先找到第i−1个节点，才能把第i个节点跳过去。双向链表不必如此，只要直接找到第i个节点，然后修改指针即可，如图2-71所示。
图2-71 删除
p->prior->next=p->next：将p的后继节点的地址赋值给p的前驱节点的next指针域。即p的前驱节点的next指针指向p的后继节点。
注意：等号的右侧是节点的地址，等号的左侧是节点的指针域。
p->next->prior =p->prior：将p的前驱节点的地址赋值给p的后继节点的prior指针域，即p的后继节点的prior指针指向p的前驱节点。此项修改的前提是p的后继节点存在，如果不存在，则不需要此项修改。
这样就把p节点跳过去了，然后用delete p释放被删除节点的空间。删除节点修改指针没有顺序，先修改哪个都可以。
代码实现
bool ListDelete_L(DuLinkList &L, int i) //双向链表的删除
{
//在带头节点的双向链表L中，删除第i个节点
DuLinkList p;
int j;
p=L;
j=0;
while(p&&(j<i)) //查找第i个节点，p指向该节点
{
p=p->next;
j++;
}
if(!p||(j>i))//当i>n或i<1时，删除位置不合理
return false;
if(p->next) //如果p的后继节点存在
p->next->prior=p->prior;
p->prior->next=p->next;
delete p; //释放被删除节点的空间
return true;
}单链表中，只能向后，不能向前。如果从当前节点开始，无法访问该节点前面的节点，而最后一个节点的指针指向头节点，形成一个环，就可以从任何一个节点出发，访问所有的节点，这就是循环链表。循环链表和普通链表的区别就是最后一个节点的后继指向了头节点。单向链表和单向循环链表的区别如图2-72和图2-73所示。
图2-72 单向链表
图2-73 单向循环链表
单向循环链表最后一个节点的next域不为空，而是指向了头节点。
而单向链表和单向循环链表为空的条件也发生了变化，如图2-74和图2-75所示。
图2-74 单向链表空表(L->next=NULL)
图2-75 单向循环链表空表(L->next=L)
双向循环链表除了让最后一个节点的后继指向第一个节点外，还要让头节点的前驱指向最后一个节点，如图2-76所示。
图2-76 双向循环链表
双向循环链表为空表时，L->next=L->prior=L，如图2-77所示。
图2-77 双向循环链表空表
链表的优点：链表是动态存储，不需要预先分配最大空间；插入删除不需要移动元素。
链表的缺点：每次动态分配一个节点，每个节点的地址是不连续的，需要有指针域记录下一个节点的地址，指针域需要占用一个int的空间，因此存储密度低（数据所占空间/节点所占总空间）。存取元素必须从头到尾按顺序查找，属于顺序存取。
线性表的用途非常广泛，在此介绍几个实例，体会线性表的操作过程。其中包括合并有序顺序表、合并有序链表、就地逆置单链表、查找链表的中间节点、删除链表中的重复元素。
题目：将两个有序（非递减）顺序表La和Lb合并为一个新的有序（非递减）顺序表。
解题思路
1）首先创建一个顺序表Lc，其长度为La和Lb的长度之和。
2）然后从La和Lb中分别取数，比较其大小，将较小者放入Lc中，一直进行下去，直到其中一个顺序表La或Lb中的数取完为止。
3）把未取完的数再依次取出放入Lc中即可。
以下面两个顺序表为例，如图2-78所示，演示合并过程。
图2-78 有序顺序表La和Lb
完美图解
1）创建一个顺序表Lc，其长度为La和Lb的长度之和9。设置3个工作指针：i、j、k（其实是整型数）。其中，i和j分别指向La和Lb中当前待比较的元素，k指向Lc中待放置元素的位置，如图2-79所示。
图2-79 有序顺序表La、Lb和Lc
2）比较La.elem[i]和Lb.elem[j]，将较小的赋值给Lc.elem[k]，同时相应指针向后移动。如此反复，直到顺序表La或Lb中的数取完为止。
图2-80 有序顺序表合并过程1
图2-81 有序顺序表合并过程2
图2-82 有序顺序表合并过程3
图2-83 有序顺序表合并过程4
图2-84 有序顺序表合并过程5
图2-85 有序顺序表合并过程6
图2-86 有序顺序表合并过程7
3）把La中未取完的数依次取出，放入Lc中即可，如图2-87和图2-88所示。
图2-87 有序顺序表合并过程8
图2-88 有序顺序表合并过程9
现在已经完成了两个有序顺序表的合并过程，Lc即为La和Lb合并后的结果。
代码实现
void MergeSqlist(SqList La, SqList Lb, SqList &Lc) // 有序顺序表的合并
{
//已知有序顺序表La和Lb的元素按值非递减排列
//La和Lb合并得到新的有序顺序表Lc，Lc的元素也按值非递减排列
int i,j,k;
i=j=k=0;
Lc.length=La.length+Lb.length; //新表长度为待合并两表的长度之和
Lc.elem=new int[Lc.length]; //为合并后的新表分配一段空间
while (i<La.length&&j<Lb.length) //两个表都非空
{
if(La.elem[i]<=Lb.elem[j] ) //依次取出两表中较小值放入Lc表中
Lc.elem[k++]=La.elem[i++];
else
Lc.elem[k++]=Lb.elem[j++];
}
while(i<La.length) //La有剩余，依次将La的剩余元素放入Lc表的尾部
Lc.elem[k++]=La.elem[i++];
while(j<Lb.length) //Lb有剩余，依次将Lb的剩余元素放入Lc表的尾部
Lc.elem[k++]=Lb.elem[j++];
}算法复杂度分析
合并操作需要将La和Lb中的每一个元素取出放入Lc中，如果La和Lb的长度分别为m、n，那么合并操作时间复杂度为O(m+n)，空间复杂度也为O(m+n)。
题目：将两个有序（非递减）单链表La和Lb合并为一个新的有序（非递减）单链表。
解题思路
链表合并不需要再创建空间，只需要“穿针引线”，把两个单链表中的节点按非递减的顺序串联起来即可。
注意：单链表的头指针不可以移动，一旦头指针丢失，就找不到该单链表了，因此需要辅助指针。
以下面两个单链表为例，如图2-89所示，演示合并过程。
图2-89 有序单链表La和Lb
完美图解
1）初始化。设置3个辅助指针p、q、r，p和q分别指向La和Lb链表的当前比较位置，新链表头指针Lc指向La，当作合并后的头节点。r指向Lc的当前最后一个节点，利用r指针“穿针引线”，如图2-90所示。
图2-90 有序单链表合并过程1
2）穿针引线。比较元素大小，将较小元素用r指针串起来。
图2-91 有序单链表合并过程2
串联操作分为3步。
r->next=q; //把q节点的地址赋值给r的next指针域，即r的next指针指向q
r=q; //r指针指向Lc的当前尾节点
q=q->next; //q指针向后移动，等待处理下一个节点串联之后如图2-92所示。
图2-92 有序单链表合并过程3
图2-93 有序单链表合并过程4
图2-94 有序单链表合并过程5
图2-95 有序单链表合并过程6
图2-96 有序单链表合并过程7
图2-97 有序单链表合并过程8
图2-98 有序单链表合并过程9
3）串联剩余部分。p指针不为空，用r指针将p串连起来，即r->next=p;。注意这里只是把这个指针连上即可，剩余的节点不需要再处理。释放Lb节点空间，即delete Lb。两个有序链表的合并结果如图2-99所示。
图2-99 有序单链表合并过程10
代码实现
void mergelinklist(LinkList La, LinkList Lb, LinkList &Lc)
{
LinkList p,q,r;
p=La->next; //p指向La的第一个数据元素节点
q=Lb->next; //q指向Lb的第一个数据元素节点
Lc=La; //Lc指向La的头节点
r=Lc; //r指向新链表Lc的尾部
while(p&&q)
{
if(p->data<=q->data) //把p指向的节点串起来
{
r->next=p;
r=p;
p=p->next;
}
else //把q指向的节点串起来
{
r->next=q;
r=q;
q=q->next;
}
}
//如果p不空，则把p后面剩余节点链接起来，即r->next=p;，否则r->next=q;
r->next=p?p:q; //相当于if(p) r->next=p; else r->next=q;
delete Lb;
}算法复杂度分析
链表合并不需要再创建空间，只需要穿针引线，把两个单链表中的节点按非递减的顺序串联起来即可。因此在最坏的情况下，需要串联每一个节点，如果La和Lb的长度分别为m、n时间复杂度为O(m+n)，空间复杂度为O(1)。
题目：将带有头节点的单链表就地逆置。即元素的顺序逆转，而辅助空间复杂度为O(1)。
解题思路
充分利用原有的存储空间，通过修改指针实现单链表的就地逆置。还记得吗？头插法创建单链表得到的序列正好是逆序，那么我们就利用头插法建表的思路，实现就地逆置。
下面以单链表为例，如图2-100所示，演示单链表就地逆置的过程。
图2-100 单链表
注意：在修改指针之前，一定要用一个辅助指针记录断点，否则后面这一部分就会遗失，再也找不到了。
完美图解
1）首先用p指针指向第一个元素节点，然后将头节点的next域置空。
记录第一个节点：p=L->next;。头节点的next域置空：L->next=NULL，如图2-101所示。
图2-101 单链表就地逆置过程1
2）将p节点用头插法插入链表L中，插入之前用q指针记录断点，如图2-102所示。
图2-102 单链表就地逆置过程2
记录断点：q=p->next; // q指向p的下一个节点，记录断点
头插法操作：p->next=L->next; //将L的下一个节点地址赋值给p的next域
L->next=p; //将p节点地址赋值给L的next域
指针后移：p=q; //p指向q指针后移后，如图2-103所示。
图2-103 单链表就地逆置过程3
3）将p节点用尾插法插入链表L中，插入之前用q指针记录断点，如图2-104所示。
图2-104 单链表就地逆置过程4
记录断点：q=p->next; // q指向p的下一个节点，记录断点
头插法操作：p->next=L->next; //将L的下一个节点地址赋值给p的next域
L->next=p; //将p节点地址赋值给L的next域
指针后移：p=q; //p指向q指针后移后，如图2-105所示。
图2-105 单链表就地逆置过程5
4）将p节点用头插法插入链表L中，插入之前用q指针记录断点，如图2-106所示。
图2-106 单链表就地逆置过程6
记录断点：q=p->next; //q指向p的下一个节点，记录断点
头插法操作：p->next=L->next; //将L的下一个节点地址赋值给p的next域
L->next=p; //将p节点地址赋值给L的next域
指针后移：p=q; //p指向q指针后移后，如图2-107所示。
图2-107 单链表就地逆置过程7
5）将p节点用尾插法插入链表L中，如图2-108所示。
图2-108 单链表就地逆置过程8
记录断点：q=p->next; // q指向p的下一个节点，记录断点
头插法操作：p->next=L->next; //将L的下一个节点地址赋值给p的next域
L->next=p; //将p节点地址赋值给L的next域
指针后移：p=q; //p指向q指针后移后，如图2-109所示。
图2-109 单链表就地逆置过程9
6）p指针为空，算法停止，单链表就地逆置完毕。
代码实现
void reverselinklist(LinkList &L)
{
LinkList p,q;
p=L->next; //p指向L的第一个元素
L->next=NULL; //头节点的next域置空
while(p)
{
q=p->next;//q指向p的下一个节点，记录断点
p->next=L->next; //头插法，将L的下一个节点地址赋值给p的next域
L->next=p; //将p节点地址赋值给L的next域
p=q;//指针后移，p指向q
}
}算法复杂度分析
算法对单链表进行了一趟扫描，如果L的长度为n，则时间复杂度为O(n)，没有使用其他辅助空间，只是几个辅助指针变量，因此空间复杂度为O(1)。
题目：带有头节点的单链表L，设计一个尽可能高效的算法求L中的中间节点。
解题思路
此类题型可以使用快慢指针来解决。一个快指针，一个慢指针，快指针走两步，慢指针走一步。当快指针指向结尾的时候，慢指针刚好指向中间节点。
完美图解
放置两个小青蛙，一个跳得远，一次走两块石头；一个跳得近，一次走一块石头。当快青蛙走到终点时，慢青蛙正好走到中间。
1）第1次，快青蛙走到2，慢青蛙走到1，如图2-110所示。
图2-110 查找中间节点过程1
2）第2次，快青蛙走到4，慢青蛙走到2，如图2-111所示。
图2-111 查找中间节点过程2
3）第3次，快青蛙走到6，慢青蛙走到3，如图2-112所示。
图2-112 查找中间节点过程3
链表访问完毕，慢青蛙正好在中间位置。
如果是奇数个节点会怎么样？读者可以试试看。
代码实现
LinkList findmiddle(LinkList L)
{
LinkList p,q;
p=L; //p为快指针，初始时指向L
q=L; //q为慢指针，初始时指向L
while(p!=NULL&&p->next!=NULL)
{
p=p->next->next;//p为快指针一次走两步
q=q->next; //q为慢指针一次走一步
}
return q;//返回中间节点指针
}算法复杂度分析
算法对单链表进行了一趟扫描，如果L的长度为n，则时间复杂度为O(n)，没有使用其他辅助空间，只是几个辅助指针变量，因此空间复杂度为O(1)。
思考：如何在单链表中查找倒数第k个节点？
仍然可以使用快慢指针，慢指针不要动，快指针先走k−1步，然后两个指针一起以同样的速度走。当快指针走到终点时，慢指针正好停留在倒数第k个节点，为什么呢？
因为它们之间的距离始终保持k−1。
完美图解
例如，找倒数第4个节点。
1）初始时快慢指针都指向第1个数据元素节点，如图2-113所示。
图2-113 查找倒数第k个节点过程1
2）第1步：慢指针不要动，快指针先走3步，如图2-114所示。
图2-114 查找倒数第k个节点过程2
3）第2步：快慢指针一起走，快指针走到5，慢指针走到2，如图2-115所示。
图2-115 查找倒数第k个节点过程3
4）第3步：快慢指针一起走，快指针走到6，慢指针走到3，如图2-116所示。
图2-116 查找倒数第k个节点过程4
链表访问完毕，慢青蛙正好在倒数第4个位置。
代码实现
LinkList findk(LinkList L,int k)
{
LinkList p,q;
p=L->next; //p为快指针，初始时指向第一个数据元素节点
q=L->next; //q为慢指针，初始时指向第一个数据元素节点
while(p->next!=NULL)
{
if(--k<=0) //k减到0时，慢指针开始走
q=q->next; //q为慢指针
p=p->next; //p为快指针，先走k-1步
}
if(k>0)
return NULL;
else
return q;//返回中间节点指针
}算法复杂度分析
算法对单链表进行了一趟扫描，如果L的长度为n，则时间复杂度为O(n)，没有使用其他辅助空间，只是几个辅助指针变量，因此空间复杂度为O(1)。
用快慢指针还可以解决很多问题，例如判断链表是否有环，判断两个链表是否相交等。
题目：用单链表保存m个整数，节点的结构为(data,next)，且|data|n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的节点，仅保留第一次出现的节点而删除其余绝对值相等的节点。
解题思路
本题数据大小有范围限制，因此可以设置一个辅助数组记录该数据是否已出现，如果已出现，则删除；如果未出现，则标记。一趟扫描即可完成。
完美图解
假设m=6，n=10，链表如图2-117所示。
图2-117 单链表
1）设置一个辅助数组flag[]，因为n为正整数，不包括0，所以0空间不用。需要分配n+1个辅助空间，初始化时都为0，表示这些数还未出现过，如图2-118所示。
图2-118 辅助数组（一）
设置p指针指向头节点，检查第一个数据元素是否已出现过。令x=abs(p->next->data)，如果已出现过（flag[x]=1），则删除该节点；如果该节点数据元素未出现过，则标记flag[x]=1，p指针向后移动，直到处理完毕，如图2-119所示。
图2-119 单链表（初始状态）
2）abs(p->next->data)=5，读取flag[5]=0，说明该节点数据元素未出现过，标记flag[5]=1，p指针向后移动。辅助数组和链表状态如图2-120和图2-121所示。
图2-120 辅助数组（二）
图2-121 删除重复元素过程1
3）abs(p->next->data)=2，读取flag[2]=0，说明该节点数据元素未出现过，标记flag[2]=1，p指针向后移动。辅助数组和链表状态如图2-122和图2-123所示。
图2-122 辅助数组（三）
图2-123 删除重复元素过程2
4）abs(p->next->data)=5，读取flag[5]=1，说明该节点数据元素已出现过，删除该节点。链表状态如图2-124所示。
图2-124 删除重复元素过程3
q=p->next; //q指向p的下一个节点
p->next=q->next; //跳过重复元素，即删除
delete q; //释放空间删除节点后链表状态如图2-125所示。
图2-125 删除重复元素过程4
5）abs(p->next->data)=4，读取flag[4]=0，说明该节点数据元素未出现过，标记flag[4]=1，p指针向后移动。辅助数组和链表状态如图2-126和图2-127所示。
图2-126 辅助数组（四）
图2-127 删除重复元素过程5
6）abs(p->next->data)=2，读取flag[2]=1，说明该节点数据元素已出现过，删除该节点。链表状态如图2-128所示。
图2-128 删除重复元素过程6
q=p->next;p->next=q->next; delete q; //删除重复元素，删除后释放空间删除节点后链表状态如图2-129所示。
图2-129 删除重复元素过程7
7）abs(p->next->data)=10，读取flag[10]=0，说明该节点数据元素未出现过，标记令flag[10]=1，p指针向后移动。辅助数组和链表状态如图2-130和图2-131所示。
图2-130 辅助数组（五）
图2-131 删除重复元素过程8
8）此时p->next为空，算法停止。对于链表中data的绝对值相等的节点，仅保留第一次出现的节点而删除其余绝对值相等的节点。
代码实现
void Deleterep(LinkList &L)//删除重复元素
{
LinkList p,q;
int x;
int *flag=new int[n+1]; //定义flag数组，分配n+1个空间，0空间未用
for(int i=0;i<n+1;i++) //初始化
flag[i]=0;
p=L; //指向头节点
while(p->next!=NULL)
{
x=abs(p->next->data);
if(flag[x]==0)//未出现过
{
flag[x]=1; //标记出现过
p=p->next; //指针后移
}
else
{
q=p->next; //q指向p的下一个节点
p->next=q->next;//删除重复元素
delete q; //释放空间
}
}
delete []flag;
}算法复杂度分析
根据题意，单链表中保存m个绝对值小于等于n的整数，因此链表元素个数为m，算法从头到尾扫描了一遍链表，时间复杂度为O(m)；采用了辅助数组flag[]，因为n为正整数，不包括0，所以0空间不用，需要分配n+1个辅助空间，因此空间时间复杂度为O(n)。
本章从数据结构三要素（逻辑结构、存储结构、运算）出发，讲解线性表，具体内容如图2-132所示。
图2-132 线性表主要内容
顺序表和链表各有所长，其优缺点和适用情况如表2-1所示。
表2-1 顺序表和链表的比较
| 顺序表 | 链表 | ||
|---|---|---|---|
| 空间 | 存储空间 | 预先分配，会导致空间闲置或溢出现象 | 动态分配，不会出现空间闲置或溢出现象 |
| 存储密度 | 不需要额外的存储开销表达逻辑关系，存储密度等于1 | 需要借助指针存储表达逻辑关系，存储密度小于1 | |
| 时间 | 存取元素 | 随机存取，时间复杂度为O(1) | 顺序存取，时间复杂度为O(n) |
| 插入删除 | 平均移动约表中一半元素，时间复杂度为O(n) | 不需移动元素，确定插入删除位置后，时间复杂度为O(1) | |
| 适用情况 | ① 表长变化不大，且能事先确定变化的范围 ② 很少进行插入或删除操作，经常按元素序号访问数据元素 |
① 长度变化较大 ② 频繁进行插入或删除操作 |
|
顺序表解题时需要注意几个问题。
1）位序和下标差1，第i个元素的下标为i−1。
2）移动元素时，特别注意先后顺序，以免覆盖。
例如，在第i个位置插入一个元素e，需要从需要从最后一个元素开始，后移一位……直到把第i个元素也后移一位，然后把e放入第i个位置，如图2-133所示。
图2-133 顺序表（插入）
例如，删除第i个元素，从i+1个元素开始前移……直到把第n个元素也前移一位，即可完成删除操作，如图2-134所示。
图2-134 删除元素
3）交换元素、有序合并需要借助辅助空间。
链表的题目变化多端，但只要熟练掌握其精髓，无论其如何变化，都可以驾轻就熟。链表需要注意的几个问题如下。
（1）赋值语句两端的含义
对于有关指针的赋值语句，很多读者表示不理解，容易混淆。等号的右侧是节点的地址，等号的左侧是节点的指针域，如图2-135所示。
图2-135 赋值解释
在图2-135中，假设q节点的下一个节点地址为“1013”，该地址存储在q->next里面，因此等号右侧的q->next的值为“1013”。把该地址赋值给p节点的next指针域，把原来的值“2046”覆盖掉，这样p->next也为“1013”，相当于把q节点跳过去了。赋值之后，如图2-136所示。
图2-136 赋值之后
（2）修改指针的顺序
修改指针的顺序原则：先修改没有指针标记的那一端，如图2-137所示。
图2-137 指针修改（有顺序）
如果要插入节点的两端都有标记，例如，再定义一个指针q指向L节点后面的节点，那么先修改哪个指针都无所谓了，如图2-138所示。
图2-138 指针修改（无顺序）
（3）建立链表的两种方法：头插法、尾插法。头插法是逆序建表，尾插法是正序建表。
（4）链表逆置、归并不需要额外空间，属于就地操作。
（5）快慢指针法：快慢指针可以解决很多问题，如链表中间节点、倒数第k个节点、判断链表是否有环、环的起点、公共部分的起点等。
