資 料 結 構 鄭 彬
資 料 資 料 : 可 以 拿 來 利 用 的 一 些 資 訊 例 如 : 旅 遊 資 訊 氣 象 資 料 考 試 成 績 考 古 題 網 頁 報 紙 談 天 廣 告 時 刻 表 電 腦 展 的 價 目 表 導 遊 地 圖 金 融 房 地 產 軍 事 交 通 商 業 市 場 科 技 新 知 商 品 價 格 各 類 書 籍 收 支 帳 單 醫 學 電 視 收 音 機 廣 告 看 板 標 籤 警 告 標 誌 說 明 書 使 用 手 冊 雜 誌 報 告 記 錄 路 標 示 範 聲 音 影 像 圖 案
取 得 資 料 新 聞 記 者 會 取 得 那 些 資 料?( 政 治 經 濟 體 育 影 劇 文 學 人 物 活 動 選 舉 ) 考 生 會 取 得 那 些 資 料? ( 大 學 高 考 證 照 特 考 ) 求 職 者 會 取 得 那 些 資 料? ( 工 業 商 業 薪 資 時 間 ) 檢 察 官 會 取 得 那 些 資 料? ( 民 事 刑 事 法 律 規 定 ) 商 人 會 取 得 那 些 資 料? ( 外 匯 股 市 法 律 政 經 ) 工 程 師 會 取 得 那 些 資 料? ( 材 料 尺 寸 規 格 工 具 ) 病 人 醫 生 會 取 得 那 些 資 料? ( 血 壓 心 跳 體 溫 )
資 料 項 資 料 項 : 構 成 資 訊 的 一 些 元 素, 例 如 計 算 利 息 資 料 項 值 資 料 項 值 本 金 50,000 姓 名 張 三 年 利 率 4% 學 號 13456 年 期 3 班 級 子 一 甲 資 料 項 : 資 料 的 項 目 或 是 資 料 的 欄 位 名 稱
資 料 型 態 資 料 的 表 示 方 式 : 例 :100 元 =10 個 10 元 =100 個 1 元 =0 個 5 元 = 個 50 元 ( 可 用 不 同 的 形 式 表 示 同 一 個 值 ) 例 : 5 元 =1 個 代 幣 (token) 字 元 集 :ASCII EBCDIC BIG-5 ( 利 用 數 值 來 表 示 一 個 圖 像 的 文 字 ) 圖 片 影 片 的 壓 縮 檔 案 ( 若 不 壓 縮 則 會 造 成 資 料 的 傳 輸 時 間 增 加 及 需 要 較 大 的 記 憶 體 空 間 ) MP3 音 樂 ( 壓 縮 檔 案 ) 網 路 協 定 ( 雙 方 都 同 意 的 規 則 )
c 語 言 的 資 料 型 態 英 文 型 態 名 稱 中 文 型 態 名 稱 所 佔 記 憶 體 數 量 char int 字 元 整 數 1 byte 4 bytes 不 含 小 數 點 的 數 值 float 單 精 度 浮 點 4 bytes double 双 精 度 浮 點 8 bytes void 沒 有 傳 回 值 無 含 有 小 數 點 的 數 值 重 點 複 習
變 數 內 容 解 讀 當 變 數 宣 告 之 後, 編 譯 程 式 需 決 定 : 1 起 始 位 址 ( 資 料 放 在 記 憶 體 的 什 麼 地 方 ) 所 佔 memory 的 數 量, 例 :char:1, int:4, float:4, double:8 (bytes) 3 解 釋 memory 內 容 的 方 法, 例 :011010...011 (char? int? float? double?) 錯 誤 的 解 讀 視 同 亂 碼 為 何 要 一 定 指 出 變 數 的 資 料 形 態? 因 為 需 要 知 道 有 多 少 位 元 需 要 解 讀, 以 及 解 讀 的 方 式
c 語 言 的 資 料 型 態 字 元 : 英 文 字 元 : 即 為 鍵 盤 上 的 按 鍵 (a,b,r,#,! 等 ) 中 文 字 元 : 需 要 輸 入 法 輸 入 整 數 : 陣 列 的 索 引 值, 不 含 小 數 點 的 數 值, 一 般 計 算 物 件 數 量 用 的 值 ( 例 : 1 5 10 300) float: 含 有 小 數 點 的 數 值 ( 例 : 3.14159 5.6-3 ) double: 含 有 小 數 點 的 數 值, 多 了 可 讀 的 有 效 數 值, 通 常 用 在 求 sin, tan, log 等 ( 若 不 使 用 double, 則 在 迴 圈 等 環 境 中, 因 為 反 覆 的 處 理, 精 密 度 會 下 降 太 多 )
結 構 化 資 料 結 構 化 資 料 : 將 資 料 依 據 規 則 組 成 另 一 種 資 料 例 如 : 姓 與 名 可 以 組 成 一 個 人 名 成 績 單 : 姓 名 國 文 分 數 英 文 分 數 平 均 成 績 名 次 收 支 表 : 收 入 支 出 時 間 統 一 發 票 : 列 出 購 買 清 單 金 額 銷 售 日 期 發 票 號 碼 班 機 時 間 表 : 到 達 時 間 離 開 時 間 閘 門 班 次 目 的 地 節 目 流 程 ; 第 一 幕 表 演 第 二 幕 表 演 第 三 幕 表 演 菜 單 : 菜 名 材 料 內 容 美 食 成 品 照 片 價 目 彩 卷 : 對 奬 號 碼 對 奬 日 期 期 別 彩 卷 名 稱
電 腦 處 理 的 資 料 早 期 電 腦 變 數 文 字 數 值 名 稱 敘 述 字 元 離 散 (int) ( 速 度 快 ) 連 續 (float double) ( 速 度 慢 ) 圖 片 影 片 動 畫 聲 音 多 媒 體 向 量 文 字 文 字 顏 色 網 路 ( 網 頁 email...) 現 代 電 腦 再 加 上 的 功 能 重 點 複 習
資 料 結 構 課 程 所 討 論 的 項 目 資 料 結 構 種 類 陣 列 串 列 ( 鏈 結 串 列 ) 堆 疊 與 佇 列 樹 狀 結 構 ( 二 元 樹 ) 排 序 法 尋 找 法 圖 形 結 構
演 算 法 利 用 指 令 來 完 成 一 件 工 作, 具 有 五 大 特 性 : 輸 入 : 使 用 預 設 值 或 有 數 個 輸 入 輸 出 : 至 少 有 一 個 輸 出 ( 通 常 為 螢 幕 )( 音 效 語 音 燈 光 等 ) 明 確 性 : 每 一 個 指 令 必 須 明 確 定 義 其 功 能 ( 例 :for, if, switch, break ) 有 限 性 : 執 行 的 步 驟 是 可 以 用 手 數 出 來 的 ( 註 : 不 論 其 值 是 成 千 上 萬 ) ( 註 : 不 能 包 含 無 限 迴 圈 ) ( 註 : 可 用 圖 表 顯 示 執 行 順 序, 可 以 用 紙 筆 一 步 一 步 的 追 蹤 其 結 果 ) 有 效 性 : 必 需 確 實 能 解 決 問 題 ( 註 : 没 有 bug)
虛 擬 碼 使 用 近 似 日 常 生 活 的 語 言, 來 表 達 一 個 程 式 的 流 程, 本 身 不 能 被 執 行 ( 此 點 與 流 程 圖 一 樣 ) 例 : Begin program Input integers X and Y If X > Y then output X Otherwise output Y End program 輸 入 整 數 X 及 Y, 若 X 大 於 Y, 則 輸 出 X, 其 他 情 形 (X 等 於 Y 或 X 小 於 Y), 則 輸 出 Y
陣 列 一 個 有 序 的 索 引 與 值 的 集 合, 一 般 表 示 成 < 索 引, 值 > 的 形 式 陣 列 的 宣 告 1 資 料 型 態 陣 列 名 稱 3 陣 列 大 小 例 : char string[str_size]; // 宣 告 字 元 陣 列 int array[5]; // 宣 告 整 數 陣 列 double *parray[5]; // 宣 告 雙 精 指 標 陣 列 int x[5][]; // 宣 告 二 維 整 數 陣 列
陣 列 的 應 用 螢 幕 的 圖 點 座 標 GPS 座 標 試 算 表 影 像 處 理 工 程 設 計 ( 橋 樑 建 築 物 ) IC 設 計 製 圖 文 書 排 版 處 理 記 憶 體 管 理 印 表 機 數 位 相 機 試 想 一 部 電 腦 不 能 使 用 陣 列 會 怎 樣?
陣 列 自 定 的 陣 列 名 稱 int t1[3]; 等 於 一 次 宣 告 三 個 變 數 資 料 型 態 t1[0], t1[1], t1[] 陣 列 格 數 memory 需 求 量 為 1 bytes char 字 元 1 byte int 整 數 4 bytes 3 格 X 4byte/ 格 = 1 bytes float 單 精 度 浮 點 4 bytes double 双 精 度 浮 點 8 bytes
一 維 陣 列 初 值 的 設 定 例 : int data[ ]={7, 5,37, 10}; 長 度 可 以 不 寫, 編 譯 器 會 自 動 填 入 4 四 個 初 值 data[0]=7; data[1]=5; data[]=37; data[3]=10;
泡 沫 排 序 法 ( 排 列 成 由 大 到 小 ) main() { int i,j,tmp, s[]={1,,3,4,5}; for(i=0;i<4;i++) { for(j=0;j<4;j++) if(s[j]<s[j+1]) } 欲 排 序 的 數 列 亦 可 寫 成 for(j=0;j<4-i;j++) 環 狀 交 換 {tmp=s[j]; s[j]=s[j+1]; s[j+1]=tmp;} } for(i=0;i<5;i++) printf("\n%d", s[i]); printf("\n"); 加 上 getche(); 指 令 可 讓 DOS 畫 面 停 下 來
泡 沫 排 序 法 環 狀 交 換 : tmp=s[j]; s[j]=s[j+1]; s[j+1]=tmp; 1 s[j] tmp 交 換 s[j+1] 3 重 要! 二 個 變 數 的 內 容 不 能 直 接 交 換, 一 定 要 經 由 第 三 者
i i=0,j 迴 圈 結 束 後 的 結 果 i=1,j 迴 圈 結 束 後 的 結 果 i=,j 迴 圈 結 束 後 的 結 果 j 泡 沫 排 序 法 0 1 3 4 1 3 4 5 1 3 1 4 1 5 1 3 4 5 1 3 4 5 3 4 5 1 4 3 5 3 4 5 3 1 5 4 5 4 3 1 j 的 值 欲 排 序 的 數 列 決 定 了 第 一 個 最 小 值 i=3,j 迴 圈 結 束 後 的 結 果
上 機 實 作 ( 使 用 Microsoft Visual Studio 6.0) 開 始 所 有 程 式 Microsoft Visual Studio 6.0 Microsoft Visual C++ 6.0 File New 按 Files 頁 籤 選 Text File File 欄 位 鍵 入 test.c Location 欄 位 選 擇 可 寫 入 的 目 錄, 例 如 temp OK 回 到 簡 報 軟 體 編 輯 全 選 用 Ctrl-c 拷 貝 程 式 碼 用 Ctrl-v 貼 到 VC++ 工 作 區 Build Build(ALL) Execute 查 看 執 行 結 果, 按 任 一 鍵 跳 回 VC++ 一 定 要 打 上 副 檔 名 (*.c)
若 使 用 Microsoft Visual Studio.NET 00 003 檔 案 新 增 專 案 檔 案 類 型 選 (Visual C++/NET) 在 範 本 中 選 空 專 案 (.NET) 名 稱 T 位 址 ( 使 用 瀏 覽 找 尋 目 錄 ) 專 案 加 入 新 項 目 選 文 字 檔 (.TXT) 名 稱 XX.c( 副 檔 名 需 用.c) 開 啟 ( 此 時 在 螢 幕 右 邊 方 案 總 管 中 原 始 程 檔 目 錄 內 可 見 此 檔 ) 在 XX.c 中 打 入 程 式 ( 或 將 欲 執 行 的 程 式 碼 貼 上 ) 按 一 下 方 案 總 管 中 的 T 名 稱 ( 在 第 二 行 ) 再 按 主 選 單 的 專 案 屬 性 組 態 屬 性 一 般 在 使 用 Managed Extension 選 項 內 將 是 改 為 否 確 定 偵 錯 啟 動 ( 或 直 接 按 F5) 在 程 式 結 束 前 加 上 getche(); 可 停 留 畫 面
二 維 陣 列 每 一 列 佔 用 三 格 float data[3][3]; 行 (j) 陣 列 的 名 稱 同 時 也 代 表 了 陣 列 的 起 始 位 址 列 (i) 0,0 1,0,0 0,1 1,1,1 0, 1,, 水 平 為 列, 垂 直 為 行 列 的 編 號 行 的 編 號
二 維 陣 列 0,0 0,1 0, 行 (j) 列 (i) 1,0,0 1,1,1 1,, 0,0 1,0 0,1 1,1 0, 1,,0,1, 水 平 為 列, 垂 直 為 行 每 一 列 佔 用 三 格, 每 一 行 也 佔 用 三 格
二 維 陣 列 二 維 陣 列 在 記 憶 體 中 仍 是 排 列 成 一 維 陣 列 的 形 式 二 維 陣 列 的 範 例 : 某 元 素 起 始 位 址 = (i * 每 列 格 數 + j) * byte/ 格 + 陣 列 起 始 位 址 data ( 起 始 位 址 ) 二 維 陣 列 每 一 列 佔 多 少 格 0 1 列 0,0 0,1 0, 1,0 1,1 1,,0,1, 4 bytes +8 +1 +16 +0 +4 +8 +3 亦 可 char:1, int:4, float:4, double:8
絕 對 位 址 與 相 對 位 址 絕 對 位 址 : 在 坐 標 上 實 際 的 位 址 相 對 位 址 : 與 某 一 已 知 基 準 點 ( 參 考 點 ) 的 偏 移 量
二 維 陣 列 公 式 絕 對 位 址 某 元 素 起 始 位 址 = 二 維 陣 列 起 始 位 址 + (i * 每 列 格 數 + j) * byte/ 格 相 對 位 址
初 值 的 設 定 : 二 維 陣 列 初 值 設 定 int map[3][3]={ {1,,3}, 或 {4,5,6}, {7,8,9}}; int map[3][3]={1,,3,4,5,6,7,8,9}; 內 部 括 號 是 給 人 看 的 九 個 元 素
三 維 陣 列 初 值 設 定 C=4 int map[3][][4]={ { { 1,, 3, 4}, { 5, 6, 7, 8} }, { {11,1,13,14}, A B C {15,16,17,18} }, { {1,,3,4}, {56,3,11,99} } }; B= A=3
三 維 陣 列 初 值 設 定 int map[3][][4]= { { { 1,, 3, 4}, { 5, 6, 7, 8} }, { {11,1,13,14}, {15,16,17,18} }, { {1,,3,4}, {56,3,11,99} } }; 或 是 : int map[3][][4]={ 1,, 3, 4, 5, 6, 7, 8,11,1,13,14, 15,16,17,18, 1,,3,4,56,3,11,99 }; 三 維 陣 列 在 記 憶 體 中 仍 是 排 列 成 一 維 陣 列 的 形 式
三 維 陣 列 起 始 值 A( i, j, k) = l0 + ( i l1) uu3 * d + ( j l) u3 * d + ( k l3 )* d 起 始 位 址 跳 掉 多 少 個 面 長 乘 寬 形 成 面 跳 掉 多 少 個 長 方 形 長 方 形 寬 度 由 左 至 右 的 徧 移 量 char d=1 int d=4 float d=4 double d=8
u 的 起 始 長 方 形 u 1 * 第 i 面 u u 3 的 起 始 格 u 3 u 1 的 起 始 面
n 維 陣 列 公 式 d l i d u l i d u u u l i d u u u u l i l i i i A n n n n n n n n ) * ( * ) (... *... ) ( *..... ) ( ),..., ( 1 1 4 3 4 3 1 1 0 1 + + + + + = 陣 列 起 始 位 址 byte/ 格 每 列 格 數 若 起 點 不 是 由 0 開 始
m - -3-3 - -1 0 1 54310-1 -4 n=7 m n A(-3:5,-4:) 的 起 始 位 址 為 A(-3,4)=100, 以 列 為 主 排 列, 請 問 A(1,1) 所 在 的 位 址, 假 設 d=1 m=5-(-3)+1=9, l 1 = -3 n=-(-4)+1=7, l = -4 代 入 公 式 A(i,j) = l 0 + ( i-l 1 )nd + ( j-l )d A(1,1)=100+(1-(-3))*7*1+(1-(-4))*1 =100+4*7+5 =133 亦 可 用 手 數 出 來
有 一 個 三 維 陣 列 u -1-4310 0 1 3-3 - -1 0 1 u 1 A(-3:,-:4,0:3) 以 列 為 主 排 列, 陣 列 的 起 始 值 為 318, 求 (1,3,) 所 在 的 位 址, 假 設 d=1 u 3 u 1 =6, u =7, u 3 =4 A(1,3,)=l 0 +(i-i 0 )*u *u 3 *d+(j-j 0 )*u 3 *d+(k-k 0 )*d =318+(1-(-3)*7*4*1+(3-(-))*4+(-0) =45
九 九 乘 法 表 的 列 印 main() { int i,j,data; for(i=1;i<10;i++) { for( j=1 ; j<10 ; j++) { data= i * j; printf("%d*%d=%d, ",i,j,data); } printf("\n"); i 迴 圈, 外 迴 圈 j 迴 圈, 內 迴 圈 } } 跳 行 上 機 作 業
九 九 乘 法 表 的 列 印 1*1= 1, 1*=, 1*3= 3, 1*4= 4, 1*5= 5, 1*6= 6, 1*7= 7, 1*8= 8, 1*9= 9, *1=, *= 4, *3= 6, *4= 8, *5=10, *6=1, *7=14, *8=16, *9=18, 3*1= 3, 3*= 6, 3*3= 9, 3*4=1, 3*5=15, 3*6=18, 3*7=1, 3*8=4, 3*9=7, 4*1= 4, 4*= 8, 4*3=1, 4*4=16, 4*5=0, 4*6=4, 4*7=8, 4*8=3, 4*9=36, 5*1= 5, 5*=10, 5*3=15, 5*4=0, 5*5=5, 5*6=30, 5*7=35, 5*8=40, 5*9=45, 6*1= 6, 6*=1, 6*3=18, 6*4=4, 6*5=30, 6*6=36, 6*7=4, 6*8=48, 6*9=54, 7*1= 7, 7*=14, 7*3=1, 7*4=8, 7*5=35, 7*6=4, 7*7=49, 7*8=56, 7*9=63, 8*1= 8, 8*=16, 8*3=4, 8*4=3, 8*5=40, 8*6=48, 8*7=56, 8*8=64, 8*9=7, 9*1= 9, 9*=18, 9*3=7, 9*4=36, 9*5=45, 9*6=54, 9*7=63, 9*8=7, 9*9=81, Press any key to continue 上 機 作 業
矩 陣 相 乘 1 1 3 1 1 1 1 * 4 3 3 1 3 1 C[0][0] = A[0][0] * B[0][0] + A[0][1] * B[1][0] + A[0][] * B[][0] = 14 上 機 作 業
矩 陣 相 乘 ( 陣 列 型 式 ) main() { int a[][3]={{1,,3},{,1,3},{3,,4}}; int b[][3]={{1,1,1},{,,1},{3,1,1}}; int c[3][3], i,j,k; for(i=0;i<3;i++)for(j=0;j<3;j++) {c[i][j]=0; for(k=0;k<3;k++) c[i][j] += a[i][k] * b[k][j];} 利 用 i 索 引 值 來 控 制 a 陣 列 的 列 利 用 k 索 引 值 來 控 制 a 與 b 陣 列 的 對 應 元 素 printf("\n"); 利 用 j 索 引 值 來 控 制 b 陣 列 的 行 for(i=0;i<3;i++) {for(j=0;j<3;j++)printf("%d, ",c[i][j]);printf("\n");} } 上 機 作 業 14 8 6 13 7 6 19 11 9
矩 陣 相 乘 ( 指 標 型 式 ) main() { 注 意 到 二 維 陣 列 函 數 的 傳 遞 int a[][3]={{1,,3},{,1,3},{3,,4}}; int b[][3]={{1,1,1},{,,1},{3,1,1}}; 一 定 要 先 清 除 int c[][3]={0,0,0,0,0,0,0,0,0}; int i,j,k; void TT(int a[][3],int b[][3],int c[][3],int i, int j, int k); for(i=0;i<3;i++) for(j=0;j<3;j++) for(k=0;k<3;k++) TT(a,b,c,i,j,k); printf("\n"); for(i=0;i<3;i++) 呼 叫 函 數 {for(j=0;j<3;j++)printf("%d, ",c[i][j]);printf("\n");} } void TT(int a[][3],int b[][3],int c[][3],int i, int j, int k) { *(*(c+i)+j) += *(*(a+i)+k) * *(*(b+k)+j); } 使 用 c[i][j]+=a[i][j]*b[k][j] 亦 可 上 機 作 業 函 數 在 使 用 之 前 必 需 要 事 先 宣 告 14 8 6 13 7 6 19 11 9
結 構 指 令 結 構 與 陣 列 struct student { int score; 自 定 的 結 構 名 稱 數 字 成 績, 例 :85,7 char grade; }name_a[50], name_b[45]; 結 構 為 物 件 導 向 程 式 中 物 件 的 前 身 文 字 成 績, 例 :A,B 甲 班 50 位 同 學 乙 班 45 位 同 學 或 這 樣 宣 告 struct student name_a[50]; struct student name_b[45]; 重 點 複 習
結 構 與 陣 列 struct student { int score; char grade; } name_a[50], name_b[45]; 資 料 結 構 的 架 構, 有 若 工 程 用 的 藍 圖 一 個 建 築 的 藍 圖 可 以 複 製 出 多 個 建 築 物 實 體 複 製 出 50 個 實 體 複 製 出 45 個 實 體 或 這 樣 宣 告 struct student name_a[50]; struct student name_b[45]; 重 點 複 習
結 構 與 陣 列 struct student { int score; char grade; }name_a[50], name_b[45]; 為 何 一 個 結 構 需 要 命 名? 因 為 在 一 個 程 式 中 可 能 會 有 一 個 以 上 的 結 構, 若 不 命 名, 則 在 以 後 的 應 用 中 就 不 知 道 是 要 引 用 那 一 個 結 構 指 名 使 用 以 student 命 名 的 結 構 或 這 樣 宣 告 struct student name_a[50]; struct student name_b[45]; 重 點 複 習
巢 狀 結 構 struct student {int score; char grade;}; struct course { struct student english; struct student computer; }name; 巢 狀 結 構 : 結 構 中 含 有 另 一 個 結 構 例 : name.english.score=85; // 某 人 的 英 文 數 字 成 績 是 85 分 name.computer.score=9; // 某 人 的 計 概 成 績 是 9 分 name.english.grade='a ; // 某 人 的 英 文 文 字 成 績 得 到 A
重 點 回 顧 何 謂 資 料? 何 謂 資 料 項? 資 料 型 態 分 為 那 幾 種? 何 謂 結 構 化 資 料? 資 料 結 構 所 討 論 的 項 目 有 那 些? 何 謂 演 算 法? 何 謂 虛 擬 碼? 何 謂 陣 列? 何 謂 環 狀 交 換? 請 列 出 n 維 陣 列 的 公 式? 當 變 數 宣 告 之 後, 編 譯 程 式 需 決 定 那 些 事 情?
c 語 言 表 示 是 非 的 方 式 非 0 正 負 整 數 0 是 (Ture) (YES) 非 (False) (NO) 唯 一 的 0 代 表 測 試 失 敗 數 值 0 看 起 來 像 是 英 文 的 NO 的 O 重 點 複 習
宣 告 鏈 結 的 資 料 結 構 struct node { char data; 自 定 的 結 構 名 稱, node 為 節 點 之 意 } struct node *next; DATA NEXT 自 定 的 指 標 變 數 名 稱, 指 標 的 內 容 為 一 位 址 儲 存 的 資 料 NEXT 欄 位 有 如 信 封 上 的 地 址 欄 位 宣 告 變 數 :struct node *AV; 重 點 複 習
宣 告 鏈 結 的 資 料 結 構 struct node { char data; } struct node *next; 資 料 結 構 的 架 構, 有 若 工 程 用 的 藍 圖 一 個 建 築 的 藍 圖 可 以 複 製 出 多 個 建 築 物 實 體 宣 告 變 數 :struct node *AV; 使 用 指 標 變 數 以 便 於 指 出 該 節 點 所 在 的 位 址, 目 前 其 內 容 是 空 的 重 點 複 習
鏈 結 DATA DATA NEXT DATA NEXT DATA NEXT NEXT 欄 位 指 向 下 一 個 節 點 所 在 的 位 址 每 個 節 點 可 能 分 散 在 記 憶 體 各 部 分
鏈 結 記 憶 體 位 址 A F500 F500 B F400 CE5 D C CE5 F400
鏈 結 串 列 與 陣 列 的 比 較 空 間 : 時 間 : 陣 列 需 事 先 宣 告 陣 列 大 小, 固 定 排 列 位 置 陣 列 是 以 固 定 的 形 式 配 置 記 憶 體, 所 以 可 以 利 用 索 引 值 很 快 的 推 算 出 資 料 所 在 的 位 址, 效 率 佳 鏈 結 串 列 否, 不 固 定 排 列 位 置 需 知 鏈 結 的 起 始 位 址, 再 使 用 循 序 搜 尋, 找 尋 資 料 所 在 的 位 址, 影 响 隨 機 存 取 的 效 率
記 憶 體 與 陣 列 電 腦 的 記 憶 體 本 身 就 是 一 個 有 序 的 陣 列, 其 有 序 的 編 號 稱 為 位 址, 陣 列 與 記 憶 體 均 可 儲 存 值, 稱 為 資 料
指 標 利 用 變 數 來 儲 存 某 變 數 的 位 址 或 某 陣 列 的 起 始 位 址 陣 列 起 始 位 址 1000 +0 +1 + +3 +4 +5 +6 +7 +8 +9 位 址 計 數 器 101 0 1 表 示 工 作 到 記 憶 體 的 什 麼 地 方
指 標 日 常 生 活 常 用 到 的 指 標, 能 夠 獨 一 無 二 的 指 向 特 定 物 件 例 如 : 電 話 號 碼 手 機 號 碼 地 址 身 分 證 字 號 學 號 車 牌 號 碼 DNA 電 腦 帳 號 與 密 碼 存 款 帳 號 GPS 的 經 緯 度 座 標 商 品 條 碼... 商 品 的 serial number 發 票 號 碼 信 用 卡 號 碼 鈔 票 號 碼 護 照 號 碼 新 年 ( 一 月 一 日 ) 帳 單 條 碼 護 照 條 碼 身 分 證 條 碼 指 標 的 功 能 不 是 C 語 言 才 有 的 功 能
指 標 範 例 區 塊 的 搬 動 : 必 須 已 知 1. 區 塊 的 起 始 位 址 (1000). 搬 動 的 數 量 (30) 格 * (byte/ 格 ) 3. 新 的 起 始 位 址 (000) ptr1=1000; ptr=000; *ptr=*ptr1++; 需 加 一 迴 圈 原 始 資 料 的 指 標 1000 指 標 內 的 內 容, 就 是 位 址 指 標 的 本 身, 是 一 個 變 數 目 的 地 的 指 標 copy 000 當 指 標 變 數 的 內 容 變 動 時, 就 表 示 所 指 向 的 位 址 也 跟 著 變 動 上 機 作 業
指 標 重 點 複 習 電 腦 cpu 中, 會 有 一 個 位 址 計 數 器 位 址 計 數 器 的 內 容, 就 是 被 選 中 的 記 憶 體 格 子 (byte) 的 號 碼, 也 就 是 該 格 子 的 位 址 此 時 稱 為 該 計 數 器 指 向 了 該 格 子 在 軟 體 環 境, 可 有 類 似 的 功 能 此 模 擬 計 數 器 在 c 語 言 程 式 內, 由 一 變 數 來 代 表 而 該 變 數 具 有 指 向 的 功 能, 故 稱 為 指 標 變 數 指 標 變 數 的 內 容, 就 是 一 個 位 址
C 語 言 變 數 的 分 類 變 數 指 標 變 數 儲 存 位 址 一 般 變 數 儲 存 數 字 ( 整 數, 浮 點 數 ) 文 字 ( 字 元, 字 串 )
指 標 變 數 的 宣 告 在 宣 告 時, 在 變 數 的 名 稱 前 加 上 * 記 號 例 : char *ptr; int *ptr; float *ptr3; double *ptr4; 宣 告 字 元 指 標 變 數 宣 告 整 數 指 標 變 數 宣 告 浮 點 指 標 變 數 宣 告 雙 精 指 標 變 數 ptr: pointer ( 指 標 )
指 標 在 一 般 變 數 前, 加 上 & 記 號, 表 示 找 出 該 變 數 在 記 憶 體 的 位 址 例 : char *ptr, ch; ptr = &ch; ch 變 數 所 在 的 位 址, 存 到 了 指 標 變 數 ptr 中 位 址 (300) ptr 300 300 上 機 作 業 ch
指 標 在 非 宣 告 的 情 況 下, 指 標 變 數 前 若 有 * 記 號, 則 代 表 找 出 該 指 標 變 數 所 指 的 那 個 位 址 上 的 內 容 *ptr 比 較 : char *ptr; 宣 告 字 元 指 標 變 數
main() 指 標 變 數 { char *ptr, ch='x'; ptr=&ch; printf("%c\n", *ptr); *ptr='y'; printf("%c\n",ch); printf("%c\n", *ptr); } 指 標 變 數 所 指 的 位 址 上 的 內 容 指 標 應 用 範 例 ptr 一 般 變 數 300 必 須 要 設 定 ptr 的 初 值 印 x,*ptr 與 ch 在 此 時 為 同 義 更 改 ptr 所 指 的 位 址 上 的 內 容 為 字 元 y 印 y 印 y 300 x 上 機 作 業 ch
指 標 變 數 指 標 變 數 在 使 用 之 前, 一 定 要 給 一 個 位 址, 否 則 它 會 亂 指, 因 而 造 成 當 機 由 於 指 標 變 數 容 易 造 成 bug, 可 在 網 路 上 執 行 的 軟 體 多 不 支 援 指 標 變 數 的 功 能 C 語 言 原 先 是 用 來 設 計 UNIX 作 業 系 統, 故 有 指 標 變 數 的 功 能
配 置 記 憶 體 char *p; float f, *pf; p=malloc(100); pf=(float *)malloc(sizeof(float)); *pf=0.54; 傳 回 值 為 4, 因 為 一 個 浮 點 佔 4 BYTE 請 求 保 留 100 bytes 大 小 的 記 憶 體 區 塊 p 上 機 作 業 配 置 100 bytes 記 憶 體 區 塊 將 傳 回 值 的 資 料 型 態 改 為 浮 點 指 標 的 型 態 ( 原 來 的 型 態 為 char) malloc: 配 置 記 憶 體 sizeof: 記 憶 體 數 量 pf 0.54 配 置 4 bytes 記 憶 體 區 塊
加 一 個 新 節 點 到 鏈 結 最 前 端 1 3 4 void insert_first(item) int item; { struct node *temp; } temp=(struct node *)malloc(sizeof(struct node)); if(!temp){printf(" 記 憶 體 不 足!\n"); exit(1);} temp->data=item; temp->next=head; head=temp; 1 temp 4 head struct node { char data; 指 向 鏈 結 的 起 點 struct node *next; } 產 生 一 個 新 節 點 原 本 鏈 結 的 起 點 3 填 入 item 資 料 item data next 上 機 作 業
删 除 p 節 點 的 前 一 個 節 點 5 1 3 int delete_before(struct node *p) {struct node *r1, *r; int val; a 4 } if(p==null head==null p==head) printf(" 節 點 不 正 確!\n"); r1=r=head; while((r1->next!=p)&&(r1->next!=null)) b { r=r1; r1=r1->next; } if(r1->next==p) // 確 認 p 節 點 存 在 {r->next=r1->next; // 將 r1 由 鏈 結 中 刪 除 val=r1->data; // 取 出 資 料 free(r1); // 歸 還 記 憶 體 給 OS return val;} else {printf(" 找 不 到 p 節 點!\n"); exit(1);} 由 鍵 結 的 起 點 走 到 p 節 點 前 的 二 個 節 點 若 為 yes, 則 己 到 達 鏈 結 終 點,p 節 點 並 不 存 在 在 p 節 點 前 結 束 while 迴 圈 上 機 作 業
删 除 p 節 點 的 前 一 個 節 點 head 標 示 出 鏈 節 的 起 點 data next 1 r1 r 3 p r a r1 b val 4 5 free(r1) 歸 還 記 憶 體 給 OS 鏈 結 終 點 r1 指 向 欲 删 除 的 節 點 取 出 資 料
重 點 回 顧 何 謂 指 標 變 數? 試 述 c 語 言 表 示 是 非 的 方 式? 請 問 變 數 的 分 類 可 分 為 那 些? 試 宣 告 最 簡 單 的 鏈 結 資 料 結 構 請 比 較 鏈 結 串 列 與 陣 列 的 差 異 點? 配 置 記 憶 體 與 釋 放 記 憶 體 的 指 令 為 何? 試 用 c 語 言 寫 出 加 一 個 新 節 點 到 鏈 結 最 前 端 的 程 式 碼 試 用 c 語 言 寫 出 删 除 p 節 點 的 前 一 個 節 點 的 程 式 碼
堆 疊 與 佇 列 (Stack and Queue) 堆 疊 : 先 進 後 出, 後 進 先 出 類 似 於 一 疊 盤 子, 先 放 進 的 盤 子 被 壓 在 最 下 面, 最 後 才 能 取 出, 而 最 後 放 進 的 盤 子, 在 最 上 面, 將 是 第 一 個 被 取 出 的 input/output 端 d c b a 同 一 個 出 入 口 例 : 超 商 貨 架 物 品 放 置 方 式, 電 梯 人 員 進 出
堆 疊 與 佇 列 佇 列 : 類 似 於 排 隊, 排 在 排 頭 的 將 先 被 服 務, 排 在 排 尾 的, 最 後 才 被 服 務 output input a b c d e f 排 頭 排 尾
堆 疊 與 佇 列 堆 疊 : 佇 列 : d c b a TOP( 取 出 端 與 放 入 端 ) 例 : 儲 存 副 程 式 到 主 程 式 的 位 址 front 取 出 端 a b c d e f rear 放 入 端 放 入 端 : INPUT 取 出 端 : OUTPUT 例 如 : 作 業 系 統 印 表 機 modem 的 緩 衝 區 硬 碟 緩 衝 區
堆 疊 程 式 範 例 #define STACKSIZE 5 struct stack{ int top; 堆 疊 的 指 標 int items[stacksize]; } struct stack s; // 宣 告 堆 疊 變 數 利 用 陣 列 來 當 作 堆 疊 儲 存 資 料 的 地 方 傳 送 該 堆 疊 的 位 址 create_stack(struct stack *ps) { ps->top=-1;} // 負 1 代 表 空 的 堆 疊, 呼 叫 方 式 create_stack(&s); push(struct stack *ps, int x) // 加 資 料 到 堆 疊 { if(ps->top==stacksize-1) // 不 能 超 出 範 圍, 否 則 可 能 影 響 到 其 他 程 式 {printf("%s", " 堆 疊 溢 出!"); exit(1); } else ps->items[++(ps->top)]=x; // 先 加 後 存 } 堆 疊 的 指 標 說 明 圖 在 後 面
堆 疊 程 式 範 例 pop(struct stack *ps) { if(isempty(ps)) {printf("%s"," 堆 疊 是 空 的!"); exit(1);} return(ps->item[ps->top--]); // 先 取 後 減 } 堆 疊 的 指 標 將 取 出 的 資 料 傳 回 給 呼 叫 程 式 說 明 圖 在 後 面
堆 疊 運 作 圖 解 STACKSIZE=5 TOP 4 3 1 0-1 再 填 入 資 料 1 先 將 指 標 加 一 先 取 後 減 TOP b a push 'c' c b a TOP 1 先 加 後 存 先 取 出 資 料 d c b a pop TOP c b a TOP 再 將 指 標 減 一 push: 將 一 筆 資 料 放 入 堆 疊 pop: 由 堆 疊 取 出 一 筆 資 料
比 較 ps->items[++(ps->top)]=x; // 先 加 後 存 先 於 變 數 就 先 做 先 增 加 索 引 值, 再 儲 存 資 料 ps->item[ps->top--]; // 先 取 後 減 後 於 變 數 就 後 做 先 取 得 資 料, 再 將 索 引 值 減 一
堆 疊 的 應 用 堆 疊 可 以 用 來 儲 存 return 的 位 址 主 程 式 X... 並 且 將 次 一 指 令 的 位 址 放 進 堆 疊 1 3 副 程 式 Z... RETURN 會 將 堆 疊 最 上 面 的 資 訊 ( 位 址 ) 取 出 CALL Y STATEMENT A...... 6 副 程 式 Y CALL Z STATEMENT B RETURN 5 4 堆 疊 的 內 容 變 化 STATEMENT B 位 址 STATEMENT A 位 址
堆 疊 的 應 用 中 序 式 轉 後 序 式 : 例 :A*B/C (( A*B ) /C ) AB*C/ 將 運 算 子 搬 到 右 括 號 的 位 置 上 依 照 原 來 的 優 先 權 的 方 式, 加 上 括 號 運 算 子 :+ - * / 優 先 權 : 決 定 運 算 子 的 執 行 次 序
堆 疊 的 應 用 中 序 式 轉 後 序 式 : 例 :A/B^C+B*E-A*C (((A / (B^C)) + (B * E)) - (A * C)) A B C^/ B E*+ A C*- A/B^C+B*E-A*C ABC^/BE*+AC*-
堆 疊 的 應 用 中 序 式 轉 後 序 式 : 例 : a-b^c*d abc^d*-
後 序 式 的 優 點 不 再 具 有 括 號 及 優 先 權 的 問 題, 計 算 機 直 接 利 用 堆 疊 處 理
由 後 序 式 算 出 答 案 98 7 ^ / 4 5 * + 3 * - 狀 況 數 字 運 算 符 號 處 置 放 入 堆 疊 pop 上 面 两 個 數 值 出 來, 運 算 後, 再 放 回 堆 疊
由 後 序 式 算 出 答 案 98 7 ^ / 4 5 * + 3 * - 7 98 ^ 49 98 5 4 0 / * + * - 3 6 16 狀 況 數 字 運 算 符 號 處 置 放 入 堆 疊 pop 上 面 两 個 數 值 出 來, 運 算 後, 再 放 回 堆 疊
由 後 序 式 算 出 答 案 驗 算 : 98 7 ^ / 4 5 * + 3 * - 98 7 ^ / 4 5 * + 3 * - 49 0 6 16
重 點 回 顧 試 將 a-b^c*d 轉 成 後 序 式 試 將 A*B/C 轉 成 後 序 式 試 述 後 序 式 的 優 點 試 將 98 7 ^ / 4 5 * + 3 * - 答 案 算 出, 並 列 出 使 用 堆 疊 步 驟
存 資 料 取 資 料 環 狀 佇 列 ( 存 資 料 ) rear front addqueue(char temp) // 加 資 料 到 佇 列 { rear=(rear+1) % QSIZE; //rear 先 前 進 一 步 if(front!= rear) // 再 檢 查 索 引 0 Q[rear] = temp; // 先 加 後 存 1 3 else exit(1); // 跳 脫 並 通 知 錯 誤 } rear rear {printf("%s","add Queue Error!");exit(1);} (before) 0 (after) 1 1 %: 取 餘 數!=: 不 等 於 QSIZE=4 若 rear+1 後, 發 現 rear=front 則 不 可 再 加 入 資 料, 否 則 會 有 全 滿 及 全 空 的 判 斷 問 題, 需 空 一 格 3 3 0
存 資 料 rear 取 資 料 1 front 0 3 環 狀 佇 列 ( 取 資 料 ) char deletequeue() // 由 佇 列 中 取 資 料 { char temp; if(front!= rear) // 先 檢 查 索 引 再 加 1 {front=(front+1) % QSIZE; temp = Q[rear] ; // 先 加 後 取 Q[front]='\0'; // 清 除 資 料 ( 可 省 ) return temp; } // 傳 回 佇 列 中 資 料 else exit(1); } rear (before) %: 取 餘 數 1!=: 不 等 於 3 QSIZE=4 若 rear=front 則 一 定 是 代 表 全 空 3 0 0 rear (after) 1
output 環 狀 佇 列 ( 需 空 出 一 格 作 為 全 空 還 是 全 滿 的 判 斷 ) front 0 儲 存 中 的 元 素 個 數 : 若 rear=front 則 為 全 空 若 rear>front 則 rear-front 若 rear<front 則 rear+n-front 例 :rear=, front=0, 則 為, 亦 即 在 索 引 值 1 及 上 面 有 資 料 1 3 input 例 :rear=1,front=, 則 為 3, 亦 即 在 索 引 值 1 0 及 3 上 面 有 資 料 rear rear 追 不 到 front, 會 空 一 格, 但 front 可 以 追 到 rear front 在 呼 叫 前, 永 遠 指 向 空 格 若 儲 存 全 滿 而 rear 强 行 前 進, 則 雖 然 資 料 可 以 儲 存 在 空 格 上, 但 會 造 成 front=rear 之 後, 則 無 法 判 定 是 全 滿 還 是 全 空 如 果 實 為 全 空 而 誤 判 為 全 滿, 若 front 前 進, 則 得 到 無 意 義 的 資 訊 rear 1 0 3 front
優 先 權 : 中 序 轉 後 序 程 式 設 計 指 數 負 號 正 號 ^, unary -, unary +, not *,/ +,- <,<=,==,!=,>=,> and or 6 5 4 3 1 高 低 unary: 單 一 的 優 先 權 : 運 算 符 號 的 執 行 次 序
中 序 轉 後 序 程 式 設 計 遇 此 符 號, 則 POP stack, 直 到 遇 見 ( 符 號 符 號 ) ^ *, / binary +, - ISP (in-stack priority) - 3 1 ICP (in-coming priority) - 4 1 ( 0 4 一 直 停 留 在 STACK, 除 非 碰 到 右 括 號 最 低 優 先 權 最 高 優 先 權
優 先 權 ISP(in-stack priority): 運 算 符 號 在 堆 疊 內 的 優 先 權 ICP(in-coming priority) : 運 算 符 號 在 運 算 式 內 的 優 先 權 A + B * C C B A ICP ISP
中 序 轉 後 序 程 式 設 計 運 算 元 ( 直 接 輸 出 ) A + B * C TOKEN( 算 式 中 的 元 素 ), 分 成 運 算 元 及 運 算 子 两 種 運 算 子 ( 丟 到 堆 疊 ) 運 算 元 : 變 數 數 值 運 算 子 : 運 算 符 號
STACK 中 運 算 子 輸 出 條 件 凡 是 大 於 或 等 於 in-coming priority 一 律 輸 出, 没 有 次 數 限 制 遇 到 算 式 結 束 記 號 則 依 次 將 堆 疊 清 空
運 算 子 輸 出 順 序 1. 若 堆 疊 裏 面 的 運 算 子 的 優 先 權 大 於 或 等 於 外 面 的 運 算 子 優 先 權, 則 丟 出 去 ( 輸 出 ). 之 後, 再 將 外 面 運 算 子 丟 到 堆 疊 內
運 算 子 輸 出 條 件 為 何 兩 個 優 先 權 等 於 也 要 由 堆 疊 輸 出? 因 為 若 優 先 權 相 同, 中 序 式 運 算 子 在 左 邊 的 要 先 執 行 例 如 :A*B/C AB*C/ 會 先 進 入 堆 疊 會 先 由 堆 疊 中 輸 出 在 放 除 號 到 堆 疊 之 前, 會 先 將 乘 號 輸 出
A + 1 B * C 優 先 權 輸 出 : 大 於 或 等 於 incoming priority 或 遇 到 算 式 結 束 記 號 next token none A A + 1 + 1 B AB * + 1 * C stack empty 注 意 : 此 格 隱 藏 算 式 結 束 記 號 + output none ABC ABC* ABC*+ 優 先 權 : 外 面 大, 丟 進 來, 裏 面 大 或 等 於, 丟 出 去 算 式 結 束, POP 一 次 再 POP 一 次, 直 到 清 空 堆 疊
中 序 轉 後 序 程 式 設 計 A * B + 1 C next token none A A * * B AB + 1 C stack empty + 1 output none AB* AB*C AB*C+
中 序 轉 後 序 程 式 設 計 next token none C A + 1 B * C - 1 D stack empty output none A A + 1 + 1 B AB * + 1 * ABC - 1 D - 1 ABC*+ ABC*+D ABC*+D- 連 續 提 出 * 及 +
中 序 轉 後 序 程 式 設 計 A * ( 4 B + 1 C ) - * D 遇 此 符 號, 則 POP stack, 直 到 遇 見 ( 符 號 next token none A A * ( 4 * ( 0 * B AB + 1 * ( 0 + 1 C ABC ) - * ABC+ * * ABC+* D ABC+*D stack empty output none ABC+*D*
中 序 轉 後 序 程 式 設 計 A * ( ( B + C ) * D) next token none A A * ( 4 * * ( 0 ( 4 * ( 0 ( 0 B + 1 * ( 0 ( 0 + 1 C ABC ) - ABC+ * * ( 0 * ABC+ D ABC+D ) - * ABC+D* ABC+D** stack empty output none AB
中 序 轉 後 序 虛 擬 碼 case x='': while top >= 0 do print(stack(top)); top top-1; end_do; print(''); return; x is an operand: print(x); x=')': while STACK(top)!= '('do print(stack(top)); top--; end_do; top--; else: while ISP(STACK(top)) >= ICP(x) do 若 外 面 優 先 權 大 於 堆 疊 裏 面 print(stack(top)); top--; end_do; CALL ADDS(); 將 堆 疊 內 的 '(' 除 去 若 遇 到 運 算 式 結 束 記 號, 則 將 堆 疊 內 剩 下 的 資 料 全 部 印 出 表 示 後 序 式 的 結 束 將 運 算 子 放 到 STACK 中 如 為 運 算 元, 則 直 接 輸 出 印 出 STACK 中 的 資 料, 直 到 '(' 為 止 五 種 情 況 若 ISP 大 於 或 等 於 ICP, 則 做... 堆 疊 裏 面 優 先 權 大 於 或 等 於 外 面, 則 丟 出 去 ( 輸 出 )
中 序 轉 後 序 程 式 設 計 A * ( ( B + C /D)+E*F)-G next token none A A * ( 4 * * ( 0 ( 4 * ( 0 ( 0 B + 1 * ( 0 ( 0 + 1 C ABC / * ( 0 ( 0 + 1 / D ABCD ) - stack empty output none AB ABCD/+ + 1 * ( 0 + 1 E ABCD/+E 後 頁 繼 續
中 序 轉 後 序 程 式 設 計 A * ( ( B + C /D)+E*F)-G next token stack output * * ( 0 + 1 * F ABCD/+EF ) - * ABCD/+EF*+ - 1 ABCD/+EF*+* G - 1 ABCD/+EF*+*G ABCD/+EF*+*G- 結 束
重 點 回 顧 拿 出 一 張 白 紙, 實 際 將 下 列 式 子 應 用 表 格 將 中 序 式 轉 換 成 後 序 式 : A+B*C A*B+C A*(B+C)*D A*((B+C)*D) A*((B+C/D)+E*F)-G
樹 狀 結 構 可 用 於 血 統 表, 組 織 表 ( 公 司 國 家 ), 電 腦 檔 案 管 理 ( 目 錄 ) 階 度 樹 根 A B C D 1 E F G H I J 3 K L M 4 圓 圈 代 表 節 點, 內 存 資 料 短 線 代 表 分 支, 沒 有 方 向 限 制 節 點 分 支
樹 狀 結 構 祖 先 與 子 孫 : 由 某 一 節 點 X, 由 上 往 下, 走 到 另 一 節 點 Y, 則 X 稱 為 祖 先, 而 Y 稱 為 子 孫 例 如 :A 為 M 的 祖 先,M 為 A 的 子 孫 階 度 A B C D 1 E F G H I J 3 K L M 4
樹 狀 結 構 父 節 點 與 子 節 點 : 如 同 祖 先 與 子 孫 關 係, 但 節 點 X 直 接 接 到 節 點 Y 例 如 :C 為 G 的 父 節 點, G 為 C 的 子 節 點 階 度 A 1 B C D E F G H I J 3 K L M 4
樹 狀 結 構 兄 弟 節 點 : 共 用 父 節 點 的 子 節 點, 例 如 :H,I,J 為 兄 弟 節 點 G 節 點 沒 有 兄 弟 節 點, 因 為 沒 有 其 他 節 點 與 其 共 用 父 節 點 階 度 A B C D 1 E F G H I J 3 K L M 4
樹 狀 結 構 終 點 節 點 ( 樹 葉 ): 沒 有 子 節 點 的 節 點, 例 如 : K,L,F,G,M,I,J 階 度 A B C D 1 E F G H I J 3 K L M 4
樹 狀 結 構 分 支 度 : 某 節 點 的 子 節 點 的 數 目, 例 如 :D 節 點 的 分 支 度 為 3 一 棵 樹 的 分 支 度 代 表 此 樹 所 能 找 出 的 最 大 分 支 度 階 度 A B C D 1 E F G H I J 3 K L M 4
樹 狀 結 構 階 度 : 表 示 此 樹 的 水 平 層 面, 樹 根 的 階 度 為 1 階 度 A B C D 1 E F G H I J 3 K L M 4
樹 狀 結 構 高 度 或 深 度 : 由 某 一 節 點 到 終 點 節 點 的 最 大 階 度 例 如 : 節 點 A 的 高 度 為 4, 節 點 B 的 高 度 為 3 階 度 A 1 4 3 B C D E F G H I J 3 K L M 4
樹 狀 結 構 路 徑 長 度 : 两 節 點 間 的 直 線 線 段 數 量 例 如 :A 到 M 為 3 階 度 A B C D 1 E F G H I J 3 K L M 4
重 點 回 顧 祖 先 與 子 孫 父 節 點 與 子 節 點 兄 弟 節 點 終 點 節 點 ( 樹 葉 ) 分 支 度 階 度 高 度 或 深 度 路 徑 長 度
樹 狀 結 構 此 樹 的 最 大 分 支 度 就 等 於 LINK 欄 位 的 需 求 量 struct tree { char DATA; struct tree *link1; struct tree *link;... struct tree *linkn; }; 每 一 節 點 都 共 用 一 個 資 料 結 構, 所 以 要 取 最 大 分 支 度 分 支 DATA LINK1 LINK... LINKN 利 用 指 標 變 數 做 為 分 支 分 支 度 為 n
樹 狀 結 構 圖 A 分 支 B C D E F G H I J K L M 分 支 度 為 3 方 格 內 的 斜 線 代 表 沒 有 向 下 的 分 支
二 元 樹 (binary tree) 最 大 分 支 度 為 的 樹 struct btree { int info; left info right struct btree *left; // 左 LINK 欄 位 struct btree *right; }; // 右 LINK 欄 位 3 分 支 度 為 常 用
一 般 樹 轉 換 成 二 元 樹 為 何 要 將 一 般 樹 轉 換 成 二 元 樹? ANS: 首 先, 先 估 出 有 多 少 個 LINK 欄 位 被 浪 費 掉 : 若 樹 的 分 支 度 k 若 總 節 點 數 n 則 總 共 的 LINK 欄 位 為 nk 除 了 樹 根 外, 每 一 節 點 均 被 一 個 LINK 欄 位 所 指 向, 故 共 用 了 n-1 個 LINK 欄 位 E 樹 根 ( 沒 被 指 向 ) F 非 樹 根 ( 被 指 向 )
一 般 樹 轉 換 成 二 元 樹 因 為 除 了 樹 根 外, 每 一 節 點 均 被 一 個 LINK 欄 位 所 指 向, 所 以 共 用 了 n-1 個 LINK 欄 位 因 此, 空 的 LINK 欄 位, 應 為 總 共 的 LINK 欄 位 減 掉 被 使 用 掉 的 LINK 欄 位 : nk-(n-1) = nk-n+1 所 以 有 nk-n+1 個 LINK 欄 位 被 浪 費 掉 一 般 而 言, 有 3 分 之 的 LINK 欄 位 是 空 的
二 元 樹 浪 費 記 憶 體 的 程 度 較 少 分 支 度 nk-n+1 k= k=3 k=4 n=5 5*-5+1=6 5*3-5+1=11 5*4-5+1=16 n=10 10*-10+1=11 10*3-10+1=1 10*4-10+1=31 節 點 總 數 大 約 二 倍 大 約 三 倍
二 元 樹 分 支 度 分 支 度 : 某 節 點 所 含 子 節 點 的 數 目 父 節 點 A A A A B B C B B C 子 節 點 右 子 樹 為 空 集 合 左 子 樹 為 空 集 合 左 斜 樹 ( 找 不 到 任 何 右 子 樹 )
階 度 1 完 滿 ( 滿 枝 ) 二 元 樹 1 3 3 4 5 6 7 4 8 9 10 11 1 13 14 15 節 點 個 數 = 階 度 -1 = 4-1 =15 可 得 知 需 要 保 留 多 少 元 素 的 限 制 樹 根 到 各 樹 葉 的 長 度 均 為 階 度 減 1 編 號 : 由 上 而 下, 由 左 至 右, 依 序 由 1 到 n
階 度 1 完 整 二 元 樹 1 3 3 4 5 6 7 4 8 9 節 點 個 數 < 階 度 -1 由 號 碼 最 大 的 少 起
二 元 樹 在 第 i 階 度 的 那 一 層 最 多 的 節 點 數 為 i-1 階 度 (i) 1 3... i-1 1 4...
階 度 為 k 的 二 元 樹 最 多 的 節 點 數 為 k -1 階 度 (k) 1 3... k -1 1 3 7...
重 點 回 顧 請 問 為 何 要 將 一 般 樹 轉 換 成 二 元 樹? 請 問 何 謂 完 滿 ( 滿 枝 ) 二 元 樹? 請 問 何 謂 完 整 二 元 樹? 請 問 二 元 樹 在 第 i 階 度 的 那 一 層 最 多 的 節 點 數 為 多 少? 請 問 階 度 為 k 的 二 元 樹 最 多 的 節 點 數 為 多 少?
二 元 樹 追 蹤 中 序 前 序 後 序 三 種 方 式 走 的 路 徑 是 一 樣 的 左 邊 為 優 先, 走 到 底, 再 退 回 一 個 節 點 ( 子 樹 的 樹 根 ), 再 走 到 右 邊 的 一 個 節 點, 再 左 邊 優 先... 反 覆 循 環, 直 到 走 回 樹 根 停 止 前 序 : 第 一 次 走 到 就 列 印 出 答 案 中 序 : 第 二 次 走 到 就 列 印 出 答 案 後 序 : 第 三 次 走 到 就 列 印 出 答 案
二 元 樹 追 蹤 + / D * E 前 序 :+*/A^BCDE 中 序 :A/B^C*D+E 後 序 :ABC^/D*E+ A ^ B C 可 用 紙 筆 將 圖 畫 出, 在 圓 點 上 每 次 走 到 就 打 一 個 勾 當 有 一 個 勾 時, 就 在 前 序 欄 位 填 入 圈 內 字 母 當 有 二 個 勾 時, 就 在 中 序 欄 位 填 入 圈 內 字 母 當 有 三 個 勾 時, 就 在 後 序 欄 位 填 入 圈 內 字 母
二 元 樹 追 蹤 前 序 快 速 解 法 + 1 * E 5 前 序 :+*/A^BCDE / D 4 A ^ 由 右 上 至 左 下 各 線 段 所 形 成 的 順 序 B C 3
二 元 樹 追 蹤 中 序 快 速 解 法 * + / D E 中 序 :A/B^C*D+E A ^ 將 樹 壓 成 水 平 線 時 所 形 成 的 順 序 B C A / B ^ C * D + E
二 元 樹 追 蹤 後 序 快 速 解 法 + * 5 E / 4 D 後 序 :ABC^/D*E+ A 1 3 ^ 由 右 下 至 左 上 各 線 段 所 形 成 的 順 序 B C
二 元 樹 結 構 type struct btree { char info; struct btree *left; struct btree *right; }node; 資 料 分 支 度 為 此 node 將 被 用 在 後 面 三 個 遞 迴 程 式 中
前 序 遞 迴 preorder(root) node *root; { if(root!=null) { printf("%d\n",root->info); preorder(root->left); preorder(root->right); } } 程 式 的 本 身 是 表 示 各 指 令 的 執 行 的 順 序, 也 就 是 一 個 執 行 的 藍 圖 對 於 每 一 次 的 呼 叫, 電 腦 會 將 資 料 的 變 化 記 錄 在 堆 疊 中 輸 出 放 在 最 前 面 遞 迴 : 自 已 呼 叫 自 已
中 序 遞 迴 inorder(root) node *root; { if(root!=null) { ineorder(root->left); printf("%d\n",root->info); ineorder(root->right); } } 輸 出 放 在 中 間
後 序 遞 迴 postorder(root) node *root; { if(root!=null) { postorder(root->left); postorder(root->right); printf("%d\n",root->info); } } 輸 出 放 在 最 後 面
遞 迴 範 例 範 例 實 際 上 只 有 一 份 程 式, 但 是 為 了 解 釋 上 的 方 便, 可 想 像 每 一 個 節 點 都 有 同 樣 一 份 的 程 式 字 母 小 寫 a b c d 表 示 節 點 字 母 大 寫 A B C D R 表 示 執 行 步 驟 堆 疊 內 為 表 示 節 點 - 執 行 步 驟, 亦 即 表 示 return 指 令 執 行 後 要 去 的 位 址
postorder(root) node *root; A {if(root!=null) B {postorder(root->left); C postorder(root->right); D printf("%d\n",root->info); }} 二 元 樹 後 序 追 蹤 範 例 NO 4 6 7 d-c d-c, b-c d-c, b-c, a-c d-c, b-c 後 序 :acbed STACK 5 A 6 B 8 C 10 D 3 A 4 B 11 C 18 D a 1 A B 19 C 6 D b 1 A 13 B 15 C 17 D d c e A B C D 0 A 1 B 3 C 5 D 4 A B C D 8 9 10 11 13 14 15 16 17-18- d-c, b-c, a-d d-c, b-c d-c d-c, b-d d-c, b-d, c-c d-c, b-d d-c, b-d, c-d d-c, b-d d-c - 19 d-d 1 d-d, e-c 7 A B C D 9 A B C D 14 A B C D 16 A B C D 3 4 d-d d-d, e-d d-d 5 -
inorder(root) node *root; A {if(root!=null) B {inorder(root->left); C printf("%d\n",root->info); D inorder(root->right); R }} 7 A B C D 5 A 6 B 8 C 9 D 11 R 10 A B C D 3 A 4 B 1 C 13 D 1 R a 1 A B C 3 D 30 R b 14 A 15 B 17 C 18 D 0 R 16 A B C D d c 二 元 樹 中 序 追 蹤 範 例 19 A B C D e 6 A B C D 4 A 5 B 7 C 8 D 30 R 9 A B C D NO 4 6 7 9 10 11 13 15 16 18 19 0 1 3 5 6 8 9 30 d-c d-c, b-c d-c, b-c, a-c d-c, b-c d-c, b-c, a-r d-c, b-c d-c d-c, b-r d-c, b-r, c-c d-c, b-r d-c, b-r, c-r d-c, b-r d-c - d-r d-r, e-c d-r d-r, e-r d-r - 中 序 :abcde STACK
重 點 回 顧 請 問 二 元 樹 追 蹤 有 那 些? 其 追 蹤 方 式 為 何? 請 問 二 元 樹 追 蹤 前 序 快 速 解 法 方 式 為 何? 請 問 二 元 樹 追 蹤 中 序 快 速 解 法 方 式 為 何? 請 問 二 元 樹 追 蹤 後 序 快 速 解 法 方 式 為 何? 請 問 何 謂 遞 迴?
快 速 排 序 英 文 名 稱 : quick sort 目 的 : 希 望 排 成 數 值 大 的 在 右 邊, 成 數 值 小 的 在 左 邊 規 則 : 將 最 左 邊 的 數 值 視 為 基 數, 做 為 此 較 時 的 參 考 值 若 i 在 左,j 在 右, 則 A[i] 與 A[j] 互 換 互 換 後,i 向 右 移 一 格,j 向 左 移 一 格 若 i j 重 疊 ( 重 號 ), 則 不 互 換 重 號 代 表 與 基 數 同 值 若 i 在 右,j 在 左, 則 A[j] 與 基 數 互 換 將 非 基 數 的 數 值 用 方 括 號 括 起 來 此 時 基 數 己 移 到 正 確 的 排 序 位 置 上 i 可 超 出 方 框 一 格,j 可 到 基 數 的 那 一 格
快 速 排 序 基 數 大 於 或 等 於 基 數 時 停 止 小 於 或 等 於 基 數 時 停 止 i j 6 5 37 1 61 11 59 15 48 19 i j 6 5 37 1 61 11 59 15 48 19 交 換 19 與 37 兩 值 交 換 後, 移 動 i 及 j 指 標 i j 6 5 19 1 61 11 59 15 48 37
快 速 排 序 j i 6 5 19 1 15 11 59 61 48 37 交 換 基 數 與 A[j] 兩 值 交 換 後, 用 方 括 號 括 住 非 原 基 數 數 值 [11 5 19 1 15] 6 [59 61 48 37] 固 定 位 置, 不 會 再 變 被 方 括 號 圍 起 來 的 數 值 尚 需 排 序
快 速 排 序 i j i j [11 5 19 1 15] 6 [59 61 48 37] j i j i [11 5 1 19 15] 6 [59 37 48 61] j i j i j i [1 5] 11 [19 15] 6 [48 37] 59 [61]
快 速 排 序 j i j i j i [1 5] 11 [19 15] 6 [48 37] 59 [61] [1] 5 11 [15] 19 6 [37] 48 59 61 結 束 排 序, 檢 查 是 否 是 由 小 到 大 的 數 列
快 速 排 序 範 例 ( 含 有 重 號 ) 1 16 30 8 16 4 10 0 18 1 i j 1 16 30 8 16 4 10 0 18 1 i j 1 1 30 8 16 4 10 0 18 16
快 速 排 序 範 例 ( 含 有 重 號 ) i j 1 1 30 8 16 4 10 0 18 16 i j 1 1 10 8 16 4 30 0 18 16 j i 1 1 10 8 4 16 30 0 18 16 [4 1 10 8] 1 [16 30 0 18 16]
快 速 排 序 範 例 ( 含 有 重 號 ) j i i j [4 1 10 8] 1 [16 30 0 18 16] j i [] 4 [1 10 8] 1 [16 16 0 18 30] 4 [1 10 8] 1 [16] 16 [0 18 30]
快 速 排 序 範 例 ( 含 有 重 號 ) 4 [1 10 8] 1 16 16 [0 18 30] j i j i 4 [1 10 8] 1 16 16 [0 18 30] j i 4 [8 10] 1 1 16 16 [18] 0 [30]
快 速 排 序 範 例 ( 含 有 重 號 ) j i 4 [8 10] 1 1 16 16 [18] 0 [30] 4 8 10 1 1 16 16 18 0 30 結 束 排 序, 檢 查 是 否 是 由 小 到 大 的 數 列
請 實 作 一 個 快 速 排 序 重 點 回 顧
ceil 及 floor ceil( 天 花 板 ): 大 於 又 最 接 近 的 整 數 例 :3.1 的 ceil 為 4 floor( 地 板 ): 小 於 又 最 接 近 的 整 數 例 :3.1 的 floor 為 3 4 ceil 3.1 3 floor 浮 點 轉 整 數 的 工 具
二 元 搜 尋 中 間 索 引 被 搜 尋 的 數 列 必 須 事 先 經 過 排 序 要 找 的 值 low 0, up n-1 while low <= up do mid [(low+up)/] floor end case: KEY>KEY mid :low mid+1 ( 改 為 只 搜 尋 上 半 部 ) KEY=KEY mid :p mid; return ( 找 到 了 ) KEY<KEY mid :up mid-1 ( 改 為 只 搜 尋 下 半 部 ) end return 最 後 一 格 也 要 搜 尋 在 中 間 索 引 上 的 值 up mid low 每 次 都 做 對 半 篩 選 69 51 49 31 5 1 15 6 5 4 3 1 0 n=7
二 元 搜 尋 呼 叫 程 式 可 在 程 式 結 束 後 判 斷, 若 p 有 值 則 為 找 到, 若 p 無 值 則 資 料 不 在 表 格 中
計 算 所 需 的 次 數 n/, n/, n/ 3,...n/?? =n 最 差 的 情 況 若 第 一 次 找 不 到 所 剩 下 的 個 數 比 較 接 近 的 固 定 值 若 要 找 的 值 不 在 表 內 或 僅 剩 最 後 一 個 元 素 才 找 到 都 必 需 結 朿 方 法 1 log? =log n?log =log n?=log n 方 法 log 10? =log 10 n?=log 10 n/log 10 依 換 底 公 式 得?=log n 最 好 的 情 形 是 第 一 次 就 找 到
請 實 作 一 個 二 元 搜 尋 重 點 回 顧
雜 湊 搜 尋 鍵 值 (KEY): 能 夠 獨 一 無 二 的 分 辨 出 某 一 記 錄 例 如 : 身 分 證 字 號 車 牌 號 碼 等 鍵 值 轉 換 實 際 記 憶 體 位 置 資 料 表 中 要 選 出 一 個 欄 位 來 做 為 搜 尋 的 依 據
餘 數 法 例 : 至 少 需 要 記 憶 體 空 間 大 小 A 0 1 3 4... A % 3 0 1 0 1...
平 方 取 中 例 : key=5103, 5103 =6040609, 記 憶 體 空 間 為 100, 則 取 6040609 中 的 40 為 記 憶 體 位 址 任 意 取 的 二 位 數, 非 相 鄰 亦 可
桶 與 槽 雜 湊 表 內, 水 平 方 向 的 格 子 稱 為 桶, 垂 直 方 向 的 格 子 稱 為 槽 槽 桶
範 例 例 : 將 下 列 鍵 值 GA,D,A,G,L,A,A1,A3,A4,E 利 用 雜 湊 函 數 分 配 到 記 憶 體 中 假 定 桶 內 只 有 兩 個 槽 1 3 4 5 6 7... 1... 6 3 10 1 5 A D E? GA L 槽 1 槽 A1? 產 生 溢 位, 不 知 要 放 到 那 裹? 6 4 A G 7 8 A3? 不 知 要 放 到 那 裹? 9 A4? 不 知 要 放 到 那 裹? 欲 放 入 資 料 時 可 能 發 生 : 碰 撞 : 第 一 槽 已 被 使 用 溢 位 : 兩 槽 均 已 使 用 ASCII 碼 順 序 : A:1, D:4, E:5, G:7, L:1
解 決 溢 位 的 方 法 1, 線 性 探 測, 重 覆 雜 湊 3, 鏈 結 串 列 法
線 性 探 測 將 溢 位 的 鍵 值 資 料 放 入 下 一 空 白 位 置 例 : 將 GA 7 D 4 A 1 G 7 L 1 A 1 A1 1 A3 1 A4 1 Z 6 ZA 6 E 5, 放 入 每 桶 只 有 一 個 糟 的 雜 湊 表 中 下 標 表 示 ASCII 碼 的 順 序
1 3 6 資 料 A A 溢 位 次 數 0 1 例 : 將 下 列 鍵 值 GA 7 D 4 A 1 G 7 L 1 A 1 A1 1 A3 1 A4 1 Z 6 ZA 6 E 5, 放 入 每 桶 只 有 一 個 糟 的 雜 湊 表 中 3 4 7 A1 D 0 5 6 7 8 9 10 8 9 1 4 11 1 A3 A4 GA G ZA E 4 5 0 1 9 5 置 放 G 時 有 溢 位 一 格 11 1 5 L 0 13... 6 10 Z 0 總 共 溢 位 次 數 為 7 次
1 3 4 5 6 7 8 9 10 11 1 13... 6 資 料 A A A1 D A3 A4 GA G ZA E L Z 找 尋 次 數 1 3 1 5 6 1 10 6 1 1 總 共 搜 尋 次 數 為 39 次
重 覆 雜 湊 當 一 種 雜 湊 函 數 產 生 溢 位 時, 則 換 用 另 一 種 雜 湊 函 數 去 試 例 如 : 餘 數 法 平 方 法
鏈 結 串 列 法 若 用 線 性 探 測 及 選 取 個 位 數 key 48 55 3 5 78 1 80 位 址 8 5 5 8 1 0
key 48 55 3 5 78 1 80 位 址 8 5 5 8 1 0 0 1 3 4 5 6 7 8 9 80 1 3 55 48 5 78
重 點 回 顧 試 述 雜 湊 搜 尋 工 作 原 理 請 問 解 決 溢 位 的 方 法 有 那 些?
最 短 路 徑 演 算 法 9 1 7 14 10 1 起 點 8 11 13 5 9 4 4 3 16 6 11 終 點
1 7 5 4 8 3 6 9 14 10 13 1 11 9 4 16 11 0 4 8 0 1 7 0 16 6 10 13 0 9 5 11 0 4 0 3 9 11 0 14 0 1 8 7 6 5 4 3 1 from to 將 圖 製 成 表, 因 為 人 可 以 看 圖, 但 電 腦 只 能 看 表
from 1 3 4 5 6 7 8 to 1 3 4 5 6 7 8 在 每 一 step 中, 選 出 最 小 值, 下 一 1 11 16 4 9 11 13 14 10 9 step 將 由 此 出 發 已 經 圈 選 過 的 節 點 不 能 再 使 用 新 距 離 = 圈 選 距 離 + 圈 選 點 至 新 節 點 距 離 求 出 的 新 距 離 若 比 原 距 離 大, 則 仍 用 原 距 離, 以 維 持 最 短 距 離 3 4 5 6 7 8 step 1 14 step 11 15 1 step 3 15 1 step 4 4 15 step 5 4 31 step 6 31 33
step 1 3 4 5 6 7 14 8 最 後 路 徑 的 選 取 是 由 終 點 反 推 回 起 點 step step 3 11 15 15 1 1 找 出 目 前 距 離 是 由 何 節 點 所 決 定 的 step 4 4 15 step 5 4 31 step 6 31 33 9 1 7 14 10 1 8 11 13 5 9 4 4 3 16 6 11
重 點 回 顧 試 述 最 短 路 徑 演 算 法 工 作 原 理
謝 謝 各 位! 課 程 結 束