前言

本書用于高等院校的數(shù)據(jù)結(jié)構(gòu)課程。Python是一門可以作為入門課程的優(yōu)秀的計算機語言。它相對簡單的語法能夠讓學生更加專注于解決問題，而不用把很多精力放在對具體的編程語言的語法的理解上。Python的內(nèi)置數(shù)據(jù)結(jié)構(gòu)和大型標準庫還能夠讓學生比用其他語言更簡便地編寫一些更有趣的程序。本書假設(shè)學生已經(jīng)學習了Python的基本語法，并且已經(jīng)接觸過類的用法。大多數(shù)使用Python的傳統(tǒng)編程導論課程都涵蓋了這些基礎(chǔ)的內(nèi)容，有些課程甚至可能涵蓋了這本書里所涉及的一些主題。

Python的面向?qū)ο筇匦?，讓它成為一種非常適合用來學習數(shù)據(jù)結(jié)構(gòu)課程的語言。我們發(fā)現(xiàn)，大多數(shù)學習完編程導論課程的學生都已經(jīng)知道了如何使用類，但是他們中的許多人還需要更多的知識和經(jīng)驗，來學習如何設(shè)計和編寫自己的類?？紤]到在編程導論課程里用來學習設(shè)計類的時間非常有限，這樣的情形并不奇怪。我們可以通過學習本書前幾章里包含的一些關(guān)于類的設(shè)計的例子來解決這個問題。

學生在數(shù)據(jù)結(jié)構(gòu)課程里學習使用Python語言，可以繼續(xù)擴展他們的知識和技能，并且能夠通過一種更簡單、更熟悉的語言來獲得設(shè)計和編寫類的經(jīng)驗。Python語言也使得學習鏈式結(jié)構(gòu)變得相對更容易，這是因為Python里的每個名稱都是一個引用。因此如果要編寫鏈式結(jié)構(gòu)，學生不用再去學習其他的語法。與學習使用更復雜的語言相比，這些優(yōu)勢能夠讓主題內(nèi)容的教學速度更快。

把Python用于數(shù)據(jù)結(jié)構(gòu)課程的一個潛在缺點是：它隱藏了內(nèi)存管理的復雜性。這個特性在學習第1門課程的時候是一個優(yōu)勢，但我們認為在學習第2門課程時，學生應該需要開始理解Python解釋器隱藏的底層級細節(jié)了，這也是非常重要的內(nèi)容。由于我們學習的是Python，因此可以在更短的時間內(nèi)完成對基本數(shù)據(jù)結(jié)構(gòu)的相關(guān)內(nèi)容和知識的掌握。也就是說即使在只需要一個學期的數(shù)據(jù)結(jié)構(gòu)課程里，學生也是有時間去學習第2種編程語言的。在學生不斷提高他們的Python編程技能，并同時學習了本書的前幾章之后，他們可以相對更容易地去學習第2種面向?qū)ο蟮木幊陶Z言。通過使用C++作為第2種編程語言，學生將接觸到比較底層的編譯語言。C++的語法比Python更復雜，但是好在學生通過Python的學習已經(jīng)掌握了基本的編程概念，這使得學習C++的語法不會有非常大的障礙。例如，既然他們已經(jīng)理解了編程的基本概念以及各個語句（如條件語句和循環(huán)語句）的語義，那么他們也就只用重點學習一下這些語句在C++中的語法就行了。

一旦學生學習了基本的C++語法，就可以通過在C++里重寫鏈式結(jié)構(gòu)來涵蓋動態(tài)內(nèi)存管理的概念。這部分內(nèi)容會對基本的數(shù)據(jù)結(jié)構(gòu)概念進行加強，同時也會開始關(guān)注內(nèi)存管理問題。本書無意提供C++語言的完整介紹，只會引入C++語言的一個比較大的子集，從而方便學生理解內(nèi)存管理的底層細節(jié)，并學會在C++里編寫面向?qū)ο蟮拇a。在介紹了C++語言的基礎(chǔ)知識之后，本書還會提供Python實現(xiàn)，讓學生用C++來實現(xiàn)它們，從而介紹一些更高級的數(shù)據(jù)結(jié)構(gòu)。換句話說，Python代碼成了用來呈現(xiàn)關(guān)鍵算法和數(shù)據(jù)結(jié)構(gòu)的可執(zhí)行的偽代碼。

