📄 第1章 绪论.htm
字号:
lang=EN-US style="mso-bidi-font-size: 10.5pt"><o:p></o:p></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 0.05pt; TEXT-INDENT: -0.05pt; tab-stops: 45.0pt"><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><SPAN
style="mso-spacerun: yes"> </SPAN></SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">3</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">）栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><o:p></o:p></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 0.05pt; TEXT-INDENT: -0.05pt; tab-stops: 45.0pt"><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><SPAN
style="mso-spacerun: yes"> </SPAN></SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">4</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">）数据结构的评价非常复杂，可以考虑两个方面，一是所选数据结构是否准确、完整的刻划了问题的基本特征；二是是否容易实现（如对数据分解是否恰当；逻辑结构的选择是否适合于运算的功能，是否有利于运算的实现；基本运算的选择是否恰当。）</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><o:p></o:p></SPAN></P>
<P class=MsoNormal
style="TEXT-INDENT: 22.8pt; tab-stops: 45.0pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">5</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">．评价好的算法有四个方面。一是算法的正确性；二是算法的易读性；三是算法的健壮性；四是算法的时空效率（运行）。</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><o:p></o:p></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 22.8pt; tab-stops: 45.0pt; mso-para-margin-left: 2.0gd"><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">6</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">．（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">1</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">）见上面题</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">3<SPAN
style="mso-spacerun: yes"> </SPAN></SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">2</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">）见上面题</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">4<SPAN
style="mso-spacerun: yes"> </SPAN></SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">3</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">）见上面题</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">3<o:p></o:p></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 0.05pt; TEXT-INDENT: -0.05pt; tab-stops: 45.0pt"><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><SPAN
style="mso-spacerun: yes"> </SPAN></SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">4</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">）算法的时间复杂性是算法输入规模的函数。算法的输入规模或问题的规模是作为该算法输入的数据所含数据元素的数目，或与此数目有关的其它参数。有时考虑算法在最坏情况下的时间复杂度或平均时间复杂度。</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><o:p></o:p></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 0.05pt; TEXT-INDENT: -0.05pt; tab-stops: 45.0pt"><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><SPAN
style="mso-spacerun: yes"> </SPAN></SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">5</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">）算法是对特定问题求解步骤的描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有五个重要特性：有穷性、确定性、可行性、输入和输出。</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><o:p></o:p></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 0.05pt; TEXT-INDENT: -0.05pt; tab-stops: 45.0pt"><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><SPAN
style="mso-spacerun: yes"> </SPAN></SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">（</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">6</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">）频度。在分析算法时间复杂度时，有时需要估算基本操作的原操作，它是执行次数最多的一个操作，该操作重复执行的次数称为频度。</SPAN><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt"><o:p></o:p></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 22.8pt; tab-stops: 45.0pt; mso-para-margin-left: 2.0gd"><SPAN
lang=EN-US style="mso-bidi-font-size: 10.5pt">7</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">．</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">集合、线性结构、树形结构、图形或网状结构。<SPAN
lang=EN-US><SPAN style="mso-spacerun: yes">
</SPAN>8</SPAN>．逻辑结构、存储结构、操作（运算）。<SPAN lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal
style="TEXT-INDENT: 22.8pt; tab-stops: 45.0pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">9</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">．通常考虑算法所需要的存储空间量和算法所需要的时间量。后者又涉及到四方面：程序运行时所需输入的数据总量，对源程序进行编译所需时间，计算机执行每条指令所需时间和程序中指令重复执行的次数。<SPAN
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal
style="TEXT-INDENT: 22.8pt; tab-stops: 45.0pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">10</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">．<SPAN
lang=EN-US>D</SPAN>是数据元素的有限集合，<SPAN lang=EN-US>S</SPAN>是<SPAN
lang=EN-US>D</SPAN>上数据元素之间关系的有限集合。<SPAN lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal style="TEXT-INDENT: 22.8pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">11</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">．</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-hansi-font-family: 'Times New Roman'; mso-bidi-font-size: 10.5pt; mso-ascii-font-family: 'Times New Roman'">“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。<SPAN
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal
style="TEXT-INDENT: 22.8pt; tab-stops: 45.0pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">12</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">．见上面题<SPAN
lang=EN-US>2</SPAN>。<SPAN lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal
style="TEXT-INDENT: 22.8pt; tab-stops: 45.0pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">13</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">．将学号、姓名、平均成绩看成一个记录（元素，含三个数据项），将<SPAN
lang=EN-US>100</SPAN>个这样的记录存于数组中。因一般无增删操作，故<SPAN
style="COLOR: red">宜采</SPAN>用顺序存储。<SPAN lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 22.8pt; TEXT-INDENT: -22.8pt; tab-stops: 45.0pt; mso-char-indent-count: -2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN
style="mso-spacerun: yes">
</SPAN><B style="mso-bidi-font-weight: normal">typedef</B> <B
style="mso-bidi-font-weight: normal"><SPAN
style="mso-spacerun: yes"> </SPAN>struct</B><o:p></o:p></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 22.8pt; TEXT-INDENT: -22.8pt; tab-stops: 45.0pt; mso-char-indent-count: -2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN
style="mso-spacerun: yes">
</SPAN>{<B style="mso-bidi-font-weight: normal">int</B> num;//</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">学号<SPAN
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 22.8pt; TEXT-INDENT: -22.8pt; tab-stops: 45.0pt; mso-char-indent-count: -2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN
style="mso-spacerun: yes">
</SPAN><B style="mso-bidi-font-weight: normal">char</B> name[8];//</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">姓名<SPAN
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 22.8pt; TEXT-INDENT: -22.8pt; tab-stops: 45.0pt; mso-char-indent-count: -2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN
style="mso-spacerun: yes">
</SPAN><B style="mso-bidi-font-weight: normal">float</B> score;/</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">平均成绩<SPAN
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 22.8pt; TEXT-INDENT: -22.8pt; tab-stops: 45.0pt; mso-char-indent-count: -2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN
style="mso-spacerun: yes"> </SPAN><SPAN
style="mso-spacerun: yes"> </SPAN>}node</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">；<SPAN
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 22.8pt; TEXT-INDENT: -22.8pt; tab-stops: 45.0pt; mso-char-indent-count: -2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt"><SPAN
style="mso-spacerun: yes">
</SPAN><SPAN style="mso-spacerun: yes"> </SPAN><SPAN
style="mso-spacerun: yes"> </SPAN>node student[100];<o:p></o:p></SPAN></P>
<P class=MsoNormal
style="MARGIN-LEFT: 22.8pt; tab-stops: 45.0pt; mso-para-margin-left: 2.0gd"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">14. </SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">见上面题<SPAN
lang=EN-US>4</SPAN>（<SPAN lang=EN-US>3</SPAN>）。<SPAN
lang=EN-US><o:p></o:p></SPAN></SPAN></P>
<P class=MsoNormal
style="TEXT-INDENT: 22.8pt; tab-stops: 45.0pt; mso-char-indent-count: 2.0"><SPAN
lang=EN-US style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">15</SPAN><SPAN
style="FONT-FAMILY: 宋体; mso-bidi-font-size: 10.5pt">．应从两方面进行讨论：如通讯录较少变动（如城市私人电话号码），主要用于查询，以顺序存储较方便，既能顺序查找也可随机查找；若通讯录经常有增删操作，用链式存储结构较为合适，将每个人的情况作为一个元素⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -