网上做家教的网站,做设计图任务的网站,ui设计软件培训学校,如何获取网站开发语言文章目录队列#xff1a;单链队列的实现及操作#xff1a;1.定义一个队列2.构造一个空队列3.销毁队列4.插入元素e到队尾5.删除队头元素#xff0c;用e返回其值单链队列操作实例及代码#xff1a;队列#xff1a;
队列是先进先出的线性表。
队列只允许在表的一端插入元素…
文章目录队列单链队列的实现及操作1.定义一个队列2.构造一个空队列3.销毁队列4.插入元素e到队尾5.删除队头元素用e返回其值单链队列操作实例及代码队列
队列是先进先出的线性表。
队列只允许在表的一端插入元素在另一端删除元素。
队列中允许插入的一端叫队尾允许删除的一端叫队头。
单链队列的实现及操作
1.定义一个队列
一个链队列由每个结点连接起来。由于插入和删除是在队头和队尾进行的我们为了方便起见直接弄两个指针指向头结点和队尾元素所在结点。
typedef struct QNode
{QElemType_L data;struct QNode *next;
}QNode;
typedef QNode* QueuePtr;
typedef struct
{QueuePtr front; QueuePtr rear;
}LinkQueue; 2.构造一个空队列
我们增加一个头结点首先分配一个头结点的内存空间。当队列为空时队头指针和队尾指针都指向头结点而且头结点的指针域的指针指向空意味着队列里面没有存元素。
Status InitQueue_L(LinkQueue Q)
{Q.front Q.rear (QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front-next NULL;return OK;
}3.销毁队列
这个销毁最终把头结点也给销毁了。
注意一点链表知道头指针就能根据-next确定后面所有结点我们初始化增加了一个尾指针让他指向最后一个结点但这并不意味着我们改变了尾指针指向的位置链表中间的结点就没了中间的结点还是可以根据头指针和-next找到的我们其实可以把尾指针理解成一个标记他的位置并不影响链表只不过方便了我们找队尾元素所在结点。真正影响链表的是我们的头指针我们遍历也是通过头指针-next来的每个结点都会用到。
这里我们就把尾指针当作一个转移变量来用了。先存头结点指向的下一个结点的位置然后把头结点的位置free掉再让头结点指向尾指针指向的位置即将下一个结点的位置当作头结点。一路循环当没有下一个存元素的结点了头指针的位置指向头结点尾指针被赋为null头指针free之后头结点的空间也没了然后把头指针也赋为null。最终头指针尾指针都指向null而且所有空间全被free掉。
void DestroyQueue_L(LinkQueue Q)
{while(Q.front){Q.rear Q.front-next;free(Q.front);Q.front Q.rear; }
}如果是清空的话有一点不同就是还有头结点只不过-next指向null了和初始状态一样头指针尾指针指向头结点头结点指向下一个结点的指针指向null。这里还是把尾指针当作一个转移变量初始指向第一个结点每次让头指针指向的下一个结点变成尾指针这个转移变量指向的下一个结点然后free掉尾指针原来指向的结点然后把当前尾指针指向的结点更新为尾指针这个转移变量指向的下一个结点。举个例子即可明白。
void ClearQueue_L(LinkQueue Q)
{Q.rear Q.front-next;while(Q.rear){Q.front-next Q.rear-next; free(Q.rear); Q.rear Q.front-next;}Q.rear Q.front;
}4.插入元素e到队尾
插入元素分配一个结点的空间然后原尾指针的下一个位置指向新结点更新尾指针。
Status EnQueue_L(LinkQueue Q, QElemType_L e)
{QueuePtr p;p (QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p-data e;p-next NULL;Q.rear-next p;Q.rearp;return OK;
} 5.删除队头元素用e返回其值
删除先判端是否有元素然后取出队头元素让头结点指针域里面的指针指向的下一个结点变成第一个元素的结点指向的下一个元素的结点。
这里我们还要考虑是否对尾指针产生影响当仅有一个元素时删除后队列为空尾指针应该指向头结点。
最后把删除的结点的空间释放掉即可。
Status DeQueue_L(LinkQueue Q, QElemType_L e)
{QueuePtr p;if(Q.frontQ.rear)return ERROR;p Q.front-next;e p-data;Q.front-next p-next;if(Q.rearp)Q.rear Q.front;free(p);return OK;
} 单链队列操作实例及代码
代码
#includecstdio
#includecstdlib#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define UNDERFLOW -3
#define TRUE 1
#define FALSE 0typedef int QElemType_L;
typedef int Status;typedef struct QNode
{QElemType_L data;struct QNode *next;
}QNode;
typedef QNode* QueuePtr;
typedef struct
{QueuePtr front; QueuePtr rear;
}LinkQueue;
Status InitQueue_L(LinkQueue Q)
{Q.front Q.rear (QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front-next NULL;return OK;
}
void ClearQueue_L(LinkQueue Q)
{Q.rear Q.front-next;while(Q.rear){Q.front-next Q.rear-next; free(Q.rear); Q.rear Q.front-next;}Q.rear Q.front;
}
void DestroyQueue_L(LinkQueue Q)
{while(Q.front){Q.rear Q.front-next;free(Q.front);Q.front Q.rear; }
}
Status EnQueue_L(LinkQueue Q, QElemType_L e)
{QueuePtr p;p (QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p-data e;p-next NULL;Q.rear-next p;Q.rearp;return OK;
}
Status DeQueue_L(LinkQueue Q, QElemType_L e)
{QueuePtr p;if(Q.frontQ.rear)return ERROR;p Q.front-next;e p-data;Q.front-next p-next;if(Q.rearp)Q.rear Q.front;free(p);return OK;
}
void QueueTraverse_L(LinkQueue Q, void (Visit)(QElemType_L))
{QueuePtr p;p Q.front-next;while(p){Visit(p-data);p p-next;}printf(\n);
}
void PrintElem(QElemType_L e)
{printf(%d , e);
}
Status QueueEmpty_L(LinkQueue Q)
{if(Q.frontQ.rear)return TRUE;elsereturn FALSE;
}
int main(){LinkQueue Q;int i;QElemType_L e;printf(初始化链队 Q ...\n); InitQueue_L(Q);printf(\n);QueueEmpty_L(Q) ? printf( Q 为空\n) : printf( Q 不为空\n);printf(\n);for(i1; i6; i) {printf(元素 \%2d\ 入队, 2*i);EnQueue_L(Q, 2*i);printf(\n);}printf(\n);printf( Q 中的元素为Q ); QueueTraverse_L(Q, PrintElem);printf(\n);DeQueue_L(Q, e);printf(队头元素 \%d\ 出队...\n, e);printf( Q 中的元素为Q ); QueueTraverse_L(Q, PrintElem);printf(\n); printf(销毁 Q 前);Q.front!NULL Q.rear!NULL ? printf( Q 存在\n) : printf( Q 不存在\n);DestroyQueue_L(Q);printf(销毁 Q 后);Q.front!NULL Q.rear!NULL ? printf( Q 存在\n) : printf( Q 不存在\n);printf(\n);
}
输出
初始化链队 Q …
Q 为空
元素 2 入队 元素 4 入队 元素 6 入队 元素 8 入队 元素 “10” 入队 元素 “12” 入队
Q 中的元素为Q 2 4 6 8 10 12
队头元素 “2” 出队… Q 中的元素为Q 4 6 8 10 12
销毁 Q 前 Q 存在 销毁 Q 后 Q 不存在
