实用的单向链表

08 July 2013

其实C语言也可以写成面向对象的形式，也许你听过C++、java这些面向对象的编程语言，当然也知道C语言不属于这一类。别不信，随便上网搜一搜你就会发现，这方面的文章还挺多。在C语言中你需要结构体,typedef,没准还会需要一些函数指针。举个例子：

typedef struct node *Bird;
struct node {
	int fly_able;
	char wing_color[10];
	int feature[3];
};

代码很明确的指出了这是一个关于鸟类的结构体，结构体里定义了一些变量包括鸟类能否飞翔，翅膀颜色，各类特征等等。建立完这个结构体后，我们可以用它定义其他变量。你可以如此定义：

Bird chicken;
if (NULL == (chicken = (Bird)malloc(struct node))) {
	printf("malloc failed!\n");
	exit(1);
}
chicken->fly_able = 0;
strcpy(chicken->wing_color,  "yellow");

分配完内存,我们就可以给结构体中的各个变量赋值了。怎么样，有点那么个意思吧。

讲了这么多题外话，我们现在进入正题，讲讲单向链表吧。单向链表顾名思义是单向的，Bingo！也存在双向链表。单向链表只能单向遍历，而双向链表就是双向的。与上面所说一样，我们也要定义一个结构体，至于你是想定义成什么就看你的需要了，我这里就定义成一个人吧：

typedef struct node *Human;
struct node {
	int sex;
	char name[10];
	double height;
	Human next_human;
	...
};

我们定义单向链表一定要定义一个用来标示下个节点的Human next_human，要不怎么找到下一个节点呢。okey，什么都有个开始，链表也是一样的，我们需要定义一个头节点，无论是扩充还是删除都是必不可少的。

Human head_human;
if (NULL == (head_human = (Human)malloc(sizeof(struct node))) {
	printf("malloc failed!\n");
	exit(1);
}
head_human-> next_human = NULL;

这个头节点的下一个节点要指向空指针，毕竟我们还没有定义下一个指针。

有了头节点，我们就要考虑如何扩充链表了，我们可以在链表的任意位置（后）插入节点。

void insert(Human target_human) 
{
	Human new_human; 
	if (NULL == (new_human = (Human)malloc(sizeof(struct node))) {
		printf("malloc failed!\n");
		exit(1);
	}
											   
	new_human->next_human = target_human->next_human;
	target_human->next_human = new_human;    
}

这里你可能会有疑问，我们如何找到这个目标人物，并在其后插入新节点呢？我们可以遍历整个链表，找到我们需要的节点。

void find(Human head_human)
{
	Human tep;
	tep = head_human;

	while (tep->next_human != NULL) {
		tep = tep->next_human;
		if (tep->height = 2.26)
			break;
	}
}

我们先建立一个临时用来指向头节点的指针（该指针无需分配空间），谁都不想头指针最后不知道跑到哪里去了。while先测试该指针下一节点是不是NULL，如果是,对于头节点，它一定是一个光杆司令（仅有一个头节点），对于非头节点，它表示到达链表结尾。不对啊，它的下一节点是结尾，当前节点不是结尾啊，这个节点也需要处理的？仔细再看看代码，其实我们已经处理过这个节点了。也许do-while循环能看的更加清晰（不过对于光杆司令的头节点，这可不好办啊）。接下来遍历开始，当我们找到一个身高是2.26（姚明？）的人时，跳出循环，这时tep是指向“姚明”的节点了。至于查找规则，你完全可以自己设定，没准你要找“mike”或者什么别的人，这里只是一个简单的例子。

可以新增就可以减少，删除节点也很重要。我们发现删除节点就不好办了，每次我们只能知道当前节点和下一节点（单向链表么），要想删除某一节点需要知道前一节点。所以，我们需要一个函数找到前一个节点。

void delete(Human head_human, Human target_human)
{
	Human pre_human, next_human;
	next_human = target_human->next_human;
	pre_human = pre(head_human, target_human);
	
	if (pre_human != NULL) {
		pre_human->next_human = next_human;
		free(target_human);//删除了还留着干嘛，记得一定要释放掉所占内存
	} else { 
		printf("shit, no this man\n");
	}
}

找到目标节点的上一节点。

Human pre(Human head_human, Human target_human)
{
	Human tep;
	tep = head_human;
	
	while (tep->next_human != NULL) {
		if (tep->next_human == target_human) 
			return tep; 
			tep = tep->next_human;
		} 
	return NULL;
}

当然还可以删除整个链表，打印整个链表，其实会了遍历链表，这都是水到渠成的事情，大家自己练习吧。

说了半天，不知道你喜欢上链表没有，难道你没看到链表这么多的优点么？我们不需要预先知道数据的多少，来着不拒，大不了生成空间存储就是了。不要了删除就行，需要了插入就行，多么方便。更多好处，请查看维基百科。

亲，别忘了最后释放内存空间啊！