用游戏串起程序员的基本功（五）
2004-03-23■作者：潇潇■出处： YESKY
游戏的细节部分快谈完了，我们的这篇文章也即将结束。但这部分所谈到得内容依然是数据结构方面的很主要的一部分内容。闲话少叙，回到我们的教程中。
细心的读者可能发现了，这里我的所有例子都是基于数组这种结构来谈的。所以我们先来看一看数组的一些特点。从前面的例子中,我们可以看到,数组是一种不仅在存储地址上连续而且其中前后数据在逻辑上也连续的存储数据的结构.它的优点是,读取和修改其中的每一个数值都很方便.只要直接找到它的索引值就可以读取和修改它的数值.即使要想读取或修改数组中所有的数值,我们也只需要一个从头到尾的循环.但是对于数组的插入,删除,和排序却 是一件很繁琐的事,比如我们在数组中间插入一个数值,就要将它所在的位置之后的所有数值后移一位,如果其后的数值很多,效率是极低的.示例如下:
2
3
4
5
6
7
8
9
上面是待插入数值的数组.如果想在5的后面插入一个1,可以想到首现要找到5所在的位置,然后,从最后的9开始,向后移动一个位置,直到空出5后面的位置,最后将1插入其中.在这里我们只需移动四个数,但当数值越多,那么移动的数值也就会越多.
除此之外,数组还有一个不足之处.那就是我们在不知到数据多少时,为存储下所有数据,必须建立很多空的数组,势必造成存储空间的浪费.
这里我们在介绍一种数据结构——链表.我们先来看个例子。
1
2
3
4
5
上面是存在内存中的数据，在存储位置上，它们都是不连续的，但我们可以不考虑他们的实际位置，而在逻辑上让他们形成一种前后相联的关系。怎么做呢？
1
正如左图所示：我们只要加一个“链”就可以将内存中不连续的单元连接起来。用c语言我们可以这样做：
Struct jiegouming //结构名称
{
int shu； //用来存储数据
Struct list *Next； //用来连接下一个
}
typedef struct jiegouming node；
typedef Node *link；
这样我们就可以用Next这样的一个指针，将多个这样的结构联系起来了。而且还可以在需要的时候 ，动态的建立，不需要的时候，再释放掉，从而节省了，内存空间。
2
3
4
我们来看一看链表的建立和释放。下面是源程序：
link creatlist（link head）//建立一个有10个节点的链表,并初始化为0
{
link point;//声明两个接点
link new;
int num=10;//计数值设为10
head = （link）malloc （sizeof（node））；
if（head==NULL）
printf（” 内存建立失败”）;
else
{
head->next=NULL;
printf(“建立成功”)
}
point = head;//将point 设为首节点
while(num>0)
{
new = (link) malloc (sizeof(node));
if(new==NULL)
printf(“内存建立失败”);
else
new->shu=o;//将新建的节点中的数值设为0
new->next=NULL;// 将新建的节点中的下一个节点设为NULL
point->next=new;//将新建的节点连接到前一个节点上
point=new;// 将新建节点设为当前节点
num--; //计数值减一
}//end while
}//end
void freelist(link head)//释放链表
{
link point; //声明一个节点
while(head !=NULL)//当节点为空,说明已到链表最后
{
point=head;//保存节点头
head=hesd->next; //向后移动倒下一个节点
free(point); //删除头一个节点
}//end while
}//end
对于链表如果不能实现查询,插入,删除等功能,那么它也就没有价值了,所以我们再来看看在链表中怎样实现这些功能.
先来看看链表的查询.因为链表在逻辑上也是有序排列的,所以,要找一个数值,我们同样可以采用线性查找法挨个往下查找下去,直到找到所要查找的数值或者查找结束.
下面是例程:
int searchlist(int key,link head) //在链表head中查找key值
{
link point;//声明一个节点,指示当前位置
int num=1;//记录节点所在位置的数值
point = head; // 指向头一个节点
while(point !=NULL)
{
if(point->shu==key) //如果节点中的数值和要查找的数值相等
return num;// 返回这个数值在链表中的位置
point = point->next; //如果节点中的数值和要查找的数值不相等,节点后移
num++;//计数值加一
}//end while
}//end
对于链表的插入方法,很灵活,不用象数组一样插入后,还要向后移动其后面的数值.下面是一个示例图:
1
要插入的新节点
5
2
3
左图中黑线表示原来的链表结构,红色表示插入心节点后得到的修改后的样子.
可见,链表的插入,只要修改节点的指向就可以了.
下面是源代码 :
4
Link insertlist(link head,link new,int key)
//在链表head中插入数值为key的节点new
{
link point;// 声明一个节点,来指示当前节点
point = head; //当前节点指向头节点
while(1)
{
if(point==NULL)//如果链表head中只有一个节点
{ //插入到首节点的前面
new->next=head;
head=new;//新节点作为首节点
break;
} //end if
if(point->shu==key)//如果在链表head中找到key值
{ //插入到这个数值的后面
new->next=point->next;
point->next=new;
break;
} //end if
point=point->next;//当前节点后移
}//end while
return head;
}//end
最后是怎样删除一个节点.方法和插入类似.请看示例图:
1
2
在左图中黑线表示的是在删除第二个节点前的状态.红线表示删除后的状态.
可见,对于在链表中删除一个节点同样是只需要修改一下节点的指向.
下面是代码:
3
4
Link deletelist(link head,int key)
/在链表head中删除数值key
{
link point;//指示当前节点
link back;//指示后一个节点
point =head;//将头节点设为当前节点
while(1)
{
if(point->next==NULL)//如果,没有节点
{
printf(“没有节点可供删除”);
break;
}
if(head->shu ==key)//如果找到数值key所在的节点
{
head=point->next;//将当前节点的下一个
free(point);//释放节点
break;
}
back=point;//保存当前节点
point=point->next;//当前节点后移
if(point->shu==key)// 如果找到数值key所在的节点
{
back->next=point->next;
//将当前节点所连接的节点连接到当前节点的前一个节点上
free(point);//释放当前节点
break;
}//end if
}end while
return head;
}//end
好了,就到这吧,毕竟只是一篇基础教程.所以我们不打算讲的太深.把它当作一篇入门的教程吧,有兴趣的读者可以学习一下相关的课程.一定会又所收获的.
