【正文】 復(fù)雜，需要額外存儲(chǔ)空間。 ? 結(jié)構(gòu)簡(jiǎn)單，易實(shí)現(xiàn)。 ? 任何一個(gè) 算法的設(shè)計(jì) 取決于選定的邏輯結(jié)構(gòu)；而算法的最終實(shí)現(xiàn) 依賴于采用的存儲(chǔ)結(jié)構(gòu)。 與數(shù)據(jù)在計(jì)算機(jī)中的存放的 物理位置無(wú)關(guān) 下一頁(yè) 上一頁(yè) 停止放映 第 13 頁(yè) 舉例 ? 課題組由 1名教師、 1~3名研究生、 1~6名本科生組成；成員關(guān)系是：教師指導(dǎo)研究生、研究生指導(dǎo) 1~2名本科生。 ? 數(shù)據(jù)結(jié)構(gòu)（ Data Structure） 是帶有結(jié)構(gòu)特征的數(shù)據(jù)元素的集合 ,三要素： DS=數(shù)據(jù)的邏輯結(jié)構(gòu) +存儲(chǔ)結(jié)構(gòu) +數(shù)據(jù)的運(yùn)算 數(shù)據(jù)結(jié)構(gòu)是以數(shù)據(jù)為加工對(duì)象，研究數(shù)據(jù)組織方式和相關(guān)操作方法的學(xué)問(wèn)。下一頁(yè) 第 2單元 線性數(shù)據(jù)結(jié)構(gòu) （一） 主講：劉志強(qiáng) 計(jì)算機(jī)軟件基礎(chǔ) Fundamentals of Computer software 下一頁(yè) 上一頁(yè) 停止放映 第 2 頁(yè) 思考問(wèn)題 數(shù)據(jù)結(jié)構(gòu)要研究什么問(wèn)題？ 數(shù)組是怎樣的存儲(chǔ)和操作？ 什么是線性數(shù)據(jù)結(jié)構(gòu)和線性表？ 如何描述線性表？ 線性表在計(jì)算機(jī)中如何存放？有幾種存儲(chǔ)形式？它們的特點(diǎn)是什么？ 如何處理線性數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)？ 下一頁(yè) 上一頁(yè) 停止放映 第 3 頁(yè) 什么是數(shù)據(jù)結(jié)構(gòu)？ 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)的專業(yè)技術(shù)基礎(chǔ)課。 ? 數(shù)據(jù)元素（ Element） 是數(shù)據(jù)的基本單位、數(shù)據(jù)集合中的個(gè)體。一般用下列二元組來(lái)描述： DS=（ D， R） 其中： D：是數(shù)據(jù)元素的有限集合； R：是數(shù)據(jù)元素之間關(guān)系的集合。 ? 數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu) 是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，是依賴于計(jì)算機(jī)的；離開(kāi)了機(jī)器，則無(wú)法進(jìn)行任何操作。邏輯上相鄰 ,物理上也相鄰。數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu) : d1 ... d2 dn ^ 數(shù)據(jù)域 指針域 特點(diǎn) : ? 非連續(xù)存放 ,借助指針來(lái)表示元素間的關(guān)系 。數(shù)據(jù)結(jié)點(diǎn)結(jié)構(gòu) : 序 號(hào)： 1 2 3 4 5 6 7 數(shù)據(jù)項(xiàng)： 索引號(hào)： 12 21 35 2 45 5 10 4 3 2 7 1 6 5 數(shù)據(jù)域 索引順序號(hào) 特點(diǎn)： ? 非連續(xù)存放； ? 檢索速度快； ? 增、刪操作簡(jiǎn)單。 下一頁(yè) 上一頁(yè) 停止放映 第 21 頁(yè) ?數(shù)據(jù)運(yùn)算是指對(duì)存放在物理結(jié)構(gòu)上的數(shù)據(jù) ,按定義的邏輯結(jié)構(gòu)進(jìn)行的各種操作。顯然，這是矛盾的。 下一頁(yè) 上一頁(yè) 停止放映 第 27 頁(yè) 健壯性（ Robustness） ?當(dāng)輸入非法數(shù)據(jù)時(shí)，算法也能適當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行處理；并且，處理出錯(cuò)的方法應(yīng)該是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值并中止程序的執(zhí)行，以便在更高的抽象層次上進(jìn)行處理。用“ O（數(shù)量級(jí)）”來(lái)表示，稱為“階”。例如，一星期七天的英文縮寫表示： （ Sun， Mon， The， wed， Thu， Fri， Sat） 是一個(gè)線性表，其中的元素是字符串，表的長(zhǎng)度為 7。關(guān)系 N是一個(gè)有序偶對(duì)的集合。順序表的存儲(chǔ)特點(diǎn)是：只要確定了起始位置，表中任一元素的地址都通過(guò)下列公式得到： LOC（ ai） =LOC（ a1） +（ i1） *L 1?i ?n 其中， L是元素占用存儲(chǔ)單元的長(zhǎng)度。 線性表采用一維數(shù)組存放。k) /* last 是元素個(gè)數(shù) (8), */ list[k+1]=list[k]。 exit(1)。K=i1。 } } 下一頁(yè) 上一頁(yè) 停止放映 第 41 頁(yè) 算法 11 插入算法主程序 define MAXLENGTH 100 /* 例 11主程序 */ int list[MAXLENGTH]={5,3,1,10,7,8,1,4}。 scanf(“%d,%d”,amp。jMAXLENGTH,j++) printf(“%d “,list[j])。jMAXLENGTH,j++) printf(“%d “,list[j])。 線性表采用一維數(shù)組存放。k++) /* last 是元素個(gè)數(shù) (9), */ list[k1]=list[k]。 } for(k= i1。 } 下一頁(yè) 上一頁(yè) 停止放映 第 45 頁(yè) 算法 12 線性表刪除算法 define MAXLENGTH 100 /* 例 12主程序 */ int list[MAXLENGTH]={5,3,1,10,7,8,1,4}。 scanf(“%d”,amp。 printf(“\n”)。 printf(“\n”)。 ? 鏈表存儲(chǔ)結(jié)構(gòu) 在這兩個(gè)方面恰好是優(yōu)點(diǎn)： – 容易插入、刪除操作 – 不需要預(yù)分空間。 }。 首元結(jié)點(diǎn) 第一個(gè)結(jié)點(diǎn)（ a1）。 ai ai1 ai+1 ai ai1 ai+1 p p 操作前狀態(tài) 操作后狀態(tài) 下一頁(yè) 上一頁(yè) 停止放映 第 59 頁(yè) 指針操作的舉例 3 p=qnext p指向 q所指結(jié)點(diǎn)的后繼 ai ai1 ai+1 ai ai1 ai+1 q q p p 操作前狀態(tài) 操作后狀態(tài) 下一頁(yè) 上一頁(yè) 停止放映 第 60 頁(yè) 指針操作的舉例 4 pnext=NULL 將指針 p所指結(jié)點(diǎn)與后繼結(jié)點(diǎn)斷開(kāi) ai ai1 ai+1 ai ai1 p 操作前狀態(tài) 操作后狀態(tài) p ^ ai+1 下一頁(yè) 上一頁(yè) 停止放映 第 61 頁(yè) 單鏈表的查找算法 ?返回指向第 i個(gè)結(jié)點(diǎn)的指針。amp。 if((p!=NULL)amp。 /* 否則，返回空值 */ 下一頁(yè) 上一頁(yè) 停止放映 第 63 頁(yè) 單鏈表查找算法程序 NODE *get(NODE *head, int i） ｛ NODE *p。amp。amp。 下一頁(yè) 上一頁(yè) 停止放映 第 65 頁(yè) 單鏈表查找算法程序 NODE *length(NODE *head ） ｛ NODE *p。 counter++。 else p=get(head,i1)。 sdata=x。 if(i==1) p=head。 } if(pnext==NULL) { printf(“i=表長(zhǎng) +1,無(wú)此結(jié)點(diǎn) \n”)。 free(t) 。 ?鏈表可以從兩個(gè)方向檢索，效果更佳；這就是 雙向循環(huán)鏈表 。 ?雙向循環(huán)鏈表，其存儲(chǔ)結(jié)構(gòu)： struct dnode{ int data； struct dnode *prior， *next； }； typedef struct dnode DNODE； 下一頁(yè) 上一頁(yè) 停止放映 第 74 頁(yè) 雙向循環(huán)鏈表結(jié)點(diǎn)結(jié)構(gòu) prior data next 指向后繼結(jié)點(diǎn) 指針域 數(shù)據(jù)域 指向前趨結(jié)點(diǎn) 指針域 下一頁(yè) 上一頁(yè) 停止放映 第 75 頁(yè) 雙向循環(huán)鏈表表示形式 雙向循環(huán)鏈表表示形式： 雙循環(huán)鏈表為空的條件 : head ?.prior = head ?.next = head 表示形式為 : head head ... ... ^ ^ an a2 a1 下一頁(yè) 上一頁(yè) 停止放映 第 76 頁(yè) 雙向循環(huán)鏈表特點(diǎn) ?適合于兩個(gè)方向的移動(dòng)。 下一頁(yè) 上一頁(yè) 停止放映 第 81 頁(yè) 5. 鏈表的動(dòng)態(tài)生成 鏈表是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。 head ^ ... s ai1 ai an ai2 下一頁(yè) 上一頁(yè) 停止放映 第 84 頁(yè) 例題分析一 將一個(gè)單鏈表分解為兩個(gè)帶頭結(jié)點(diǎn)的單鏈表 A和 B， A中含有原表中序號(hào)為奇數(shù)的元素， B中含有原表中序號(hào)為偶數(shù)的元素，且保持其相對(duì)順序。 if ( j%2 == 1) j 。 /* 將 A中偶數(shù)元素刪除 */ j = 2。 若 a = b , 則將 a插入 C中 ,i、 j和 k均加 1。 len_b = length(b) 。 data_b = get( b, j) 。 k ++ 。 中心網(wǎng)址： 課件下載地址 : 我的 Email地址 : 答疑安排： 每星期四下午： 4： 00～ 6： 00 地點(diǎn)： 計(jì)教中心 102房間（ 1300大教室對(duì)面）