xtjd1.htm

严蔚民版的数据结构的完整课件

style='font-family:宋体;color:blue'><span style="mso-spacerun: yes">&nbsp;&nbsp;
</span>O(n<sup>3</sup>)<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:26.25pt'><span lang=EN-US
style='font-family:宋体;color:blue'><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

<p><span style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";
mso-hansi-font-family:"MS Shell Dlg"'>第一章</span><span style='font-size:9.0pt;
font-family:"MS Shell Dlg"'> </span><span style='font-size:9.0pt;mso-ascii-font-family:
"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>绪论</span><span
style='font-size:9.0pt;font-family:"MS Shell Dlg"'> <span lang=EN-US><o:p></o:p></span></span></p>

<p><span lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>1.16 <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>void
print_descending(int x,int y,int z)//</span><span style='font-size:9.0pt;
mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>按从大到小顺序输出三个数</span><span
lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'><br>
{<br>
&nbsp;&nbsp;scanf(&quot;%d,%d,%d&quot;,&amp;x,&amp;y,&amp;z);<br>
&nbsp;&nbsp;if(x&lt;y) x&lt;-&gt;y; //&lt;-&gt;</span><span style='font-size:
9.0pt;mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>为表示交换的双目运算符</span><span
lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>,</span><span
style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:
"MS Shell Dlg"'>以下同</span><span lang=EN-US style='font-size:9.0pt;font-family:
"MS Shell Dlg"'><br>
&nbsp;&nbsp;if(y&lt;z) y&lt;-&gt;z;<br>
&nbsp;&nbsp;if(x&lt;y) x&lt;-&gt;y; //</span><span style='font-size:9.0pt;
mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>冒泡排序</span><span
lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'><br>
&nbsp;&nbsp;printf(&quot;%d %d %d&quot;,x,y,z);<br>
}//print_descending <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>1.17 <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>Status
fib(int k,int m,int &amp;f)//</span><span style='font-size:9.0pt;mso-ascii-font-family:
"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>求</span><span lang=EN-US
style='font-size:9.0pt;font-family:"MS Shell Dlg"'>k</span><span
style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:
"MS Shell Dlg"'>阶斐波那契序列的第</span><span lang=EN-US style='font-size:9.0pt;
font-family:"MS Shell Dlg"'>m</span><span style='font-size:9.0pt;mso-ascii-font-family:
"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>项的值</span><span
lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>f<br>
{<br>
&nbsp;&nbsp;int tempd;<br>
&nbsp;&nbsp;if(k&lt;2||m&lt;0) return ERROR;<br>
&nbsp;&nbsp;if(m&lt;k-1) f=0;<br>
&nbsp;&nbsp;else if (m==k-1) f=1;<br>
&nbsp;&nbsp;else<br>
&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;for(i=0;i&lt;=k-2;i++) temp[i]=0;<br>
&nbsp;&nbsp;&nbsp;&nbsp;temp[k-1]=1; //</span><span style='font-size:9.0pt;
mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>初始化</span><span
lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'><br>
&nbsp;&nbsp;&nbsp;&nbsp;for(i=k;i&lt;=m;i++) //</span><span style='font-size:
9.0pt;mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>求出序列第</span><span
lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>k</span><span
style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:
"MS Shell Dlg"'>至第</span><span lang=EN-US style='font-size:9.0pt;font-family:
"MS Shell Dlg"'>m</span><span style='font-size:9.0pt;mso-ascii-font-family:
"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>个元素的值</span><span
lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'><br>
&nbsp;&nbsp;&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sum=0;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(j=i-k;j&lt;i;j++) sum+=temp[j];<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp[i]=sum;<br>
&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;f=temp[m];<br>
&nbsp;&nbsp;}<br>
&nbsp;&nbsp;return OK;<br>
}//fib<br>
</span><span style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";
mso-hansi-font-family:"MS Shell Dlg"'>分析</span><span lang=EN-US
style='font-size:9.0pt;font-family:"MS Shell Dlg"'>:</span><span
style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:
"MS Shell Dlg"'>通过保存已经计算出来的结果</span><span lang=EN-US style='font-size:9.0pt;
font-family:"MS Shell Dlg"'>,</span><span style='font-size:9.0pt;mso-ascii-font-family:
"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>此方法的时间复杂度仅为</span><span
lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>O(m^2).</span><span
style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:
"MS Shell Dlg"'>如果采用递归编程</span><span lang=EN-US style='font-size:9.0pt;
font-family:"MS Shell Dlg"'>(</span><span style='font-size:9.0pt;mso-ascii-font-family:
"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>大多数人都会首先想到递归方法</span><span
lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>),</span><span
style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:
"MS Shell Dlg"'>则时间复杂度将高达</span><span lang=EN-US style='font-size:9.0pt;
font-family:"MS Shell Dlg"'>O(k^m). <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>1.18 <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>typedef
struct{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;char
*sport;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;enum{male,female}
gender;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;char
schoolname; //</span><span style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";
mso-hansi-font-family:"MS Shell Dlg"'>校名为</span><span lang=EN-US
style='font-size:9.0pt;font-family:"MS Shell Dlg"'>'A','B','C','D'</span><span
style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:
"MS Shell Dlg"'>或</span><span lang=EN-US style='font-size:9.0pt;font-family:
"MS Shell Dlg"'>'E'<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;char
*result;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int
score;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
resulttype; <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>typedef
struct{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int
malescore;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int
femalescore;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int
totalscore;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}
scoretype; <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>void
summary(resulttype result[ ])//</span><span style='font-size:9.0pt;mso-ascii-font-family:
"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>求各校的男女总分和团体总分</span><span
lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>,</span><span
style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:
"MS Shell Dlg"'>假设结果已经储存在</span><span lang=EN-US style='font-size:9.0pt;
font-family:"MS Shell Dlg"'>result[ ]</span><span style='font-size:9.0pt;
mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>数组中</span><span
lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'><br>
{<br>
&nbsp;&nbsp;scoretype score;<br>
&nbsp;&nbsp;i=0;<br>
&nbsp;&nbsp;while(result[i].sport!=NULL)<br>
&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;switch(result[i].schoolname)<br>
&nbsp;&nbsp;&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;case 'A':<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;score[ 0
].totalscore+=result[i].score;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(result[i].gender==0) score[
0 ].malescore+=result[i].score;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else score[ 0
].femalescore+=result[i].score;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;case 'B':<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;score.totalscore+=result[i].score;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(result[i].gender==0)
score.malescore+=result[i].score;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else
score.femalescore+=result[i].score;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style='font-size:9.0pt;
mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>……</span><span
lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>&nbsp;&nbsp;&nbsp;&nbsp;</span><span
style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:
"MS Shell Dlg"'>……</span><span lang=EN-US style='font-size:9.0pt;font-family:
"MS Shell Dlg"'>&nbsp;&nbsp;&nbsp;&nbsp;</span><span style='font-size:9.0pt;
mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>……</span><span
lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'><br>
&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;i++</span><span style='font-size:9.0pt;mso-ascii-font-family:
"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>；</span><span lang=EN-US
style='font-size:9.0pt;font-family:"MS Shell Dlg"'><br>
&nbsp;&nbsp;}<br>
&nbsp;&nbsp;for(i=0;i&lt;5;i++)<br>
&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;School %d:\n&quot;,i);<br>
&nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;Total score of
male:%d\n&quot;,score[i].malescore);<br>
&nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;Total score of
female:%d\n&quot;,score[i].femalescore);<br>
&nbsp;&nbsp;&nbsp;&nbsp;printf(&quot;Total score of
all:%d\n\n&quot;,score[i].totalscore);<br>
&nbsp;&nbsp;}<br>
}//summary <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>1.19 <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>Status
algo119(int a[ARRSIZE])//</span><span style='font-size:9.0pt;mso-ascii-font-family:
"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>求</span><span lang=EN-US
style='font-size:9.0pt;font-family:"MS Shell Dlg"'>i!*2^i</span><span
style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:
"MS Shell Dlg"'>序列的值且不超过</span><span lang=EN-US style='font-size:9.0pt;
font-family:"MS Shell Dlg"'>maxint<br>
{<br>
&nbsp;&nbsp;last=1;<br>
&nbsp;&nbsp;for(i=1;i&lt;=ARRSIZE;i++)<br>
&nbsp;&nbsp;{a[i-1]=last*2*i;<br>
&nbsp;&nbsp; if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;<br>
&nbsp;&nbsp; last=a[i-1];<br>
&nbsp;&nbsp; return OK;<br>
&nbsp;&nbsp;}<br>
}//algo119<br>
</span><span style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";
mso-hansi-font-family:"MS Shell Dlg"'>分析</span><span lang=EN-US
style='font-size:9.0pt;font-family:"MS Shell Dlg"'>:</span><span
style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:
"MS Shell Dlg"'>当某一项的结果超过了</span><span lang=EN-US style='font-size:9.0pt;
font-family:"MS Shell Dlg"'>maxint</span><span style='font-size:9.0pt;
mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>时</span><span
lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>,</span><span
style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:
"MS Shell Dlg"'>它除以前面一项的商会发生异常</span><span lang=EN-US style='font-size:9.0pt;
font-family:"MS Shell Dlg"'>. <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>1.20 <o:p></o:p></span></p>

