計(jì)算機(jī)專業(yè)課程與計(jì)算思維關(guān)聯(lián)分析研究畢業(yè)論文

1、長(zhǎng) 治 學(xué) 院2013屆學(xué)士學(xué)位畢業(yè)論文計(jì)算機(jī)專業(yè)課程與計(jì)算思維關(guān)聯(lián)分析研究 以數(shù)據(jù)結(jié)構(gòu)為例 學(xué) 號(hào)： 09407112 姓 名： 指導(dǎo)教師： 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 系 別： 計(jì)算機(jī)系 計(jì)算機(jī)專業(yè)課程與計(jì)算思維關(guān)聯(lián)分析研究 以數(shù)據(jù)結(jié)構(gòu)為例摘 要：計(jì)算思維是當(dāng)前國(guó)際計(jì)算機(jī)教育界關(guān)注的熱點(diǎn)，也是當(dāng)前計(jì)算機(jī)教育需要重點(diǎn)研究的重要課題，為了培養(yǎng)大學(xué)生計(jì)算思維能力，提高大學(xué)生運(yùn)用計(jì)算思維解決實(shí)際問(wèn)題的能力，并促進(jìn)大學(xué)生更好的學(xué)習(xí)計(jì)算機(jī)專業(yè)課程，需要對(duì)計(jì)算思維與計(jì)算機(jī)專業(yè)課程知識(shí)點(diǎn)的關(guān)聯(lián)進(jìn)行研究。本文首先對(duì)本課題的研究背景和意義進(jìn)行闡述，然后對(duì)計(jì)算思維基本概念和數(shù)據(jù)結(jié)構(gòu)知識(shí)體系進(jìn)行闡述，最后以數(shù)據(jù)結(jié)

2、構(gòu)課程為例，通過(guò)兩個(gè)實(shí)例重點(diǎn)分析研究遞歸和分治思想在數(shù)據(jù)結(jié)構(gòu)課程知識(shí)點(diǎn)中的運(yùn)用。通過(guò)本課題的研究，可以使我們真正理解計(jì)算思維方法在數(shù)據(jù)結(jié)構(gòu)課程中是怎樣體現(xiàn)的，并且更深入的掌握數(shù)據(jù)結(jié)構(gòu)課程，進(jìn)而提高計(jì)算思維能力。關(guān)鍵詞：計(jì)算思維；數(shù)據(jù)結(jié)構(gòu)；關(guān)聯(lián)目 錄1 引言12 計(jì)算思維基本概念13 數(shù)據(jù)結(jié)構(gòu)課程的知識(shí)體系13.1 數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容13.2 數(shù)據(jù)結(jié)構(gòu)的四類基本結(jié)構(gòu)及其特點(diǎn)24 計(jì)算思維與數(shù)據(jù)結(jié)構(gòu)課程的關(guān)聯(lián)34.1 遞歸方法的應(yīng)用實(shí)例44.2 分治方法的應(yīng)用實(shí)例55 總結(jié)7參考文獻(xiàn)7致謝9計(jì)算機(jī)專業(yè)課程與計(jì)算思維關(guān)聯(lián)分析研究 以數(shù)據(jù)結(jié)構(gòu)為例1 引言計(jì)算思維是當(dāng)前國(guó)際計(jì)算機(jī)界廣為關(guān)注的一個(gè)重要

3、概念，也是當(dāng)前計(jì)算機(jī)教育需要重點(diǎn)研究的重要課題。計(jì)算思維是必須具備的思維能力，就如同所有人都具備“讀、寫(xiě)、算”能力一樣，當(dāng)計(jì)算思維真正融入到人們的生活中時(shí)，它作為一個(gè)解決問(wèn)題的有效工具。近年來(lái)，計(jì)算思維能力的培養(yǎng)成為國(guó)際和國(guó)內(nèi)關(guān)注的熱點(diǎn)。文中通過(guò)實(shí)例研究計(jì)算思維方法在數(shù)據(jù)結(jié)構(gòu)課程知識(shí)點(diǎn)中的體現(xiàn)，讓學(xué)生真正理解計(jì)算思維與數(shù)據(jù)結(jié)構(gòu)課程中知識(shí)點(diǎn)的關(guān)聯(lián)，促進(jìn)學(xué)生更好地學(xué)習(xí)計(jì)算機(jī)專業(yè)課程，并且訓(xùn)練和培養(yǎng)學(xué)生的計(jì)算思維能力，使學(xué)生學(xué)會(huì)用計(jì)算思維去思考問(wèn)題和解決問(wèn)題。2 計(jì)算思維基本概念計(jì)算思維是卡內(nèi)基梅隆大學(xué)計(jì)算機(jī)科學(xué)系主任周以真（jeannettem.wing）教授首先提出的。計(jì)算思維運(yùn)用計(jì)算機(jī)科學(xué)的基

4、礎(chǔ)概念進(jìn)行問(wèn)題求解、系統(tǒng)設(shè)計(jì)以及人類行為理解的涵蓋計(jì)算機(jī)科學(xué)的一系列思維活動(dòng)。計(jì)算思維方法主要有：遞歸思維方法，直接或間接的調(diào)用自身的思維方法；分治思維方法，將一個(gè)規(guī)模為n的復(fù)雜問(wèn)題分解為k個(gè)規(guī)模較小的容易解決的子問(wèn)題的思維方法；抽象思維方法，利用概念、判斷和推理的形式，借助語(yǔ)言符號(hào)來(lái)進(jìn)行的思維方法；歸納思維方法，從觀察一類事物中的一部分具有某種屬性，經(jīng)分析判斷得出該類事物都具有這種屬性的思維方法；類比思維方法，借助于兩類不同本質(zhì)事物之間的相似性，通過(guò)比較把一種已掌握的對(duì)象的知識(shí)平移到另一種新的對(duì)象上去的推理方法；逆向思維方法，運(yùn)用反證法來(lái)進(jìn)行推理得到問(wèn)題的結(jié)論的思維方法。3 數(shù)據(jù)結(jié)構(gòu)課程的知

5、識(shí)體系3.1 數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)課程中研究的主要內(nèi)容如下表1所示：表1 數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容結(jié)構(gòu)主要內(nèi)容線性表 順序表，線性鏈表，循環(huán)鏈表，雙向鏈表?xiàng)?順序棧，鏈?zhǔn)綏ｊ?duì)列 抽象數(shù)據(jù)類型隊(duì)列，鏈隊(duì)列，循環(huán)隊(duì)列串 定長(zhǎng)順序存儲(chǔ)，堆分配存儲(chǔ)，塊鏈存儲(chǔ)數(shù)組 順序表示，壓縮存儲(chǔ)廣義表 鏈?zhǔn)酱鎯?chǔ)樹(shù)和二叉樹(shù) 順序存儲(chǔ)，鏈?zhǔn)酱鎯?chǔ)，遍歷二叉樹(shù)，線索二叉樹(shù)圖 存儲(chǔ)結(jié)構(gòu)，圖的遍歷（深度優(yōu)先搜索，廣度優(yōu)先搜索）查找 靜態(tài)查找表，動(dòng)態(tài)查找表3.2 數(shù)據(jù)結(jié)構(gòu)的四類基本結(jié)構(gòu)及其特點(diǎn)在任何問(wèn)題中，數(shù)據(jù)元素都不是孤立存在

6、的，在它們之間存在著某種關(guān)系，這種數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)。根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有四種基本結(jié)構(gòu)：線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu)、集合，這四種基本結(jié)構(gòu)的概念、特點(diǎn)及關(guān)系圖如表2所示：表2 數(shù)據(jù)結(jié)構(gòu)的四種基本結(jié)構(gòu)概念特點(diǎn)關(guān)系圖線性結(jié)構(gòu)各個(gè)數(shù)據(jù)元素組成的結(jié)點(diǎn)按邏輯關(guān)系依次排成一條鏈。每個(gè)結(jié)點(diǎn)只有一個(gè)直接前驅(qū)（除第一個(gè)結(jié)點(diǎn)之外）和一個(gè)直接后繼（除最后一個(gè)結(jié)點(diǎn)）；各元素之間的邏輯關(guān)系是線性關(guān)系。樹(shù)形結(jié)構(gòu)具有分支、層次結(jié)構(gòu)，其形態(tài)有點(diǎn)像自然界中的樹(shù)。每個(gè)結(jié)點(diǎn)只有一個(gè)直接前驅(qū)（除根結(jié)點(diǎn)之外），每個(gè)結(jié)點(diǎn)可以有多個(gè)直接后繼（除葉子結(jié)點(diǎn)之外）；各元素之間的邏輯關(guān)系是非線性的。圖形結(jié)構(gòu)結(jié)點(diǎn)按邏輯

