【正文】 oc。 list [i1] =x。 exit(2)。 list [i+1] =x。 算法描述： ?從數(shù)列右邊開始，即從第 8個(gè)元素開始； ?為在第 5個(gè)元素“ 21”后插入“ 25”，則要把其后的 3個(gè)元素右移，移動(dòng)元素個(gè)數(shù)是 3（ 85）； for (k=last。 step2 將 x插入到 ai1之后 。 下一頁 上一頁 停止放映 第 35 頁 線性表的基本操作 Setnull（ L） 置空表 Length（ L） 求表長度；求表中元素個(gè)數(shù) Get（ L， i） 取表中第 i個(gè)元素（ 1?i ?n） Prior（ L， i） 取 i的前趨元素 Next（ L， i） 取 i的后繼元素 Locate（ L， x） 返回指定元素在表中的位置 Insert（ L， i， x） 插入元素 Delete（ L， x） 刪除元素 Empty（ L） 判別表是否為空 下一頁 上一頁 停止放映 第 36 頁 （二）線性表的順序存儲結(jié)構(gòu) 將表中元素一個(gè)接一個(gè)的存入一組連續(xù)的存儲單元中，這種存儲結(jié)構(gòu)是順序結(jié)構(gòu)。 下一頁 上一頁 停止放映 第 33 頁 （一）線性表的邏輯結(jié)構(gòu) 定義： 線性表是 n（ n?0）個(gè)元素 a1,a2,…,a n 的有限序列；表中每個(gè)數(shù)據(jù)元素，除了第 1個(gè)和最后 1個(gè)外，有且僅有一個(gè)前趨元素和后繼元素。度量同時(shí)間復(fù)雜度。 下一頁 上一頁 停止放映 第 29 頁 算法的描述 算法的描述方式（常用的）： 自然語言 流程圖 特定的表示算法的圖形 符號 算法描述 偽語言 包括程序設(shè)計(jì)語言的三 大基本結(jié)構(gòu)及自然語言 的一種語言 類語言 類似高級語言的語言， 例如，類 PASCAL、類 C語言。 下一頁 上一頁 停止放映 第 24 頁 算法的設(shè)計(jì)要求 ?正確性 （ Correctness） ?可讀性 （ Readability） ?健壯性 （ Robustness） ?高效率 與 低存儲量 下一頁 上一頁 停止放映 第 25 頁 正確性（ Correctness） 有 4個(gè)層次： A. 程序不含語法錯(cuò)誤； B. 程序?qū)捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格要求的結(jié)果； C. 程序?qū)倪x擇的、典型的、苛刻的、帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格要求的結(jié)果； D. 程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格要求的結(jié)果。 下一頁 上一頁 停止放映 第 22 頁 算法（ Algorithm） – 是對特定問題求解步驟的一種描述； – 是一組指令的有限集合。 ?哈希查找中的哈希表就是這樣一種存儲結(jié)構(gòu)。 下一頁 上一頁 停止放映 第 19 頁 索引存儲結(jié)構(gòu) 數(shù)據(jù)按索引形式存放。 ? 插入、刪除操作不便（需大量移動(dòng)元素）。 下一頁 上一頁 停止放映 第 16 頁 數(shù)據(jù)存儲結(jié)構(gòu)分類 ?順序存儲結(jié)構(gòu) ?鏈?zhǔn)酱鎯Y(jié)構(gòu) ?索引存儲結(jié)構(gòu) ?散列存儲結(jié)構(gòu) 下一頁 上一頁 停止放映 第 17 頁 順序存儲結(jié)構(gòu) 把數(shù)據(jù)元素按某種順序存放在一塊連續(xù)的存儲單元中的存儲形式。 定義 DS如下： Group=（ D， R） 其中： D={T， G1， … ,Gn,S11,… Snm} 1 ? n ? 3 , 1 ? m ? 2 R={R1,R2} R1={T,Gi|1 ? i ? n , 1 ? n ? 3} R2={Gi,Sij|1?i?n ,1? j ? m , 1 ? n ? 3 , 1 ? m ? 2 } 下一頁 上一頁 停止放映 第 14 頁 2. 數(shù)據(jù)的存儲結(jié)構(gòu) ?又稱物理結(jié)構(gòu) ?是指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示 (又稱映象 ),即數(shù)據(jù)在計(jì)算機(jī)中的存放 。 按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的存儲方式把它存儲在計(jì)算機(jī)存儲器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，叫做一個(gè)數(shù)據(jù)結(jié)構(gòu) (Data Structures)。它研究的主要問題： ? 分析數(shù)據(jù)（加工對象）的特征 ? 選擇邏輯存儲結(jié)構(gòu)和物理存儲結(jié)構(gòu) ? 在存儲結(jié)構(gòu)基礎(chǔ)上實(shí)現(xiàn)對數(shù)據(jù)的操作 下一頁 上一頁 停止放映 第 4 頁 第 2單元 線性數(shù)據(jù)結(jié)構(gòu)（一） 教學(xué)目標(biāo)： ? 了解數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念 什么是線性 DS、線性表 ? 了解線性 DS的特點(diǎn) ? 了解線性 DS的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)以及操作 下一頁 上一頁 停止放映 第 5 頁 學(xué)習(xí)要求 通過本單元的學(xué)習(xí)，了解并掌握： ? 有關(guān) 數(shù)據(jù)結(jié)構(gòu)（ DS）的基本概念 –數(shù)據(jù)元素、 DS、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、 DS的分類及特點(diǎn)、算法、時(shí)間復(fù)雜度等 ? 線性 DS的常用存儲結(jié)構(gòu) –順序、鏈表、索引、散列存儲結(jié)構(gòu) –單向、雙向、循環(huán)鏈表等 ? 線性 DS的有關(guān)算法 –增、刪、改 下一頁 上一頁 停止放映 第 6 頁 涉及的章節(jié) 第 1章的 數(shù)據(jù)結(jié)構(gòu)概述 (P13~P17) 線性表 (P17~P32) 下一頁 上一頁 停止放映 第 7 頁 數(shù)據(jù)結(jié)構(gòu)問題的由來 計(jì)算機(jī)求解問題的過程步驟： 分析抽象 模型求解 命令 編程 調(diào)試程序 編制 程序 運(yùn)行 程序 求解 結(jié)果 結(jié)果輸出 用戶 需求 數(shù)據(jù)類型、格式、 邏輯結(jié)構(gòu) 數(shù)據(jù) 邏輯 運(yùn)算 數(shù)據(jù)的物理 操作 實(shí)際問題 問題 模型 求解算法 下一頁 上一頁 停止放映 第 8 頁 問題模型 ? 結(jié)構(gòu)分析 —— 線性方程組 ? 人口預(yù)報(bào) —— 微分方程 ? 優(yōu)化問題 —— 線性規(guī)劃 、 非線性規(guī)劃 ? 震動(dòng)問題 —— 矩陣分析；特征值 、 特征向量 ? 信息管理 —— 二維數(shù)據(jù)表 ? 下棋 —— 人工智能 (樹型結(jié)構(gòu) ) ? 交通管理 ——最佳道路選擇 (圖型結(jié)構(gòu) ) 下一頁 上一頁 停止放映 第 9 頁 下棋問題 ? 1 1 ? 1 1 1 ? ? 1 1 1 ? ? 1 1 1 ? ? ? ? 1 1 1 ? ? 1 ? 1 下一頁 上一頁 停止放映 第 10 頁 一、基本概念 ? 數(shù)據(jù)（ Data） 能存于計(jì)算機(jī)、并被計(jì)算機(jī)處理的符號的集合。它是客觀事物的符號表示。 下一頁 上一頁 停止放映 第 11 頁 數(shù)據(jù)結(jié)構(gòu)分類 線性表 堆棧 隊(duì)列 串 數(shù)組 樹 二叉樹 圖 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu) DS 下一頁 上一頁 停止放映 第 12 頁 1. 數(shù)據(jù)的邏輯結(jié)構(gòu) 它是描述數(shù)據(jù)間的順序（邏輯）關(guān)系，只是抽象地反映數(shù)據(jù)元素的結(jié)構(gòu)，而不管它們在計(jì)算機(jī)中如何存放。 數(shù)據(jù)庫中的數(shù)據(jù)存放在計(jì)算機(jī)中的物理位置 下一頁 上一頁 停止放映 第 15 頁 邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的關(guān)系 ? 數(shù)據(jù)的 邏輯結(jié)構(gòu) 是從邏輯關(guān)系（某種順序）上觀察數(shù)據(jù)，它是獨(dú)立于計(jì)算機(jī)的；可以在理論上、形式上進(jìn)行研究、推理、運(yùn)算等各種操作。數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu) : d1 d2 …… dn 數(shù)據(jù)域 特點(diǎn) : ? 連續(xù)存放 。 下一頁 上一頁 停止放映 第 18 頁 鏈?zhǔn)酱鎯Y(jié)構(gòu) 以鏈表形式將數(shù)據(jù)元素存放于任意存儲單元中，可連續(xù)存放，也可以不連續(xù)存放，以指針實(shí)現(xiàn)鏈表間的聯(lián)系。存儲時(shí)分為：數(shù)據(jù)項(xiàng)和索引號；通過索引表記錄邏輯號（記錄號）和物理號（存儲序號）之間的對應(yīng)關(guān)系。 特點(diǎn)： – 數(shù)據(jù)元素間無內(nèi)在聯(lián)系； – 存儲形式不定。 算法和數(shù)據(jù)結(jié)構(gòu)的關(guān)系 為了充分地利用系統(tǒng)資源；既要效率高、速度快，又要存儲空間少。 下一頁 上一頁 停止放映 第 26 頁 可讀性（ Readability） ?算法的第一目的是為了閱讀和交流； ?可讀性有助于對算法的理解； ?可讀性有助于對算法的調(diào)試和修改。 下一頁 上一頁 停止放映 第 30 頁 算法的評價(jià) 算法評價(jià)的標(biāo)準(zhǔn)： 時(shí)間復(fù)雜度 指在計(jì)算機(jī)上運(yùn)行該算法所花費(fèi)的時(shí)間。 下一頁 上一頁 停止放映 第 3