1、数据结构高分笔记购书： 讨论群：108945580 立志于打造最贴近考生实际的辅导书 计算机考研之数据结构高分笔记 率辉 编著 周伟 张浩 审核 数据结构高分笔记购书： 讨论群：108945580 数据结构高分笔记精彩摘录之考研数据结构必备基础知识 作者的话： 大部分同学在学习数据结构时，想必对数据结构课本里的伪代码多多少少有点不是很 清楚，特别是自己在动手编写算法的时候，明明知道算法的思路，但是编写出来的程序就 是不标准，可能在考试的时候就会吃大亏。所以在开始数据结构的旅程之前，我觉得有必 要将一些基本功提前告知你们，掌握了这些东西，在本章以后的章节中，才能以此为基础 来修炼更高深的武功。
2、本章概略 针对考研数据结构的C /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 coutL; /30 cinn; /31 for(i=0;iRi; /33 RCR(R,n,L); /34 for(i=0;i=n) /14 coutdata;一般来说，用结构体变 量直接取分量，其操作用”.”，用指向结构体变量的指针来取分量，其操作用”-”。 这里再扩展一点，前边我们提到，如果p 是指针（假设已经指向x） ，*p 就是取这个变 量的值，a=*p;等价于a=x;那么对于中的B
3、T 指针，怎么用”.”来取其data 值呢？类比 p，*BT 就是BT 指向的变量，因此可以写成(*BT).data;（(*BT).data;与BT-data 是等价的） 。注意 *BT 外边要用括号括起来，不要写成*BT.data。在 C 或 C+语言中这 是一种好的习惯，在你不知道系统默认的运算符优先级的情况下，你最好依照自己所期望 的运算顺序加上括号。有可能这个括号加上是多余的，但是为了减少错误，这种做法是必要 的。对于与刚才那句，我所期望的运算顺序是先算*BT，即用”*”先将 BT 变成它所指的变数据结构高分笔记购书： 讨论群：108945580 量，然后再用”.”取分量值。因此写成(
4、*BT).data。比如这样一个式子a*b/c，假设你不 知道系统会默认先算乘再算除， 而你所期望的运算优先顺序是先算乘再算除， 为了减少错误， 你最好是把它写成(a*b)/c，即便这里的括号是多余的。 （4）关于typedef 和#define 1）typedef 有的书上在定义变量的时候会出现一些你在程序设计教材中从来没见过的诡异的数据 类型，比如严奶奶书上就有类似于 Elemtype A;的变量定义语句，这里的 Elemtype 是 什么类型，新来的同学常常会一头雾水。要说明这个问题，我们先来说明一下typedef 的 用法。一句话，typedef 就是用来给现有的数据类型起一个新名字的
5、，我们在结构类型定 义时用到过，如 typedef struct TypeA;即为给 “struct”起了一个 名字 TypeA，就好比你制作了计算机中的整型，给他起了个名字为 int。并且如果我想给 int 型起个新名字 A,就可以这样写 typedef int A;这样的话定义一个整形变量 x 的时 候 A x;就等价于 int x;在考研中typedef 用的最多的地方就在结构型的定义过程中， 其他的地方几乎不用。你可以这样理解typedef 是用来起名字的，新定义的结构型没有名 字， 因此用typedef 给它起个名字是有必要的， 但是对于已有的数据类型， 如int， float 等已
6、经有了简洁的名字，还有必要给它起个新名字吗？有必要，但不是在考研数据结构中。 为什么有必要，有兴趣的同学可以去查下资料，查完你会发现，typedef 对程序设计的贡 献很大，但是对于考研答卷，用处不大，所以大家对其用法不必深究。说到这里大家就明白 了，严奶奶的书上之所以有那么多大家不认识的数据类型，只不过是严奶奶悄悄的给我们认 识的数据类型起了新名字而已。 2）#define 在严奶奶的书上除了我们没见过的数据类型以外，还有一些东西我们也没见过，比如在 一个函数中她会写到 return ERROR； return OK；之类的语句，对于经常在编译器上 写代码的同学，乍一看到这种语句会十分的不爽
7、，立马就会想，ERROR 和OK 这样的东西能 编译通过？或者就是怀疑自己语言水平太差， 严奶奶写的程序里边有太多自己看不懂的地方 了，信心大减。其实不然，和typedef 一样，严奶奶悄悄的用#define 语句处理过ERROR 或者OK 之类的词了。其实ERROR 和OK 就是两个常量，作为函数的返回值，来提示用户函 数操作结果的。严奶奶初衷是想把 0,1 这种常作为函数返回标记的数字定义成 ERROR 和 OK（一般出错返回 0，成功返回 1） ，这样比起数字来更人性化，更容易理解，但结果却适 得其反，让新手们更困惑了。#define 对于考研数据结构可以说没有什么贡献，我们只要 认得它
8、就行，写程序时一般用不到。比如#define MAX 50 这句，即定义了常量MAX（此 时x=50;等价于x=MAX;） 。 在写程序大题的时候如果你要定义一个数组， 如int AMAX; 加上一句注释： “/*MAX 为已经定义的常量，其值为 50*/”即可。没必要跑到你的程序最 前边去加上#define MAX 50 这一句，原因前边已经讲过。 严奶奶的书中有很多用自己加工过的代码书写的程序， 和编译器上我们习惯的写法有很 大出入，所以对于新手较难理解。本书的作用在很大程度上就是做了一个翻译的角色，不过 是站在学生的角度把课本上用过于严谨以及专业化的词语描述的思想用通俗易懂的语言表 达给
9、你而已。 2函数 说明:只要是算法设计题，必用到函数，所以其中的一些注意事项这里有必要说一下。 （1）用函数来缩短代码 如果有一段较长的操作需要在一个函数中反复多次使用， 那么你最好把这个操作做成一 个函数，在你要用的地方调用它，会节省很多答题空间。比如： 数据结构高分笔记购书： 讨论群：108945580 void f() /1 /2 /3 /4 /5 /6 /7 /8 这个函数中的8 句组成了一个操作。这个操作在另一个函数（函数名为F）中要多次用 到。此时我们就可以把这8 句做成一个函数，当用到的时候调用即可，比如： void F() f(); f(); f(); 从上边可以看出，如果不用
10、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，即句的执
11、行过程拆开看来是这样两句：x=a;x+;因 此a 的值在执行完,两句之后不变。 如果我想让 a 依照 f()函数体中的操作来改变应该怎么写呢，这里就要用到函数的引 用型（这种语法是C+中的，C 中没有，C 中是靠传入变量的地址的方法来实现的，写起来 比较麻烦且容易出错，因此这里采用C+的语法） ，其函数声明方法如下： void f(int 这样就相当于a 取代了x 的位置，函数f()就是在对a 本身进行操作，执行完两 句后，a 的值由0 变为1。 上边讲到的是对针对普通变量的“引用型” ，如果传入的变量是指针型变量，且在函数 体内要对传入的指针进行改变，则需写成如下形式： void f(int
12、 * 执行完上述函数后，指针x 的值自增1。 说明：这种写法很多同学不太熟悉，但是它在树与图的算法中应用广泛，在之后的章 节中考生要注意观察其与一般引用型变量的书写差别。 上边是单个变量作为函数参数的情况。如果一个数组作为函数的参数，该怎么写呢？传 入的数组是不是也有“引用型”一说呢？对于数组作为函数的参数，这里讲两种情况，一维 和二维数组。 一维数组作为参数的函数声明方法： void f(int x,int n) ; 对于第一个参数位置上的数组的定义只需写出两个中括号即可，不需要限定数组长度 （即不需要写成 f(int x5,int n)，即便是你传入的数组真的是长度为5） ，对于第二 个参数n， 是写数组作参数的函数的习惯， 用来说明将来要传进函数加工的数组元素的个数， 并不是指数组的总长度。 二维数组作为参数的函数声明方法： void f(int xMAX，int n) ; 如果函数的参数是二维数组，数组的第一个中括号内不需要写上数组长度，而第二个中 括号内必须写上数组长度（假设MAX 是已经定义的常量） 。这里需要注意，你所传入的数组 第二维长度也得是MAX，否则出错，比如： void f（int x5） ; int a105; int b103; f(a); /参数正确 f(b); /参数错误
