数据结构代码实现之队列的链表实现(C/C++)

上班闲着无聊,一直想着要开始写博客,但又不知道写什么。最近又回顾了下数据结构的知识,那就从数据结构开始吧。

前言

关于C语言结构体的知识以及队列的特性请读者自行了解,此处不做过多解释,嘻嘻。

同时此篇文章仅仅是关于队列的链表实现。

第一步:结构体编写

我们首先分析一下队列的特征:先进先出,队尾插入,队头删除,暂时想到的就这么多。

首先,对于链表的节点结构体的内容,我们首先想到的是它有一个值,还有一个指向下

一个节点的指针(链表相关知识请读者自行了解),那么它的结构体可实现如下:

 typedef struct Qnode{
int data;
struct Qnode *next;
};

映射到图形,其是这样的结构:

数据结构代码实现之队列的链表实现(C/C++)

接下来,要让这种节点实现队列的特性,我们可以再建立一个结构体,该结构体有一个指向队头节点的指针和一个指向队尾节点的指针,那么它的实现如下:

 typedef struct LQueue{
Qnode *front;
Qnode *rear;
};

其中,front指针指向队头,rear指针指向队尾(注意,该指针是指向Qnode类型的指针)

映射到图形,其是这样的结构:

数据结构代码实现之队列的链表实现(C/C++)

好了,结构体编写工作到这里就完成了,下面开始下一步工作。

第二步,队列的方法分析及实现

一个队列有哪些方法呢,根据前面提到的特性,首先要有插入和删除的方法,我们可以定义插入操作为入队(书上也是这么说的),删除操作为出队,这两个操作应该是队列里最基本的。接下来,初始化队列的方法也是尤其必要的。然后,为了测试方便,还可以定义一个获取队列的长度,队列是否为空,获取队头元素值,获取队尾元素值以及打印队列所有节点数据的方法。下面是对这些方法的实现。

初始化方法:void initQueue(LQueue *q);

方法描述:将创建的队列结构(通过参数传入该方法)的队头和队尾指针都指向一个动态生成的Qnode节点,代码如下:

 void initQueue(LQueue *q){
q->front = q->rear = (Qnode *)malloc(sizeof(Qnode));
q->front->next = NULL;
}

当创建了一个队列变量,然后调用该方法时:

代码:

     LQueue L;
initQueue(&L);

内存空间如图:

数据结构代码实现之队列的链表实现(C/C++)

判断队列是否为空方法:int empty(LQueue *t);

该方法很简单,不做过多描述,代码如下:

int empty(LQueue *t){
return t->front->next == t->rear;
}

入队方法:void push(LQueue *t, int x);

方法描述:通过动态生成一个Qnode节点,然后将x赋值给该节点的data值,再将该节点插入到队列中,代码如下:

 void push(LQueue *t, int x){
Qnode *s = (Qnode *)malloc(sizeof(Qnode));
s->data = x;
s->next = NULL;
t->rear->next = s;
t->rear = s;
}

代码解释:

  第2行:动态生成一个Qnode节点,让指针s指向它;

  第3行:将传入的x值赋值给生成的节点(s所指向)的data值;

  第4行:将s所指节点的next指针置为空;

  第5行:将队列的队尾指针的next指针指向s所指节点;

  第6行:再将队尾指针指向s节点,完成push操作。

不懂的读者希望能自行画图帮助理解,其实图一画出来就一目了然了。

出队方法:void pop(LQueue *t);

方法描述:使用该方法时,首先应判断队列是否为空,为空则退出,不进行出队操作。如果队列不空,则首先定义一个Qnode类型指针q,让q指向队头节点的下一个节点(因为队头节点仅作为队头,不存储值),把队头去掉的话,就是头节点啦。然后让队头节点的next指针指向q所指节点的下一个节点,再释放掉q所指节点(q所指节点即为要出队的节点),代码如下:

 void pop(LQueue *t){
if(empty(t)){
cout << "LQueue is empty,can't pop.\n";
return;
}
Qnode *q = t->front->next;
t->front->next = q->next;
free(q);
}

代码解释:

  第2-5行:判断队列是否为空,若为空则打印提示消息后退出,不进行出队操作;

  第6行:定义一个指针q,使其指向队头节点的next指针所指向的节点;(前面已经解释了,其实就是指向队头节点)

  第7行:让队头节点的next指针指向q的next指针所指向的节点;

  第8行:释放掉q所指的节点的内存,完成出队操作;

