C – 浅析链表中的点点滴滴 《C语言篇》

最近大家都在学习数据结构,其中链表部分是目前出问题最多的地方,这里就我最近收到的问题进行简单的整理,有出错的地方欢迎指出

本文讨论一下几个问题:
1. 结构体怎么声明和定义变量?
2. struct Node p 和 struct Node *pp 什么区别?
3. typedef 到底定义了什么?
4. 我该如何将一个结构体变量传入自定义的方法并且对其进行操作?

1. 结构体怎么声明和定义变量?

结构体类似下面这种样式

struct 结构体名{
	int a;
	double b;
}; //注意分号

定义结构体变量

struct 结构体名 a;

注意在C语言中使用 ‘ struct  结构体名 ‘ 两个关键词来定义一个结构体变量,当然在C++中可以直接用’ 结构体名’ 来定义变量

//在C++中与上面等效
结构体名 a;

注意在声明结构体的时候不能将其变量赋值,即上面的结构体中不能将int a书写成int a = 0;


2. struct Node p 和 struct Node *pp 什么区别?

这两个浅层次理解就是p就是一个结构体,可以用 p.a 的方式来设置a的值,而*pp 是一个结构体指针,它本身不能和前面的p一样来设置a的值,需要先指向一块结构体大小的内存,然后就可以通过pp->a的方式来设置a的值。

往深处讲,前者和后者的在内存中的分配不同,就像C++中用new和不用new实例化对象一样。

这里注意一点,很多同学都是从Java转向C数据结构的,在Java可以用 . (俗称点语法)调用对象的成员变量。但是在p和pp中, p可以用 . 来调用成员,而pp则要用 -> 的方式来调用成员,pp->a表示引用  pp所指向的结构体中的成员a。

下面用代码区分一下这两种形式。


#include 
#include 	//在调用malloc()方法时用到此库

struct Node{
	int a;
};

int main(){

	//第一种方式 定义一个正常的结构体变量
	struct Node p1;
	p1.a = 1;
	printf("%d\n", p1.a);

	//第二种方式 定义一个正常的结构体变量,并直接赋值
	struct Node p2 = {2};
	printf("%d\n", p2.a);

	//第三种方式 定义一个结构体指针
	struct Node *pp = (struct Node *)malloc(sizeof(struct Node));
	pp->a = 3;
	printf("%d\n", pp->a);

	return 0;
}

可以明显看出,第一种第二种方式是正常的结构体变量,可以直接或间接的赋值,第三种使用了结构体指针,必须让指针pp指向一块新的结构体类型内存,然后才能通过pp指针对结构体操作。 区别在于,正常的结构体变量只能在程序结束时释放掉内存,而接哦固体指针可以使用free()方法在程序运行时释放对应的内存。


3. typedef 到底定义了什么?

typedef 在百科上的解释是 为复杂的声明  定义简单的别名,就理解为起绰号吧。

typedef struct NodeName{
	int a;
}Node;

//如此之后,下面两个定义是等效的
struct NodeName p1;
Node p2;

这里一定要正确理解原来的定义方式是什么,修改后的定义方式。 这里 struct NodeName 与 Node 是等效的。
然而当出现下面的书写方式时,有些同学可能就搞混了到底是谁是谁的别名。

typedef struct NodeName{
	int a;
}NodeA,NodeB;

//如此之后,下面三个定义是等效的
struct NodeName p1;
NodeA p2;
NodeB p3;

这三种定义方式是等效的,就好比一个人有两个绰号一样,

或许当你想起这位小哥的时候你就理解typedef的作用了。

那我们再看一种复杂的typedef

typedef struct NodeName{
	int a;
}Node, *pNode;

//如此之后,下面四个定义是等效的
struct NodeName p1;
Node p2;
Node *p3 = (Node *)malloc(sizeof(Node));
pNode p4 = (pNode)malloc(sizeof(Node));

注意我只是说方法上是等效的,实际上p1,p2 和 p3,p4 是有区别的,具体去看问题 2。

在这里我们给struct NodeName 起了两个不同类型的别名,一个带*一个不带*,Node则和前面的例子一样属于正常起绰号,凡是带*号的那就和指针有关了,用pNode定义变量时其实就相当于Node *,只不过人家pNode在一开始就写过*了,所以效果是等同的(看上述代码)。
那么还有一个问题,为什么p4在使用malloc的时候我最后的sizeof()里面是Node而不是pNode,因为给sizeof()方法传入指针时,只会求的指针本身的大小,而不是Node的大小,这就是为什么有时候自定义方法对数组操作时需要把数组的长度一并传给自定义方法。

因为在链表中我们会大量的操作内存,比如分配新的内存,回收旧的内存等操作,所以在链表中会大量的使用指针,如果每次声明结构体指针都要用  Node *p 这样的方式也许会显得比较麻烦,所以会有一部分同学把*直接写在typedef那里,那么可以直接用pNode p 来定义结构体指针了,只要记得凡是pNode定义的变量都是指针就好。(tip:  p代表point,所以一般程序中都会用p代表指针变量或者与指针有关的关键词)


4. 我该如何将一个结构体变量传入自定义的方法并且对其进行操作?

写这个问题原因是有的同学会遇到类似这样的问题 (VC 6.0):

假设我们现在要写一个方法,传入一个结构体,然后在方法中改变结构体的值。

void changeA1(Node p){
	p.a = 2;
}

void changeA2(Node *p){
	p->a = 2;
} 

void changeA3(Node &p){
	p.a = 2;
}

int main(){
	Node p;
	p.a = 1;

	changeA1(p);

	changeA2(&p);

	changeA3(p);
}

这是我在最近收到的代码中遇到的几种写法,主要是形参的不同,然后在主方法调用三个自定义的方法。结果有的地方就会出现上图所示的错误。
这里比较混乱,我们先想一下C语言传参的方式,值传递和址传递两种,我暂时没见过类似changeA3(Node &p)那样的方式,&是取地址符,在这里没有取地址的必要,所以这种定义方式一般不要去考虑,从值传递和址传递两种去考虑,即方法1 和 2, 方法1大家都知道,最终不会改变a的值,所以最终留下来的只有方法2 定义的时候形参为指针形式,使用的时候将结构体的地址传入。


void changeA2(Node *p){
	p->a = 2;
}

int main(){
	Node p;
	p.a = 1;
	//这里就用到了上述的取地址符&,意思是将p的地址取出来传给方法
	changeA2(&p);

	//第二种形式
	Node *p2 = (Node *)malloc(sizeof(Node));
	p2->a = 1;
	changeA2(p2);
}

目前遇到的有意义的问题暂时有这么多,后续继续填坑,理解能力有限,欢迎指出错误。