作者：杨峰
出版社：清华大学出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
妙趣横生的算法(C语言实现)第2版试读：
前言
程序＝数据结构＋算法——著名的计算机科学家沃斯（Nikiklaus Wirth）
自从著名的计算机科学家沃斯将程序设计形象地用上面的公式表示出来后，这条“黄金定律”便成为了人们学习程序设计，进行程序开发的准则。要想成为一名真正专业的程序设计人员，基本的数据结构基础和常用的算法知识是必须掌握的。脱离了这两点，编写出来的程序一定不是健壮的好程序。
然而单纯地掌握一些数据结构基础和常用的算法知识也是远远不够的。空洞地掌握所谓的数据结构和算法等理论知识只是纸上谈兵，这些知识必须要依托于一门程序设计语言才具有真正的生命力，才能够转化为真实的程序代码，才能真正地解决实际问题。
本书就是将数据结构基础和常用的算法知识与目前广泛应用、最具群众基础的C语言相结合而产生的。本书的写作思想是理论与实践相结合，以实践为核心，以实例为主要内容。
首先，本书总结归纳了数据结构基础、常用的排序查找算法和经典的算法思想，提纲挈领地阐述了核心的理论知识。这样可以使没有系统学习过或者不熟悉数据结构和算法等知识的读者，对这部分知识有一个基本的了解，并掌握基本的数据结构知识和常用而经典的算法思想，以便更加深入地学习本书的其他内容。
其次，本书列举了大量的编程实例，这些题目都按照知识体系进行了内容上的划分。本书列举的这些编程实例都是一些比较灵活有趣的题目，有些题目渗透了巧妙的算法思想，有些题目则必须借助特殊的数据结构才能更加容易解答。通过这些题目的训练，可以使读者开阔眼界，启迪思维，提高编程的兴趣。最重要的是能够提高读者算法设计的本领；提高读者灵活应用各种数据结构的本领；提高读者编写程序解决实际问题的能力。
关于本书第2版
本书第1版出版后广受读者好评，并且多次加印，被大量的算法入门人员和爱好者及一些参加算法竞赛的读者作为参考读物。但是随着技术的发展，第1版图书已经不能完全适应当前的阅读需求。例如，很多开发人员已经将C语言的编程环境由以前流行的Tubro C迁移到了当前流行的Visual Studio平台上，加之本书第1版图书在解析上还有改进空间。基于这些原因，我们对本书第1版进行了系统的改版，以方便读者更好地学习。相比第1版图书，本书第2版内容上的主要变化体现在以下几个方面：
● 书中涉及的实例代码在Visual Studio 2010环境下重新编译通过；
● 对一些叙述不清或不够通顺的语句进行了修改；
● 对第1版图书中存在的一些疏漏进行了修订；
● 给实例源代码增加了更加详细的注释；
● 给第1～3章中各增加了一节新内容，作为课后练习，并给出了参考答案；
● 对第2章中的快速排序和希尔排序等内容进行了较大幅度的修改，同时还新增加了堆排序的介绍及各种排序性能的比较；
● 新增了一章关于ACM程序设计竞赛的相关内容。
本书有何特点
1．结构清晰，知识全面
本书分为2篇。第1篇是基础知识介绍，主要介绍数据结构的基础知识和一些常用的算法思想。这部分内容为核心的理论知识，可以帮助读者学习和回顾数据结构和算法的知识，使读者在理论水平上有所提高，从而能够更加顺利地深入学习后续内容。第2篇主要是编程实例的介绍，通过一些非常有趣的编程实例使读者开阔眼界，发散思维，提高算法设计本领，提高灵活应用各种数据结构的本领，提高读者编写程序解决实际问题的能力。
2．实例丰富，讲解到位
本书的写作思想就是以实践为核心，以编程实例为主要内容。因此本书中包含了大量的编程实例，并都附有详细的分析和解答。作者认为讲解到位是本书与同类书籍相比的一大特点。本书尽量做到深入浅出，多用简单的语句配以图示来讲解比较复杂的问题，而且尽量做到讲解透彻明白，不敷衍读者。
3．题材新型，趣味性强
兴趣是最好的老师。本书在编写过程中始终贯穿这一思想。因此本书中的题目设置尽量做到既有练习意义，又富有趣味性。特别是在本书的第2篇中，列举了大量的兼顾难度和趣味性的经典题目，例如魔幻方阵、汉诺塔、魔王语言翻译、约瑟夫环、马踏棋盘、巧算24、八皇后问题等。这样使读者对所谓的难题也不再那么畏惧，而是更加愿意面对它。
4．重点突出，实用性强
本书的写作意图是通过讲解大量生动有趣的实例，培养读者的编程能力、算法设计思想和对数据结构的灵活运用。归根到底就是通过程序设计解决实际问题的能力。因此本书中的所有题目都不只是给出答案而已，而是从算法思想的层面来剖析，涉及复杂数据结构的内容，还通过图示的方法形象地加以说明。特别值得一提的是，本书的最后一章为算法设计与数据结构面试题精粹，这部分内容从实战和应试的角度出发，旨在巩固读者的知识水平和提高读者的应试能力，同时使得本书更具实用价值。
5．视频教学，高效直观
本书中的重点内容和实例提供了配套教学视频辅助讲解。读者可以先阅读书中的内容讲解，然后再结合教学视频进行学习，可以获得更加高效而直观的学习效果。
本书内容及知识体系
本书共11章，分为2篇，主要内容介绍如下。
第1篇 算法基础（第1～3章）
本篇主要介绍一些必备的算法基础知识，包括数据结构基础知识、常用的查找和排序方法、常用的算法思想。
第2篇 常用算法实例解析（第4～11章）
本篇主要介绍一些基于C语言的算法编程实例。包括编程的基本功、数学趣题、数据结构题、数值计算题、综合题、算法设计与数据结构面试题、ACM程序设计竞赛试题等。这些题目内涵丰富，兼顾趣味性，从不同侧面体现出对数据结构知识和算法设计思想的灵活运用，相信会对读者有一定帮助。
本书读者对象
● 对算法设计有兴趣的入门人员；
● 有一定编程基础的算法爱好者；
● 需要提高C语言编程水平的人员；
● 参加IT企业面试的人员；
● 信息学竞赛的参赛人员；
● 各种程序设计选拔赛的参赛人员；
● 大中专院校的学生。
本书配套资源获取方式
本书提供了配套的教学视频、源代码和教学PPT，这些资源需要读者自行下载。读者可以在清华大学出版社的网站上（www.tup.com.cn）搜索到本书页面，然后按照提示下载，也可以通过本书服务网站上（www.wanjuanchina.net）的光盘下载版块下载。
本书作者
本书由杨峰主笔编写。其他参与编写的人员有韩先锋、何艳芬、李荣亮、刘德环、孙姗姗、王晓燕、杨平、杨艳艳、袁玉健、张锐、张翔、陈明、邓睿、巩民顺、吉燕、水淼、宗志勇、安静、曹方、曾苗苗、陈超。
如果您在阅读本书的过程中有任何疑问，请发E-mail到bookservice2008@163.com以获得帮助。编者第1篇 算法基础
第1章 数据结构基础
第2章 常用的查找与排序方法
第3章 常用的算法思想第1章 数据结构基础
要想成为一名真正的程序员，数据结构是必备的基础知识。只有学过数据结构，才能真正有效规范地组织程序中的数据。而在实际编程中，有些问题必须通过特定的数据结构才能更方便地解决。因此数据结构是每一个搞计算机的人都必须掌握的知识。
要想全面而系统地学习数据结构的知识，本章的介绍显然是不充分的，建议寻找专门介绍数据结构的书籍学习。如果你只想掌握一般层次的知识，或是已经学过数据结构，只是为了深入学习本书后续的内容而进行回顾和复习，那么本章的介绍是足够的。1.1 什么是数据结构
数据结构是指计算机内部数据的组织形式和存储方法。我们熟悉的数组就是一种简单而典型的线性数据结构类型。本章中将更加具体地介绍一些常用的数据结构，主要包括：线性结构、树结构、图结构。
线性结构是最常用，也是最简单的一种数据结构。所谓线性结构，就是指由n个数据元素构成的有限序列。直观地讲，它就是一张有限的一维数表。数组就是一种最为简单的线性结构表示。更加具体地说，线性结构主要包括：顺序表、链表、栈、队列等基本形式。其中顺序表和链表是从存储形式上（或者说物理结构上）区分的，而栈和队列是从逻辑功能上区分的。也就是说，顺序表和链表是线性数据结构的基础，队列和栈是基于顺序表和链表的，它们由顺序表或链表构成。
有时仅仅用线性结构存储管理数据是难以胜任的，一些数据之间存在着“一对多”的关系，这就构成了所谓的树形结构，简称树结构。例如人工智能领域常用的“博弈树”，数据挖掘和商业智能中使用的“决策树”，多媒体技术中的“哈夫曼树”等都是应用树结构存储管理数据的实例。
还有一种常用的数据结构叫做图状结构，简称图结构。图结构中数据元素之间存在着“多对多”的关系，因此图结构比线性结构和树结构都复杂得多。在处理一些复杂的问题中，图结构往往能派上用场，例如：人工智能领域中的神经网络系统、贝叶斯网络等都是应用图结构存储管理数据的实例。1.2 顺序表
在计算机内部存储一张线性表（线性结构的数表），最方便简单的方法就是用一组连续地址的内存单元来存储整张线性表。这种存储结构称为顺序存储结构，这种存储结构下的线性表就叫做顺序表。如图1-1所示，就是顺序表的示意。图1-1 顺序表的示意
从图1-1中可以看出，一张顺序表包括以下特征。
● 有一个唯一的表名来标识该顺序表，例如图1-1所示的A。
● 内存单元连续存储，也就是说，一张顺序表要占据一块连续的内存空间。
● 数据顺序存放，元素之间有先后关系。
因为数组满足上述特征，所以一个数组本身就是一张顺序表。
下面介绍如何定义顺序表以及对顺序表的几种操作。
1.2.1 顺序表的定义
定义一张顺序表也就是在内存中开辟一段连续的存储空间，并给它一个名字进行标识。只有定义了一个顺序表，才能利用该顺序表存放数据元素，也才能对该顺序表进行各种操作。
有两种定义顺序表的方法：一是静态地定义一张顺序表；二是动态地生成一张顺序表。
静态地定义一张顺序表的方法与定义一个数组的方法类似。可以描述如下： #define MaxSize 100 ElemType Sqlist[MaxSize]; int len;
为了更完整、更精确地描述一张顺序表，可以把顺序表定义成上面的代码形式。其中ElemType是指定的顺序表的类型，这里只是一个抽象的类型描述，要根据实际情况决定ElemType的内容。ElemType可以是int、char等基本类型，也可以是其他构造类型（结构体类型等）。len为顺序表的长度，定义这个变量的目的是更加方便地对顺序表进行操作。
这里要注意，上述这种定义方法，包括今后的其他数据类型的定义，都只是一种更完整、更精确的描述。读者不应刻板地机械模仿。例如这样定义： int a[1000];
是定义一个数组，但同时也是静态定义一个顺序表。不一定非要预定义MaxSize和定义变量len。因此读者学习时应灵活掌握。
动态地生成一张顺序表的方法可描述如下： #define MaxSize 100 typedef struct{ ElemType *elem; int length; int listsize; } Sqlist; void initSqlist(Sqlist *L){ /*初始化一个顺序表*/ L->elem=(int *)malloc(MaxSize*sizeof(ElemType)); if(!L->elem) exit(0); L->length=0; L->listsize= MaxSize; }
动态生成一张顺序表可分为以下两步。（1）定义一个类型Sqlist，它是一个结构体，其成员包括：指向顺序表的首地址elem，顺序表中表的长度（表中元素个数）length，顺序表的存储空间容量（占据内存大小，以sizeof(ElemType)为单位，由MaxSize规定）listsize。（2）通过调用一个函数initSqlist()实现动态生成一张顺序表。函数initSqlist()的参数是一个Sqlist类型的指针变量，因此可以在函数initSqlist()中直接对顺序表进行操作。
函数initSqlist()的作用是动态初始化一个顺序表，其操作步骤如下。（1）调用了C标准库函数malloc()动态地分配一段长度为MaxSize*sizeof(ElemType)的内存空间，并将该段空间的首地址赋值给变量L的elem成员L->elem。也就是说，L->elem指向顺序表的首单元。（2）将L->length置为0，表明此时刚刚生成一张空的顺序表，表内尚无内容，将L->listsize置为MaxSize，表明该顺序表占据内存空间大小为MaxSize（以sizeof(ElemType)为单位）。
这样Sqlist类型的变量L就代表了一张顺序表。其中，L->elem指向该顺序表的表头地址，L->length为该顺序表的长度，L->listsize为该顺序表的容量。通过变量L可以灵活地操纵该顺序表，因此L就代表了一张顺序表。
需要强调一点的是，动态生成顺序表与静态定义一个顺序表的本质区别在于它们所占内存空间的位置不同。对于静态定义一个顺序表，顺序表占用的内存空间开辟在内存的静态区，也就是函数栈上，这个区域的内存空间会随着函数调用的完成而被系统自动回收。而对于动态生成一个顺序表，其内存空间开辟在内存的动态区上，也就是堆内存上，这个区域的内存空间不会被系统自动回收，需要程序主动去释放它。
至此我们知道了如何静态地定义一张顺序表以及如何动态生成一张顺序表。
1.2.2 向顺序表中插入元素
下面介绍如何在长度为n的顺序表中的第i个位置插入新元素item。
所谓在长度为n的顺序表中的第i个位置插入新元素，是指在顺序表第i–1个数据元素和第i个数据元素之间插入一个新元素item。例如顺序表为：
A（a1，a2，…ai–1，ai，…an）
在第i个位置插入新元素item后，该顺序表变为：
A（a1，a2，…ai–1，，item，ai，…an）
而此时顺序表A的长度由n变为n+1。
下面给出向静态顺序表中第i个位置插入元素item和向动态生成的顺序表中第i个位置插入元素item的代码描述。
按照1.2.1节中介绍的方法创建一个静态的顺序表Sqlist[MaxSize]，那么向该静态顺序表中第i个位置插入元素item的代码描述如下： void InserElem(ElemType Sqlist[],int &n,int i, ElemType item){ /*向顺序表Sqlist中第i个位置插入元素item，该顺序表原长度为n*/ int t; if(n==MaxSize||i<1||i>n+1) exit(0); /*非法插入*/ for(t=n-1;t>=i-1;t--) Sqlist[t+1]=Sqlist[t]; /*将i-1以后的元素顺序后移一个元素的位置*/ Sqlist[i-1]=item; /*在第i个位置上插入元素item*/ n=n+1; /*表长加1*/ }
函数InserElem()的作用是在顺序表Sqlist中第i个位置上插入元素item，并将顺序表长度加1。其实现过程如下。（1）判断插入元素的位置是否合法。一个长度为n的顺序表的可能插入元素的位置是1～n+1，因此如果i<1或者i>n+1，或者表已满，即n == MaxSize（因为表的内存大小固定不变）的插入都是非法的。（2）将顺序表的i–1以后的元素顺序后移一个元素的位置，即：将顺序表从第i个元素到第n个元素顺序后移一个元素的位置。（3）在表的第i个位置（下标为i–1）上插入元素item，并将表长加1。
按照1.2.1节中介绍的方法创建一个动态的顺序表L，那么向该动态生成的顺序表中第i个位置插入元素item的代码描述如下： void InsertElem(Sqlist *L,int i,ElemType item){ /*向顺序表L中第i个位置上插入元素item*/ ElemType *base,* insertPtr,*p; if(i<1||i>L->length+1) exit(0); /*非法插入*/ if(L->length>=L->listsize) { base=(ElemType*)realloc(L->elem,(L->listsize+10)*sizeof(ElemType)); /*重新追加空间*/ L->elem=base; /*更新内存基地址*/ L->listsize=L->listsize+100; /*存储空间增大100单元*/ } insertPtr=&(L->elem[i-1]); /*insertPtr 为插入位置*/ for(p=&(L->elem[L->length-1]);p>= insertPtr;p--) *(p+1)=*p; /*将i-1以后的元素顺序后移一个元素的位置*/ * insertPtr=item; /*在第i个位置上插入元素item */ L->length++; /*表长加1*/ }
上述算法与“向静态顺序表中第i个位置插入元素item”的算法类似，都是利用将i–1以后的元素顺序后移一个元素的位置，然后再向第i个位置上插入元素item的方法实现。不同之处在于向静态顺序表插入元素时，由于表的内存大小固定不变，所以只能在MaxSize规定的范围之内顺序插入元素。而向动态生成的顺序表中第i个位置插入元素item时，由于顺序表是建立在动态存储区的，因此可以随时扩充。因此当向表中插入元素时，如果顺序表已满（L->len>=L->listsize），可以追加一段内存空间，再并入原顺序表中。这就是动态顺序表的优势所在。
1.2.3 从顺序表中删除元素
下面介绍如何删除长度为n的顺序表中的第i个位置的元素。
所谓删除长度为n的顺序表中的第i个位置的元素，就是指将顺序表第i个位置上的元素去掉。例如顺序表为：
A（a1，a2，…ai–1，ai，ai+1…an）
删除第i个位置的元素后，该顺序表变为：
A（a1，a2，…ai–1，ai+1…an）
而此时顺序表A的长度由n变为n–1。
下面给出从静态顺序表中删除第i个位置元素和从动态生成的顺序表中删除第i个位置元素的代码描述。
按照1.2.1节中介绍的方法创建一个静态的顺序表Sqlist[MaxSize]，那么从该静态顺序表中删除第i个位置元素的代码可描述如下： void DelElem(ElemType Sqlist[],int &n,int i){ int j; if(i<1||i>n) exit(0) /*非法删除*/ for(j=i;j 函数DelElem()的作用是从顺序表Sqlist中删除第i个位置的元素，并将表的长度值减1。其实现过程如下。（1）判断要删除的元素是否合法。对于一个长度为n的顺序表，删除元素的合法位置是1～n，因此如果i<1或者i>n都是不合法的。（2）将顺序表的第i位置以后的元素依次前移，这样会将第i个元素覆盖，也就起到删除第i个位置元素的作用。（3）最后将表长减1。 如果按照1.2.1节中介绍的方法创建一个动态的顺序表L，那么从该动态生成的顺序表中删除第i个位置元素的代码描述如下。 void DelElem(Sqlist *L,int i) { /*从顺序表L中删除第i个元素*/ ElemType *delItem, *q; if(i<1||i>L->len) exit(0); /*非法删除*/ delItem=&(L->elem[i-1]); /*delItem指向第i个元素*/ q=L->elem+L->length-1; /*q指向表尾*/ for(++delItem; delItem<=q;++ delItem){ *( delItem-1)=* delItem; /*将第i位置以后的元素依次前移*/ } L->length--; /*表长减1*/ } 从动态生成的顺序表中删除第i个位置元素的方法与从静态顺序表中删除第i个位置元素的方法本质上是一样的，都是将第i个位置以后的元素依次前移，从而覆盖掉第i个元素。 以上介绍了顺序表的定义方法、向顺序表中插入元素、从顺序表中删除元素等操作。顺序表是最简单的一种线性存储结构，它的优点是：构造简单，操作方便，且通过顺序表的首地址（或数组名）可直接对表进行随机存取，从而存取速度快，系统开销小。同时它也存在着缺点：有可能浪费存储空间，在插入或删除一个元素时，需要对插入或删除位置后面的所有元素逐个进行移动，从而导致操作效率较低。因此，顺序表数据结构适用于表的长度不经常发生变化的场合，例如批处理操作。 下面通过程序实例来理解顺序表的应用。 1.2.4 实例与分析 前面介绍了静态顺序表和动态顺序表的定义、创建、插入元素、删除元素等方法。下面通过具体的实例巩固学到的知识。【实例1-1】 创建一个静态的顺序表存放整数，大小为10，完成以下的操作。（1）输入6个整数，打印出顺序表中的内容，并显示表中剩余的空间个数。（2）在顺序表中的第3个位置插入元素0，打印出顺序表中的内容，并显示表中剩余的空间个数。（3）再试图向表中第11个位置插入整数0，程序提示超出范围。（4）删除表中第6个元素，打印出顺序表中的内容，并显示表中剩余的空间个数。 下面给出本题的程序清单。 程序清单1-1 /*---------------------------------- 1-1.c --------------------------*/ #include "stdio.h" #define MaxSize 10 /*静态顺序表的各种操作*/ /** 向顺序表中插入元素 */ /** 参数Sqlist:表首地址 */ /** 参数*len:表的长度 */ /** 参数i:插入元素的位置 */ /** 参数x:待插入的元素值 */ void insertElem(int Sqlist[],int *len,int i,int x) { int t; if(*len==MaxSize || i<1 || i>*len+1) { printf("This insert is illegal\n"); return; } /*非法插入*/ for(t=*len-1;t>=i-1;t--) Sqlist[t+1]=Sqlist[t]; Sqlist[i-1]=x; /*插入元素*/ *len=*len+1; /*表长加1*/ } /** 向顺序表中删除元素 */ /** 参数Sqlist:表首地址 */ /** 参数*len: 表的长度 */ /** 参数i: 插入元素的位置 */ void DelElem(int Sqlist[],int *len,int i) { int j; if(i<1 || i>len) { printf("This insert is illegal"); return; } /*非法插入*/ for(j=i;j<=*len-1;j++) Sqlist[j-1]=Sqlist[j]; /*将第i个元素之后的元素前移*/ *len=*len-1; /*表长减1*/ } /**测试函数*/ main() { /*按照题目要求进行测试*/ int Sqlist[MaxSize]; /*定义一个静态顺序表*/ int len; int i; printf("Please input six integer number\n"); for(i=0;i<6;i++) scanf("%d",&Sqlist[i]); /*从键盘输入6个整数*/ len=6; for(i=0;i 需要说明一点，上面的程序采用标准C方式编写，本书中所有的程序也都是采用标准C的方式进行编写。程序的开发环境采用Visual Studio 2010，所有程序都在该集成环境下调试通过。 在程序清单1-1中，定义了静态顺序表的插入元素操作insertElem()函数和删除元素操作DelElem()。在前面已经讲过，insertElem()函数的作用是将元素插入到指定的顺序表中第i个位置，同时顺序表的长度标记len加1。DelElem()函数的作用是将顺序表中的第i个位置的元素删除，同时顺序表的长度标记len减1。 主函数作为测试函数，实现了题目的要求。通过主函数的测试可以得出结论：本程序中的insertElem()和DelElem()函数可以正确地实现静态顺序表插入元素和删除元素的功能。 本程序的运行结果如图1-2所示。图1-2 例1-1的运行结果 如图1-2所示，首先从终端输入1，2，3，4，5，6这6个整数，此时显示顺序表中剩余空间为4；在第3个位置插入整数0后，顺序表中的内容变为1，2，0，3，4，5，6，此时顺序表的剩余空间为3；试图向表中第11个位置插入整数0，程序提示非法操作；删除表中第6个元素后内容变为1，2，0，3，4，6，此时顺序表的剩余空间为4。注意：insertElem()和DelElem()函数中所定义的第i个元素是指位于顺序表中的第i–1个元素，因为顺序表的第1个元素下标为0，因此第i个元素的下标为i–1。【实例1-2】 编写一个程序，动态地创建一个顺序表。要求：顺序表初始长度为10，向顺序表中输入15个整数，并打印出来；再删除顺序表中的第5个元素，打印出删除后的结果。 下面给出本题的程序清单。 程序清单1-2 /*---------------------------- 1-2.c -------------------------------*/ #include "stdio.h" #include "conio.h" #define MaxSize 10 typedef int ElemType ; /*将int定义为ElemType*/ typedef struct{ int *elem; int length; int listsize; } Sqlist; /** 初始化一个顺序表 */ /** 参数L：Sqlist类型的指针 */ void initSqlist(Sqlist *L){ L->elem=(int *)malloc(MaxSize*sizeof(ElemType)); if(!L->elem) exit(0); L->length=0; L->listsize= MaxSize; } /** 向顺序表中插入元素 */ /** 参数L：Sqlist类型的指针 */ /** 参数i：插入元素的位置 */ /** 参数item：插入的元素 */ void InsertElem(Sqlist *L,int i,ElemType item){ /*向顺序表L中第i个位置上插入元素item*/ ElemType *base,* insertPtr,*p; if(i<1||i>L->length+1) exit(0); if(L->length>=L->listsize) { base=(ElemType*)realloc(L->elem,(L->listsize+10)*sizeof (ElemType)); L->elem=base; L->listsize=L->listsize+100; } insertPtr=&(L->elem[i-1]); for(p=&(L->elem[L->length-1]);p>= insertPtr;p--) *(p+1)=*p; * insertPtr=item; L->length++; } /** 从顺序表中删除元素 */ /** 参数L：Sqlist类型的指针 */ /** 参数i：删除元素的位置 */ void DelElem(Sqlist *L,int i) { /*从顺序表L中删除第i个元素*/ ElemType *delItem, *q; if(i<1||i>L->length) exit(0); delItem=&(L->elem[i-1]); q=L->elem+L->length-1 ; for(++delItem; delItem<=q;++ delItem)*( delItem-1)=* delItem; L->length--; } /** 测试函数 */ main() { Sqlist l; int i; initSqlist(&l); /*初始化一个顺序表*/ for(i=0;i<15;i++) InsertElem(&l,i+1,i+1); /*向顺序表中插入1…15*/ printf("\nThe content of the list is\n"); for(i=0;i 本程序实现了一个动态顺序表，并按照题目的要求对该顺序表实施各种操作，具体操作如下。（1）程序首先用函数initSqlist()动态地创建了一个顺序表，其初始化长度为MaxSize 10。（2）然后通过函数InsertElem()动态地向顺序表中插入数据。这里通过一个循环，每次向顺序表的第i+1的位置插入整数i+1。然后打印出该顺序表中的值。在插入顺序表的过程中，由于顺序表初始化长度为10，而要插入15个元素，因此要调用realloc()函数为顺序表重新分配内存空间。（3）再应用DelElem()函数删除表中第5个元素，也就是5。（4）最后打印出删除元素后该顺序表中的值。 本程序的运行结果如图1-3所示。图1-3 例1-2的运行结果 如图1-3所示，程序首先通过一个循环操作向顺序表中插入15个元素（每次都是从表尾插入元素，从1到15），然后删除第5个元素，这时顺序表中第5个元素“5”被删掉。1.3 链表 与顺序表相同，链表也是一种线性表，它的数据的逻辑组织形式是一维的。而与顺序表不同的是，链表的物理存储结构是用一组地址任意的存储单元存储数据的。也就是说，它不像顺序表那样占据一段连续的内存空间，而是将存储单元分散在内存的任意地址上。在链表结构中，每个数据元素记录都存放到链表的一个结点（node）中，而每个结点之间由指针将其连接在一起，这样就形成了一条如同“链”的结构。 在C程序中，链表的每个结点可以是一个结构体类型元素，当然也可以是其他的构造类型元素。在链表的每个结点中，都必须有一个专门用来存放指针（地址）的域，用这个指针域来存放后继结点的地址，这样就达到了连接后继结点的目的。一条链表通常有一个“表头”，它是一个指针变量，用来存放第一个结点地址。此外，一条链表的最后一个结点的指针域要置空（NULL），表示该结点为链表的尾结点，因为它没有后继结点了。链表的结构如图1-4所示。图1-4 链表结构示意 从图1-4中可以看出链表存在以下特征。 ● 每一个结点包括两部分：数据域和指针域。其中数据域用来存放数据元素本身的信息，指针域用来存放后继结点的地址。 ● 链表逻辑上是连续的，而物理上并不一定连续存储结点。 ● 只要获得链表的头结点，就可以通过指针遍历整条链表。 一个链表结点可用C语言描述如下： typedef struct node{ ElemType data; /*数据域*/ struct node *next /*指针域*/ }LNode,*LinkList; 这里采用自定义类型的方式将结构struct node定义为LNode类型。也就是说，该链表每个结点的类型为LNode。另外，*LinkList是指向LNode类型数据的指针类型定义。也就是说，在定义一个指向LNode类型数据的指针类型变量时，语句 LNode *L; 和 LinkList L; 是等价的。 下面介绍如何建立一个链表以及如何操作链表。 1.3.1 创建一个链表 建立一个链表的过程可通过下面这段代码来实现。 LinkList GreatLinkList(int n){ /*建立一个长度为n的链表*/ LinkList p,r,list=NULL; ElemType e; int i; for(i=1;i<=n;i++){ Get(e); p=(LinkList)malloc(sizeof(LNode)); p->data=e; p->next=NULL; if(!list) list=p; else r->next=p; r=p; } return list; } 上面这段代码描述了一个建立一条长度为n的链表的全过程，共分为以下几个步骤。（1）用malloc()函数在内存的动态存储区（堆内存）中开辟一块大小为sizeof（LNode）的空间，并将其地址赋值给LinkList类型变量p（前面讲过，LinkList为指向LNode变量的类型，LNode为前面定义的链表结点类型）。然后将数据e存入该结点的数据域data，指针域存放NULL。其中数据e由函数Get()获得。（2）如果指针变量list为空，说明本次生成的结点为第一个结点，所以将p赋值给list，list是LinkList类型变量，只用来指向第一个链表结点，因此它是该链表的头指针，最后要返回。（3）如果指针变量list不为空，则说明本次生成的结点不是第一个结点，因此将p赋值给r->next。这里r是一个LinkList类型变量，它永远指向原先链表的最后一个结点，也就是要插入结点的前一个结点。（4）再将p赋值给r，目的是使r再次指向最后的结点，以便生成链表的下一个结点，即保证r永远指向原先链表的最后一个结点。（5）重复（1）～（4）n次，生成包含n个结点的链表。（6）最后将生成的链表的头指针list返回主调函数，通过list就可以访问到该链表的每一个结点，并对该链表进行操作。 1.3.2 向链表中插入结点 下面介绍如何在指针q指向的结点后面插入结点。该过程的步骤如下：（1）先创建一个新结点，并用指针p指向该结点。（2）将q指向的结点的next域的值（即q的后继结点的指针）赋值给p指向结点的next域。（3）将p的值赋值给q的next域。 通过以上3步，就可以实现在链表中由指针q指向的结点后面插入p所指向的结点。可以通过图1-5形象地展示出这一过程。图1-5 向链表插入结点过程 下面给出代码描述： void insertList(LinkList *list,LinkList q,ElemType e){ /*向链表中由指针q指出的结点后面插入结点，结点数据为e*/ LinkList p; p=( LinkList)malloc(sizeof(LNode)); /*生成一个新结点，由p指向它*/ p->data=e; /*向该结点的数据域赋值e*/ if(!*list){ *list=p; /*list的内容为NULL表示该链表为空*/ p->next=NULL; } /*当链表为空时q没有意义，只能在头结点后面插入第一个元素*/ else{ p->next=q->next; /*当链表不为空时，认为q指向的结点一定存在*/ /*将q指向的结点的next域的值赋值给p指向结点的next域*/ q->next=p; /*将p的值赋值给q的next域*/ } } 上面的这段代码描述了如何在指针q指向的结点后面插入结点的过程。其过程包括以下几步。（1）首先生成一个新的结点，大小为sizeof（LNode），用LinkList类型的变量p指向该结点。将该结点的数据域赋值为e。（2）接下来判断链表是否为空。如果链表为空，则将p赋值给list，p的next域的值置为空。否则，将q指向结点的next域的值赋值给p指向结点的next域，这样p指向的结点就与q指向结点的下一个结点连接到了一起。（3）然后再将p的值赋值给q所指结点的next域，这样就将p指向的结点插入到了指针q指向结点的后面。 其实通过上面这段算法描述可以看出，应用这个算法同样可以创建一个链表。这是因为当最开始时链表为空，即list==NULL，该算法可自动为链表创建一个结点。在下面的创建其他结点的过程中，只要始终将指针q指向链表的最后一个结点，就可以创建出一个 链表。注意：函数insertList()的参数中有一个LinkList *list，它是指向LinkList类型的指针变量，相当于指向LNode类型的指针的指针。这是因为在函数中要对list，也就是表头指针进行修改，而调用该函数时，实参是&list，而不是list。因此必须采取指针参数传递的办法，否则无法在被调函数中修改主函数中定义的变量的内容。以下的代码也有类似的情况。 1.3.3 从链表中删除结点 下面介绍如何从非空链表中删除q所指的结点。在讨论这个问题时，必须考虑以下3种情形。 ● q所指向的是链表的第一个结点。 ● q所指向的结点的前驱结点的指针已知。 ● q所指向的结点的前驱结点的指针未知。 下面给出不同情形的解决方法。 当q所指向的是链表的第一个结点时，只需将q所指结点的指针域next的值赋值给头指针list，让list指向第二个结点，再释放掉q所指结点即可。该过程如图1-6所示。图1-6 删除链表结点的第一种情形 当q所指向的结点的前驱结点指针已知时（假设为r），只需将q所指结点的指针域next的值赋值给r的指针域next，再释放掉q所指结点即可。该过程如图1-7所示。图1-7 删除链表结点的第二种情形 以上两种情形可用下面这段代码来描述。 void delLink(LinkList *list,LinkList r,LinkList q){ if(q==*list) /*删除链表结点的第一种情形*/ *list=q->next; else r->next=q->next; /*删除链表结点的第二种情形*/ free(q); /*释放掉q所指向的空间*/ } 当q所指向的结点的前驱结点的指针未知时，需要先通过链表头指针list遍历链表，找到q的前驱结点的指针，并将该指针赋值给指针变量r，再按照第二种情形去做即可。 下面给出具体的代码描述。 void delLink(LinkList *list ,LinkList q){ LinkList r; if(q==*list){ *list=q->next; free(q); } else{ for(r=*list;r->next!=q;r=r->next); /*遍历链表，找到q的前驱结点的指针*/ if(r->next!=NULL){ r->next=q->next; /*从链表中删除q指向的结点*/ free(q); /*释放掉q所指向的空间*/ } } } 1.3.4 销毁一个链表 在链表使用完毕后建议销毁它，因为链表本身会占用内存空间。如果一个系统中使用很多的链表，而使用完毕后又不及时地销毁它，那么这些垃圾空间积累过多，最终会导致内存的泄漏甚至程序的崩溃。因此应当养成及时销毁不用的链表的习惯。 下面给出销毁一个链表list的代码描述： void destroyLinkList(LinkList *list){ LinkList p,q; p=*list; while(p){ q=p->next; free(p); p=q; } *list=NULL; } 函数destroyLinkList()的作用是销毁一个链表list，它包括以下步骤。（1）首先将*list的内容赋值给p，这样p也指向链表的第一个结点，成为了链表的 表头。（2）然后判断只要p不为空（NULL），就将p指向的下一个结点的指针（地址）赋值给q，并调用函数free()释放掉p所指向的结点，再进行p=q的操作，也就是p再指向下一个结点。如此循环，直到链表为空为止。（3）最后将*list的内容置为NULL，这样主函数中的链表list就为空了，防止了list变为野指针，而且链表在内存中也被完全地释放掉了。 1.3.5 实例与分析【实例1-3】 编写一个程序，要求：从终端输入一组整数（大于10个数），以0作为结束标志，将这一组整数存放在一个链表中（结束标志0不包括在内），打印出该链表中的值。然后删除该链表中的第5个元素，打印出删除后的结果。最后在内存中释放掉该链表。 下面给出本题的程序清单。 程序清单1-3 /*--------------------------------- 1-3.c ---------------------------*/ #include "stdio.h" typedef int ElemType; typedef struct node{ ElemType data; /*数据域*/ struct node *next; /*指针域*/ }LNode,*LinkList; LinkList GreatLinkList(int n){ /*创建一个链表，包含n个结点*/ LinkList p,r,list=NULL; ElemType e; int i; for(i=1;i<=n;i++){ scanf("%d",&e); /*输入结点的内容*/ p=(LinkList)malloc(sizeof(LNode)); /*为新建的结点开辟内存空间*/ p->data=e; /*元素赋值*/ p->next=NULL; if(!list) list=p; /*赋值链表头指针*/ else r->next=p; /*将结点连入链表*/ r=p; } return list; /*返回链表头指针*/ } void insertList(LinkList *list,LinkList q,ElemType e){ /*向链表中插入结点*/ LinkList p; p=( LinkList)malloc(sizeof(LNode)); /*为新建的结点开辟内存空间*/ p->data=e; /*元素赋值*/ if(!*list){ *list=p; /*赋值链表头指针*/ p->next=NULL; } else{ /*将结点连入链表*/ p->next=q->next; q->next=p; } } void delLink(LinkList *list ,LinkList q){ /*删除链表的某结点*/ LinkList r; if(q==*list){ /*如果删除第一个结点*/ *list=q->next; free(q); } else{ /*删除其他结点*/ for(r=*list;r->next!=q;r=r->next); if(r->next!=NULL){ r->next=q->next; free(q); } } } void destroyLinkList(LinkList *list){ /*销毁一个链表*/ LinkList p,q; p=*list; while(p){ /*循环释放掉每一个链表结点*/ q=p->next; free(p); p=q; } *list=NULL; } main() { int e,i; LinkList l,q; q=l=GreatLinkList(1); /*创建一个链表结点，q和l指向该结点*/ scanf("%d",&e); while(e) /*循环地输入数据，同时插入新生成的结点*/ { insertList(&l,q,e) ; q=q->next; scanf("%d",&e); } q=l; printf("The content of the linklist\n"); while(q) /*输出链表中的内容*/ { printf("%d ",q->data); q=q->next; } q=l; printf("\nDelete the fifth element\n"); for(i=0;i<4;i++) /*将指针q指向链表第5个元素*/ { if (q == NULL) { /*确保此时链表的长度大于等于5，否则将是非法操作*/ printf("The length of the linklist is smaller than 5 !"); getche(); return; } q=q->next; } delLink(&l,q); /*找到链表中第5个元素，用q指向它，再删除q所指的结点*/ q=l; while(q) /*打印出删除后的结果*/ { printf("%d ",q->data); q=q->next; } destroyLinkList(&l); /*销毁该链表*/ getche(); } 本程序的执行过程如下：（1）应用函数GreatLinkList()创建一个只含有1个结点的链表，并向该结点中输入 数据。（2）然后通过函数insertList()向链表中插入新的结点，在插入结点的同时输入数据，直到输入0为止。数据从键盘终端输入。（3）然后打印出该链表中的数据。再通过循环使指针q指向该链表的第5个元素，调用函数delLink()删除q所指的结点，打印出删除元素后链表中的值。（4）最后调用destroyLinkList()函数释放掉链表所占据的内存空间。 本程序的运行结果如图1-8所示。图1-8 例1-3的运行结果1.4 栈 栈是一种重要的线性结构。它是前面讲过的线性表（顺序表、链表）的一种具体形式。也就是说，栈必须通过顺序表或者链表来实现。顺序表或者链表既可以像前面介绍的那样独立存在，组织和操作数据，同时它们也是一些特殊的数据结构（栈、队列……）的实现基础，其概念更宽泛一些。下面通过具体的介绍来深入理解栈的概念。 1.4.1 栈的定义 栈（stack）是一个后进先出（last in first out，LIFO）的线性表，它要求只在表尾进行数据的删除和插入等操作。也就是说，所谓栈其实就是一个线性表（顺序表、链表），但是它在操作上有一些特殊的要求和限制。首先，栈的元素必须先进后出，这与一般的顺序表不同。其次，栈的操作只能限定在这个顺序表的表尾进行。这就是栈的独特之处。对于栈来说，这个顺序表或者链表的表尾（也就是进行删除和插入等操作的地方）称为栈的栈顶（top），相应的表头称为栈底（bottom）。 栈形如一个子弹膛，最先压进去的子弹一定最后弹出，如图1-9所示。图1-9 栈的示意图 如图1-9所示，栈的本质就是一个线性表，只不过数据不能像一般的顺序表那样操作自如。数据必须从栈顶进入，还必须从栈顶取出，先进入栈中的数据再后进入栈中的数据的下面。最开始栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。 上面只给出了栈及其操作的形象描述。下面具体介绍如何定义一个栈，并在后续的小节中介绍栈的操作。 线性表有两种存储形式，即顺序表存储和链表存储。一般的栈都是用顺序表存储形式实现的，因此在这里只介绍顺序栈。 可以用以下的方式定义一个顺序栈。 typedef struct{ ElemType *base; ElemType *top; int stacksize; }sqStack; 这里定义了一个顺序栈sqStack类型，它包含3个数据项：base、top、stacksize。其中，base是指向栈底的指针变量。top是指向栈顶的指针变量，它们指向的数据类型为ElemType，这是压入栈中的数据的类型（可以是int、char等）。stacksize指示栈的当前可使用的最大容量。掌握了这3个数据，就相当于掌握了一个完整的栈。可以通过base和top对栈进行各种操作，通过stacksize判断栈的空间分配情况。 1.4.2 创建一个栈 创建一个栈有两个任务：一是在内存中开辟一段连续的空间，用做栈的物理存储空间；二是将栈顶、栈底地址赋值给sqStack类型变量（对象）的top和base域，并设置stacksize值，以便通过这个变量（对象）对栈进行各种操作。创建一个栈的代码如下： #define STACK_INIT_SIZE 100 initStack(sqStack *s)
试读结束[说明：试读内容隐藏了图片]