【正文】 輸入數(shù)據(jù)能夠得出滿足規(guī)格要求的結(jié)果； C. 程序?qū)倪x擇的、典型的、苛刻的、帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格要求的結(jié)果； D. 程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格要求的結(jié)果。 下一頁 上一頁 停止放映 第 27 頁 健壯性（ Robustness） ?當(dāng)輸入非法數(shù)據(jù)時(shí)，算法也能適當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行處理；并且，處理出錯(cuò)的方法應(yīng)該是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值并中止程序的執(zhí)行，以便在更高的抽象層次上進(jìn)行處理。 下一頁 上一頁 停止放映 第 29 頁 算法的描述 算法的描述方式（常用的）： 自然語言 流程圖 特定的表示算法的圖形 符號 算法描述 偽語言 包括程序設(shè)計(jì)語言的三 大基本結(jié)構(gòu)及自然語言 的一種語言 類語言 類似高級語言的語言， 例如，類 PASCAL、類 C語言。用“ O（數(shù)量級）”來表示，稱為“階”。度量同時(shí)間復(fù)雜度。例如，一星期七天的英文縮寫表示： （ Sun， Mon， The， wed， Thu， Fri， Sat） 是一個(gè)線性表，其中的元素是字符串，表的長度為 7。 下一頁 上一頁 停止放映 第 33 頁 （一）線性表的邏輯結(jié)構(gòu) 定義： 線性表是 n（ n?0）個(gè)元素 a1,a2,…,a n 的有限序列；表中每個(gè)數(shù)據(jù)元素，除了第 1個(gè)和最后 1個(gè)外，有且僅有一個(gè)前趨元素和后繼元素。關(guān)系 N是一個(gè)有序偶對的集合。 下一頁 上一頁 停止放映 第 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)。順序表的存儲特點(diǎn)是：只要確定了起始位置，表中任一元素的地址都通過下列公式得到： LOC（ ai） =LOC（ a1） +（ i1） *L 1?i ?n 其中， L是元素占用存儲單元的長度。 step2 將 x插入到 ai1之后 。 線性表采用一維數(shù)組存放。 算法描述： ?從數(shù)列右邊開始，即從第 8個(gè)元素開始； ?為在第 5個(gè)元素“ 21”后插入“ 25”，則要把其后的 3個(gè)元素右移，移動(dòng)元素個(gè)數(shù)是 3（ 85）； for (k=last。k) /* last 是元素個(gè)數(shù) (8), */ list[k+1]=list[k]。 list [i+1] =x。 exit(1)。 exit(2)。K=i1。 list [i1] =x。 } } 下一頁 上一頁 停止放映 第 41 頁 算法 11 插入算法主程序 define MAXLENGTH 100 /* 例 11主程序 */ int list[MAXLENGTH]={5,3,1,10,7,8,1,4}。 main（） { int x,j,loc。 scanf(“%d,%d”,amp。loc)。jMAXLENGTH,j++) printf(“%d “,list[j])。 insert(loc,x)。jMAXLENGTH,j++) printf(“%d “,list[j])。 } 下一頁 上一頁 停止放映 第 42 頁 算法 12 線性表刪除算法 算法步驟 : step1 判別指定的位置是否合法； step2 若合法，則將位置 i+1至 n上的元素前 移一個(gè)存儲位置 。 線性表采用一維數(shù)組存放。 算法描述： ?從第 7個(gè)元素開始 (i+1)； ?將第 7個(gè)元素“ 30”存入第 6位，將“ 25”覆蓋，即元素左移，移動(dòng)元素個(gè)數(shù)是 3（ 96）； for(k= i+1。k++) /* last 是元素個(gè)數(shù) (9), */ list[k1]=list[k]。 if( i 1 || i last ) { printf(“表中不存在位置為 i的元素 \n”)。 } for(k= i1。k++) list[k]=list[k+1]。 } 下一頁 上一頁 停止放映 第 45 頁 算法 12 線性表刪除算法 define MAXLENGTH 100 /* 例 12主程序 */ int list[MAXLENGTH]={5,3,1,10,7,8,1,4}。 main（） { int j,loc。 scanf(“%d”,amp。 for (j=0。 printf(“\n”)。 /* 刪除操作子函數(shù) */ for (j=0。 printf(“\n”)。 下一頁 上一頁 停止放映 第 47 頁 （三 ）線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ? 線性表的順序存儲結(jié)構(gòu)容易實(shí)現(xiàn)，可以隨機(jī)存取表中的任意元素。 ? 鏈表存儲結(jié)構(gòu) 在這兩個(gè)方面恰好是優(yōu)點(diǎn)： – 容易插入、刪除操作 – 不需要預(yù)分空間。 鏈表存儲結(jié)構(gòu)形式為： 鏈表結(jié)構(gòu)的 C語言描述為： struct node { int data 。 }。 頭指針（ head） 指向鏈表中第 1個(gè)結(jié)點(diǎn)的指針。 首元結(jié)點(diǎn) 第一個(gè)結(jié)點(diǎn)（ a1）。 ?空表形式 : head = NULL ?非空表形式 : head ? . next = address head head a1 下一頁 上一頁 停止放映 第 52 頁 鏈表舉例 ? 由食品組成的單鏈表（不帶頭結(jié)點(diǎn) ） （ biscuit,butter,cheese,eggs,grapes,jam) biscuit butter cheese jam grapes eggs ^ head 頭指針 下一頁 上一頁 停止放映 第 53 頁 單鏈表在存儲區(qū)的物理狀態(tài) Grapes 60 biscuit 61 cheese 13 eggs 1 jam NULL butter 12 存儲地址 數(shù)據(jù)域（ data）指針域（ next） 1 11 12 13 60 61 11 頭指針 head …… 下一頁 上一頁 停止放映 第 54 頁 2. 單鏈表的操作 ?指針的基本操作 ?單鏈表的查找 get ?單鏈表長度計(jì)數(shù) Count ?單鏈表的的插入 insert ?單鏈表的刪除 delete 下一頁 上一頁 停止放映 第 55 頁 指針的基本操作 ? 設(shè)指針變量 p、 q的定義為： NODE *p， *q； ? 對鏈表的操作實(shí)際上是對指針的操作。 ai ai1 ai+1 ai ai1 ai+1 p p 操作前狀態(tài) 操作后狀態(tài) 下一頁 上一頁 停止放映 第 59 頁 指針操作的舉例 3 p=qnext p指向 q所指結(jié)點(diǎn)的后繼 ai ai1 ai+1 ai ai1 ai+1 q q p p 操作前狀態(tài) 操作后狀態(tài) 下一頁 上一頁 停止放映 第 60 頁 指針操作的舉例 4 pnext=NULL 將指針 p所指結(jié)點(diǎn)與后繼結(jié)點(diǎn)斷開 ai ai1 ai+1 ai ai1 p 操作前狀態(tài) 操作后狀態(tài) p ^ ai+1 下一頁 上一頁 停止放映 第 61 頁 單鏈表的查找算法 ?返回指向第 i個(gè)結(jié)點(diǎn)的指針。 下一頁 上一頁 停止放映 第 62 頁 單鏈表查找示意舉例 命題 : 設(shè)有數(shù)列 {4,5,8,10,21,3