2017計算機應用基礎知識

　　1.1數據結構與算法

　　借助于計算機解決問(wèn)題，首先需要了解所處理對象的性質(zhì)和特點(diǎn)即所操作對象的數據結構，然后再設計解決問(wèn)題的方法和步驟即設計一個(gè)合理的算法，即通常所說(shuō)的“程序=數據結構+算法”。

　　1.1.1算法的基本概念

　　“算法”（Algorithm）一詞最早來(lái)自公元9世紀波斯數學(xué)家比阿勒·霍瓦里松的一本影響深遠的著(zhù)作《代數對話(huà)錄》。20世紀的英國數學(xué)家圖靈提出了著(zhù)名的圖靈論點(diǎn)，并抽象出了一臺機器，這臺機器被我們稱(chēng)之為圖靈機。圖靈的思想對算法的發(fā)展起到了重要的作用。一般來(lái)說(shuō)，算法是指完成一個(gè)任務(wù)或解決一個(gè)問(wèn)題所需要的具體步驟和方法的描述。在這里我們說(shuō)的算法是指計算機能執行的算法。

　　1.算法分類(lèi)

　　計算機算法可分為兩大類(lèi)，一類(lèi)是數值運算算法，另一類(lèi)是非數值運算算法。數值運算算法主要是求數值解，如求方程的解、求函數的定積分等，非數值運算的范圍則非常廣泛，如人事管理、圖書(shū)檢索等。

　　2.算法特征

　　一個(gè)科學(xué)的算法必須具備以下特征：

　　(1)有窮性：一個(gè)算法必須保證執行有限步之后結束，而不能是無(wú)限的。這是顯而易見(jiàn)的。更進(jìn)一步說(shuō)，有窮性是指在合理的范圍內結束運算，如果一個(gè)算法需計算機執行幾百年或更長(cháng)時(shí)間才結束，這顯然是不合理的。

　　(2)確定性：算法的每一步驟必須有確切的定義而不能模棱兩可，算法中不能出現諸如“一個(gè)比較大的數”等模糊描述。

　　(3)有零個(gè)或多個(gè)輸入

　　(4)有一個(gè)或多個(gè)輸出。算法的目的是為了解決問(wèn)題,一個(gè)沒(méi)有輸出的算法是不能解決任何問(wèn)題因而它是沒(méi)有意義的.

　　(5)有效性。算法中的每一個(gè)步驟都都應當能有效地執行，并得到確定的結果。例如，若n=0則執行m/n是無(wú)法有效執行的。

　　3.算法表示

　　一個(gè)計算機算法可以用自然語(yǔ)言、流程圖、N-S圖等來(lái)表示。

　　4.算法分析

　　算法分析的任務(wù)是對設計出的每一個(gè)具體的算法，利用數學(xué)工具，討論各種復雜度，以探討某種具體算法適用于哪類(lèi)問(wèn)題，或某類(lèi)問(wèn)題宜采用哪種算法。

　　算法的復雜度分時(shí)間復雜度和空間復雜度。

　�。畷r(shí)間復雜度：在運行算法時(shí)所耗費的時(shí)間為f(n)(即 n的函數)。

　�。�空間復雜度：實(shí)現算法所占用的空間為g(n)（也為n的函數）。

　　稱(chēng)O(f(n))和O(g(n))為該算法的復雜度。

　　1.1.2 數據結構的定義

　　數據結構是計算機科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語(yǔ)。盡管它至今還未有一個(gè)被一致公認的定義，但其內容是大家一致公認的。它用來(lái)反映一個(gè)數據的內部構成，即一個(gè)數據由那些成分數據構成，以什么方式構成，呈什么結構。數據結構有邏輯上的數據結構和物理上的數據結構之分。邏輯上的數據結構反映成分數據之間的邏輯關(guān)系，而物理上的數據結構反映成分數據在計算機內部的存儲安排。數據結構是數據存在的形式。

　　數據結構是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組算法的集合相對應，通過(guò)這組算法集合可以對數據結構中的數據進(jìn)行某種操作。

　　一般數據結構可采用下面兩類(lèi)主要的存儲方式，大多數數據結構的存儲表示都采用其中的一類(lèi)方式，或兩類(lèi)方式的結合。

　　1. 順序存儲結構

　　這種存儲方式的主要用于線(xiàn)性數據結構，它把邏輯上相鄰的數據元素存儲在物理上相鄰的存儲單元內，結點(diǎn)之間的關(guān)系由存儲單元的鄰接關(guān)系來(lái)實(shí)現。

　　順序存儲結構的主要特點(diǎn)是：（1）結點(diǎn)中只有自身信息域，沒(méi)有連接信息域，因此存儲密度大，存儲空間利用率高；（2）可以通過(guò)計算直接確定數據結構中第i個(gè)結點(diǎn)的存儲地址Li，計算公式為L(cháng)i=L0+(i-1)*m，其中L0為第一個(gè)結點(diǎn)的存儲地址，m為每個(gè)結點(diǎn)所占用的存儲單元個(gè)數；（3）插入、刪除運算不便，會(huì )引起大量結點(diǎn)的移動(dòng)。

　　2. 鏈式存儲結構

　　鏈式存儲結構就是在每個(gè)結點(diǎn)中至少包括一個(gè)指針域，用指針來(lái)體現數據元素之間邏輯上的聯(lián)系。這種存儲結構可把邏輯上相鄰的兩個(gè)元素存放在物理上不相鄰的存儲單元中；還可以在線(xiàn)性編址的計算機存儲器中表示結點(diǎn)之間的非線(xiàn)性聯(lián)系。

