带头结点的单链表就地逆置_单链队列_C语言「抄作业」

C语言「抄作业」系列之单链队列

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define qElemType int				/* 单链队列元素数据类型 */
#define QNODE_SIZE sizeof (struct qNode)	/* 单链队列结点空间大小 */
#define LINKQUE_SIZE sizeof (struct linkQue)	/* 单链队列空间大小 */

#define status int	/* 状态型变量 */
#define OVERFLOW -1	/* 内存溢出状态码 */
#define ERROR 0		/* 错误状态码 */
#define OK 1		/* 正确状态码 */

/* 单链队列结点数据结构 */
typedef struct qNode {
	qElemType data;
	struct qNode *next;
} qNode, *qNodePtr;

/* 单链队列数据结构 */
typedef struct linkQue {
	qNodePtr front;	/* 队首指针 */
	qNodePtr rear;	/* 队尾指针 */
} linkQue, *linkQueue;

/****************************** 带头结点的单链队列基本操作(9个) *****************************/
void initQueue (linkQueue *Q);		/* 初始化 */
void destroyQueue (linkQueue Q);	/* 销毁 */
void clearQueue (linkQueue Q);		/* 清空 */

status queueIsEmpty (linkQueue Q);	/* 判断单链队列是否为空 */
int queueLength (linkQueue Q);		/* 获取单链队列的长度 */
status getHeadElem (linkQueue Q, qElemType *e);	/* 获取队首元素值 */

status enQueue (linkQueue Q, qElemType e);	/* 入队 */
status deQueue (linkQueue Q, qElemType *e);	/* 出队 */

void queueTraverse (linkQueue Q, void (*vi)(qElemType));	/* 依次对单链队列的每个元素调用函数vi() */
/********************************************************************************************/
void vi (qElemType e);	/* visit函数，定义为打印元素值 */
/********************************************************************************************/

/* 初始化 */
/* 操作结果：构造一个带头结点的空单链队列Q */
void initQueue (linkQueue *Q) {
	*Q = (linkQueue) malloc (LINKQUE_SIZE); /* 产生单链队列 */
	if (!*Q) /* 内存分配失败 */
		exit (OVERFLOW);
	(*Q)->front = (*Q)->rear = (qNodePtr) malloc (QNODE_SIZE); /* 产生头结点，并使队首、队尾指针均指向此头结点 */
	if (!(*Q)->front) /* 内存分配失败 */
		exit (OVERFLOW);
	(*Q)->front->next = NULL;
}

/* 销毁 */
/* 初始条件：单链队列Q已存在*/
/* 操作结果：销毁单链队列Q */
void destroyQueue (linkQueue Q) {
	qNodePtr p, q;
	
	p = Q->front; /* p指向Q的头结点 */
	while (p) {
		q = p->next; /* q指向p的下一个结点 */
		free (p); /* 回收p指向的结点 */
		p = q; /* p移动到下一个结点 */
	} /* 直到没有下一个结点 */
}

/* 清空 */
/* 初始条件：单链队列Q已存在 */
/* 操作结果：将Q重置为空队列 */
void clearQueue (linkQueue Q) {
	qNodePtr p, q;
	
	p = Q->front->next; /* p指向队列的第一个结点 */
	while (p) {
		q = p->next; /* q指向p的下一个结点 */
		free (p); /* 回收p指向的结点 */
		p = q; /* p移动到下一个结点 */
	} /* 直到没有下一个结点 */
	
	Q->rear = Q->front; /* 队头、队尾指针均指向Q的头结点 */ 
	Q->front->next = NULL;
}

/* 判断单链队列是否为空 */
/* 初始条件：单链队列Q已存在 */
/* 操作结果：若Q为空队列，则返回TRUE，否则返回FALSE */
status queueIsEmpty (linkQueue Q) {
	return Q->front->next == NULL;
}

/* 获取单链队列的长度 */
/* 初始条件：单链队列Q已存在 */
/* 操作结果：返回Q中数据元素个数 */
int queueLength (linkQueue Q) {
	int i = 0;
	qNodePtr p;
	
	p = Q->front->next; /* p指向队列的第一个结点 */
	while (p) { /* 未到队尾 */
		i++;
		p = p->next;
	}
  	
	return i;
}

/* 获取队首元素值 */
/* 初始条件：单链队列Q已存在 */
/* 操作结果：在带头结点的单链队列Q中，当队列不为空时，将队首元素值赋予e并返回OK，否则返回ERROR */
status getHeadElem (linkQueue Q, qElemType *e) {
	qNodePtr p;
	
	if (Q->front->next == NULL)
		return ERROR;
	
	p = Q->front->next; /* p指向队列的第一个结点 */
	*e = p->data;
	
	return OK;
}

