详情
本书旨在讲解数据结构和算法的核心知识。本书主要内容包括线性表、栈、队列、串、数组、广义表、树、图、查找算法、排序算法、递推算法、递归算法、枚举算法、贪心算法、回溯算法、数值算法和实用算法等。本书适合计算机专业的学生、软件开发专业人员等阅读。
书名：数据结构与算法详解
ISBN：978-7-115-54666-1
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
编 著 陈 锐 张志锋 马军霞 等
责任编辑 谢晓芳
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
本书旨在讲解数据结构和算法的核心知识。本书主要内容包括线性表、栈、队列、串、数组、广义表、树、图、查找算法、排序算法、递推算法、递归算法、枚举算法、贪心算法、回溯算法、数值算法和实用算法等。本书适合计算机专业的学生、软件开发专业人员等阅读。
写作本书的目的是对数据结构与算法知识做一个梳理，并对数据结构和算法方面的各种实例进行归类，同时提供相应实例的代码，为越来越多需要学习这方面知识的读者提供帮助。面对与日俱增的数据，运行效率成为制约软件系统的关键因素之一，数据结构和算法显得尤为重要。因此，具备扎实的数据结构与算法基础是计算机相关从业人员的必备技能。
编写本书的过程也是作者重新学习的过程，作者在调试程序上花费了不少时间，但是每一次都有很大收获。因为在调试程序的过程中总会遇到一些新的问题，在解决这些问题时，作者对算法有了更深入的理解，同时提高了程序调试水平。
在数据结构和算法中，栈的初始化部分为什么要用二级指针，其他函数却用一级指针呢？虽然很多读者已经了解了一级指针和二级指针，但是并没有深入理解它们之间的区别，没有考虑过在什么地方应该使用一级指针，什么地方应该使用二级指针，以及为什么要将指针作为函数参数进行传递。要搞懂这些问题，需要认真思考，因为要返回一个地址，所以就用了二级指针。
本书不仅讲解了数据结构和算法的基础知识，还融合了数据结构和算法方面的大量实例，这些实例都经过精心调试，能够保证算法的正确性。调试程序是一件花费时间的事情，但是只有亲自动手调试，才能深刻理解算法思想，发现错误和不足。在调试程序的过程中，自身水平会得到提高。因此，建议读者多动手，上机调试程序，即使把程序“敲”一遍，也会比不动手效果好。
本书的许多实例选自部分高校的考研题目。这些考研题目非常具有代表性，它们涵盖了数据结构的各个方面，同时考查了数据结构的基础知识和算法设计思想。
参与编写本书的有郑州轻工业大学的陈锐、张志锋、马军霞、崔建涛、李璞、王博、赵晓君。其中，陈锐编写了第1～4章，张志锋编写了第9～11章，马军霞编写了第12～15章，崔建涛编写了第6～7章，李璞编写了第5章，王博编写了第8章，赵晓君编写了第16～18章。
由于水平有限，书中难免存在一些不足之处，希望读者通过邮箱235668080@qq.com与作者联系。
本书涵盖数据结构和算法等内容，可作为计算机专业人士的工具书，适合C/C++程序员阅读，也可作为数据结构和算法初学者的参考用书。
本书分为两部分。第一部分涵盖线性表、栈、队列、串、数组、广义表、树、图等内容，第二部分涵盖查找算法、排序算法、递推算法、递归算法、枚举算法、贪心算法、回溯算法等内容。
本书选取的实例具有代表性、趣味性和实用性。第一部分不仅注重基础知识的讲解，还给出了基本运算的实现，其中大部分的实例来自高校的考研题目，注重理论与实践相结合。第二部分的不少实例极具趣味性，例如，“求n个数中的最大者”“和式分解”“大牛生小牛问题”巧妙地利用递归算法来实现。在算法实例的选取上，本书还注重实用性，尽量将实例与实际工作、生活相结合，例如，加油点问题、找零钱问题、阿拉伯数字与中文大写金额的转换等。
此外，为了帮助读者熟悉C语言的调试技术，本书最后通过具体的实例讲解如何用Visual C++ 6.0调试程序。
本书具有以下特点。
本书涵盖大量数据结构和算法的实现代码，读者在使用本书的过程中，若需要用到对应功能，可以直接调用，不需要重新编写代码。这些已经实现的算法的代码可帮助读者理解相关知识点。要想真正学好数据结构与算法，还需要多编写代码，或者至少要理解每段代码的功能。
可以将本书作为一本教材从头到尾阅读，也可以将本书作为一本工具书，需要时查阅。
本书的算法都是使用C/C++实现的，但是并不涉及面向对象的知识，仅仅考虑到输入和输出的方便。有的代码中用cin代替了scanf函数，用cout代替了printf函数。
在学习数据结构和算法之前，需要读者熟练掌握C/C++，包括基本语法、指针、函数及结构体。在学习数据结构和算法的过程中，读者也可以提高使用C/C++的水平。
在阅读本书的过程中，既需要理解算法思想，又需要上机实践，在计算机上验证算法思想和编写的程序是否正确。对于难以理解的算法，特别是递归、树和图的算法，可以根据程序在纸上画一遍流程图，不要怕麻烦，这不是浪费时间。在学习数据结构与算法的过程中，一定不能偷懒，不能只动脑不动手。除了理解算法思想外，还要实现每个算法。只有实现算法，才能真正解决日常生活中的实际问题，将所学知识应用于实际生活中。我们学数据结构与算法的目的有两个。一是在理论层次上学会算法设计，二是要用C/C++/Java/Python等语言实现算法，正确运行程序。设计的算法正确不正确不是想象出来的，而是通过编译器检验出来的。即使一个人设计算法的能力很强，也不能保证他写出的程序不需要修改就可以直接在计算机上成功运行。因此，设计算法然后在计算机上运行是非常重要的，只有这样才能真正学好数据结构和算法。
在写作本书和之前学习数据结构与算法的过程中，与读者一样，作者也经常遇到这样或那样的问题，但是现在越来越少了。因为接触多了，每遇到一个问题，就想办法去解决它。其实，C语言、数据结构和算法并没有那么复杂。记得在写本书第4章时，需要通过键盘输入两个字符串，但是直接使用C语言提供的gets函数或C++的cin输入流，会遇到莫名其妙的问题：当输入一个字符串完毕后按Enter键，就会出现跳过第二个输入提示的问题。有时因为第一个字符串中包含了空格，有时因为连续用了几个gets函数。既然直接使用gets函数或cin输入流都不好，那么我们可以尝试使用最原始的getchar函数，把它与while语句结合起来使用，以输入一个字符串，这个字符串可以包含空格。假设我们以回车符作为结束标志，代码如下。
while((ch=getchar())!='\n')
{
str[i++]=ch;
}这样就巧妙地解决了上面的问题。
本书中，特别是在第一部分，我们把基本运算单独放在一个.h文件中，以便对代码进行重用。每章的算法调用基本比较模式化，经常会使用一些输入或输出的功能，因此我们就可以把这些比较常用的功能写成一个函数，避免重复编码，这就是软件工程的思想，今后大家编写程序时也要养成这个习惯。
如何快速找出程序中出错的位置和原因，以便程序正确运行？针对程序调试问题，应该首先选择一个比较适合自己的开发工具，比如Visual C++就是一个很成熟的开发工具。对于语法错误，编译器会直接定位错误行，并给出相应的错误提示；对于逻辑错误和运行时错误，对可能出现问题的代码段设置断点，跟踪、查看变量在程序运行过程中的变化情况，针对输入的数据进行分析，就能很快找出问题。
虽然本书展示了所有实例的完整代码，但是建议读者在计算机上“敲”代码，在“敲”代码的过程中去体会算法设计思想。你也许会输入错误，也许会为一个小错误苦恼半天，但经过多次检查和调试，终将找到错误的原因并且解决问题，直到程序正常运行。只有经历了痛苦、挣扎、喜悦的反复过程，你才可能成为一名经验丰富的C/C++程序员。计算机是一门科学，也是一门技术，算法思想虽然很重要，但再优秀的算法也需要验证，只有验证了，才知道它是否可行，在验证的过程中才能发现问题。
在本书的编写过程中，作者得到了很多老师的大力支持与帮助，在此表示感谢。感谢人民邮电出版社的各位编辑，在他们的努力下本书才得以顺利出版。
在本书的编写过程中，许多热心的朋友提出了有用的反馈意见。感谢网友puppypyb。感谢中国科学院大学的胡英鹏，中国科学技术大学的王启，华中科技大学的杨梨花，西安电子科技大学的杜坚，西安交通大学的郝昊天，华东师范大学的牛颖楠，南京航空航天大学的韩琦文，南京理工大学的邓裕彬，北京工业大学的潘姝妤，电子科技大学的丁亮、吕鑫垚，上海海事大学的左伟康，福州大学的李川，湘潭大学的王乾，天津职业技术师范大学的董春妹，桂林电子科技大学的曹礼，郑州大学的张杨、张冬冬，成都理工大学的张良，西华师范大学的刘富腾，衡水学院的杨帅，重庆电子工程职业学院的冯博，湖南女子学院的李奇，湖北汽车工业学院的李兴海，黄淮学院的于景波，九江学院的樊美林，信阳师范学院的周亚林，云南大学的袁宏磊，广东技术师范大学的欧阳镇，江苏省扬州中学的张佑杰，浙江工业大学的陈文邦，北京邮电大学世纪学院的昂超，兴义民族师范学院的鲜一峰，赶集网的康钦谋，山东趣维网络科技有限公司的刘晓倩，中国航空计算技术研究所的王泉，中兴通讯股份有限公司的杨柯，华为技术有限公司的卢春俊，云南昆船设计研究院的夏翔，大唐电信科技股份有限公司的张天广，腾讯科技有限公司的杨凡，浪潮集团的郭鹏，三星集团的欧晓哲。很多网友也提出了宝贵建议，这里不再一一列举，祝他们学业有成，事业进步。
作 者
本书由异步社区出品，社区（https://www.epubit.com/）为你提供相关资源和后续服务。
作者和编辑尽最大努力来确保书中内容的准确性，但难免会存在疏漏。欢迎你将发现的问题反馈给我们，帮助我们提升图书的质量。
当你发现错误时，请登录异步社区，按书名搜索，进入本书页面，单击“提交勘误”，输入勘误信息，单击“提交”按钮即可（见下图）。本书的作者和编辑会对你提交的勘误进行审核，确认并接受后，你将获赠异步社区的100积分。积分可用于在异步社区兑换优惠券、样书或奖品。
我们的联系邮箱是contact@epubit.com.cn。
如果你对本书有任何疑问或建议，请你发邮件给我们，并请在邮件标题中注明本书书名，以便我们更高效地做出反馈。
如果你有兴趣出版图书、录制教学视频，或者参与图书翻译、技术审校等工作，可以发邮件给我们；有意出版图书的作者也可以到异步社区在线投稿（直接访问www.epubit.com/contribute即可）。
如果你所在学校、培训机构或企业想批量购买本书或异步社区出版的其他图书，也可以发邮件给我们。
如果你在网上发现有针对异步社区出品图书的各种形式的盗版行为，包括对图书全部或部分内容的非授权传播，请你将怀疑有侵权行为的链接发邮件给我们。你的这一举动是对作者权益的保护，也是我们持续为你提供有价值的内容的动力之源。
“异步社区”是人民邮电出版社旗下IT专业图书社区，致力于出版精品IT图书和相关学习产品，为作译者提供优质出版服务。异步社区创办于2015年8月，提供大量精品IT图书和电子书，以及高品质技术文章和视频课程。更多详情请访问异步社区官网https://www.epubit.com。
“异步图书”是由异步社区编辑团队策划出版的精品IT专业图书的品牌，依托于人民邮电出版社近几十年的计算机图书出版积累和专业编辑团队，相关图书在封面上印有异步图书的LOGO。异步图书的出版领域包括软件开发、大数据、人工智能、测试、前端、网络技术等。
异步社区
微信服务号
数据结构主要研究数据的逻辑结构和存储结构，以及对数据的各种操作，是深入学习算法设计与分析、操作系统、编译原理、软件工程等的重要基础。随着计算机应用领域的不断扩展，非数值计算问题已成为计算机应用领域处理的主要问题之一，简单的数据结构已经不能满足需要，无论是系统软件设计还是应用软件设计，均涉及复杂的数据结构处理。好的算法是建立在解决实际问题过程中对数据结构的描述上的。因此，掌握扎实的数据结构的基本知识和技能对于今后的专业学习和软件开发是十分必要的。该部分主要介绍线性表、栈、队列、串、数组、广义表、树和图等方面的知识和应用。
在学习数据结构和算法方面的内容之前，本章先介绍有关数据结构的基本概念，帮助读者为今后的学习扫清障碍。
本节主要介绍有关数据结构的一些基本概念和术语，以便读者对数据结构有一个初步的认识。
数据（data）是能被计算机识别并能被输入计算机中进行处理的符号的集合。换言之，数据就是计算机化的信息。早期的计算机主要应用于数值计算，数据量小且结构简单，数据只包括整型、实型和布尔型，仅能用于算术运算与逻辑运算。那时的程序设计人员把主要精力放在程序设计的技巧上，并不重视计算机中数据的组织。
随着计算机软件、硬件的发展与应用领域的不断扩大，计算机应用领域也发生了战略性转移，非数值运算处理所占的比例越来越大，现在几乎达到90%以上，数据的概念被大大扩展了。数据不仅包括整型、实型等数值类型，还包括字符、声音、图像、视频等非数值类型。多种信息通过编码被归到数据的范畴，大量复杂的非数值数据需要处理，数据的组织显得越来越重要。例如，王鹏的身高是172cm，王鹏是关于一个人姓名的描述数据，172cm是关于身高的描述数据。一张照片是图像数据，一部电影是视频数据。
数据元素（data element）是数据的基本单位，在计算机程序中通常被作为一个整体考虑和处理。一个数据元素可由若干个数据项（data item）组成，数据项是数据不可分割的最小单位。例如，一个学校的教职工基本情况表包括工号、姓名、性别、籍贯、所在院系、出生年月及职称等数据项。教职工基本情况如表0.1所示。表中的一行就是一个数据元素，也称为一条记录。
表0.1 教职工基本情况
| 工号 |
姓名 |
性别 |
籍贯 |
所在院系 |
职称 |
|---|---|---|---|---|---|
| 2006002 |
李四 |
男 |
河南 |
计算机学院 |
教授 |
| 2013026 |
赵六 |
女 |
北京 |
软件学院 |
副教授 |
| 2015028 |
张三 |
男 |
陕西 |
软件学院 |
副教授 |
| 2019016 |
王五 |
男 |
山东 |
软件学院 |
讲师 |
数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。例如，对于正整数来说，数据对象是集合N={1, 2, 3,…}；对于字母字符数据来说，数据对象是集合C={‘A’,‘B’,‘C’, …, ‘a’, ‘b’, ‘c’,…}。
数据结构（data structure）即数据的组织形式，它是相互之间存在一种或多种特定关系的数据元素的集合。在现实世界中，任何事物都是有内在联系的，而不是孤立存在的。同样，在计算机中，数据元素不是孤立的、杂乱无序的，而是具有内在联系的。例如，表0.1所示的教职工基本情况是一种表结构，图0.1所示的学校的组织机构是一种层次结构，图0.2所示的城市之间的交通路线是一种图结构。
图0.1 学校的组织机构
图0.2 城市之间的交通路线
数据类型（data type）用来刻画一组性质相同的数据及对其所能进行的操作。数据类型是按照数据取值范围的不同进行划分的。在高级语言中，每个变量、常量和表达式都有各自的取值范围，数据类型就说明了变量、常量和表达式的取值范围和所能进行的操作。例如，C语言中规定了字符类型所占空间是8位，这样就确定了它的取值范围，同时也定义了在其范围内可以进行赋值运算、比较运算等操作。
在C语言中，按照取值范围的不同，数据类型还可以分为原子类型和结构类型两类。原子类型是不可以再分解的基本类型，包括整型、实型、字符型等；结构类型是由若干个类型组合而成的，是可以再分解的。例如，整型数组是由若干整型数据组成的，它们的类型都是相同的。
数据结构的主要任务就是通过分析数据对象的结构特征，包括逻辑结构及数据对象之间的关系，将逻辑结构表示成计算机可实现的存储结构，从而便于计算机处理。
数据的逻辑结构（logical structure）是指数据对象中数据元素之间的逻辑关系。数据元素之间存在不同的逻辑关系，主要分为以下4种结构类型。
集合结构。结构中的数据元素除了同属于一个集合外，数据元素之间没有其他关系。这就像数学中的自然数集合，集合中的所有元素都属于该集合，除此之外，没有其他特性。例如，数学中的正整数集合{1,2,3,5,6,9}，集合中的元素除了均属于正整数外，元素之间没有其他关系。数据结构中的集合类似于数学中的集合。集合结构如图0.3所示。
图0.3 集合结构
线性结构。结构中的数据元素之间是一对一的关系。线性结构如图0.4所示。数据元素之间有一种先后的次序关系，a、b、c是一个线性表，其中，a是b的“前驱”，b是a的“后继”。
图0.4 线性结构
树形结构。结构中的数据元素之间存在一种一对多的层次关系，树形结构如图0.5所示。这就像大学的组织结构图，大学下面是教学的院系、处、所及一些教研室。
图0.5 树形结构
图结构。结构中的数据元素是多对多的关系，图0.6所示为一个图结构。城市之间的交通路线图就是多对多的关系，假设a、b、c、d、e、f、g是7个城市，城市a和城市b、e、f之间都存在一条直达路线，城市b和a、c、f之间也存在一条直达路线。
图0.6 图结构
存储结构（storage structure）也称为物理结构（physical structure），指的是数据的逻辑结构在计算机中的存储形式。数据的存储结构应能正确反映数据元素之间的逻辑关系。
数据元素的存储结构形式通常有两种——顺序存储结构和链式存储结构。顺序存储结构是把数据元素存放在一组地址连续的存储单元里，其数据元素间的逻辑关系和物理关系是一致的。顺序存储结构如图0.7所示。链式存储结构是把数据元素存放在任意的存储单元里，这些存储单元可以是连续的，也可以是不连续的，数据元素的物理关系并不能反映其逻辑关系，因此需要借助指针来表示数据元素之间的逻辑关系。链式存储结构如图0.8所示。
图0.7 顺序存储结构
图0.8 链式存储结构
数据的逻辑结构和存储结构是密切相关的，一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于所采用的存储结构。对于顺序存储结构，可用C语言中的一维数组类型来描述；对于链式存储结构，可用C语言中的自引用类型即结构体来描述。
为了在计算机上实现某种操作，需要把处理的对象描述成计算机能识别的形式，即一定形式的数据类型，并定义其上的一组操作。
抽象数据类型（Abstract Data Type，ADT）是描述具有某种逻辑关系的数学模型，并定义在该数学模型上进行的一组操作。抽象数据类型描述的是一组逻辑上的特性，与数据在计算机内部的表示无关。
抽象数据类型其实是根据数据结构的研究对象进行定义的，包含了数据对象、数据对象间的关系及其基本运算。本书把抽象数据类型分为两个部分来描述，即数据对象集合和基本操作集合。其中，数据对象集合部分描述了数据对象的定义及数据对象中元素之间的关系，基本操作集合部分描述了数据对象的运算。数据对象和数据关系的定义可采用数学符号和自然语言描述，基本操作的定义格式如下。
基本操作名（参数表）：初始条件和操作结果描述。例如，队列的抽象数据类型描述如下。
队列的数据对象集合为{a1, a2,…, an}，每个数据元素都具有相同的数据类型。
队列中的数据元素之间是一对一的关系。除第一个元素a1外，每一个元素有且只有一个直接前驱元素；除最后一个元素an外，每一个元素有且只有一个直接后继元素。
（1）InitQueue(&Q)：初始化操作，建立一个空队列Q。这就像日常生活中医院新增一个挂号窗口，前来看病的人就可以排队在这里挂号。
（2）QueueEmpty(Q)：若Q为空队列，返回1；否则，返回0。这就像判断挂号窗口前是否还有人在排队挂号。
（3）EnQueue(&Q,e)：把元素e插入队列Q的队尾。这就像新来挂号的人都要到队列的最后排队挂号。
（4）DeQueue(&Q,&e)：删除Q的队首元素，并用e返回其值。这就像排在最前面的人挂完号离开队列。
（5）Gethead(Q,&e)：用e返回Q的队首元素。这就像询问当前排队挂号的人是谁一样。
（6）ClearQueue(&Q)：将队列Q清空。这就像所有排队的人都挂完号离开队列。
在数据类型建立起来之后，就要对这些数据类型进行操作，建立起运算的集合即程序。运算策略的好坏直接决定着计算机程序运行效率的高低。
数据结构与算法关系密切，两者既有联系又有区别。数据结构与算法的关系可用一个公式描述，即程序=算法+数据结构。数据结构是算法实现的基础，算法要依赖于某种数据结构来实现。设计算法的实质就是对实际问题中需要处理的数据选择一种恰当的存储结构，并在选定的存储结构上描述解决问题的步骤。
数据结构与算法的区别在于数据结构关注的是数据的逻辑结构、存储结构以及基本操作，而算法更多的是关注如何在数据结构的基础上解决实际问题。算法是一种编程思想，数据结构则是这种思想的基础。
算法（algorithm）是特定问题的求解步骤的描述，在计算机中表现为有限的操作序列。操作序列包括了一组操作，其中的每一个操作都完成特定的功能。例如，求n个数中最大数的问题，其算法描述如下。
（1）定义一个变量max和一个数组a，分别用来存放最大数和n个数，并假定数组中第一个数最大，把第一个数赋给max。
max=a[0];（2）依次把数组a中其余的n−1个数与max进行比较，遇到较大的数时，将其赋给max。
for(i=1;i<n;i++)
{if(max<a[i])
max=a[i];}最后，max就是n个数中的最大数。
算法具有以下五大特性。
（1）有穷性。有穷性指的是算法在执行有限的步骤之后，会自动结束而不会出现无限循环，并且每一个步骤都在可接受的时间内完成。
（2）确定性。算法的每一个步骤都具有确定的含义，不会出现二义性。算法在一定条件下只有一条执行路径，也就是相同的输入只能有唯一的输出。
（3）可行性。算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。
（4）输入。算法具有零个或多个输入。
（5）输出。算法至少有一个或多个输出。可以直接输出，也可以返回一个或多个值。
算法的描述方式有多种，如使用自然语言、伪代码（或称为类语言）、程序流程图及程序设计语言（如C语言）等。其中，自然语言描述中可以用汉字或英文等文字描述；伪代码类似于程序，但是不能直接运行；程序流程图的优点是直观，但是不易被直接转化为可运行的程序；采用C、C++、Java等程序设计语言描述算法，很容易把算法转换为可运行的程序。
为了方便读者学习和上机操作，本书所有算法均采用C语言描述，所有程序均可直接在计算机上运行。
一个好的算法往往可以使程序尽可能快地运行，往往以算法效率和存储空间作为衡量算法性能的重要依据。
一个好的算法应该实现以下4个目标。
算法的正确性是指算法至少应该包括对于输入、输出和处理的无歧义性描述，能正确反映需求，且能够得到问题的正确答案。
通常算法的正确性应包括以下4个层次。
（1）算法对应的程序没有语法错误。
（2）对于几组输入数据均能得到满足规格要求的输出。
（3）对于精心选择的、典型的、苛刻的几组输入数据均能得到满足规格要求的输出。
（4）对于一切合法的输入都能得到满足规格要求的输出。
对于这4层算法正确性的含义，达到第4层的正确性是极困难的，所有不同输入数据的数量大得惊人，逐一验证的方法是不现实的。一般情况下，我们把前3个层次作为衡量一个算法是否正确的标准。
可读性好有助于人们对算法的理解，晦涩难懂的程序往往隐含不易被发现的错误，难以调试和修改。
鲁棒性是指当输入数据不合法时，算法也应该能做出反应或进行处理，而不会产生异常或莫名其妙的输出结果。例如，求一元二次方程ax2+bx+c=0(a≠0)的根的算法，需要考虑多种情况，先判断b2−4ac的值的正负，如果其值为正数，则该方程有两个不同的实根；如果其值为负数，则表明该方程无实根；如果其值为0，则表明该方程只有一个实根。如果a=0，则该方程又变成了一元一次方程。此时，若b=0，还要处理除数为0的情况。如果输入的a、b、c不是数值型，还要提示用户输入错误。
效率指的是算法的执行时间。对于同一个问题，如果有多个算法能够解决，执行时间越短的算法效率越高，执行时间越长的算法效率越低。存储量指算法在执行过程中需要的最大存储空间。效率和存储量都与问题的规模有关，如求100个人的平均分与求1000个人的平均分所花的执行时间和存储空间显然有一定的差别。设计算法时应尽量选择高效率和低存储量的算法。
算法执行时间需通过依据该算法编制的程序在计算机上运行时所耗费的时间来度量，而一个算法在计算机上的执行时间通常用时间复杂度进行度量。
在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，通过分析T(n)随n的变化情况来确定T(n)的数量级。算法的时间复杂度也就是算法的时间量度，记作T(n)=O(f(n))。
O(f(n))表示随问题规模n的增大，算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度（asymptotic time complexity），简称时间复杂度。其中，f(n)是问题规模n的某个函数。
一般情况下，随着n的增大，T(n)的增长率较低的算法为最优的算法。例如，请分别对以下3个程序段中的基本操作k=k+1的时间复杂度进行分析。
k=k+1;
for（i=1;i<=n;i++）
k=k+1;
for（i=1;i<=n;i++）
for（j=1;j<=n;j++）
k=k+1;程序段1的时间复杂度为O(1)，称为常量阶；程序段2的时间复杂度为O(n)，称为线性阶；程序段3的时间复杂度为O(n2)，称为平方阶。
一些常见的时间复杂度量级从小到大依次是O(1)<O(log2n)<O(n)<O(n2)<O(n3)<O(2n)<O(n!)。
时间复杂度是衡量算法性能的重要指标之一。一般情况下，具有指数级的时间复杂度的算法是当n足够小时才使用的算法。具有常量阶、线性阶、对数阶、平方阶和立方阶的时间复杂度的算法是常用的算法。一些常见函数的增长率如图0.9所示。
图0.9 常见函数的增长率
一般情况下，算法的时间复杂度只需要考虑问题规模n的增长率或阶数。例如以下程序段。
for(i=2;i<=n;i++)
for(j=2;j<=i-1;j++)
{
k++;
a[i][j]=x;
}一条语句的执行时间等于该条语句的重复执行次数和执行该语句一次所需时间的乘积，其中该语句的重复执行次数称为语句频度（frequency count）。
语句k++的执行次数关于n的增长率为n2，它是语句频度(n−1)(n−2)/2中增长最快的项。
在某些情况下，算法中基本操作的重复执行次数除了依赖数据集大小，还依赖数据集初始值状态。例如，以下的冒泡排序算法中基本操作的重复执行次数就依赖初始数据的排列状态。
void BubbleSort(int a[],int n)
{
int i,j,t;
change=TRUE;
for(i=1;i<=n-1&&change;i++)
{
change=FALSE;
for(j=1;j<=n-i;j++)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
change=TRUE;
}
}
}交换相邻两个整数为该算法中的基本操作。当数组a中的初始序列从小到大有序排列时，基本操作的执行次数为0；当数组中初始序列从大到小排列时，基本操作的执行次数为n(n−1)/2。对这类算法的分析有两种方法：一种方法是计算所有情况的平均值，这种方法计算出的时间复杂度称为平均时间复杂度；另一种方法是计算最坏情况下的时间复杂度，这种方法计算出的时间复杂度称为最坏时间复杂度。若数组a中初始输入数据出现n! 种排列情况的概率相等，则冒泡排序的平均时间复杂度为T(n)=O(n2)。
然而，在很多情况下，若各种输入数据出现的概率难以确定，算法的平均复杂度也就难以确定。因此，更常用的办法是讨论算法在最坏情况下的时间复杂度，即分析最坏情况以估算算法执行时间的上界。例如，对于上面的冒泡排序，当数组a中初始序列从大到小有序排列时，则冒泡排序算法在最坏情况下的时间复杂度为T(n)=O(n2)。讨论时间复杂度时，若没有特殊说明，一般都指的是最坏情况下的时间复杂度。
空间复杂度（space complexity）是算法所需存储空间的量度，记作S(n)=O(f(n))。其中，n为问题的规模，f(n)为算法所占存储空间。一般情况下，一个程序在计算机上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据进行操作的存储单元。若输入数据所占存储空间只取决于问题本身，和算法无关，那么只需要分析该算法在实现时所需的辅助存储空间元即可。若算法执行时所需的辅助存储空间相对输入数据量而言是个常数，则称此算法在原地工作，空间复杂度为O(1)。
线性表是一种最基本、最常用的数据结构，表中的元素呈线性关系。线性表、栈、队列和串都属于线性结构，线性结构的特点是：除了第一个元素没有直接前驱元素，最后一个元素没有直接后继元素外，其他元素有唯一的前驱元素和唯一的后继元素。
【定义】
线性表是由n个类型相同的数据元素组成的有限序列，记为 (a1, a2,…, ai−1, ai, ai+1,…, an)。线性表的数据元素之间存在着序偶关系，即数据元素之间具有一定的次序。在线性表中，数据元素ai−1位于ai的前面，ai又在ai+1的前面，我们把ai−1称为ai的直接前驱元素，ai称为ai+1的直接前驱元素。ai称为ai−1的直接后继元素，ai+1称为ai的直接后继元素。
线性表 (a1, a2,a3, a4, a5, a6)的逻辑结构如图1.1所示。
图1.1 线性表的逻辑结构
线性表按照存储方式可以分为顺序存储和链式存储。线性表的顺序存储指的是将线性表中的各个元素依次存放在一组地址连续的存储单元中。
线性表中第i个元素的存储位置与第一个元素a1的存储位置满足以下关系。
LOC(ai)=LOC(a1)+(i−1)m
其中，m表示一个元素占用的存储单元数量，第一个元素的位置LOC(a1)称为起始地址或基地址。
线性表的这种表示称为线性表的顺序存储结构或顺序映像。通常，将以这种方式存储的线性表称为顺序表。
【特点】
顺序表具有以下特征：逻辑上相邻的元素，在物理上也是相邻的。只要确定了第一个元素的起始位置，线性表中的任意元素都可以随机存取。因此，线性表的顺序存储结构是一种随机存取的存储结构。
【存储结构】
#define ListSize 100
typedef struct
{
DataType list[ListSize];
int length;
}SeqList;其中，DataType表示数据元素类型，list用于存储线性表中的数据元素，length表示线性表中数据元素的个数，SeqList是结构类型名。
如果要定义一个顺序表，代码如下。
SeqList L;如果要定义一个指向顺序表的指针，代码如下。
SeqList *L;【基本运算】
（1）初始化线性表。
void InitList(SeqList *L)
/*初始化线性表*/
{
L->length=0; /*把线性表的长度设置为0*/
}（2）判断线性表是否为空。
int ListEmpty(SeqList L)
/*判断线性表是否为空*/
{
if(L.length==0)
return 1;
else
return 0;
}（3）按序号查找。
int GetElem(SeqList L,int i,DataType *e)
/*查找线性表中第i个元素*/
{
if(i<1||i>L.length)/*在查找第i个元素之前，判断该序号是否合法*/
return -1;
*e=L.list[i-1]; /*将第i个元素的值赋值给e*/
return 1;
}（4）按内容查找。
int LocateElem(SeqList L,DataType e)
/*查找线性表中元素值为e的元素*/
{
int i;
for(i=0;i<L.length;i++)
if(L.list[i]==e)
return i+1;
return 0;
}（5）插入操作。要在顺序表中的第i个位置插入元素e，首先将第i个位置以后的元素依次向后移动1个位置，然后把元素e插入第i个位置。
例如，要在顺序表(3,15,49,20,23,44,18,36)的第5个元素之前插入一个元素22，需要先将序号为8、7、6、5的元素依次向后移动一个位置，然后在第5个位置插入元素22，顺序表就变成了(3,15,49,20,22,23,44,18,36），如图1.2所示。
图1.2 在顺序表中插入元素22的过程
int InsertList(SeqList *L,int i,DataType e)
/*在顺序表的第i个位置插入元素e*/
{
int j;
if(i<1||i>L->length+1)/*在插入元素前，判断插入位置是否合法*/
{
printf("插入位置i不合法！\n");
return -1;
}
else if(L->length>=ListSize) /*在插入元素前，判断顺序表是否已满*/
{
printf("顺序表已满，不能插入元素。\n");
return 0;
}
else
{
for(j=L->length;j>=i;j--) /*将第i个位置以后的元素依次后移*/
L->list[j]=L->list[j-1];
L->list[i-1]=e; /*把元素插入第i个位置*/
L->length=L->length+1; /*将顺序表的表长增1*/
return 1;
}
}插入元素的位置i的合法范围应该是1
iL−>length+1。当i=1时，插入位置在第一个元素之前；当i=L−>length+1时，插入位置在最后一个元素之后。当插入位置是i=L−>length+1时，不需要移动元素；当插入位置是i=0时，则需移动所有元素。
（6）删除第i个元素。在进行删除操作时，先判断顺序表是否为空。若非空，接着判断序号是否合法。若非空且合法，则将要删除的元素赋给e，并把该元素删除，将表长减1。
例如，要删除顺序表(3,15,49,20,22,23,44,18,36)的第4个元素，则需要将序号为5、6、7、8、9的元素依次向前移动一个位置，这样就删除了第4个元素，最后将表长减1，如图1.3所示。
图1.3 在顺序表中删除元素20的过程
int DeleteList(SeqList *L,int i,DataType *e)
{
int j;
if(L->length<=0)
{
printf("顺序表已空，不能进行删除!\n");
return 0;
}
else if(i<1||i>L->length)
{
printf("删除位置不合适!\n");
return -1;
}
else
{
*e=L->list[i-1];
for(j=i;j<=L->length-1;j++)
L->list[j-1]=L->list[j];
L->length=L->length-1;
return 1;
}
}被删除元素的位置i的合法范围应该是1iL−>length。当i=1时，表示要删除第一个元素，对应C语言数组中的第0个元素；当i=L−>length时，要删除的是最后一个元素。
（7）求线性表的长度。
int ListLength(SeqList L)
{
return L.length;
}（8）清空顺序表。
void ClearList(SeqList *L)
{
L->length=0;
}
如何使用顺序表的基本运算？
将以上顺序表存储结构的定义及基本运算保存在SeqList.h文件中，在使用时可通过#include"SeqList.h"使用这些基本运算。
问题描述
顺序表A和顺序表B的元素都是非递减排列的，利用顺序表的基本运算，将它们合并成一个顺序表C，要求C也是非递减排列的。例如，若 A=(8,17,17,25,29)，B=(3,9,21,21,26,57)，则C=(3,8,9,17,17,21,21,25,26,29,57)。
【分析】
顺序表C是一个空表，首先取出顺序表A和B中的元素，并将这两个顺序表中的元素进行比较。如果A中的元素m1大于B中的元素n1，则将B中的元素n1插入C中，继续取出B中下一个元素n2并与A中元素m1比较；如果A中的元素m1小于或等于B中的元素n1，则将A中的元素m1插入C中，继续取出A中的下一个元素m2与B中的元素n1比较。依次比较，直到一个表中元素比较完毕，将另一个表中的剩余元素插入C中。
第1章\实例1-01.c
/********************************************
*实例说明：合并两个有序的线性表为一个有序的线性表
*********************************************/
#include<stdio.h> /*包含输入/输出头文件*/
#define ListSize 200
typedef int DataType; /*元素类型定义为整型*/
#include"SeqList.h" /*包含顺序表的基本运算*/
void MergeList(SeqList A,SeqList B,SeqList *C);
/*合并顺序表A和B中元素的函数声明*/
void main()
{
int i,flag;
DataType a[]={8,17,17,25,29};
DataType b[]={3,9,21,21,26,57};
DataType e;
SeqList A,B,C;
InitList(&A);
InitList(&B);
InitList(&C);
for(i=1;i<=sizeof(a)/sizeof(a[0]);i++)/*将数组a中的元素插入顺序表A中*/
{
if(InsertList(&A,i,a[i-1])==0)
{
printf("位置不合法");
return;
}
}
for(i=1;i<=sizeof(b)/sizeof(b[0]);i++)/*将数组b中的元素插入顺序表B中*/
{
if(InsertList(&B,i,b[i-1])==0)
{
printf("位置不合法");
return;
}
}
printf("顺序表A中的元素：\n"); /*输出顺序表A中的每个元素*/
for(i=1;i<=A.length;i++)
{
flag=GetElem(A,i,&e); /*返回顺序表A中的每个元素到e中*/
if(flag==1)
printf("%4d",e);
}
printf("\n");
printf("顺序表B中的元素：\n"); /*输出顺序表B中的每个元素*/
for(i=1;i<=B.length;i++)
{
flag=GetElem(B,i,&e);
if(flag==1)
printf("%4d",e);
}
printf("\n");
printf("将顺序表A和B中的元素合并得到C：\n");
MergeList(A,B,&C); /*将顺序表A和B中的元素合并*/
for(i=1;i<=C.length;i++) /*显示合并后顺序表C中的所有元素*/
{
flag=GetElem(C,i,&e);
if(flag==1)
printf("%4d",e);
}
printf("\n");
}
void MergeList(SeqList A,SeqList B,SeqList *C)
/*合并顺序表A和B的元素到顺序表C中，并保持元素非递减排序*/
{
int i,j,k;
DataType e1,e2;
i=1;j=1;k=1;
while(i<=A.length&&j<=B.length)
{
GetElem(A,i,&e1);
GetElem(B,j,&e2);
if(e1<=e2)
{
InsertList(C,k,e1); /*将较小的一个元素插入顺序表C中*/
i++; /*往后移动一个位置，准备比较下一个元素*/
k++;
}
else
{
InsertList(C,k,e2);
j++;
k++;
}
}
while(i<=A.length) /*如果顺序表A中元素还有剩余，顺序表B中已经没有元素*/
{
GetElem(A,i,&e1);
InsertList(C,k,e1);
i++;
k++;
}
while(j<=B.length) /*如果顺序表B中元素还有剩余，顺序表A中已经没有元素*/
{
GetElem(B,j,&e2);
InsertList(C,k,e2);
j++;
k++;
}
C->length=A.length+B.length; /* 顺序表C的长度等于顺序表A和顺序表B的长度的和*/
}运行结果如图1.4所示。
图1.4 运行结果
如何调用顺序表的头文件？
在程序中，需要调用头文件SeqList.h时，因为其中包含数据类型DataType和表示顺序表长度的宏名ListSize，所以在包含命令#include"SeqList.h"前首先需要给宏名赋值，并进行类型定义，其语句次序如下。
#define ListSize 200
typedef int DataType;
#include"SeqList.h"
问题描述
假设线性表LA和LB分别表示两个集合A和B，利用线性表的基本运算，实现新的集合，即扩大线性表LA，将存在于线性表LB中且不存在于LA中的元素插入LA中。
【分析】
为了依次从线性表LB中取出每个元素，并将该元素依次与线性表LA中的元素进行比较，可调用LocateElem(SeqList L,DataType e)。若LA中不存在该元素，则将该元素插入LA中。
第1章\实例1-02.c
/********************************************
*实例说明：将两个无序的线性表元素合并（相同元素只保留一个）
*********************************************/
#include<stdio.h>
#define ListSize 200
typedef int DataType;
#include"SeqList.h"
void UnionAB(SeqList *A,SeqList B);
void main()
{
int i,flag;
DataType e;
DataType a[]={81,32,61,12,39,25};
DataType b[]={12,44,39,16,28,6,61,76};
SeqList LA,LB;
InitList(&LA);
InitList(&LB);
for(i=0;i<sizeof(a)/sizeof(a[0]);i++) /*将数组a中的元素插入LA中*/
{
if(InsertList(&LA,i+1,a[i])==0)
{
printf("位置不合法");
return;
}
}
for(i=0;i<sizeof(b)/sizeof(b[0]);i++) /*将数组a中的元素插入表LB中*/
{
if(InsertList(&LB,i+1,b[i])==0)
{
printf("位置不合法");
return;
}
}
printf("顺序表LA中的元素：\n");
for(i=1;i<=LA.length;i++) /*输出顺序表LA中的每个元素*/
{
flag=GetElem(LA,i,&e); /*返回顺序表LA中的每个元素并放入e中*/
if(flag==1)
printf("%4d",e);
}
printf("\n");
printf("顺序表LB中的元素：\n");
for(i=1;i<=LB.length;i++) /*输出顺序表LB中的每个元素*/
{
flag=GetElem(LB,i,&e); /*返回顺序表LB中的每个元素并放入e中*/
if(flag==1)
printf("%4d",e);
}
printf("\n");
printf("将在顺序表LB中但不在顺序表LA中的元素插入LA中：\n");
UnionAB(&LA,LB); /*将在顺序表LB中但不在顺序表LA中的元素插入顺序表LA中*/
for(i=1;i<=LA.length;i++) /*输出顺序表LA中的所有元素*/
{
flag=GetElem(LA,i,&e);
if(flag==1)
printf("%4d",e);
}
printf("\n");
}
void UnionAB(SeqList *LA,SeqList LB)
/*删除LA中出现LB的元素的函数实现*/
{
int i,flag,pos;
DataType e;
for(i=1;i<=LB.length;i++)
{
flag=GetElem(LB,i,&e);
if(flag==1)
{
pos=LocateElem(*LA,e); /*在顺序表LA中查找和顺序表LB中取出的元素e相等的元素*/
if(!pos)
InsertList(LA,LA->length+1,e);/*若找到该元素，将其插入顺序表LA中*/
}
}
}运行结果如图1.5所示。
图1.5 运行结果
问题描述
利用线性表的基本运算实现，如果在线性表A中出现的元素，在线性表B中也出现，则将A中该元素删除。
【分析】
其实这是求两个线性表的差集，即A−B。依次检查线性表B中的每一个元素，如果在线性表A中也出现，则在A中删除该元素。
第1章\实例1-03.c
/********************************************
*实例说明：求两个线性表的差集
*********************************************/
#include<stdio.h>
#define ListSize 200
typedef int DataType;
#include"SeqList.h"
void DelElem(SeqList *A,SeqList B);
void main()
{
int i,j,flag;
DataType e;
SeqList A,B;
InitList(&A);
InitList(&B);
for(i=1;i<=10;i++)
{
if(InsertList(&A,i,i*2+10)==0)
{
printf("位置不合法");
return;
}
}
for(i=1,j=10;i<=8;j=j+2,i++) /*插入顺序表B中8个元素*/
{
if(InsertList(&B,i,j+i*2)==0)
{
printf("位置不合法");
return;
}
}
printf("顺序表A中的元素：\n"); /*输出顺序表A中的每个元素*/
for(i=1;i<=A.length;i++)
{
flag=GetElem(A,i,&e); /*返回顺序表A中的每个元素并放入e中*/
if(flag==1)
printf("%4d",e);
}
printf("\n");
printf("顺序表B中的元素：\n"); /*输出顺序表B中的每个元素*/
for(i=1;i<=B.length;i++)
{
flag=GetElem(B,i,&e); /*返回顺序表B中的每个元素并放入e中*/
if(flag==1)
printf("%4d",e);
}
printf("\n");
printf("将在A中出现的B的元素删除后,A中的元素(即A-B)：\n");
DelElem(&A,B); /*将在顺序表A中出现的顺序表B的元素删除*/
for(i=1;i<=A.length;i++) /*显示删除后顺序表A中所有元素*/
{
flag=GetElem(A,i,&e);
if(flag==1)
printf("%4d",e);
}
printf("\n");
}
void DelElem(SeqList *A,SeqList B)
/*求A-B，即删除顺序表A中出现的B的元素*/
{
int i,flag,pos;
DataType e;
for(i=1;i<=B.length;i++)
{
flag=GetElem(B,i,&e);
if(flag==1)
{
pos=LocateElem(*A,e); /*在顺序表A中查找元素e*/
if(pos>0) /*如果该元素存在*/
DeleteList(A,pos,&e); /*则将其从顺序表A中删除*/
}
}
}运行结果如图1.6所示。
图1.6 运行结果
问题描述
实现一个算法，把一个顺序表分解成两个部分，使顺序表中小于或等于0的元素位于左边，大于0的元素位于右边。要求不占用额外的存储空间。例如，顺序表(−12,3,−6,−10,20,−7,9,−20)经过分解调整后变为(−12,−20,−6,−10,−7,20,9,3)。
【算法思想】
设置两个指示器i和j，分别扫描顺序表中的元素，i和j分别从顺序表的左边和右边开始扫描。如果i遇到小于或等于0的元素，略过不处理，继续向前扫描；如果遇到大于0的元素，暂停扫描。如果j遇到大于0的元素，略过不处理，继续向前扫描；如果遇到小于或等于0的元素，暂停扫描。如果i和j都停下来，则交换i和j指向的元素。重复执行直到i≥j为止。
第1章\实例1-04.c
/********************************************
*实例说明：分解顺序表，使左边的元素小于或等于0，右边的大于0
*********************************************/
#include<stdio.h>
#define ListSize 200
typedef int DataType;
#include"SeqList.h"
void SplitSeqList(SeqList *L);
void main()
{
int i,flag,n;
DataType e;
SeqList L;
int a[]={88,-9,-28,19,-31,22,-50,62,-76};
InitList(&L); /*初始化顺序表L*/
n=sizeof(a)/sizeof(a[0]);
for(i=1;i<=n;i++) /*将数组a的元素插入顺序表L中*/
{
if(InsertList(&L,i,a[i-1])==0)
{
printf("位置不合法");
return;
}
}
printf("顺序表L中的元素：\n"); /*输出顺序表L中的每个元素*/
for(i=1;i<=L.length;i++)
{
flag=GetElem(L,i,&e); /*返回顺序表L中的每个元素并放入e中*/
if(flag==1)
printf("%4d",e);
}
printf("\n");
printf("顺序表L调整后(左边元素小于或等于0,右边元素大于0):\n");
SplitSeqList(&L); /*调整顺序表*/
for(i=1;i<=L.length;i++) /*输出调整后顺序表L中的所有元素*/
{
flag=GetElem(L,i,&e);
if(flag==1)
printf("%4d",e);
}
printf("\n");
}
void SplitSeqList(SeqList *L)
/*将顺序表L分成两个部分*/
{
int i,j; /*定义两个指示器i和j*/
DataType e;
i=0,j=(*L).length-1; /*指示器i与j分别指示顺序表的左边和右边元素*/
while(i<j)
{
while(L->list[i]<=0)
i++;
while(L->list[j]>0)
j--;
if(i<j)
{
e=L->list[i];
L->list[i]=L->list[j];
L->list[j]=e;
}
}
}运行结果如图1.7所示。
图1.7 运行结果
问题描述
试设计一种表示任意长度的整数的数据结构，并设计计算任意给定的两个整数之和的算法。
【分析】
C语言提供的整数范围为−231～231−1，超出这个范围的整数该如何存储呢？可以利用数组来存储，数组中的每一个元素存放一个数字，数组A和B分别存储两个整数，在将两个整数相加时，从数组低位到高位依次将对应位相加，如果和大于9，则将高位加上进位1，并将和减去10后存储到当前位。
第1章\实例1-05.c
/********************************************
*实例说明：求两个任意长度的整数之和
*********************************************/
#include<stdio.h>
#define MaxLen 100
typedef int sqlist[MaxLen];
int input(sqlist A)
{
int i;
for(i=0;i<MaxLen;i++)
A[i]=0;
printf("输入一个正整数的各位(输入-1结束)\n");
i=0;
while(1)
{
scanf("%d",&A[i]);
if(A[i]<0)
break;
i++;
}
return i;
}
void output(sqlist A,int low,int high)
{
int i;
for(i=low;i<high;i++)
printf("%d",A[i]);
printf("\n");
}
void move(sqlist A,int na)
{
int i;
for(i=0;i<na;i++)
A[MaxLen-i-1]=A[na-i-1];
}
int add(sqlist *A,int na,sqlist B,int nb)
{
int nc,i,j,length=0;
if(na>nb)
nc=na;
else
nc=nb;
move(*A,na);
move(B,nb);
for(i=MaxLen-1;i>=MaxLen-nc;i--)
{
j=(*A)[i]+B[i];
if(j>9)/*和大于9*/
{
(*A)[i-1]=(*A)[i-1]+1; /*高位加上1*/
(*A)[i]=j-10; /*和减去10后存储到当前位*/
}
else
(*A)[i]=j;
if(i==MaxLen-nc) /*处理最高位*/
{
if(j>9)
{
(*A)[i-1]=1;
length=nc+1;
}
else
length=nc;
}
}
return length;
}
void main()
{
sqlist A,B;
int na,nb,nc;
na=input(A);
nb=input(B);
printf("整数A:");
output(A,0,na);
printf("整数B:");
output(B,0,nb);
nc=add(&A,na,B,nb);
printf("相加后的结果:");
output(A,MaxLen-nc,MaxLen);
}运行结果如图1.8所示。
图1.8 运行结果
问题描述
设有一个长度为L（L
1）的升序序列S，位于序列中位置为的元素称为S的中位数。例如，如果有序列S1={21, 23, 25, 27, 29}，则25为S1的中位数。对于两个元素序列，其中位数为两个元素序列中元素合并在一起后的中位数，如果S2={12, 14, 16, 18, 30}，则S1和S2的中位数是21。要求设计一个时间和空间尽可能高效的算法，求两个升序序列A和B的中位数。
【分析】
这是某年全国考研计算机统考试题。为了设计一个尽可能高效的算法得到两个升序序列中的中位数，可通过不断缩小两个元素序列的长度，这样就可以减少运算次数。分别求两个升序序列A和B的中位数，记作mida和midb，求A和B的中位数的算法过程如下。
（1）若mida==midb，则mida或midb即为中位数。
（2）若mida<midb，则舍弃A中较小的一半，同时舍弃B中较大的一半，舍弃的元素个数必须相等。
（3）若mida>midb，则舍弃A中较大的一半和B中较小的一半，舍弃的元素个数必须相等。
令A和B中剩下的元素序列重复执行以上过程，直到两个序列均只剩下一个元素为止，其中较小者即为中位数。
第1章\实例1-06
/********************************************
*实例说明：求两个元素序列的中位数
*********************************************/
#include<stdio.h>
#define ListSize 200
typedef int DataType;
#include"SeqList.h"
int MidSeqList(SeqList A, SeqList B);
void DispList(SeqList L);
void main()
{
int i,n;
DataType mid;
SeqList A,B;
int a[]={21, 23, 25, 27, 29};
int b[]={12, 14, 16, 18, 30};
InitList(&A); /*初始化顺序表A*/
InitList(&B); /*初始化顺序表B*/
n=sizeof(a)/sizeof(a[0]);
for(i=1;i<=n;i++) /*将数组a的元素插入顺序表A中*/
if(InsertList(&A,i,a[i-1])==0)
{
printf("位置不合法");
return;
}
}
n=sizeof(b)/sizeof(b[0]);
for(i=1;i<=n;i++) /*将数组b的元素插入顺序表B中*/
{
if(InsertList(&B,i,b[i-1])==0)
{
printf("位置不合法");
return;
}
}
printf("顺序表A中的元素：\n");
DispList(A);
printf("\n");
printf("顺序表B中的元素：\n");
DispList(B);
printf("\n");
mid=MidSeqList(A,B); /*求A和B的中位数*/
printf("顺序表A和B中的中位数为%d\n",mid);
}
DataType MidSeqList(SeqList A, SeqList B)
/*求A和B中的中位数*/
{
int first1,first2,last1,last2,mid1,mid2; /*定义指示器*/
first1=first2=1; /*first1和first2分别指示顺序表A和B的最左端元素*/
last1=last2=A.length;/*last1和last2分别指示顺序表A和B的最右端元素*/
while(first1!=last1 || first2!=last2)
{
mid1=(first1+last1)/2;/*mid1指示顺序表A的中位数*/
mid2=(first2+last2)/2;/*mid2指示顺序表B的中位数*/
if(A.list[mid1-1]==B.list[mid2-1])/*若两个序列的中位数相等*/
return A.list[mid1];
else if(A.list[mid1-1]<B.list[mid2-1])/*若A的中位数小于B的中位数*/
{/*则取A的右端元素和B的左端元素组成新的序列*/
if((first1+last1)%2==0)/*若元素个数为奇数*/
{
first1=mid1;
last2=mid2;
}
else
{
first1=mid1+1;
last2=mid2;
}
}
else /*若A的中位数大于B的中位数*/
{/*则取B的右端元素和A的左端元素组成新的序列*/
if((first2+last2)%2==0)
{
last1=mid1;
first2=mid2;
}
else
{
last1=mid1;
first2=mid2+1;
}
}
}
return A.list[first1-1] < B.list[first2-1] ? A.list[first1-1] : B.list[first2-1];
}
void DispList(SeqList L)
/*输出顺序表L中的每个元素*/
{
int i,flag;
DataType e;
for(i=1;i<=L.length;i++)
{
flag=GetElem(L,i,&e);
if(flag==1)
printf("%4d",e);
}
}运行结果如图1.9所示。
图1.9 运行结果
【定义】
所谓线性表的链式存储，是采用一组任意的存储单元存放线性表的元素。这组存储单元可以是连续的，也可以是不连续的。为了表示元素ai与其直接后继ai+1的逻辑关系，还需要存储一个指示其直接后继元素的信息（即直接后继元素的地址）。这两部分构成的存储结构称为节点（node）。即节点包括两个域——数据域和指针域。节点结构如图1.10所示。
图1.10 节点结构
通过指针域将线性表中的n个节点按照逻辑顺序链接在一起就构成了单链表。
一般情况下，我们只关心单链表中节点的逻辑顺序，而不关心它的实际存储位置。通常用箭头表示指针，把单链表表示成通过箭头链接起来的序列。线性表(Kang,Geng,Guan,Chen,Zhou,Hua,Feng)的单链表的逻辑状态如图1.11所示。
图1.11 单链表的逻辑状态
为了便于实现插入、删除等操作，在单链表的第一个节点之前增加一个节点，称为头节点。头节点的数据域可以存放如单链表的长度等信息，头节点的指针域存放第一个节点的地址信息，使其指向第一个节点。带头节点的单链表如图1.12所示。
图1.12 带头节点的单链表
若带头节点的单链表为空链表，则头节点的指针域为“空”，如图1.13所示。
图1.13 带头节点的单链表
【存储结构】
单链表的存储结构用C语言描述如下。
typedef struct Node
{
DataType data;
struct Node *next;
}ListNode,*LinkList;其中，ListNode是单链表的节点类型，LinkList是指向单链表节点的指针类型。如果有以下定义，则L被定义为指向单链表的指针类型。
LinkList L;以上语句相当于以下定义。
ListNode *L;【基本运算】
（1）初始化单链表。
void InitList(LinkList *head)
/*初始化单链表*/
{
if((*head=(LinkList)malloc(sizeof(ListNode)))==NULL)
exit(-1);
(*head)->next=NULL;
}（2）判断单链表是否为空。若单链表为空，返回1；否则，返回0。
int ListEmpty(LinkList head)
/*判断单链表是否为空*/
{
if(head->next==NULL)
return 1;
else
return 0;
}（3）按序号查找操作。
ListNode *Get(LinkList head,int i)
/*按序号查找单链表中的第i个节点。若查找成功，则返回该节点的指针；否则，返回NULL*/
{
ListNode *p;
int j;
if(ListEmpty(head))
return NULL;
if(i<1)
return NULL;
j=0;
p=head;
while(p->next!=NULL&&j<i)
{
p=p->next;
j++;
}
if(j==i)
return p;
else
return NULL;
}（4）查找元素值与e相等的节点。
ListNode *LocateElem(LinkList head,DataType e)
/*按内容查找单链表中元素值与e相等的节点。若查找成功，则返回对应节点的节点指针；否则，返回NULL*/
{
ListNode *p;
p=head->next;
while(p)
{
if(p->data!=e)
p=p->next;
else
break;
}
return p;
}（5）定位操作，确定节点在单链表中的序号。从头指针出发，依次访问每个节点，并将节点的元素值与e比较。如果相等，返回该序号；如果没有与e相等的元素值，返回0。
int LocatePos(LinkList head,DataType e)
/*查找线性表中元素值与e相等的节点*/
{
ListNode *p;
int i;
if(ListEmpty(head)) /*查找第i个节点前，判断链表是否为空*/
return 0;
p=head->next; /*指针p指向第一个节点*/
i=1;
while(p)
{
if(p->data==e) /*找到与e相等的元素值*/
return i; /*返回该节点序号*/
else
{
p=p->next;
i++;
}
}
if(!p) /*若没有找到与e相等的元素值*/
return 0; /*返回0 */
}（6）在第i个位置插入元素e。
先来看如何在单链表中插入一个节点。假设存储元素e的节点为p指向的节点，要将p指向的节点插入pre和pre−>next之间，无须移动节点，只需要改变p和pre指针的指向即可。先把*pre的直接后继节点变成*p的直接后继节点，然后把*p变成*pre的直接后继节点，如图1.14所示，代码如下。
p->next=pre->next;
pre->next=p;图1.14 在*pre节点之后插入*p节点
注意：不能颠倒插入节点操作的顺序。如果先执行pre−>next=p，后执行p−>next= pre−>next，则第一条代码就会覆盖pre−>next的地址，pre−>next的地址就变成了p的地址，执行p−>next=pre−>next就等于执行p−>next=p，这样pre−>next就会与上级断开链接，如图1.15所示。
图1.15 颠倒插入操作顺序后，*(pre->next)节点与上一个节点断开链接
在单链表的第i个位置插入一个新元素e的步骤如下。
① 在单链表中找到其直接前驱节点，即第i−1个节点，并由指针pre指向该节点，如图1.16所示。
图1.16 找到第i个节点的直接前驱节点
② 申请一个新节点空间，由p指向该节点，将e赋值给p所指向节点的数据域。
③ 修改*p和*pre节点的指针域，如图1.17所示。
图1.17 将新节点插入第i个位置
在单链表中插入元素e的算法实现如下。
int InsertList(LinkList head,int i,DataType e)
/*在单链表中第i个位置插入一个节点，节点存放元素e*/
{
ListNode *pre,*p; /*定义第i个节点的前驱节点指针pre，指针p指向新生成的节点*/
int j;
pre=head; /*指针p指向头节点*/
j=0;
while(pre->next!=NULL&&j<i-1)/*找到第i－1个节点，即第i个节点的前驱节点*/
{
pre=pre->next;
j++;
}
if(j!=i-1) /*如果没找到，则说明插入位置错误*/
{
printf("插入位置错误！");
return 0;
}
/*新生成一个节点，并将e赋值给该节点的数据域*/
if((p=(ListNode*)malloc(sizeof(ListNode)))==NULL)
exit(-1);
p->data=e;
/*插入节点操作*/
p->next=pre->next;
pre->next=p;
return 1;
}（7）删除第i个节点。
先来观察删除单链表中的第i个节点是如何操作的。假设p指向第i个节点，要将*p节点删除，只需将它的直接前驱节点的指针（即pre的指针域）直接指向它的直接后继节点即可，如图1.18所示。
图1.18 删除*pre节点的直接后继节点
删除单链表中第i个节点的步骤如下。
① 找到第i个节点的直接前驱节点（即第i−1个节点）和第i个节点，分别用pre和p指向这两个节点，如图1.19所示。
图1.19 找到第（i−1）个节点和第i个节点
② 将*p节点的数据域赋给e，并删除第i个节点，即pre−>next=p−>next。
③ 释放*p的节点空间。删除过程如图1.20所示。
图1.20 删除第i个节点
删除第i个节点的算法实现如下。
int DeleteList(LinkList head,int i,DataType *e)
/*删除单链表中的第i个位置的节点。删除成功返回1，失败返回0*/
{
ListNode *pre,*p;
int j;
pre=head;
j=0;
while(pre->next!=NULL&&pre->next->next!=NULL&&j<i-1)
/*判断是否找到前驱节点*/
{
pre=pre->next;
j++;
}
if(j!=i-1) /*如果没找到要删除的节点的位置，则说明删除位置有误*/
{
printf("删除位置有误");
return 0;
}
p=pre->next;
*e=p->data;
pre->next=p->next;
free(p); /*释放p指向的节点*/
return 1;
}
注意： 在查找第（i−1）个节点时，要注意不可遗漏判断条件pre−>next−>next!=NULL，以确保第i个节点非空。如果没有此判断条件，且pre指针指向单链表的最后一个节点，那么在执行循环后的 "p=pre−>next；*e=p−>data" 操作时，p指针指向的就是NULL指针域，这样就会产生致命错误。
（8）求表长操作。
int ListLength(LinkList head)
/*求表长操作*/
{
ListNode *p;
int count=0;
p=head;
while(p->next!=NULL)
{
p=p->next;
count++;
}
return count;
}（9）销毁链表操作。
void DestroyList(LinkList head)
/*销毁链表*/
{
ListNode *p,*q;
p=head;
while(p!=NULL)
{
q=p;
p=p->next;
free(q);
}
}以上基本运算存放在#include"LinkList.h"文件中，供其他函数在需要这些基本运算时调用。
问题描述
实现算法，将一个单链表逆置。所谓单链表的逆置，就是将一个单链表中的所有节点按照逆序存放。例如，一个单链表中有5个节点，节点中分别存放的数据是A、B、C、D、E，逆置后单链表中的节点数据次序是E、D、C、B、A，如图1.21所示。
图1.21 单链表逆置前后的状态
【分析】
将一个单链表逆置其实就是用头插法建立单链表。定义一个空链表，分别将原单链表中的第一个节点、第二个节点，……，第n个节点依次插入新单链表的头部，即插入的节点成为新单链表的第一个节点。例如，将单链表1逆置为单链表2的过程如图1.22（a）～（f）所示。
图1.22 单链表1逆置为单链表2的过程
从图1.22可以看出，依次将单链表1的每个节点插入单链表2的头部，就得到了一个单链表1的逆置单链表。
假设已经创建了一个带头节点的单链表，其中节点包含工号、姓名和籍贯等信息，如图1.23所示。
图1.23 带头节点的单链表
单链表逆置就是指依次取出单链表中的每个节点，用头插法建立新单链表的过程。初始时，有h−>next=NULL。然后从单链表中依次取出每个节点，将其插入新单链表的头部，这样就得到了一个逆置单链表。例如，将p指向的单链表的第一个节点插入h指向的空单链表的过程如图1.24（a）～（d）所示。
初始时，h指向头节点，将头节点的指针域设置为NULL，表示得到的逆置单链表为空，如图1.24（a）所示。然后准备将第一个节点插入该空单链表中，先让q指向原单链表的第一个节点，即将要插入新单链表的节点，p指向原单链表的第二个节点，表示原单链表的头指针，如图1.24（b）所示。接下来要将q指向的节点插入h指向的单链表中。先将q指向的节点的指针域指向h指向的下一个节点，即q−>next=h−>next，此时，h−>next=NULL，所以q的指针域为空，如图1.24（c）所示。最后让h的指针域指向q，即要插入的节点。这样h指向的单链表中就有了一个节点如图1.24（d）所示。
图1.24 将p指向的单链表的第一个节点插入h指向的空单链表的过程
接下来，将p指向的原单链表的第2个节点插入h指向的单链表中。先让q指向p，然后让p指向下一个节点以记录原节点的位置。按照以上方法将工号为“10902”的节点插入逆置单链表的过程如图1.25（a）和（b）所示。
图1.25 插入第2个节点的过程
按照以上方法，即可实现将单链表逆置。
第1章\实例1-07.c
/********************************************
*实例说明：将单链表逆置
*********************************************/
#include<stdio.h>
struct Node /*定义节点类型*/
{
long no;
char name[20];
char addr[30];
struct Node *next;
};
typedef struct Node ListNode;
ListNode *CreateList();
ListNode * ReverseList(ListNode *h);
void DispList(ListNode *h);
void main()
{
ListNode *head,*p;
head=CreateList();
DispList(head);
head=ReverseList(head);
DispList(head);
}
ListNode *CreateList()
{
ListNode *pre,*cur,*h;
int i,n;
h=NULL;
printf("输入节点个数：\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
cur=(ListNode *)malloc(sizeof(ListNode)); /*生成新节点*/
cur->next=NULL;
if(h==NULL)
h=cur;
else
pre->next=cur;
scanf("%d %s %s",&cur->no,cur->name,cur->addr); /*输出单链表的节点的数据*/
pre=cur; /*pre指向当前节点，即最后一个节点*/
}
return h; /*返回头指针*/
}
void DispList(ListNode *h)
{
ListNode *p=h;
printf("学号 姓名 地址\n");
while(p!=NULL)
{
printf("%d %s %s\n",p->no,p->name,p->addr);
p=p->next;
}
}
ListNode * ReverseList(ListNode *h)
/*将单链表逆置*/
{
ListNode *q,*p=h; /*p指向第一个节点*/
h=(ListNode*)malloc(sizeof(ListNode));
h->next=NULL;
while(p)
{
q=p;
p=p->next;
q->next=h->next;
h->next=q;
}
return h->next; /*返回单链表的第一个节点的指针*/
}运行结果如图1.26所示。
图1.26 运行结果
问题描述
利用单链表的基本运算求A−B。即如果单链表A中出现的元素，在B中也出现，则删除A中的该元素。例如，单链表A中的元素为(22,7,15,56,89,38,44,65,109,83），B中的元素为(15,9,22,89, 33,65,90,83），则执行A−B操作后，A中的元素为(7,56,38,44,109）。
【分析】
这是上海大学考研试题，下面是一个求两个集合A和B之差C=A−B的算法，即当且仅当e是A中的一个元素，但不是B中的一个元素时，e才是C中的一个元素。集合用有序单链表表示，先把集合A、B中的元素按递增顺序排列，C为空；操作完成后，A、B保持不变，C中元素按递增顺序排列。函数Append(last，e)把新节点元素e链接在由指针last指向的节点的后面，并返回新节点的地址。函数Difference(A，B)实现集合运算A−B，并返回表示结果集合C的单链表的头节点的地址。在执行A−B运算之前，用于表示结果集合的单链表中首先增加一个头节点，以方便新节点的添加。当A−B运算执行完毕后，再删除并释放表示结果集合的单链表的头节点。
第1章\实例1-08.c
/********************************************
*实例说明：求单链表的差集
*********************************************/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef int DataType;
#include"LinkList.h" /*包含单链表实现文件*/
void SortList(LinkList S);
ListNode *Append(ListNode *last,DataType e);
ListNode *Difference(ListNode *A,ListNode *B);
void main()
{
int i;
DataType a[]={22,7,15,56,89,38,44,65,109,83};
DataType b[]={15,9,22,89,33,65,90,83};
LinkList A,B,C; /*声明单链表A、B、C*/
ListNode *p;
InitList(&A); /*初始化单链表A*/
InitList(&B); /*初始化单链表B*/
/*将数组a中的元素插入单链表A中*/
for(i=1;i<=sizeof(a)/sizeof(a[0]);i++)
{
if(InsertList(A,i,a[i-1])==0)
{
printf("位置不合法");
return;
}
}
/*将数组b中的元素插入单链表B中*/
for(i=1;i<=sizeof(b)/sizeof(b[0]);i++)
{
if(InsertList(B,i,b[i-1])==0)
{
printf("位置不合法");
return;
}
}
printf("单链表A中的元素有%d个：\n",ListLength(A));
p=A->next;
while(p!=NULL)
{
printf("%4d",p->data); /*输出单链表A中的每个元素*/
p=p->next;
}
printf("\n");
printf("单链表B中的元素有%d个：\n",ListLength(B));
p=B->next;
while(p!=NULL)
{
printf("%4d",p->data); /*输出单链表B中的每个元素*/
p=p->next;
}
printf("\n");
SortList(A);
SortList(B);
C=Difference(A,B);
printf("单链表C中的元素：\n");
p=C;
while(p!=NULL)
{
printf("%4d",p->data);
p=p->next;
}
printf("\n");
}
void SortList(LinkList S)
/*利用选择排序法对单链表S中的元素进行排序*/
{
ListNode *p,*q,*r;
DataType t;
p=S->next;
while(p->next)
{
r=p;
q=p->next;
while(q)
{
if(r->data>q->data)
r=q;
q=q->next;
}
if(p!=r)
{
t=p->data;
p->data=r->data;
r->data=t;
}
p=p->next;
}
}
ListNode *Append(ListNode *last,DataType e)
//释放头节点
{
last->next=(ListNode*)malloc(sizeof(ListNode));
last->next->data=e;
return last->next;
}
ListNode *Difference(ListNode *A,ListNode *B)
//求A-B，将结果存放在C中
{
ListNode *C,*last;
C=last=(ListNode*)malloc(sizeof(ListNode));
while(A!=NULL&&B!=NULL)
if(A->data<B->data)
{
last=Append(last,A->data);
A=A->next;
}
else if(A->data==B->data)
{
A=A->next;
B=B->next;
}
else
B=B->next;
while(A!=NULL) //如果A中还有剩余元素，则把剩余元素追加到C中
{
last=Append(last,A->data);
A=A->next;
}
last->next=NULL; //最后一个节点的指针域设置为空
last=C;
C=C->next; //指向第一个节点
free(last); //释放头节点
return C;
}运行结果如图1.27所示。
图1.27 运行结果
这个算法也可以利用单链表的基本运算实现（无须对单链表进行排序）。对于单链表A中的每个元素，在单链表B中进行查找，如果在B中存在与A相同的元素，则将元素从A中删除。算法如下。
void DelElem(LinkList A,LinkList B)
/*删除在单链表A中出现的单链表B的元素的算法实现*/
{
int i,pos;
DataType e;
ListNode *p;
/*在单链表B中，取出每个元素与单链表A中的元素比较，如果相等，则删除单链表A中元素对应的节点*/
for(i=1;i<=ListLength(B);i++)
{
p=Get(B,i); /*取出单链表B中的每个节点，将指针返回给p*/
if(p)
{
pos=LocatePos(A,p->data);
if(pos>0)
DeleteList(A,pos,&e);
}
}
}
问题描述
已知两个单链表A和B，其中的元素都是非递减排列的，实现算法将单链表A和B合并成一个有序递减的单链表 C（值相同的元素只保留一个），并要求利用原单链表的节点空间。例如，A=(12,16,21,33,35,87,102)，B=(3,5,21,23,35,99,123)，则合并后 C=(123,102,99,87,35,33,23,21,16, 12,5,3)。
【分析】
此题为单链表合并问题。利用头插法建立单链表，使先插入的元素值小的节点在单链表末尾，后插入的元素值大的节点在单链表开头。初始时，单链表C为空（插入的是C的第一个节点），将单链表A和B中有较小的元素值的节点插入C中；单链表C不为空时，比较C和将插入节点的元素值，当值不同时，插入C中，当值相同时，释放该节点。当A和B中有一个单链表为空时，将剩下的节点依次插入C中。
第1章\实例1-09.c
/********************************************
*实例说明：合并两个单链表
*********************************************/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef int DataType;
#include"LinkList.h" /*单链表基本运算实现文件*/
void MergeList(LinkList A,LinkList B,LinkList *C);/*函数声明：将单链表A和B的元素合并到C中*/
void main()
{
int i;
DataType a[]={12,16,21,33,35,87,102};
DataType b[]={3,5,21,23,35,99,123};
LinkList A,B,C;
ListNode *p;
InitList(&A);
InitList(&B);
for(i=1;i<=sizeof(a)/sizeof(a[0]);i++)
/*利用数组元素创建单链表A*/
{
if(InsertList(A,i,a[i-1])==0)
{
printf("插入位置不合法!");
return;
}
}
for(i=1;i<=sizeof(b)/sizeof(b[0]);i++)
/*利用数组元素创建单链表B*/
{
if(InsertList(B,i,b[i-1])==0)
{
printf("插入位置不合法!");
return;
}
}
printf("单链表A中的元素有%d个：\n",ListLength(A));
for(i=1;i<=ListLength(A);i++) /*输出单链表A*/
{
p=Get(A,i); /*返回单链表A中的每个节点的指针*/
if(p)
printf("%4d",p->data); /*输出单链表A中的每个元素*/
}
printf("\n");
printf("单链表B中的元素有%d个：\n",ListLength(B));
for(i=1;i<=ListLength(B);i++) /*输出单链表B*/
{
p=Get(B,i); /*返回单链表B中的每个节点的指针*/
if(p)
printf("%4d",p->data); /*输出单链表B中的每个元素*/
}
printf("\n");
MergeList(A,B,&C); /*将单链表A和B中的元素合并到单链表C中*/
printf("将单链表A和B合并成一个有序递减的单链表C(包含%d个元素)：\n",ListLength(C));
for(i=1;i<=ListLength(C);i++)
{
p=Get(C,i); /*返回单链表C中的每个节点的指针*/
if(p)
printf("%4d",p->data); /*输出单链表C中的所有元素*/
}
printf("\n");
}
void MergeList(LinkList A,LinkList B,LinkList *C)
{
ListNode *pa,*pb,*qa,*qb; /*定义指向单链表A、B的指针*/
pa=A->next; /*pa指向单链表A*/
pb=B->next; /*pb指向单链表B*/
free(B); /*释放单链表B的头节点*/
*C=A; /*初始化单链表C，利用单链表A的头节点作为C的头节点*/
(*C)->next=NULL;
while(pa&&pb)
{
if(pa->data<pb->data) /*pa指向元素值较小的节点时，将pa指向的节点插入单链表C中*/
{
qa=pa;
pa=pa->next;
if((*C)->next==NULL) /*单链表C为空时，直接将节点插入单链表C中*/
{
qa->next=(*C)->next;
(*C)->next=qa;
}
else if((*C)->next->data<qa->data)
{
qa->next=(*C)->next;
(*C)->next=qa;
}
else/*否则，释放元素值相同的节点*/
free(qa);
}
else/*pb指向元素值较小的节点时，将pb指向的节点插入单链表C中*/
{
qb=pb;
pb=pb->next;
if((*C)->next==NULL)/*单链表C为空时，直接将节点插入单链表C中*/
{
qb->next=(*C)->next;
(*C)->next=qb;
}
else if((*C)->next->data<qb->data)
{
qb->next=(*C)->next;
(*C)->next=qb;
}
else/*否则，释放元素值相同的节点*/
free(qb);
}
}
while(pa)/*若pb为空、pa非空，则将pa指向的后继节点插入单链表C中*/
{
qa=pa;
pa=pa->next;
if((*C)->next&&(*C)->next->data<qa->data)
{
qa->next=(*C)->next;
(*C)->next=qa;
}
else
free(qa);
}
while(pb)/*若pa为空、pb非空，则将pb指向的后继节点插入单链表C中*/
{
qb=pb;
pb=pb->next;
if((*C)->next&&(*C)->next->data<qb->data)
{
qb->next=(*C)->next;
(*C)->next=qb;
}
else
free(qb);
}
}运行结果如图1.28所示。
图1.28 运行结果
问题描述
假定采用带头节点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如图1.29所示。
图1.29 “loading”和“being”的存储映像
设str1和str2分别指向两个单词所在单链表的头节点，链表节点结构为
，请设计一个时间上尽可能高效的算法，找出由str1和str2所指的两个链表共同后缀的起始位置（图1.29中字符i所在节点的位置p）。
【分析】
该题为某年全国计算机考研题目。令指针p和q分别指向str1和str2，扫描两个链表，当p和q指向同一个地址时，即找到共同后缀的起始位置。
设str1和str2指向的链表长度分别为m和n。将两个链表以表尾对齐，令指针p和q分别指向str1和str2的头节点，若mn，则指针p先扫描，使p指向链表的第（m−n+1）个节点；若m＜n，则让q先扫描str2，使q指向链表中的第（n−m+1）个节点，即令指针p和q所指向的节点到表尾的长度相等。反复让指针p和q同步向后移动，当p和q指向同一个位置时停止，即为共同后缀的起始地址。
第1章\实例1-10
/********************************************
*实例说明：找出单链表表示的两个单词的共同后缀起始地址
*********************************************/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef char DataType;
#include"LinkList.h" /*包含单链表基本操作实现文件*/
ListNode *FindAddr(LinkList A, LinkList B); /*函数声明：查找单链表A和B的共同后缀起始地址*/
void CreateList(LinkList *A, LinkList *B, DataType a[], DataType b[], int n, int m);
void DispList(LinkList L);
void main()
{
DataType a[]={'l','o','a','d','i','n','g'};
DataType b[]={'b','e'};
LinkList A,B; /*声明单链表A和B*/
ListNode *p;
int n=sizeof(a)/sizeof(a[0]);
int m=sizeof(b)/sizeof(b[0]);
CreateList(&A,&B,a,b,n,m);/*创建单链表A和B*/
printf("单链表A中的元素：\n");
DispList(A);
printf("\n单链表B中的元素：\n");
DispList(B);
p=FindAddr(A,B); /*求单链表A和B的共同后缀起始地址*/
printf("\nA和B的共同后缀起始地址是%p, 起始元素是%2c\n",p,p->data);
}
ListNode *FindAddr(LinkList A, LinkList B)
/*求单链表A和B的共同后缀起始地址*/
{
int m,n;
ListNode *p,*q;
m=ListLength(A);
n=ListLength(B);
for(p=A;m>n;m--)
p=p->next;
for(q=B;m<n;n--)
q=q->next;
while(p->next!=NULL && p->next!=q->next)
{
p=p->next;
q=q->next;
}
return p->next;
}
void CreateList(LinkList *A, LinkList *B, DataType a[], DataType b[], int n, int m)
/*创建具有共同后缀的单链表A和B*/
{
int i;
ListNode *p,*q;
InitList(A); /*初始化单链表A*/
InitList(B); /*初始化单链表B*/
for(i=1;i<=n;i++) /*利用数组元素创建单链表A*/
{
if(InsertList(*A,i,a[i-1])==0)
{
printf("插入位置不合法!");
return;
}
}
q=*A;
while(q->next!=NULL && q->data!='i')
q=q->next;
if(q->next==NULL)
{
printf("error!");
exit(-1);
}
for(i=1;i<=m;i++) /*利用数组元素创建单链表B*/
{
if(InsertList(*B,i,b[i-1])==0)
{
printf("插入位置不合法!");
return;
}
}
/*令单链表A和B共享共同后缀*/
p=*B;
while(p->next!=NULL)
p=p->next;
p->next=q;
}
void DispList(LinkList L)
/*输出单链表L*/
{
LinkList p=L->next;
while(p)
{
printf("%4c",p->data);
p=p->next;
}
}运行结果如图1.30所示。
图1.30 运行结果
问题描述
已知一个带头节点的单链表，节点结构为
，假设该链表只给出了头指针list，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，输出该节点的data域的元素值，并返回1；否则，返回0。
【分析】
该题为某年计算机考研全国统考试题。定义两个指针变量p和q，初始时均指向首节点（头节点的下一个节点）。先让p沿着链表向后移动，并用计数器count进行计数，当p指向第k个节点时，即k==count，使q从第一个节点开始与p指针向后同步移动。当p指向最后一个节点时，q指向的节点就是倒数第k个节点。具体算法步骤如下。
（1）令p和q均指向链表的首节点，令count=0。
（2）若p为NULL，则转向步骤（5）。
（3）若count==k，则令q指向下一个节点；否则，使count=count+1。
（4）令p指向下一个节点，转向步骤（2）。
（5）若count==k，则查找成功，输出该节点的data域的元素值，并返回1；否则，表示查找失败，返回0。
第1章\实例1-11.c
/********************************************
*实例说明：找出单链表中倒数第k个位置上的节点
*********************************************/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef int DataType;
#include"LinkList.h"
int Search_K_Reverse(LinkList L, int k, DataType *e);
void DispList(LinkList L);
void main()
{
DataType a[]={10,20,30,40,50,60,70,80,90,100},e;
LinkList L; /*声明单链表L*/
int n=sizeof(a)/sizeof(a[0]),flag,i,k;
InitList(&L); /*初始化单链表L*/
/*将数组a中元素插入单链表L中*/
for(i=1;i<=sizeof(a)/sizeof(a[0]);i++)
{
if(InsertList(L,i,a[i-1])==0)
{
printf("位置不合法");
return;
}
}
printf("单链表L中的元素有%d个：\n",ListLength(L));
DispList(L);
printf("\n请输入要查找L中倒数第几个节点元素值 k=(1≤k≤%d):",n);
scanf("%d",&k);
flag=Search_K_Reverse(L,k,&e);
if(flag==1)
printf("L中倒数第%d个节点的元素值是%2d\n",k,e);
else
printf("L中不存在倒数第%d个元素\n",k,e);
}
int Search_K_Reverse(LinkList L, int k, DataType *e)
{
int count=0;
ListNode *p,*q;
p=q=L->next;
while(p!=NULL)
{
if(count<k)
count++;
else
q=q->next;
p=p->next;
}
if(count<k)
return 0;
else
{
*e=q->data;
return 1;
}
}
void DispList(LinkList L)
/*输出单链表L*/
{
LinkList p=L->next;
while(p)
{
printf("%4d",p->data);
p=p->next;
}
}运行结果如图1.31所示。
图1.31 运行结果
【定义】
循环单链表（circular linked list）是一种首尾相连的单链表。将单链表的最后一个节点的指针域由空指针改为指向头节点或第一个节点，整个单链表就形成一个环，我们称这样的单链表为循环单链表。
与单链表类似，循环单链表也可分为带头节点的循环单链表和不带头节点的循环单链表两种。对于不带头节点的循环单链表，当单链表非空时，最后一个节点的指针域指向头节点，如图1.32所示。对于带头节点的循环单链表，当单链表为空链表时，头节点的指针域指向头节点本身，如图1.33所示。
图1.32 非空的循环单链表
图1.33 空的循环单链表
问题描述
已知一个带头节点的循环单链表中的数据元素含有正数和负数，试实现一个算法，创建两个循环单链表，使一个循环单链表中只含正数，另一个循环单链表只含负数。例如，创建一个循环单链表(55,106,−29,−203,761,329,−76,432,87），分解后变成两个循环单链表，一个只含有正数，一个只含有负数，即(55,106,761,329,432,87)和(−29,−203,−76)。
【分析】
初始时，先创建两个空的单链表ha和hb，然后依次查看指针p指向的节点的元素值，如果值为正数，则将其插入ha中；否则，将其插入hb中。最后，使最后一个节点的指针域指向头节点，构成循环单链表。
第1章\实例1-12.c
/********************************************
*实例说明：将一个循环单链表分解成两个循环单链表
*********************************************/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
/*单链表类型定义*/
typedef int DataType;
typedef struct Node
{
DataType data;
struct Node *next;
}ListNode,*LinkList;
/*函数声明*/
LinkList CreateCycList(); /*创建一个循环单链表*/
void Split(LinkList ha,LinkList hb);
/*按ha中元素值的正负将ha分成两个循环单链表ha和hb*/
void DispCycList(LinkList head); /*输出循环单链表*/
void main()
{
LinkList ha,hb=NULL;
ListNode *s,*p;
ha=CreateCycList();
p=ha;
while(p->next!=ha) /*找ha的最后一个节点，p指向该节点*/
p=p->next;
/*为ha添加哨兵节点*/
s=(ListNode*)malloc(sizeof(ListNode));
s->next=ha;
ha=s;
p->next=ha;
/*创建一个空的循环单链表hb*/
s=(ListNode*)malloc(sizeof(ListNode));
s->next=hb;
hb=s;
Split(ha,hb);
printf("输出循环单链表A(正数):\n");
DispCycList(ha);
printf("输出循环单链表B(负数):\n");
DispCycList(hb);
}
void Split(LinkList ha,LinkList hb)
/*将一个循环单链表ha分解成两个循环单链表，其中ha中的元素为正数，hb中的元素为负数*/
{
ListNode *ra,*rb,*p=ha->next;
int v;
ra=ha;
ra->next=NULL;
rb=hb;
rb->next=NULL;
while(p!=ha)
{
v=p->data;
if(v>0) /*若元素值大于0，插入ha中*/
{
ra->next=p;
ra=p;
}
else /*若元素值小于0，插入hb中*/
{
rb->next=p;
rb=p;
}
p=p->next;
}
ra->next=ha; /*构成循环单链表ha*/
rb->next=hb; /*构成循环单链表hb*/
}
LinkList CreateCycList()
/*创建循环单链表*/
{
ListNode *h=NULL,*s,*t=NULL;
DataType e;
int i=1;
printf("创建一个循环单链表(输入0表示创建链表结束):\n");
while(1)
{
printf("请输入第%d个节点的data域值:",i);
scanf("%d",&e);
if(e==0)
break;
if(i==1)
{
h=(ListNode*)malloc(sizeof(ListNode));
h->data=e;
h->next=NULL;
t=h;
}
else
{
s=(ListNode*)malloc(sizeof(ListNode));
s->data=e;
s->next=NULL;
t->next=s;
t=s;
}
i++;
}
if(t!=NULL)
t->next=h;
return h;
}
void DispCycList(LinkList h)
/*输出循环单链表*/
{
ListNode *p=h->next;
if(p==NULL)
{
printf("链表为空!\n");
return;
}
while(p->next!=h)
{
printf("%4d",p->data);
p=p->next;
}
printf("%4d",p->data);
printf("\n");
}运行结果如图1.34所示。
图1.34 运行结果
单链表与循环单链表的操作有何不同？
从以上算法容易看出，循环单链表的创建与单链表的创建基本一样，只是最后增加了两条语句，
if(t!=NULL)
t->next=h;使最后一个节点的指针指向第一个节点，构成一个循环单链表。
问题描述
已知L为指向单链表中头节点的指针，每个节点的数据域都存放一个字符，该字符可能是英文字母字符、数字字符或其他字符。实现算法，根据该单链表构造3个带头节点的循环单链表——ha、hb、hc，使得每个循环单链表只含有同一类字符。
【分析】
该题是东北大学考研题目的变形，为了便于编写程序，这里为单链表增加了一个头节点。这个题目考查单链表的基本操作（单链表和循环单链表的操作基本相同）。首先为3个循环单链表建立头节点并初始化。若要将一个单链表分解成3个循环单链表，可按照每个字符的ASCII码进行分类。若遇到A～Z和a～z的字符，将其插入ha中；若遇到0～9的字符，将其插入hb中；若遇到剩下的字符，将其插入hc中。
第1章\实例1-13.cpp
/********************************************
*实例说明：将一个单链表分解成3个循环单链表
*********************************************/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<iostream.h>
#include<iomanip.h>
/*宏定义和单链表类型定义*/
typedef char DataType;
#include"LinkList.h"
LinkList CreateList(DataType a[],int n);/*根据给定的数组创建单链表*/
void Decompose(LinkList L,LinkList *ha,LinkList *hb,LinkList *hc);
/*分解单链表为3个循环单链表*/
void DispList(LinkList L);
void DispCycList(LinkList head);
int CycListLength(LinkList head);
void main()
{
LinkList h,ha,hb,hc;
int n;
DataType a[]={'a','X','0','$','@','%','p','m','3','9','y','*','i','&'};
n=sizeof(a)/sizeof(a[0]);
h=CreateList(a,n);
Decompose(h,&ha,&hb,&hc);
cout<<"大小写英文字母的字符有"<<CycListLength(ha)<<"个，分别是"<<endl;
DispCycList(ha);
cout<<"数字字符的有:"<<CycListLength(hb)<<"个，分别是"<<endl;
DispCycList(hb);
cout<<"其他字符有:"<<CycListLength(hc)<<"个，分别是"<<endl;
DispCycList(hc);
}
LinkList CreateList(DataType a[],int n)
//根据数组中的元素创建单链表
{
LinkList L;
int i;
InitList(&L); //初始化单链表L
for(i=1;i<=n;i++) //将数组a中的元素插入单链表L中
{
if(InsertList(L,i,a[i-1])==0)
{
printf("插入位置不合法!");
return NULL;
}
}
DispList(L);
return L;
}
void Decompose(LinkList L,LinkList *ha,LinkList *hb,LinkList *hc)
/*将带头节点的单链表L分解为3个带头节点的循环单链表ha、hb和hc，其中ha仅含英文字母字符，hb仅含数字字符，hc仅含其他字符*/
{
ListNode *p,*q;
p=L->next;
*ha=(LinkList)malloc(sizeof(ListNode));
*hb=(LinkList)malloc(sizeof(ListNode));
*hc=(LinkList)malloc(sizeof(ListNode));
(*ha)->next=(*ha);
(*hb)->next=(*hb);
(*hc)->next=(*hc);
while(p)
{
if((p->data>='A' && p->data<='Z')||(p->data>='a' && p->data<'z'))
{
q=p;
p=p->next;
q->next=(*ha)->next;
(*ha)->next=q;
}
else if(p->data>='0' && p->data<='9')
{
q=p;
p=p->next;
q->next=(*hb)->next;
(*hb)->next=q;
}
else
{
q=p;
p=p->next;
q->next=(*hc)->next;
(*hc)->next=q;
}
}
}
void DispList(LinkList L)
//输出单链表中的元素
{
int i;
LinkList p;
cout<<"单链表L中的元素有"<<ListLength(L)<<"个"<<endl;
for(i=1;i<=ListLength(L);i++) /*输出单链表L中的每个元素*/
{
p=Get(L,i); /*返回单链表L中的每个节点的指针*/
if(p)
cout<<setw(4)<<p->data; /*输出单链表L中的每个元素*/
}
cout<<endl;
}
void DispCycList(LinkList h)
//输出循环单链表中的元素
{
ListNode *p=h->next;
if(p==NULL)
{
cout<<"链表为空!"<<endl;
return;
}
while(p->next!=h)
{
cout<<setw(4)<<p->data;
p=p->next;
}
cout<<setw(4)<<p->data;
cout<<endl;
}
int CycListLength(LinkList head)
//求循环单链表的长度
{
ListNode *p;
int count=0;
p=head;
while(p->next!=head)
{
p=p->next;
count++;
}
return count;
}运行结果如图1.35所示。
图1.35 运行结果
求循环单链表长度和求单链表长度的判断条件分别是什么？它们有何区别？
在输出循环单链表的长度时，要注意循环单链表和单链表的判断条件不同，单链表的判断条件是while(p−>next!=NULL)，而循环单链表的判断条件是while(p−>next!=head)。否则，就会出现死循环，不显示这一部分的输出结果。
问题描述
约瑟夫问题是一个很有意思的游戏。所谓约瑟夫问题，就是有n个人，编号分别是1，2，3，…，n。他们围坐在一张圆桌周围，从编号为k的人开始报数，数到m的人出列。然后下一个人又从1开始报数，数到m的人出列。以此类推，直到坐在圆桌周围的人都出列。例如，若n=7，k=2，m=3，则出列的人的顺序依次是4、7、3、1、6、2、5。
要解决这个问题，需要先创建一个循环单链表，循环单链表就像一群小孩子手拉手围成一个大圆圈。将单链表的最后一个节点和第一个节点首尾相连就构成了循环单链表，如图1.36所示。
图1.36 循环单链表
在图1.36中，将最后一个节点与第一个节点相连构成一个循环单链表。
【分析】
要解决约瑟夫问题，就要将循环单链表中的节点依次从循环单链表中删除。可以将这个问题分为以下两个小问题。
首先需要找到开始报数的人，也就是循环单链表的第k个节点。需要从循环单链表的头指针出发，依次计数，直到k。这需要定义一个指针p，让p指向head。通过for循环实现计数，p指向的节点就是第k个节点。代码如下。
p=head; /*使p指向第一个节点*/
for(i=1;i<k;i++) /*通过循环令p指向开始报数的人*/
{
r=p;
p=p->next;
}如果k=3，则指针p和r的变化情况如图1.37（a）～（c）所示。
图1.37 在寻找第k个节点时指针p和r的变化情况
当i=2时，不再执行循环，p指向的节点就是开始报数的节点，r指向前一个节点。
从p指向的节点开始计数，使用循环进行计数。代码如下。
for(i=1;i<m;i++) /*找到报数为m的人*/
{
r=p;
p=p->next;
}最后p指向要删除的节点，r指向前一个节点。如果m=2，则要删除的节点是编号为5的节点。删除p指向的节点的过程如图1.38（a）～（d）所示。
图1.38 删除p指向的节点的过程
删除p指向的节点的代码如下。
r->next=p->next; /*将报数为m的人即p指向的节点脱链*/
free(p); /*释放p指向的节点的空间*/删除节点之后，需要将p指向下一个节点以便下一次报数。代码如下。
p=r->next; /*令p指向下一次开始报数的人*/第1章\实例1-14.c
/********************************************
*实例说明：约瑟夫问题
*********************************************/
#include<stdio.h>
#include<stdlib.h>
void Josephus(int n,int k,int m); /*函数声明*/
typedef struct node{
int data;
struct node *next;
}ListNode,*LinkList; /*定义节点类型*/
void main()
{
int n,k,m;
printf("请依次输入总人数、开始报数的序号及出列人所报的数:\n");
scanf("%d,%d,%d",&n,&k,&m); /*输入总人数、第一个开始报数的人、出列的人所报的数*/
Josephus(n,k,m); /*调用函数*/
}
void Josephus(int n,int k,int m)
/*n表示总人数，k表示第一个报数的人，报数为m的人出列*/
{
LinkList p,r,head=NULL; /*定义指向节点的指针，其中头指针head初始时为NULL*/
int i;
/*------------------------建立循环链表------------------------*/
for(i=1;i<=n;i++)
{
p=(LinkList)malloc(sizeof(ListNode)); /*生成新节点*/
p->data=i; /*为节点元素赋值*/
if(head==NULL)
head=p;
else
r->next=p;
r=p;
}
p->next=head; /*使链表循环起来*/
/*------------------------寻找开始报数的人------------------------*/
p=head; /*使p指向第一个节点*/
for(i=1;i<k;i++) /*通过循环令p指向开始报数的人*/
{
r=p;
p=p->next;
}
/*------------------------删除报数为m的人------------------------*/
while(p->next!=p) /*如果链表中的节点多于1个*/
{
for(i=1;i<m;i++) /*找到报数为m的人*/
{
r=p;
p=p->next;
}
r->next=p->next; /*使报数为m的人（即p指向的节点）脱链*/
printf("被删除的元素：%d\n",p->data); /*输出出列的人的序号*/
free(p); /*释放p指向的节点的空间*/
p=r->next; /*令p指向下一次开始报数的人*/
}
printf("最后被删除的元素是%d\n",p->data); /*输出最后一个出列的人的序号*/运行结果如图1.39所示。
图1.39 运行结果
【定义】
双向链表（double linked list）就是链表中的每个节点都有两个指针域：一个指向直接前驱节点，另一个指向直接后继节点。双向链表的每个节点都有3个域——data域、prior域和next域。双向链表的节点结构如图1.40所示。
图1.40 双向链表的节点结构
其中，data域为数据域，存放数据元素；prior域为前驱节点指针域，指向直接前驱节点；next域为后继节点指针域，指向直接后继节点。
双向链表和循环链表结合就构成了双向循环链表（double circular linked list）。一个带头节点的双向循环链表如图1.41所示。带头节点的双向循环链表为空的情况如图1.42所示，带头节点的双向循环链表为空的判断条件是head−>prior==head或head−>next==head。
图1.41 带头节点的双向循环链表
图1.42 带头节点的空的双向循环链表
在带头节点的双向循环链表中，若双向循环链表为空，则有p=p−>prior−>next=p−>next−>prior。双向循环链表中，既可以根据节点的前驱节点指针域向前查找，也可以根据后继节点指针域向后查找，因此给节点的查找带来了很大便利。
【存储结构】
typedef struct Node
{
DataType data;
struct Node *prior;
struct Node *next;
}DListNode,*DLinkList;【基本运算】
双向链表中的大多数操作和单链表的操作相同，如求链表的长度、查找链表的第i个节点等。因为双向链表中节点有两个指针域，所以插入和删除操作比单链表要稍微复杂一些，需要同时修改两个指针域的指针指向。
（1）找到第i个节点，用p指向该节点。
（2）申请一个新节点，由s指向该节点，将e放入数据域。
（3）修改p和s指向的节点的指针域：修改s的prior域，使其指向p的直接前驱节点，即s−>prior=p−>prior；修改p的直接前驱节点的next域，使其指向s指向的节点，即p−>prior−>next=s；修改s的next域，使其指向p指向的节点，即s−>next=p；修改p的prior域，使其指向s指向的节点，即p−>prior=s。修改指针的顺序如图1.43中的①～④所示。
图1.43 修改指针的顺序
插入操作算法实现如下所示。
int InsertDList(DListLink head,int i,DataType e)
{
DListNode *p,*s;
int j;
p=head->next;
j=0;
while(p!=head&&j<i)
{
p=p->next;
j++;
}
if(j!=i)
{
printf("插入位置不正确");
return 0;
}
s=(DListNode*)malloc(sizeof(DListNode));
if(!s)
return -1;
s->data=e;
s->prior=p->prior;
p->prior->next=s;
s->next =p;
p->prior=s;
return 1;
}（1）找到第i个节点，用p指向该节点。
（2）使p指向的节点与双向链表断开，这需要修改p指向的节点的直接前驱节点和直接后继节点的指针域。首先修改p的直接前驱节点的next域，使其指向p的直接后继节点，即p−>prior−> next=p−>next；其次修改p的直接后继节点的prior域，使其指向p的直接前驱节点，即p−>next−> prior=p−>prior，如图1.44所示。
图1.44 双向链表的删除节点操作过程
删除操作算法实现如下所示。
int DeleteDList(DListLink head,int i,DataType *e)
{
DListNode *p;
int j;
p=head->next;
j=0;
while(p!=head&&j<i)
{
p=p->next;
j++;
}
if(j!=i)
{
printf("删除位置不正确");
return 0;
}
p->prior->next=p->next;
p->next->prior =p->prior;
free(p);
return 1;
}
问题描述
创建一个带头节点的含n个元素的双向链表H，并在双向链表H中第i个位置插入一个元素。例如，创建一个双向链表(‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’, ‘g’)，元素为字符型数据，在双向链表中第5个位置插入元素y，则双向链表变为(‘a’, ‘b’, ‘c’, ‘d’, ‘y’, ‘e’, ‘f’, ‘g’)。
【分析】
主要考察双向链表的基本操作，双向链表的基本操作与单链表类似，只是双向链表的每个节点有两个指针域。
第1章\实例1-15.c
/********************************************
*实例说明：在双向链表中插入一个元素
*********************************************/
/*包含头文件*/
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
/*类型定义*/
typedef char DataType;
typedef struct Node
{
DataType data;
struct Node *prior;
struct Node *next;
}DListNode,*DLinkList;
/*函数声明*/
DListNode *GetElem(DLinkList head,int i);
void PrintDList(DLinkList head);
int CreateDList(DLinkList head,int n);
int InsertDList(DLinkList head,int i,char e);
/*函数实现*/
int InitDList(DLinkList *head)
/*初始化双向循环链表*/
{
*head=(DLinkList)malloc(sizeof(DListNode));
if(!head)
return -1;
/*使头节点的prior指针和next指针指向自己*/
(*head)->next=*head;
(*head)->prior=*head;
return 1;
}
int CreateDList(DLinkList head,int n)
/*创建双向循环链表*/
{
DListNode *s,*q;
int i;
DataType e;
q=head;
for(i=1;i<=n;i++)
{
printf("输入第%d个元素",i);
e=getchar();
s=(DListNode*)malloc(sizeof(DListNode));
s->data=e;
/*将新生成的节点插入双向循环链表*/
s->next=q->next;
q->next=s;
s->prior=q;
head->prior=s;
/*这里要注意头节点的prior域指向新插入的节点*/
q=s; /*q始终指向最后一个节点*/
getchar();
}
return 1;
}
int InsertDList(DLinkList head,int i,DataType e)
/*在双向循环链表的第i个位置插入元素e*/
{
DListNode *p,*s;
p=GetElem(head,i); /*查找链表中的第i个节点*/
if(!p)
return 0;
s=(DListNode*)malloc(sizeof(DListNode));
if(!s)
return -1;
s->data=e;
/*将s节点插入双向循环链表*/
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
return 1;
}
DListNode *GetElem(DLinkList head,int i)
/*查找插入的位置*/
{
DListNode *p;
int j;
p=head->next;
j=1;
while(p!=head&&j<i)
{
p=p->next;
j++;
}
if(p==head||j>i) /*如果位置不正确，则返回NULL*/
return NULL;
return p;
}
void main()
{
DLinkList h;
int n;
int pos;
char e;
InitDList(&h);
printf("输入元素个数：");
scanf("%d",&n);
getchar();
CreateDList(h,n);
printf("链表中的元素：");
PrintDList(h);
printf("请输入插入的元素及位置：");
scanf("%c",&e);
getchar();
scanf("%d",&pos);
InsertDList(h,pos,e);
printf("插入元素后链表中的元素：");
PrintDList(h);
}
void PrintDList(DLinkList head)
/*输出双向循环链表中的每一个元素*/
{
DListNode *p;
p=head->next;
while(p!=head)
{
printf("%c",p->data);
p=p->next;
}
printf("\n");
}运行结果如图1.45所示。
图1.45 运行结果
双向链表的插入操作的语句顺序可以颠倒吗？
双向链表的插入和删除操作需要修改节点的prior域和next域，比单链表要复杂，因此要注意修改节点的指针域的顺序。
在创建双向循环链表时，首先要让指针q始终指向链表的最后一个节点，将s指向动态生成的节点，然后在链表的最后插入s指向的节点。插入节点时，注意，语句s−>next=q−>next和q−>next=s的顺序不能颠倒。
问题描述
有n个小朋友，编号分别为1，2，…，n，将小朋友按编号围成一个圆圈，他们按顺时针方向从编号为k的人由1开始报数，报数为m的人出列，在他之后的一个人重新从1开始报数，数到m的人出列，照这样重复下去，直到所有的人都出列。实现一个算法，输入n、k和m，按照出列顺序输出编号。
【分析】
解决约瑟夫问题可以分为3个步骤。第1步，创建一个具有n个节点的不带头节点的双向循环链表（模拟编号为1～n的圆圈可以利用循环单链表实现，这里采用双向循环链表实现），编号从1到n，代表n个小朋友。第2步，找到第k个节点，即第一个开始报数的人。第3步，编号为k的人从1开始报数，并开始计数，报到m的人出列即将该节点删除。继续从下一个节点开始报数，直到最后一个节点被删除。
第1章\实例1-16.c
/********************************************
*实例说明：约瑟夫问题（双向链表）
*********************************************/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
/*双向链表类型定义*/
typedef int DataType;
typedef struct Node
{
DataType data;
struct Node *prior;
struct Node *next;
}DListNode,*DLinkList;
/*函数声明*/
DLinkList CreateDCList(int n);
/*创建一个长度为n的双向循环链表的函数声明*/
void Josephus(DLinkList head,int n,int m,int k);
/*在长度为n的双向循环链表中，报数为m的出列*/
int InitDList(DLinkList *head);
void main()
{
DLinkList h;
int n,k,m;
printf("输入环中人的个数n=");
scanf("%d",&n);
printf("输入开始报数的序号k=");
scanf("%d",&k);
printf("报数为m的人出列m=");
scanf("%d",&m);
h=CreateDCList(n);
Josephus(h,n,m,k);
}
void Josephus(DLinkList head,int n,int m,int k)
/*在长度为n的双向循环链表中，从第k个人开始报数，数到m的人出列*/
{
DListNode *p,*q;
int i;
p=head;
for(i=1;i<k;i++) /*从第k个人开始报数*/
{
q=p;
p=p->next;
}
while(p->next!=p)
{
for(i=1;i<m;i++) /*数到m的人出列*/
{
q=p;
p=p->next;
}
q->next=p->next; /*将p指向的节点删除，即报数为m的人出列*/
p->next->prior=q;
printf("%4d",p->data); /*输出被删除的节点*/
free(p);
p=q->next; /*p指向下一个节点，重新开始报数*/
}
printf("%4d\n",p->data);
}
DLinkList CreateDCList(int n)
/*创建双向循环链表*/
{
DLinkList head=NULL;
DListNode *s,*q;
int i;
for(i=1;i<=n;i++)
{
s=(DListNode*)malloc(sizeof(DListNode));
s->data=i;
s->next=NULL;
/*将新生成的节点插入双向循环链表*/
if(head==NULL)
{
head=s;
s->prior=head;
s->next=head;
}
else
{
s->next=q->next;
q->next=s;
s->prior=q;
head->prior=s;
}
q=s; /*q始终指向双向循环链表的最后一个节点*/
}
return head;
}
int InitDList(DLinkList *head)
/*初始化双向循环链表*/
{
*head=(DLinkList)malloc(sizeof(DListNode));
if(!head)
return -1;
/*使头节点的prior指针和next指针指向自己*/
(*head)->next=*head;
(*head)->prior=*head;
return 1;
}运行结果如图1.46所示。
图1.46 运行结果
问题描述
要求用链表表示一元多项式，并实现算法求两个多项式的和。例如，输入两个多项式3x2+2x+1和5x3+3x+2，输出结果为5x3+3x2+5x+3。
【分析】
假设一元多项式表示为
Pn(x)=anxn+an−1xn−1+…+a1x+a0
一元多项式的每一项都由系数和指数构成，因此要表示一元多项式，需要定义一个结构体。结构体由coef和exp两个部分构成，分别表示系数和指数。代码如下。
struct node
{
float coef; /*系数*/
int exp; /*指数*/
};如果用结构体数组表示一元多项式的每一项，则需要n+1个数组元素存放一元多项式（假设n为最高次幂）。当指数不连续且指数之间跨度非常大的时候（例如，一元多项式2x500+1），则需要数组的长度为501，这显然会浪费很多内存空间。
为了有效利用内存空间，可以使用链表表示一元多项式，一元多项式的每一项都使用节点表示，节点由3个部分构成，分别是系数、指数和指针域。节点的结构如图1.47所示。
图1.47 节点的结构
节点用C语言描述如下。
struct node
{
float coef; /*系数*/
int exp; /*指数*/
struct node *next; /*指针域*/
};为了操作上的方便，将链表的节点按照指数从高到低进行排列，即降幂排列。由最高次幂为n的一元多项式构成的链表如图1.48所示。
图1.48 由最高次幂为n的一元多项式的构成的链表
两个一元多项式p(x)=3x2+2x+1和q(x)=5x3+3x+2的链表表示如图1.49所示。
图1.49 两个一元多项式的链表表示
如果要将两个一元多项式相加，则需要比较两个一元多项式的指数项。当两个一元多项式的两项中指数相同时，才将系数相加。如果两个一元多项式的指数不等，则求和后的一元多项式中该项的系数是其中一个多项式的系数。代码如下。
if(s1->exp==s2->exp) /*如果两个指数相等，则将系数相加*/
{
c=s1->coef+s2->coef;
e=s1->exp;
s1=s1->next;
s2=s2->next;
}
else if(s1->exp>s2->exp) /*如果s1的指数大于s2的指数，则将s1的指数作为结果*/
{
c=s1->coef;
e=s1->exp;
s1=s1->next;
}
else /*如果s1的指数小于或等于s2的指数，则将s2的指数作为结果*/
{
c=s2->coef;
e=s2->exp;
s2=s2->next;
}其中，s1和s2分别指向两个表示一元多项式的链表。因为链表的节点是按照指数从大到小排列的，所以在指数不等时，将指数大的作为结果，指数小的还要继续进行比较。例如，如果当前s1指向系数为3、指数为2的节点，即(3,2)，s2指向节点(3,1)，因为s1−>exp>s2−>exp，所以将s1指向的节点作为结果。在s1指向(2,1)时，还要与s2指向的(3,1)相加，得到(5,1)。
如果相加后系数不为0，则需要生成一个节点存放到链表中。代码如下。
if(c!=0)
{
p=(ListNode*)malloc(sizeof(ListNode));
p->coef=c;
p->exp=e;
p->next=NULL;
if(s==NULL)
s=p;
else
r->next=p;
r=p;
}如果一个链表已经到达末尾，而另一个链表还有节点，则需要将剩下的节点插入新链表中，代码如下。
while(s1!=NULL)
{
c=s1->coef;
e=s1->exp;
s1=s1->next;
if(c!=0)
{
p=(ListNode*)malloc(sizeof(ListNode));
p->coef=c;
p->exp=e;
p->next=NULL;
if(s==NULL)
s=p;
else
r->next=p;
r=p;
}
}
while(s2!=NULL)
{
c=s2->coef;
e=s2->exp;
s2=s2->next;
if(c!=0)
{
p=(ListNode*)malloc(sizeof(ListNode));
p->coef=c;
p->exp=e;
p->next=NULL;
if(s==NULL)
s=p;
else
r->next=p;
r=p;
}
}最后，s指向的链表就是两个多项式的和的链表。
第1章\实例1-17.c
/********************************************
*实例说明：求两个一元多项式的和
*********************************************/
//创建多项式。依次输入多项式的系数和指数。当输入0、0时，即系数和指数都为0时，输入结束
#include<stdio.h>
#include<stdlib.h>
struct node
{
int exp;
float coef;
struct node *next;
};
typedef struct node ListNode;
ListNode *CreatePoly()
/*创建多项式链表*/
{
ListNode *h=NULL,*p,*q=NULL;
int e;
float c;
printf("请输入系数和指数:");
scanf("%f,%d",&c,&e);
while(e!=0||c!=0)
{
p=(ListNode*)malloc(sizeof(ListNode));
p->coef=c;
p->exp=e;
p->next=NULL;
if(h==NULL)
h=p;
else
q->next=p;
q=p;
printf("请输入系数和指数:");
scanf("%f,%d",&c,&e);
}
return h;
}
//输出多项式。为了避免在指数为0时输出指数，指定当指数为0,则只输出系数
void DispPoly(ListNode *h)
/*输出多项式*/
{
ListNode *p;
p=h;
while(p!=NULL)
{
if(p->exp==0)
printf("%.2f",p->coef);
else
printf("%fx^%d",p->coef,p->exp);
p=p->next;
if(p!=NULL)
printf("+");
}
printf("\n");
}
//求两个多项式的和
ListNode *AddPoly(ListNode *h1,ListNode *h2)
/*将两个多项式相加*/
{
ListNode *p,*r=NULL,*s1,*s2,*s=NULL;
float c;
int e;
s1=h1;
s2=h2;
while(s1!=NULL&&s2!=NULL)
{
if(s1->exp==s2->exp)
{
c=s1->coef+s2->coef;
e=s1->exp;
s1=s1->next;
s2=s2->next;
}
else if(s1->exp>s2->exp)
{
c=s1->coef;
e=s1->exp;
s1=s1->next;
}
else
{
c=s2->coef;
e=s2->exp;
s2=s2->next;
}
if(c!=0)
{
p=(ListNode*)malloc(sizeof(ListNode));
p->coef=c;
p->exp=e;
p->next=NULL;
if(s==NULL)
s=p;
else
r->next=p;
r=p;
}
}
while(s1!=NULL)
{
c=s1->coef;
e=s1->exp;
s1=s1->next;
if(c!=0)
{
p=(ListNode*)malloc(sizeof(ListNode));
p->coef=c;
p->exp=e;
p->next=NULL;
if(s==NULL)
s=p;
else
r->next=p;
r=p;
}
}
while(s2!=NULL)
{
c=s2->coef;
e=s2->exp;
s2=s2->next;
if(c!=0)
{
p=(ListNode*)malloc(sizeof(ListNode));
p->coef=c;
p->exp=e;
p->next=NULL;
if(s==NULL)
s=p;
else
r->next=p;
r=p;
}
}
return s;
}
//在使用完链表后，需要释放链表所占用的内存空间
void DeletePoly(ListNode *h)
/*释放链表所占用的内存空间*/
{
ListNode *p,*r=h;
while(r!=NULL)
{
p=r->next;
free(r);
r=p;
}
}
//测试部分
void main()
{
ListNode *head1,*head2,*head;
printf("创建第一个多项式:\n");
head1=CreatePoly();
printf("创建第二个多项式:\n");
head2=CreatePoly();
printf("将两个多项式相加:\n");
head=AddPoly(head1,head2);
DispPoly(head);
DeletePoly(head);
}运行结果如图1.50所示。
图1.50 运行结果
问题描述
将两个一元多项式相乘，要求用链表实现。例如，分别输入两个一元多项式5x4+3x2+3x和7x3+5x2+6x，输出结果为35x7+25x6+51x5+36x4+33x3+18x2。
【分析】
两个一元多项式的相乘运算，需要将一个一元多项式的每一项的指数与另一个一元多项式的每一项的指数相加，并将其系数相乘。假设有两个多项式An(x)=anxn+an−1xn−1+…+a1x+a0和Bm(x)=bmxm+bm−1xm−1+…+b1x+b0，要将这两个多项式相乘，就是将多项式An(x)中的每一项与Bm(x)相乘，相乘的结果用线性表表示为((an ×bm,n+m),(an−1 ×bm,n+m−1),…,(a1,1),(a0,0))。
例如，两个多项式A(x)和B(x)相乘后得到C(x)。
A(x)=5x4+3x2+3x
B(x)=7x3+5x2+6x
C(x)=35x7+25x6+51x5+36x4+33x3+18x2
以上一元多项式可以表示成链式存储结构，如图1.51所示。
图1.51 多项式的链表表示
算法思想如下。设A、B与C分别是一元多项式A(x)、B(x)和C(x)对应链表的头指针，要计算A(x)和B(x)的乘积，先计算出A(x)和B(x)的最高指数和，即4+3=7，则A(x)和B(x)的乘积C(x)的指数范围为0～7。然后将A(x)的各项按照指数降序排列，将B(x)的各项按照指数升序排列。分别设置两个指针pa和pb，pa用来指向表示A(x)的链表，pb用来指向表示B(x)的链表，从两个链表的第一个节点开始计算指数和，并将其与k比较（k为指数和的范围，从7到0递减），使链表的指数和呈递减排列。若指数和小于k，则pb=pb−>next；若指数和等于k，则求出两个一元多项式系数的乘积，并将其存入新节点中；若和大于k，则pa=pa−>next。这样就可以得到一元多项式A(x)和B(x)的乘积C(x)。算法结束后将表示B(x)的链表逆置，将其恢复原样。
第1章\实例1-18.c
/********************************************
*实例说明：求两个一元多项式的乘积
*********************************************/
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<malloc.h>
4 /*一元多项式节点类型定义*/
5 typedef struct polyn
6 {
7 float coef; /*存放一元多项式的系数*/
8 int expn; /*存放一元多项式的指数*/
9 struct polyn *next;
10 }PolyNode, *PLinkList;
11 PLinkList CreatePolyn()
12 /*创建一元多项式，使一元多项式各项呈指数递减排列*/
13 {
14 PolyNode *p,*q,*s;
15 PolyNode *head=NULL;
16 int expn2;
17 float coef2;
18 head=(PLinkList)malloc(sizeof(PolyNode));
19 /*动态生成一个头节点*/
20 if(!head)
21 return NULL;
22 head->coef=0;
23 head->expn=0;
24 head->next=NULL;
25 do
26 {
27 printf("输入系数coef(系数和指数都为0结束)");
28 scanf("%f",&coef2);
29 printf("输入指数exp(系数和指数都为0结束)");
30 scanf("%d",&expn2);
31 if((long)coef2==0&&expn2==0)
32 break;
33 s=(PolyNode*)malloc(sizeof(PolyNode));
34 if(!s)
35 return NULL;
36 s->expn=expn2;
37 s->coef=coef2;
38 q=head->next; /*q指向链表的第一个节点，即表尾*/
39 p=head; /*p指向q的前驱节点*/
40 while(q&&expn2<q->expn)
41 /*将新输入的指数与q指向的节点的指数比较*/
42 {
43 p=q;
44 q=q->next;
45 }
46 if(q==NULL||expn2>q->expn)
47 /*q指向要插入节点的位置，p指向要插入节点的前驱节点*/
48 {
49 p->next=s; /*将s节点插入链表中*/
50 s->next=q;
51 }
52 else
53 q->coef+=coef2; /*若指数与链表中节点的指数相同，则将系数相加*/
54 } while(1);
55 return head;
56 }
57 PolyNode *MultiplyPolyn(PLinkList A,PLinkList B)
58 /*多项式的乘积*/
59 {
60 PolyNode *pa,*pb,*pc,*u,*head;
61 int k,maxExp;
62 float coef;
63 head=(PLinkList)malloc(sizeof(PolyNode)); /*动态生成头节点*/
64 if(!head)
65 return NULL;
66 head->coef=0.0;
67 head->expn=0;
68 head->next=NULL;
69 if(A->next!=NULL&&B->next!=NULL)
70 maxExp=A->next->expn+B->next->expn;/*maxExp为两个链表指数的和的最大值*/
71 else
72 return head;
73 pc=head;
74 B=Reverse(B);
75 for(k=maxExp;k>=0;k--)
76 {
77 pa=A->next;
78 while(pa!=NULL&&pa->expn>k)/*寻找pa的开始位置*/
79 pa=pa->next;
80 pb=B->next;
81 while(pb!=NULL&&pa!=NULL&&pa->expn+pb->expn<k) /*如果和小于k，使pb指向下一个节点*/
82 pb=pb->next;
83 coef=0.0;
84 while(pa!=NULL&&pb!=NULL)
85 {
86 if(pa->expn+pb->expn==k) /*如果在链表中找到对应的节点，即和等于k，求相应的系数*/
87 {
88 coef+=pa->coef*pb->coef;
89 pa=pa->next;
90 pb=pb->next;
91 }
92 else if(pa->expn+pb->expn>k) /*如果和大于k，则使pa指向下一个节点*/
93 pa=pa->next;
94 else
95 pb=pb->next; /*如果和小于k，则使pb指向下一个节点*/
96 }
97 if(coef!=0.0)
98 /*如果系数不为0，则生成新节点，将系数和指数分别赋值给新节点，并将新节点插入链表中*/
99 {
100 u=(PolyNode*)malloc(sizeof(PolyNode));
101 u->coef=coef;
102 u->expn=k;
103 u->next=pc->next;
104 pc->next=u;
105 pc=u;
106 }
107 }
108 B=Reverse(B); /*完成一元多项式相乘后，将B（x）的各项呈指数递减形式排列*/
109 return head;
110 }
111 void OutPut(PLinkList head)
112 /*输出一元多项式*/
113 {
114 PolyNode *p=head->next;
115 while(p)
116 {
117 printf("%1.1f",p->coef);
118 if(p->expn)
119 printf("*x^%d",p->expn);
120 if(p->next&&p->next->coef>0)
121 printf("+");
122 p=p->next;
123 }
124 }
125 PolyNode *Reverse(PLinkList head)
126 /*将生成的链表逆置，使一元多项式呈指数递增形式排列*/
127 {
128 PolyNode *q,*r,*p=NULL;
129 q=head->next;
130 while(q)
131 {
132 r=q->next;
133 q->next=p;
134 p=q;
135 q=r;
136 }
137 head->next=p; /*将头节点的指针指向已经逆置后的链表*/
138 return head;
139 }
140 void main()
141 {
142 PLinkList A,B,C;
143 A=CreatePolyn();
144 printf("A(x)=");
145 OutPut(A);
146 printf("\n");
147 B=CreatePolyn();
148 printf("B(x)=");
149 OutPut(B);
150 printf("\n");
151 C=MultiplyPolyn(A,B);
152 printf("C(x)=A(x)*B(x)=");
153 OutPut(C); /*输出结果*/
154 printf("\n");
155 }运行结果如图1.52所示。
图1.52 运行结果
【说明】
在第5～9行中，定义一元多项式的节点，包括两个域——系数域和指数域。
在第18～24行中，动态生成头节点，初始时链表为空。
在第27～31行中，输入系数和指数，当系数和指数都输入为0时，输入结束。
在第38～45行中，从链表的第一个节点开始寻找新节点的插入位置。
在第46～51行中，将q指向的新节点插入链表的相应位置，插入后使链表中每个节点按照指数从大到小排列，即降幂排列。
在第66～72行中，以两个一元多项式的指数的最大值之和作为一元多项式相乘后的最高指数项，若一元多项式中有一个为空，则相乘后结果为空，直接返回一个空链表。
在第73行中，初始时，pc指向的是一个空链表，将pb指向的链表逆置，使其指数按降序排列。
在第77～82行中，分别在pa和pb指向的链表中寻找可能开始的位置，保证两个链表中节点的指数相加为k。
在第87～92行中，若指数之和为k，则将两个节点的系数相乘。
在第93～94行中，若指数之和大于k，则需要从pa指向的节点的下一个节点开始查找。
在第95～96行中，若指数之和小于k，则需要从pb指向的节点的下一个节点开始查找。
在第98～107行中，若两个系数相乘后不为0，则创建一个新节点，并将系数和指数存入其中，把该节点插入pc所指向的链表中。
在第109行中，将pb指向的链表逆置，恢复原样。
