用二级指针操作链表

前天给公司的游戏服务器加了命令行的命令补齐功能,好好的研究了下命令的解析,正好手上有ID doom3的代码,所以对比下两边的代码。公司的是用数组存结构体来保存命令的信息。Doom3是用链表,链表的检索性能不如数组,但是灵活可以扩展,而且稍微有点经验的c程序员都喜欢用二级指针来操作链表。来让我们看看id的实现。
链表元素的定义

typedef struct commandDef_s {
	struct commandDef_s *	next;
	char *					name;
	cmdFunction_t			function;
	argCompletion_t			argCompletion;
	int						flags;
	char *					description;
} commandDef_t;

将next指针放在元素开头,这样就可以用二级指针,对链表进行检索。

commandDef_t *commands = (commandDef_t *) 表头元素;
commandDef_t *cmd, **prev;

	for ( prev = &commands; *prev; prev = &cmd->next ) {
		cmd = *prev;
		if ( 找到元素 ) {
			// 将找到的元素放到表头,提高下次查找的效率
			*prev = cmd->next;
			cmd->next = commands;
			commands = cmd;

		}
	}

commands是指向表头的指针,我们看到将prev定义成二级指针,并将next元素放在链表元素,*prev指向当前元素,prev则指向当前元素之前的一个元素。(**prev).next就是下个元素的指针了,非常灵活。
这样一个prev指针通吃前后三元素,好玩吧,据说如果你还用一级指针操作链表,会被大神鄙视的哦!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.