軟件基礎(chǔ)串講一

1、計(jì)算機(jī)軟件基礎(chǔ)重點(diǎn)知識(shí)串講1第一章 概 述1.1 計(jì)算機(jī)軟件的定義1.2 程序設(shè)計(jì)語言1.3 操作系統(tǒng)1.4 應(yīng)用軟件21.1 計(jì)算機(jī)軟件的定義1、計(jì)算機(jī)系統(tǒng) 計(jì)算機(jī)系統(tǒng)是接收、處理和提供數(shù)據(jù)的裝置，它由硬件和軟件兩大部分組成。 硬件是組成計(jì)算機(jī)系統(tǒng)的所有電子的、機(jī)械的、磁性的、光學(xué)的裝置和部件。 5大部件： (運(yùn)算器控制器)存儲(chǔ)器輸入設(shè)備輸出設(shè)備32、計(jì)算機(jī)軟件軟件程序，開發(fā)軟件寫程序？錯(cuò)誤！程序只是軟件的一個(gè)組成部分寫程序只是軟件開發(fā)的過程中的一個(gè)步驟軟件是程序、數(shù)據(jù)以及有關(guān)文檔資料的集合。（可運(yùn)行的）思想和內(nèi)容的數(shù)字化思想：算法、規(guī)律、辦法（程序）內(nèi)容：圖形、圖像、數(shù)據(jù)、聲音、文字等（數(shù)

2、據(jù)）4計(jì)算機(jī)軟件的定義 計(jì)算機(jī)軟件就是指計(jì)算機(jī)程序、實(shí)現(xiàn)此程序功能所采用的方法、規(guī)則以及與其相關(guān)聯(lián)的文檔和在機(jī)器上運(yùn)行它所需要的數(shù)據(jù)。53、硬件與軟件的關(guān)系硬件是計(jì)算機(jī)系統(tǒng)的物質(zhì)基礎(chǔ)；軟件是提高計(jì)算機(jī)系統(tǒng)效率和方便用戶使用計(jì)算機(jī)的程序；它們二者相互依賴、相互促進(jìn)、共同發(fā)展。好的軟件能充分發(fā)揮硬件的性能，提升計(jì)算機(jī)的價(jià)值。沒有軟件的硬件是僵尸，沒有硬件的軟件是幽靈。 各類軟件技術(shù)的最終目的就是設(shè)計(jì)出好的軟件，以便最大限度地合理利用和發(fā)揮硬件的能力，使計(jì)算機(jī)系統(tǒng)更好地為用戶服務(wù)。61.2 程序設(shè)計(jì)語言程序:是使計(jì)算機(jī)完成某種任務(wù)的一個(gè)有序的命令（指令語句）和數(shù)據(jù)的集合。 程序設(shè)計(jì)語言發(fā)展的三個(gè)階段

3、：機(jī)器語言匯編語言高級(jí)語言寫程序就像寫文章，要解決兩個(gè)問題：1.明確自己要表達(dá)的是什么2.用一種語言把它表達(dá)出來程序設(shè)計(jì)語言是編寫計(jì)算機(jī)程序所用的語言。7機(jī)器語言 是機(jī)器指令的集合，其代碼由0、1組成的二進(jìn)制串表示，不需翻譯可直接為機(jī)器所接受。 匯編語言 為符號(hào)化的機(jī)器語言。它用助記符和標(biāo)識(shí)符代替機(jī)器指令的操作碼和地址碼。面向機(jī)器的語言。高級(jí)語言 是一種與具體的計(jì)算機(jī)指令系統(tǒng)無關(guān)，獨(dú)立于計(jì)算機(jī)類型，而且表達(dá)方式接近于自然語言或數(shù)學(xué)語言，容易被人們掌握和書寫的語言。如C，Pascal，java。 面向問題的語言。8語言處理程序翻譯程序 是把甲種語言程序翻譯為等價(jià)的乙種語言程序的程序。其中，甲種語

