首页 > 代码库 > 20140503
20140503
1、队列(建议采用带头结点的链式队列)
- 何时为空?答:当队列头指针等于尾指针时,队列为空。(对一般队列而言,循环队列除外)
//不带头结点的链式队列
//不带头结点的链式队列 #include <iostream> #include <stdlib.h> #include <stdio.h> using namespace std; (出队操作) node1-->node2 --> node3 --> ....-->noden(入队操作) // 1 1 // first rear typedef struct Node { int data; struct Node *next; }node; typedef struct Queue //notice :队列的数据结构只是包括两个节点指针(头和尾); { node* first; node* rear; }queue; //队列的插入操作。注意:队列是从rear部插入 queue* insert(queue* My_queue,int x) { node* s; s = (node*)malloc(sizeof(node)); s->data =http://www.mamicode.com/ x; s->next = NULL; //分为队列为空与队列非空两种。 if(NULL == My_queue->rear) { My_queue->first = s; My_queue->rear = s; } else { My_queue->rear->next = s; My_queue->rear = s; } return My_queue; } //队列的删除操作。注意:删除是在first部的操作。 queue* del(queue* My_queue) { node* p; int x; //判断队列是否为空 if(My_queue->first == NULL) { printf("Noting to delete!!!WRONG\n"); } else { x = My_queue->first->data; p = My_queue->first; //判断队列是否删除后为空。(易忽略) if(My_queue->first == My_queue->rear) { My_queue->first = NULL; My_queue->rear = NULL; free(p); } else { My_queue->first = My_queue->first->next; free(p); } return My_queue; } }
2、带头结点队列和不带头结点队列区别
http://www.eefocus.com/ayayayaya/blog/10-06/191475_b58e3.html
队列是一种特殊的线性表,它只允许在表头进行删除操作,而在表尾进行插入操作,是一种先进先出的数据结构。
队列可以采用数组存储,也可以采用链式存储。关于链式存储常见的又有两种:带头结点和不带头结点。我们建议采用带头结点的实现方式,因为,这样可以大大简化对队列的处理。
下面以入队操作为例,对本文观点进行了进一步的阐述。假设基本结构的定义为:
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 =http://www.mamicode.com/ 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 =http://www.mamicode.com/ x; p->next = NULL; if(q->front == NULL) { q->front = p; q->rear = p; return; } q->rear->next = p; q->rear = p; }
比较上面两段程序,带头结点的链队的入队操作,只要把新生成的结点加到尾结点后即可。而不带头结点的操作则还要注意到边界操作,假如是第一次入队,需修改队头指针。同样的道理,对于出队操作,假如是最后一个结点出队,需要注意修改队尾指针。由此,我们建议链式队列最好采用带头结点的实现方式
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。