軟件基礎(chǔ)串講一

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

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

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

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

5、軟件的分類所有的硬件都是相似的，軟件則各有各的不同。但是軟件的開發(fā)過程存在很多規(guī)律和共性，找到并利用這些規(guī)律來幫助和指導(dǎo)軟件的開發(fā)，這正是各類軟件技術(shù)研究的內(nèi)容。操作系統(tǒng) 、語言編譯器、數(shù)據(jù)庫管理系統(tǒng)財務(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)上所施加的運算。一類數(shù)據(jù)結(jié)構(gòu)指的是一類數(shù)學(xué)模型。數(shù)據(jù)結(jié)構(gòu)是軟件技術(shù)的基礎(chǔ)。132.1 數(shù)據(jù)結(jié)構(gòu)的基本概念1、基本概念的識記與領(lǐng)會數(shù)

6、據(jù)：是描述客觀事物的數(shù)、字符以及所有能輸入到計算機中被計算機程序加工處理的信息的集合。數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位。是數(shù)據(jù)集合中的個體。（一個數(shù)據(jù)項或多個數(shù)據(jù)項（域）構(gòu)成）在程序處理中作為一個整體考慮，也稱為結(jié)點、記錄。數(shù)據(jù)項：數(shù)據(jù)項是數(shù)據(jù)的最小單位。數(shù)據(jù)結(jié)構(gòu)：是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。描述數(shù)據(jù)元素之間存在的相互關(guān)系的方法稱為結(jié)構(gòu)。 14一般情況下，在具有相同特征的數(shù)據(jù)元素集合中，各個數(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ù)，獨立于計算機。如P9表2-1兩大類 線性結(jié)構(gòu)：一對一關(guān)系。重點：線性表 非線性結(jié)構(gòu)：多對多關(guān)系。重點：樹結(jié)構(gòu) 16（2）數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。由于數(shù)據(jù)元素在計算機存儲空間中的位置關(guān)系可能與邏輯關(guān)系不同，因此，為了表示存放在計算機存儲空間中的各數(shù)據(jù)元素之間的邏輯關(guān)系（即前后繼關(guān)系），在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后繼關(guān)系的信息。一般來說，一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)

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

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

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

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

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

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

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

15、在順序存儲結(jié)構(gòu)下棧的這3種運算。 (a) 有6個元素的棧 (b) 插入X和Y后的棧 (c) 退出一個元素的棧1）入棧運算 入棧運算是指在棧頂位置插入一個新元素。這個運算有兩個基本操作：首先將棧頂指針進1（即top+1），然后將新元素插入到棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲空間的最后一個位置時，說明?？臻g已滿，不可能再進行入棧操作。這種情況稱為?！吧弦纭卞e誤。292）退棧運算 退棧運算是指取出棧頂元素并賦給一個指定的變量。這個運算有兩個基本操作：首先將棧頂元素（棧頂指針指向的元素）賦給一個指定的變量，然后將棧頂指針退1（即 top1）。當(dāng)棧頂指針為0時，說明?？眨豢赡苓M行退棧操作。這種

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

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

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