📄 3_20.htm
字号:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=gb_2312-80">
<META NAME="Generator" CONTENT="Microsoft Word 97">
<TITLE>第 2 章 线性表</TITLE>
</HEAD>
<BODY>
<B><FONT SIZE=3><P ALIGN="JUSTIFY">20. </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>例</FONT><FONT SIZE=3> 3-5 </B></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>假定用一个单循环链表来表示队列（也称为循环链式队列），该队列只设一个队尾指针，不设队头指针，试编写下列各种运算的算法：</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> (1) </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>向循环链式队列插入一个元素值为</FONT><FONT SIZE=3> <I>x</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的结点。</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">(2) </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>从循环链式队列中删除一个结点。</P>
<P ALIGN="JUSTIFY">在进行插入和删除之前，首先应该构造一个带头结点的空循环链式队列，算法如下：</P>
</FONT><B><FONT SIZE=3><P ALIGN="JUSTIFY">Status</B> InitQueue ( LinkQueue <B>&</B>Q ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B></FONT><FONT SIZE=3><P ALIGN="JUSTIFY">// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>构造一个空循环队列</FONT><FONT SIZE=3> <I>Q</P>
</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> Q.rear = ( QueuePtr ) <B>malloc</B> ( <B>sizeof </B>( QNode ) );	</P>
<B><P ALIGN="JUSTIFY"> if</B> ( <B>!</B> Q.rear ) <B>exit</B> ( OVERFLOW );				// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>存储空间分配失败</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> Q.rear->next = Q.rear;</P>
<B><P ALIGN="JUSTIFY"> return</B> OK;</P>
</FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">}</B></FONT><FONT SIZE=3> // InitQueue</P>
<P ALIGN="JUSTIFY">(1) </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>插入（即入队）算法。</P>
</FONT><B><FONT SIZE=3><P ALIGN="JUSTIFY">Status</B> Insert ( LinkQueue <B>&</B>Q, QElemType x ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</FONT><FONT SIZE=3> </P>
</B><P ALIGN="JUSTIFY">// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>在循环链式队列</FONT><FONT SIZE=3> <I>Q </I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>中插入</FONT><FONT SIZE=3> <I>x</P>
</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> p = ( QueuePtr ) <B>malloc </B>( <B>sizeof </B>( QNode ) );	</P>
<P ALIGN="JUSTIFY">	 <B>if</B> ( <B>!</B> p ) <B>exit</B> (OVERFLOW);					// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>为新结点分配存储空间失败</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> p->data = x;									// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将</FONT><FONT SIZE=3> <I>x</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>放入新结点的数据域</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> p->next = Q.rear->next;						// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>新结点指针域值为队尾指针域值</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> Q.rear->next = p;								// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将新结点插入到队列</FONT><FONT SIZE=3> <I>Q</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的尾</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> Q.rear = p;									// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>修改队列</FONT><FONT SIZE=3> <I>Q</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的尾指针</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> <B>return</B> OK;</P>
</FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">}</B></FONT><FONT SIZE=3> // Insert</P>
<P ALIGN="JUSTIFY"> (2) </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>删除（即出队）算法。</P>
</FONT><B><FONT SIZE=3><P ALIGN="JUSTIFY">Status</B> Delete ( LinkQueue <B>&</B>Q, QElemType <B>&</B>x ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B></FONT><FONT SIZE=3><P ALIGN="JUSTIFY">// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>若队列不空，删除</FONT><FONT SIZE=3> <I>Q</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的队头元素，并用</FONT><FONT SIZE=3> <I>x</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>返回其值；若队列空，返回</FONT><FONT SIZE=3> ERROR</P>
</FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> if</B> ( rear->next = = rear ) <B>return</B> ERROR;		// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>如果队列空，则返回</FONT><FONT SIZE=3> ERROR</P>
<P ALIGN="JUSTIFY">	 <B>else {										</B>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>如果队列非空，则进行删除</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3>p = rear->next;						</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><FONT SIZE=3>// <I>p</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>指向队列的头结点</P><DIR>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">x = p->next->data;							// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将队列中第一个结点值取出放入</FONT><FONT SIZE=3> <I>x</P>
</I><P ALIGN="JUSTIFY">q = p->next</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>								</FONT><FONT SIZE=3>// <I>q</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>指向队列第一个结点（队头指针）</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">p->next = p->next->next;					// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>修改队头指针</P></DIR>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3> // else </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> <B>free</B> ( q );									// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>释放队头元素所占空间</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> <B>return</B> OK;</P>
</FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">}</B></FONT><FONT SIZE=3> // Delete</P>
</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="CENTER"></P></FONT></BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -