2018/3/20
数据结构
1.队列
队列是一种特殊的线性表，相较于栈来说，队列是后进先出的，而栈是后进后出的，队列的特点
是多了两个指针，一个是指向队头，一个指向队尾
2.对于队列相关操作的介绍和认识
part1：新建队列
实现队列的新建，只要把队列的队头指针和队尾指针都指向空
part2：判断队列是否为空
判断队头指针和队尾指针是否都为空，如果都为空，说明队列为空
part3：实现取得队首元素
前提条件：队列不为空，然后实现取得队头所在指针的数据域
part4：展示队列
遍历队列，将一个所创建的结点放在队首，遍历取数
part5：插入数字
前提条件：判断队列是否为空，判断队列如果只有一个元素的情况，将某个结点放在队尾处
（尾插法：将尾结点的后继给予，然后移动尾指针）
part6：出队
前提条件：判断队列是否为空·，判断队列只有一个元素的情况，然后将队首指针后移
释放待删除结点
//链队列的简单使用
//使用队首队尾指针的指向来表示队首元素和队尾元素
//头文件
struct Qnode//创建结点
{
int data;//数据域
struct Qnode* next;//指针域
};
struct Queue//创建前后指针
{
struct Qnode*front;
struct Qnode*rear;
};
//1.新建队列
struct Queue *init_queue(struct Queue *q)//使用指针进行操作
{
//q = (struct Queue *)malloc(sizeof(struct Queue));
q->front = NULL;
q->rear = NULL;
return q;
}
//2.判断是否为空，采用返回值1 0来判断
int IsNotEmpty(struct Queue *q)
{
if ((q->front == NULL)&&(q->rear==NULL))
{
return 0;//为空
}
else
{
return 1;
}
}
//3.取得队首元素
struct Queue*catch_Queue(struct Queue *q)
{
if (IsNotEmpty(q)==0)
{
printf("取数错误");
}
else
{
printf("该队首元素为%2d", q->front->data);
}
return q;
}
//展示队列
int disp_queue(struct Queue *q)
{
struct Qnode *p;
p = q->front;//p为队首元素，被队首指针所指
printf("\n[队列头]");
//开始遍历
while (p!= NULL)
{
printf("(%d)-->", p->data);
p = p->next;
}
printf("[队列尾]\n");
return 1;
}
//插入数操作
struct Queue *append_queue(struct Queue *q, int num)
{
struct Qnode* p;//插入结点
p = (struct Qnode*)malloc(sizeof(struct Qnode));
p->data = num;
p->next = NULL;
//判断是否为一个结点的情况
if (q->front==NULL)
{
q->front =p;
q->rear = p;
}
//正常情况
else
{
q->rear->next = p;//将尾指针的后继给了p（尾插法）
q->rear = p;//移动尾指针
}
return q;
}
//出队操作
struct Queue* delete_queue(struct Queue *q)
{
struct Qnode* p;
//判断是否为空
if (IsNotEmpty(q) == 0)
{
printf("队列为空\n");
return q;
}
else
{
p = q->front;//将p放在队首的位置
if (q->front == q->rear)//头指针等于尾指针，说明只有一个结点
{
q->front = NULL;
q->rear = NULL;
}
else
{
q->front = p->next;//将头指针移动位置到队首
}
free(p);
return q;
}
}
//链队列的简单使用
//使用队首队尾指针的指向来表示队首元素和队尾元素
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
struct Qnode//创建结点
{
int data;//数据域
struct Qnode* next;//指针域
};
struct Queue//创建前后指针
{
struct Qnode*front;
struct Qnode*rear;
};
//1.新建队列
struct Queue *init_queue(struct Queue *q)//使用指针进行操作
{
//q = (struct Queue *)malloc(sizeof(struct Queue));
q->front = NULL;
q->rear = NULL;
return q;
}
//2.判断是否为空，采用返回值1 0来判断
int IsNotEmpty(struct Queue *q)
{
if ((q->front == NULL)&&(q->rear==NULL))
{
return 0;//为空
}
else
{
return 1;
}
}
//3.取得队首元素
struct Queue*catch_Queue(struct Queue *q)
{
if (IsNotEmpty(q)==0)
{
printf("取数错误");
}
else
{
printf("该队首元素为%2d", q->front->data);
}
return q;
}
//展示队列
int disp_queue(struct Queue *q)
{
struct Qnode *p;
p = q->front;//p为队首元素，被队首指针所指
printf("\n[队列头]");
//开始遍历
while (p!= NULL)
{
printf("(%d)-->", p->data);
p = p->next;
}
printf("[队列尾]\n");
return 1;
}
//插入数操作
struct Queue *append_queue(struct Queue *q, int num)
{
struct Qnode* p;//插入结点
p = (struct Qnode*)malloc(sizeof(struct Qnode));
p->data = num;
p->next = NULL;
//判断是否为一个结点的情况
if (q->front==NULL)
{
q->front =p;
q->rear = p;
}
//正常情况
else
{
q->rear->next = p;//将尾指针的后继给了p（尾插法）
q->rear = p;//移动尾指针
}
return q;
}
//出队操作
struct Queue* delete_queue(struct Queue *q)
{
struct Qnode* p;
//判断是否为空
if (IsNotEmpty(q) == 0)
{
printf("队列为空\n");
return q;
}
else
{
p = q->front;//将p放在队首的位置
if (q->front == q->rear)//头指针等于尾指针，说明只有一个结点
{
q->front = NULL;
q->rear = NULL;
}
else
{
q->front = p->next;//将头指针移动位置到队首
}
free(p);
return q;
}
}