日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言中隊列的結構和函數接口的使用示例_C 語言

作者：[Pokemon]大貓貓 ? 更新時間： 2023-05-08 編程語言

一、隊列的結構

隊列：一種操作受限的線性表，只允許在線性表的一端進行插入，另一端進行刪除，插入的一端稱為隊尾，刪除的一端稱為隊頭

通過 動態順序表 的實現，可以發現在數組的頭部進行插入刪除操作時，需要移動數據，效率較低，因此不采用數組來實現隊列

但通過 單鏈表 的實現，可以發現在對單鏈表進行頭插時效率很高，而進行尾插時，需要找尾數據，較為麻煩，但是可以通過增加一個尾指針的方式來提升效率，因此用單鏈表的頭尾指針來實現隊列，結構如下：

//隊列的元素類型
typedef int QueueDataType;
//隊列的結點結構
typedef struct QueueNode
{
	QueueDataType data;
	struct QueueNode* next;
}QNode;
//隊列結構，需要包含指向鏈表的頭指針和尾指針
//為了求隊列數據個數時，時間復雜度為 O(1)，這里增加一個 size 變量
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

二、隊列的函數接口

1. 初始化和銷毀

初始化函數如下：

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

鏈表的結點都是動態開辟的，不用隊列時，應當銷毀

銷毀函數如下：

void QueueDestroy(Queue* pq)
{
	assert(pq);
	//從頭結點開始銷毀
	QNode* cur = pq->head;
	while (cur)
	{
		//保存下一個結點
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

2. 入隊和出隊

入隊：在隊尾插入元素

入隊函數如下：

void QueuePush(Queue* pq, QueueDataType x)
{
	assert(pq);
	//創建新結點
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//沒有結點時，插入元素，需要改變隊列的頭尾指針
	//有結點時，直接鏈接在尾結點之后，tail 變成新的尾
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	//插入元素后，數據個數需要自增
	pq->size++;
}

出隊：刪除隊頭元素

出隊函數如下：

void QueuePop(Queue* pq)
{
	assert(pq);
	//沒有元素時，不能刪除，這里直接調用判空函數
	assert(!QueueEmpty(pq));
	//如果只有一個結點時，需要改變隊列的頭尾指針
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	//刪除元素后，數據個數需要自減
	pq->size--;
}

3. 訪問隊頭和隊尾元素

訪問隊頭元素函數如下：

QueueDataType QueueFront(Queue* pq)
{
	assert(pq);
	//沒有元素時，不能取隊頭元素，這里直接調用判空函數
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

訪問隊尾元素函數如下：

QueueDataType QueueBack(Queue* pq)
{
	assert(pq);
	//沒有元素時，不能取隊尾元素，這里直接調用判空函數
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

4. 判空和元素個數

判空函數如下：

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

元素個數函數如下：

size_t QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

原文鏈接：https://blog.csdn.net/qq_70793373/article/details/128494299

欄目分類
最近更新