7、關(guān)系相互纏繞在一起，任何兩個(gè)結(jié)點(diǎn)都可以相鄰。每個(gè)結(jié)點(diǎn)都可以有任意多個(gè)直接前驅(qū)和任意多個(gè)直接后繼；各元素之間的邏輯關(guān)系是非線性的。集合各結(jié)點(diǎn)之間無(wú)任何邏輯關(guān)系。組織形式松散；任何兩個(gè)結(jié)點(diǎn)之間都沒(méi)有任何邏輯關(guān)系。4 計(jì)算思維與數(shù)據(jù)結(jié)構(gòu)課程的關(guān)聯(lián)計(jì)算思維的本質(zhì)是抽象化和自動(dòng)化，抽象化是指將實(shí)際問(wèn)題轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)中的線性、樹(shù)形、圖形、集合四種基本結(jié)構(gòu)，自動(dòng)化是指設(shè)計(jì)算法和編程實(shí)現(xiàn)，最后在實(shí)際的計(jì)算機(jī)中運(yùn)行并求解。數(shù)據(jù)結(jié)構(gòu)課程中分別運(yùn)用四種基本結(jié)構(gòu)解決問(wèn)題時(shí)所體現(xiàn)的計(jì)算思維方法如表3所示：表3 數(shù)據(jù)結(jié)構(gòu)中體現(xiàn)的計(jì)算思維方法基本結(jié)構(gòu)體現(xiàn)的計(jì)算思維方法線性結(jié)構(gòu) 抽象思維、遞歸思維、分治思維、類比思維樹(shù)形結(jié)構(gòu)

8、 遞歸思維、抽象思維圖形結(jié)構(gòu) 遞歸思維、抽象思維、類比思維集合 抽象思維、歸納思維數(shù)據(jù)結(jié)構(gòu)中的很多知識(shí)點(diǎn)都能夠體現(xiàn)計(jì)算思維方法，下面舉兩個(gè)實(shí)例分析計(jì)算思維與數(shù)據(jù)結(jié)構(gòu)課程知識(shí)點(diǎn)的關(guān)聯(lián)。4.1 遞歸方法的應(yīng)用實(shí)例遞歸法的基本思想：把問(wèn)題轉(zhuǎn)化為規(guī)模縮小了的同類問(wèn)題的子問(wèn)題，然后直接或間接的調(diào)用自身。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。運(yùn)用遞歸算法的條件包括：確定遞歸公式；確定邊界條件。圖的深度優(yōu)先搜索遍歷問(wèn)題：已知無(wú)向圖g如圖1所示，采用深度優(yōu)先搜索遍歷求圖中頂點(diǎn)訪問(wèn)序列。圖1 無(wú)向圖g在圖1中，將整個(gè)無(wú)向圖的所有頂點(diǎn)的遍歷看作一個(gè)復(fù)雜的問(wèn)題，將圖中每個(gè)頂點(diǎn)的訪問(wèn)看成這個(gè)復(fù)雜問(wèn)題的子問(wèn)題，對(duì)每個(gè)頂

