IT虾米网

数据结构--链队列

insus 2022年11月07日 编程语言 44 0

1、结构体设计

//链队列的结构体设计 
typedef int ELEM_TYPE; 
 
//有效数据节点的结构体设计: 
typedef struct Node 
{ 
	ELEM_TYPE data;//数据域 
	struct Node* next;//指针域 
}Node, *PNode; 
 
//头结点的结构体设计: 
typedef struct LQueue 
{ 
	struct Node* front; 
	struct Node* rear; 
}LQueue, *PLQueue; 

2、可操作函数

(1)初始化、入对

//初始化  
void Init_LQueue(struct LQueue* lq) 
{ 
	//assert 
 
	lq->front = NULL; 
	lq->rear = NULL; 
	//lq->front = lq->rear = NULL; 
} 
 
//入队 
bool Push(struct LQueue* lq, ELEM_TYPE val) 
{ 
	//assert 
	//不需要判满 
 
	struct Node *pnewnode = (struct Node *)malloc(1 * sizeof(struct Node)); 
	assert(pnewnode != NULL); 
	pnewnode->data = val; 
	 
	if(IsEmpty(lq))//特殊情况下插入:空队列 
	{ 
		pnewnode->next = lq->front; 
 
		lq->front = lq->rear = pnewnode;//因为如果是一个空队列,那么你入队的元素则既是队头也是队尾 
	} 
	else//正常情况下插入:插入的时候,里面有元素,不是一个空队列 
	{ 
		pnewnode->next = lq->rear->next; 
		lq->rear->next = pnewnode; 
 
		lq->rear = pnewnode;//别忘了:更新一下队尾指针,重新让它指向新插入的尾结点 
	} 
 
	return true; 
} 

(2)出队

//出队(这里需要知道出队的值,通过输出参数rtval带出来) 
bool Pop(struct LQueue* lq, ELEM_TYPE* rtval) 
{ 
	//assert 
	if(IsEmpty(lq)) 
	{ 
		return false; 
	} 
 
	*rtval = lq->front->data; 
 
	//if(lq->front->next == NULL)//ok 判断剩余元素是否仅剩下一个 
	if(Get_length(lq) == 1)//ok 
	{ 
		struct Node *p = lq->front; 
		free(p); 
 
		lq->front = lq->rear = NULL; 
	} 
	else //正常情况下: 剩余元素不止一个 
	{ 
		struct Node *p = lq->front; 
 
		lq->front = p->next; 
		free(p); 
	} 
 
	return true; 
} 

(3)获取队头元素查找、判空、获取有效长度、清空、销毁、打印

//获取队头元素值(这里需要知道队头的值,通过输出参数rtval带出来) 
bool Top(struct LQueue* lq, ELEM_TYPE* rtval) 
{ 
	//assert 
	if(IsEmpty(lq)) 
	{ 
		return false; 
	} 
 
	*rtval = lq->front->data; 
 
	return true; 
} 
 
//搜索 
struct Node* Search(struct LQueue* lq, ELEM_TYPE val) 
{ 
	//这里用的是 不需要前驱的for循环 ,遍历一遍即可 
	for(struct Node*p=lq->front; p!=NULL; p=p->next) 
	{ 
		if(p->data == val) 
		{ 
			return p; 
		} 
	} 
 
	return NULL; 
} 
 
//判空 
bool IsEmpty(struct LQueue* lq) 
{ 
	return lq->front == NULL; 
} 
 
//判满(链式结构 不需要判满) 
 
//获取有效长度 
int Get_length(struct LQueue* lq) 
{ 
	int count = 0; 
	//这里用的是 不需要前驱的for循环 ,遍历一遍即可 
	for(struct Node*p=lq->front; p!=NULL; p=p->next) 
	{ 
		count++; 
	} 
 
	return count; 
} 
 
//清空 
void Clear(struct LQueue* lq) 
{ 
	Destroy(lq); 
} 
 
 
//销毁 
void Destroy(struct LQueue* lq) 
{ 
	struct Node *p = lq->front; 
	struct Node *q; 
 
	while(p != NULL) 
	{ 
		q = p->next; 
		free(p); 
		p = q; 
	} 
 
	lq->front = lq->rear = NULL; 
} 
 
//打印 
void Show(struct LQueue* lq) 
{ 
	//这里用的是 不需要前驱的for循环 ,遍历一遍即可 
	for(struct Node*p=lq->front; p!=NULL; p=p->next) 
	{ 
		printf("%d ", p->data); 
	} 
	printf(" 
"); 
} 

3、主函数用例测试

//链栈的测试用例 
int main() 
{ 
	LStack head; 
	Init_LStack(&head); 
 
	for(int i=0; i<20; i++)//20 19 18.....3 2 1 
	{ 
		Push(&head, i+1); 
	} 
	Show(&head); 
	printf("length = %d 
", Get_length(&head)); 
 
	ELEM_TYPE tmp; 
	bool tag1 = Pop(&head, &tmp); 
	if(tag1) 
	{ 
		printf("pop = %d 
", tmp); 
	} 
	Show(&head); 
	printf("length = %d 
", Get_length(&head)); 
 
	ELEM_TYPE flg; 
	bool tag2 = Top(&head, &flg); 
	if(tag2) 
	{ 
		printf("top = %d 
", flg); 
	} 
	Show(&head); 
	printf("length = %d 
", Get_length(&head)); 
 
	Destroy(&head); 
 
	return 0; 
} 

本文参考链接:https://blog.csdn.net/m0_67391870/article/details/123579291
评论关闭
IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

Java多线程中Lock锁如何使用