【正文】 維 數(shù) 組 數(shù)組的定義及運算 ?數(shù)組圖示 三 維 數(shù) 組 146 數(shù)組的定義及運算 ?定義： 由 值 和 下標(biāo) 構(gòu)成的有序?qū)ΓY(jié)構(gòu)中的每一個元素都與 一對下標(biāo) 有關(guān)。 試問： (1) 設(shè)有編號為 1,2,3,4,5, 6的六輛列車 , 順序開入棧式結(jié)構(gòu)的站臺 , 則可能的出棧序列有多少種 ? (2) 若進站的六輛列車順序如上所述 , 那么是否能夠得到 435612, 325641, 154623和 135426的出站序列 , 如果不能 , 說明為什么不能 。 else { front=(front+1)%MAXSIZE。 138 void en_cycque(int sq[],int front,int rear,int x){ if(((rear+1)%MAXSIZE)==front) printf(overflow)。 隊列（ QUEUE） 136 0 1 2 3 4 5 rear front J4 J5 J6 0 1 2 3 4 5 J9 J8 J7 front rear 隊列（ QUEUE） J4 J5 J6 0 1 2 3 4 5 rear front 初始狀態(tài) 解決方案： 設(shè)一個標(biāo)志 以區(qū)別隊空、隊滿 ： 隊空： front==rear 隊滿： (rear+1)%M==front ?循環(huán)隊列出入隊圖示 隊空： front==rear 隊滿： front==rear 137 隊列（ QUEUE） ?少用一個元素空間解決方案 ?隊空 rear = front。 隊滿： (rear+1) % maxSize=front。 187。 sq[rear]=x。 rear rear front rear 1 2 3 4 5 0 J1,J2,J3出隊 J1 J2 J3 front front front ? 三、循環(huán)隊列 隊列的順序表示和實現(xiàn) 133 隊列（ QUEUE） ?存在問題 設(shè)數(shù)組維數(shù)為 M，則： ?當(dāng) front=1,rear=M1時 ， 再有元素入隊發(fā)生溢出 —真溢出 ?當(dāng) front 1,rear=M1時 ， 再有元素入隊發(fā)生溢出 —假溢出 解決方案 : ?隊首固定 ， 每次出隊剩余元素向下移動 ——浪費時間 ?循環(huán)隊列 134 ?循環(huán)隊列 基本思想 ： 存儲隊列的數(shù)組被當(dāng)作首尾相接的表處理 ； 讓 sq[0]接在 sq[M1]之后，若 rear+1==M,則令 rear=0。 free(s)。/*指向被刪結(jié)點 */ if(snext == NULL){ QfrontNext = Null。 Qrearnext = p。 }Qnode,*QueuePtr。Q,amp。 隊中元素按 a1， a2， a3， … an的次序入隊，出隊按先進先出的原則進行的 ,因此 a1，a2， a3， … an的次序出隊 front 和 rear的初始值地隊列初始化時均應(yīng)置為 1。 （ 2） w=2 （ 1） w=3 top (3) 輸出： 2, 2 w 1 print(0)。 printf(“ /n” )。 if ( w!=0) { print(w1)。一個過程直接地或間接地調(diào)用自己 169。 free(p)。} 111 棧 （ stack） ?鏈棧的出棧算法 出棧等同于刪除第一個結(jié)點 Status Pop(LinkList * S,datatype *e ){ If(Stop) return ERROR。 pdata = e。 struct node *link。 Stop 。 Stop ++。新 元 素 插 入elements[top]位置 出棧： top1 an a1 a2 ……... 棧底 棧頂 ... 出棧 進棧 棧 s=(a1,a2,……,an) 棧 （ stack） ?棧的圖示 102 棧 （ stack） 棧和線性表類似，也有兩種（順序、鏈?zhǔn)剑崿F(xiàn)方法 103 ?存儲結(jié)構(gòu)定義 define MAXSIZE 6 typedef struct{ datatype elements[MAXSIZE]。s,x) （ 4） 出棧 Pop(amp。新元素插入 elements[top]位置 ?出棧 top1。 棧（ stack） 167。試寫一算法，將 x 插入線性表適當(dāng)位置上，以保持線性表的有序性，并且分析算法的時間復(fù)雜性。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 93 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) b a c p 92 ppriornext = pnext。 167。③ pprior = s。 sdata = x。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?雙向鏈表圖例 87 b c a p ppriornext= p= pnextproir。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?循環(huán)鏈表 操作與單鏈表基本一致 ,循環(huán)條件不同 ?單鏈表 : p或 pnext=NULL ?循環(huán)鏈 : p或 pnext=H h h ^ 85 167。 free(Lb)。 } else{pcnext = pb。amp。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?兩個有序單鏈表合并為一個有序單鏈表 (非遞減 ) MergeList_L(Linklist La,LinkList Lb,LinkList Lc){ pa = Lanext。 //刪除并釋放結(jié)點 *e = q data 。 ++ j。 j= 0。 return OK。} //創(chuàng)建新結(jié)點 ,數(shù)據(jù)為 x,指針為 NULL s=(LinkList * )malloc(sizeof(LinkList))。j i1){p=pnext。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) Status ListInsert_L ( LinkList L, ElemType x, const int i ) { p=L。} if(p) return ERROR。 While(!p amp。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ?頭結(jié)點 ：在單鏈表第一個結(jié)點前附設(shè)的一個結(jié)點。 LNode *h,*p 167。 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 43 存儲地址 數(shù)據(jù)域 指針域 ZHOU 43 LI QIAN SUN WANG WU ZHAO ZHENG 1 7 13 19 25 31 37 13 1 NULL 37 7 19 25 ? 定義：結(jié)點中只含一個指針域的鏈表，也叫單鏈表 例 線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG) 72 LI ZHAO QIAN SUN ZHOU WU ZHENG WANG ^ H 167。} } } 68 167。 while ([j]%2==l) j。 線性表的順序存儲和實現(xiàn) [解 ] 從左向右找到偶數(shù) [i]，從右向左找到奇數(shù) [j]，將兩 者交換；循環(huán)這個過程直到 i大于 j為止 67 167。 return 1。} for(int j = i+1。 i++) if([i] = = itme) break 。 L, const ElemType item){ if( = = 0){ printf( “ L is an empty list!” )。 線性表的順序存儲和實現(xiàn) ?刪 除 一 個 元 素圖示 1 62 內(nèi)存 a1 a2 ai+1 V數(shù)組下標(biāo) 0 1 i1 n2 i n1 1 2 i 元素序號 i+1 n1 n an ai+2 167。j++) v[j1]=v[j]。 n=*p。 ++。 L,const ElemTypeamp。 [i] = item。 i++) if(item [i]) break。 item){ if( = = MaxSize){ printf( “ List overflow!” )。 ++。 } for(i = – 1。 線性表的順序存儲和實現(xiàn) ?向線性表中表頭插入一個元素 InsertFront(Listamp。 } } 53 167。j) v[j]=v[j1]。 n=*p。 free(pData )； 167。 float price。 線性表的順序存儲和實現(xiàn) ?線性表的順序存儲示例 （圖書資料） typedef struct card{ int num。即用一組地址連續(xù)的存儲單元存放一個線性表 ?特點： ? 實現(xiàn)邏輯上相鄰 —物理地址相鄰 ? 實現(xiàn)隨機存取 ?實現(xiàn)： （ 一維 ） 數(shù)組 46 下標(biāo)位置 0 1 … i1 i … n1 … MaxSize1 數(shù)組存貯空間 a1 a2 … ai ai+1 … an … 167。 //在線性表 B中查 x if (k0) {Insert(C,x,j)。 線性表的類型定義 [解 ] 先始化線性表 C，然后依次檢查線性表 A中的每個元素，看它是否在線性表 B中；若在線性表 B中，則將其插入到線性表 C中 . 基本運算 [例 ] 利用線性表的基本運算，編寫將線性表 A和 B中公共元素生成線性表 C的算法 44 167。i++){ x=GetElem(B,i)。A， sqlist B) { //A為引用型參數(shù) int i, k。若在表A中，則將其從 A中刪除 。否則，返回 NULL 40 167。 39 167。 線性表的類型定義 38 167。 若 sq中存在一個或多個值與 x相等的元素 ， 則其作用是返回這些元素的序號的最小值；否則 ， 返回 0。 若1≤i≤ListLen(sq)， 則其作用是返回線性表 sq的第 i個數(shù)據(jù)元素 。其作用是建立一個空表 sq(即建立線性表的構(gòu)架，但不含任何數(shù)據(jù)元素 )。 線性表的類型定義 一、線性表的定義 ?一個線性表可以用一個標(biāo)識符來命名： A=(a1 , a2 , … , ai , ai+1 , … , an) ai可以是基本數(shù)據(jù)類型也可以是 struct 類型 33 167。 s++。 j++。I++){ m=m+I。jn。 26 習(xí)題與練習(xí) 一 4. 設(shè) n 為正整數(shù)，寫出下列程序段的時間復(fù)雜度： （ 1） for(I=1。jk。 T(o)=O(f(n)) 時間復(fù)雜度分為平均時間復(fù)雜度和最壞時間復(fù)雜度 復(fù)雜度的值取規(guī)模函數(shù)最高階 13 算法和算法分析 b 、空間復(fù)雜度： 算法所需存貯空間 S(n)=O(f(n)) 23 13 算法和算法分析 例：分析下列語句段的時間復(fù)雜度 m = 0。 ? DE存儲稱為 節(jié)點 ?關(guān)系存儲： a. 順序存儲 b. 鏈?zhǔn)酱鎯? 17 12 基本概念和術(shù)語 （ 7） DS廣義定義： ? DE 的邏 輯 結(jié) 構(gòu) ? DE 的物 理 結(jié) 構(gòu) ? DE 的 抽 象 運 算 （ 8）基本操作 ? 加工型：查找 刪除 更新 排序 ? 引用型：查找 18 1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等。數(shù)據(jù)項 是數(shù)據(jù)