4、言稱為源語言。乙種語言稱為目標(biāo)語言。匯編程序 若源語言是匯編語言，目標(biāo)語言是機(jī)器語言，則該翻譯程序被稱為匯編程序。編譯程序 若源語言是高級(jí)語言，目標(biāo)語言是匯編語言或機(jī)器語言，則該翻譯程序被稱為編譯程序。解釋程序 是翻譯程序的另一種形式，它對(duì)源程序的語句邊解釋邊執(zhí)行，不產(chǎn)生目標(biāo)程序。91.3 操作系統(tǒng)沒有安裝任何軟件的計(jì)算機(jī)稱為裸機(jī)。操作系統(tǒng)是直接運(yùn)行于裸機(jī)之上的系統(tǒng)軟件，它負(fù)責(zé)對(duì)計(jì)算機(jī)系統(tǒng)的各種軟硬件資源進(jìn)行管理和分配，為用戶提供友好的計(jì)算機(jī)使用界面和平臺(tái)。在裸機(jī)上配置操作系統(tǒng)之后就構(gòu)成了操作系統(tǒng)虛擬機(jī)。所有其它的程序都在擴(kuò)充后的機(jī)器上運(yùn)行。10應(yīng)用程序用戶程序操作系統(tǒng)虛擬機(jī)操作系統(tǒng)裸 機(jī)11

5、軟件的分類所有的硬件都是相似的，軟件則各有各的不同。但是軟件的開發(fā)過程存在很多規(guī)律和共性，找到并利用這些規(guī)律來幫助和指導(dǎo)軟件的開發(fā)，這正是各類軟件技術(shù)研究的內(nèi)容。操作系統(tǒng) 、語言編譯器、數(shù)據(jù)庫管理系統(tǒng)財(cái)務(wù)軟件、文字處理軟件、用戶自己開發(fā)的系統(tǒng)等硬 件系統(tǒng)軟件應(yīng)用軟件用 戶12第二章 數(shù)據(jù)結(jié)構(gòu)程序中往往要處理大量的數(shù)據(jù)，這些數(shù)據(jù)采用什么樣的方式來組織、存放才能最大限度地方便應(yīng)用處理，提高程序效率？數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的組織形式，包括數(shù)據(jù)的邏輯結(jié)構(gòu)，物理結(jié)構(gòu)以及在該數(shù)據(jù)結(jié)構(gòu)上所施加的運(yùn)算。一類數(shù)據(jù)結(jié)構(gòu)指的是一類數(shù)學(xué)模型。數(shù)據(jù)結(jié)構(gòu)是軟件技術(shù)的基礎(chǔ)。132.1 數(shù)據(jù)結(jié)構(gòu)的基本概念1、基本概念的識(shí)記與領(lǐng)會(huì)數(shù)

6、據(jù)：是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中被計(jì)算機(jī)程序加工處理的信息的集合。數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位。是數(shù)據(jù)集合中的個(gè)體。（一個(gè)數(shù)據(jù)項(xiàng)或多個(gè)數(shù)據(jù)項(xiàng)（域）構(gòu)成）在程序處理中作為一個(gè)整體考慮，也稱為結(jié)點(diǎn)、記錄。數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。數(shù)據(jù)結(jié)構(gòu)：是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。描述數(shù)據(jù)元素之間存在的相互關(guān)系的方法稱為結(jié)構(gòu)。 14一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個(gè)數(shù)據(jù)元素之間存在有某種關(guān)系（即聯(lián)系），這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。在數(shù)據(jù)處理領(lǐng)域中，通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡單地用前后繼關(guān)系（或直接前趨與直接后繼關(guān)系）來描述。15（1

