2017計(jì)算機(jī)應(yīng)用基礎(chǔ)知識(shí)
1.1數(shù)據(jù)結(jié)構(gòu)與算法
借助于計(jì)算機(jī)解決問題，首先需要了解所處理對(duì)象的性質(zhì)和特點(diǎn)即所操作對(duì)象的數(shù)據(jù)結(jié)構(gòu)，然后再設(shè)計(jì)解決問題的方法和步驟即設(shè)計(jì)一個(gè)合理的算法，即通常所說的“程序=數(shù)據(jù)結(jié)構(gòu)+算法”。
1.1.1算法的基本概念
“算法”（Algorithm）一詞最早來自公元9世紀(jì)波斯數(shù)學(xué)家比阿勒·霍瓦里松的一本影響深遠(yuǎn)的著作《代數(shù)對(duì)話錄》。20世紀(jì)的英國(guó)數(shù)學(xué)家圖靈提出了著名的圖靈論點(diǎn)，并抽象出了一臺(tái)機(jī)器，這臺(tái)機(jī)器被我們稱之為圖靈機(jī)。圖靈的思想對(duì)算法的發(fā)展起到了重要的作用。一般來說，算法是指完成一個(gè)任務(wù)或解決一個(gè)問題所需要的具體步驟和方法的描述。在這里我們說的算法是指計(jì)算機(jī)能執(zhí)行的算法。
1.算法分類
計(jì)算機(jī)算法可分為兩大類，一類是數(shù)值運(yùn)算算法，另一類是非數(shù)值運(yùn)算算法。數(shù)值運(yùn)算算法主要是求數(shù)值解，如求方程的解、求函數(shù)的定積分等，非數(shù)值運(yùn)算的范圍則非常廣泛，如人事管理、圖書檢索等。
2.算法特征
一個(gè)科學(xué)的算法必須具備以下特征：
(1)有窮性：一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束，而不能是無限的。這是顯而易見的。更進(jìn)一步說，有窮性是指在合理的范圍內(nèi)結(jié)束運(yùn)算，如果一個(gè)算法需計(jì)算機(jī)執(zhí)行幾百年或更長(zhǎng)時(shí)間才結(jié)束，這顯然是不合理的。
(2)確定性：算法的每一步驟必須有確切的定義而不能模棱兩可，算法中不能出現(xiàn)諸如“一個(gè)比較大的數(shù)”等模糊描述。
(3)有零個(gè)或多個(gè)輸入
(4)有一個(gè)或多個(gè)輸出。算法的目的是為了解決問題,一個(gè)沒有輸出的算法是不能解決任何問題因而它是沒有意義的.
(5)有效性。算法中的每一個(gè)步驟都都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。例如，若n=0則執(zhí)行m/n是無法有效執(zhí)行的。
3.算法表示
一個(gè)計(jì)算機(jī)算法可以用自然語言、流程圖、N-S圖等來表示。
4.算法分析
算法分析的任務(wù)是對(duì)設(shè)計(jì)出的每一個(gè)具體的算法，利用數(shù)學(xué)工具，討論各種復(fù)雜度，以探討某種具體算法適用于哪類問題，或某類問題宜采用哪種算法。
算法的復(fù)雜度分時(shí)間復(fù)雜度和空間復(fù)雜度。
．時(shí)間復(fù)雜度：在運(yùn)行算法時(shí)所耗費(fèi)的時(shí)間為f(n)(即 n的函數(shù))。
．空間復(fù)雜度：實(shí)現(xiàn)算法所占用的空間為g(n)（也為n的函數(shù)）。
稱O(f(n))和O(g(n))為該算法的復(fù)雜度。
1.1.2 數(shù)據(jù)結(jié)構(gòu)的定義
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。盡管它至今還未有一個(gè)被一致公認(rèn)的定義，但其內(nèi)容是大家一致公認(rèn)的。它用來反映一個(gè)數(shù)據(jù)的內(nèi)部構(gòu)成，即一個(gè)數(shù)據(jù)由那些成分?jǐn)?shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式。
數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對(duì)應(yīng)，通過這組算法集合可以對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。
一般數(shù)據(jù)結(jié)構(gòu)可采用下面兩類主要的存儲(chǔ)方式，大多數(shù)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)表示都采用其中的一類方式，或兩類方式的結(jié)合。
1. 順序存儲(chǔ)結(jié)構(gòu)
這種存儲(chǔ)方式的主要用于線性數(shù)據(jù)結(jié)構(gòu)，它把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元內(nèi)，結(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來實(shí)現(xiàn)。
順序存儲(chǔ)結(jié)構(gòu)的主要特點(diǎn)是：（1）結(jié)點(diǎn)中只有自身信息域，沒有連接信息域，因此存儲(chǔ)密度大，存儲(chǔ)空間利用率高；（2）可以通過計(jì)算直接確定數(shù)據(jù)結(jié)構(gòu)中第i個(gè)結(jié)點(diǎn)的存儲(chǔ)地址Li，計(jì)算公式為L(zhǎng)i=L0+(i-1)*m，其中L0為第一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址，m為每個(gè)結(jié)點(diǎn)所占用的存儲(chǔ)單元個(gè)數(shù)；（3）插入、刪除運(yùn)算不便，會(huì)引起大量結(jié)點(diǎn)的移動(dòng)。
2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就是在每個(gè)結(jié)點(diǎn)中至少包括一個(gè)指針域，用指針來體現(xiàn)數(shù)據(jù)元素之間邏輯上的聯(lián)系。這種存儲(chǔ)結(jié)構(gòu)可把邏輯上相鄰的兩個(gè)元素存放在物理上不相鄰的存儲(chǔ)單元中；還可以在線性編址的計(jì)算機(jī)存儲(chǔ)器中表示結(jié)點(diǎn)之間的非線性聯(lián)系。
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的主要特點(diǎn)是：（1）結(jié)點(diǎn)中除自身外，還有表示連接信息的指針域，因此比順序結(jié)構(gòu)的存儲(chǔ)密度小，存儲(chǔ)空間利用率低；（2）邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接，可用于線性表、樹、圖等多種邏輯結(jié)構(gòu)的存儲(chǔ)表示；（3）插入、刪除操作靈活方便，不必移動(dòng)結(jié)點(diǎn)，只要改變結(jié)點(diǎn)中的指針即可。
除上述兩種主要存儲(chǔ)方式外，散列法也是在線性表和集合的存儲(chǔ)表示中常用的一種存儲(chǔ)方式。
1.1.3 線性表結(jié)構(gòu)
1.線性表的定義
線性表（Linear List）是最常用并且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。它是由n（n≥0）個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）a1，a2，…，an組成的有限序列。
① 數(shù)據(jù)元素的個(gè)數(shù)n定義為表的長(zhǎng)度（n=0時(shí)稱為空表）。
② 將非空的線性表（n＞0）記作：（a1，a2，…，an）
③ 數(shù)據(jù)元素ai（1≤i≤n）只是個(gè)抽象符號(hào)，其具體含義在不同情況下可以不同。
在一些比較復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。在這種情況下，一般把數(shù)據(jù)元素稱為記錄，含有大量記錄的線性表也稱為文件。
例1英文字母表（A，B，…，Z）是線性表，表中每個(gè)字母是一個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)） 例2一副撲克牌的點(diǎn)數(shù)（2，3，…，10，J，Q，K，A）也是一個(gè)線性表，其中數(shù)據(jù)元素是每張牌的點(diǎn)數(shù)
2.線性表的存儲(chǔ)
線性表可采用順序方式存儲(chǔ)和鏈?zhǔn)椒绞酱鎯?chǔ)。在各種高級(jí)語言中的一維數(shù)組就是用順序方式存儲(chǔ)的線性表，因此也常用一維數(shù)組來稱呼順序表。下面主要討論的線性表對(duì)象是指順序表。
3.線性表的基本操作
線性表是一種相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，不僅對(duì)它的數(shù)據(jù)元素可以查找訪問，它的長(zhǎng)度也可以根據(jù)需要增大或縮小，即可對(duì)線性表進(jìn)行插入和刪除數(shù)據(jù)元素運(yùn)算。
常見的線性表的基本運(yùn)算
(1) InitList（L）
構(gòu)造一個(gè)空的線性表L，即表的初始化。
(2) ListLength（L）
求線性表L中的結(jié)點(diǎn)個(gè)數(shù)，即求表長(zhǎng)。
(3) GetNode（L，i）
取線性表L中的第i個(gè)結(jié)點(diǎn)，這里要求1≤i≤ListLength（L）
(4) LocateNode（L，x）
在L中查找值為x 的結(jié)點(diǎn)，并返回該結(jié)點(diǎn)在L中的位置。若L中有多個(gè)結(jié)點(diǎn)的值和x 相同，則返回首次找到的結(jié)點(diǎn)位置；若L中沒有結(jié)點(diǎn)的值為x ，則返回一個(gè)特殊值表示查找失敗。
(5) InsertList（L，x，i）
在線性表L的第i個(gè)位置上插入一個(gè)值為x 的新結(jié)點(diǎn)，使得原編號(hào)為i，i+1，…，n的結(jié)點(diǎn)變?yōu)榫幪?hào)為i+1，i+2，…，n+1的結(jié)點(diǎn)。這里1≤i≤n+1，而n是原表L的長(zhǎng)度。插入后，表L的長(zhǎng)度加1。
(6) DeleteList（L，i）
刪除線性表L的第i個(gè)結(jié)點(diǎn)，使得原編號(hào)為i+1，i+2，…，n的結(jié)點(diǎn)變成編號(hào)為i，i+1，…，n-1的結(jié)點(diǎn)。這里1≤i≤n，而n是原表L的長(zhǎng)度。刪除后表L的長(zhǎng)度減1。具體程序?qū)崿F(xiàn)可參考本書C語言相關(guān)章節(jié)。
1.1.4棧與隊(duì)列結(jié)構(gòu)
1.棧與隊(duì)列的定義
棧是一種限定僅在表的一端進(jìn)行插入與刪除操作的線性表。允許進(jìn)行插入與刪除操作的這一端稱為棧頂，而另一端稱為棧底，不含元素的空表稱為空棧，插入與刪除分別稱進(jìn)棧與出棧。 由于插入與刪除只能在同一端進(jìn)行，所以較先進(jìn)入棧的元素，在進(jìn)行出棧操作時(shí)，要比較后才能出棧。特別是，最先進(jìn)棧者，最后才能出棧，而最晚進(jìn)棧者，必最先出棧。因此，棧也稱作后進(jìn)先出（Last In First Out）的線性表，簡(jiǎn)稱LIFO表。
【計(jì)算機(jī)應(yīng)用基礎(chǔ)知識(shí)】相關(guān)文章：
計(jì)算機(jī)應(yīng)用的基礎(chǔ)知識(shí)03-20
計(jì)算機(jī)應(yīng)用基礎(chǔ)基礎(chǔ)知識(shí)09-30
計(jì)算機(jī)應(yīng)用基礎(chǔ)知識(shí)復(fù)習(xí)題及答案03-20
全國(guó)計(jì)算機(jī)應(yīng)用基礎(chǔ)知識(shí)：漢字、字符編碼04-01
2017年計(jì)算機(jī)應(yīng)用基礎(chǔ)知識(shí)訓(xùn)練題03-21
計(jì)算機(jī)基礎(chǔ)知識(shí)03-05
水泥功能與應(yīng)用基礎(chǔ)知識(shí)06-13