9、點(diǎn)的訪問(wèn)為一個(gè)遞歸的過(guò)程。分析問(wèn)題：從圖中某個(gè)頂點(diǎn)vi出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從vi的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，有多個(gè)鄰接點(diǎn)時(shí)，從序號(hào)為最小值的開(kāi)始進(jìn)行深度優(yōu)先遍歷，當(dāng)無(wú)路徑可走時(shí)，順原路返回到上一個(gè)鄰接點(diǎn)，進(jìn)行遞歸的搜索另一個(gè)未被訪問(wèn)的鄰接點(diǎn)，直至圖中所有和vi有路徑相同的頂點(diǎn)都被訪問(wèn)到。該無(wú)向圖的深度優(yōu)先搜索過(guò)程如圖2所示, 圖中從v1開(kāi)始訪問(wèn)，帶箭頭的實(shí)線表示遍歷時(shí)的搜索路徑，帶箭頭的虛線表示回溯的路徑，即遞歸過(guò)程，圖中的小圓圈表示已被訪問(wèn)過(guò)的鄰接點(diǎn)，小圓圈中的數(shù)字表示訪問(wèn)頂點(diǎn)的先后順序。圖2 深度優(yōu)先搜索的過(guò)程由上述分析可知，無(wú)向圖g深度優(yōu)先搜索遍歷的頂點(diǎn)訪問(wèn)序列為：v1v2v4v8v5

10、v3v6v74.2 分治方法的應(yīng)用實(shí)例分治法的基本思想是將一個(gè)規(guī)模為n的復(fù)雜問(wèn)題分解為k個(gè)規(guī)模較小的容易解決的子問(wèn)題，這些子問(wèn)題相互獨(dú)立且與原問(wèn)題相同，折半查找法能夠體現(xiàn)分治法的思想。問(wèn)題：有一組成績(jī)，現(xiàn)要在這組成績(jī)中查找分?jǐn)?shù)為21和85的成績(jī)是否存在。抽象過(guò)程：將這組成績(jī)抽象為一個(gè)有序線性表，每個(gè)分?jǐn)?shù)抽象為線性表中的數(shù)據(jù)元素，分?jǐn)?shù)21和85抽象為要查找的關(guān)鍵字，所以該問(wèn)題可以抽象為有序表查找問(wèn)題。有序表查找問(wèn)題：已知如下11個(gè)數(shù)據(jù)元素的有序表：（05,13,19,21,37,56,64，75,80,88,92），現(xiàn)要查找關(guān)鍵字為21和85的數(shù)據(jù)元素。分析問(wèn)題：有序表的查找采用折半查找法，其基

11、本思路：首先定義待查元素所在范圍的下界low和上界high,指針mid指示區(qū)間的中間位置，中間位置數(shù)據(jù)元素的關(guān)鍵字st.elemmid.key（st表示有序表名，elem表示數(shù)組名）與給定值key（關(guān)鍵字）比較，確定區(qū)間范圍。當(dāng)關(guān)鍵字st.elemmid.key與給定值key相等時(shí)，查找成功；當(dāng)下界low大于上界high時(shí),說(shuō)明該線性表中沒(méi)有關(guān)鍵字等于key的數(shù)據(jù)元素，所以查找不成功。流程圖如圖3：圖3 折半查找問(wèn)題流程圖運(yùn)用分治法將一個(gè)復(fù)雜的實(shí)際問(wèn)題轉(zhuǎn)化為多個(gè)相同的簡(jiǎn)單的子問(wèn)題并用程序化語(yǔ)言表示，最終由機(jī)器執(zhí)行完成，在很大程度上提高了工作效率。5 總結(jié)通過(guò)對(duì)計(jì)算機(jī)專業(yè)課程和計(jì)算思維關(guān)聯(lián)分析研

