2024/9/261數據結構案例教程2024/9/262導學問題1問題中的數據在計算機中如何組織？（1-1）計算某位同學高等數學、英語及計算機導論三門課程的總分。（1-2）已知一個班級20名學生的高等數學成績，求全班該門課的平均分。（1-3）已知一個班級20名學生的高等數學、英語及計算機導論課程的成績，計算每位同學的總分以及全班三門課程各自的均分。2024/9/263導學問題1問題中的數據在計算機中如何組織？（1-4）在問題1-3的基礎上，列出全班成績的排名（列出學號、姓名及分數），如表1-1所示。2024/9/264導學問題1問題中的數據在計算機中如何組織？（1-5）假設一個U盤中有3個文件夾，每個文件夾中又有若干文件，如圖1-1所示。請設計一種文件信息存儲方法，當輸入某個文件名稱后，顯示該文件在U盤中的存儲路徑，若U盤中無該文件，則顯示“文件未找到”。2024/9/265導學問題1問題中的數據在計算機中如何組織？（1-6）某城市中5個地標建筑間有多條道路相通，每條道路長度不同，如圖1-2所示。設計一個道路查詢系統，能讓游客查詢從任一個地標建筑到另一個地標建筑之間的最短路徑。2024/9/266導學問題1的分析計算機處理的對象由數值發展到非數值數據，而且處理的數據量也越來越大。在程序設計時面對這樣的數據，需要解決如何表示這些數據間的結構關系？如何在計算機中存儲這些數據？計算機處理的不再只是加減乘除等數值計算，而是排序、信息可視化、求最短路徑等較為復雜的非數值計算。在程序設計時，需要解決如何在問題數據上進行非數值計算等操作？以上這些問題正是數據結構這門課程研究的內容。2024/9/267導學問題2編程實現對輸入的整數n計算sum=1!+2!+3!+4!+…+n!doublesum(intn){doubles=0;inti,j;doublep;for(i=1;i<=n;i++){p=1;for(j=1;j<=i;j++) p*=j;s+=p;}returns;}2024/9/268導學問題2的分析可考慮將雙重循環，進一步簡化為單重循環：doublesum2(intn){doubles=0;inti;doublep=1;for(i=1;i<=n;i++){ p*=i; s+=p;}returns;}為什么用單重循環實現比用雙重循環實現有效？2024/9/2691.1知識學習1.1.1數據結構課程的研究內容數據結構就是研究非數值計算問題中的數據以及它們之間的關系和操作算法的學科，具體主要包含3個方面的內容：數據的邏輯結構、數據的存儲結構（物理結構）和數據的操作算法。2024/9/26101.1知識學習1.1.2數據的結構相關術語

數據

數據元素

數據對象數據結構的三個要素

數據結構涉及三個要素，分別是數據的邏輯結構、存儲結構和操作算法2024/9/26111.1知識學習1.1.3算法與算法分析1.什么是算法2.算法的評價3.算法的描述方法2024/9/2612算法性能分析與度量算法的性能標準算法的事前估計算法的后期測試2024/9/2613算法性能分析與度量算法的性能標準正確性健壯性可讀性高效率低存儲空間算法的事前估計算法的后期測試2024/9/2614

算法性能分析與度量算法的性能標準算法的事前估計時間復雜度空間復雜度算法的后期測試2024/9/2615算法性能分析與度量算法的性能標準算法的事前估計時間復雜度空間復雜度存儲空間的固定部分

程序指令代碼的空間，常數、簡單變量、定長成分(如數組元素、結構成分、對象的數據成員等)變量所占的空間可變部分

尺寸與實例特性有關的成分變量所占空間、引用變量所占空間、遞歸棧所用的空間、通過new和delete命令動態使用的空間2024/9/26161.2知識應用導學問題1-4的數據結構2024/9/26171.2知識應用導學問題1-5的數據結構2024/9/26181.2知識應用導學問題1-6的數據結構2024/9/26191.2知識應用導學問題2的時間復雜度問題2的原始程序是一個雙重循環，其中外循環體中的語句p=1;執行次數為n；外循環體中的語句s+=p;執行次數為n；內循環體中語句p*=j;的執行次數為：1+2+3+…+n=n(n+1)/2；因此該程序的基本語句執行次數是n2數量級，時間復雜度T(n)=O(n2)。改進后的程序是一個單重循環，循環體中的語句p*=j;和s+=p;分別執行了n次，因此該程序的基本語句執行次數是n數量級，時間復雜度T(n)=O(n)。2024/9/26