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