Chinaunix首页 | 论坛 | 博客
  • 博客访问: 601753
  • 博文数量: 165
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1554
  • 用 户 组: 普通用户
  • 注册时间: 2013-10-23 22:57
个人简介

我本仁慈,奈何苍天不许

文章分类

全部博文(165)

文章存档

2018年(1)

2016年(33)

2015年(5)

2014年(34)

2013年(92)

分类: LINUX

2013-10-23 23:15:39

队列是一种特殊的线性表,它只允许在表头进行删除操作,而在表尾进行插入操作,是一种先进先出的数据结构。

队列可以采用数组存储,也可以采用链式存储。关于链式存储常见的又有两种:带头结点和不带头结点。我们建议采用带头结点的实现方式,因为,这样可以大大简化对队列的处理。

下面以入队操作为例,对本文观点进行了进一步的阐述。假设基本结构的定义为:

typedef int datatype;
        typedef struct node
        {
                datatype data;
                struct node* next;
        }listnode, *linknode;
        typedef struct
        {
                linknode front;
                linknode rear;
        }linkqueue;

带头结点的链队入队实现:

 void enqueue(linkqueue* q, datatype x){
                linknode p = (linknode)malloc(sizeof(listnode));
                p->data = x;
                p->next = NULL;
                q->rear->next = p;
                q->rear = p;
        }

不带头结点的链队入队实现:

void enqueue(linkqueue* q, datatype x){
                linknode p = (linknode)malloc(sizeof(listnode));
                p->data = x;
                p->next = NULL;
                if(q->front == NULL){
                        q->front = p;
                        q->rear = p;
                        return;
                }
                q->rear->next = p;
                q->rear = p;
        }

比较上面两段程序,带头结点的链队的入队操作,只要把新生成的结点加到尾结点后即可。而不带头结点的操作则还要注意到边界操作,假如是第一次入队,需修改队头指针。同样的道理,对于出队操作,假如是最后一个结点出队,需要注意修改队尾指针。由此,我们建议链式队列最好采用带头结点的实现方式。

 

阅读(1014) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~