引用于原文
（1）结构型
结构型可以理解为用户以已有数据类型（int,char,float…）为原料制作的数据类型。其实我们常用的数组也是用户自己制作的数据类型。数组是由多个相同数据类型的变量组合起来的，例如:
//maxSize是已经定义的常量:
int a[maxSize];
该语句就定义了一个数组，名字为a，就是将maxSize个整型变量连续地摆在一起，其中各整型变量之间的位置关系通过数组下标来反映。如果想制作一个数组，第一个变量是整型变量，第二个变量是字符型变量，第三个变量是浮点型变量，该怎么办呢？这时就用到结构体了。结构体就是系统提供给程序员制作新的数据类型的一种机制，即可以用系统已经有的不同的基本数据类型或用户定义的结构型，组合成用户需要的复杂数据类型。
例如，上面提到的要制作一个由不同类型的变量组成的数组可以进行如下构造：
typedef struct{
int a;
char b;
float c;
}TypeA;
上面的语句制造了一个新的数据类型，即TypeA型
语句int b[3];定义了一个数组，名字为b，由3个整型分量组成。而语句TypeA a;同样可以认为定义了一个数组，名字为a，只不过组成a数组的3个分量是不同类型的。对于数组b，b[0] 、b[1] 、b[2]分别代表数组中第一、第二、第三个元素的值。而对于结构体a，a.a 、a.b 、a.c分别对应于结构体变量a中第一、第二、第三个元素的值，两者十分相似
（2）指针型
指针型和结构型一样，是比较难理解的部分。对于其他类型的变量，变量里装的是数据元素的内容，而指针型变量内部装的是变量的地址，通过它可以找出某个变量在内存中的位置，就像一个指示方向的指针，指出了某个变量的位置，因此叫作指针型。
指针型的定义方法对每种数据类型都有特定的写法，有专门指向int型变量的指针，有专门指向char型变量的指针等。对于每种变量，指针的定义方法有相似的规则，例如以下语句：
int *a;
//对比一下定义int型变量的语句:int a;
char *b;
//对比一下定义char型变量的语句:char b;
float *c;
//对比一下定义float型变量的语句:float c;
TypeA *d;
//对比一下定义TypeA型变量的语句:TypeA d;
上面4句分别定义了指向整型变量的指针a、指向字符型变量的指针b、指向浮点型变量的指针c和指向TypeA型变量的指针d。与之前所讲述的其他变量的定义相对比，指针型变量的定义只是在变量名之前多出一个“*”而已。
如果a是个指针型变量，且它已经指向一个变量b，则a中存放变量b所在的地址。*a就是取变量b的内容（x=*a;等价于x=b;），&b就是取变量b的地址，语句a=&b;就是将变量b的地址存于a中，即大家常说的指针a指向b。
指针型用得最多的就是和结构型结合起来构造结点（如链表的结点、二叉树的结点等）。下面具体讲解常用结点的构造，这里的“构造”可以理解成先定义一个结点的结构类型，然后用这个结构型制作一个结点。虽不太严谨，但便于理解
（3）结点的构造
要构造一种结点，必须先定义结点的结构类型。下面介绍链表结点和二叉树结点结构型的定义方法。
1）链表结点的定义
链表的结点有两个域：一个是数据域，用来存放数据；另一个是指针域，用来存放下一个结点的位置。
链表的结构型定义如下：
typedef struct Node
{
//1:
int data;
//2:
struct Node *next;
}Node;
注释:
//1:这里默认的是int型，如需其他类型可直接修改。
//2:指向Node型变量的指针。
上面这个结构型的名字为Node，因为组成此结构体的成员中有一个是指向和自己类型相同的变量的指针，内部要用自己来定义这个指针，所以写成struct Node *next; 。这里指出，凡是结构型（假设名为a）内部有这样的指针型（假设名为b），即b是用来存放和a类型相同的结构体变量地址的指针型（如图1-2中结点A的指针next，next所指的结点B与结点A是属于同一结构型的），则在定义a的 typedef struct语句之后都要加上a这个结构型的名字，如上述结构体定义中的Node。与之前定义的结构型TypeA相比较，会发现这里的结构型Node在定义方法上的不同。
有的参考书中把上述链表结点结构定义写成如下形式：
typedef struct node
{
...
...
}Node;
可以发现，有一个node和一个Node，即结构体定义中的上下两个名称不同。这样写除了增加记忆负担之外，没有别的好处，在定义结点结构型的时候，将上下名称写成一致，并且如果结构体内没有指向自己类型的指针，你也可以把Node加上，这样更方便记忆。
有些可能会说还有更简便的形式写法如下：
struct Node
{
//1:
int data;
//2: Node *next;
};
注释:
//1:这里默认的是int型，如需其他类型可直接修改。
//2:指向Node型变量的指针。
这种写法虽然简单，但是在一些纯C编译器中是通不过的，因此采取第一种写法。
2）二叉树结点的定义
在链表结点结构型的基础上，再加上一个指向自己同一类型变量的指针域，即二叉树结点结构型，例如：
typedef struct BTNode
{
int data;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode;
只需要熟练掌握以上两种结点（链表、二叉树）的定义方法，其他的结点都是由这两种衍生而来的（其实二叉树结点的定义也是由链表结点的定义衍生而来的，二叉树结点只不过比链表结点多了一个指针而已），无需特意地去记忆。
说明：对于结构型，用来实现构造结点的语法有很多不同的表述，没必要全部掌握。上面讲到的那些语法用来构造结点已经足够用了，建议大家熟练掌握以上两种构造结点的结构体定义的写法，其他的写法可不予理睬。有些语法对考试来说既复杂又没有意义，例如，上面二叉树结点的定义有些参考书中写成：
typedef struct BTNode
{
int data;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode,*btnode;
可以看到在最后又多了个*btnode，其实在定义一个结点指针p的时候，BTNode *p;等价于btnode p; 。对于定义结点指针，BTNode *p;
这种写法是顺理成章的，因为它继承了之前int *a; 、char *b; 、char *c;和TypeA *d;这些指针定义的一般规律，使我们记忆起来非常方便，不必再加个btnode p;来增加记忆负担。因此在考研中我们不采取这种方法，对于上面的结构体定义，删去*btnode，统一一个BTNode就可以解决所有问题。
通过以上的讲解，知道了链表结点和二叉树结点的定义方法。结构型定义好之后，就要用它来制作新结点了。
以二叉树结点的制作为例，有以下两种写法：
①：BTNode BT;
②：BTNode *BT;
BT=(BTNode*)malloc(sizeof(BTNode));
①中只用一句就制作了一个结点，而②中需要两句，比①要繁琐，但是用得最多的是②。②的执行过程：先定义一个结点的指针BT，然后用malloc函数来申请一个结点的内存空间，最后让指针BT指向这片内存空间，这样就完成了一个结点的制作。②中的第二句就是用系统已有的malloc() 函数申请新结点所需内存空间的方法。数据结构中所有类型结点的内存分配都可用malloc()函数来完成，模式固定，容易记忆。
图1-3所示为利用空间申请函数申请一个结点空间，并用一个指针（图中为p）指向这个空间的标准模板。考生需要将这个模板背下来，以后制作一个新结点的时候，只要把结点结构型的名称填入图1-3括号中的空白处即可
p=(A*)malloc(sizeof(A)):
p:p指针指向新结点
A:所定义的结构型名称,malloc完成hour就得到一个相应类型的结点,并返回结点地址赋值给p
sizeof:测量结点所占空间大小的运算符。
说明：除此之外，还有一种动态申请数组空间的方法，相对于上面提到的一次申请一个结点，这种方法可以认为是一次申请一组结点，语法如下（假设申请的数组内元素为int型，长度为n，当然这里的int型可以换成任何数据类型，包括自己构造的结构型）：
int *p;
p=(int *)malloc(n * sizeof(int));
这样就申请了一个由指针p所指的（p指向数组中第一个元素的地址）、元素为int型的、长度为n的动态数组。取元素的时候和一般的数组（静态数组）一样，如取第2个元素，则可写成p[1] 。可以看到申请数组空间（或者说一组结点）的方法同上面申请一个结点的方法的不同之处仅在于sizeof运算符前要乘以系数n。sizeof是运算符，不是函数，但是在考研时你完全可以当作一个以数据类型为参数，返回值为所传入数据类型的大小的函数来理解。
②句中的BT是个指针型变量，用它来存储刚制作好的结点的地址。因BT是变量，虽然现在BT指向了刚生成的结点，但是在以后必要的时候BT可以离开这个结点转而指向其他结点。而①句则不行，①中的BT就是某个结点的名字，一旦定义好，它就不能脱离这个结点了。从这里就看到②比①更灵活，因此②用得多，并且②完全可以取代①（②中BT的值不改变就相当于①）。
对于①和②中的BT取分量的操作也是不同的。对于①如果想取其data域的值赋给x，则应该写成x=BT.data;，而对于②则应该写成x=BT->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，即便这里的括号是多余的。
（4）关于typedef和#define
1）typedef
一些教材中，变量定义语句中会出现一些你从来没见过的数据类型，如类似于Elemtype A;的变量定义语句，要说明这个问题，先来说明一下typedef的用法。typedef就是用来给现有的数据类型起一个新名字的，如typedef struct{…}TypeA;即给“struct{…}”起了一个名字TypeA，就好比你制作了计算机中的整型，给它起了个名字为int，如果再想给int型起个新名字A，就可以写typedef int A; 。这样定义一个整型变量x的时候， A x;就等价于int x; 。typedef用得最多的地方就在结构型的定义过程中，其他的地方几乎不用。你可以将typedef理解为是用来起名字的，新定义的结构型没有名字，因此用typedef给它起个名字是有必要的。但是对于已有的数据类型，如int、float等已经有了简洁的名字，还有必要给它起个新名字吗？有必要，
2） #define
除了我们没见过的数据类型以外，比如在一个函数中会出现return ERROR; 、return OK; 之类的语句。其实ERROR和OK就是两个常量，作为函数的返回值，来提示用户函数操作结果的，这样做的初衷是想把0、1这种常作为函数返回标记的数字定义成ERROR和OK，以达到比起数字来更人性化、更容易理解的目的，但结果却适得其反，让新手们更困惑了。 #define对于考研数据结构可以说没有什么贡献，我们只要认得它就行，写程序时一般用不到。例如， #define maxSize 50这句，即定义了常量maxSize（此时x=50;等价于x=maxSize;）。在写程序答题的时候如果你要定义一个数组，如int A[maxSize];加上一句注释/*maxSize为已经定义的常量，其值为50*/即可。
2．函数
（1）被传入函数的参数是否会改变
int a;
void f(int x)
{
++x;
}
上面定义的函数需要一个整型变量作为参数，并且在自己的函数体中将参数做自增1的运算。执行完以下程序段之后a的值是多少呢？
a=0; //1
f(a); //2
有些同学可能以为a等于1。这个答案是错误的，可以这样理解，对于函数f() ，在调用它的时候，括号里的变量a和句1中的变量a并不是同一个变量。在执行句1的时候，变量a只是把自己的值赋给了一个在f()的定义过程中已经定义好的整型变量，假设为x，即句2的执行过程拆开看来是这样两句：x=a;和++x;，因此a的值在执行完1、2两句之后不变。
如果要想让a依照f()函数体中的操作来改变，应该怎么写呢？这时就要用到函数的引用型（这种语法是C++中的，C中没有，C中是靠传入变量的地址的方法来实现的，写起来比较麻烦且容易出错，因此这里采用C++的语法），其函数定义方法如下：
void f(int &x)
{
++x;
}
这样就相当于a取代了x的位置，函数f()就是在对a本身进行操作，执行完1、2两句后，a的值由0变为1。
上面讲到的是针对普通变量的引用型，如果传入的变量是指针型变量，并且在函数体内要对传入的指针进行改变，则需写成如下形式
//（Attention）指针型变量在函数体中需要改变的写法:
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[ ][maxSize],int n)
要注意的是，将数组作为参数传入函数，函数就是对传入的数组本身进行操作，即如果函数体内涉及改变数组数据的操作，传入的数组中的数据就会依照函数的操作来改变。因此，对于数组来说，没有引用型和非引用型之分，可以理解为只要数组作为参数，都是引用型的。
（2）关于参数引用型的其他例子
//因为L本身要发生改变，所以要用引用型:
void insert(Sqlist &L,int x)
{
int p,i;
p=LocateElem(L,x);
for(i=L.length;i>=p;--i)
L.data[i+1]=L.data[i];
L.data[p]=x;
++(L.length);
}
讲解：L是个结构体类型(Sqlist型)，data[]数组是它的一个分量，属于Sqlist一部分，data改变就是L自身改变，insert()函数目的是在data[]数组中插入元素，使data[]数组内容改变，L也随之改变，因此传入L要用引用型。
int SearchAndDelete(LNode *C,int x)
{
LNode *p,*q;
p=C;
while(p->next!=NULL)
{
if(p->next->data==x)
break;
p=p->next;
}
if(p->next==NULL)
return 0;
else
{
q=p->next;
p->next=p->next->next;
free(q);
return 1;
}
}
讲解：C是指向一个链表表头的指针，注意仅仅是个指针，和1中的L不一样，它不代表整个链表，SearchAndDelete()函数可能删除被操作的链表中的除C所指结点（头结点不含链表元素信息）以外的任何一个结点，导致链表相关指针改变，但是C指针自己不变，因此这里传入C的时候不需要用引用型。
对这里的疑问在于，误认为C的地位等同于insert函数中L的地位，insert函数中传入的是L这个结构体类型变量整体，L的任何一部分改变都可以看作L自身的改变，需要引用型；而C只是指向一个链表表头的指针，整个链表无法像L一样作为整体传入