/* 入队 */
/* 初始条件：单链队列Q已存在 */
/* 操作结果：在带头结点的单链队列Q，于队尾插入元素e，成为新的队尾元素 */ 
status enQueue (linkQueue Q, qElemType e) {
	qNodePtr p;
	
	p = (qNodePtr) malloc (QNODE_SIZE); /* 产生新结点 */
	if (!p) /* 内存分配失败 */
		exit (OVERFLOW);
	
	p->data = e;
	p->next = NULL;
	
	Q->rear->next = p; /* 将新结点链接到队尾之后 */
	Q->rear = p; /* 队尾指向新结点 */
	
	return OK;
}

/* 出队 */
/* 初始条件：单链队列Q已存在 */
/* 操作结果：在带头结点的单链队列Q中，删除队首元素，其值赋予e */
status deQueue (linkQueue Q, qElemType *e) {
	qNodePtr p;
	
	if (Q->front->next == NULL)
		return ERROR;
	
	p = Q->front->next; /* p指向队列的第一个结点 */
	*e = p->data; /* 取出数据 */
	Q->front->next = p->next;
	free (p); /* 删除该结点 */
	
	if (Q->rear == p){ /* 队列为空 */
		Q->rear = Q->front; /* 队头、队尾指针均指向Q的头结点 */
		Q->front->next = NULL;
	}
	
	return OK;
}

/* 依次对单链队列的每个元素调用函数vi() */
/* 初始条件：单链队列Q已存在 */
/* 操作结果：依次对Q的每个数据元素调用函数vi() */
void queueTraverse (linkQueue Q, void (*vi)(qElemType)) {
	qNodePtr p;
	
	p = Q->front->next; /* p指向队首 */
	if (p == NULL)
		puts ("The linked queue is empty! ");
	
	while (p) {
		vi (p->data);
		p = p->next;
	}
	putchar ('n');
}

/* visit函数，定义为打印元素值 */
void vi (qElemType e) {
	printf ("%d ", e);
}

int main (void) {
	linkQueue Q;
	qElemType e; 
	qElemType a=1, b=2, c=3, d=4;
	int len;
	status sts;
	
	/* 初始化单链队列 */
	initQueue (&Q);
	printf ("initQueue: &Q -> Q's Address: %p, Q->front's Address: %p, Q->rear's Address: %pn", Q, Q->front, Q->rear);
	putchar ('n');
	
	/* 入队若干元素 */
	sts = enQueue (Q, a);
	printf ("enQueue: Q,a=%d -> status: %dn", a, sts);
	sts = enQueue (Q, b);
	printf ("enQueue: Q,b=%d -> status: %dn", b, sts);
	sts = enQueue (Q, c);
	printf ("enQueue: Q,c=%d -> status: %dn", c, sts);
	sts = enQueue (Q, d);
	printf ("enQueue: Q,d=%d -> status: %dn", d, sts);
	putchar ('n');
	
	/* 依次对单链队列的每个元素调用函数vi() */
	/* 打印单链队列 */
	printf ("Q: ");
	queueTraverse (Q, &vi);
	putchar ('n');	
	
	/* 判断单链队列是否为空 */
	sts = queueIsEmpty (Q);
	printf ("queueIsEmpty: Q -> isEmpty: %dn", sts);
	
	/* 获取单链队列的长度 */
	len = queueLength (Q);
	printf ("queueLength: Q -> length: %dn", len);
	putchar ('n');
	
	/* 获取队首元素值 */
	sts = getHeadElem(Q, &e);
	printf ("getHeadElem: Q,&e -> status: %d, e: %dn", sts, e);
	putchar ('n');
	
	/* 出队 */
	sts = deQueue (Q, &e);
	printf ("deQueue: Q,&e -> status: %d, e: %dn", sts, e);
	putchar ('n');

	/* 打印单链队列 */
	printf ("Q: ");
	queueTraverse (Q, &vi);
	putchar ('n');	
	
	/* 清空单链队列 */
	clearQueue (Q);
	printf ("clearQueue: Q -> donen"); 
	sts = queueIsEmpty (Q);
	printf ("queueIsEmpty: Q -> isEmpty: %dn", sts);
	putchar ('n');	
	
	/* 销毁单链队列 */
	destroyQueue (Q);
	printf ("destroyQueue: Q -> donen");
	putchar ('n');
	
	printf ("press any key to exit.n");
	
	getch (); /* 屏幕暂留 */
	return 0;
}
           

运行结果

碧海风：数据结构篇_C语言「抄作业」​zhuanlan.zhihu.com

C语言抄作业系列，只有答案，没有讲解！

计算机科学专业毕业多年的一个啥也没学会而转行做了产品经理的家伙，从当年的各种作业里搬运来的一些乱七八糟的东西。

C语言「抄作业」​www.zhihu.com