【正文】 線(xiàn)性表； ? 線(xiàn)性表中的元素可以是多個(gè)，但不能是無(wú)窮多個(gè)； ? 同一個(gè)線(xiàn)性表中元素的類(lèi)型相同，因此元素長(zhǎng)度也相同。 ? 教學(xué)目標(biāo)： 通過(guò)本章的學(xué)習(xí)，使讀者能掌握線(xiàn)性表的概念、有關(guān)術(shù)語(yǔ)、存儲(chǔ)方式、相關(guān)運(yùn)算和算法，并能靈活應(yīng)用。 A? Thanks! 第 2章 線(xiàn) 性 表 （時(shí)間： 2次課， 4學(xué)時(shí)） 第 2章 線(xiàn) 性 表 ? 教學(xué)提示： 本章介紹的線(xiàn)性表結(jié)構(gòu)是最基本的數(shù)據(jù)結(jié)構(gòu)，也是學(xué)習(xí)后邊章節(jié)重要的基礎(chǔ)。 (9) 通常從哪幾個(gè)方面評(píng)價(jià)算法的質(zhì)量？ (10) 算法的時(shí)間復(fù)雜度主要有那幾種？按從優(yōu)到劣的順序?qū)懗龈鞣N表示形式。 (6) 什么是邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)？有哪幾種存儲(chǔ)結(jié)構(gòu)？ (7) 簡(jiǎn)述順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在表示數(shù)據(jù)元素之間關(guān)系上的主要區(qū)別。 (4) 畫(huà)出樹(shù)形結(jié)構(gòu)的示意圖。 (2) 說(shuō)出數(shù)據(jù)結(jié)構(gòu)中的四類(lèi)基本邏輯結(jié)構(gòu)，并說(shuō)明哪種關(guān)系最簡(jiǎn)單、哪種關(guān)系最復(fù)雜。 A. 結(jié)點(diǎn) B. 數(shù)據(jù)項(xiàng) C. 數(shù)據(jù)字段 D. 字符串 (15) 記錄中的各個(gè)數(shù)據(jù)項(xiàng)的類(lèi)型 _____________。 i++ ) c[i][i]=i+i 。 for(i=0。 j++ ) c[i][j]=i+j。 i++ ) for(j=0。 for(i=0。 A. O(1) B. O(n) C. O(log2n) D. O(n2) (11) 下列時(shí)間復(fù)雜度中最好的是 _____________。 A. 可以直接在計(jì)算機(jī)上運(yùn)行 B. 可以描述解題思想和基本框架 C. 不能改寫(xiě)成 C語(yǔ)言程序 D. 與 C語(yǔ)言無(wú)關(guān) (9) 算法能正確 地 實(shí)現(xiàn)預(yù)定功能的特性稱(chēng)為 _____________。 A. 集合 B. 線(xiàn)性結(jié)構(gòu) C. 樹(shù)形結(jié)構(gòu) D. 圖狀結(jié)構(gòu) 習(xí) 題 __選擇題 (7) 一個(gè)存儲(chǔ)結(jié)點(diǎn)存放一個(gè) _____________。 A. 數(shù)據(jù)元素之間邏輯 B. 數(shù)據(jù)項(xiàng)之間邏輯 C. 數(shù)據(jù)類(lèi)型之間 D. 存儲(chǔ)結(jié)構(gòu)之間 (5) 數(shù)據(jù)結(jié)構(gòu)有 _____________種基本邏輯結(jié)構(gòu)。 A. 只能包括一個(gè) B. 不包含 C. 可以包含多個(gè) D. 必須包含多個(gè) (3) 邏輯關(guān)系是指數(shù)據(jù)元素間的 _____________。 習(xí) 題 __選擇題 (1) 數(shù)據(jù)表示是指數(shù)據(jù) _____________。 (4) 從數(shù)據(jù)結(jié)構(gòu) S中撤消結(jié)構(gòu)中指定位置上結(jié)點(diǎn)的運(yùn)算是 _____________型運(yùn)算。 (2) 從數(shù)據(jù)結(jié)構(gòu) S中讀出結(jié)構(gòu)中指定位置上內(nèi)容運(yùn)算是 _____________型運(yùn)算。 j=n。 k=n。 k=n。 s=x+2。從好到壞表示時(shí)間復(fù)雜度的函數(shù)依次是：常量階 O(1)；對(duì)數(shù)階 O(log n)；線(xiàn)性階 O(n)；平方階 O(n2)；多項(xiàng)式階 O(nk)；指數(shù)階 O(2n)等。一個(gè)算法所解決問(wèn)題的規(guī)模 n增大時(shí)，時(shí)間的增長(zhǎng)率越小，時(shí)間復(fù)雜度越好，反之時(shí)間復(fù)雜度越壞。簡(jiǎn)單地說(shuō)，一個(gè)算法所進(jìn)行的計(jì)算次數(shù)的多少稱(chēng)為 時(shí)間復(fù)雜度 ，一個(gè)算法所需要輔助存儲(chǔ)空間的多少稱(chēng)為 空間復(fù)雜度 。解決一個(gè)問(wèn)題的算法如果使用時(shí)間少和占用空間少 ， 則是算法高效率的體現(xiàn) 。 健壯性： 當(dāng)輸入非法數(shù)據(jù)時(shí) ， 算法也能做出特殊處理 ，不會(huì)繼續(xù)操作或死機(jī) 。 算法分析和算法復(fù)雜度 通常用以下幾個(gè)標(biāo)準(zhǔn)來(lái)評(píng)價(jià)其優(yōu)劣： 正確性： 算法必須能正確解決問(wèn)題 。 輸 入： 一個(gè)算法可以有零個(gè)或多個(gè)輸入 。 確定性： 算法中每一步操作的含義都必須是確定的 ， 不能有二義性 。 算法 是描述操作步驟的有限序列 。 算法及其描述 定義： 算法 是計(jì)算機(jī)科學(xué)的一個(gè)概念 ， 也是程序設(shè)計(jì)的一個(gè)重要概念 。 更新運(yùn)算： 屬于加工型運(yùn)算，更換結(jié)構(gòu)中某個(gè)數(shù)據(jù)元素的內(nèi)容。 查找運(yùn)算： 屬于引用型運(yùn)算，從結(jié)構(gòu)中找出滿(mǎn)足條件的數(shù)據(jù)元素的位置。 運(yùn)算 基本運(yùn)算主要包括下列幾種： 插入運(yùn)算： 屬于加工型運(yùn)算，在原結(jié)構(gòu)的指定位置上增添新的數(shù)據(jù)元素。 運(yùn)算、算法和算法分析 ? 運(yùn)算 ? 算法及其描述 ? 算法分析和算法復(fù)雜度 運(yùn)算 運(yùn)算可以分為下列兩種基本類(lèi)型： (1) 加工型運(yùn)算： 運(yùn)算后改變了原結(jié)構(gòu)中數(shù)據(jù)元素的個(gè)數(shù)或數(shù)據(jù)元素的內(nèi)容 。 ? 在計(jì)算機(jī)中 ， 數(shù)據(jù)類(lèi)型并非局限于高級(jí)語(yǔ)言中的一個(gè)具體類(lèi)型 ， 而是通常用 抽象數(shù)據(jù)類(lèi)型 表示類(lèi)型 。結(jié)構(gòu)類(lèi)型是由若干類(lèi)型組成的 ， 是可以分解的 。原子類(lèi)型的值是不可分解的 。 ? 在高級(jí)語(yǔ)言的指針類(lèi)型中 ， 不是針對(duì)計(jì)算機(jī)的實(shí)際地址進(jìn)行存儲(chǔ) ， 稱(chēng)這種存儲(chǔ)為數(shù)據(jù)結(jié)構(gòu)的 虛擬存儲(chǔ)結(jié)構(gòu) 。 ? 當(dāng)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成時(shí) ， 位串中對(duì)應(yīng)于各個(gè)數(shù)據(jù)項(xiàng)的子位串稱(chēng)為 數(shù)據(jù)字段 。 ? 在計(jì)算機(jī)中表示信息的最小單位是一個(gè)二進(jìn)制位 ， 叫做 bit位 。 存儲(chǔ)結(jié)構(gòu)是指在計(jì)算機(jī)中存儲(chǔ)數(shù)據(jù)和邏輯結(jié)構(gòu) 。 ? 圖結(jié)構(gòu)： 這個(gè)結(jié)構(gòu)中數(shù)據(jù)元素之間相互連接成網(wǎng)狀 。 ? 線(xiàn)性結(jié)構(gòu)： 這個(gè)結(jié)構(gòu)中數(shù)據(jù)元素存在著由依次排列的先后次序決定的關(guān)系 。 邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的關(guān)系 。 由于客觀事物存在著各種不同的聯(lián)系形式 ，因此在計(jì)算機(jī)內(nèi)反映數(shù)據(jù)的關(guān)系時(shí) ， 可以用結(jié)構(gòu)來(lái)描述這些關(guān)系 。 這些關(guān)系反映了客觀世界事物之間的聯(lián)系 。例如 ， 一本書(shū)的書(shū)目信息為一個(gè)數(shù)據(jù)元素 ， 而書(shū)目信息中的每一項(xiàng) (如書(shū)名 、 作者名 )是數(shù)據(jù)項(xiàng) 。 在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理 。 基本概念和術(shù)語(yǔ) ? 數(shù)據(jù)元素： 數(shù)據(jù)元素是數(shù)據(jù)的基本單位 。 例如 ， 一個(gè)用某種程序語(yǔ)言編寫(xiě)的源程序 、 一篇文章 、 一張地圖 、 一幅照片 、 一首歌曲等等 ， 都屬于計(jì)算機(jī)能處理的數(shù)據(jù) 。 在計(jì)算機(jī)科學(xué)中 ， 所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)統(tǒng)稱(chēng)為數(shù)據(jù) 。 ? 計(jì)算機(jī)網(wǎng)絡(luò)中，各計(jì)算機(jī)之間是網(wǎng)狀關(guān)系。 實(shí)例 3: ? 網(wǎng)狀關(guān)系 : ? 在城市鐵路交通圖中，各城市之間的關(guān)系是網(wǎng)狀關(guān)系。 ? 人的輩分關(guān)系中，祖輩下是父輩，父輩下是子輩，這些是層次關(guān)系。 ? 疊盤(pán)子中各盤(pán)子之間的關(guān)系是線(xiàn)性的。 在實(shí)際問(wèn)題中，各個(gè)對(duì)象之間的關(guān)系有線(xiàn)性的、層次的和網(wǎng)狀的等等 . 實(shí)例 1: ? 線(xiàn)性關(guān)系 : ? 列車(chē)中各車(chē)箱之間的關(guān)系就是線(xiàn)性的。 (3) 編寫(xiě)程序。即從具體問(wèn)題中找出操作對(duì)象之間含有的關(guān)系，然后用數(shù)學(xué)語(yǔ)言加以描述。數(shù)據(jù)結(jié)構(gòu)是一門(mén)綜合性的專(zhuān)業(yè)基礎(chǔ)課 ， 它涉及到計(jì)算機(jī)硬件的研究范圍和軟件的研究范圍 (存儲(chǔ)裝置和存取方法等 )。 第 1章 數(shù)據(jù)庫(kù)系統(tǒng)的基本概念 ? 什么是數(shù)據(jù)結(jié)構(gòu) ? 基本概念和術(shù)語(yǔ) ? 運(yùn)算、算法和算法分析 ? 習(xí)題 什么是數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)結(jié)構(gòu)這門(mén)學(xué)科主要是研究各種 結(jié)構(gòu) 、 定義 在各種結(jié)構(gòu)上的 操作 和這些操作在計(jì)算機(jī)中的 實(shí)現(xiàn) 方法 。數(shù)據(jù)結(jié)構(gòu)（ C語(yǔ)言）上 第 1章 緒 論 （時(shí)間： 1次課， 2學(xué)時(shí)） 第 1章 緒 論 ? 教學(xué)提示： 本章主要介紹數(shù)據(jù)結(jié)構(gòu)的概念及有關(guān)術(shù)語(yǔ)，為后續(xù)章節(jié)做好鋪墊。 ? 教學(xué)目標(biāo)： 通過(guò)本章的學(xué)習(xí)，使讀者能掌握數(shù)據(jù)結(jié)構(gòu)的概念和有關(guān)的術(shù)語(yǔ)。 ? 提示： 數(shù)據(jù)結(jié)構(gòu)研究實(shí)際問(wèn)題中元素之間的邏輯關(guān)系 、 元素及其關(guān)系在計(jì)算機(jī)中的表示和相關(guān)的操作 。 用計(jì)算機(jī)解決一個(gè)具體問(wèn)題時(shí)要考慮以下步驟： (1) 從具體問(wèn)題中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型。 (2) 設(shè)計(jì)一個(gè)適合該數(shù)學(xué)模型的算法。 (4) 進(jìn)行測(cè)試、調(diào)整、修改，直至解決問(wèn)題。 ? 排隊(duì)買(mǎi)車(chē)票人之間的關(guān)系是線(xiàn)性的。 實(shí)例 2: ? 層次關(guān)系 : ? 在軍隊(duì)的編制中，軍下面是師，師下面是團(tuán)，軍、師、團(tuán)之間是層次關(guān)系。 ? 學(xué)校的編制中，學(xué)校分成若干個(gè)學(xué)院、學(xué)院下又分成若干個(gè)系、系下又分成若干個(gè)教研室，這些也都是層次關(guān)系。 ? 電話(huà)網(wǎng)中，各電話(huà)之間是網(wǎng)狀關(guān)系。 基本概念和術(shù)語(yǔ) ? 數(shù)據(jù) (Data)： 數(shù)據(jù)是計(jì)算機(jī)表示客觀事物的符號(hào) 。它是計(jì)算機(jī)程序加工的 “ 原料 ” 。 因此 ， 對(duì)計(jì)算機(jī)科學(xué)而言 ， 數(shù)據(jù)的含義極為廣泛；圖象 、 聲音等也都可以通過(guò)編碼而歸之于數(shù)據(jù)的范疇 。 數(shù)據(jù)的范圍非常廣泛 ， 數(shù)據(jù)元素也是可大可小的 。 有時(shí) ， 一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成 。 基本概念和術(shù)語(yǔ) ? 數(shù)據(jù)結(jié)構(gòu)： 數(shù)據(jù)結(jié)構(gòu)是彼此具有一定關(guān)系的數(shù)據(jù)元素的集合 。 這種數(shù)據(jù)元素之間的相互關(guān)系稱(chēng)為結(jié)構(gòu) 。 數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)兩個(gè)研究方面 。 基本概念和術(shù)語(yǔ) ? 四種基本數(shù)據(jù)結(jié)構(gòu)： ? 集合： 這個(gè)結(jié)構(gòu)中的數(shù)據(jù)元素之間同屬于一個(gè)集合 ， 除這一關(guān)系外沒(méi)有其他關(guān)系 。 ? 樹(shù)型結(jié)構(gòu)： 這個(gè)結(jié)構(gòu)中數(shù)據(jù)元素之間存在著層次關(guān)系 。 圖 四種基本數(shù)據(jù)結(jié)構(gòu) 基本概念和術(shù)語(yǔ) ? 存儲(chǔ)結(jié)構(gòu)： ? 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱(chēng)為數(shù)據(jù)的物理結(jié)構(gòu) ， 又稱(chēng)為存儲(chǔ)結(jié)構(gòu) 。 同一種邏輯結(jié)構(gòu)可以使用不同的物理結(jié)構(gòu)來(lái)實(shí)現(xiàn) 。 一個(gè)數(shù)據(jù)元素的 “ bit位串 ” 通常稱(chēng)為 “ 結(jié)點(diǎn) ” 。 ? 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有兩種基本的存儲(chǔ)結(jié)構(gòu)： 順序存儲(chǔ)結(jié)構(gòu) 和 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 。 基本概念和術(shù)語(yǔ) ? 數(shù)據(jù)類(lèi)型： ? 高級(jí)程序設(shè)計(jì)語(yǔ)言中的數(shù)據(jù)類(lèi)型分為 原子類(lèi)型 和 結(jié)構(gòu)類(lèi)型 。 C語(yǔ)言中的基本類(lèi)型 (整型 、 實(shí)型 、 字符型和枚舉類(lèi)型 )、 指針類(lèi)型和空類(lèi)型都是原子類(lèi)型 。 例如 C語(yǔ)言中數(shù)組的類(lèi)型和結(jié)構(gòu)體類(lèi)型是由其他類(lèi)型定義的 。 上機(jī)實(shí)現(xiàn)時(shí) ， 再把抽象數(shù)據(jù)類(lèi)型用具體的類(lèi)型代替 。 (2) 引用型運(yùn)算： 運(yùn)算不改變結(jié)構(gòu)中數(shù)據(jù)元素的個(gè)數(shù)和元素的內(nèi)容 ， 只從結(jié)構(gòu)中提取某些信息作為運(yùn)算的結(jié)果 。 刪除運(yùn)算： 屬于加工型運(yùn)算，將原結(jié)構(gòu)中的某個(gè)指定的數(shù)據(jù)元素刪除。 讀取運(yùn)算： 屬于引用型運(yùn)算，使用結(jié)構(gòu)中滿(mǎn)足條件的數(shù)據(jù)元素的內(nèi)容。 使用這些基本運(yùn)算，可以構(gòu)成其他的復(fù)雜運(yùn)算 。 算法 是對(duì)求解某個(gè)問(wèn)題的步驟的一種描述方法 。 算法及其描述 算法要具備下列五個(gè)特性： 有窮性： 算法必須在執(zhí)行有窮步之后結(jié)束 ， 而每一步都必須在有窮時(shí)間內(nèi)完成 。 可行性： 一個(gè)算法必須是可行的 ， 即算法中每一操作都能通過(guò)已知的一組基本操作來(lái)實(shí)現(xiàn) 。 輸 出： 一個(gè)算法有一個(gè)或多個(gè)輸出 。 易讀性： 算法應(yīng)當(dāng)便于閱讀和理解 ， 以利于修改和改寫(xiě)成程序 。 高效率： 算法的效率主要從時(shí)間和空間兩個(gè)方面考慮 。 算法分析和算法復(fù)雜度 算法分析： 研究算法的效率稱(chēng)為 算法復(fù)雜度的分析 (簡(jiǎn)稱(chēng)算法分析 )。 在算法分析中絕對(duì)的量不能反映時(shí)間復(fù)雜度，使用一個(gè)函數(shù) T(n)表示一個(gè)算法的復(fù)雜度。也就是說(shuō)，時(shí)間復(fù)雜度是 n的一個(gè)函數(shù)。 算法分析和算法復(fù)雜度 算法復(fù)雜度，舉例： ① {x++。} 時(shí)間復(fù)雜度為 O(1) ② for(k=1。 k++) s=k+2； 時(shí)間復(fù)雜度為 O(n) ③ for(k=1。 k++) for(j=1。 j++) s=k+j； 時(shí)間復(fù)雜度為 O(n2) 習(xí) 題 ? 1 填空題 ? 2 選擇題 ? 3 簡(jiǎn)答題 習(xí) 題 __填空題 (1) 從數(shù)據(jù)結(jié)構(gòu) S中找出滿(mǎn)足條件的結(jié)點(diǎn)在 S中位置的運(yùn)算是 _____________型運(yùn)算。 (3) 從數(shù)據(jù)結(jié)構(gòu) S中的某指定位置上增加一個(gè)新結(jié)點(diǎn)的運(yùn)算是 _____________型運(yùn)算。 (5) 從數(shù)據(jù)結(jié)構(gòu) S中修改結(jié)構(gòu)中某指定結(jié)點(diǎn)內(nèi)容的運(yùn)算是 _____________型運(yùn)算。 A. 書(shū)寫(xiě)在紙上 B. 從機(jī)外轉(zhuǎn)為機(jī)內(nèi) C. 磁盤(pán)中的數(shù)據(jù) D. 光盤(pán)中的數(shù)據(jù) (2) 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，其內(nèi) _____________數(shù)據(jù)項(xiàng)。 A. 類(lèi)型 B. 存儲(chǔ)方式 C. 結(jié)構(gòu) D. 數(shù)據(jù)項(xiàng) 習(xí) 題 __選擇題 (4) 邏輯結(jié)構(gòu)是 _____________關(guān)系的整體。 A. 1 B. 2 C. 3 D. 4 (6) 下列四種基本的邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是 _______。 A. 數(shù)據(jù)項(xiàng) B. 數(shù)據(jù)元素 C. 數(shù)據(jù)結(jié)構(gòu) D. 數(shù)據(jù)類(lèi)型 (8)