文章预览
结点的构造
要构造一种结点，必须先定义结点的数据类型。下面介绍链表和二叉树结点结构型的定义方法。
链表结点的定义
链表的结点有两个域：一个是数据域，用来存储数据；一个是指针域，用来指向下一个结点。如图：
image20191225204205047.png
链表结点的结构型定义如下：
typedef struct Node
{
int data;//默认int型，其它类型也是可以的
struct Node *next; //指向下一个Node型变量的指针
}Node;
上述结构体的名字为
Node
，此结构体由两部分组成：数据域int型和指针域Node类型。
凡是结构体（假设为a）内部有这样的指针型（假设为b），b是用来存放和a类型相同的结构体变量地址的指针型，则在定义a的typedef struct语句之后都要加上a这个结构体的名字（也就是Node）
。
二叉树结点定义
二叉树结点结构就是在链表结构的基础上，再加上一个指向自己同类型变量的指针域。
typedef struct BTNode
{
int data;//默认int型，其它类型也是可以的
struct BTNode *lchild;//指向左边孩子结点的指针
struct BTNode *rchild;//指向右边孩子结点的指针
}
以上两种就是链表和二叉树的定义方法，其余的结点都是通过这两种衍生来的（二叉树其实也是通过链表衍生来的，仅仅是多一个指针域而已）。
学习上文之后，可以知道链表和二叉树结点的定义方法，结点定义好之后，需要用它制作新的结点。
① BTNode BT;
② BTNode *BT;
BT = (BTNode *)malloc(sizeof(BTNode));//很重要，熟练掌握
②句的执行过程：先定义一个结点指针BT，然后用函数malloc()申请一个结点的内存空间，最后让指针BT指向这个结点空间。
同理，还有一个动态申请数组空间的方法
int *p;
p = (int *)malloc(n * sizeof(int));
很明显可以看出来，申请数组空间的方法和上面申请结点的方法不同之处在于sizeof运算符要乘n。
sizeof是运算符，并不是函数
链表和二叉树结构体的定义还可以写成以下方式：
链表结点
struct Node
{
int data;
Node *next;
}
二叉树结点
struct BTNode
{
int data;
Node *lchild;
Node *rchild;
}
注意：此种写法虽然简单，但是在一些纯C编译器中是无法编译成功的！
typedef和#define
typedef：可以自定义一些数据类型，也可以给现有的数据类型起别名。
define：常量定义
函数
涉及到算法，肯定需要使用函数，函数需要有以下注意点：
-
被传入的参数是否会改变
int a;
void f(int x)
{
++x;
}
f(a);
需要注意的是，上述代码如果需要改变传入参数a的值，则需要将代码做如下改动：
int a;
void f(int &x)
{
++x;
}
f(a);
-
参数引用型的其它demo
void insert(Sqlist &L,int x)
{
//L本身需要发生改变，所以传参需要使用引用型
int p,i;
p = LocateElem(L,x);
for(i = L.length - 1;i >= p;--i)
L.data[i+1] = L.data[i];//全部向后移动一位
L.data[p] = x;
++(L.length);
}
详解：L是一个结构体(Sqlist型)，data[]数组是它的一个分量，属于Sqlist的一部分，data改变，也就是L自身的改变。
int SearchAndDelete(LNode *C,int x)
{
LNode *p,*q;
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只是一个指向链表结点的一个指针，是通过指针操作函数之外的结点的，并不存在是否为引用型。
………………………………
