【正文】 、良好的交流氛圍。這些運作經(jīng)驗有力地保障了微軟亞洲研究院的交流項目有序、高效，并且充滿人文關(guān)懷，讓參加的學(xué)生有強烈的歸屬感和自豪感。同學(xué)們愿意融入微軟優(yōu)秀實習(xí)生交流中來，更好地促進(jìn)了項目發(fā)展。 br 正像微軟亞洲研究院院長洪小文博士所說：在積極謀求以國內(nèi)外 高校聯(lián)合培養(yǎng)人才的同時，我們也不斷總結(jié)、提煉，探討人才培養(yǎng)的全新模式。中美大學(xué)生交流項目是微軟亞洲研究院探索 IT 人才培養(yǎng)模式的新嘗試，這不僅是一個點到點的合作項目，它也將成為未來穩(wěn)定、廣泛、多領(lǐng)域的合作和相互溝通建立更自由、通暢的交流網(wǎng)絡(luò)。 br /p p /p p /p 本報訊 (記者 李敬 )7 月 26日 ,隨著網(wǎng)易初級副總裁周楓宣布獲獎名單 ,歷時 2 個半月的“有道難題 —— 2021 網(wǎng)易編程應(yīng)戰(zhàn)賽” (簡稱“有道難題大賽” )順利地落下了帷幕。這是這個被譽為“國際最高水平的順序競賽”的“有道難題大賽”第二次舉行。本屆競賽不只在賽事規(guī)模和獎金上有所打破 ,更在競賽方式上做了有益的探求。 br 據(jù)周楓引見 ,往年的“有道難題大賽”報名人數(shù)超越 萬人 ,比去年添加了 4000 人 。獎金和獎品總價值到達(dá) 60萬元 ,其中冠軍獎金 8 萬元 ,二、三名獎金 5萬元和 2萬元 ,均為業(yè)界最高。同時為使“有道難題大賽”更具專業(yè)性 ,更能代表中國編程的最好水平 ,網(wǎng)易有道更是對賽事方式做了嚴(yán)重調(diào)整。 br “去年的標(biāo)題是我們和 TopCoder 協(xié)作出的 ,偏算法 ,往年添加了實踐運用才干的調(diào)查。”網(wǎng)易有道技術(shù)總監(jiān)包塔解釋說 ,經(jīng)過去年的大賽他們發(fā)現(xiàn) ,算法做得好的選手在處置實踐效果時不一定有很好的表現(xiàn) ,因此往年的“有道難題大賽”分上下半場 ,上半場考算法 ,下半場以開放性的效果調(diào)查選手的實踐運用才干。 br 也正由于 如此 ,記者看到發(fā)布的競賽結(jié)果顯示 ,有的選手上半場算法得了很高的分?jǐn)?shù) ,但實踐運用才干測試拿的分少 ,而使其與前十名無緣。這樣的競賽設(shè)計讓眾多參與過百度之星、 Goole Code Jam、 TopCoder 和 ACM 應(yīng)戰(zhàn)賽的選手大呼“過癮”。曾在屢次國際大賽上取得冠軍、并被中國順序競賽界譽為“教主”的本屆“有道難題大賽”季軍得主樓天城則向記者坦言 ,“有道難題大賽”的特點就是一個字“難” ,由于開放性的實踐運用效果在任何一本書上也找不到答案 ,但有應(yīng)戰(zhàn)性才有吸引力。 br 關(guān)于網(wǎng)易有道為什么要追求這種首創(chuàng)性 ,周楓解釋 說 ,“在搜索方面我們十分年輕 ,沒有創(chuàng)新是不行的。我們會花更多的精神做更久遠(yuǎn)的規(guī)劃 ,我們希望跟他人不一樣。這也是丁磊不時的希冀 ,即每項業(yè)務(wù)都要有自己首創(chuàng)的中央?！?br /p p /p p /p 摘要 :本文針對困擾“數(shù)據(jù)結(jié)構(gòu)”課程教與學(xué)的幾個問題 ,作者根據(jù)自己的認(rèn)識和多年的實際教學(xué)經(jīng)驗 ,進(jìn)行深入淺出的分析和論述 ,以其對提高課程的認(rèn)識和興趣、牢固掌握課程知識及其靈活運用、提高利用計算機解決問題的能力具有很好的指導(dǎo)作用。 br 關(guān)鍵詞 :數(shù)據(jù)結(jié)構(gòu) 。抽象數(shù)據(jù)類型 。教學(xué) br br “數(shù)據(jù)結(jié)構(gòu)”是計算機科學(xué)與技術(shù)專業(yè)中一門重要的專業(yè)基礎(chǔ)課 ,它不僅是各大學(xué)計算機及相關(guān)的 IT 專業(yè)的核心課程之一 ,也是許多高校中非計算機專業(yè)的主要選修課程之一 [1]。美國 ACM 和 IEEE/CS于 2021 年制定的《 Computing Curricula 2021》課程體系以及我國在 2021年結(jié)合本國國情制定的《中國計算機科學(xué)與技術(shù)學(xué)科教程 2021》都賦予“數(shù)據(jù)結(jié)構(gòu)”課程極高的地位。但是 ,在該課程教與學(xué)的過程中有幾個核心問題許多教師和學(xué)生很模糊 ,也困擾著該課程的教與學(xué)。 br 1 數(shù)據(jù)結(jié)構(gòu)是如何發(fā)展起來的 br 什么是計算機科學(xué) ?從 20 世紀(jì) 60 年代以來一直有爭議 ,一部分人認(rèn)為計算機科學(xué)的核心是“信息結(jié)構(gòu)的轉(zhuǎn)換” ,即側(cè)重強調(diào)了數(shù)據(jù)結(jié)構(gòu) 。另一部分人則認(rèn)為計算機科學(xué)的核心是算法的學(xué)問 ,即側(cè)重 強調(diào)了算法的。我們不去評判 ,但應(yīng)該說從宏觀來看計算機科學(xué)是研究信息表示和信息處理的科學(xué) ,即信息在計算機中的表示和信息加工處理是計算機科學(xué)研究的主要范疇。 br 隨著計算機科學(xué)技術(shù)的進(jìn)步 ,計算機的硬件技術(shù)和軟件技術(shù)都有了飛速的發(fā)展 ,計算機應(yīng)用也已經(jīng)滲透到了社會的各個領(lǐng)域 ,信息是當(dāng)今社會的重要資源。在計算機應(yīng)用的發(fā)展過程中 ,出現(xiàn)了以下幾個突出的變化 :br (1) 計算機由最初的單一科學(xué)計算到現(xiàn)在的幾乎無所不能。計算機的早期任務(wù)是科學(xué)計算 ,隨著計算機的發(fā)展 ,幾乎所有工作都離不開計算機。 br (2) 計算機加工處理的對象由數(shù)值型變?yōu)閿?shù)值型和非數(shù)值型?，F(xiàn)在計算機所能加工處理的信息的種類越來越多。br (3) 計算機處理的數(shù)據(jù)量由小變?yōu)榇蟆⒃俚骄薮?(如海量存儲、計算 )。這一點從人們對存儲器無止境的追求就可以看出。 br (4) 數(shù)據(jù)之間的關(guān)系由簡單變復(fù)雜、再到很復(fù)雜?，F(xiàn)在計算機解決一個復(fù)雜問題不僅數(shù)據(jù)量大而且數(shù)據(jù)之間的關(guān)系越來越復(fù)雜。 br 這些變化對計算機提出了更高的要求和挑戰(zhàn) ,要應(yīng)對這些變化和挑戰(zhàn) ,人們自然想到的就是發(fā)展硬件技術(shù) ,開發(fā)出速度更快、存儲容量更大、性能更高的計算機硬件產(chǎn)品。那 么有沒有其他途徑呢 ?或者說 ,若硬件水平一定 ,有沒有可能的其他途徑來適應(yīng)這個變化呢 ?回答是肯定的 ,傳統(tǒng)的經(jīng)驗告訴我們 :將一“大堆雜亂無章”的數(shù)據(jù)交給計算機處理是很不明智的 ,加工處理的效率會非常低 ,有時甚至根本無法進(jìn)行。于是人們想到 ,通過研究問題本身 ,發(fā)現(xiàn)問題數(shù)據(jù)的特性 ,并讓計算機解決問題時利用問題數(shù)據(jù)的特性 ,從而提高計算機解決問題的效率。于是人們提出了研究求解問題的數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系 ,產(chǎn)生了數(shù)據(jù)結(jié)構(gòu)。 br 2學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義 br 很多教科書都了強調(diào)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義 ,但是 ,都站的高度太高 ,學(xué)生 體會不到 ,很多學(xué)生在被問到學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用時 ,都知道這課很重要 ,計算機專業(yè)都開設(shè) ,考研究生必考等 ,至于對專業(yè)能力培養(yǎng)有什么用 ,很少有學(xué)生說清楚 ,甚至有些教師也說不清楚 ,只是簡單地告訴學(xué)生很重要 ,要好好學(xué)。 br 下面看一個簡單的例子 ,它很直觀、很貼切的說明了數(shù)據(jù)結(jié)構(gòu)的重要性。 br 一個學(xué)生在剛?cè)雽W(xué)時 ,只發(fā)了幾本書 ,可以隨意地扔在自己的桌子上 ,要上課時 ,很容易的就找到上課要用的書 。到了大二 ,書多了 ,變成了 20 幾本 ,還可以隨意的扔在桌子上 ,當(dāng)然桌子上很滿、很亂了 ,要上課時 ,找到上課用的課本需要的時 間就長了很多 ,但是還可以忍受 。如果到了大四 ,積攢的書達(dá)到了 50 多本或者上百本 ,估計就忍受不了了 ,也許可以忍受桌子上的滿和亂 ,但是可能忍受不了找書花的時間了。要想花少的時間找到想用的書 ,一種方法是提高眼睛識別力和手找書的速度 ,另一種方法就是很多同學(xué)們做的 ,把書分類碼放 ,如數(shù)學(xué)一類、外語一類、人文一類、專業(yè)一類等 ,桌子上整齊了 ,更重要的是找到想用的書容易多了 ,花的時間少了。 br 例子中 ,前一種提高眼睛識別力方法就是發(fā)展“硬件”技術(shù)來提高解決問題的效率 ,后一種方法就是“數(shù)據(jù)結(jié)構(gòu)”的作用 ,利用數(shù)據(jù)結(jié)構(gòu) (書目信 息本身固有的關(guān)系 )來提高解決問題的效率。 br 如果把這個問題繼續(xù)擴大到學(xué)校的圖書館 ,想想幾百萬冊書雜亂地堆在圖書館里 ,那么借閱等管理幾乎是不可能的了。而現(xiàn)實是 ,圖書館里的書都是按一定規(guī)律組織的 ,這種規(guī)律就是利用了書本身的數(shù)據(jù)特性 ,即數(shù)據(jù)結(jié)構(gòu)。 br 需要特別指出的是 ,“數(shù)據(jù)結(jié)構(gòu)”這門課程是計算機應(yīng)用發(fā)展到一定程度才產(chǎn)生的 ,但是數(shù)據(jù)結(jié)構(gòu)本身是問題的數(shù)據(jù)固有的 ,人們用或不用 ,它都天然存在著。例如 ,書印刷出來后 ,書目的數(shù)據(jù)信息 (例如書名、分類等 )及關(guān)系就固有了 ,無論是堆在桌子上還是碼放 ,這種數(shù)據(jù)信息及關(guān) 系天然存在著。當(dāng)碼放書時 ,可以利用這種關(guān)系來碼放 ,這就是利用了數(shù)據(jù)結(jié)構(gòu) ,帶來的是圖書檢索的高效率。 br 因此 ,數(shù)據(jù)結(jié)構(gòu)是問題數(shù)據(jù)信息本身固有的一種特性(與計算機無關(guān) ),通過分析、研究、發(fā)現(xiàn)這些特性 ,然后在計算機求解該問題時能利用這些特性 ,從而提高加工處理的效率。 br 3抽象數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)的關(guān)系 br 很多人認(rèn)為數(shù)據(jù)結(jié)構(gòu)內(nèi)容很雜、很多 ,包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、算法等 ,難理清楚 ,不利于學(xué)習(xí)和掌握。其中一個重要的原因就是數(shù)據(jù)結(jié)構(gòu)本身是脫離計算機的 ,但是又要在計算機中用。即數(shù)據(jù)結(jié)構(gòu)是邏輯上的 ,研 究的目的是要讓計算機解決問題時利用它 ,所以要把數(shù)據(jù)結(jié)構(gòu)在計算機中存儲起來 (存儲數(shù)據(jù)并存儲關(guān)系 ),這就是存儲結(jié)構(gòu)。但是存起來不是目的 ,目的是求解問題 ,需要對問題數(shù)據(jù)實施一系列操作 (以期產(chǎn)生預(yù)期結(jié)果 ),這就是算法。 br 抽象數(shù)據(jù)類型是對問題進(jìn)行抽象建模的一個結(jié)果 ,它抽象并刻畫出問題的數(shù)據(jù)及關(guān)系 (數(shù)據(jù)結(jié)構(gòu) ),抽象并描述出實施在數(shù)據(jù)結(jié)構(gòu)上的一系列操作?？梢钥闯?,數(shù)據(jù)結(jié)構(gòu)是抽象數(shù)據(jù)類型的重要組成部分 ,因此 ,從抽象數(shù)據(jù)類型的觀點來研究數(shù)據(jù)結(jié)構(gòu)是最合適的 (筆者建議“數(shù)據(jù)結(jié)構(gòu)”課程改為“抽象數(shù)據(jù)類型及實現(xiàn)” )。 br 計算機求解一個問題 ,實際上就是一個抽象數(shù)據(jù)類型的計算機實現(xiàn) [2],包括以下兩個階段。 br (1) 抽象定義階段 :分析問題 ,給出問題的抽象數(shù)據(jù)類型定義。該階段包括分析問題的數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系 ,描述出數(shù)據(jù)結(jié)構(gòu) ,定義出實施在數(shù)據(jù)結(jié)構(gòu)上的操作。 br (2) 實現(xiàn)階段 :在計算機上實現(xiàn)抽象數(shù)據(jù)類型。該階段包括 :①數(shù)據(jù)結(jié)構(gòu)的實現(xiàn) ,即在計算機中把數(shù)據(jù)及結(jié)構(gòu)存儲起來 (既要存儲元素也要存儲關(guān)系 )—— 選擇存儲結(jié)構(gòu) 。②操作的具體實現(xiàn) ,即設(shè)計出各個操作的具體步驟 —— 算法設(shè)計。 br 從這里可以看出 ,數(shù)據(jù)結(jié)構(gòu)是 計算機求解問題過程中很重要的一部分 ,由此也可以看出數(shù)據(jù)結(jié)構(gòu)的重要性。 br 高級語言中有很多預(yù)定義類型 ,其中數(shù)組、字符串也是。在數(shù)據(jù)結(jié)構(gòu)中介紹它們 ,是要了解它們的原始邏輯模型 ,也就是說數(shù)組、字符串抽象數(shù)據(jù)類型在高級語言中都已經(jīng)給予了實現(xiàn)。高級語言中的其他數(shù)據(jù)類型也一樣 ,它們也有自己的抽象數(shù)據(jù)類型原始模型?？梢赃@么認(rèn)為 ,現(xiàn)實世界里最常用的一些原始抽象模型 ,因為用途廣泛都已經(jīng) (確定了存儲結(jié)構(gòu) )實現(xiàn)了 ,變成了預(yù)定義類型。從這里可以看出數(shù)據(jù)類型和抽象數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)的內(nèi)在聯(lián)系。 br 4內(nèi)容組織 及講授方法 br “數(shù)據(jù)結(jié)構(gòu)”的開章篇必須要講清楚數(shù)據(jù)結(jié)構(gòu)是如何產(chǎn)生的、學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要性 ,對于重要的概念不僅僅是學(xué)習(xí)其定義 ,更重要的是理清楚它們之間的關(guān)系、聯(lián)系 ,特別是抽象數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)、算法等概念。筆者認(rèn)為應(yīng)該在“問題 — 抽象 — 抽象數(shù)據(jù)類型 — 實現(xiàn)”這個大模式下來組織、教授和學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)。 br /p p p數(shù)據(jù)結(jié)構(gòu)的內(nèi)容一般包括三部分內(nèi)容 :三種基本數(shù)據(jù)結(jié)構(gòu)、最常用和最重要的操作 (查找、分類 )、典型應(yīng)用。 br 基本數(shù)據(jù)結(jié)構(gòu) br 有些教科書把數(shù)據(jù)結(jié)構(gòu)分為四種 [3],即把集合也列為一種基本數(shù)據(jù)結(jié)構(gòu) ,筆者認(rèn)為是不合適的。因為數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)元素及元素之間關(guān)系的合稱 ,集合中數(shù)據(jù)元素之間沒有關(guān)系 ,因此它不應(yīng)該算是一種數(shù)據(jù)結(jié)構(gòu)。 br 三種基本數(shù)據(jù)結(jié)構(gòu)按照“抽象 — 實現(xiàn)”的線路進(jìn)行課程內(nèi)容的組織和講授。包括三大部分。(1)抽象數(shù)據(jù)類型的定義。包括數(shù)據(jù)結(jié)構(gòu) (即數(shù)據(jù)及其邏輯特性 )、 定義的操作。 (2)抽象數(shù)據(jù)類型的實現(xiàn)。包括數(shù)據(jù)結(jié)構(gòu)的實現(xiàn) (即存儲結(jié)構(gòu) )、操作的實現(xiàn) (算法設(shè)計 )。 (3)典型應(yīng)用舉例 ,利用實現(xiàn)的抽象數(shù)據(jù)類型解決現(xiàn)實應(yīng)用中的問題。 br 線性數(shù)據(jù)結(jié)構(gòu) br 線性數(shù)據(jù)結(jié)構(gòu)是簡單但是重要的數(shù)據(jù)結(jié)構(gòu) ,在數(shù)據(jù)結(jié)構(gòu)中都占有很大的內(nèi)容篇幅。在教授和學(xué)習(xí)中必須抓住共同點、側(cè)重點。線性數(shù)據(jù)結(jié)構(gòu)的共同點是元素之間都是具有線性關(guān)系 ,因一些特殊性產(chǎn)生了一些特殊的線性數(shù)據(jù)結(jié)構(gòu)。 br (1) 一般線性表 :數(shù)據(jù)元素、操作都沒有任何特殊限制。 br (2) 棧和隊列 :數(shù)據(jù)元素?zé)o 特殊限制 ,但是插入、刪除操作限制在兩端進(jìn)行。這樣 ,這兩種線性數(shù)據(jù)結(jié)構(gòu)就具有了“先進(jìn)先出”、“先進(jìn)后出”的操作特征 ,具有非常重要的應(yīng)用價值。 br (3) 字符串 :數(shù)據(jù)元素限制為字符集 ,操作沒有限制。但是由于元素的限制 ,使得操作時的操作對象不再是簡單的單個元素