一項計算機基礎課程改革的啟示（五）

奚：王老師，C程序語言和數據結構一直是各自獨立開設的課程，而你們的改革是把數據結構融入到從C到C++的發展過程中。

王：確切地說，是把順序結構部分融入從C到C++的發展過程中，然后用C++描述非順序結構部分。應該表明，我們不是要否定數據結構作為一門獨立課程的意義，可是獨立不表示孤立，獨立表示這門課程有其特有的、重點研究的內容，孤立是它與其他課程沒有聯系。而程序語言和數據結構是有內在聯系的，我們要研究這種聯系，目的是探索程序語言發展的規律，促進程序語言和數據結構的學習。

奚：數據結構重點研究的內容是什么呢？

王：算法分析。對一個問題，僅僅編寫一個求解程序還不夠，處理大規模的復雜數據，一個程序能夠在合理的時間內結束才有意義，這就需要對程序正文所代表的算法進行嚴格的時間復雜度分析，而這種分析又必須和數據結構一起進行，因為沒有不依賴數據結構而設計的算法，也沒有不為算法服務的數據結構。

奚：所以數據結構這門課程也可以叫做數據結構和算法分析。

王：是的。我國最早引進的一本數據結構經典教材的名稱便是“算法＋數據結構＝程序”。

奚：數據結構用偽碼描述在很長一段時間是占主流的研究方法，您如何看待這種方法呢？

王：要歷史地看待這個問題。在二十世紀六十年代，數據結構剛剛成為一門科學的時候，霍爾的“計算機程序設計公理化基礎”一文清楚地表明它的研究方法：把注意力集中到程序的構成和分析方面，說得更明確點，就是集中到程序正文所代表的算法的結構上，以便在數學推理的基礎上對程序進行嚴格的分析。[1]而用偽碼描述，可以不受程序實現細節的影響，突出重點。再加上當時個人電腦還不普及，描述數據結構的語言還只是主要供教學使用的PASCAL，而非實用的軟件開發語言，使數據結構的應用范圍受到很大限制，這也從另一個方面促進了這種偏向于學者的研究方法的形成。

奚：您不贊同這種方法嗎？

王：不能簡單地說贊同還是不贊同，要看研究的重點和學習的主體?！端惴ǎ珨祿Y構＝程序》一書的作者沃思說過：“盡管對于學者們來說，純粹描述算法原則及其數學分析可能具有刺激性和挑戰性，但這對于實際工程人員似乎是不實在的。因此，我嚴格遵循這一原則：將程序的最終形式以某一語言表述出來，以便確實能在計算機上執行?！盵1] 他認為把程序表示為充分考慮細節的最終形式對工程人員是很重要的，因為程序設計中，錯誤正是隱藏在細節之中。[1]

奚：用偽碼描述和重視程序實現細節是兩種對立的方法嗎？

王：不應該是。用偽碼描述，可以突出數據結構的研究重點——算法分析，重視程序實現細節，可以認識到數據結構對程序語言發展的積極作用。

奚：這兩種方法可以統一起來嗎？

王：可以。隨著計算機的不斷普及，數據結構這門課程不僅成為各大學計算機專業本科的主干課程，也成為非計算機類學生和研究生學習計算機的必修課程，這些學生大部分不屬于學者群，他們很難把偽碼描述的數據結構用程序語言描述出來，并且在計算機上通過。

奚：他們需要用程序語言描述數據結構的方法。

王：是的。

奚：可是如您所說，數據結構最初的描述語言是PASCAL，您為什么選擇了C呢？

王：從描述數據結構的作用上說，PASCAL和C是一樣的，但是從研究程序語言發展規律上說，從C到C++比從PASCAL到C++更容易講述，而且C和C++都是軟件設計的核心語言，這種研究更有實際價值。

奚：現在不僅有許多用C描述的數據結構教材，而且還有用C++、JAVA描述的，它們都不能滿足您的要求嗎？

王：應該說，是程序語言和數據結構相互脫節的教學模式不能滿足計算機科學發展的要求，教材是為教學服務的。這種教學模式的思想根源是，程序語言僅僅是描述數據結構的工具，而數據結構不依賴任何編程語言的描述，或者說，數據結構既不影響程序語言的發展，也不受程序語言發展的影響。現在，C++的最新發展將運用最廣的一些數據結構實現出來，而且成為C++新標準的一部分，使這種教學模式陷入一種困境：如果用C++描述數據結構，就要先學習C++，而學習C++又需要數據結構的知識。你中有我，我中有你。

奚：如何走出這個困境呢？

王：C++新標準為我們具體指出了走出這個困境的道路：首先把C++新標準實現的數據結構內容，例如連續順序存儲結構、鏈式順序存儲結構、string，歸入到C語言教學中，用C語言實現這些數據結構，完成對C語言的第一次辯證意義上的否定。

奚：如您在本期文章中所講述的那樣。

王：是的。然后發現問題，再完成第二次辯證意義上的否定，把數據結構的C代碼轉化為C++代碼，達到C++的新標準。這是我們下一期要講述的內容。

奚：這是一個否定之否定的過程。

王：是的。這是C、C++和結構的辯證關系決定的C的必然發展過程：C需要創建結構，但是C語言結構不能像語言內部類型一樣使用，這不利于軟件重用程度的進一步提高，于是，用戶從設計自定義數據類型開始擴展C語言 [2]，C++對C的結構體類型作了實質性的擴充 [2]?？梢哉f，C++的許多性能都圍繞著一個根本的思想：創建新的數據類型的能力[3]。這就是哲學所說的事物內部的必然的自己的運動。