教學過程

由于Python能夠讓我們比其他語言更快地學習完主題內(nèi)容，因此數(shù)據(jù)結(jié)構(gòu)課程中用5個學分就可以學完本書的大部分內(nèi)容。如果用兩個學期來教學整本書，每個學期的課程就只需要3個學分。在這兩個學期，每個學期3個學分的數(shù)據(jù)結(jié)構(gòu)課程安排如下：前7章的內(nèi)容在8周內(nèi)完成；然后在剩下的7周里完成前3章關(guān)于C++的內(nèi)容，從而讓學生有足夠的時間來編寫大量的C++代碼；之后剩下的5章將在第2個學期的3個學分課程里進行詳細的介紹。因此，教師可以在課程開始的時候，先進行一周的復習，用更多的時間來討論在最后3章里提到的高級算法和數(shù)據(jù)結(jié)構(gòu)。

根據(jù)學生使用面向?qū)ο缶幊痰慕?jīng)驗，本書前3章的教學進度可以安排得很快，也可以更詳細地闡述。第1章介紹算法的漸進運行時分析，從而讓我們可以分析所有數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的運行時間。本書較早地介紹了一個Python的單元測試框架，從而可以方便學生比較正式地測試他們的代碼。在完成第4章的鏈式結(jié)構(gòu)的討論之后，教師可以比較快地介紹一下堆棧和隊列的基本概念，或者也可以通過提供的示例應用程序來繼續(xù)介紹各個算法，以及加強設(shè)計技能的教學。雖然一些編程導論課程已經(jīng)涵蓋了遞歸，但大多數(shù)學生在第一次學習的時候，并不能夠完全地理解遞歸。由于對樹的研究需要用到遞歸的概念，因此本書會在第7章的樹的內(nèi)容之前插入關(guān)于遞歸內(nèi)容的一章（第6章）。

在關(guān)于樹的一章之后，本書內(nèi)容就會切換到C++語言。第8章在基于讀者已經(jīng)了解掌握了Python的情況下，開始對C++進行簡單的介紹。第9章介紹在C++里編寫和使用類的相關(guān)細節(jié)。第10章和第11章介紹動態(tài)內(nèi)存以及在C++里如何編寫鏈式結(jié)構(gòu)。我們強烈建議讀者按順序來學習第8章到第11章。第12章介紹使用和編寫C++模板代碼的基礎(chǔ)知識，但并沒有完全覆蓋模板的所有相關(guān)內(nèi)容。由于其他的章節(jié)都不需要理解模板，讀者也可以選擇跳過第12章。最后3章介紹了一些高級算法和數(shù)據(jù)結(jié)構(gòu)。雖然這3章之間會有一些相互的參考，但是它們可以任意調(diào)換順序。

致謝

我們要感謝維滕貝格大學（Wittenberg University）的Nancy Saks和Steve Bogaerts對本書C++章節(jié)的早期草稿版本的意見。我們還要感謝Franklin, Beedle& Associates出版社，尤其是Jim Leisy和Tom Sumner。我們還要感謝我們的編輯Stephanie Welch，他發(fā)現(xiàn)了許多小錯誤，幫助我們提高了這本書的質(zhì)量。

David感謝美國Capital大學提供了休假的支持，這讓他開始了這本書的編著。David還要感謝那些使用了本書早期草稿版本，并且提出改進建議的學生們。以下這些美國Capital大學的學生因為提出了很多的合理化建議而值得得到特別認可：Kyle Beal、Michael Herold、Jeff Huenemann、John Larison以及Brenton Wolfe。最后，David要感謝他的妻子Sherri在他完成本書所需的無數(shù)個小時里給予的支持和理解。

John感謝他在沃特伯格大學（Wartburg College）的部門的同事們，他們一直為他的努力寫作提供支持；也要感謝他的學生們，他們幫助John“嘗試體驗”了一些學習材料。最重要的是，John感謝他的家人，特別是他的妻子Elizabeth Bingham，感謝她的愛、支持和理解，讓這個項目成為可能。