　　鏈式存儲結構的主要特點(diǎn)是：（1）結點(diǎn)中除自身外，還有表示連接信息的指針域，因此比順序結構的存儲密度小，存儲空間利用率低；（2）邏輯上相鄰的結點(diǎn)物理上不必鄰接，可用于線(xiàn)性表、樹(shù)、圖等多種邏輯結構的存儲表示；（3）插入、刪除操作靈活方便，不必移動(dòng)結點(diǎn)，只要改變結點(diǎn)中的指針即可。

　　除上述兩種主要存儲方式外，散列法也是在線(xiàn)性表和集合的存儲表示中常用的一種存儲方式。

　　1.1.3 線(xiàn)性表結構

　　1.線(xiàn)性表的定義

　　線(xiàn)性表（Linear List）是最常用并且最簡(jiǎn)單的一種數據結構。它是由n（n≥0）個(gè)數據元素（結點(diǎn)）a1，a2，…，an組成的有限序列。

　�、� 數據元素的個(gè)數n定義為表的長(cháng)度（n=0時(shí)稱(chēng)為空表）。

　�、� 將非空的線(xiàn)性表（n＞0）記作：（a1，a2，…，an）

　�、� 數據元素ai（1≤i≤n）只是個(gè)抽象符號，其具體含義在不同情況下可以不同。

　　在一些比較復雜的線(xiàn)性表中，一個(gè)數據元素可以由若干個(gè)數據項組成。在這種情況下，一般把數據元素稱(chēng)為記錄，含有大量記錄的線(xiàn)性表也稱(chēng)為文件。

　　例1英文字母表（A，B，…，Z）是線(xiàn)性表，表中每個(gè)字母是一個(gè)數據元素（結點(diǎn)） 例2一副撲克牌的點(diǎn)數（2，3，…，10，J，Q，K，A）也是一個(gè)線(xiàn)性表，其中數據元素是每張牌的點(diǎn)數

　　2.線(xiàn)性表的存儲

　　線(xiàn)性表可采用順序方式存儲和鏈式方式存儲。在各種高級語(yǔ)言中的一維數組就是用順序方式存儲的線(xiàn)性表，因此也常用一維數組來(lái)稱(chēng)呼順序表。下面主要討論的線(xiàn)性表對象是指順序表。

　　3.線(xiàn)性表的基本操作

　　線(xiàn)性表是一種相當靈活的數據結構，不僅對它的數據元素可以查找訪(fǎng)問(wèn)，它的長(cháng)度也可以根據需要增大或縮小，即可對線(xiàn)性表進(jìn)行插入和刪除數據元素運算。

　　常見(jiàn)的線(xiàn)性表的基本運算

　　(1) InitList（L）

　　構造一個(gè)空的線(xiàn)性表L，即表的初始化。

　　(2) ListLength（L）

　　求線(xiàn)性表L中的結點(diǎn)個(gè)數，即求表長(cháng)。

　　(3) GetNode（L，i）

　　取線(xiàn)性表L中的第i個(gè)結點(diǎn)，這里要求1≤i≤ListLength（L）

　　(4) LocateNode（L，x）

　　在L中查找值為x 的結點(diǎn)，并返回該結點(diǎn)在L中的位置。若L中有多個(gè)結點(diǎn)的值和x 相同，則返回首次找到的結點(diǎn)位置；若L中沒(méi)有結點(diǎn)的值為x ，則返回一個(gè)特殊值表示查找失敗。

　　(5) InsertList（L，x，i）

　　在線(xiàn)性表L的第i個(gè)位置上插入一個(gè)值為x 的新結點(diǎn)，使得原編號為i，i+1，…，n的結點(diǎn)變?yōu)榫幪枮閕+1，i+2，…，n+1的結點(diǎn)。這里1≤i≤n+1，而n是原表L的長(cháng)度。插入后，表L的長(cháng)度加1。

　　(6) DeleteList（L，i）

　　刪除線(xiàn)性表L的第i個(gè)結點(diǎn)，使得原編號為i+1，i+2，…，n的結點(diǎn)變成編號為i，i+1，…，n-1的結點(diǎn)。這里1≤i≤n，而n是原表L的長(cháng)度。刪除后表L的長(cháng)度減1。具體程序實(shí)現可參考本書(shū)C語(yǔ)言相關(guān)章節。

　　1.1.4棧與隊列結構

　　1.棧與隊列的定義

　　棧是一種限定僅在表的一端進(jìn)行插入與刪除操作的線(xiàn)性表。允許進(jìn)行插入與刪除操作的這一端稱(chēng)為棧頂，而另一端稱(chēng)為棧底，不含元素的空表稱(chēng)為空棧，插入與刪除分別稱(chēng)進(jìn)棧與出棧。 由于插入與刪除只能在同一端進(jìn)行，所以較先進(jìn)入棧的元素，在進(jìn)行出棧操作時(shí)，要比較后才能出棧。特別是，最先進(jìn)棧者，最后才能出棧，而最晚進(jìn)棧者，必最先出棧。因此，棧也稱(chēng)作后進(jìn)先出（Last In First Out）的線(xiàn)性表，簡(jiǎn)稱(chēng)LIFO表。

【計算機應用基礎知識】相關(guān)文章：

計算機應用的基礎知識03-20

計算機應用基礎基礎知識09-30

計算機應用基礎知識復習題及答案03-20

全國計算機應用基礎知識：漢字、字符編碼04-01

2017年計算機應用基礎知識訓練題03-21

計算機基礎知識03-05

水泥功能與應用基礎知識06-13

計算機硬盤(pán)基礎知識11-09

服裝號型標準基礎知識與實(shí)際應用03-22