奚：這就是規律。

王：是的。這兩次否定過程構成我們的教材《C/C++與數據結構》（第3版）（上冊），可以作為C和C++語言教材。

奚：教材下冊的內容呢？

王：用C++描述數據結構非線性部分和算法的時間復雜度分析構成我們的教材《C/C++與數據結構》（第3版）（下冊）。這樣，數據結構教學就可以在比較堅實的C++語言基礎上，相對獨立地開展算法研究。

奚：兩種方法統一了，既促進C語言的學習，也促進數據結構的學習。

王：是的。從C語言，到數據結構的順序部分的C描述，再到C++，再到數據結構的非順序部分的C++描述，

奚：那么就可以說C、C++和數據結構已經成為相互包含的整體了？

王：可以這樣說。我們要知道，辯證法所說的相互包含或某物中包含他物，并不是指他物作為一個現成的細小的東西包含在某物中，而是作為某物的一個方面、一種趨勢、一種因素包含在某物中。C包含C++，是指C包含著C++作為其必然的發展。C++包含C是因為它是更好的C。

奚：這是否定之否定運動的結果。

王：或者說是辯證運動的結果。

奚：那么如何把握這種辯證運動的實質呢？

王：“兩個矛盾方面的共存、斗爭以及融合成一個新范疇，就是辯證運動的實質。誰要給自己提出消除壞的方面的任務，就是立即使辯證運動終結”。[4]

奚：就程序設計而言，兩個矛盾的方面就是存儲和處理。

王：或者說是數據結構和算法，數據結構是發展的存儲?？v觀短暫的計算機發展史，這兩個方面一直保持不變。發展演化的是它們之間的關系，就是所謂的程序設計方法。[5]

奚：算法+數據結構=程序，簡明地表示了這種辯證運動的實質。

王：是的。抓住矛盾，否定之否定這個過程就容易看出來了。可以用個比喻，形象的說明這個否定之否定的過程。一顆麥粒種子，在適宜的土壤和氣候中發芽，是麥粒的一次否定，在精心培育下，它生長，開花，結果，最后又產生了麥粒，這是否定之否定。這兩次否定的結果就不僅是收獲更多的麥粒種子，而且種子的品質得到改良。這個過程的每一次否定都推進事物的完善化。

奚：可以把第一顆麥粒種子比作C，把在適宜的土壤和氣候中發芽比作數據結構的C描述，把精心培育和收獲比作C++。

王：是這樣的。沒有適宜的土壤和氣候，種子不會發芽結果，類似，沒有數據結構的C描述過程，就沒有C++的新標準。在數據結構的C描述過程中，C語言內部類型代表存儲，函數代表處理。要實現數據結構，就需要存儲復雜數據，而C語言沒有相應的內部類型，這就要求程序員自己在C語言的機制上構造這樣的存儲。例如，雖然C數組類型提供了數據的連續存儲模式，但是沒有提供對數組插入、刪除等基本處理，而這是存儲應該包含的內容，它們是算法或者說處理所依賴的方法。于是程序員通過創建基本函數克服了C的這種局限性，他們由此創建了基本順序表，結構串等，作為語言類型的補充。不僅如此，C語言沒有直接支持鏈式存儲模式的類型，程序員還創建了鏈表存儲結構（由于篇幅的限制，我們沒有在文章中一一講述這方面的內容）。這個過程持續了約40年，可是人們簡單地把它歸結為傳統的設計方法，如《標準C++寶典》一書中所說，“在傳統的程序設計方法中，程序員先設計幾組數據結構，然后用函數和過程處理這些數據。該方法稱為過程化程序設計，這種方法已經沿用了40年”。[6]而實際上，在這個過程中，程序員不僅最大限度地克服了C語言局限性，而且也具體表達了對C語言未來方展的要求，這是改造世界的主體的主觀能動性。

奚：程序語言和數據結構脫節的教學模式，把從C到C++的過程給抽象掉了。

王：是的，也可以說是把人的主觀能動性給抽象掉了，把改造世界的主體給抽象掉了，把認識的主體也給抽象掉了，因為人首先是改造世界的主體，然后才是認識世界的主體。

奚：那就是說把學習的主動性和積極性也給抽象掉了。

王：是的。主動性和積極性不是固有的抽象物，而是產生于包含主體的改造世界的實踐活動。

奚：這個活動不存在了，主動性和積極性也就不存在了。

王：C++迫使我們走上辯證唯物主義道路。這樣我們就會少走很多彎路。

參考文獻

[1] 沃思著.曹德和，劉椿年譯. 算法+數據=結構程序[M]. 北京: 科學出版社，1987.1，5.

[2] AI Stevens，Clayton Walnum著.林麗閔，別紅霞譯.標準C++寶典.北京:電子工業出版社，2001.245.

[3] Bruce Eckel著.劉宗田，邢大紅，孫慧杰譯.C++編程思想[M].北京:機械工業出版社，2001.前言.

[4] 馬克思恩格斯全集（第4卷）. 北京: 人民出版社，1960. 145-146.

[5] Stanley B.Lippman著.潘愛民，張麗譯.C++ Primer第三版 中文版.北京:中國電力出版社，2004.1.

[6] AI Stevens，Clayton Walnum著.林麗閔，別紅霞等譯.標準C++寶典.北京:電子工業出版社，2001.154.