7、）數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。即從邏輯結(jié)構(gòu)上描述數(shù)據(jù)，獨(dú)立于計(jì)算機(jī)。如P9表2-1兩大類 線性結(jié)構(gòu)：一對(duì)一關(guān)系。重點(diǎn)：線性表 非線性結(jié)構(gòu)：多對(duì)多關(guān)系。重點(diǎn)：樹結(jié)構(gòu) 16（2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。由于數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)系可能與邏輯關(guān)系不同，因此，為了表示存放在計(jì)算機(jī)存儲(chǔ)空間中的各數(shù)據(jù)元素之間的邏輯關(guān)系（即前后繼關(guān)系），在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后繼關(guān)系的信息。一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)

8、構(gòu)，常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈?zhǔn)?、索引等存?chǔ)結(jié)構(gòu)。采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在進(jìn)行數(shù)據(jù)處理時(shí)，選擇合適的存儲(chǔ)結(jié)構(gòu)是很重要的。17線性表的結(jié)構(gòu)及運(yùn)算1、 線性表概念線性表（line list）是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表是怎樣一種邏輯結(jié)構(gòu) 線性表是由n(n 0)個(gè)數(shù)據(jù)元素a1, a2, a3, 組成的一個(gè)有限序列，表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件，除了最后一個(gè)外，有且只有一個(gè)后繼。即線性表或是一個(gè)空表，或可以表示為(a1, a2, ai, an)，其中ai(i = 1, 2, , n)是屬于數(shù)據(jù)對(duì)象的元素，通常也稱其為線性表中的一個(gè)結(jié)點(diǎn)。顯然

9、，線性表是一種線性結(jié)構(gòu)。數(shù)據(jù)元素在線性表中的位置只取決于它們自己的序號(hào)，即數(shù)據(jù)元素之間的相對(duì)位置是線性的。182、線性表的順序存儲(chǔ) 線性表按順序存儲(chǔ)稱為順序表。順序存儲(chǔ)特點(diǎn)：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。 在線性表的順序存儲(chǔ)結(jié)構(gòu)中，如果線性表中各數(shù)據(jù)元素所占的存儲(chǔ)空間（字節(jié)數(shù)）相等，線性表中查找某一個(gè)元素是很方便的。 假設(shè)線性表中的第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為ADR，一個(gè)數(shù)據(jù)元素占k個(gè)字節(jié)，則線性表中第i個(gè)元素在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址為： ADR +(i1)k 即：存儲(chǔ)地址由該元素在線性表中的位置序號(hào)唯一確定。因此，

10、順序存儲(chǔ)適宜隨機(jī)存取。193、順序表上的運(yùn)算主要的運(yùn)算有以下幾種：1）順序表中插入運(yùn)算 在長度為n的線性表中插入一個(gè)結(jié)點(diǎn)x，其插入過程如下： 首先從最后一個(gè)元素開始直到第i個(gè)元素，將其中的每一個(gè)元素均依次往后移動(dòng)一個(gè)位置，然后將新元素x插入到第i個(gè)位置。插入一個(gè)新元素后，線性表的長度變成了n+1，202）順序表刪除運(yùn)算 一個(gè)長度為n的線性表順序存儲(chǔ)在長度為maxsize的存儲(chǔ)空間中?，F(xiàn)在要求刪除線性表中的第i個(gè)元素。其刪除過程如下： 從第i個(gè)元素開始直到最后一個(gè)元素，將其中的每一個(gè)元素均依次往前移動(dòng)一個(gè)位置。此時(shí)，線性表的長度變成了n1，214、線性表的鏈?zhǔn)酱鎯?chǔ) 在一般情況下，要在順序存儲(chǔ)的線

11、性表中插入一個(gè)新元素或刪除一個(gè)元素時(shí)，為了保證插入或刪除后的線性表仍然為順序存儲(chǔ)，則在插入或刪除過程中需要移動(dòng)大量的數(shù)據(jù)元素。在平均情況下，為了在順序存儲(chǔ)的線性表中插入或刪除一個(gè)元素，需要移動(dòng)線性表中約一半的元素；在最壞情況下，則需要移動(dòng)線性表中所有的元素。因此，對(duì)于大的線性表，特別是元素的插入或刪除很頻繁的情況下，采用順序存儲(chǔ)結(jié)構(gòu)是很不方便的，插入與刪除運(yùn)算的效率都很低。 22鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)： 存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。即把邏輯上相連的元素用指針連接。線性表的鏈?zhǔn)酱鎯?chǔ)稱為鏈表。有單鏈

