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