[转载]双向、循环链表
C语言的基础知道都忘了，
这两天在看贪吃蛇的Code时，算法中用到双向链表的知识，我晕了好几天，今天到网上搜了一下，巩固一下吧
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
在双向链表的结点中有两个指针域，其一指向直接后继，另一个指向直接前趋
1. 线性表的双向链表存储结构
typedef struct DulNode{
struct DulNode *
struct DulNode *
}DulNode,*DuLinkL
对指向双向链表任一结点的指针d ，有下面的关系：
d-&next-&prior=d-&prior-&next=d;
即：当前结点后继的前趋是自身，当前结点前趋的后继也是自身。
2.双向链表的插入操作：(很遗憾，图片传不上来),不过记住四步：
基本原理：双链表就好像是手拉手站成一排的人，每个人的右手(next)拉着下一个人，左手(prior)拉着前一个人，每两个人之间有两只手互联，插入操作实际是队伍中增加人员，他需要拉上左右两边人的手，即共三个人要发生关系，由于每个人之间有两只手互联，所以要发生四次操作：如已知结点
p、q需要插入s(称为原型吧)
--------------------------------------
---------------------------------------
现在假设需要插入结点s，则需要进行以下4次操作：
(1)(2)完成q 与s的握手
(1)q-&next =
(2)s-&prior=q;
--------------------------------------
(3)(4)完成s 与q 的握手
(3)s-&next =
(4)p-&prior =
q-&next s-&next
s-&prior p-&prior
对于上面的Sample，只已知结点p，而不致结点q，但是通过双向链表的性质我们可以在初始时(插入前)得到以下关系：p-&prior
所以对于以上的4次操作我们可以作等效操作，即将q换为p-&prior,则以上4次操作为：
p-&prior-&next =
s-&prior = p-&
p-&prior =
&3. 双向链表的呼唤问题
由于不知道q 结点，因此用p-&prior
来代替，所以p-&prior 的值应当在已经不再使用q 结点的时候再改变，由原型：
(1)q-&next =
(2)s-&prior =
(3)s-&next =
(4)p-&prior =
4.删除操作
基本原理：删除操作就好像某个人退出队伍，但退出前他需要让他两边的人把手拉上，以保持队伍的连续性，如已知q、s、p，需要删除s
，由于只需要两个人发生关系，所以需要进行以下两次操作：
(1)q-&next=p;
(2)p-&prior=q;
s-&prior p-&prior
对于本例，是上面原型的变种，只已知s ，但由双向链表的性质，我们可以推出以下关系：
因此可做以下替换：
(1)s-&prior-&next =
(2)s-&next-&prior =
由于s ,以及prior和next的值在两次操作中并没有被改变,因此(1)(2)的顺序没有关系.
三、一些结论
&（1）对于双向链表的插入，只需知道插入位置的一个节点即可完成插入；
&&（2）对于双向链表的删除，只需知道删除节点即可完成删除。
因此对于双向链表的插入和删除在该情况下，时间度为O(1)。
循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链
循环链表的运算与单链表的运算基本一致，所不同的有以下几点：
1。在建立一个循环链表是，必须是其最后一个结点的指针指向表头结点，而不是像单链表那样置为NULL。此种情况还是用于在最后一个结点后插入一个新的结点。
2。在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已经到表尾。而非像单链表那样判断链域值是否是NULL
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。导读：贪吃蛇是一款非常经典的手机游戏，本文将使用MIDP实现这款著名的游戏，//游戏区域宽度//游戏区域高度，贪吃蛇游戏设计与分析，游戏中要随机产生食物，还必须有一个类来判断游戏是否结束了，于是创建一个isGameOver类来判断游戏是否结束了，这个贪吃蛇小游戏就完成了，move(direction);//结束游戏，贪吃蛇是一款非常经典的手机游戏，本文将使用MI
贪吃蛇是一款非常经典的手机游戏，本文将使用MIDP实现这款著名的游戏。 基本概念介绍
节：一条蛇可以看成有许多正方形的“小格子”拼凑成，我把它称作节。节是蛇身上最小的单位。
段：当许多节连成一条直线，我称它为段。上图的贪吃蛇只有一段，如果它拐弯就变成两段。
链表：用来保存每一段的状态，链表的元素单位是段。且链表的最后一个元素表示蛇的头部段。
坐标系：MIDP中的坐标以左上角那点为(0,0)，向右则x递增，向下则y递增。 一条完整的贪吃蛇是由一段一段组成的。链表中保存的第一个元素是蛇的尾巴段，最后一个元素是蛇的头部段。当蛇运动的时候，它头部段增加一节而尾段减少一节。如果它吃到了食物，尾部段就不减少一节。也就是说，蛇是从头部段开始长的。
SnakeCanvas类中有以下代码: int[][] snake = new int[200][2];
int snakeN
private final int DIRECTION_UP = 0;
private final int DIRECTION_DOWN = 1;
private final int DIRECTION_LEFT = 2;
private final int DIRECTION_RIGHT = 3;
先存储贪吃蛇节点坐标,其中第二维下标为0的代表x坐标，第二维下标是1的代表y坐标; int snakeNum 表示已经使用的节点数量.
private final int DIRECTION_UP = 0;
private final int DIRECTION_DOWN = 1;
private final int DIRECTION_LEFT = 2; private final int DIRECTION_RIGHT = 3;
这段代码是设定贪吃蛇的运动方向，0代表向上，1代表向下，2代表向左，3代表向右。
//游戏区域宽度
//游戏区域高度 贪吃蛇游戏设计与分析
private final byte SNAKEWIDTH = 4;
//蛇身单元宽度
boolean isPaused =
//是否处于暂停状态,true代表暂停
boolean isRun =
//是否处于运行状态,true代表运行
private final int SLEEP_TIME = 300;
//时间间隔 接下来就是设定食物的坐标：
int foodX;
// 食物的X坐标
int foodY;
// 食物的Y坐标
boolean b =
// 食物的闪烁控制 再接着就构建一个构造方法来启动线程：
public SnakeCanvas() {
width = this.getWidth();
height = this.getHeight();
new Thread(this).start();
//启动线程
} 然后再初始化开始数据，代码如下：
private void init(){
snakeNum = 7;
//初始化节点数量
for(int i = 0;i < snakeNi++){
//初始化节点数据
snake[i][0] = 100 - SNAKEWIDTH *
snake[i][1] = 40;
direction = DIRECTION_RIGHT;
//初始化移动方向
foodX = 100;
//初始化食物坐标
foodY = 100;
//初始化食物坐标
} 然后创建一个画布类来绘制贪吃蛇和食物：
protected void paint(Graphics g) {
g.setColor(0xffffff);
g.fillRect(0,0,width,height);
g.setColor(0);
for(int i = 0;i < snakeNi++){
//绘制蛇身
g.fillRect(snake[i][0],snake[i][1],SNAKEWIDTH,SNAKEWIDTH);
//绘制食物
g.fillRect(foodX,foodY,SNAKEWIDTH,SNAKEWIDTH);
} 然后创建一个move类来实现贪吃蛇的移动，贪吃蛇吃掉食物后，自身的长度应该增长，所以创建一个eatFood类来实现这个效果，代码如下：
private void eatFood(){
//判别蛇头是否和食物重叠
if(snake[0][0] == foodX && snake[0][1] == foodY){
snakeNum++;
generateFood();
} 游戏中要随机产生食物，并且食物的坐标必须位于屏幕内，且不能和蛇身重合，于是创建一个generateFood 类来实现这个效果，代码如下：
private void generateFood(){
while(true){
foodX = Math.abs(random.nextInt() % (width - SNAKEWIDTH + 1))
/ SNAKEWIDTH * SNAKEWIDTH;
foodY = Math.abs(random.nextInt() % (height - SNAKEWIDTH + 1))
/ SNAKEWIDTH * SNAKEWIDTH;
boolean b =
for(int i = 0;i < snakeNi++){
if(foodX == snake[i][0] && snake[i][1] == foodY){
} 还必须有一个类来判断游戏是否结束了，结束的条件是蛇头超过边界或者是蛇头碰到自身，于是创建一个isGameOver 类来判断游戏是否结束了，代码如下：
private boolean isGameOver(){
//边界判别
if(snake[0][0]
(width - SNAKEWIDTH) ||
snake[0][1]
(height - SNAKEWIDTH)){
//碰到自身
for(int i = 4;i < snakeNi++){
if(snake[0][0] == snake[i][0]
&& snake[0][1] == snake[i][1]){
游戏中，我们需要用键盘上的上下左右方向键来控制贪吃蛇的移动，所以创建一个keyPressed 类来实现这个功能，代码如下：
public void keyPressed(int keyCode){
int action = this.getGameAction(keyCode);
//改变方向
switch(action){
if(direction != DIRECTION_DOWN){
direction = DIRECTION_UP;
case DOWN:
if(direction != DIRECTION_UP){
direction = DIRECTION_DOWN;
case LEFT:
if(direction != DIRECTION_RIGHT){
direction = DIRECTION_LEFT;
case RIGHT:
if(direction != DIRECTION_LEFT){
direction = DIRECTION_RIGHT;
case FIRE:
//暂停和继续
isPaused = !isP
} 最后再创建一个线程方法，这个贪吃蛇小游戏就完成了，代码如下：
public void run(){
while (isRun) {
//开始时间
long start = System.currentTimeMillis();
if(!isPaused){
eatFood();
move(direction);
//结束游戏
if(isGameOver()){
//控制闪烁
//重新绘制
repaint();
long end = System.currentTimeMillis();
if(end - start < SLEEP_TIME){
Thread.sleep(SLEEP_TIME - (end - start));
}catch(Exception e){}
} } 包含总结汇报、旅游景点、资格考试、文档下载、办公文档、IT计算机、出国留学、计划方案、党团工作以及贪吃蛇游戏设计与分析等内容。
相关内容搜索建立二叉树二叉链表存储结构实现有关操作_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
建立二叉树二叉链表存储结构实现有关操作
&&建立二叉树二叉链表存储结构实现有关操作
建立二叉树的二叉链表存储结构实现以下操作(选择其中的两个做)
(1)输出二叉树
(2)先序遍历二叉树
(3) 中序遍历二叉树
(4)后序遍历二叉树
(5)层次遍历二叉树
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩1页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢刚写了个贪吃蛇，， - LabVIEW论坛 -
中国电子技术论坛 -
最好最受欢迎电子论坛!
后使用快捷导航没有帐号？
刚写了个贪吃蛇，，
16:07:33　　
本帖最后由 wghou 于
09:58 编辑
第一次写这种程序，代码不是很条理，，，
自己用数组做的链表，用来存储蛇身。。
又用队列写了一遍，见附件2
本帖子中包含更多资源
才可以下载或查看，没有帐号？
资源分享达人,加分鼓励!
本帖被以下淘专辑推荐:
& |主题: 70, 订阅: 31
18:13:26　　
刚写了个贪吃蛇，，
22:50:22　　
看看！！！！！！！！！！！！！！！！！！！！
12:38:57　　
顶一个~{:12:}
高级工程师
18:22:15　　
10:10:09　　
不知道是什么版本的
21:36:36　　
good&&already&&download !
22:03:07　　
这也可以……omg太厉害了
10:44:11　　
怎么能用键盘控制呢~
10:49:34　　
怎么能用键盘控制呢~
应该可以把里面的条件分支改成事件结构
08:19:15　　
学习一下队列和上下键
17:02:28　　
17:04:24　　
00:11:02　　
09:06:17　　
22:18:04　　
看看怎么样
12:15:54　　
09:39:40　　
请问，大神，哪个部分是代表蛇吃食物增长体长的程序，急急急
Powered by
供应链服务
版权所有 (C) 深圳华强聚丰电子科技有限公司Linux 环境下C语言编译实现贪吃蛇游戏_Linux编程_Linux公社-Linux系统门户网站
你好，游客
Linux 环境下C语言编译实现贪吃蛇游戏
来源：Linux社区&
作者：fbi987996
^_^一个小游戏，贪吃蛇，C语言实现 嘎嘎 在Linux 环境下 编译通过。
//mysnake1.0.c//编译命令：cc mysnake1.0.c -lcurses -o mysnake1.0//用方向键控制蛇的方向#include &stdio.h&#include &stdlib.h&#include &curses.h&#include &signal.h&#include &sys/time.h&#define NUM 60struct direct&&&&&&&&&&&&&&& //用来表示方向的{&&& int &&& int };typedef struct node&&&&&&&&&&& //链表的结点{&&& int &&& int &&& struct node *&&& struct node *}void initGame();&&&&&&&&&&& //初始化游戏int setTicker(int);&&&&&&&&&&& //设置计时器void show();&&&&&&&&&&&&&&& //显示整个画面void showInformation();&&&&&&& //显示游戏信息（前两行）void showSnake();&&&&&&&&&&& //显示蛇的身体void getOrder();&&&&&&&&&&& //从键盘中获取命令void over(int i);&&&&&&&&&&& //完成游戏结束后的提示信息void creatLink();&&&&&&&&&&&&&&& //（带头尾结点）双向链表以及它的操作void insertNode(int x, int y);&&&void deleteNode();void deleteLink();int &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& //输入的命令int hour, minute,&&&&&&&&&&& //时分秒int length, tTime,&&&&&&&&&&& //（蛇的）长度，计时器，（游戏）等级struct direct dir,&&&&&&&&&&& //蛇的前进方向，食物的位置node *head, *&&&&&&&&&&&&&&&&&&& //链表的头尾结点int main(){&&& initscr();&&& initGame();&&& signal(SIGALRM, show);&&& getOrder();&&& endwin();&&& return <SPAN style="COLOR: #;}void initGame(){&&& cbreak();&&&&&&&&&&&&&&&&&&& //把终端的CBREAK模式打开&&& noecho();&&&&&&&&&&&&&&&&&&& //关闭回显&&& curs_set(<SPAN style="COLOR: #);&&&&&&&&&&&&&&& //把光标置为不可见&&& keypad(stdscr, true);&&&&&&& //使用用户终端的键盘上的小键盘&&& srand(time(<SPAN style="COLOR: #));&&&&&&&&&&&&&&& //设置随机数种子&&& //初始化各项数据&&& hour = minute = second = tTime = <SPAN style="COLOR: #;&&& length = <SPAN style="COLOR: #;&&& dir.cx = <SPAN style="COLOR: #;&&& dir.cy = <SPAN style="COLOR: #;&&& ch = 'A';&&& food.cx = rand() % COLS;&&& food.cy = rand() % (LINES-<SPAN style="COLOR: #) + <SPAN style="COLOR: #;&&& creatLink();&&& setTicker(<SPAN style="COLOR: #);}//设置计时器（这个函数是书本上的例子，有改动）int setTicker(int n_msecs){&&& struct itimerval new_&&& long&&& n_sec, n_&&& n_sec = n_msecs / <SPAN style="COLOR: #00 ;&&& n_usecs = ( n_msecs % <SPAN style="COLOR: #00 ) * <SPAN style="COLOR: #00L ;&&& new_timeset.it_interval.tv_sec& = n_&&&&&&& &&& new_timeset.it_interval.tv_usec = n_&&&&& &&& n_msecs = <SPAN style="COLOR: #;&&& n_sec = n_msecs / <SPAN style="COLOR: #00 ;&&& n_usecs = ( n_msecs % <SPAN style="COLOR: #00 ) * <SPAN style="COLOR: #00L ;&&& new_timeset.it_value.tv_sec&&&& = n_sec& ;&&&&& &&& new_timeset.it_value.tv_usec&&& = n_&&&& &&& return setitimer(ITIMER_REAL, &new_timeset, NULL);}void showInformation(){&&& tTime++;&&& if(tTime &= <SPAN style="COLOR: #00000)&&&&&&&&&&&&&&& //&&&&&&& tTime = <SPAN style="COLOR: #;&&& if(<SPAN style="COLOR: # != tTime % <SPAN style="COLOR: #)&&&&&&& return;&&& move(<SPAN style="COLOR: #, <SPAN style="COLOR: #);&&&&&& //显示时间&&& printw("time: %d:%d:%d %c", hour, minute, second);&&& second++;&&& if(second & NUM)&&& {&&&&&&& second = <SPAN style="COLOR: #;&&&&&&& minute++;&&& }&&& if(minute & NUM)&&& {&&&&&&& minute = <SPAN style="COLOR: #;&&&&&&& hour++;&&& }&&& //显示长度，等级&&& move(<SPAN style="COLOR: #, <SPAN style="COLOR: #);&&& int i;&&& for(i=<SPAN style="COLOR: #;i&COLS;i++)&&&&&&& addstr("-");&&& move(<SPAN style="COLOR: #, COLS/<SPAN style="COLOR: #-<SPAN style="COLOR: #);&&& printw("length: %d", length);&&& move(<SPAN style="COLOR: #, COLS-<SPAN style="COLOR: #);&&& level = length / <SPAN style="COLOR: # + <SPAN style="COLOR: #;&&& printw("level: %d", level);}//蛇的表示是用一个带头尾结点的双向链表来表示的，//蛇的每一次前进，都是在链表的头部增加一个节点，在尾部删除一个节点//如果蛇吃了一个食物，那就不用删除节点了void showSnake(){&&& if(<SPAN style="COLOR: # != tTime % (<SPAN style="COLOR: #-level))&&&&&&& return;&&& //判断蛇的长度有没有改变&&& bool lenChange = false;&&& //显示食物&&& move(food.cy, food.cx);&&& printw("@");&&& //如果蛇碰到墙，则游戏结束&&& if((COLS-<SPAN style="COLOR: #==head-&next-&cx && <SPAN style="COLOR: #==dir.cx)&&&&&&& || (<SPAN style="COLOR: #==head-&next-&cx && -<SPAN style="COLOR: #==dir.cx)&&&&&&& || (LINES-<SPAN style="COLOR: #==head-&next-&cy && <SPAN style="COLOR: #==dir.cy)&&&&&&& || (<SPAN style="COLOR: #==head-&next-&cy && -<SPAN style="COLOR: #==dir.cy))&&& {&&&&&&& over(<SPAN style="COLOR: #);&&&&&&& return;&&& }&&& //如果蛇头砬到自己的身体，则游戏结束&&& if('*' == mvinch(head-&next-&cy+dir.cy, head-&next-&cx+dir.cx) )&&& {&&&&&&& over(<SPAN style="COLOR: #);&&&&&&& return;&&& }&&& insertNode(head-&next-&cx+dir.cx, head-&next-&cy+dir.cy);&&& //蛇吃了一个“食物”&&& if(head-&next-&cx==food.cx && head-&next-&cy==food.cy)&&& {&&&&&&& lenChange = true;&&&&&&& length++;&&&&&&& //恭喜你，通关了&&&&&&& if(length &= <SPAN style="COLOR: #)&&&&&&& {&&&&&&&&&&& over(<SPAN style="COLOR: #);&&&&&&&&&&& return;&&&&&&& }&&&&&&& //重新设置食物的位置&&&&&&& food.cx = rand() % COLS;&&&&&&& food.cy = rand() % (LINES-<SPAN style="COLOR: #) + <SPAN style="COLOR: #;&&& }&&& if(!lenChange)&&& {&&&&&&& move(tail-&back-&cy, tail-&back-&cx);&&&&&&& printw(" ");&&&&&&& deleteNode();&&& }&&& move(head-&next-&cy, head-&next-&cx);&&& printw("*");}void show(){&&& signal(SIGALRM, show);&&&&&&& //设置中断信号&&& showInformation();&&& showSnake();&&& refresh();&&&&&&&&&&&&&&&&&&& //刷新真实屏幕}void getOrder(){&&& //建立一个死循环，来读取来自键盘的命令&&& while(<SPAN style="COLOR: #)&&& {&&&&&&& ch = getch();&&&&&&& if(KEY_LEFT == ch)&&&&&&& {&&&&&&&&&&& dir.cx = -<SPAN style="COLOR: #;&&&&&&&&&&& dir.cy = <SPAN style="COLOR: #;&&&&&&& }&&&&&&& else if(KEY_UP == ch)&&&&&&& {&&&&&&&&&&& dir.cx = <SPAN style="COLOR: #;&&&&&&&&&&& dir.cy = -<SPAN style="COLOR: #;&&&&&&& }&&&&&&& else if(KEY_RIGHT == ch)&&&&&&& {&&&&&&&&&&& dir.cx = <SPAN style="COLOR: #;&&&&&&&&&&& dir.cy = <SPAN style="COLOR: #;&&&&&&& }&&&&&&& else if(KEY_DOWN == ch)&&&&&&& {&&&&&&&&&&& dir.cx = <SPAN style="COLOR: #;&&&&&&&&&&& dir.cy = <SPAN style="COLOR: #;&&&&&&& }&&&&&&& setTicker(<SPAN style="COLOR: #);&&& }}void over(int i){&&& //显示结束原因&&& move(<SPAN style="COLOR: #, <SPAN style="COLOR: #);&&& int j;&&& for(j=<SPAN style="COLOR: #;j&COLS;j++)&&&&&&& addstr(" ");&&& move(<SPAN style="COLOR: #, <SPAN style="COLOR: #);&&& if(<SPAN style="COLOR: # == i)&&&&&&& addstr("Crash the wall. Game over");&&& else if(<SPAN style="COLOR: # == i)&&&&&&& addstr("Crash itself. Game over");&&& else if(<SPAN style="COLOR: # == i)&&&&&&& addstr("Mission Complete");&&& setTicker(<SPAN style="COLOR: #);&&&&&&&&&&&&&&& //关闭计时器&&& deleteLink();&&&&&&&&&&&&&&& //释放链表的空间}//创建一个双向链表void creatLink(){&&& node *temp = (node *)malloc( sizeof(node) );&&& head = (node *)malloc( sizeof(node) );&&& tail = (node *)malloc( sizeof(node) );&&& temp-&cx = <SPAN style="COLOR: #;&&& temp-&cy = <SPAN style="COLOR: #;&&& head-&back = tail-&next = NULL;&&& head-&next = &&& temp-&next = &&& tail-&back = &&& temp-&back = }//在链表的头部（非头结点）插入一个结点void insertNode(int x, int y){&&& node *temp = (node *)malloc( sizeof(node) );&&& temp-&cx = x;&&& temp-&cy = y;&&& temp-&next = head-&&&& head-&next = &&& temp-&back = &&& temp-&next-&back = }//删除链表的（非尾结点的）最后一个结点void deleteNode(){&&& node *temp = tail-&&&& node *bTemp = temp-&&&& bTemp-&next = &&& tail-&back = bT&&& temp-&next = temp-&back = NULL;&&& free(temp);&&& temp = NULL;}//删除整个链表void deleteLink(){&&& while(head-&next != tail)&&&&&&& deleteNode();&&& head-&next = tail-&back = NULL;&&& free(head);&&& free(tail);}
相关资讯 & & &
& (08月22日)
& (05月08日)
& (06月29日)
& (03月05日)
　　　同意评论声明
　　　发表
尊重网上道德，遵守中华人民共和国的各项有关法律法规
承担一切因您的行为而直接或间接导致的民事或刑事法律责任
本站管理人员有权保留或删除其管辖留言中的任意内容
本站有权在网站内转载或引用您的评论
参与本评论即表明您已经阅读并接受上述条款
匿名 发表于 按键获取这样比较合理一点，用户按下与运行方向相反的按键不应该认为游戏失败void getOrder()if(KEY_LEFT == ch&&dir.cx!= 1)else if(KEY_UP == ch&&dir.cy!= 1)else if(KEY_RIGHT == ch&&dir.cx!= -1)else if(KEY_DOWN == ch&&dir.cy!= -1)评论篇幅先，只贴了要改的地方
(0) 杨建军 发表于 多谢分享
(0) 匿名 发表于 好多错
(1) 匿名 发表于 错误真的很多
(1) sdsfdsf 发表于 怎么这么多错