完整版：http://item.taobao.com/item.htm?id=5616898223 第一章 绪论 作者的话： 大部分同学在学习数据结构时，想必对数据结构课本里的伪代码多多少少有点不是很 清楚，特别是自己在动手编写算法的时候，明明知道算法的思路，但是编写出来的程序就 是不标准，可能在考试的时候就会吃大亏。所以在开始数据结构的旅程之前，我觉得有必 要将一些基本功提前告知你们，掌握了这些东西，在本章以后的章节中，才能以此为基础 来修炼更高深的武功。 本章概略 ▲ 针对考研数据结构的 C&C++语言基础以及代码书写规范 对于考研数据结构，需要 C 与 C++语言作为基础，但是又不需要太多，因此此处讲解 有针对性。现在我们面临的是研究生考试，要在答题纸上写代码，代码的评判者是阅卷老师， 而不是 TC，VC6.0 等编译器。如果之前你只熟悉在这些编译器下写代码，那你要看看这一 部分，这里教你怎么快速的写出能让阅卷老师满意的代码。 ▲ 算法的时间复杂度分析基础 为什么要特别注重这一块的讲解？在 09 年批阅数据结构算法那道题的时候，由于当时 阅卷的标准答案是教育部给出的，并且明确说明以此为标准答案，但是教育部给出的算法时 间复杂度太大，对于算法有研究的同学，可以很轻松的写出一个算法，并且时间复杂度远远 小于标准答案。教育部就是权威，没有办法，只能按照教育部的答案改，这样就导致了算法 牛人写出更完美的算法，却得了最低的分。也许是为了避免这种不公平的再次出现，10 年 的考试要求终于改了，考生必须对自己写的算法给出时间复杂度和空间复杂度，并以此来作 为评分的依据。所以这已经成为数据结构 45 分里面的必考内容，这一点的考察在图、排序、 查找这三章内体现的尤为明显，因此我会在本章先总体讲一下算法时间复杂度分析的基本方 法，并在以后章节中以题目的形式讲一些具体分析思路，这样考生逐渐的就会掌握考研要求 的算法复杂度分析方法。 ▲ 数据结构和算法的基本概念 这一部分介绍一些贯穿于整本书的基本概念。 1．1 针对考研数据结构的代码书写规范以及 C&C++语言基础 1．1．1 考研综合应用题中算法设计部分的代码书写规范 要在答题纸上快速的写出能让阅卷老师满意的代码，是有些技巧的，这与写出能在编译 器上编译通过的代码有所不同。为了说明这一点我们首先看一个例题： 设将 n（n>1）个整数存放到一维数组 R 中。设计一个算法，将 R 中的序列循环左移 P （ 0 //1 #define N 50 //2 using namespace std; //3 void Reverse(int R[],int l,int r) //4 { //5 int i,j; //6 int temp; //7 for(i=l,j=r;i=n) //17 cout<<"ERROR"<>L; //30 cin>>n; //31 for(i=0;i<=n-1;i++) //32 cin>>R[i]; //33 RCR(R,n,L); //34 for(i=0;i<=n-1;i++) //35 cout<=n) //14 cout<<"ERROR"<data;一般来说，用结构体变 量直接取分量，其操作用”.”，用指向结构体变量的指针来取分量，其操作用”->”。 这里再扩展一点，前边我们提到，如果 p 是指针（假设已经指向 x），*p 就是取这个变 量的值，a=*p;等价于 a=x;那么对于②中的 BT 指针，怎么用”.”来取其 data 值呢？类比 p，*BT 就是 BT 指向的变量，因此可以写成(*BT).data;（(*BT).data;与 BT->data 是等价的）。注意 *BT 外边要用括号括起来，不要写成*BT.data。在 C 或 C++语言中这 是一种好的习惯，在你不知道系统默认的运算符优先级的情况下，你最好依照自己所期望 的运算顺序加上括号。有可能这个括号加上是多余的，但是为了减少错误，这种做法是必要 的。对于与刚才那句，我所期望的运算顺序是先算*BT，即用”*”先将 BT 变成它所指的变 量，然后再用”.”取分量值。因此写成(*BT).data。比如这样一个式子 a*b/c，假设你不 知道系统会默认先算乘再算除，而你所期望的运算优先顺序是先算乘再算除，为了减少错误， 你最好是把它写成(a*b)/c，即便这里的括号是多余的。 完整版：http://item.taobao.com/item.htm?id=5616898223 （4）关于 typedef 和#define 1）typedef 有的书上在定义变量的时候会出现一些你在程序设计教材中从来没见过的诡异的数据 类型，比如严奶奶书上就有类似于 Elemtype A;的变量定义语句，这里的 Elemtype 是 什么类型，新来的同学常常会一头雾水。要说明这个问题，我们先来说明一下 typedef 的 用法。一句话，typedef 就是用来给现有的数据类型起一个新名字的，我们在结构类型定 义时用到过，如 typedef struct{……} TypeA;即为给 “struct{……}”起了一个 名字 TypeA，就好比你制作了计算机中的整型，给他起了个名字为 int。并且如果我想给 int 型起个新名字 A,就可以这样写 typedef int A;这样的话定义一个整形变量 x 的时 候 A x;就等价于 int x;在考研中 typedef 用的最多的地方就在结构型的定义过程中， 其他的地方几乎不用。你可以这样理解 typedef 是用来起名字的，新定义的结构型没有名 字，因此用 typedef 给它起个名字是有必要的，但是对于已有的数据类型，如 int，float 等已经有了简洁的名字，还有必要给它起个新名字吗？有必要，但不是在考研数据结构中。 为什么有必要，有兴趣的同学可以去查下资料，查完你会发现，typedef 对程序设计的贡 献很大，但是对于考研答卷，用处不大，所以大家对其用法不必深究。说到这里大家就明白 了，严奶奶的书上之所以有那么多大家不认识的数据类型，只不过是严奶奶悄悄的给我们认 识的数据类型起了新名字而已。 2）#define 在严奶奶的书上除了我们没见过的数据类型以外，还有一些东西我们也没见过，比如在 一个函数中她会写到 return ERROR； return OK；之类的语句，对于经常在编译器上 写代码的同学，乍一看到这种语句会十分的不爽，立马就会想，ERROR 和 OK 这样的东西能 编译通过？或者就是怀疑自己语言水平太差，严奶奶写的程序里边有太多自己看不懂的地方 了，信心大减。其实不然，和 typedef 一样，严奶奶悄悄的用#define 语句处理过 ERROR 或者 OK 之类的词了。其实 ERROR 和 OK 就是两个常量，作为函数的返回值，来提示用户函 数操作结果的。严奶奶初衷是想把 0,1 这种常作为函数返回标记的数字定义成 ERROR 和 OK（一般出错返回 0，成功返回 1），这样比起数字来更人性化，更容易理解，但结果却适 得其反，让新手们更困惑了。#define 对于考研数据结构可以说没有什么贡献，我们只要 认得它就行，写程序时一般用不到。比如#define MAX 50 这句，即定义了常量 MAX（此 时x=50;等价于x=MAX;）。在写程序大题的时候如果你要定义一个数组，如int A[MAX]; 加上一句注释：“/*MAX 为已经定义的常量，其值为 50*/”即可。没必要跑到你的程序最 前边去加上#define MAX 50 这一句，原因前边已经讲过。 严奶奶的书中有很多用自己加工过的代码书写的程序，和编译器上我们习惯的写法有很 大出入，所以对于新手较难理解。本书的作用在很大程度上就是做了一个翻译的角色，不过 是站在学生的角度把课本上用过于严谨以及专业化的词语描述的思想用通俗易懂的语言表 达给你而已。 2．函数 说明:只要是算法设计题，必用到函数，所以其中的一些注意事项这里有必要说一下。 （1）用函数来缩短代码 如果有一段较长的操作需要在一个函数中反复多次使用，那么你最好把这个操作做成一 个函数，在你要用的地方调用它，会节省很多答题空间。比如： void f() { ……//1 ……//2 完整版：http://item.taobao.com/item.htm?id=5616898223 ……//3 ……//4 ……//5 ……//6 ……//7 ……//8 } 这个函数中的 8 句组成了一个操作。这个操作在另一个函数（函数名为 F）中要多次用 到。此时我们就可以把这 8 句做成一个函数，当用到的时候调用即可，比如： void F() { f(); …… …… f(); …… …… f(); } 从上边可以看出，如果不用 f()函数，就得把 f()中的 8 行写 3 遍，使得 F()函数很 长。 （2）被传入函数的参数是否会改变 int a; void f(int x) { x++; } 上边声明的函数，它需要一个整型变量作为参数，且在自己的函数体中将参数做自增 1 的运算。执行完以下程序段之后 a 的值是多少呢？ a=0; //① f(a); //② 有些同学可能以为 a 等于 1。这个答案是错误的，可以这样理解，对于函数 f()，在调 用他的时候，括号里的变量 a 和句①中的变量 a 并不是同一个变量。在执行句②的时候， 变量 a 只是把自己的值赋给了一个在 f()的声明过程中已经定义好的整形变量，可以把这 个变量想象为上述声明过程中的 x，即句②的执行过程拆开看来是这样两句：x=a;x++;因 此 a 的值在执行完①,②两句之后不变。 如果我想让 a 依照 f()函数体中的操作来改变应该怎么写呢，这里就要用到函数的引 用型（这种语法是 C++中的，C 中没有，C 中是靠传入变量的地址的方法来实现的，写起来 比较麻烦且容易出错，因此这里采用 C++的语法），其函数声明方法如下： void f(int &x) { x++; } 这样就相当于 a 取代了 x 的位置，函数 f()就是在对 a 本身进行操作，执行完①②两 完整版：http://item.taobao.com/item.htm?id=5616898223 句后，a 的值由 0 变为 1。 上边讲到的是对针对普通变量的“引用型”，如果传入的变量是指针型变量，且在函数 体内要对传入的指针进行改变，则需写成如下形式： void f(int *&x) //指针型变量在函数体中需要改变的写法。 { x++; } 执行完上述函数后，指针 x 的值自增 1。 说明：这种写法很多同学不太熟悉，但是它在树与图的算法中应用广泛，在之后的章 节中考生要注意观察其与一般引用型变量的书写差别。 上边是单个变量作为函数参数的情况。如果一个数组作为函数的参数，该怎么写呢？传 入的数组是不是也有“引用型”一说呢？对于数组作为函数的参数，这里讲两种情况，一维 和二维数组。 一维数组作为参数的函数声明方法： void f(int x[],int n) { ……; } 对于第一个参数位置上的数组的定义只需写出两个中括号即可，不需要限定数组长度 （即不需要写成 f(int x[5],int n)，即便是你传入的数组真的是长度为 5），对于第二 个参数 n，是写数组作参数的函数的习惯，用来说明将来要传进函数加工的数组元素的个数， 并不是指数组的总长度。 二维数组作为参数的函数声明方法： void f(int x[][MAX]，int n) { ……; } 如果函数的参数是二维数组，数组的第一个中括号内不需要写上数组长度，而第二个中 括号内必须写上数组长度（假设 MAX 是已经定义的常量）。这里需要注意，你所传入的数组 第二维长度也得是 MAX，否则出错，比如： void f（int x[][5]） { ……; } int a[10][5]; int b[10][3]; f(a); //参数正确 f(b); //参数错误 要注意的是，将数组作为参数传入函数，函数就是对传入的数组本身进行操作，即如果 函数体内涉及到改变数组数据的操作，传入的数组中的数据就会依照函数的操作来改变。因 此，对于数组来说，没有“引用型”和“非引用型”之分，可以理解为只要数组作为参数， 都是引用型的。 完整版：http://item.taobao.com/item.htm?id=5616898223 （3）有返回值的函数 声明一个函数： int f(int a) { return a; } 在这个声明中我们可以看到，有一个 int 在函数名的前边，这个 int 是指函数返回值 是 int 型。如果没有返回值，声明函数的时候用 void，前边讲过的函数中已经有所体现。 返回值常常用来作为判断函数执行状态（完成还是出错）的标记，或者一个计算的结果。严 奶奶的书中出现过类似于下边这样的函数。 STATUS f(ELEMTYPE a) { if(a>=0) return ERROR; else return OK; } 对于一些基础稍差的同学来说，这个函数麻烦了，STATUS,ELEMTYPE,ERROR,OK 这 都什么东西，其实严奶奶在离这个函数很远的地方写过这些语句： #define ERROR 1 #define OK 0 typedef STATUS bool //这句中的 bool 是布尔型，只取两个值 //0 和 1，其实用 bool 用 int 型代替就可以， //所以对于考研 bool 用处不大。 typedef ELEMTYPE int 在那个函数前边加上这四句是否看懂了呢？看懂后可以把它翻译一下就能写出以下代 码： bool f(int a) //本行可换成 int f(int a) { if(a>=0) return 1; else return 0; } 上边这种写法是不是清楚明白了。严奶奶之所以要将程序写的如此个性，原因有两个， 一是上边那个自己另起的类型名或者常量名，都有着实际的意义，STATUS 代表状态，OK 代表程序执行成功，ERROR 代表出错，这样代码写的就更人性化。二是，如果我们在写一 个大工程，对于其中的一个变量，在整个工程中都已经用 int 型定义过了，但是工程现在 要求修改，将所有 int 型换成 char 型，这下麻烦就大了。如果你写成上边那种形式，将 int 型起个新名字 ELEMTYPE，在整个程序中凡是类似于 int x;的语句都写成 ELEMTYPE x;此时如果要统一更换数据类型，只需将 typedef ELEMTYPE int 这一句中的 int 换成 char 即可，这无疑是十分方便的事情，这就是 typedef 对于程序设计的意义所在 （#define 也能达到类似的目的）。但显然的是，这对考研答卷意义不大。 完整版：http://item.taobao.com/item.htm?id=5616898223 1．2 算法的时间复杂度与空间复杂度分析基础 1．2．1 考研中的算法时间复杂度杂谈 对于这部分，要牢记住一句话：将算法中基本操作的执行次数作为算法的时间复杂度。 这里我们所讨论的时间复杂度，不是执行完一段程序的总时间，而是其中基本操作的总次数。 因此对于一个算法进行时间复杂度分析的要点，无非是明确算法中哪些操作是基本操作，然 后计算出基本操作所重复执行的次数。在考试中算法题目里你总能找到一个 n，可以称为问 题的规模，比如要处理的数组元素的个数为 n，而基本操作所执行的次数是 n 的一个函数 f(n)（这里的函数是数学中的函数的概念，不是 C 或 C++语言中的函数的概念）。对于求其 基本操作执行的次数，就是求函数 f(n)。求出以后我们就可以取出 f(n)中随 n 增大增长 最快的项，然后将其系数变为 1 做为时间复杂度的度量，记为 T(n)=O(f(n)中增长最快的 项 / 此项的系数) ，比如 f(n)=2n3+4n2+100 ，则其时间复杂度为为 T(n)=O(2n3/2)=O(n3)。其实计算算法的时间复杂度， 就是给出相应的数量级，当 f(n) 与 n 无关时， 时间复杂度 T(n)=O(1)；当 f(n)与 n 是线性关系时，T(n)=O(n)；是平 方关系时，T(n)=O(n2)；以此类推。 说明： 中 较 时 的 下考研 常常要比 各种 间复杂度的大小，常用 比较关系如 ： O1≤Olog2n≤On≤nlog2n≤On2≤On3≤……≤Onk≤O2n 通过以上分析我们总结出计算一个算法时间复杂度的步骤如下： （1） 确定算法中的基本操作，以及问题的规模。 （2）根据基本操作执行情况计算出规模 n 的函数 f(n)，并确定时间复杂度为 T(n)=O(f(n)中增长最快的项/此项的系数)。 注意：有的算法中基本操作执行次数跟初始输入的数据有关。如果题目不做特殊要求， 一般我们依照使得基本操作执行次数最多的输入来计算时间复杂度，即将最坏的情况作为 算法时间复杂度的度量。 1．2．2 例题选讲 例题 1：求出以下算法的时间复杂度。 void fun(int n) { int i=1,j=100; while(i 为指向结点的指针。 （4）散列（或哈希）存储方法 该方法的基本思想是根据结点的关键字通过哈希函数直接计算出该结点的存储 地址。这种存储方法本质上 8．数据类型和变量 数据类型是一个值的集合以及定义在这个值集上的一组操作。 变量是用来存储值的所在处，它们有名字和数据类 代表这些值的位存储到计算 变量都具有数据类型，以决定能够存储哪种数据。 1．3．2 算法的基本概念 1．算法 算法可以理解为有基本运 成按照要求设计好的有限的确切 2．算法的 一个算法应该具有以下五个重要的特征： 1 一个算法必须保证执行有限步之后结束。 ）确定性 算法的每一步骤 完整版：http://item.taobao.com/item.htm?id=5616898223 （ 个或多个输入，以刻画运算对象的初始情况，所谓 0 个输入是指算 法本 笔和纸做有限次运算后也可完成。 目标 算法设计目标为正确性、可读性、健壮性和算法 其中算法效率通过算法的 时间复杂度和空间复杂度来描述。 （ 健壮性 好的容错性，能够对不合理的数据进行检查。 要是指算法的执行时间。对于同一个问题如果有多种算法可以求解， 执行 需要的最大存储空 间。 问题的规模有关。 一、选择题 的大小称为算法的（ ）。 A．效率 B. 复杂性 C. 现实性 D. 难度 复杂度取决于（ ） C. A 和 B 3.计 C. 解决问题的步骤序列 D. 调度方法 性、有穷性 定性、安全性 4． A 和 C 5. 下面 6. 空间 3）输入 一个算法有 0 身确定了初始条件。 （4）输出 一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法 是毫无意义的。 （5）可行性 算法中的所有操作都必须可以通过已经实现的基本操作机型运算，并在有限次内 实现，而且人们用 3 效率。 ．算法的设计 1）正确性 要求算法能够正确地执行预先规定的功能和性能要求。这是最重要也是最基本的 标准。 （2）可读性 要求算法易于人的理解。 （3） 要求算法有很 （4）高效率与低存储量需求 算法的效率主 时间短的算法效率高。算法的存储量指的是算法执行过程中所 高效率和低存储量这两者都与 习题心选 1. 算法的计算量 2. 算法的时间 A．问题的规模 B. 待处理数据的初态 算机算法指的是（1），它必须具备（2） 这三个特性。 (1)A．计算方法 B. 排序方法 (2)A．可执行性、可移植性、可扩充性 B. 可执行性、确定 C. 确定性、有穷性、稳定性 D. 易读性、稳 一个算法应该是（ ）。 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D． 关于算法说法错误的是（ ）。 A．算法最终必须由计算机程序实现 B. 为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 下面说法错误的是（ ）。 （1）算法原地工作的含义是指不需要任何额外的辅助 完整版：http://item.taobao.com/item.htm?id=5616898223 复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的算法 ，估算算法执行时间的一个上界 C E.循环队列 9． n) C．O(n2) D．O(log2 n) 10． --) r(j=1;j<=i;j++) 频度在最坏情况下是（ ）。 . O(n3) D. O(n2) 12． D．部分连续，部分不连续 13． D. 单链表 合应用题 1． （） （2）f2(n)=n2+1000n; （3）f3(n)=3n3+100n2+n+1; 分别写出相应的大 O 表示的运算时间。 少 mergesort(1,n),merge O(n)。 void mergesort(int i,int j) { esort(i,m); ort(m+1,j); merge(i,j,m);//本函数时间复杂度为 O(n) （2）在相同的规模 n 下， （3）所谓时间复杂度是指最坏情况下 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 ．线性结构、非线性结构 D．初等结构、构造型结构 8．以下哪一个术语与数据的存储结构无关？（ ）。 A．栈 B.哈希表 C.线索树 D.双向链表 在下面的程序段中，对 x 的赋值语句的频度为（ ）。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) x++; A． O(2n) B．O( 程序段 for(i=n-1;i>=1;i fo if(A[j]>A[j+1]) A[j]与 A[j+1]对换; 其中 n 为正整数，则最后一行的语句 A. O（n） B. O(nlogn) C 11．以下数据结构中，（ ）是非线性数据结构 A．树 B．队 C．栈 连续存储设计时，存储单元的地址（ ）。 A．一定连续 B．一定不连续 C．不一定连续 以下属于逻辑结构的是（ ）。 A．顺序表 B. 哈希表 C.有序表 二．综 有下列运行时间函数： 1 f1(n)=1000; 2. 下 mergesort 函数时间复杂度为 面函数 执行的时间复杂度为多 ? 假设函数调用被写为 { int m; if(i!=j) merg merges } } 完整版：http://item.taobao.com/item.htm?id=5616898223 习 讲题 选择题： 法时间复杂度的定义。算法中基本操作的重复执行次数就是算法的计算量， 将其大小作为算法的时间复杂度，因此选 B。 题考查算法时间复杂度的定义。算法时间复杂度即为基本操作执行次数，显然问题 在相同的规模下，与数据初 0 的计算速度显然要比两个因子都非 0 的情 。本题选 。 考查算法的概念。 计算机程序只是实现算法的一种手段，人用手工也可以完成。 项 B 算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤。程序 现特定目标或解决特 问题而用计算机语言编写的命令序列的集合。两者显然是不同 的概念。 算法的时间复杂度和空间复杂度的相关知识。 可执行程序除了需要内存空间来寄 本身的指令、常数、变量和输入数据外， （输入数据）来说是个常数，那我么 （ n n0 |O(f(n) )| M |f(n)|， 结构上的原 绝对 8.A 题考查基本数据 构 1 3 7 项，哈希是算法，哈希存储方法本质上是顺序存储方法的扩展。哈希表本质上是顺序 心 1.B 本题考查算 2.C 本 规模越大，基本操作的次数越多，因此时间复杂度与规模有关。 关，比如两个数相乘，有一个因子为 时态也有 况要快 C 3. C、B 本章算法基本概念中已讲过。 4.B 本章算法基本概念中已讲过。 5.D 本题 选项 A 选 是为实 定 明选项 C 显错误，课本概念中已经讲过。 6.C 本题考查 （ ）一1 个 存 额外空间，如果这个额外空间相对于问题的规模还需要 们就称之为原地工作。因此（1）不对。 ） 节考研中的算法时间复杂度杂谈中已经讲过。2 1.2.1 （3）对于 O(1),O(log2n),O(n)等，O 的形式定义为：若 f(n)是正数 n 的一个函数， 则 O(f(n))表示存在一个正常数 M，使得当 ≥ 时满足 小于等于 × 也就是 给出了函数 f(n)的一个上界。O(f(n)) ）这句话是严版数据 是（4 句，大多数情况下应该 这样，但是不能说的这么 ，得看编译链接后的最终的机器指令，这些指令操作的次数越少，说明该语言在某种编 译链接环境下效率较高，实际上即使同一种语言在不同的编译环境下，也有可能不同。 综上，本题答案为 C。 7.C 1.3．1 节数据结构的概念中已经讲过。 本 结 。 A 项，栈是逻辑结构。 1. . 节第 个讲解中可以知道。 从 B 项，线索树是在链式存储结构的基础上对树进行线索，与链式存储结构有关。 项，双向链表也是说明线性表是以链式结构存储。C D 完整版：http://item.taobao.com/item.htm?id=5616898223 表的扩展。 E 项，循环队列是建立在顺序存储结构上的。 说明：这种题目还有一种比较直观的解法，要判断是否与数据的存储结构无关，只需 看看这 是和数据 明是用顺序栈还是用链栈来实现， 所以 本题考查算法时间复杂度的计算。 2，因此时间复杂度是 2 。 的核心语句，最坏情况下时 度为 O(n2)。 11.A 题考查基本数据结构。树是一种分支结构，显然不属于线性结构。 理结构。顺序存储结构要开辟一片连续的存储空间，结合 1.1.3 解可知本题选 A 题考查数据的物理结构。有序表指出了表中数据是有一定逻辑顺序排列的，是一种 构。 题： 根据 1.1.2 节中公式得： O(1000/1000)=O(1) 2/1)=O(n2) （ 3) 2. 函数中，merge 时间复杂度为 O(n)因此 merge 内基 本操 数基本操作次数设为 f(n)，则有： f(n/2)+cn n………………………………………………………………① ，f(1)=O(1)………………………………………………② 由①②可知，当 n=2k 即 k=log2n 时 种结构到底有没有具体到使用顺序存储还是链式存储，如果已经具体到了那就一定 存储的 结构有关，比如 A 选项中的栈并没有说 是逻辑结构。B 选项中的线索树很明显是要用链式来实现（现在不清楚没关系，等学完 树那一章就理解了），故与数据的存储结构有关，以此类推。 9.C f(n)=n O(n ) 10.D 本题考查算法时间复杂度的计算。此算法为冒泡排序算法 间复杂 本 12.A 本题考查数据的物 第 7 个讲 13.C 本 逻辑结 综合应用 1．答案： （1）T1(n)= （2）T2(n)=O(n 3）T3(n)=O(3n3/3)=O(n 分析： 显然规模为 n，基本操在 merge 作次数可设为 cn，mergesort 函 f(n)=2 =22f(n/4)+2cn =23f(n/8)+3cn =…… =2kf(n/(2k))+kc 由 mergesort 函数可知 f(n)=n+kcnlog2n 完整版：http://item.taobao.com/item.htm?id=5616898223 因此时间复杂度 T(n)=O(nlog2n) 作者 很新的新手（至少要稍微有一点 C 或 C++语言基础，如 果连这 ），到这里为止，我已经把考研数据结构要 用到的全部基本功教给你了，对于考研数据结构，要想拿高分，有很多学习的风格， 本书 的话：假如你是一个 个都没有的话，先去读谭浩强的 C 则走了一种让广大考生都容易接受的风格，希望读者能适应这种风格，这样你的 学习会变的轻松。下面就让我们从下一章开始，把考纲所要求的知识点一一击破。 完整版：http://item.taobao.com/item.htm?id=5616898223 第二章 大纲要求 ▲ 线性表的定义和基本操作 的实现 1. 顺序存储结构 线性表的 (这一部分通过线性表算法中的各种题目来讲解，不单独作为一 ) 说明：本 有些知识点大纲没有明文写出，但是掌握了这些知识 点对本章 其他章中很多知识点的理解都有帮助。因此本章会添加一些必须的知识点， 以帮助你 理解，虽然大纲中没有涉及这些知识点。 线性表是具有相同特性数据元素的一个有限序列。该序列中所含元素的个数叫做线性表 的长度，用 n 表示（n≥ 表，空表也可以作为 一个线性表。 线性表可以是有序的也可以是无序的， 如果学生是按照身高来排队，矮在前，高在后，这就体现了线性表的有序性。 除了队 头和队尾的学生以外， 紧挨着站在其前后的学生都只有一个，这是 很显然的事情。 （ 表就是把线性表 素按照其逻辑顺序，依次存储到存储器中从指定存储 i+1 i 线性表 ▲ 线性表 2. 链式存储结构 3. 应用 节 章大纲要求过于简略， 以及 更好的 2．1 线性表的基本概念与实现 1.线性表的定义 0）；注意 n 可以等于零，表示线性表是一个空 线性表是一种简单的数据结构，我们可以把它想象成一队学生。学生人数对应了线性表 的长度，学生人数是有限的，这里体现了线性表是一个有限序列；队中所有人的身份都是学 生，这里体现了线性表中的数据元素具有相同的特性； 2.线性表的逻辑特性 继续拿定义中的例子来说明。在一队学生中，只有一个学生在队头，同样只有一个学生 在队尾。在队头的学生的前面没有其他学生，在队尾的学生的后边也没有其他学生。 对于其他的每一个学生， 线性表也是这样，只有一个表头元素，只有一个表尾元素，表头元素没有前 驱，表尾元素没有后继，除表头和表尾元素之外其他元素只有一个直接前驱，也只有一个直 接后继。以上就是线性表的逻辑特性。 3.线性表的存储结构 线性表的存储结构有顺序存储结构和链式存储结构两种。前者称为顺序表，后者称为 链表。下边就通过对比来介绍这两种存储结构。 1）顺序表 顺序 中的所有元 位置开始的一块连续的存储空间中。这样线性表中第一个元素的存储位置就是指定的存储位 置，第 个元素的存储位置紧接在第 个元素的存储位置的后面。 完整版：http://item.taobao.com/item.htm?id=5616898223 （ 的地址信息方便的 找到后继结点的位置。 房间的长度为 1。因此我们只要知道 0 点的位置，然后通过房间号 这就是顺序表的第一个特性，随机访问特性。由 下 图 我们还可以看出， 个房 即连续的占用了一片空间， 再看链表，如图所示，房间是散落存在的，每个房间的右边有走向下一个房间的方向 通过图 结点位置的 散落的分布在存储器中的，所以链表支持存储空间的动态分配，即在需要新的结点时再进行 移动多个 而链表就无需这样，如图 的链表， 图 2.1 顺序表和链表的比较 链表有如下 5 种形式（在程序题目中用到的链表结点的 c 语言描述将在以后的章节中 介绍）： （1）单链表 图 2.2 带头结点的单链表 2）链表 在链表存储中，每个结点不仅包含所存元素本身的信息，还包含元素之间逻辑关系的 信息，即前驱结点包含后继结点的地址信息，这样就可以通过前驱结点中 两种存储结构的比较： 顺序表就好像图 2.1(a)所示的一排房间，每个房间左边的数字就是该房间离 0 点的距 离同时也代表了房间号， 就马上可以找到任何一个房间的位置， 5 间所占用的地皮是紧挨着的， 并且地皮 的块数 6 是确定的，当我们在地皮上布置新的房间或者拆掉老的房间（即对顺序表的操作 过程中）地皮的块数不会增加也不会减少。这就是顺序表的第二个特性，即顺序表要求占用 连续的存储空间，存储分配只能预先进行，即静态分配，一旦分配好了，在对其操作过程中 不变。 指示箭头。因此如果我们想访问最后一个房间，就必须从第一个房间开始，依次走过前三个 房间才能来到最后一个房间，而不能直接得出最后一个房间的位置，即链表不支持随机访问。 2.1(b)我们还可以知道，链表中每一个结点需要划出一部分空间来存储指向下一个 指针，因此链表中结点的存储空间利用率较之顺序表稍低一些。链表中结点是 空间划分，而不需要一次性的划分所有所需空间给链表。 图 2.1(a)顺序表中最右边的一个表结点空间代表没有被利用（即顺序表还有剩余空间 来注入新数据），如果我们想在 1 号房间和 2 号房间之间插入一个房间，则必须将 2 号以后 的房间都往后移动一个位置（假设房间是可以随意搬动的），即顺序表做插入操作的时候要 如果想在第一个和第二个房间之元素。 2.1(b) 间插入一个新房间，则只需改动房间后边的方向指示箭头即可，将第一个房间的箭头指向新 插入的房间，然后将新插入的房间的箭头指向第二个房间即可，即在链表中进行插入操作无 需移动元素。 完整版：http://item.taobao.com/item.htm?id=5616898223 在每个结点中除了包含数据域外，还包含一个指针域，用以指向其后继结点。如图 2.2 所示，即为带头结点的单链表。这里要区分一下带头结点的单链表和不带头结点的单链表。 1）带头结点的单链表中头指针 head 指向头结点，头结点的值域不含任何信息，从头 结点的后继结点开始存储信息。头指针 head 始终不等于 NULL，head->next 等于 LL 的时候链表为空。 2）不带头结点的单链表其中的头指针head直接指向开始结点，即图2.2中的结点A1， 当 h 而不 表中第一个结点，即图 2.2 中的 head 指针。而头结点是带头结点的 链表 图 2.3 双链表 单链表只能由开始结点走到终端结点，而不能由终端结点反向走到开始结点。如果要求 输出从终端结点到开始结点的数据序列，则对于单链表来说操作就非常麻烦。为了解决这类 问题我们构造了双链表。如图 2.3 所示，即为带头结点的双链表。双链表就是在单链表结 点上增添了一个指针域，指向当前结点的前驱。这样就可以方便的由其后继来找到其前驱， 而实现输出终端结点到开始结点的数据序列。 同样，双链表也分为带头结点的双链表和不带头结点的双链表，情况类似于单链表。带 头结 图 2.4 循环链表 知道了单链表的结构之后，循环单链表就显得比较简单了，只要将单链表的最后一个指 针域（空指针）指向链表中第一个结点即可（这里之所以说第一个结点而不说是头结点是因 为，如果循环单链表是带头结点的则最后一个结点的指针域要指向头结点；如果循环单链表 不带头结点，则最后一个指针域要指向开始结点）。如图 2.4 所示，即为带头结点的循环单 链表。循环单链表可以实现从任一个结点出发访问链表中任何结点，而单链表从任一结点出 发后只能访问这个结点本身及其后边 结点的循环单链表当 head 等于 hea NU ead 等于 NULL 的时侯链表为空。 总之，两者最明显的区别是，带头结点的单链表有一个结点不存储信息，只是作为标记， 带头结点的单链表所有结点都存储信息。 注意：在题目中要区分头结点和头指针，不论是带头结点的链表还是不带头结点的链 表，头指针都指向链 中的第一个结点，只作为链表存在的标志，结点内不存信息。 （2）双链表： 点的双链表 head->next 为 NULL 的时候链表为空。不带头结点的双链表 head 为 NULL 的时候链表为空。 （3）循环单链表 的所有结点。带头 d->next;时链表为空；不带头结点的循环单链表当 head 等于 NULL 时链表为空。 完整 表中 双链 hea NUL 整版：http: （4）循环双 和循环单链 中第一个结点 链表同样有带 ad->prior LL 的时候为空 上述前 4 种 单链表： 单链表就像 双链表： 双链表就像 循环单链表 循环单链表 //item.taob 双链表 链表类似，循环 点，将链表中 带头结点和不 两个指针都等 空。 种链表可以用 像图 中(a) 的 像图(b)中的双 表： 表就像图(c) bao.com/ite 图 2 环双链表的构 第一个结点 不带头结点之 等于 head 时 用 4 种道路来 的单行车道， 双向车道，车 的环形车道， em.htm?id= 2.5 双循环链 构造源自双链 的 prior 指 之分。带头结 时链表为空， 来形象的比喻 (a) 只允许车辆往 (b) 车辆既可以从 (c) ，车辆可沿着 =561689822 链表 链表，即将终 指针指向终端 结点的循环 不带头结点 喻一下，如以下 往一个方向行 从左往右行驶 着一个方向行 23 终端结点的 n 端结点，如图 双链表当 h 点的循环双链 下图组： 行驶。 驶，又可以从 行驶在这条车 next 指针指指 2.5 所示。 向链 循环 head->nextt 和 等于表当 head链 从右向左行驶。 驶 道上。 车 完整版：http://item.taobao.com/item.htm?id=5616898223 循环双链表： (d)的双向环形车道，车辆可以沿着 2 个方向行驶在这条车道上。 （5）静态链表 这种链表借助一维数组来表示，如图 2.6 所示。 图 2.6 静态链表的表示 图 2.6 中左图是静态链表，右图是其对应的一般链表。一般链表结点空间是来自于整 个内存，静态链表则来自于一个结构体数组，数组中每一个结点含有两个分量，一个是数据 元素分量 data，另一个是指针分量，指示了当前结点的直接后继结点在数组中的位置（这 和一般链表中 next 指针的地位是同等的）。 说明：在考研中经常要考到顺序表和链表的比较，这里给出一个较为全面的答案： （1）基于空间的比较： 存储分配的方式： 顺序表的存储空间是静态分配的。 链表的存储空间是动态分配的。 存储密度(存储密度= 结点数据域所占的存储量/结点结构所占的存储总量)： 顺序表的存储密度 =1。 （对于顺序表一般只答随机存取即可） (d) 循环双链表就像图 链表的存储密度<1（因为结点中有指针域）。 （2）基于时间的比较： 存取方式： 顺序表可以随机存取，也可以顺序存取 完整版：http://item.taobao.com/item.htm?id=5616898223 链表是顺序存取的。 插入/删除时移动元素个数： 移动近一半元素。 针。 对顺序表 度分析 具有 ），插入一个元素所进行的平均移动个数为多少（假设 新元素插 因为 数，这就是告诉我们要计算移动个数的期望。对于本题要 计算 插入元素时所对应的元素移动个数以及在每个位 置发生插 1 求 可能性都是相同的，有 n 个可 p=1/n。 个元素之后，则需要将 i 元素之后的所有元素往后移 动一个位置，因此移动元素个数为 n-i。 由 1 和 2 知，移动元素个数的期望为： 顺序表平均需要 链表不需要移动元素，只需要修改指 进 插入和 算法时间复杂行 删除 ： n 个元素的顺序表（如下图 入在表中每个元素之后）。 题目要计算平均移动个 期望的话就要知道在所有可能的位置 入操作的概率。 概率： 因为插入位置的选择是随机的，所以所有位置被插入的 插入位置，所以任何一个位置被插入元素的概率都为 2 求对应于每个插位置需要移动的元素个数： 假设要把新元素插入在表中第 i 即要移动近一半元素，由此即可以知道，插入和删除算法的平均时间复杂度为 O(n)。 2． 义一个整型常量 MAX，值为 100。 1.顺序表的结构定义 typedef struct int data[MAX]; //存放顺序表元素的数组（默认是 int 型，可根据题目要 / int 换成其他类型）。 int length; }Sqlist; // 类型的定义。 2．2 线性表的基本操作 2．1 线性表的定义 #define MAX 100 //这里定 { /求将 //存放顺序表的长度。 顺序表 完整版：http://item.taobao.com/item.htm?id=5616898223 图 2.7 顺序表 如图 2.7 所示，一个顺序表包括一个存储表中元素的数组 data[]，和一个指示元素 个数的变量 length。 说明：在考试中用的最多的顺序表的定义并不是这里讲到的结构型定义，而是如下这 种形式： int A[MAX]; int n; 简洁一些。 t LNode 中存放结点数据域（默认是 型）。 指向后继结点的指针。 }LNode; // 单链表结点类型。 typedef struct DLNode { int data; //data 中存放结点数据域（默认是 int 型） struct DLNode *prior; //指向后继结点的指针 struct DLNode *nex 针 //定义单链表结点类型 C 语言描述，希望考生牢记并且可以默写， 这是完成本章程序设计题目所必须的最基本的东西。 上边这两句就定义了一个长度为 n，表内元素为整数的线性表。显然在答卷的时候这种 定义方法要比定义结构体 2.单链表结点定义 typedef struc { int data; //data int struct LNode *next; // 定义 图 2.8 单链表结点结构图 3.双链表结点定义 t; //指向前驱结点的指 }DLNode; 图 2.9 双链表结点结构图 说明：以上就是本章所需所有数据结构的 完整版：http://item.taobao.com/item.htm?id=5616898223 2．2．2 顺序表的算法操作 说明：这一部分我们采取先讲例题，然后从例题中总结出这部分考研所的需基知识点。 例题 1 已知一个顺序表 L，其中的元素递增有序排列，设计一个算法插入一个元素 x （x 为 int 型）后保持该顺序表仍然递增有序排列（假设插入操作总能成功，即插入后表 长不会大于 ）。 有序的插入位置。 以及其后的元素往后移动一个位置，然后将 x 放入腾出 的位 说明：本书中如果不做特殊说明则默认数组元素的存放从下标 1 开始，0 号空位置不 存数据以方便操作。 操作一：因为顺序表 L 中的元素是递增排列，所以我们可以从小到大逐个扫描表中元 素，当找到第一个比 x 大的元素时，将 x 插入在这个元素之前即可。如上图所示，12 为要 插入元素，从左往右逐个进行比较，当扫描到 13 的时候发现 13 是第一个比 12 大的数， 因此 12 应插入在 13 之前。 由此我们可以写出以下函数，本函数返回第一个比 x 大的元素的位置： int LocateElem (Sqlist L,int x) ; //如果小于则返回当前位置 i 不存在比 x 大的元素，则应 MAX 分析： 由题干可知，解决本题需完成两个操作。 一：要找出可以让顺序表保持 二：将第一步中找出的位置上 置上。 其执行过程图下： { int i; for(i=1;i<=L.length;i++) if(x=p;i--) L.data[i+1]=L.data[i]; //从右往左逐个将元素右移一个位置。 L.data[p]=x; //将 x 放在插入位置 p 上。 //表内元素多了一个，因此表长自增 1。 体现了考研中顺序表算法部分要求掌握的以下两个知识点： （1）按元素值的查找算法。 在顺 理），并返回其下标，代码如下。 0 置上插入新的元素 e。如果 p 的输入不正 确， 插入失败；如果 p 的输入正确则将顺序表第 p 个元素及以后元素右移一 个位置，腾出一个空位置插入新元素，顺序表长度增加 1，插入操作成功，返回 1。 //而退 之后// 的位置，同样也是正确的插入位置）。 后，将插入位置及其以后的元素向后移动一个元素 。一 答案是先移动最右边的元素，如果先移动最左边的元素则右边的元素会被 L.length++; } 本题 序表中查找第一个元素值等于 e 的元素（与上题中查找第一个比 x 大的元素是同 样的道 int LocateElem (Sqlist L,int e) { int i; for(i=1; i<=L.length;i++) if(e==L.data[i]) ）。return i; //找到返回下表（下表均大于 没return 0; // 找到返回 0，作为标记，因为 0 位置上不存放元素。 } （2）插入数据元素的算法 序表 L 的第 p（1≤p≤length+1）个位在顺 则返回 0，代表 完整版：http://item.taobao.com/item.htm?id=5616898223 插入操作 int ins { int i; +1||L.length==MAX)//位置错误或者表长已经达到 顺序表的最大允许值， 插入 ，返回 。 // x p 表内元素多了一个，因此表长自增 1。 插入成功返回 1。 例题 ，否则返回 0，并将 分析： 要删除表 素逐个往前移动一个位置，将 位置 元素插入的算法，本算法写起来就相对 只需将插入操作中的元素右移改成元素左移即可，右移的时候需要从最右边的元素开 始移动，这里很自然想到左移的时候需要从最左边的元素开始移动。 由此可以 lis &e)// 0; //位置不对返回 0，代表删除不成功。 //删除成功返回 1。 这是考研 是考生必须熟练掌握的。 顺序表中还剩下两个比较简单的算法操作在这里稍微一提： （1） 只需 //p 值越界错误，返回 0 代码如下： ert(Sqlist &L,int p,int e) if(p<1||p>L.length return 0; // 此时 不成功 0 for(i=L.length;i>=p;i--) L.data[i+1]=L.data[i];//从后往前逐个将元素往后移动一个位置。 将 放在插入位置 上。L.data[p]=e; L.length++; // return 1; // } 2 序表 L 中下标为 p（1≤p≤length）的元素，成功返回 1 被删除元素的值赋值给 。 删除顺 e 中下标为 的元素，只需将其后边p 的元 p 上的元素覆盖掉，就达到了删除的目的。明白了上述 容易。 写出以下代码： tDelete(Sqlist &L,int p,int 需要改变的变量用引用型。int { int i; if(p<1||p>L.length)return e=L.data[p]; //将被删除元素赋值给 e。 for(i=p;i<=L.length;i++) //从p 位置开始将其后边的元素逐个前移一个位置。 L.data[i]=L.data[i+1]; L.length--; //表长减 1。 return 1; } ：通过以上两个例题，我们可以总结出顺序表的查找，插入和删除三种算法操作。说明 中的重点， 初始化顺序表的算法： 将 length 设置为 0。 要发生改变所以用引用型void InitList(Sqlist &L) //L 本身 { L.length=0; } （2）求指定位置元素的算法 用 e 返回 L 中 p（1≤p≤length）位置上的元素 int GetElem（Sqlist L,int p,int &e）//要改变所以用引用型 { if(p<1||p>L.length) 完整版：http://item.taobao.com/item.htm?id=5616898223 return 0; e=L.data[p]; 2． 说明则链表都是含有头结点的链表） 是 其中元素递增有序。设计一个算法将 A 中的结点组成。 已知 有序，怎样使归并后的 C 中元素依然有序呢。我们可以从 A， B 中挑出 ，这样当 A，B 中所有元素都插入 C 中的时候，C 一定是 递增有序的。哪一个元素是 A，B 中最小的元素呢？很明显，由于 A，B 是递增的，所以 A 中的最小元素是其开始结点中的元素，B 也一样。我们只需从 A，B 的开始结点中选出一个 与 中的元素有可能一个已经全部被插入到 A CB 说明 经过以上分析我们可以写出如下代码： //r 指向 C，因为此时头结点也是终端结点。 //当 p 与 q 都不空时选取 p 与 q 所指结点中的较小 的终端节点，作为接纳新结 点的 点以便于接受下一个新 结点，这 /*以下两个 链接在 C 的尾部*/ if( N r->n if( N r->next=q; } return 1; } 2．3 单链表的算法操作（本书中如果没有特殊 例题 归并 3 A 和 B 两个单链表（带表头结点）， 和 B 成一个按元素递增有序的链表 C，C 由 A 和 B 分析： A，B 中的元素递增 C 的尾部最小的元素插入 较小的来插入 C 的尾部即可。这里还需注意，AB C 中，另一个还没有插完，比如 中所有元素已经全部被插入到 中而 还没有插完，这 B 中所有元素都大于 C 中元素，因此只要将 B 链接到 C 的尾部即可，如果 A 没有插完 则用类似的方法来解决。 void merge(LNode *&A,LNode *&B,LNode *&C) { LNode *p=A->next; //p 来跟踪 A 的最小值结点。 LNode *q=B->next; //q 来跟踪 B 的最小值结点。 LNode *r; //r 始终指向 C 的终端结点。 C=A; //用 A 的头结点来做 C 的头结点。 C->next=NULL; free(B); //B 的头结点已无用，则释放掉。 r=C; while(p!=NULL&&q!=NULL) { //者插入 C 的尾部。 /*以下的 if else 语句中，r 始终指向当前链表 一个媒介，通过它新结点被链接入 C 并且重新指向新的终端结 里体现了建立链表的尾插法思想。*/ if(p->data<=q->data) { p; p=p->next; r->next= r=r->next; } else { r->next=q; q=q->next; r=r->next; } } r->next=NULL; if p!= 语句将还有剩余结点的链表 ULL) ext=p; ULL) q!= 完整版：http://item.taobao.com/item.htm?id=5616898223 知识点总结： 例题.3 中涵盖了两个知识点，一是尾插法建立单链表，二是单链表的归并操作。上边 的程序就是单链表归并操作的标准写法，希望同学们熟练掌握，下边我提取出尾插法建立单 链表的算法，具体如下。 a e *&C,int a[],int n) //要改变的变量用引用型。 用来指向新申请的结点， r 始终指向 C 的终端结点。 //r 指向头结点，因为此时头结点就是终端结点。 for(i=1;i<=n;i++) //循环申请 n 个结点来接受数组 a 中的元素。 s->data=a[i]; // a 。 //r 指向终端结，点以便于接纳下一个到来的结点。 经装 链表 C 中，C 的终端结点的指 的建立链 的算法是头插法， 码如下： { /* */ ->next;//s 所指新结点的指针域 next 指向 C 中的开始结点。 t=s;//头结点的指针域 next 指向 s 结点，使得 s 成为了新的开始结点。 入链表的前端，因此新建立的链表中元素的次序和数组 中的元素的次序是相反的。 .3 的题干，将归并成一个递增的链表 C 将插入过程改成头插法即可 C s C 的前 端。 尾插法建立单链表： 储在数组 中，用尾插法建立链表 C。假设有 n 个元素已经存 void CreatelistR(LNod { LNode *s,*r; //s int i; C=(LNode *)malloc(sizeof(LNode));//申请 C 的头结点空间。 C->next=NULL; r=C; { s=(LNode*)malloc(sizeof(LNode)); //s 指向新申请的结点。 用新申请的结点来接受 中的一个元素 r->next=s; //用 r 来接纳新结点。 xt; r=r->ne } 数组 a 中所有的元素都已 入 r->next=NULL; // //针域置为 NULL，C 建立完成。 } 尾插法，与尾插法对应 表 代以上是 void CreatelistF(LNode *&C,int a[],int n) { LNode *s; int i; =(LNode*)malloc(sizeof(LNode)); C C->next=NULL; for(i=1;i<=n;i++) s=(LNode*)malloc(sizeof(LNode)); s->data=a[i]; 下边两句是头插法的关键步骤。 s->next=C C->nex } } 在上述算法中不断的将新结点插 假如这里修改一下例题a 改为归并成一个递减的链表 C。怎么来解决呢？答案是显然的， 解决。代码如 追踪 的终端结点，用 来接受新的结点插入链表下，这里不需要 r 完整版：http://item.taobao.com/item.htm?id=5616898223 归并成递减的单链表算法： void merge(LNode *&A,LNode *&B,LNode *&C) { LNode *p=A->next; free(B); NULL) if(p->data<=q->data) ; next=s; 循是和求递增归并序列不同的地方，必须将剩余元素逐个插入 C 的头 部才能得到最终的递减序列。*/ =NULL) t; xt=s; (q!=NULL) ; >next=s; 了单链表的结点插入操作，此操作很简单，但有一点需要注意。 假设 结点，要将 s 所指结点插入 p 所指结点之后的操作如下： =s; LNode *q=B->next; LNode *s; C=A; C->next=NULL; while(p!=NULL&&q!= { /*下边这个 if else 语句体现了链表的头插法*/ { s=p;p=p->next; s->next=C->next C->next=s; } else { s=q; q=q->next; s->next=C->next; C-> } } /*下边这两个 while(p! { s=p;p=p->next; s->next=C->nex C->ne } while { s=q;q=q->next; s->next=C->next C- } } 上边头插法的程序中提到 p 指向一个 s->next=p->next; p->next 完整版：http://item.taobao.com/item.htm?id=5616898223 2.10 插入操作过程图 语句能不能颠倒一下顺序写成 p->next=s;s->next=p->next; 呢？显然是不可以的，因为第一句 p->next=s;虽然将 s 链接在 p 之后，但是同时也丢失 了 p 直接后继结点的地址（p->next 指针原本所存储的 p 直接后继结点的地址在没有被转 存到其他地方的情况下被 s 所覆盖，而正确的写法中，p->next 中的值在被覆盖前被转存 在了 s->next 中，因而 p 后继结点的地址依然可以找到），这样链表断成了两截，没有满 足将 s 插入链表的要求。 与插入结点对应的是删除结点，也比较简单，要将单链表的第 i 个结点删去，必须先 在单链表中找到第 i-1 个结点，再删除其后继结点。如下图所示，若要删除结点 b，为了 实现这一逻辑关系的变化，仅需要修 设 p 为指向 a 的指针。则只 需将 2.11 删除操作过程图 这里还需注意，在考试答卷中，删除操作要释放所删除结点的内存空间，即完整的删 除操作应该是这样： q=p->next; p->next=p->next->next; free（q）;//调用 free 函数来释放 q 所指结点的内存空间。 掌握了单链表中结点删除的算法后，下边再看一个例题。 例题 2 查找链表 C（带头结点）中是否存在一个值为 x 的结点，存在就删除之并返回 1，否则返回 0。 分析： 对于本题需要解决两个问题，一是要找到值为 x 的结点；二是将找到的结点删除。问 题一引出了本章要讲的单链表中最后一个重要操作，链表中结点的查找。为了实现查找，我 们定 链表一直走到表尾，每来到一个新结点就检测其值是 否为 一 已经 过。 注意：以上插入操作 改结点 a 中的指针域。假 p 的指针域 next 指向原来 p 的下一个结点的下一个结点即可。即 p->next=p->next->next; 义一个结点指针变量 p，让他沿着 ，是则证明找到，不是则继续检x 测下 个结点。 当找到 为 的 后就是 内 讲值 x 结点 删除操作的 容，如何删除上面 完整版：http://item.taobao.com/item.htm?id=5616898223 由此可以写出以下代码： int SearchAndDelete(LNode *&C,int x) if(p->next->data==x) =NULL) ext->next; q); } 中之所以要使 p 指向所要删除结点的前驱结点而不是直接指向所要删 点必须知道其前驱结点的位置，这在之前删除操作的讲 中 经 操作部分所涉及的最重要的知识点都已经讲 完 考生务必要熟练掌握以上内容。下边要介绍的是双链表，循环链表，循环双链表的操 作。这些内容 ，常以选择题的形式出现，重要性不如以上两部分内容， 分内容的基础上稍加变动而来的，容易理解。 2 4 结点 for(i=1;i<=n;i++) s=(DLNode*)malloc(sizeof(DLNode)); //创建新结点 { LNode *p,*q; p=C; /*查找部分开始*/ while(p->next!=NULL) { break; p=p->next; } /*查找部分结束*/ if(p->next= return 0; else { /*删除部分开始*/ q=p->next; p->next=p->n free( /* */ return 1; 删除部分结束 } 说明：以上程序 除结点本身，是因为要删除一个结 解 已 体现。 到此为止考研中对于顺序表和单链表算法 解 。 考研中虽然也会涉及 并且这些内容是在上述两部 2． ． 双链表的算法操作 （1）采用尾插法建立双链表 void CreateDlistR(DLNode *&L,int a[],int n) { DLNode *s,*r; int i; L=(DLNode*)malloc(sizeof(DLNode)); L->next=NULL; r=L; //和单链表一样 r 始终指向终端结点，开始头结点也是尾 { s->data=a[i]; 完整版：http://item.taobao.com/item.htm?id=5616898223 /*下边 3 句将 s 插入在 L 的尾部并且 r 指向 s， s->prior=r; 这一句是和建立单链 双 较，若找 这 x) } 束）因此这一句可以 的种情况统一。 插入一个结点 s，其操作语句描述为： 指针变化过程如图 图 2.12 双链表结点插入过程图 说明：不知道大家有没有注意到在插入时，如果按照上面的顺序来插入，可以看成是 一个万能的插入方式。不管怎样，先将要插入的结点两边链接好，这样有什么好处？对了， 就是可以保证不会发生链断之后找不到结点的情况。所以请考生们一定要记住这种万能插 表不同的地方。*/ ext=s; r->n s->prior=r; r=s; } r->next=NULL; } （2）查找结点的算法 为 x 的结点。从第一个结点开始，边扫描边比在 链表中查找第一个结点值 到 样的结点，则返回结点指针，否则返回 NULL。算法代码如下： DLNode* Finfnode(DLNode *C,int x) { DLNode *p=C->next; NULL) while(p!= { if(p->data== break; p=p->next; return p; //如果找到则 p 中内容是结点地址（循环因 break 结束），没找到 //p 中内容是 NULL（循环因 p 等于 NULL 而结 //将题干中要求的两种返回值 } （ ）插入结点的算法3 p 所指的结点之后假设在双链表中 s->next=p->next; s->prior=p; p->next=s; s->next->prior=s; 2.12 所示。 完整版：http://item.taobao.com/item.htm?id=5616898223 入结点的方式。 （4）删除结点的算法，设要删除双链表中 p 结点的后继结点，其操作的语句为： q=p->next; p->next=q->next; q->next->prior=p; free(q); 指针变化过程如图 2.13 所示。 图 2.13 双链表结点删除过程图 2 循环 应的单链表和双链表改造而来，只需在终端结点和头结 点间建立 结点的 next 结点指针指向表头结点；循环双链表终端 结点的 n 头结点的 prior 指针指向表尾结点。需要注意的是如果 p 指针沿着循环链表行走，判断 p 走到表尾结点的条件是 p->next==head。循环链表的各 种操作均与非循环链表类似，这里不再细说。 ▲真题仿造(根据考研新大纲综合应用题的走向编制) 1.设顺序表用数组 A[]表示，表中元素存储在数组下标 1~m+n 的范围内，前 m 个元素 递增有序，后 n 个元素递增有序，设计一个算法，使得整个顺序表有序。 （1）给出算法的基本设计思想。 （2）根据设计思想，采用 或 和空间复杂度。 （1）给出算法的基本设计思想。 ．2．5 循环链表的算法操作 单链表和循环双链表由对 联系即可。循环单链表终端 ext 指针指向表头结点， C C++语言描述算法，关键之处给出注释。 （3）说明你所设计算法的时间复杂度 2. 已知递增有序的单链表 A,B（A,B 中元素个数分别为 m,n 且 A,B 都带有头结点） 分别存储了一个集合，请设计算法以求出两个集合 A 和 B 的差集 A-B（即仅由在 A 中出现 而不在 B 中出现的元素所构成的集合）。将差集保存在单链表 A 中，并保持元素的递增有序 性。 完整版：http://item.taobao.com/item.htm?id=5616898223 （2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。 真题 （ 表 L 和表 R。将 数组当前状态看做起始状态，即此时表 L A[] m R 由 A[]中后 n 个 元素构成。要使 A[]中 m+n 个元素整体有序只需将表 R 中的元素逐个插入表 L 中的合适位 置即可。 过程：取表 中的第一 存 辅 变量 让 逐个与 mp A[j+1] A[m+2],A[m+3], ,A[m+n] 最终 []中元素整体有序。 void Insert(int A[],int m,int n) int i,j; 变量，用来暂存待插入元素。 for(i=m+1;i<=m+n;i++) //将 A[m+1…m+n]插入到 A[1…m]中。 { ]; for(j=i-1;j>=1&&tempnext,*q=B->next; //p和q分别是链表A和B的工作指针。 //pre 为 A 中 p 所指结点的前驱结点的指针。 ) pre=p; p=p->next; //A 链表中当前结点指针后移。 //处理 A，B 中元素值相同的结点，应删除。 free(r); //删除结点。 } （3） 由算 共同确定。算法中有一个单层循环，循环内的所 有操作都是常 的次数作为基本操作执行的次数。可见循环执行 的次数即为 p,q 考虑最坏的情况，即 p,q 都走完了自己 所在的链表，循环 习题心选 一 .选择 中的链表如果不特殊指出就是带头结点的链表） 1．下述哪一条是顺序存储结构的优点？（ ） A．存储密度 C．删除运算 D．可方便地用于各种逻辑结构的存储表示 2．下面关于线性表的叙述中，错误的是哪一个？（ A． 性表 存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 线 表采用链接存储，不必占用一片连续的存储单元。 线性表采用链接存储，便于插入和删除操作。 void Difference(LNode *&A,LNode *B) { LNode *pre=A; LNode *r; while(p!=NULL&&q!=NULL { if(p->datadata) { } else if(p->data>q->data) q=q->next; //B 链表中当前结点指针后移。 else { pre->next=p->next; r=p; p=p->next; } } 算 法描 法时间复杂度分析： 述可知，算法规模由 m 和 n 的，因此可以用循环执行数级 两指针沿着各自链表移动的次数， 执行 m+n 次。即时间复杂度为 O(m+n)。 题（题目 大 B．插入运算方便 方便 ） 顺序存储，必须占用一片连续的线 采用 C． D． 性 3．线性表是具有 n 个（ ） 有限序列。 的 完整版：http://item.taobao.com/item.htm?id=5616898223 A．表元素 B．字符 C．数据元素 D．数据项 4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算， 则利用（ ）存储方式最节省时间。 A．顺序表 B．双链表 C．双循环链表 D．单循环链表 中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素， 则采 ．不带头结点且有尾指针的单循环链表 ．内存地址 ．数组下标 C.2n D.n-1 ． ． ． 入一个新结点并仍然保持有序的时间复杂度 是（ og2n) 单链表 h 上，另设有尾指针 r（指向尾结点）， 执行 新结点。 点之后插入结点 q 的操作是（ ）。 p->next->prior=q; q->next=p->next; = ior=q; ext=p; p->prior=q->next; 5．某线性表 用（ ）存储方式最节省运算时间。 ．单链表 ．不带头结点的单循环链表 A B C．双链表 D 8. 静态链表中指针指示的是（ ）。 A B C．链表中下一元素在数组中的地址 D．左、右孩子地址 9. 链表不具有的特点是（ ）。 A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 ．所需空间与线性长度成正比D 10.将两个有 n 个元素的有序表归并成一个有序表，其最少比较次数为（ ）。 A.n B.2n-1 11.单链表 L（带头结点）为空的判断条件是（ ）。 A L==NULL B L->next==NULL C L->next!=NULL D. L!=NULL 12 在一个具有n个结点的有序单链表中插 ）。 A．O(1) B．O(n) C.O(n2) D．O(nl 13.在一个长度为 n（n>1）的带头结点的 （ ）操作与链表的长度有关。 A．删除单链表中的第一个结点。 B．删除单链表中的最后一个结点。 ．在 插入 个C 单链表第一个元素前 一 ．在单链表最后一个元素后插入一个新结点。D 14.在一个双链表中，在 p 结 A．q->prior=p; p->next=q; B．q->next=p->next; p->next->prior=q; p->next=q; q->prior=p; ior q;C．p->next=q; q->prior=p; q->next=p->next; p->next->pr D．q->prior=p; p->next=q; q->next=p->next; p->next->pr 15.在一个双链表中，在 p 结点之前插入 q 结点的操作是（ ）。 A. p->prior=q; q->next=p; p->prior->next=q; q->prior=p->prior; B. q->prior=p->prior; p->prior->next=q; q->n C. q->next=p; p->next=q; q->prior->next=q; q->next=p; 完整版：http://item.taobao.com/item.htm?id=5616898223 D. p->prior->next=q; q->next=p; q->prior=p->prior;p->prior=q; 在16. 一个双链表中，删除 p 结点的 ． 操作是（ ）（结点空间释放语句省略）。 ->next->prior=p->prior; or->prior=p; p->next=p->prior->prior; p->prior=p->prior->prior; A． 不可以为空。 ）。 便 高。 求能够快速的进行插入和删除，又要求存储结构能够反映数 据元 元素的线性表，其存储结构为（ ）。 .双链表。 ）存储方式最节省时 间。 D.顺序表 与单链表相比，双链表的优点之一是（ ）。 可以省略表头指针或表尾指针。 D.访问前后相邻结点更灵活。 A p->prior->next=p->next; p ．B p->prior=p->prior->prior; p->pri ．C p->next->prior=p; p->next=p->next->next; D． 17. L 的终端结点（由 p 所 ） 足（ ）。 非空的单循环链（带头结点）表 指向 满 A.p->next==NULL B.p==L C.p->next==L D.p->next==L&&p!=L 18．带头结点的双循环链表 L 为空的条件是（ ）。 A．L==NULL B．L->next->prior==NULL C. L->prior==NULL D. L->prior==L||L->next==L 19．线性表是（ ）。 一个有限序列，可以为空。 B．一个有限序列， C．一个无限序列，可以为空。 D．一个无限序列，不可以为空。 20.线性表采用链表存储时，其地址（ ）。 A.必须是连续的。 B.一定是不连续的。 C.部分地址必须是连续的。 D.连续与否均可以。 21. 所有的操作算法实现简单。 便于随机存取。 线性表的静态链表存储结构，与顺序存储结构相比其优点是（ A. B. C. 于插入和删除。 D.便于利用零散的存储空间。 22.设线性表有 n 个元素，以下操作中，（ ）在顺序表上实现比在链表上实现效率更 A.输出第 i(1≤i≤n)个元素值。 B.交换第 1 个元素与第 2 个元素的值。 C.顺序输出这 n 个元素的值。 D.输出与给定值 x 相等的元素在线性表中的序号。 23.对于一个线性表，既要 素之间的逻辑关系，则应采用（ ）存储结构。 A.顺序 B.链式 C.散列（Hash 表） 24.需要分配较大的空间，插入和删除不需要移动 A.单链表 B.静态链表 C.顺序表 D 25.如果最常用的操作是取第 i 个元素的前驱结点，则采用（ A.单链表 B.双链表 C.单循环链表 26. A.插入、删除操作更简单。 B.可以进行随机访问。 C. 完整版：http://item.taobao.com/item.htm?id=5616898223 27.在顺序表中插入一个元素的时间复杂度为（ ）。 C.o(n) D.o(n2) o(n 采用 ）存 运算时间 双链表。 D.带头结点的循环双链表。 则采 用（ 相同，若以 h1 为头结点指针 的链 O(1)和 O(n)。 二： （1） 序表 L 中删除下标 i 到 j（i≤j，包括 i，j）之间的 所有 ，其元素为整型数据，设计一个算法，将 中所有小于表头元素的 有一个递增非空单链表，设计一个算法删除值域重 {1, 1,2,3,4,7 一 法删除单链表 L（有头结点）中的一个最小值结点。 6.有一个线性表，采用带头结点的单链表 L 来存储。设计一个算法将其逆置。要求不 7.设计一个算法将一个头结点为 A 的单链表（其数据域为整数）分解成两个单链表 A A.O(1) B.O(log2n) 28.在顺序表中删除一个元素的时间复杂度为（ ）。 A.O(1) B.O(log2n) C.o(n) D.o(n2) 对于一个具有29. n 个元素的线性表，建立其单链表的时间复杂度为（ ）。 A.O(1) B.O(log2n) C.o(n) D. 2) 30 （ 储结构最节省 。 .若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则 A.单链表。 B.给出表头指针的循环单链表。 C. 31.线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点， ）存储方式最节省时间。 A.单链表 B.仅有头结点的单循环链表 C.双链表 D.仅有尾结点指针的单循环链表。 32.设有两个长度为 n 的单链表（带头结点），结点类型 表是非循环的，以 h2 为头结点指针的链表是循环的，则（ ）。 A.对于两个链表来说，删除开始结点的操作，其时间复杂度分别为 B.对于两个链表来说，删除终端结点的操作，其时间复杂度都是 O(n)。 C.循环链表要比非循环链表占用更多的内存空间。 D.h1 和 h2 是不同类型的变量。 综合应用题 础题基 1.设计一个算法，将顺序表中的所有元素逆置。 2.设计一个算法，从一给定的顺 元素，假定 i,j 都是合法的。 3.有一个顺序表 L L 整数放在前半部分，大于的整数放在后半部分，数组从下表 1 开始存储。 4. 复 ,9}。 的结点。比如 1,2,3,3,3,4,4,7,7,7,9,9,9}经过删除后变成{ 5.设计 个算 能建立新结点，只能通过表中已有结点的重新组合来完成。 完整版：http://item.taobao.com/item.htm?id=5616898223 和 B 点，而 B 链表只含有原链表中 data 域为偶数的结点，且保持原来相对顺序。 1.有 N 个个位正整数存在 int 型数组 A[0……N-1]中，N 为已定义好的常量且 N≤9， 数组 数组 A[]中的 数据。 始结点。 习题 选择 本题考查顺序表与链表的对比。顺序表不像链表一样在结点中存在指针域，因此存储 密度 2.B 本题考查线性表两种存储结构的特点。线性表的顺序存储结构必须占用一片连续的存 储空间，而链表不需要这样，这在顺序存储结构中已经讲过。顺序表不便于元素的插入和删 本题考查线性表的定义。线性表的定义：线性表是具有相同特性数据元素的一个有限 序列 序表的特点。顺序表进行插入或者删除操作时需要移动的元素是待插或者 待删位置之后的元素，因此当插入或者删除操作发生在顺序表的表尾时，不需要移动元素。 随机存储，方便于存取任意指定序号的元素，因此本题情况下顺序表最节省时间。 5.D 历整个链表才能找到 置时间复杂度是 O(n)。删除第一个元素时间复杂度是 O(1)。 表相同，时 然后执行 p->next=q->next;r=q;q=q->next;free(r); （其中 p 指向终端结点，q 指向起始结点，r 用来帮助释放结点空间）。 程示意图如下： ，使得 A 链表只含有原来链表中 data 域为奇数的结 （2）思考题 A[]的长度为 N，另给一个 int 型变量 i，要求只用上述变量（即 A[0]~A[n-1]与 i 这 N+1 个整型变量）写算法找出这 N 个整数中的最小者，并且要求不能破坏 2.写一个函数，逆序打印单链表中的数据，假设指针 L 指向了单链表的开 心讲 题： 1.A 大，A 正确。BC 两项是链表的优点。D 中可方便地用于各种逻辑结构的存储表示是错 误的，比如对于树型结构，顺序表显然不如链表表示起来更方便。 除，因为要移动多个元素。链表在插入和删除的过程中不需要移动元素，只需修改指针。因 此本题选 B 3.C 。 4.A 本题考查顺 顺序表支持 本题考查几种链表的插入和删除操作。 对于 A 项，单链表，要在最后一个元素后插入一个元素，需要遍 插入位 对于 B 项，不带头结点的单循环链表在最后一个元素之后插入一个元素的情况和单链 间复杂度是 O(n)。对于删除表中第一个元素的情况，同样需要找到终端结点， 即删除结点的时间复杂度也是 O(n)，因为终端结点的指针 next 指向开始结点，首先需要 遍历整个链表找到终端结点， 四句才满足删除要求 删除过 完整版：http://item.taobao.com/item.htm?id=5616898223 对于 项，有尾指针（即指向表中终端结点的指针），因为已经知道终端结点的位置所 以省去了 B 选项中链表的遍历过程，因此删除和插入结点的时间复杂度为 O(1)。 综上所述，本题选 D 8.C 本题考查静态链表中指针作用。虽然静态链表用数组来存储，但其指针域和一般单链 表一样，指出了表中下一个结点的位置。不要因为静态链表是用数组来存储就想当然的将静 态链表等同于顺序表，而误选 B 项。 9.B 本题考查顺序表和链表的比较。显然随机存储是顺序表的特性，而不是链表的特性。 10.A 较次数最少，为 n。因为此时 L1 中的元素在比较了 n 次后已经全部被并入 顺序 与 L2 表各 -2 次，这时还需进行一次比较就有一个表变为空表，至此所有 束，因此总的比较次数是 2n-1 次。 LL，不带头结点的单链表是看头指针 head 是否为 考查链表的查找与插入操作。这里假设单链表递增有序（递减的情况同理），在插 后插入该结点。查找的过程时间复杂度为 程时间复杂度为 。 13. 说明：本选项的讲解中顺便给出了不带头结点的单循环链表中删开始结点的算法过程， 供考生参考。 对于 C 项，双链表的情况和单链表相同，一个 O(n)，一个 O(1)。 D 本题考查线性表的归并算法。在归并算法中，当 L1 表中的所有元素均小于 L2 表中的 所有元素时，比 表，剩下的 L2 中的元素就不需要比较。 补充：如果本题问比较次数最多是几次该选什么呢。答案是 2n-1 次，此时 L1 与 L2 中元素轮流被并入顺序表，每并入一个就比较一次，当剩下最后 2 个元素的时候（L1 一个），已经比较了 2n 比较结 11.C 本题考查带头结点的单链表和不带头结点的单链表基本操作的区别。带头结点的单链 表判空条件看 head->next 是否为 NU NULL。 12.B 本题 入数据为 x 的结点之前，先要在单链表中找到第一个大于 x 的结点的直接前驱 p，在 p 之 O(n)，插入过程的时间复杂度为 O(1)，整个过 O(n) B 本题考查链表的删除操作。在带有头结点的链表中要删除一个结点，必须知道其前驱 完整版：http://item.taobao.com/item.htm?id=5616898223 结点位置，由题干知，第一个结点的前驱结点位置已知，为 h 所指的头结点，因此无论链 表多长删除其中第一个结点的操作都是p=h->next;h->next=p->next;free(p);这三 尾结点的前驱结点地址未知，因此要删除链表中最后一个结点，需要从头结点开始 链表来找到最后一个结点的前驱结点，链表越长执行操作的循环次数越多，即删除 C 个 结点，等价于在头结点后插入一个新结点，头结点地址已知，插入操作与链表长 同样，对于 D 选项尾结点地址已知，在其后插入新结点的操作与链表长度无关。 参见之前双链 入 作执行图可知本 B A 选项执行完第二句时 p 的后继结点地址丢失，插入不能完成。 项执行完第一句时 p 的后继结点地址丢失，插入不能完成。 t;应该改为 p->prior=q; 之前双链表删除算法执行图可知本题选 A 继结点和前边的所有结点都失去联系。 结点地址丢失。 求。 17. 带头结点的单循环链表中没有空指针域，因此 A 不对。 端结点与头结点为同一个结点，即满足 p==L 时，链表为空因此 B 不对。 ，同时也是终端结点，此时一定满足 p->next==L。当 链表 立，不能作为判断 链表 件。链循双环链表为空时头结点体现如下形态： 。并且循环双链表同循环单 条语句。 遍历整个 最后一个结点的操作与链表长度有关。 要在某一个结点后插入一个结点，则必须知道这个结点的地址， 项中在第一个元素前 插入一 新 度无关。 14.B 本题考查双链表的插入操作。 表插 操 题选 C 选 D 选项执行完第二句时 p 的后继结点地址丢失，插入不能完成。 15.D 本题考查链表的插入操作。 A 选项执行完第一句时 p 的前驱结点地址丢失，插入不能完成。 B 选项最后一句 p->prior=q->nex C 选项破坏了 p 和其后继结点的联系。 16.A 本题考查链表的插入操作。 参见 B 选项第一句执行完之后 p 的后 C 选项第一句为废操作，第二句执行完 p 的后继 D 选项将 p 结点的 next 指针指向了其前驱的前驱，不满足删除要 D 本题考查单循环链表的判空条件。 当终 当链表为空时，p 指向头结点 不空时，p 指向终端结点，同样满足 p->next==L，因此 C 项恒成 非空的条件。 因此本题答案为 D。 18.D 本题考查双循环链表的判空条 可见当满足 L->prior==L||L->next==L 时，链表为空 完整版：http://item.taobao.com/item.htm?id=5616898223 链表 。线性表是具 元素 一个有限序列。该序列中 所含元素的个数叫做线性表的长度，用 n 表示（n≥0）。注意 n 可以等于零，表示线性表是 ，空表也可以作为一个线性表。因此本题选 A。 20. 本题考查链表存储结构的特点。一般链表结点在内存中是分散存在的，因此可是不连 续的；当然如果连续的申请一片存储空间来存储链表结点也未尝不可。因此本题选 D。 21.C 本题考查静态链表与顺序表的特点。静态链表具有链表的插入和删除方便的特点，也不 需要移动较多的元素，这是优于顺序表的地方，因此本题选 C。 本题考查顺序表与链表的特点。 表支持随机存储，链表不支持，因此顺序表输出地 i 个元素值的时间复杂度为 O(1)， 链表 C 不对。 输出与给定值 x 相等的元素在线性表中的序号，对于顺序表和链表，都需要搜索整个表， 复杂度为 O(n)，D 不对。 要执行 3 次操作。 ： p=p->data; 项也正确。在考研中 很容易出现，考生 显然比起 项来说， 项更准确。 23. Hash 表中各元素之间不存 在逻 24.B 静态链表 静态 点，即插入和删除操作不需要移动元素。因此本题选 B。 25. 点。较之其他三种存储结构，顺序表找到表中第 i 个元素的时间 复杂 i 个元素前驱的时间复杂度也是最小，为 O(1)。因此本题选 一样，没有空指针域，因此本题选 D。 19.A 本题考查线性表的定义 有相同特性数据 的 一个空表 D 22.A 顺序 则为 O(n)，因此 A 正确。 交换第 1 与第 2 个元素的值，对于顺序表与链表，时间复杂度均为 O(1)，因此 B 不对。 输出 n 个元素的值，两者时间复杂度均为 O(n)，因此 因此时间 说明：对于 B 项，写出两者的具体操作如下： 线性表：temp=a[1];a[1]=a[2];a[2]=temp; 链表 p=head->next->data; q=head->next->next->data; tem p->data=q->data; q->data=p->data; 需要执行 5 次操作。因此严格来说，B 这种情况 遇到这种题目的时候要选择 更准确 的一项，“”BA B 本题考查链表的特点。链表较之题选项中其他两种存储结构的最大优点就是能够快速的 进行插入和删除，当然链表也能反映数据元素之间的逻辑关系， 辑关系，因此本题选 B。 本题考查 的特点。静态链表用数组来表示，因此需要分配较大的连续空间， 链表同时还具有一般链表的特 D 本题考查顺序表的特 度最小，为 O(1)；取第 完整版：http://item.taobao.com/item.htm?id=5616898223 D。 而单 能快速访问任何一个结点的后继结点。因此本题选 D。 顺序表插入算法的基本操 的移动。在一个 n i 插入一个元素，需要进行元素移动的次数大约为 n-i 次， 元素平均移动次数大约为 n/2 次，因此时间复杂度为 O(n)。 n 的顺序表中的 i 位置上删除一个元素，需要进行元素移动的次数大约为 n-i 次， 删除 题考查链表的建立。链表建立的过程即将结点逐个插入链表的过程，因此链表建立的 度即为链表规模 n 乘以链表插入操作的时间复杂度 O(1)，即 n×O(1)，即 O(n)。 因此 30.D 考查链表的基本操作。在链表中插入或删除一个结点，需要修改相邻结点的指针域。 如不 因此本题选 D。 头结点地址。 两个链表来说，要删除终端结点，都需要从头结点开始找到终端结点的前驱结点， 26.D 本题考查双链表的特点。在双链表中可以快速访问任何一个结点的前后相邻结点， 链表中只 27.C 本题考查顺序表插入算法的效率。 作是元素 长度为 的顺序表中的位置 上 插入算法 28.C 本题考查顺序表删除算法的效率。顺序表删除算法的基本操作是元素的移动。在一个 长度为 算法平均元素移动次数大约为 n/2 次，因此时间复杂度为 O(n)。 29.C 本 时间复杂 本题选 C。 本题 特别指明，通常只给出链表头结点的地址，其他结点的地址只能从它的前驱或者后继得 到。以上 4 种选项中只有 D 能通过头结点指针直接获得最后一个结点的相邻结点的地址， 因此本题选 D。 31.D 本题考查链表的基本操作。在有尾结点指针 r 的循环单链表中，在最后一个结点之后 插入结点 s 的操作是：s->next=r->next;r->next=s;r=s;删除第一个结点的操作是： p=r->next;r->next=p->next;free(p);其时间复杂度均为 O(1)。 32.B 本题考查链表的综合知识。 对于两个链表来说，要删除开始结点，其时间复杂度都为 O(1)。因为已知开始结点的 前驱结点地址，即 对于 其时间复杂度都是 O(n)。 两链表占用内存空间相同。不要误以为循环链表比非循环链表多一个指向头结点的指针， 其实非循环链表也有这个指针，只是它没有指向头结点而已。 h1 和 h2 指向相同类型的结点，因此是相同类型的变量。单链表和循环单链表结点类 型相同，只是表中结点的组织方式不同。 完整版：http://item.taobao.com/item.htm?id=5616898223 综合 1 1 本算法简单，上图即可说明问题，两个变量 i，j 指示顺序表的第一个元素和最后一个 素，交换 i，j 所指元素，然后 i 向后移动一个位置，j 向前移动一个位置，如此循环， 到 i 与 j 相遇时结束，此时顺序表 L 中的元素已经逆置。 由此可写出以下代码： void reverse(Sqlist &L) //L 要改变，用引用型 { int i,j; int emp; //辅助变量，用于交换 =1,j=L.length;itemp) j--; //j 从左往右扫描，当来到第一个比 temp 小的元素时停止 完整版：http://item.taobao.com/item.htm?id=5616898223 if(inext,*q; LNode while(p->next!=NUL { if(p->data==p->next->data) //找到重复结点删除之 q=p->next; p->next=q->next; else p=p->next; } } 解法二：依次将原序列中每个连续相等子序列的第一个元素移动到表的前端，将剩余的 完整版：http://item.taobao.com/item.htm?id=5616898223 第 4 题图 令 p 指向起始将结点。q 从 p 的后继结点开始扫描，q 每来到一个新结点的时候进行 检测：当 q->data 等于 p->data 的时候，什么也不做，q 继续往后走；当两者不相等的 时候，p 往后走一个位置，然后用 q->data 取代 p->data。之后 q 继续往后扫描，重复 以上过程。当 q 为空的时候，释放从 p 之后的所有结点空间。 void delsl2(LNode *&L) { LNode *p=L->next,*q=L->next->next,*r; while(q!=NULL) { while(q!=NULL&&q->data==p->data) 表，pre 指向*p 结点的前驱，用 minp 保存值最小的结点指针， 一边扫描，一边比较，将最小值结点放到 minp 中。 ode(LNode *&L) =pre->next,*minp=p,*minpre=pre; le(p!=NULL) //查找最小值结点 minp 以及前驱结点 minpre { if(p->datadata) q=q->next; if(q!=NULL) { p=p->next; p->data=q->data; } } q=p->next; p->next=NULL; while(q!=NULL) { r=q; q=q->next; ee(r); fr } } 5． 析 分 ： 用 从头p 至尾扫描链 minpre 指向 minp 的前驱。 代码如下： v delminnoid { *p LNode *pre=L, whi { minp=p; 完整版：http://item.taobao.com/item.htm?id=5616898223 pre=pre; pre=p; pre->next=minp->next; //删除*minp 结点。 分 ： 前 算法基础中，提到过关与逆序的问题，那就是链表建立的头插法。头插法 成 ， 序和原数组中元素的顺序相反。这里我们可以将 L 中的元素作为 转 L ->next 设置为空，然后将头结点后的一串结点用头插法逐个 入 L 中的元素顺序正好是逆序的。 ode *&L) LNode *p=L->next,*q; L->next=NULL; le(p!=NULL) //p 结点始终指向旧的链表的开始结点。 入 q 中，因此 p 仍然可以找到后继 //（即此时的新开始结点）。 p A data 域 元 来建立 B 链表。 i sp *p,*q,*r; B=(LNode*)malloc(sizeof(LNode)); //申请链表 B 的头结点 B->next=NULL;//每申请一个新结点的时候，将其指针域 next 设置为 NULL 是个好习 //惯，这样可以避免很多因链表的终端结点忘记置 NULL 而产生的错误。 前驱结点，这和删除结点类似， { //因为取下一个结点，就是删除一个结点，只是不释放这个 而已。 if(p->next->data%2==0) //判断结点的 data 域是否为偶数，是则从链表中取下 min } p=p->next; } min free(minp); } 6． 析 在 边讲过的 完 后 链表中的元素顺 逆 后 的元素来源，即将 L 插 L 中，这样新的 本题代码如下： void Reversel(LN { whi { q=p->next; //q 结点作为辅助结点来记录 p 的直接后继结点的位置。 p->next=L->next; //将 p 所指结点插入新的链表中。 L->next=p; p=q; //因为后继结点已经存 } } 7． 分析： 不难，可以这样解决，用指针 从头至尾扫描 链表，当发现结点此题思路 为偶数的结点则取下，插入链表 B 中。要用头插法还是用尾插法呢，因为题目要求保持原 来数据 素的相对顺序，所以要用尾插法 本题代码如下： vo d lit2(LNode *&A,LNode *&B) { LNode r=B; p=A; while(p->next!=NULL)//p 始终指向当前被判断结点的 //结点的内存空间 { 完整版：http://item.taobao.com/item.htm?id=5616898223 q->nex next=q; ; p=p->next; //p 后移一个位置，即开始检查下一个结点。 } ： 个始终记录当前所 [0]~A[N-1]和 i 这 N+1 i 这一个变量来实现 功能。本题一种可行的办法如下： 对于处理 N 规模的数据足够用，我们可以让 i 的十位上的数字作为 将 i 个位上的数字来代替通常题目中 min 的功能，这样一个 i 就可以实现 i 与 n 十位上 的数字。 由以上分析可写出如下代码： dMin(int A[],int &i)//用 i 来保存最小值 循环结束后 i 个位上的数字保存了 A[]中最小值，将 i 分 数据，然后打印第一个数据，即可实现单链表的中数据的逆序打印。 LL) } q=p->next; //q 指向要从链表中取下的结点 p->next=q->next; //从链表中取下这个结点 t=NULL; r-> r=q } } （2）思考题 1.分析 通常在顺序表中找最小值，需要一个循环变量 i 用来控制循环和一 扫描序列中最小值的变量 min。本题则不同，题目要求只能用 A 个变量，且要求不能破坏数组 A[]中的数据，这就是说现在我们要用 通常题目中 i 和 min 两者实现的 i 是 int 型变量， 循环变量， mi 两者实现的功能。对于本题中的 i，i%10 即取 i 个位上的数字，i/10 即取 i void Fin { i=A[0]; //i 先保存存入 A[0]的值。 while(i/10<=N-1) //取 i 的十位上的数字作为循环变量，来与 N-1 比较。 { if(i%10>A[i/10]) //取 i 个位上的数字与 A[i/10]中各数值比较。 { i=i-i%10; //如果过 i 个位上的数字大于 A[i/10]中数字则将 i i=i+A[i/10]; //个位上的数字换成 A[i/10]。 } i=i+10; //i 十位上的数字加 1，即对 A[]中下一个数字进行检测。 } i=i%10; // //更新为 i 个位上的数字。 } 2. 析： 本题可用递归的方法解决，在表不空的情况下先递归的逆序打印表中第一个数据之后的 代码如下： void reprint(LNode *L) { if(L!=NU { reprint(L->next);//递归逆序打印开始结点后边的数据 cout<data<<" ";//打印开始结点中数据。 } 完整版：http://item.taobao.com/item.htm?id=5616898223 第三章 栈、队列和数组 大纲 栈和队列的应用 ▲ 特殊矩阵的压缩存 3．1 栈和队列的基本概念 3 1 1 1.栈的定义 删除操作的线性表。其中允许进行插入或删除操作的 一端称为栈顶（ 称为栈顶指针的位置指示器（其实就是一个变量。对于 顺序栈，就是记录栈顶元素所在数组位置标号的一个整型变量，对于链式栈就是记录栈顶元 它是动态变化。表的另一端称为栈底，栈底是固定不变的。 栈的插入和删除操作一般被称为入栈和出栈。 2.栈的特点 由栈的定义可以看出栈 LO）。栈中的元素就好比 开进一个死胡同的多辆汽车，最先开进去的汽车只能等后进来的汽车都出去了，才能出来。 的存储结构，顺序栈和链式栈。会读书的同学不看这一段就应该知道这两 种存 （fr 入新元素称为进队，新元素进队后就成为新的队尾元素；从队列中 删除元素称为 素出队后，其后继元素就成为新的队头元素。 节车厢就是队中的元素，最先开进隧道的车厢总是最先驶出隧道。 要求： ▲ 栈和队列的基本概念 ▲ 栈和队列的顺序存储结构 ▲ 栈和队列的链式存储结构 ▲ 储 ． ． 栈的基本概念 栈是一种只能在一端进行插入或 top）。栈顶由一个 素所在结点地址的指针）来指示， 的特点，一句话概括就是先进后出（FI 3.栈的存储结构 栈有两种主要 储结构。因为在栈的定义中已经说明，栈是一种在操作上稍加限制的线性表，即栈本质 上是线性表，而线性表有两种主要存储结构，顺序表和链表，因此栈也同样有对应的两种存 储结构。 3．1．2 队列的基本概念 1.队列的定义 队列简称队，它也是一种运算受限的线性表，其限制为允许在表的一端进行插入，而 在表的另一端进行删除。进行插入的一端称作队尾（rear），进行删除的一端称为队头 ont）。向队列中插 出队，元 2.队列的特点 队列的特点概括一句话就是先进先出（FIFO）。打个比方说，队列就好像开进隧道的一 列火车，各 完整版：http://item.taobao.com/item.htm?id=5616898223 3.队列的存储结构 队列的存储结构不用多说，顺序队和链队。 栈和队列的存储结构、算法与应用 { ]; //存放栈中元素 } SqStack; //顺序栈类型定义 顺序栈示意图 顺序栈示意图 ode { int data; //数据项 struct LNode *next; //指针域 }LNode; //链栈类型定义 链栈就是采用链表来存储栈。这里我们用带头结点的单链表来作为存储体，示意图如 下： 图 3.2 链栈示意图 int front; //队首指针 3．2 说明：本节包括了大纲要求中的中间三部分 3．2．1 本章所涉及的数据结构定义 1.顺序栈定 义 typedef struct int data[MAX int top; //栈顶指针 如下： 图 3.1 2.链栈结点定义 typedef struct LN 3.顺序队列的定义 typedef struct { int data[MaxSize]; 完整版：http://item.taobao.com/item.htm?id=5616898223 int rear; //队尾指针 }SqQueue; //顺序队类型定义 4.链队的定义 （1）队结点类型定义 typedef struct QNode { //数据域 *next; //指针域 ode; //结点类型定义 ear; //队尾指针 //链队类型定义 图 3.3 链队示意图 ． 殊状态，两个操作。 1 ①栈空状态 st.top==-1（有的书上规定 st.top==0 为栈空条件，这样会浪费一个 元素大小的空间，本书统一规定栈空状态为 st.top==-1。考试中有时会出现其他规定， 其实大同小异稍加注意即可） ②栈满状态 st.top==MAX-1（MAX 为栈中最大元素个数，则 MAX-1 为栈满时栈顶元 素在数组中的位置，因为数组下标从 0 号开始。本书规定栈顶指针 top 为 1 时栈空，即 top==0 的数组位置也可以存有数据 中规定 0 号数组位置不存数据元 素是不同的，考生应注意这一点） 进栈操作 （既然规定了 top 为-1 时栈 元素进栈 作 须是 动指针，再进入元素，因为数组下表不存在-1。在其他 书中因有不同规定，会有先元素进栈再栈顶指针加 1 的进栈操作，其实本质一样，考生注 意即可） 为先取出元素，再变动 操作不变的情况下先变 取出元素， int data; struct QNode }QN （ ）链队类型定义2 typedef struct { QNode *front; //队头指针 QNode *r }LiQueue; 链队示意图如下： 3 2．2 顺序栈的基本算法操作 顺序栈的要素 1. 对于顺序栈 st，一共有 4 个要素，包括两个特 （ ）两状态： - 元素，这与之前顺序表 （2）两操作： 素①元 x st.top++;st.data[st.top]=x; 为空，则 必操 先移 ②元素 x 出栈操作 x=st.data[st.top];st.top--;（进栈操作次序决定了出栈操 作次序，为什么这样说呢，如果进栈操作是先变动栈顶指针，再存入元素，则出栈操作必须 指针。如果在上述进栈 动指针，再 完整版：http://item.taobao.com/item.htm?id=5616898223 则栈顶元素丢失，取出的是栈顶下边的元素。考生可动手自行模拟一下这个过程，这样便于 理解和加深记忆） ．初始化栈的算法2 t.top=-1; //只需将栈顶指针设置为-1。 （ ） 进栈算法 t x) 注意，栈满不能 栈。 //先移动指针，再进栈。 p x; 出栈算法 tack &st,int &x) 空则不能出栈 x= st } ： 常作为一个工具来解决其他问题，因此一般情况下，栈的声明 以及 可以写的很简单，不必要调用以上函数。上述函数只作为标准操作来参考，使用 价值 比较实用的栈的操作的写法如下： int 型，可以这么写： stack[MAX]; int top=-1; 这两句话连声明带初始化都有了。 2． st 句话就搞定进栈操作。 初始化一个栈只需将栈顶指针置为-1 即可。对应算法如下： void initStack(Sqstack &st)//初始化栈 { s } 3．判断栈空的算法 栈 st 为空的时候返回 1，否则返回 0。对应算法如下： int StackEmpty(SqStack st) { if st.top==-1 ; return 1 else return 0; } 4． int Push(SqStack &st,in { if(st.top==MAX-1) //这里 return 0; 要 进 st.top++; ]=st.data[st.to urn 1; ret } 5． int Pop(SqS { 注意，如果栈if(st.top==-1) // return 0; st op]; //先取出元素，再移动指针.data[st.t .top--; return 1; 说明 操作 在考试中，栈常 不高。在考题中 1．声明一个栈并且初始化，假设元素是 int 元素 x 进栈： ack[++top]=x;这一 完整版：http://item.taobao.com/item.htm?id=5616898223 3． x=stack[top--];这一句话就搞定出栈操作。 2 与 方是，当前栈是否为空，空时不出；是否为满，满时不进。这些 判断 题目需要来决定写还是不写，不必要像标准操作那样每次都判断（比如题目中入 栈元 top 赋值给接收它的变量，然后 top 如 a=top++;中 a 保存 ++top]=x; 中 x 的位置上（一下看不懂可以拆开看。第一步：top 先自增 1。第 ]的括号内而指出了将要保存元素的 位置 op所指的位置上）。这里看懂了，就很容易理解stack[++top]=x; 等价 ;等价于 x=stack[top];top--; 3．2． 栈 算法操作 不 请新的结点，为栈满。一般题目要求不太严 所指）进栈操作： 作（出栈元素保存在 x 中）： x=p->data; lst->next=p->next; free(p);（其实就是单链 表的 要改变，用引用型。 c(sizeof(LNode));//制造一个头结点。 =NULL; 元素 x 出栈： 3 点需注意的地 根据 素不多，而 MAX 足够大，就无需考虑入栈操作会产生溢出）。 通过 2 与 3 两点，来稍微复习一下 C 语言基础。top++与++top（--top 与 top-- 的情况类似）的不同可以用几句话来说清楚。前者是先将 自增 1，而后者是先 top 自增之后，再把值赋给接收它的变量。比 了自增前的top值，而a=++top;中a保存了自增后的top值。同样stack[ 存放到 top 变化之后所指示 二步：自增后的 top 把自己的数值放在 stack[ 。第三步：x存储在t 于 top++; stack[top]=x;而 x=stack[top--] 以上所讲的初始化栈，出栈入栈的简单写法在考试的时候很实用，是提高程序书写速 度的好方法，且通过上边的理解很好记忆。 基本3 链 的 1. 链栈的要素 和顺序栈对应，链栈也有 4 个要素，包括两个特殊状态，两个操作。链栈 lst 的 4 个 要素如下： （1）两状态： ①栈空状态 ： lst->next==NULL ②栈满状态 ： 存在栈满的情况（这句话来自其他辅导书，我认为不太准确，链栈可以利用的结点数 和内存大小有关，当内存满时，此时链栈不能申 格可认为不存在栈满的情况） （2）两操作： ①元素（由指针 p p->next=lst->next; lst->next = p;（其实就是头插法建立链表中的插入操作） ②出栈操 p=lst->next; 删除操作） 2. 链栈的初始化算法 void InitStack(LNode *&lst) //lst { lst=(LNode*)mallo lst->next } 3. 判断栈空算法 当栈空时返回 1，否则返回 0。 int StackEmpty(LNode *lst) //判断是否为空 { 完整版：http://item.taobao.com/item.htm?id=5616898223 ULL) else } 进栈算法 *&lst,int x) p=(LNode*)malloc(sizeof(LNode));//为进栈元素申请结点空间。 //虽然此函数中此句不写也正确，但是每当申请 //新结点的时候，将其指针域设置为 NULL，是 //可以避免一些错误的好习惯。 表的头插法*/ p->data=x; lst->next; { LNode *p; 0 ; */ x=p->data; xt=p->next; ，和顺序栈一样，在应对考试的时候，不必要像以上那样严格的写 中即可，具体思路类 于 栈少的多。顺序栈声 家，如果你有 10 份时间，把 7 份用在顺序栈的 合适的时间分配比例。 ． 的应用。 1 c 语言里算术表达式中的括号只有小括号。编写算法，判断一个表达式中的括 号是 if(lst->next==N return 1; return 0; 4． void push(LNode { LNode *p; p->next=NULL; /*以下 3 句就是链 p->next= lst->next=p; } 5.出栈算法 在栈不空的情况下可以执行，返回 1；否则返回 0，代码如下： int Pop(LNode *&lst,int &x)//需要改变的变量要用引用型 if(lst->next==NULL) //栈空则不能出栈返回 return 0 /*以下就是单链表的删除操作 p=lst->next; lst->ne p) free( ; return 1; } 说明：对于链式栈 出其操作的函数，只需要摘取其中必要的语句组合在自己的题目代码 序 还需注意在考研中链栈的应用要远比顺序似 顺 栈中的讲解。大家 明 单 操作也简单的多，因简 ， 此在此提醒大 目上，这是一个题目上，3 份用在链栈的题 3 2．4 栈的应用 说明：这部分通过例题来体会栈 1.顺序栈的应用 例题 否正确配对，表达式已经存入字符数组 exp[]中（元素从数组下标 1 开始存储），表达 完整版：http://item.taobao.com/item.htm?id=5616898223 式中的字符个数为 n。 分析： 本题可以用栈来解决，为什么可以用栈来解决呢，这是关键，学生拿到一个问题，如果 被告知用什么方法解决，大多数学生都不会感到困难，困难的是自己遇到新问题时想不到用 但是不知何时何地使用，这是考试中最纠结的事情，下边 解决。 匹配？可以这样做，从左往右看这个表达 式中的括号，看到一个“(”，就记住它（这里可以理解为入栈），如果下一个括号是“)”， 则划 里可以理解为出栈），表示一对括号处理完毕继续往后看。如果前边 “(” “(” 边的 掉后再来处理它（后边的“(”处理掉才能回来处理先前的“(”，这里体现了栈 的先进后出） 的括号要么是 要么是 ，就用前边说的方法来处理。如果到 最后所有括号都被划掉，则匹配，否则就不匹配。由此可以看到，一个问题中如果出现这种 要用栈来 { if(top==-1)// “)” 0。 top--; //如果栈不空则出栈，这里相当于完成了以上分析中的 } //栈空，即所有括号都被处理掉则说明括号是匹配的。 return 1; 的数值，其中后缀式存于一个字符数组 exp 中，exp 里 习一下算术表 式的三种形式：前缀式、中缀式、后缀式。中缀式是我们 如 是一个中缀式，转化为前缀式为：/++ab×cde，转 这种方法来解决问题，心中有招， 就来说说为什么要用栈来 给你一个表达式，用目测怎么判断括号是否 掉这 号（这两个括 所有的括号都被划掉，而下一个括号却是“)”，则括号一定不匹配，因为“)”之前已经没有 括号和它匹配了。如果下一个括号是 ，则暂时不管前一个 ，先把它放在那里，等后 “(”处理 。以后看到 “(” “)” 情况，即在解决问的过程中出现了一个状态，但凭现有条件不能判断当前的状态是否可以 解决，需要记下，等待以后出现可以解决当前状态的条件后返回来再解决之。这种问题需 能解决，栈具有记忆的功 ，这是栈的 FILO 特性所延伸出来的一种特性。 通过以上分析可知，此题应该用栈来解决，代码如下： int match(char exp[],int n) { char stack[MAX]; int top=-1; //两句完成栈的声明和初始化，考试 //中的这种简写可以节省时间。 int i; for(i=1;i<=n;i++) if(exp[i]=='(') //如果遇到“(”则入栈等待以后处理。 stack[++top]='('; //一句话完成入栈操作。 if(exp[i]==')') { 如果当前遇到的括号是 且栈已空，则不匹配，返回 return 0; else //划掉两个括号的动作。 } if(top==-1) else //否则括号不匹配。 return 0; } 说明：通过这个简单的例子，考生可以了解什么样的题目要用栈来解决。 例题 编写一个函数，求后缀式2. 中最后一个字符为‘\0’，作为结束符，并且假设后缀式中的数字都只有一位。 分析： 这 首先要复 达 所熟悉的表达式。比 (a+b+c×d)/e 化为后缀式为：abcd×++e/。 完整版：http://item.taobao.com/item.htm?id=5616898223 注意：中缀表达式转化成后缀或者是前缀，结果并不一定唯一。比如 ab+cd×+e/同样 (a 种运算次序，而中缀式却不一 ， 缀式按某一种运算次序而生成的，因此对于一个中缀式可能有 多种后缀式或者前缀式。比如 a+b+c 可以先算 a+b 也可以先算 b+c，这样就有两种后缀式 与其 知道，因 此必须先存起来，这符合例题 1 中粗体字所描述的情形，因此可以用栈来解决。 的值。 由此 ; l; n 0; /后缀式计算函数。 a,b,c; //a,b 为操作数，c 来保存结果 不能是 数都只有一位，但是在 中可能产生多位的数字，因此要用整型。 //Op i++) ( 0'&&exp[i]<='9')//如果遇到操作数，则入栈等待处理，体现了栈的记忆功能。 exp[i]-'0'; //注意：字符型和整形的转换（后边讲解）。 e //如果遇到运算符，则说明前边待处理的数字的处 //理条件已经具备，开始运算。 算符。 后入栈， a=stack[top--]; c=op(a,Op,b); // 是 +b+c×d)/e 的后缀式。后缀式和前缀式都只有唯一的一 定 后 式和前缀式是由中缀 对应，分别是 ab+c+和 abc++。 回到本题，后缀式的求值可以用栈来解决，为什么呢？对于一个后缀式，当从左往右扫 描到一个数值的时候，具体怎么运算，此时还不知道，需要扫描到后边的运算符才 执行过程：当遇到数值的时候入栈，当遇到运算符的时候，连续两次出栈，将两个出栈 元素结合运算符进行运算。将结果当成新遇到的数值入栈。如此往复，直到扫描到终止符 ‘\0’,此时栈底元素值即为表达式 可以写出以下代码： int op(int a,char Op,int b) //本函数是运算函数，来完成算式 a Op b 的运算。 { if(Op=='+') return a+b; if(Op=='-') return a-b if(Op=='*') return a*b; if(Op=='/') { if(b==0) //这里需要判断，如果除数为 0 则输出错误标记，这种 { //题目中的小陷阱，是考生应该注意的。 cout<<"ERROR"<=' stack[++top]= els { Op=exp[i]; //取运 b=stack[top--]; //取第二个操作数（因为第二个操作数 //所以先出栈的是第二个操作数）。 //取第一个操作数。 将两个操作数结合运算符 Op 进行运算，结果保存在 c 中。 完整版：http://item.taobao.com/item.htm?id=5616898223 stack[++top]=c; //运算结果入栈。 } } return stack[top]; } 补充：假设有一个字符 ‘5’，如果定义一个整型变量 a，执行 a=‘5’;此时 a 里边保 存了 码，而不是数字 。如5 的 ASCII 5 即 5 这个整数 只需要执行 a=‘5’-‘0’;即可。同理，如果把一个整型数字(假设为 a)， ，只需执行 b=a+‘0’;即可。此时 b 考的同学可能不是太熟练。 带头结点的单链表存储链栈，设计初始化栈、判断栈是否为空、进栈和出 ，为空的条件是：lst==NULL，进栈和出栈操作都是 { if(lst==NULL) p=(LNode *)malloc(sizeof(LNode)); p->data=x; ; Popl(LNode *&lst,int &x) //元素出栈 LNode *p; L) //栈空的情况 何将‘5’这个字符代表的真正意义， 保存于 a 中呢？ 转 为 应 字符型数字存储在字符变量(假设为 b)中化 对 的 中保存的是 a 这个数字的字符，但是这 转 小技巧在种 化只适用于 0~9 这 10 个数字。这个 程序设计题目中应用的比较多，因此在这里要提一下，有些跨 2.链栈的应用 例题.3 用不 栈等相应的算法。 分析：不带头结点的单链表 lst 在表头进行的。算法如下： void InitStackl (LNode *&lst) //初始化栈 { lst=NULL; } int StackEmptyl (LNode *lst)//判断栈是否为空 return 1; else return 0; } void Pushl (LNode *&lst,int x) //进栈 { LNode *p; p->next=NULL; /*下边是插入操作*/ p->next=lst; lst=p } int { if(lst==NUL return 0; p=lst; //p 指向第一个数据结点 /*删除结点操作*/ 完整版：http://item.taobao.com/item.htm?id=5616898223 ． 循 rear front 指针指向 素进队的时候，rear 要向后移动，元素出队的时候，front 也 的出队和进队操作以后，两个指针最终会达到数组末端 MAX-1 然无法让元素进队，这就是所谓的“假溢出”。要解决这 问 弄成一个环，让 rear 和 front 沿着环走，这样就永远不会出现 这样就产生了循环队列，循环队列是改进的顺序 队列。示意图如下： 3.4 图 3.4 中进队出队变化情况如下： ①由空队进队两个元素，此时 front 指向 0，rear 指向 2。 ②进队 4 个元素，出对 3 个元素，此时 front 指向 3，rear 指向 6。 ③进队 2 个元素，出队 4 个元素，此时 front 指向 7，rear 指向 0。 从上图中由①到③的变化过程可以看出，经过元素的进进出出，即便是 rear 和 front 都到了数组尾端（③图所示），依然可以让元素继续入队，因为两指针不是沿着数组下表递 增的直线行走，而是沿着一个环行走，走到数组尽头的时候自动返回数组起始位置。 怎样实现指针在递增的过程中沿着环形道路行走呢，有一个方法，就上图 3.1 中的例 子，拿 front 指针来说，可 ，front 初值为 0 的 话， 0,1,2,3,4,5,6,7,0,1,2……，即以 0 到 7 为周 般情况，上述语句可写 为 f 的状态，队 满和 x=p->data; lst=p-> free(p); next; return 1; } 3 2．5 顺序队的算法操作 1. 环队列 在顺序队中，通常让队尾指针 指向刚进队的元素位置，让队首 刚出队的元素位置。因此元 要向后移动，这样经过一系列 元素，但仍处，虽然队中已经没有 个 题，我们可以把数组 两者来到数组尽头无法继续往下走的情况， 图 循环队列元素的进队出队 以循环执行语句 front=(front+1)%8 在一个无限循环中，front 的取值为 期的无限循环数，也就是 front 沿着上图的环在行走。对于一 ront=(front+1)%MAX(MAX 是数组长度)。图 3.2 是循环队列两个特殊 队空（rear 的情况和 front 类似）。 完整版：http://item.taobao.com/item.htm?id=5616898223 图 3.5 循环队列队空与对满的判断 由上图可以看出，循环队列必须损失一个存储空间，如果右图中空白处也存入元素的话， 队满的条件也成了 front==rear，和队空条件相同而无法区分了。 2.循环队列的要素 通过以上讲述我们总结出顺序队列的四个要素。 （1）两状态： ①队空状态 qu.rear==qu.front ②队满状态 （qu.rear+1）%MAX==qu.front （2）两操作： ①元素 x 进队操作（移动队尾指针） qu.rear=(qu.rear+1)%MAX;qu.data[qu.rear]=x; ②元素 x 出队操作（移动队首指针） ，也是先移动指 针再 可能有不同的次序，其实本质是一样的，考生只需去适应一种写 法， 据题目描述确定是先存取元素，再 移动 理顺序。 0。 //只要两者重合，即为队空。 else 0; enQueue(SqQueue &qu,int x) qu.front=(qu.front+1)%MAX;x=qu.data[qu.front] 说明：本书中，元素入队时，先移动指针，后存入元素；元素出队时 取出元素。其他书上 对于程序设计题目已经足够。对于选择题，则可根 指针，还是其他处 3.始化队列算法 void InitQueue(SqQueue &qu) { qu.front=qu.rear=0; //队首队尾指针重合，且指向 } 4．判断队空 int QueueEmpty(SqQueue qu) { if(qu.front==qu.rear) //不论队首队尾指针指向数组中的哪个位置， return 1; return } 5．元素进队 int { 完整版：http://item.taobao.com/item.htm?id=5616898223 ront) //队满的判断条件，满则不能入队。 a[qu.rear]=x; //再存入元素。 空则不能出队 。 动指针。 函数在书写程序题目的时候并不实用， 需要 ． 队 结构存储队列，这里采用单链表来实现。链表的特点就是不存在 状态两个操作，如下。 ）两个状态： ront==NULL（为什么有两个，后边解释） 队 状态： ①元素进队操作（假设 p 指向进队元素）： ext=p;lqu->rear=p; qu->front=p->next;x=p->data;free(p); 个链队的动态变化过程，由图可以看 front 和 rear 任何一个为空都 可以 if((qu.rear+1)%MAX==qu.f return 0; qu. rear=(qu.rear+1)%MAX; //先移动指针。 qu.dat return 1; } 6．元素出 队 int deQueue(SqQueue &qu,int &x) { if(qu.front==qu.rear) //队 return 0; qu.front=(qu.front+1)%MAX; //先移 x=qu.data[qu.front]; //再取出元素。 return 1; } 说明：这里和前面讲到的情况一样，以上这些 在题目中提取其中有用的操作。 3 2．6 链队的算法操作 链 就是采用链式存储 队列满上溢的情况（其实这里也不太严格，内存满了就上溢了）。 1.链队的要素 链队也有两个特殊 （1 ①队空状态： lqu->rear==NULL 或者 lqu->f ② 满 不存在队列满的情况。 （2）两操作： lqu->rear->n ②元素出队操作（假设 x 存储出队元素）： p=lqu->front;l 图 3.2 显示了一 用来判定链队为空。 完整版：http://item.taobao.com/item.htm?id=5616898223 图 3.6 链队元素的进队出队 1．初始化链队的算法 void InitQueue(LiQueue *&lqu)//初始化队列 { lqu=(LiQueue*)malloc(sizeof(LiQueue)); lqu->front=lqu->rear=NULL; } 2．判断队空的算法 int QueueEmpty(LiQueue *lqu)//判断队空 { if(lqu->rear==NU return 1; d enQueue(LiQueue *&lqu,int x) NULL) //若队列为空，则新结点是队首结点，也是队尾结点。 u->front=lqu->rear=p; { lqu->rear->next=p; //将新结点链接到队尾，rear 指向它。 ear=p; LL||lqu->front==NULL) else return 0; } 3．入队的算法 voi { QNode *p; p=(QNode*)malloc(sizeof(QNode)); p->data=x; p->next=NULL; if(lqu->rear== lq else lqu->r } } 完整版：http://item.taobao.com/item.htm?id=5616898223 4．出队的算法 int dequeue(LiQueue *&lqu,int &x) { QNode *p; if(lqu->rear==NULL) //队空不能出队。 return 0; p=lqu->front; 队列中只有一个结点时的 特殊处理。 ULL; lqu->front=lqu->front->next; ; 操作的意义即可 的定义、操作等等都要简单，因此在考研的程序设计题目中， 3．3 特殊矩阵的压缩存储 素或者 0 元素的分布有一定规律的矩阵。为了节省存储空间，可 ，对其进行压缩存储，使多个相同的非零元素共享同一个存储单元， 0 间。特殊矩阵的主要形式有对称矩阵，对角矩阵等。它们都是方阵。 的压缩存储 n(n+1)/2 个元素的空间中。不失一般性，假设以行序为主序存储其下三角（包括对角线） 的元素。 假设以一维数组 sa[0 的存储结构，则 A 中任一 元素 ai,j 和 sa[k]之间存在着如下对应关系： if(lqu->front==lqu->rear) // 出队操作需 u->rear=N lqu->front=lq e els x=p->data free(p); return 1; } 说明： ．以 记忆，读程序并且理解每一步 。1 上的算法，不需要 2．与链队相比，顺序队 要尽量采用顺序队来解决问题，而尽可能地避免用链队，除非题目明确规定要用链队。 特殊矩阵是指非 0 元 以利用特殊矩阵的规律 对 元素不分配存储空 1.对称矩阵 若一个 n 阶方阵 A 中的元素满足 ai,j=aj,i(0≤i,j≤n-1)则称其为 n 阶对称矩阵。 由于对称矩阵中的元素关于主对角线对称，因此在存储时只存储对称矩阵中上三角或 者下三角的元素，使得对称的元素共享一个存储空间。这样就可将 n2 个元素压缩存储到 ……n×(n+1)/2]作为 n 阶对称矩阵 A k j 当 ij时 i 当 ij时 2.三角矩阵的压缩存储 三角矩阵有上三角矩阵和下三角矩阵两种，上三角矩阵的下三角元素均为常量 c，下 三 角矩阵则反之。因此重复元素 c 可共享一个存储单元。矩阵 A 的元素 a[i][j]和存储数组 sa[0……n×(n+1)/2]之间的关系为： 完整版：http://item.taobao.com/item.htm?id=5616898223 上三角矩阵：k j1 , 当 ij时 , 当 ij时 （常数 c） 下三角矩阵：k j , 当 ij时 , 当 ij时 （常数 c） m 1≤m bc+（假设 x=“bc+”） 二步： （假设 ） 考查栈的应用。在栈的众多应用中，括号匹配是一个重要的体现。 12. 本题考查链队的基本操作及其存储结构。连队示意图如下： 要修改尾指针，删除结点 a 则需要修改头指针，当 将 a 因此本题选 D。 13.D 8.B 题考查栈基本概念的扩展。两栈共享空间，栈满的时候应该是两栈顶指针本 候，相 top1+1=top2。本题选 B。 9.D 本题考查 B 是函 要用到栈（前边讲过栈有记忆当前状态的功能）。因此选 D 10.B 本题考查中缀表达式转化成后缀表达式的方法。 本题转化过程如下图 由上图可以写出以下转化过 第 第 a*x -> ax* y=“ax*” 第三部: y-d -> yd- 将 xy 还原后得到：abc+*d- 11.D 本题 D 由此图可见，如果删除结点 c 则需 bc 都删除掉的时候，头尾指针都需要修改。 完整版：http://item.taobao.com/item.htm?id=5616898223 本题又是一个基本知识的扩展。用单链表来表示队列，当队列中有多个元素的时候， 只改变头指针即可，当队列中只有一个元素时，此时，队头队尾指针都指向这个元 它的话显然两指针都要置 ，因此本题选 考查栈的应用。函数的递归调用过程要用到系统栈。 15.D 本题考查队列的基本操作。入队时队尾变化为 rear=(rear+1)%MAX,其中 MAX 是数 组元素最大个数，题干中数组最大个数为 m+1，因下标从 0 开始。因此答案为 D 16.B 本题考查循环队列的基本操作。在循环队列中入队执行 rear=(rear+1)%MAX;出队 执行 front=(front+1)%MAX;将本题数据代入其中可以算出最后 rear 为 2，front 为 4， 答案选 。 考查循环队列的判空条件。当首尾指针重合时队空。选 B。 18. 19.C 考查栈和队列的概念与比较。栈和队列都是限制存取点的线性结构。 20.A 考查数组的存储。不论数组是几维，在存储器中的存放方式都是一维的，只需根据 所给 。对于 组第一个元素 a[0][0]的存储地址是 860，从这一句话我们可以知道，数组下标 储地址是 考查数组的不同存储方式。对于元素 a[i][j]，前面有 j-1 列，第 1 列到第 j-1 (j-1)/2个元素， 故 k=j (j-1)/2+i-1 B 0 1）。 A，因 D,A。 23. 考查栈的基本操作。执行前三句后，栈 st 内的值为 a,b 其中 b 为栈顶元素。执 25.C 删除操作 素，删除 NULL D 14.C 本题 B 17.B 本题 C 本题考查栈和队列的比较。两者共同点即为只允许在端点处插入和删除元素。 本题 本题 元素 a 的下标，结合存储方式（按照行优先还是列优先），算出 a 是数组中第 k 个元素， 然后用 k×每个元素所占的存储单元，所得结果加上数组首地址，就是 a 的存储地址 本题，数 的两个分量都是从 0 开始，因此 a[3][5]是第 k=3×10+5=35 个元素，则 a[3][5]的存 860+35×4=1000。因此本题选 A 21.D 本题 列的元素个数分别为1到j-1个，由等差数列求和公式可算得一共有j× × （注意 数组是从 开始存元素，因此要减去 22.D,A 本题考查栈的性质。A,B,C,D 依次进展，则从栈顶到栈底的元素序列为 D,C,B, 此本题选 A 本题 行第四局句后，x 的值为 b，执行最后一句后 x 的值为 a。因此本题选 A。 24.C 本题考查栈的基本操作。由题知，先经过两次进栈操作，后经过两次出栈操作，此时 栈必为空，因此判断栈空函数 StackEmpty()的返回值为 1。本题选 C。 完整版：http://item.taobao.com/item.htm?id=5616898223 本题考查根据入栈序列对出栈序列的判断。当 p1=3 时，说明 1,2,3 都已进栈。立即 然后可能出栈，即为 2；也可能 4 或者后面的元素进栈，再出栈。因此 p2 可能是 2， … 中的任何一个，但一定不是 。 结点），需要 始结点的前驱结点。只有表头指针没有表尾指针的循环单链表，不方便查找开始 结点 27.C 考查栈的基本操作。栈空无法进行出栈操作，因此本题选 C。 本题考查队 的性质 列先进先出，由入队序列 1,2,3,4 知出队序列必为 1,2,3,4， B。 29. 讨论：①当 r 时，栈内元素为 r-f。②当 r t=rear->next; //将 s 结点链入队尾 基础题 1．答： （1） 列的开始 （2 : A,B,C A,B,C 和 B,A,C 均可得到输出元素序列 A,B,C。对于合法序列 A,B,C，我们使用本题约 定的 SXSXSX 操作序列；对于合法序列 B,A,C，我们使用 SSXXS 操作序列。 （ ）由（ ）中分析可以写出以下代码： in /*判断字符数组 ch 中序列是否是合法序列。如是，返回 1 否则返回 0。*/ { i if(O>I) return 0; //扫描过程中出现O的个数大于I 的情况，则一 i++; } if(I!=O) return 0; //I 的总数和 O 不 else return 1; //合法返回 1。 } A,B 的相对顺序已经确定，必为 B 先与 。E 的位最先出栈，且 C 先与 D，则 B 与 A 中间，或者 A 后前， ,E B,A C,D,B,E, 队基本操作的扩展，知 出队操作，则需要根据 指向终端 /*rear 是带 { 头结 LNode *s=( data=x; s->nex rear->next=s; 完整版：http://item.taobao.com/item.htm?id=5616898223 rea ear 指向新队尾 ）出队 Queue(LNode *rear,int &x) (rear->next==rear) s->data; rear)rear=rear->next; //如果元素出队后队列为空需要特殊处理， /将 rear 指向头结点。 1; //操作成功返回 1。 4.分析： 用一 列 其中 MAX 是队列长度。设置队头指针 front 和 rear 指向队尾元素。 定义满足 front==rear 时为队空。从队尾删除元素，则 rear 向着下标减小的方向行走， 从队 标减小的方向行走，因此当满足 rea 的结构定义 ef struct { X 为已定义常量。 }cy （2） ①出 t dequeue(cycqueue &Q,int &x) /*本算法 否 返回 0。*/ { if(Q.front==Q.rear) //队空无法出队，返回 0。 return 0; //出队成功，返回 1。 元 */ r=s; //r } （2 int De /*rear 是带头结点的循环链队列的尾指针，x 接收出队元素，操作成功返回 1 否则返 回 0。*/ { LNode *s; if return 0; s=rear->next->next; //s 指向开始结点。 rear->next->next=s->next; //队头元素出队。 x= if(s== / free(s); //释放队结点空间。 return } AX-1]实现循环队 ，维数组 data[0……M 队尾指针 rear，约定 front 指向队头元素的前一位置， 头插入元素，front 同样向着下 r==(front-1+MAX)%MAX 时队满。 （1）队列 edtyp int data[MAX]; //假设 MA int front,rear; cqueue; 算法实现： 队算法 in 实现“从队尾删除”，若删除成功用 x 接纳删除元素，返回 1， 则 else { x=Q.data[Q.rear]; Q.rear=(Q.rear-1+MAX)%MAX; //修改队尾指针。 return 1; } } 队算法 ②入 int enqueue(cycqueue &Q,int x) ” 素 x。/*本算法实现“从队头插入 完整版：http://item.taobao.com/item.htm?id=5616898223 { =(Q.front-1+MAX)%MAX) //队满 urn 0; Q.data[Q.front]=x; //x 入队列。 题算法中用到了一个操作:Q.front=(Q.front-1+MAX)%MAX;如果把这一 Max-1,Max-2, ……2,1,0,Max-1,Max-2…… 果正好相反。这 分 本题为循环队列基本算法操作的扩展。在队列结构定义中加入 tag。用 tag 判断队列 是否 程如下： 队列 Queue qu; qu.front==qu.rear&&qu.tag==0 qu.front==qu.rear&&qu.tag==1 } ueueEmpty(Queue qu)//判断队是否为空。 front==qu.rear) 1; 。 if (Q.rear= ret else { Q.front=(Q.front-1+MAX)%MAX; //修改队头指针。 } } 说明：本 句放在一个循环中，front 指针则沿着 的无限循环数行走，这个操作和 Q.front=(Q.front+1)%MAX;实现的效 两个操作在程序设计题目中是很常用的。 5. 析 ： 为空，用 front==rear 判断队满。具体过 队列的结构定义： edef struct typ { int data[MAX];//假设 MAX 为已定义的常量。 ; int front,rear ag; int t }Queue; 定义一个 队列的各要素： 初始时 qu.tag=0; qu.front=qu.rear; 队空条件 条件队满 算法描述： void InitQueue(Queue &qu)//初始化队列。 { qu.front=qu.rear=0; qu.tag=0; int Q { if(qu.front==qu.rear&&qu.tag==0) return 1; else return 0; } int QueueFull(Queue qu)//判断队是否为满。 { ==1&&qu.if(qu.tag turnre else 0; return } nQ 元素进int e ueue(Queue &qu,int x)// 队 { if(QueueFull(qu)==1) 完整版：http://item.taobao.com/item.htm?id=5616898223 return 0; +1)%MAX; =x; //只要进队就把 tag 设置为 1。 qu)==1) //只要有元素出队，就把 tag 设置为 0。 } 0。插入成功后应设置为 1，删除成功后应 设置 0 才有可能满，在删除操作后队列才有可能空。tag 的值再配合上 r 这一句的判断就能正确区分队满与队空。 （2）思考 分析： 设 str 是 r[k-1]的 所有字符 tr,k,n)为 str[0]~str[k]的全排列，prem(str,k-1,n) 处理的字符个数比 prem(str,k,n)处理的字符少一个。假设 perm(str,k-1,n)可求， 对于 合 prem(str,k-1,n)，则得 到 p 由此 void prem2(char str[],int k,int n) { int cha if( else for(i=0;i<=k;i++) else { qu.rear=(qu.rear a[qu.rear]qu.dat qu.tag=1; return 1; } } t &qu,int &x)//元素出队in deQueue(Queue { if(QueueEmpty( return 0; else { qu.front=(qu.front+1)%MAX; qu.front]; x=qu.data[ tag=0; qu. return 1; } ：对于 tag 值的设置，初始时一定为说明 为 ；因为只有在插入操作后队列 front==rea 题 含有 n 个不同字符的字符串，perm(str,k-1,n)为 str[0]~st 的全排列，perm(s str[k]位置，可以取 str[0]~str[k]任何值，再组 rem(str,k,n)。 可以 ： 写出以下代码 i,j; r temp; k==0) { for(j=0;j<=n-1;j++) cout<