【正文】 counter++。 下一頁(yè) 上一頁(yè) 停止放映 第 62 頁(yè) 單鏈表查找示意舉例 命題 : 設(shè)有數(shù)列 {4,5,8,10,21,30,43,59}，長(zhǎng)度為 8，返回第 5個(gè)元素的指針。 下一頁(yè) 上一頁(yè) 停止放映 第 47 頁(yè) （三 ）線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ? 線性表的順序存儲(chǔ)結(jié)構(gòu)容易實(shí)現(xiàn)，可以隨機(jī)存取表中的任意元素。k++) list[k]=list[k+1]。 insert(loc,x)。 exit(2)。 下一頁(yè) 上一頁(yè) 停止放映 第 35 頁(yè) 線性表的基本操作 Setnull（ L） 置空表 Length（ L） 求表長(zhǎng)度；求表中元素個(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） 判別表是否為空 下一頁(yè) 上一頁(yè) 停止放映 第 36 頁(yè) （二）線性表的順序存儲(chǔ)結(jié)構(gòu) 將表中元素一個(gè)接一個(gè)的存入一組連續(xù)的存儲(chǔ)單元中，這種存儲(chǔ)結(jié)構(gòu)是順序結(jié)構(gòu)。 下一頁(yè) 上一頁(yè) 停止放映 第 24 頁(yè) 算法的設(shè)計(jì)要求 ?正確性 （ Correctness） ?可讀性 （ Readability） ?健壯性 （ Robustness） ?高效率 與 低存儲(chǔ)量 下一頁(yè) 上一頁(yè) 停止放映 第 25 頁(yè) 正確性（ Correctness） 有 4個(gè)層次： A. 程序不含語(yǔ)法錯(cuò)誤； B. 程序?qū)捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格要求的結(jié)果； C. 程序?qū)倪x擇的、典型的、苛刻的、帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格要求的結(jié)果； D. 程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格要求的結(jié)果。 ? 插入、刪除操作不便（需大量移動(dòng)元素）。它研究的主要問(wèn)題： ? 分析數(shù)據(jù)（加工對(duì)象）的特征 ? 選擇邏輯存儲(chǔ)結(jié)構(gòu)和物理存儲(chǔ)結(jié)構(gòu) ? 在存儲(chǔ)結(jié)構(gòu)基礎(chǔ)上實(shí)現(xiàn)對(duì)數(shù)據(jù)的操作 下一頁(yè) 上一頁(yè) 停止放映 第 4 頁(yè) 第 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)以及操作 下一頁(yè) 上一頁(yè) 停止放映 第 5 頁(yè) 學(xué)習(xí)要求 通過(guò)本單元的學(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的常用存儲(chǔ)結(jié)構(gòu) –順序、鏈表、索引、散列存儲(chǔ)結(jié)構(gòu) –單向、雙向、循環(huán)鏈表等 ? 線性 DS的有關(guān)算法 –增、刪、改 下一頁(yè) 上一頁(yè) 停止放映 第 6 頁(yè) 涉及的章節(jié) 第 1章的 數(shù)據(jù)結(jié)構(gòu)概述 (P13~P17) 線性表 (P17~P32) 下一頁(yè) 上一頁(yè) 停止放映 第 7 頁(yè) 數(shù)據(jù)結(jié)構(gòu)問(wèn)題的由來(lái) 計(jì)算機(jī)求解問(wèn)題的過(guò)程步驟： 分析抽象 模型求解 命令 編程 調(diào)試程序 編制 程序 運(yùn)行 程序 求解 結(jié)果 結(jié)果輸出 用戶 需求 數(shù)據(jù)類型、格式、 邏輯結(jié)構(gòu) 數(shù)據(jù) 邏輯 運(yùn)算 數(shù)據(jù)的物理 操作 實(shí)際問(wèn)題 問(wèn)題 模型 求解算法 下一頁(yè) 上一頁(yè) 停止放映 第 8 頁(yè) 問(wèn)題模型 ? 結(jié)構(gòu)分析 —— 線性方程組 ? 人口預(yù)報(bào) —— 微分方程 ? 優(yōu)化問(wèn)題 —— 線性規(guī)劃 、 非線性規(guī)劃 ? 震動(dòng)問(wèn)題 —— 矩陣分析；特征值 、 特征向量 ? 信息管理 —— 二維數(shù)據(jù)表 ? 下棋 —— 人工智能 (樹(shù)型結(jié)構(gòu) ) ? 交通管理 ——最佳道路選擇 (圖型結(jié)構(gòu) ) 下一頁(yè) 上一頁(yè) 停止放映 第 9 頁(yè) 下棋問(wèn)題 ? 1 1 ? 1 1 1 ? ? 1 1 1 ? ? 1 1 1 ? ? ? ? 1 1 1 ? ? 1 ? 1 下一頁(yè) 上一頁(yè) 停止放映 第 10 頁(yè) 一、基本概念 ? 數(shù)據(jù)（ Data） 能存于計(jì)算機(jī)、并被計(jì)算機(jī)處理的符號(hào)的集合。數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu) : d1 d2 …… dn 數(shù)據(jù)域 特點(diǎn) : ? 連續(xù)存放 。 算法和數(shù)據(jù)結(jié)構(gòu)的關(guān)系 為了充分地利用系統(tǒng)資源；既要效率高、速度快，又要存儲(chǔ)空間少。 形式定義： 含有 n個(gè)數(shù)據(jù)元素的線性表是一種數(shù)據(jù)結(jié)構(gòu)，表示為： Linear_list=( D , R ) 其中 : D={ai | ai?D0,i=1,2,3,…,n,n ?0} R={N}, N={ai1,ai|ai1,ai ?D0 ,i=1,…,n} D是數(shù)據(jù)元素的有限集合， R是 D上邏輯關(guān)系的有限集合。 /* 將 x存放在第 i+1 位置 */ ?元素個(gè)數(shù)加“ 1” last++； /* last加“ 1”后，結(jié)果為“ 9” */ ?最后，得到的結(jié)果數(shù)列是 {4,5,8,10,21,25,30,43,59} 下一頁(yè) 上一頁(yè) 停止放映 第 40 頁(yè) 算法 11 插入算法 insert（ int i， int x） { int k； if（ last==MAXLENGTH） { printf（“線性表已滿！ \n”)。 for (j=0。 exit(1)。jMAXLENGTH,j++) printf(“%d “,list[j])。例如，要?jiǎng)h除結(jié)點(diǎn) ai，首先要使指針 P指向 ai，即： a1 ... ... head ai an ^ p 指針 p是指向存儲(chǔ)單元 ai的指針，地址內(nèi)的內(nèi)容可以通過(guò) Pdata得到，指向下個(gè)元素的指針用 pnext得到 下一頁(yè) 上一頁(yè) 停止放映 第 56 頁(yè) 指針的基本操作列表 p=（ NODE*） malloc（ sizeof（ NODE）） 申請(qǐng)一個(gè)結(jié)點(diǎn)空間 ,并將地址送入 p中 free（ p） 釋放 p指針?biāo)附Y(jié)點(diǎn)的空間 p=q 指針 p指向指針 q所指的結(jié)點(diǎn) p=qnext 指針 p指向指針 q所指結(jié)點(diǎn)的后繼 p=pnext 指針 p向后移動(dòng)一個(gè)結(jié)點(diǎn) pnext=q 將指針 q所指結(jié)點(diǎn)改接為指針 p所指結(jié)點(diǎn)的后繼 pnext=NULL 將指針 p所指結(jié)點(diǎn)與后繼結(jié)點(diǎn)斷開(kāi) 下一頁(yè) 上一頁(yè) 停止放映 第 57 頁(yè) 指針操作的舉例 1 申請(qǐng)一個(gè)結(jié)點(diǎn)空間 ,并將地址送入 p中 p 操作前狀態(tài) 操作后狀態(tài) p p=（ NODE*） malloc（ sizeof（ NODE）） 下一頁(yè) 上一頁(yè) 停止放映 第 58 頁(yè) 指針操作的舉例 2 p=pnext 指針右移一個(gè)結(jié)點(diǎn)位置。 while((p!=NULL)amp。 if(i==1) p=head。 pnext = tnext。 head s ^ ... p a i ai1 a2 a1 下一頁(yè) 上一頁(yè) 停止放映 第 83 頁(yè) 鏈表的動(dòng)態(tài)生成（方法二）從后往前 算法操作步驟： step1 初始化；頭指針置 NULL,線性表元素存于A[N]中 ,i=N1 step2 i = 0 循環(huán) 1) 使 s指向新生成的結(jié)點(diǎn)， 2) sdata = A[i] ,snext = head 3) 指針 s始終指向頭指針 head=s step3 結(jié)束循環(huán) , 返回頭指針 head。 len_a = length(a) 。 i ++ 。 } } 例如： A = { a1， a2， a3， a4， a5}， B={}； Step1 從 A中取出 a4插入 B中，從 A中刪除 a4 A = { a1， a2， a3， a5}， B={a4}； Step2 從 A中取出 a2插入 B中，從 A中刪除 a2 A = { a1， a3， a5}， B={ a2， a4}； 下一頁(yè) 上一頁(yè) 停止放映 第 86 頁(yè) 例題分析二 ? 求兩個(gè)鏈表 A和 B的交集 C（由 A和 B中相同元素組成的集合為交集），且 A和 B是遞增有序的。 ?找其前趨結(jié)點(diǎn)的時(shí)間復(fù)雜度是 O（ 1）。 else p=get(head,i1)。 int counter = 0。amp。 typedef struct node NODE；