数据结构-基础知识详解

1. 结构型和指针型

（1）结构型

结构型是用户自己制作的数据类型。
例：

typedef struct {
   
	int a;
	float b;
	char c;
} TypeA;

注释：自定义了一个数据类型，名字叫做TypeA，再用TypeA去定义别的变量时，则该变量就会具有3个元素，分别是int型的a和float型的b和char型的c。
例：TypeA arr;表示自定义了一个TypeA类型的变量arr，arr是一个结构体，该结构体包含了3个不同类型的变量，可以使用arr.a、arr.b、arr.c来调用这3个变量。结构体变量arr相当于是一个数组，只不过其中的元素类型不同。
TypeA arr ：
例：TypeA arr[3];自定义了一个TypeA类型的数组arr，这里的arr就相当于是一个二维数组。
TypeA arr[3]：

（2）指针型

指针型变量内部装的是变量的地址，通过它可以找出这个变量在内存中的位置。指针型变量的定义方法对每种数据类型都有特定的写法。
例：

int *a;  // 定义了指向整型变量的指针a
TypeA *b;  // 定义了指向TypeA类型变量的指针b

int *a,b;
*a = &b;
x = **a;  // 等价于 x = b;

（3）结点的构造

要构造一种结点，必须先定义结点的结构类型
1）链表结点的定义

typedef struct Node {
   
	int data;
	struct Node *next;  // 指向Node型变量的指针
} Node;

注释：

• 这个结构体的名字叫Node。
• 由于组成此结构体的成员中有一个是指向和自己类型相同的变量的指针，内部要用自己来定义这个指针，所以写成struct Node *next;。
• 第一行中的Node也是该结构体的名字，但通常在该结构体的内部定义时使用，并且前面需要带上struct。
• 第三行中struct Node中的Node和第一行中的Node要相同。第三行注释中的Node则是指第四行中的Node。
• 第四行中的Node也是该结构体的名字，通常在外部需要定义该结构体类型的变量时用。
• 第一行和第三行的Node要相同，但和第四行的 Node可以不同，但为了方便，通常写成一样的。
• 如果内部没有使用指向Node类型的指针，则第一行中的Node可以不写，就像在（1）中定义的结构体那样，但是也可以写，内部用不用是自己的事。如果要用就必须要写，如果不用就随便。
  Node A; Node B; ：

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;中的p等价于btnode。
一般不写*btnode，需要时直接使用BTNode *p;

3）用上面制作好的结构来制作新结点
以二叉树结点的制作为例：有两种写法：

1. BTNode BT;
2. BTNode *BT; BT = (BTNode *）malloc(sizeof(BTNode));

2.的制作过程：先定义一个结点类型的指针BT，然后用malloc函数来申请一个结点的内存空间，最后让指针BT指向这片内存空间。

利用空间申请函数malloc()申请一个结点空间，并用一个指针指向这个空间的标准模板：
p = ( *) malloc(sizeof( )); // 一次申请一个结点
这一句完成后，就会得到一个相应类型的结点，并返回结点地址强制转为指针类型后赋值给p

另一种动态申请数组空间的方法，相当于一次申请了一组结点：

int *p;
p = (int *) malloc(n * sizeof(int));

申请了一个由指针p所指的（p指向数组中第一个元素的地址）、元素为int型的、长度为n的动态数组。取元素时和静态数组一样：p[0]，p[1]、…

关于前面1.和2.的补充解释：

• 2.中的BT是个指针型变量，用它来存储刚制作好的结点的地址。并且BT可以在需要的时候离开这个结点转而指向其他结点。而1.中则不行。1.中BT就是某个结点的名字，一旦定义好，它就不能脱离这个结点。
• 1.中取其data域的值赋给x：x = BT.data;用“ . ”。2.中则为：x = BT->data;或x = (*BT).data;用“ -> ” 。
• 一般来说，用结构体变量直接取分量，其操作用“ . ”；用指向结构体变量的指针来取分量，其操作用“ -> ”。

（4）关于函数的参数

1）引用型（&x）
这种语法是C++中的，C中没有，C中是靠传入变量的地址的方法来实现的。

void f(int &x) {
     // 调用该函数后，传入的参数值会加1
	x++;
}

如果传入指针型变量，并且要在函数体内对传入的指针进行改变：

void f(int *&x) {
     // 在树与图的算法中应用广泛
	x++;  // 指针x的值自增1
}

2）数组作为参数
将数组作为参数传入函数，函数就是对传入的数组本身进行操作，即如果函数体内涉及改变数据数据的操作，传入数组中的数据就会依照函数的操作来改变。可以理解为对于数组来说，只要数组作为参数，都是引用型。

上述内容是数据结构中及其重要的基础知识，需要反复实践和理解。

创作不易，喜欢的话加个关注，点个赞，谢谢谢谢谢谢谢谢！