?? 第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 + -