第3單元線性數(shù)據(jù)結構二(已改無錯字)
2022-08-17 10:04:08 本頁面
【正文】 front rear NULL ... an a2 a1 33/53 算法 114 鏈隊列的入隊算法 ? step1 申請建立一個新結點 T。 ? step2 判別 T是否為 NULL。若是 ,表示 ? 隊列已滿 。 ? step3 若非空 ,將 T插入鏈中 ,修改 rear ? 指針。 34/53 鏈隊列的入隊操作 ? addqueue(int x) ? { QNODE *t。 ? t = (QNODE*)malloc(sizeof(QNODE))。 ? if （ t = = NULL） ? { printf(”無可用空間 \n”)。exit(1)。} ? else ? { rear next = t。 rear = t。 ? t data = x。 t next = NULL 。 } ? } 35/53 鏈隊列的出隊操作 ? 兩種情況 : –隊列長度為 1,修改頭結點指針域和隊尾指針。 –隊列長度大于 1,只修改頭結點指針域 an NULL front rear Queue Queue front rear NULL an ^ T Queue Queue front rear rear front a1 an NULL a1 a2 ... a2 ^ ... an NULL 36/53 棧的應用 例 1: 遞歸過程 ? 計算 5的階乘（ 5!=5 4 3 2 1） – { if ( n = = 1) return (1)。 – else return ( n * f(n1))。 – } f(2) f(3) f(4) f(5) top f(1)=1 2*f(1) f(2)=2*f(1) 3*f(2) f(3)=3*f(2) 4*f(3) f(4)=4*f(3) 5*f(4) f(5)=5*f(4) 37/53 棧的應用 例 2:程序的嵌套調(diào)用 – main sub1 sub2 sub3 ? sub2 sub1 main top 38/53 串和數(shù)組 ? 一 . 串及其運算 ? 1. 串的概念 – 1) 定義 : 特殊的線性表 ,每個數(shù)據(jù)元素僅由單個字符組成 , 如 : A=very good – 2) 串的長度 : 串中的字符個數(shù) – 3) 空串 :串長度為 0 – 4) 空格串 : 組成串的元素都是空格 – 5) 子串 :串中任意個連續(xù)字符組成的序列 – 6) 兩個串的相等 : 39/53 ? LENGTH(S) 求串 S的長度 ? SUBSTR(S,start,len) 求 S的子串 ? CONCAT(S1,S2) – S2聯(lián)接在 S1末尾 ? INDEX(S1,S2) –確定 S2在 S1中的位置 ? REPLACE（ S1， S2， S3） –用 S3替換串 S1中所有與串 S2相等且不重疊的子串 40/53 二 .串的存儲結構 ? 1. 順序存儲結構 ? 用連續(xù)存儲單元存儲串的字符序列 ? 使用字編址方式時，設 1字 4個字節(jié) ,則 : ? (1)非緊縮存儲 :一個字的存儲單元中只存放1個字符。 ? 特點：存儲密度低 ,浪費空間 ? (2) 緊縮存儲 一個單元中存放 4個字符； ? 特點：節(jié)省空間 – 訪問時要花費分離時間 41/53 2. 鏈表存儲結構 ? (1) 結點由數(shù)據(jù)域和指針域組成 ? 圖 138 ? (2) 指針域通常兩個字節(jié) ? 若數(shù)據(jù)域占一個字節(jié) : ? 有效存儲密度 =1/3 ? 若數(shù)據(jù)域占四個字節(jié) : ? 有效存儲密度 =4/6=2/3 42/53 –堆結構 :一種動態(tài)存儲結構，定義一個很大的連續(xù)空間和相應的指針結構。 –指針用來指示串在堆中的位置 –例如， a=?BEI?， b=? JING?， c=??，d=?SHANGHAI?； 串名串長 起始地址 a 3 1 b 5 4 c
職業(yè)教育相關推薦
鄂ICP備17016276號-1