还是那句话,画图!一步一步理解。

获取队头节点的值方法:int getFront(LQueue *t);

该方法很简单,不做过多描述,代码如下:

 int getFront(LQueue *t){
return t->front->next->data;
}

获取队尾节点的值方法:int getRear(LQueue *t);

该方法很简单,不做过多描述,代码如下: 

 int getRear(LQueue *t){
return t->rear->data;
}

获取队列长度的方法:int getSize(LQueue *t);

方法描述:使用一个指向头结点的指针,不断遍历,每遍历一次,计数器加1,当该指针指向空时,遍历完成,返回该计数器,代码如下:

 int getSize(LQueue *t){
Qnode *q = t->front->next;
int k = ;
while(q){
k++;
q = q->next;
}
return k;
}

代码解释:

  第2行:定义一个指向队头节点的指针q;

  第3行:定义一个计数器k;

  第4-7行:该代码为,当q不指向NULL时,k+1,然后q指向下一个节点,继续循环判断。

  第8行:当循环结束时,返回该计数器k,即为队列的长度。

打印队列所有值方法:void printQueue(LQueue *t);

方法描述,定义一个指向Qnode类型的指针,进行遍历,每遍历一个节点,打印该节点,然后继续遍历下一节点,代码如下:

 void printQueue(LQueue *t){
Qnode *q = t->front->next;
while(q){
cout << q->data << " ";
q = q->next;
}
cout << "\n";
}

该代码比较简单,不做过多解释。

好了,方法至此已全部完成,接下来,就可以通过main函数进行测试了。

第三步:编写main方法测试运行

完整代码如下,亲测可用,希望各位新入坑的朋友多多敲代码练习哦:

 #include <iostream>
using namespace std; typedef struct Qnode{
int data;
struct Qnode *next;
}; typedef struct LQueue{
Qnode *front;
Qnode *rear;
}; void initQueue(LQueue *q){
q->front = q->rear = (Qnode *)malloc(sizeof(Qnode));
q->front->next = NULL;
} int empty(LQueue *t){
return t->front->next == t->rear;
} void push(LQueue *t, int x){
Qnode *s = (Qnode *)malloc(sizeof(Qnode));
s->data = x;
s->next = NULL;
t->rear->next = s;
t->rear = s;
} void pop(LQueue *t){
if(empty(t)){
cout << "LQueue is empty,can't pop.\n";
return;
}
Qnode *q = t->front->next;
t->front->next = q->next;
free(q);
if(t->rear == NULL)
t->rear = t->front;
} int getFront(LQueue *t){
return t->front->next->data;
} int getRear(LQueue *t){
return t->rear->data;
} int getSize(LQueue *t){
Qnode *q = t->front->next;
int k = ;
while(q){
k++;
q = q->next;
}
return k;
} void printQueue(LQueue *t){
Qnode *q = t->front->next;
while(q){
cout << q->data << " ";
q = q->next;
}
cout << "\n";
}
int main(){
LQueue L;
initQueue(&L);
cout << "Push data to Queue...\n";
push(&L,);
push(&L,);
push(&L,);
push(&L,);
push(&L,);
push(&L,);
push(&L,);
push(&L,);
cout << "Push finished.\n";
cout << "You have pushed such data:";
printQueue(&L);
cout << "Pop data out of Queue...\n";
pop(&L);
cout << "Pop finished.\n";
cout << "Now the Queue have such data:";
printQueue(&L);
cout << "Get Queue's front data:" << getFront(&L) << endl;
cout << "Get Queue's rear data:" << getRear(&L) << endl;
cout << "Get Queue's size:" << getSize(&L) << endl;
pop(&L);
pop(&L);
pop(&L);
cout << "After poped 3 times:";
printQueue(&L);
cout << "Judge the Queue is null or not(0 means not null,others means null):" << empty(&L) << endl;
pop(&L);
pop(&L);
pop(&L);
pop(&L);
cout << "After poped 4 times:";
printQueue(&L);
cout << "Judge the Queue is null or not(0 means not null,others means null):" << empty(&L) << endl; return ;
}

人生中的第一篇博客,写的不好还请海涵~~祝大家生活愉快~~

上一篇:Python中关于split和splitext的差别和运用


下一篇:Python与数据结构[1] -> 栈/Stack[0] -> 链表栈与数组栈的 Python 实现