12、表、雙鏈表、循環(huán)鏈表。（1）鏈表的存儲(chǔ) 在線性鏈表中，各數(shù)據(jù)元素之間的前后繼關(guān)系是由各結(jié)點(diǎn)的指針域來指示的，指向線性表中第一個(gè)結(jié)點(diǎn)的指針head稱為頭指針，當(dāng)head = NULL（或0）時(shí)稱為空表。對(duì)于線性鏈表，可以從頭指針開始，沿各結(jié)點(diǎn)的指針掃描到鏈表中的所有結(jié)點(diǎn)。23單鏈表。每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，由這個(gè)指針只能找到后繼結(jié)點(diǎn)，但不能找到前趨結(jié)點(diǎn)。雙向鏈表。每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱為左指針（Llink），用以指向其前趨結(jié)點(diǎn)；另一個(gè)稱為右指針（Rlink），用以指向其后繼結(jié)點(diǎn)。24鏈表運(yùn)算 1）單鏈表的插入線性鏈表的插入是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中插入一個(gè)新元素。為了要在線性鏈表中插入

13、一個(gè)新元素，首先要給該元素分配一個(gè)新結(jié)點(diǎn)，以便用于存儲(chǔ)該元素的值。然后將存放新元素值的結(jié)點(diǎn)鏈接到線性鏈表中指定的位置。在p指針后插入新結(jié)點(diǎn)，其插入過程如圖。線性鏈表在插入過程中不發(fā)生數(shù)據(jù)元素移動(dòng)的現(xiàn)象，只需改變有關(guān)結(jié)點(diǎn)的指針即可， 252）線性鏈表的刪除在線性鏈表中刪除包含元素x的結(jié)點(diǎn)，其刪除過程如下： 在線性鏈表中尋找包含元素x的結(jié)點(diǎn)。 將其直接前趨節(jié)點(diǎn)的指針改為指向其直接后繼結(jié)點(diǎn)。 將結(jié)點(diǎn)r送回存儲(chǔ)池。線性鏈表的刪除運(yùn)算完成。26（3）循環(huán)鏈表在單鏈表中，只有從頭結(jié)點(diǎn)出發(fā)才能找到鏈表中的其他結(jié)點(diǎn)，當(dāng)把最后一個(gè)結(jié)點(diǎn)的鏈域指向頭結(jié)點(diǎn)，構(gòu)成一個(gè)環(huán)，稱為循環(huán)鏈表。在循環(huán)鏈表中，只要指出表中任何一個(gè)

14、結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點(diǎn)，而線性單鏈表做不到這一點(diǎn)。另外，由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，因此，在任何情況下，循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在。 27棧、隊(duì) 列和數(shù)組 1什么是棧 棧是一種特殊的線性表。 棧（stack）是限定在一端進(jìn)行插入與刪除的線性表。在棧中，允許插入與刪除的一端稱為棧頂，而不允許插入與刪除的另一端稱為棧底。棧頂元素總是最后被插入的元素，從而也是最先能被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。即棧是按照“先進(jìn)后出”的原則組織數(shù)據(jù)的。 282棧的順序存儲(chǔ)及其運(yùn)算 棧的基本運(yùn)算有3種：入棧、退棧與讀棧頂元素。下面分別介紹

