链队列的基本操作(带头结点,不带头结点)
结构体
typedef struct linknode{int data;struct linknode* next;后继指针
}linknode;
typedef struct {linknode* front, * rear;//队头队尾指针
}linkquene;
初始化队列(带头结点)
int initquene(linkquene* q)//初始化队列
{q->front = q->rear = (linknode*)malloc(sizeof(linknode));q->front->next =NULL;
}
队列判空
int isempty(linkquene* q)//队列判空
{if (q->front == q->rear)return true;else return false;
}
进队操作
int enquene(linkquene* q, int x)//进队操作
{linknode* s = (linknode*)malloc(sizeof(lnode));s->data = x;s->next = NULL;q->rear->next = s;q->rear = s;
}
出队操作
int dequene(linkquene* q, int* x)//出队操作
{if (q->front == q->rear)return false;linknode* p = q->front->next;x = p->data;q->front->next = p->next;if (q->rear == p)q->rear = q->front;free(p);return true;
}
完整的测试代码
#include<stdio.h>
typedef struct linknode{int data;struct linknode* next;
}linknode;
typedef struct {linknode* front, * rear;
}linkquene;
int initquene(linkquene* q)//初始化队列
{q->front = q->rear = (linknode*)malloc(sizeof(linknode));q->front->next =NULL;
}
int isempty(linkquene* q)//队列判空
{if (q->front == q->rear)return true;else return false;
}
int enquene(linkquene* q, int x)//进队操作
{linknode* s = (linknode*)malloc(sizeof(linknode));s->data = x;s->next = NULL;q->rear->next = s;q->rear = s;
}int dequene(linkquene* q, int* x)//出队操作
{if (q->front == q->rear)return false;linknode* p = q->front->next;x = p->data;q->front->next = p->next;if (q->rear == p)q->rear = q->front;free(p);return true;
}
int main()
{linkquene q;initquene(&q);if (!isempty(&q)) //队列判空 printf("队列不为空\n");elseprintf("队列为空\n");int x = 0;printf("要进队的元素为:");scanf("%d", &x);if (enquene(&q, x)) //进队操作 printf("进队元素为%d\n", x);elseprintf("队列满,不能进队%d\n", x);if (dequene(&q, &x)) //出队操作 printf("出队元素为%d\n", x);elseprintf("队列为空,不能出队\n");printf("%d\n", x);
}
不带头结点初始化操作
int initquene(linkquene* q)//不带头结点的初始化队列
{q->front =NULL;q->next = NULL;
}
不带头结点队列判空
int isempty(linkquene* q)//不带头结点的队列判空
{if (q->front == NULL)return true;elsereturn false;
}
不带头结点进队操作
int enquene(linkquene* q, int x)//不带头结点进队操作
{linknode* s = (linknode*)malloc(sizeof(linknode));s->data = x;s->next = NULL;if(q->front==NULL)//在空队列中插入元素{q->front=s;//修改队尾指针q->rear=s;}else{q->rear->next=s;//新结点插入到rear结点之后q->rear=s; //修改rear指针}
}
不带头结点的出队操作
int dequene(linkquene* q, int* x)//不带头结点的出队操作
{if (q->front == NULL)return false;linknode* p = q->front;x = p->data;q->front = p->next;if (q->rear == p){q->front=NULL;q->rear =NULL;}free(p);return true;
}
不带头结点的完整测试代码
#include<stdio.h>
typedef struct linknode{int data;struct linknode* next;
}linknode;
typedef struct {linknode* front, * rear;
}linkquene;
int initquene(linkquene* q)//不带头结点的初始化队列
{q->front =NULL;q->rear = NULL;
}
int isempty(linkquene* q)//不带头结点的队列判空
{if (q->front == NULL)return true;elsereturn false;
}
int enquene(linkquene* q, int x)//不带头结点进队操作
{linknode* s = (linknode*)malloc(sizeof(linknode));s->data = x;s->next = NULL;if(q->front==NULL)//在空队列中插入元素{q->front=s;//修改队尾指针q->rear=s;}else{q->rear->next=s;//新结点插入到rear结点之后q->rear=s; //修改rear指针}
}
int dequene(linkquene* q, int* x)//不带头结点的出队操作
{if (q->front == NULL)return false;linknode* p = q->front;x = p->data;q->front = p->next;if (q->rear == p){q->front=NULL;q->rear =NULL;}free(p);return true;
}
int main()
{linkquene q;initquene(&q);if (!isempty(&q)) //队列判空 printf("队列不为空\n");elseprintf("队列为空\n");int x = 0;printf("要进队的元素为:");scanf("%d", &x);if (enquene(&q, x)) //进队操作 printf("进队元素为%d\n", x);elseprintf("队列满,不能进队%d\n", x);if (dequene(&q, &x)) //出队操作 printf("出队元素为%d\n", x);elseprintf("队列为空,不能出队\n");printf("%d\n", x);
}