12、究，可以使學(xué)生真正理解計(jì)算思維與數(shù)據(jù)結(jié)構(gòu)課程之間的關(guān)聯(lián)，進(jìn)而幫助學(xué)生更好的將計(jì)算思維運(yùn)用于其他計(jì)算機(jī)專業(yè)課程的學(xué)習(xí)中，并提高學(xué)生的計(jì)算思維能力，使學(xué)生體會(huì)到學(xué)習(xí)計(jì)算機(jī)專業(yè)課程的樂(lè)趣，形成一個(gè)良性循環(huán)，極大地提高學(xué)生學(xué)習(xí)其他課程的積極性和主動(dòng)性。文中主要研究了遞歸和分治方法在數(shù)據(jù)結(jié)構(gòu)課程知識(shí)點(diǎn)中的體現(xiàn)，在研究過(guò)程中遇到一些問(wèn)題而不能得到理想結(jié)果，通過(guò)反復(fù)查找錯(cuò)誤，修改，最終得到正確結(jié)果。另外，文中提到的其他計(jì)算思維方法在數(shù)據(jù)結(jié)構(gòu)課程知識(shí)點(diǎn)中的體現(xiàn)仍是值得探討的問(wèn)題。參考文獻(xiàn)1 教育部高等學(xué)校計(jì)算機(jī)基礎(chǔ)課程教學(xué)指導(dǎo)委員會(huì).高等學(xué)校計(jì)算機(jī)基礎(chǔ)教學(xué)發(fā)展戰(zhàn)略研究報(bào) 告暨計(jì)算機(jī)基礎(chǔ)課程教學(xué)基本要求m,北京

13、:高等教育出版社.2009.2 中國(guó)高等院校計(jì)算機(jī)基礎(chǔ)教育改革課題研究組,中國(guó)高等院校計(jì)算機(jī)基礎(chǔ)教育課程體系 2008m,北京:清華大學(xué)出版社.2008.3 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)m,北京:清華大學(xué)出版社.2010.4 董榮勝,古天龍.計(jì)算思維與計(jì)算機(jī)方法論j,計(jì)算機(jī)科學(xué).2009(1):1-4.5 陳杰華.程序設(shè)計(jì)課程中強(qiáng)化計(jì)算思維訓(xùn)練的實(shí)踐探索j,計(jì)算機(jī)教育.2009(20):84-85.6 王震江,何英,吳紹兵.數(shù)據(jù)結(jié)構(gòu)m,昆明:云南大學(xué)出版社.2008.7 楊曉光.數(shù)據(jù)結(jié)構(gòu)實(shí)例教程m,北京:清華大學(xué)出版社.2008.8 賈茹,郝長(zhǎng)勝,裴衣非.visual basic程序設(shè)

14、計(jì)課程的計(jì)算思維教學(xué)實(shí)踐j,電腦知識(shí)與技術(shù).2011(25):6266-6268. 9 吳紹兵.計(jì)算思維和程序設(shè)計(jì)能力的培養(yǎng)j,計(jì)算機(jī)教育.2011(16):11-14.10 于曉強(qiáng),趙秀巖,閆丕濤.計(jì)算機(jī)程序設(shè)計(jì)課程中計(jì)算思維能力的培養(yǎng)j,計(jì)算機(jī)教育. 2011(13):18-21.the study on the analysis of computer professionalcourses and associated computational thinking a case study of data structuremajor: computer science and tec

15、hnology name: li pingstudent id: 09407112 supervisor: guo yongmeiabstract: computational thinking is the hot spot in the current international computer education circle, and is the important topic of computer education that needs to focus on research in the current. in order to calculate the college

16、 students thinking ability, improve the ability of college students using computational thinking to solve practical problems, and promote college students better learning computer professional course, you need to study on the analysis of computer professional courses and associated computational thi

17、nking. this subject at first, this paper elaborates the research background and significance, then the basic concepts of computational thinking and data structure of knowledge, the data structure course, for example, through two examples analyzed studies recursive and partition in the application of

18、 data structure course knowledge point. through this topic research, we can really understand how the thinking method in the data structure course is to reflect, and to further master data structure course, computational thinking ability can be improved. keywords: computational thinking; data structure; associate致謝經(jīng)過(guò)一段時(shí)間的不懈努力，終于將這篇論文寫(xiě)完，在我寫(xiě)論文的過(guò)程中遇到了無(wú)數(shù)的困難和障礙，但都在同學(xué)和老師的幫助下渡過(guò)了，在此向幫助和指導(dǎo)過(guò)我的各位老師表示最忠心的感謝！這篇論文能夠順利完成，首先要感謝我的論文指導(dǎo)老師郭詠梅老師，開(kāi)始寫(xiě)論文郭老師給我下載很多文獻(xiàn)資料，