<p><span lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>void
polyvalue()<br>
{<br>
&nbsp;&nbsp;float ad;<br>
&nbsp;&nbsp;float *p=a;<br>
&nbsp;&nbsp;printf(&quot;Input number of terms:&quot;);<br>
&nbsp;&nbsp;scanf(&quot;%d&quot;,&amp;n);<br>
&nbsp;&nbsp;printf(&quot;Input the %d coefficients from a0 to
a%d:\n&quot;,n,n);<br>
&nbsp;&nbsp;for(i=0;i&lt;=n;i++) scanf(&quot;%f&quot;,p++);<br>
&nbsp;&nbsp;printf(&quot;Input value of x:&quot;);<br>
&nbsp;&nbsp;scanf(&quot;%f&quot;,&amp;x);<br>
&nbsp;&nbsp;p=a;xp=1;sum=0; //xp</span><span style='font-size:9.0pt;mso-ascii-font-family:
"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>用于存放</span><span
lang=EN-US style='font-size:9.0pt;font-family:"MS Shell Dlg"'>x</span><span
style='font-size:9.0pt;mso-ascii-font-family:"MS Shell Dlg";mso-hansi-font-family:
"MS Shell Dlg"'>的</span><span lang=EN-US style='font-size:9.0pt;font-family:
"MS Shell Dlg"'>i</span><span style='font-size:9.0pt;mso-ascii-font-family:
"MS Shell Dlg";mso-hansi-font-family:"MS Shell Dlg"'>次方</span><span lang=EN-US
style='font-size:9.0pt;font-family:"MS Shell Dlg"'><br>
&nbsp;&nbsp;for(i=0;i&lt;=n;i++)<br>
&nbsp;&nbsp;{<br>
&nbsp;&nbsp;&nbsp;&nbsp;sum+=xp*(*p++);<br>
&nbsp;&nbsp;&nbsp;&nbsp;xp*=x;<br>
&nbsp;&nbsp;}<br>
&nbsp;&nbsp;printf(&quot;Value is:%f&quot;,sum);<br>
}//polyvalue<o:p></o:p></span></p>