15、在順序存儲(chǔ)結(jié)構(gòu)下棧的這3種運(yùn)算。 (a) 有6個(gè)元素的棧 (b) 插入X和Y后的棧 (c) 退出一個(gè)元素的棧1）入棧運(yùn)算 入棧運(yùn)算是指在棧頂位置插入一個(gè)新元素。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將棧頂指針進(jìn)1（即top+1），然后將新元素插入到棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲(chǔ)空間的最后一個(gè)位置時(shí)，說明?？臻g已滿，不可能再進(jìn)行入棧操作。這種情況稱為棧“上溢”錯(cuò)誤。292）退棧運(yùn)算 退棧運(yùn)算是指取出棧頂元素并賦給一個(gè)指定的變量。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將棧頂元素（棧頂指針指向的元素）賦給一個(gè)指定的變量，然后將棧頂指針退1（即 top1）。當(dāng)棧頂指針為0時(shí)，說明?？?，不可能進(jìn)行退棧操作。這種

16、情況稱為棧“下溢”錯(cuò)誤。303、隊(duì)列 隊(duì)列（queue）是指允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊(duì)尾，通常用一個(gè)稱為尾指針（rear）的指針指向隊(duì)尾元素，即尾指針總是指向最后被插入的元素；允許刪除的一端稱為隊(duì)頭。顯然，在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將最先能夠被刪除，反之，最后插入的元素將最后才能被刪除。因此，隊(duì)列又稱為“先進(jìn)先出”（first in first out，F(xiàn)IFO）的線性表，它體現(xiàn)了“先來先服務(wù)”的原則。在隊(duì)列中，隊(duì)尾指針rear與排頭指針front共同反映了隊(duì)列中元素動(dòng)態(tài)變化的情況。 6個(gè)元素的隊(duì)列示意圖31在隊(duì)列的末尾插入一個(gè)元素（入隊(duì)運(yùn)算

17、）只涉及隊(duì)尾指針rear的變化，而要?jiǎng)h除隊(duì)列中的排頭元素（退隊(duì)運(yùn)算）只涉及排頭指針front的變化。（a）一個(gè)隊(duì)列 （b）刪除一個(gè)元素后的隊(duì)列 （c）插入一個(gè)元素后的隊(duì)列324循環(huán)隊(duì)列及其運(yùn)算 所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，隊(duì)列循環(huán)使用，如圖所示。 在循環(huán)隊(duì)列結(jié)構(gòu)中，當(dāng)存儲(chǔ)空間的最后一個(gè)位置已被使用而再要進(jìn)行入隊(duì)運(yùn)算時(shí)，只要存儲(chǔ)空間的第一個(gè)位置空閑，便可將元素加入到第一個(gè)位置，即將存儲(chǔ)空間的第一個(gè)位置作為隊(duì)尾。33循環(huán)隊(duì)列的初始狀態(tài)為空，即rear=front=m循環(huán)隊(duì)列主要有兩種基本運(yùn)算：入隊(duì)運(yùn)算和退隊(duì)運(yùn)算。 1）入隊(duì)運(yùn)算 入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)

18、新元素。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將隊(duì)尾指針加1（即rear + 1），然后將新元素插入到隊(duì)尾指針指向的位置。當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于排頭指針時(shí)，說明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算，該情況稱為“上溢”。 2）退隊(duì)運(yùn)算 退隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的排頭位置退出一個(gè)元素并賦給指定的變量。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將隊(duì)頭指針進(jìn)一（即front = front + 1）；然后將排頭指針指向的元素賦給指定的變量。當(dāng)循環(huán)隊(duì)列為空時(shí)，不能進(jìn)行退隊(duì)運(yùn)算，這種情況稱為“下溢”。34 (a) 循環(huán)隊(duì)列 (b) 加入X、Y的循環(huán)隊(duì)列 (c) 退出一個(gè)元素的循環(huán)隊(duì)列355、數(shù)組數(shù)組一般用順序存儲(chǔ)的方式表示。存儲(chǔ)的方式有： 行優(yōu)先順序，也就是把數(shù)組逐行依次排列。列優(yōu)先順序，就是把數(shù)組逐列依次排列。地址的計(jì)算方法： 按行優(yōu)先順序