<p class=MsoNormal style='text-indent:26.25pt'><span lang=EN-US
style='font-family:宋体;color:blue'><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

<p class=MsoNormal align=center style='text-align:center'><span lang=EN-US
style='font-family:宋体'><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>


<div class=MsoNormal align=center style='text-align:center'><span lang=EN-US>

<hr size=2 width="100%" align=center>

</span></div>


<p class=MsoNormal><span lang=EN-US style='font-family:宋体'><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

<p class=MsoNormal><b><span style='font-size:24.0pt;font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";color:blue'>数据结构辅导站</span></b><b><span
lang=EN-US style='font-size:24.0pt;color:blue'><span style="mso-spacerun:
yes">&nbsp; </span></span></b><span lang=EN-US style='font-family:宋体'><a
href="index.htm"><b><span style='font-size:24.0pt;font-family:"Times New Roman";
text-decoration:none;text-underline:none'><span style="mso-spacerun:
yes">&nbsp;</span></span></b><span style='color:windowtext;text-decoration:
none;text-underline:none'><span style='mso-field-code:"HYPERLINK \0022G\:\\My Documents\\数据结构站点\\datas-sohu\\index\.htm\0022"'><span
style='font-family:"Times New Roman"'><span style='mso-field-code:"HYPERLINK \0022file\:\/\/\/G\:\/My%20Documents\/数据结构站点\/datas-sohu\/index\.htm\0022"'><u><span
style='font-family:宋体;color:blue'>返回主页</span></u></span></span></span></span></a><o:p></o:p></span></p>

</div>

</body>

</html>