算 法 與 數(shù) 據(jù) 結(jié) 構(gòu)教 材 ： 數(shù) 據(jù) 結(jié) 構(gòu) (C語 言 版 ) 。 嚴(yán) 蔚 敏 ， 吳 偉 民 編 著 。 清 華 大 學(xué) 出 版 社 。參 考 文 獻(xiàn) ： 1 數(shù) 據(jù) 結(jié) 構(gòu) 。 張 選 平 ， 雷 詠 梅 編 ， 嚴(yán) 蔚 敏 審 。 機(jī) 械 工 業(yè) 出 版 社 。 2 數(shù) 據(jù) 結(jié) 構(gòu) 與 算 法 分 析 。 Clifford A. Shaffer著 ， 張 銘 ， 劉 曉 丹 譯 。 電 子 工 業(yè) 出 版 社 。 3 數(shù) 據(jù) 結(jié) 構(gòu) 習(xí) 題 與 解 析 (C語 實 言 版 ) 。 李 春 葆 。 清 華 大 學(xué) 出 版 社 。 4 數(shù) 據(jù) 結(jié) 構(gòu) 與 算 法 。 夏 克 儉 編 著 。 國 防 工 業(yè) 出版 社 。 第 1章 緒 論 目 前 ， 計 算 機(jī) 已 深 入 到 社 會 生 活 的 各 個 領(lǐng) 域 ， 其 應(yīng)用 已 不 再 僅 僅 局 限 于 科 學(xué) 計 算 ， 而 更 多 的 是 用 于 控 制 ，管 理 及 數(shù) 據(jù) 處 理 等 非 數(shù) 值 計 算 領(lǐng) 域 。 計 算 機(jī) 是 一 門 研 究用 計 算 機(jī) 進(jìn) 行 信 息 表 示 和 處 理 的 科 學(xué) 。 這 里 面 涉 及 到 兩個 問 題 ： 信 息 的 表 示 ， 信 息 的 處 理 。 信 息 的 表 示 和 組 織 又 直 接 關(guān) 系 到 處 理 信 息 的 程 序 的效 率 。 隨 著 應(yīng) 用 問 題 的 不 斷 復(fù) 雜 ， 導(dǎo) 致 信 息 量 劇 增 與 信息 范 圍 的 拓 寬 ， 使 許 多 系 統(tǒng) 程 序 和 應(yīng) 用 程 序 的 規(guī) 模 很 大 ，結(jié) 構(gòu) 又 相 當(dāng) 復(fù) 雜 。 因 此 ， 必 須 分 析 待 處 理 問 題 中 的 對 象的 特 征 及 各 對 象 之 間 存 在 的 關(guān) 系 ， 這 就 是 數(shù) 據(jù) 結(jié) 構(gòu) 這 門課 所 要 研 究 的 問 題 。 編 寫 解 決 實 際 問 題 的 程 序 的 一 般 過 程 ： 如 何 用 數(shù) 據(jù) 形 式 描 述 問 題 ?即 由 問 題 抽 象 出 一 個適 當(dāng) 的 數(shù) 學(xué) 模 型 ; 問 題 所 涉 及 的 數(shù) 據(jù) 量 大 小 及 數(shù) 據(jù) 之 間 的 關(guān) 系 ; 如 何 在 計 算 機(jī) 中 存 儲 數(shù) 據(jù) 及 體 現(xiàn) 數(shù) 據(jù) 之 間 的 關(guān) 系 ? 處 理 問 題 時 需 要 對 數(shù) 據(jù) 作 何 種 運(yùn) 算 ? 所 編 寫 的 程 序 的 性 能 是 否 良 好 ?上 面 所 列 舉 的 問 題 基 本 上 由 數(shù) 據(jù) 結(jié) 構(gòu) 這 門 課 程 來 回 答 。計 算 機(jī) 求 解 問 題 的 一 般 步 驟 1.1 數(shù) 據(jù) 結(jié) 構(gòu) 及 其 概 念 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) 是 計 算 機(jī) 科 學(xué) 中 的 一 門 綜 合 性專 業(yè) 基 礎(chǔ) 課 。 是 介 于 數(shù) 學(xué) 、 計 算 機(jī) 硬 件 、 計 算 機(jī) 軟 件 三者 之 間 的 一 門 核 心 課 程 ， 不 僅 是 一 般 程 序 設(shè) 計 的 基 礎(chǔ) ，而 且 是 設(shè) 計 和 實 現(xiàn) 編 譯 程 序 、 操 作 系 統(tǒng) 、 數(shù) 據(jù) 庫 系 統(tǒng) 及其 他 系 統(tǒng) 程 序 和 大 型 應(yīng) 用 程 序 的 重 要 基 礎(chǔ) 。 1.1.1 數(shù) 據(jù) 結(jié) 構(gòu) 的 例 子姓 名 電 話 號 碼陳 海 13612345588 李 四 鋒 13056112345。 。 。 。 。 。例 1： 電 話 號 碼 查 詢 系 統(tǒng) 設(shè) 有 一 個 電 話 號 碼 薄 ， 它 記 錄 了 N個 人 的 名 字 和 其相 應(yīng) 的 電 話 號 碼 ， 假 定 按 如 下 形 式 安 排 ： (a1, b1)， (a2, b2)， (an, bn)， 其 中 ai, bi(i=1， 2n) 分 別 表 示 某 人 的名 字 和 電 話 號 碼 。 本 問 題 是 一 種 典 型 的 表 格 問 題 。 如表 1-1， 數(shù) 據(jù) 與 數(shù) 據(jù) 成 簡 單 的 一 對 一 的 線 性 關(guān) 系 。表 1-1 線 性 表 結(jié) 構(gòu) 例 2： 磁 盤 目 錄 文 件 系 統(tǒng) 磁 盤 根 目 錄 下 有 很 多 子 目 錄及 文 件 ， 每 個 子 目 錄 里 又 可 以 包含 多 個 子 目 錄 及 文 件 ， 但 每 個 子目 錄 只 有 一 個 父 目 錄 ， 依 此 類 推 ： 本 問 題 是 一 種 典 型 的 樹 型 結(jié)構(gòu) 問 題 ， 如 圖 1-1 ， 數(shù) 據(jù) 與 數(shù) 據(jù)成 一 對 多 的 關(guān) 系 ， 是 一 種 典 型 的非 線 性 關(guān) 系 結(jié) 構(gòu) 樹 形 結(jié) 構(gòu) 。 樹 形 例 3： 交 通 網(wǎng) 絡(luò) 圖 從 一 個 地 方 到 另 外 一 個 地 方 可 以 有 多 條 路 徑 。 本 問題 是 一 種 典 型 的 網(wǎng) 狀 結(jié) 構(gòu) 問 題 ， 數(shù) 據(jù) 與 數(shù) 據(jù) 成 多 對 多 的關(guān) 系 ， 是 一 種 非 線 性 關(guān) 系 結(jié) 構(gòu) 。佛 山 惠 州廣 州中 山 東 莞 深 圳 珠 海 圖 1-2 網(wǎng) 狀 結(jié) 構(gòu) 數(shù) 據(jù) (Data) ： 是 客 觀 事 物 的 符 號 表 示 。 在 計 算 機(jī) 科學(xué) 中 指 的 是 所 有 能 輸 入 到 計 算 機(jī) 中 并 被 計 算 機(jī) 程 序 處 理的 符 號 的 總 稱 。 數(shù) 據(jù) 元 素 (Data Element) ： 是 數(shù) 據(jù) 的 基 本 單 位 ， 在程 序 中 通 常 作 為 一 個 整 體 來 進(jìn) 行 考 慮 和 處 理 。 一 個 數(shù) 據(jù) 元 素 可 由 若 干 個 數(shù) 據(jù) 項 (Data Item)組 成 。數(shù) 據(jù) 項 是 數(shù) 據(jù) 的 不 可 分 割 的 最 小 單 位 。 數(shù) 據(jù) 項 是 對 客 觀事 物 某 一 方 面 特 性 的 數(shù) 據(jù) 描 述 。 數(shù) 據(jù) 對 象 (Data Object)： 是 性 質(zhì) 相 同 的 數(shù) 據(jù) 元 素 的 集合 ， 是 數(shù) 據(jù) 的 一 個 子 集 。 如 字 符 集 合 C=A,B,C, 。1.1.2 基 本 概 念 和 術(shù) 語 數(shù) 據(jù) 結(jié) 構(gòu) (Data Structure)： 是 指 相 互 之 間 具 有 (存 在 )一 定 聯(lián) 系 (關(guān) 系 )的 數(shù) 據(jù) 元 素 的 集 合 。 元 素 之 間 的 相 互 聯(lián)系 (關(guān) 系 )稱 為 邏 輯 結(jié) 構(gòu) 。 數(shù) 據(jù) 元 素 之 間 的 邏 輯 結(jié) 構(gòu) 有 四種 基 本 類 型 ， 如 圖 1-3所 示 。 集 合 ： 結(jié) 構(gòu) 中 的 數(shù) 據(jù) 元 素 除 了 “ 同 屬 于 一 個 集 合 ”外 ， 沒 有 其 它 關(guān) 系 。 線 性 結(jié) 構(gòu) ： 結(jié) 構(gòu) 中 的 數(shù) 據(jù) 元 素 之 間 存 在 一 對 一 的關(guān) 系 。 樹 型 結(jié) 構(gòu) ： 結(jié) 構(gòu) 中 的 數(shù) 據(jù) 元 素 之 間 存 在 一 對 多 的關(guān) 系 。 圖 狀 結(jié) 構(gòu) 或 網(wǎng) 狀 結(jié) 構(gòu) ： 結(jié) 構(gòu) 中 的 數(shù) 據(jù) 元 素 之 間 存在 多 對 多 的 關(guān) 系 。 數(shù) 據(jù) 結(jié) 構(gòu) 的 形 式 定 義 是 一 個 二 元 組 ： Data-Structure=(D， S)其 中 ： D是 數(shù) 據(jù) 元 素 的 有 限 集 ， S是 D上 關(guān) 系 的 有 限 集 。例 2： 設(shè) 數(shù) 據(jù) 邏 輯 結(jié) 構(gòu) B=（ K， R） K=k1, k2, , k9 R= ， ， ， ， ， ， ， ， ， 畫 出 這 邏 輯 結(jié) 構(gòu) 的 圖 示 ， 并 確 定 那 些 是 起 點(diǎn) ， 那 些 是 終 點(diǎn)1.1.3 數(shù) 據(jù) 結(jié) 構(gòu) 的 形 式 定 義圖 1-3 四 類 基 本 1.1.4 數(shù) 據(jù) 結(jié) 構(gòu) 的 存 儲 方 式 數(shù) 據(jù) 元 素 之 間 的 關(guān) 系 可 以 是 元 素 之 間 代 表 某 種 含 義的 自 然 關(guān) 系 ， 也 可 以 是 為 處 理 問 題 方 便 而 人 為 定 義 的關(guān) 系 ， 這 種 自 然 或 人 為 定 義 的 “ 關(guān) 系 ” 稱 為 數(shù) 據(jù) 元 素之 間 的 邏 輯 關(guān) 系 ， 相 應(yīng) 的 結(jié) 構(gòu) 稱 為 邏 輯 結(jié) 構(gòu) 。 數(shù) 據(jù) 結(jié) 構(gòu) 在 計 算 機(jī) 內(nèi) 存 中 的 存 儲 包 括 數(shù) 據(jù) 元 素 的存 儲 和 元 素 之 間 的 關(guān) 系 的 表 示 。 元 素 之 間 的 關(guān) 系 在 計 算 機(jī) 中 有 兩 種 不 同 的 表 示 方 法 ：順 序 表 示 和 非 順 序 表 示 。 由 此 得 出 兩 種 不 同 的 存 儲 結(jié) 構(gòu) ：順 序 存 儲 結(jié) 構(gòu) 和 鏈 式 存 儲 結(jié) 構(gòu) 。 順 序 存 儲 結(jié) 構(gòu) ： 用 數(shù) 據(jù) 元 素 在 存 儲 器 中 的 相 對 位置 來 表 示 數(shù) 據(jù) 元 素 之 間 的 邏 輯 結(jié) 構(gòu) (關(guān) 系 )。 鏈 式 存 儲 結(jié) 構(gòu) ： 在 每 一 個 數(shù) 據(jù) 元 素 中 增 加 一 個 存放 另 一 個 元 素 地 址 的 指 針 (pointer )， 用 該 指 針 來 表示 數(shù) 據(jù) 元 素 之 間 的 邏 輯 結(jié) 構(gòu) (關(guān) 系 )。例 ： 設(shè) 有 數(shù) 據(jù) 集 合 A=3.0,2.3,5.0,-8.5,11.0 ， 兩 種 不 同的 存 儲 結(jié) 構(gòu) 。 順 序 結(jié) 構(gòu) ： 數(shù) 據(jù) 元 素 存 放 的 地 址 是 連 續(xù) 的 ； 鏈 式 結(jié) 構(gòu) ： 數(shù) 據(jù) 元 素 存 放 的 地 址 是 否 連 續(xù) 沒 有 要求 。 數(shù) 據(jù) 的 邏 輯 結(jié) 構(gòu) 和 物 理 結(jié) 構(gòu) 是 密 不 可 分 的 兩 個 方 面 ，一 個 算 法 的 設(shè) 計 取 決 于 所 選 定 的 邏 輯 結(jié) 構(gòu) ， 而 算 法 的 實現(xiàn) 依 賴 于 所 采 用 的 存 儲 結(jié) 構(gòu) 。 在 C語 言 中 ， 用 一 維 數(shù) 組 表 示 順 序 存 儲 結(jié) 構(gòu) ； 用 結(jié)構(gòu) 體 類 型 表 示 鏈 式 存 儲 結(jié) 構(gòu) 。 數(shù) 據(jù) 結(jié) 構(gòu) 的 三 個 組 成 部 分 ：邏 輯 結(jié) 構(gòu) ： 數(shù) 據(jù) 元 素 之 間 邏 輯 關(guān) 系 的 描 述 D_S=（ D， S）存 儲 結(jié) 構(gòu) ： 數(shù) 據(jù) 元 素 在 計 算 機(jī) 中 的 存 儲 及 其 邏 輯關(guān) 系 的 表 現(xiàn) 稱 為 數(shù) 據(jù) 的 存 儲 結(jié) 構(gòu) 或 物 理 結(jié) 構(gòu) 。數(shù) 據(jù) 操 作 ： 對 數(shù) 據(jù) 要 進(jìn) 行 的 運(yùn) 算 。 本 課 程 中 將 要 討 論 的 三 種 邏 輯 結(jié) 構(gòu) 及 其 采 用 的 存 儲結(jié) 構(gòu) 如 圖 1-4所 示 。 數(shù) 據(jù) 的 邏 輯 結(jié) 構(gòu) 非 線 性 結(jié) 構(gòu)集 合 圖 狀 結(jié) 構(gòu)有 向 圖 無 向 圖樹 形 結(jié) 構(gòu)一 般 樹 二 叉 樹線 性 結(jié) 構(gòu)一 般 線 性 表 線 性 表 推 廣 廣 義 表數(shù) 組串受 限 線 性 表棧 和 隊 列圖 1-5 數(shù) 據(jù) 邏 輯 結(jié) 構(gòu) 層 次 關(guān) 系 圖圖 1-4 邏 輯 結(jié) 構(gòu) 與 所 采 用 的 存 儲 結(jié) 構(gòu)線 性 表樹圖 順 序 存 儲 結(jié) 構(gòu)鏈 式 存 儲 結(jié) 構(gòu)復(fù) 合 存 儲 結(jié) 構(gòu)邏 輯 結(jié) 構(gòu) 物 理 結(jié) 構(gòu) 數(shù) 據(jù) 類 型 (Data Type)： 指 的 是 一 個 值 的 集 合 和 定義 在 該 值 集 上 的 一 組 操 作 的 總 稱 。 數(shù) 據(jù) 類 型 是 和 數(shù) 據(jù) 結(jié) 構(gòu) 密 切 相 關(guān) 的 一 個 概 念 。 在 C語 言 中 數(shù) 據(jù) 類 型 有 ： 基 本 類 型 和 構(gòu) 造 類 型 。 數(shù) 據(jù) 結(jié) 構(gòu) 不 同 于 數(shù) 據(jù) 類 型 ， 也 不 同 于 數(shù) 據(jù) 對 象 ， 它不 僅 要 描 述 數(shù) 據(jù) 類 型 的 數(shù) 據(jù) 對 象 ， 而 且 要 描 述 數(shù) 據(jù) 對 象各 元 素 之 間 的 相 互 關(guān) 系 。1.1.5 數(shù) 據(jù) 類 型 數(shù) 據(jù) 結(jié) 構(gòu) 的 主 要 運(yùn) 算 包 括 ： 建 立 (Create)一 個 數(shù) 據(jù) 結(jié) 構(gòu) ； 消 除 (Destroy)一 個 數(shù) 據(jù) 結(jié) 構(gòu) ； 從 一 個 數(shù) 據(jù) 結(jié) 構(gòu) 中 刪 除 (Delete)一 個 數(shù) 據(jù) 元 素 ； 把 一 個 數(shù) 據(jù) 元 素 插 入 (Insert)到 一 個 數(shù) 據(jù) 結(jié) 構(gòu) 中 ； 對 一 個 數(shù) 據(jù) 結(jié) 構(gòu) 進(jìn) 行 訪 問 (Access)； 對 一 個 數(shù) 據(jù) 結(jié) 構(gòu) (中 的 數(shù) 據(jù) 元 素 )進(jìn) 行 修 改(Modify)； 對 一 個 數(shù) 據(jù) 結(jié) 構(gòu) 進(jìn) 行 排 序 (Sort)； 對 一 個 數(shù) 據(jù) 結(jié) 構(gòu) 進(jìn) 行 查 找 (Search)。1.1.6 數(shù) 據(jù) 結(jié) 構(gòu) 的 運(yùn) 算 抽 象 數(shù) 據(jù) 類 型 (Abstract Data Type ， 簡 稱 ADT)： 是指 一 個 數(shù) 學(xué) 模 型 以 及 定 義 在 該 模 型 上 的 一 組 操 作 。 ADT的 定 義 僅 是 一 組 邏 輯 特 性 描 述 ， 與 其 在 計 算機(jī) 內(nèi) 的 表 示 和 實 現(xiàn) 無 關(guān) 。 因 此 ， 不 論 ADT的 內(nèi) 部 結(jié) 構(gòu) 如何 變 化 ， 只 要 其 數(shù) 學(xué) 特 性 不 變 ， 都 不 影 響 其 外 部 使 用 。 ADT的 形 式 化 定 義 是 三 元 組 ： ADT=(D， S， P)其 中 ： D是 數(shù) 據(jù) 對 象 ， S是 D上 的 關(guān) 系 集 ， P是 對 D的 基本 操 作 集 。1.2 抽 象 數(shù) 據(jù) 類 型 ADT的 一 般 定 義 形 式 是 ：ADT 數(shù) 據(jù) 對 象 ： 數(shù) 據(jù) 關(guān) 系 ： 基 本 操 作 ： ADT 其 中 數(shù) 據(jù) 對 象 和 數(shù) 據(jù) 關(guān) 系 的 定 義 用 偽 碼 描 述 。 基 本 操 作 的 定 義 是 ：()初 始 條 件 ： 操 作 結(jié) 果 ： 初 始 條 件 ： 描 述 操 作 執(zhí) 行 之 前 數(shù) 據(jù) 結(jié) 構(gòu) 和 參 數(shù) 應(yīng)滿 足 的 條 件 ;若 不 滿 足 ， 則 操 作 失 敗 ， 返 回 相 應(yīng) 的 出錯 信 息 。 操 作 結(jié) 果 ： 描 述 操 作 正 常 完 成 之 后 ， 數(shù) 據(jù) 結(jié) 構(gòu) 的變 化 狀 況 和 應(yīng) 返 回 的 結(jié) 果 。 1.3.1 算 法算 法 (Algorithm)： 是 對 特 定 問 題 求 解 方 法 (步 驟 )的 一 種描 述 ， 是 指 令 的 有 限 序 列 ， 其 中 每 一 條 指 令 表 示 一 個 或多 個 操 作 。算 法 具 有 以 下 五 個 特 性 有 窮 性 ： 一 個 算 法 必 須 總 是 在 執(zhí) 行 有 窮 步 之 后 結(jié)束 ， 且 每 一 步 都 在 有 窮 時 間 內(nèi) 完 成 。 確 定 性 ： 算 法 中 每 一 條 指 令 必 須 有 確 切 的 含 義 。不 存 在 二 義 性 。 且 算 法 只 有 一 個 入 口 和 一 個 出 口 。 可 行 性 ： 一 個 算 法 是 能 行 的 。 即 算 法 描 述 的 操 作都 可 以 通 過 已 經(jīng) 實 現(xiàn) 的 基 本 運(yùn) 算 執(zhí) 行 有 限 次 來 實 現(xiàn) 。1.3 算 法 分 析 初 步 輸 入 ： 一 個 算 法 有 零 個 或 多 個 輸 入 ， 這 些 輸 入取 自 于 某 個 特 定 的 對 象 集 合 。 輸 出 ： 一 個 算 法 有 一 個 或 多 個 輸 出 ， 這 些 輸 出是 同 輸 入 有 著 某 些 特 定 關(guān) 系 的 量 。 一 個 算 法 可 以 用 多 種 方 法 描 述 ， 主 要 有 ： 使 用 自 然語 言 描 述 ； 使 用 形 式 語 言 描 述 ； 使 用 計 算 機(jī) 程 序 設(shè) 計 語言 描 述 。 算 法 和 程 序 是 兩 個 不 同 的 概 念 。 一 個 計 算 機(jī) 程 序 是對 一 個 算 法 使 用 某 種 程 序 設(shè) 計 語 言 的 具 體 實 現(xiàn) 。 算 法 必須 可 終 止 意 味 著 不 是 所 有 的 計 算 機(jī) 程 序 都 是 算 法 。 在 本 門 課 程 的 學(xué) 習(xí) 、 作 業(yè) 練 習(xí) 、 上 機(jī) 實 踐 等 環(huán) 節(jié) ，算 法 都 用 C語 言 來 描 述 。 在 上 機(jī) 實 踐 時 ， 為 了 檢 查 算 法是 否 正 確 ， 應(yīng) 編 寫 成 完 整 的 C語 言 程 序 。 評 價 一 個 好 的 算 法 有 以 下 幾 個 標(biāo) 準(zhǔn) 正 確 性 (Correctness )： 算 法 應(yīng) 滿 足 具 體 問 題 的需 求 。 可 讀 性 (Readability)： 算 法 應(yīng) 容 易 供 人 閱 讀 和 交流 。 可 讀 性 好 的 算 法 有 助 于 對 算 法 的 理 解 和 修 改 。 健 壯 性 (Robustness)： 算 法 應(yīng) 具 有 容 錯 處 理 。 當(dāng)輸 入 非 法 或 錯 誤 數(shù) 據(jù) 時 ， 算 法 應(yīng) 能 適 當(dāng) 地 作 出 反 應(yīng)或 進(jìn) 行 處 理 ， 而 不 會 產(chǎn) 生 莫 名 其 妙 的 輸 出 結(jié) 果 。 通 用 性 (Generality)： 算 法 應(yīng) 具 有 一 般 性 ， 即 算法 的 處 理 結(jié) 果 對 于 一 般 的 數(shù) 據(jù) 集 合 都 成 立 。1.3.2 算 法 設(shè) 計 的 要 求 算 法 執(zhí) 行 時 間 需 通 過 依 據(jù) 該 算 法 編 制 的 程 序 在 計 算機(jī) 上 運(yùn) 行 所 消 耗 的 時 間 來 度 量 。 其 方 法 通 常 有 兩 種 ：事 后 統(tǒng) 計 ： 計 算 機(jī) 內(nèi) 部 進(jìn) 行 執(zhí) 行 時 間 和 實 際 占 用 空 間 的統(tǒng) 計 。 問 題 ： 必 須 先 運(yùn) 行 依 據(jù) 算 法 編 制 的 程 序 ； 依 賴 軟 硬件 環(huán) 境 ， 容 易 掩 蓋 算 法 本 身 的 優(yōu) 劣 ； 沒 有 實 際 價 值 。事 前 分 析 ： 求 出 該 算 法 的 一 個 時 間 界 限 函 數(shù) 。1.3.3 算 法 效 率 的 度 量 效 率 與 存 儲 量 需 求 ： 效 率 指 的 是 算 法 執(zhí) 行 的 時間 ； 存 儲 量 需 求 指 算 法 執(zhí) 行 過 程 中 所 需 要 的 最 大 存儲 空 間 。 一 般 地 ， 這 兩 者 與 問 題 的 規(guī) 模 有 關(guān) 。 與 此 相 關(guān) 的 因 素 有 ： 依 據(jù) 算 法 選 用 何 種 策 略 ； 問 題 的 規(guī) 模 ； 程 序 設(shè) 計 的 語 言 ； 編 譯 程 序 所 產(chǎn) 生 的 機(jī) 器 代 碼 的 質(zhì) 量 ； 機(jī) 器 執(zhí) 行 指 令 的 速 度 ； 撇 開 軟 硬 件 等 有 關(guān) 部 門 因 素 ， 可 以 認(rèn) 為 一 個 特 定 算法 “ 運(yùn) 行 工 作 量 ” 的 大 小 ， 只 依 賴 于 問 題 的 規(guī) 模 （ 通常 用 n表 示 ） ， 或 者 說 ， 它 是 問 題 規(guī) 模 的 函 數(shù) 。 算 法 分 析 應(yīng) 用 舉 例 算 法 中 基 本 操 作 重 復(fù) 執(zhí) 行 的 次 數(shù) 是 問 題 規(guī) 模 n的 某個 函 數(shù) ， 其 時 間 量 度 記 作 T(n)=O(f(n)， 稱 作 算 法 的漸 近 時 間 復(fù) 雜 度 (Asymptotic Time complexity)， 簡 稱 時間 復(fù) 雜 度 。 一 般 地 ， 常 用 最 深 層 循 環(huán) 內(nèi) 的 語 句 中 的 原 操 作 的 執(zhí)行 頻 度 (重 復(fù) 執(zhí) 行 的 次 數(shù) )來 表 示 。 “ O”的 定 義 ： 若 f(n)是 正 整 數(shù) n的 一 個 函 數(shù) ， 則 O(f(n)表 示 M0 ， 使 得 當(dāng) n n 0時 ， | f(n) | M | f(n0) | 。表 示 時 間 復(fù) 雜 度 的 階 有 ： O(1) ： 常 量 時 間 階 O (n)： 線 性 時 間 階 O( n) ： 對 數(shù) 時 間 階 O(n n) ： 線 性 對 數(shù) 時 間 階 O (nk)： k2 ， k次 方 時 間 階例 兩 個 n階 方 陣 的 乘 法 for(i=1， i=n; +i) for(j=1; j=n; +j) cij=0 ; for(k=1; k=n; +k) cij+=aik*bkj ; 由 于 是 一 個 三 重 循 環(huán) ， 每 個 循 環(huán) 從 1到 n， 則 總 次 數(shù) 為 ： n n n=n 3 時 間 復(fù) 雜 度 為 T(n)=O(n3)例 +x; s=0 ; 將 x自 增 看 成 是 基 本 操 作 ， 則 語 句 頻 度 為 ， 即 時間 復(fù) 雜 度 為 (1) 。 如 果 將 s=0也 看 成 是 基 本 操 作 ， 則 語 句 頻 度 為 ， 其 時間 復(fù) 雜 度 仍 為 (1)， 即 常 量 階 。例 for(i=1; i=n; +i) +x; s+=x ; 語 句 頻 度 為 ： 2n， 其 時 間 復(fù) 雜 度 為 ： O(n) ， 即 為 線 性階 。例 for(i=1; i=n; +i) for(j=1; j=n; +j) +x; s+=x ; 語 句 頻 度 為 ： 2n 2 ， 其 時 間 復(fù) 雜 度 為 ： O(n2) ， 即 為 平方 階 。 定 理 ： 若 A(n)=a m n m +a m-1 n m-1 +a1n+a0是 一 個 m次 多 項 式 ， 則 A(n)=O(n m)例 for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x; ai,j=x; 語 句 頻 度 為 ： 1+2+3+n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 時 間 復(fù) 雜 度 為 O(n2)， 即 此 算 法 的 時 間 復(fù) 雜 度 為 平 方階 。 一 個 算 法 時 間 為 O(1)的 算 法 ， 它 的 基 本 運(yùn) 算 執(zhí) 行的 次 數(shù) 是 固 定 的 。 因 此 ， 總 的 時 間 由 一 個 常 數(shù) （ 即零 次 多 項 式 ） 來 限 界 。 而 一 個 時 間 為 O(n 2)的 算 法 則由 一 個 二 次 多 項 式 來 限 界 。 以 下 六 種 計 算 算 法 時 間 的 多 項 式 是 最 常 用 的 。 其關(guān) 系 為 ： O(1)O( n)O(n)O(n n)O(n2)O(n3) 指 數(shù) 時 間 的 關(guān) 系 為 ： O(2n)O(n!)O(nn) 當(dāng) n取 得 很 大 時 ， 指 數(shù) 時 間 算 法 和 多 項 式 時 間 算 法在 所 需 時 間 上 非 常 懸 殊 。 因 此 ， 只 要 有 人 能 將 現(xiàn) 有 指數(shù) 時 間 算 法 中 的 任 何 一 個 算 法 化 簡 為 多 項 式 時 間 算 法 ，那 就 取 得 了 一 個 偉 大 的 成 就 。 有 的 情 況 下 ， 算 法 中 基 本 操 作 重 復(fù) 執(zhí) 行 的 次 數(shù) 還隨 問 題 的 輸 入 數(shù) 據(jù) 集 不 同 而 不 同 。 例 1： 素 數(shù) 的 判 斷 算 法 。Void prime( int n)/* n是 一 個 正 整 數(shù) */ int i=2 ; while ( (n% i)!=0 elseprintf(“ 嵌 套 的 最 深 層 語 句 是 i+； 其 頻 度 由 條 件 ( (n% i)!=0 -i)for (j=0; jaj+1) aj aj+1 ; change=TURE ; 最 好 情 況 ： 0次 最 壞 情 況 ： 1+2+3+ +n-1=n(n-1)/2 平 均 時 間 復(fù) 雜 度 為 ： O(n 2) 1.3.4 算 法 的 空 間 分 析 空 間 復(fù) 雜 度 (Space complexity) ： 是 指 算 法 編 寫 成程 序 后 ， 在 計 算 機(jī) 中 運(yùn) 行 時 所 需 存 儲 空 間 大 小 的 度 量 。記 作 ： S(n)=O(f(n) 其 中 ： n為 問 題 的 規(guī) 模 (或 大 小 )該 存 儲 空 間 一 般 包 括 三 個 方 面 ： 指 令 常 數(shù) 變 量 所 占 用 的 存 儲 空 間 ; 輸 入 數(shù) 據(jù) 所 占 用 的 存 儲 空 間 ; 輔 助 (存 儲 )空 間 。 一 般 地 ， 算 法 的 空 間 復(fù) 雜 度 指 的 是 輔 助 空 間 。 一 維 數(shù) 組 an： 空 間 復(fù) 雜 度 O(n) 二 維 數(shù) 組 anm： 空 間 復(fù) 雜 度 O(n*m) 習(xí) 題 一1 簡 要 回 答 術(shù) 語 ： 數(shù) 據(jù) ， 數(shù) 據(jù) 元 素 ， 數(shù) 據(jù) 結(jié) 構(gòu) ， 數(shù) 據(jù)類 型 。2 數(shù) 據(jù) 的 邏 輯 結(jié) 構(gòu) ？ 數(shù) 據(jù) 的 物 理 結(jié) 構(gòu) ？ 邏 輯 結(jié) 構(gòu) 與 物理 結(jié) 構(gòu) 的 區(qū) 別 和 聯(lián) 系 是 什 么 ？3 數(shù) 據(jù) 結(jié) 構(gòu) 的 主 要 運(yùn) 算 包 括 哪 些 ？4 算 法 分 析 的 目 的 是 什 么 ？ 算 法 分 析 的 主 要 方 面 是 什么 ？5 分 析 以 下 程 序 段 的 時 間 復(fù) 雜 度 ， 請 說 明 分 析 的 理 由或 原 因 。 Sum1( int n ) int p=1, sum=0, m ;for (m=1; m=n; m+) p*=m ; sum+=p ; return (sum) ;Sum2( int n ) int sum=0, m, t ;for (m=1; m=n; m+) p=1 ; for (t=1; t=m; t+) p*=t ;sum+=p ; return (sum) ; 遞 歸 函 數(shù)fact( int n ) if (n0時 ， 將 非 空 的 線 性 表 記 作 ： (a 1， a2， an) a1稱 為 線 性 表 的 第 一 個 (首 )結(jié) 點(diǎn) ， an稱 為 線 性 表 的 最 后一 個 (尾 )結(jié) 點(diǎn) 。2.1.1 線 性 表 的 定 義 a1， a2， ai-1都 是 ai(2 i n)的 前 驅(qū) ， 其 中 ai-1是 ai的 直 接前 驅(qū) ;ai+1， ai+2， an都 是 ai(1 i n-1)的 后 繼 ， 其 中 ai+1是 ai的直 接 后 繼 。2.1.2 線 性 表 的 邏 輯 結(jié) 構(gòu) 線 性 表 中 的 數(shù) 據(jù) 元 素 ai所 代 表 的 具 體 含 義 隨 具 體 應(yīng)用 的 不 同 而 不 同 ， 在 線 性 表 的 定 義 中 ， 只 不 過 是 一 個 抽象 的 表 示 符 號 。 線 性 表 中 的 結(jié) 點(diǎn) 可 以 是 單 值 元 素 (每 個 元 素 只 有 一個 數(shù) 據(jù) 項 ) 。例 1: 26個 英 文 字 母 組 成 的 字 母 表 ： (A， B， C、 、 Z） 例 2 ： 某 校 從 1978年 到 1983年 各 種 型 號 的 計 算 機(jī) 擁 有 量的 變 化 情 況 ： (6， 17， 28， 50， 92， 188）例 3 ： 一 副 撲 克 的 點(diǎn) 數(shù) (2， 3， 4， ， J， Q， K， A) 線 性 表 中 的 結(jié) 點(diǎn) 可 以 是 記 錄 型 元 素 ， 每 個 元 素 含有 多 個 數(shù) 據(jù) 項 ， 每 個 項 稱 為 結(jié) 點(diǎn) 的 一 個 域 。 每 個 元素 有 一 個 可 以 唯 一 標(biāo) 識 每 個 結(jié) 點(diǎn) 的 數(shù) 據(jù) 項 組 ， 稱 為關(guān) 鍵 字 。例 4 ： 某 校 2001級 同 學(xué) 的 基 本 情 況 ： (2001414101， 張 里 戶 ， 男 ， 06/24/1983)， (2001414102， 張 化 司 ， 男 ， 08/12/1984) ， (2001414102， 李 利 辣 ， 女 ， 08/12/1984) 若 線 性 表 中 的 結(jié) 點(diǎn) 是 按 值 (或 按 關(guān) 鍵 字 值 )由 小 到大 (或 由 大 到 小 )排 列 的 ， 稱 線 性 表 是 有 序 的 。 2.1.3 線 性 表 的 抽 象 數(shù) 據(jù) 類 型 定 義ADT List數(shù) 據(jù) 對 象 ： D = ai | ai ElemSet, i=1,2,n, n 0 數(shù) 據(jù) 關(guān) 系 ： R = | ai-1, ai D, i=2,3,n 基 本 操 作 ：InitList( 數(shù) 據(jù) 元 素 之 間 的 關(guān) 系 是 以 元 素 在 計 算 機(jī) 內(nèi) “ 物 理位 置 相 鄰 ” 來 體 現(xiàn) 。 設(shè) 有 非 空 的 線 性 表 ： (a 1， a2， an) 。 順 序 存 儲 如 圖2-1所 示 。 2.2.1 線 性 表 的 順 序 存 儲 結(jié) 構(gòu) 在 具 體 的 機(jī) 器 環(huán) 境 下 ： 設(shè) 線 性 表 的 每 個 元 素 需 占 用l個 存 儲 單 元 ， 以 所 占 的 第 一 個 單 元 的 存 儲 地 址 作 為 數(shù)據(jù) 元 素 的 存 儲 位 置 。 則 線 性 表 中 第 i+1個 數(shù) 據(jù) 元 素 的 存儲 位 置 LOC(ai+1)和 第 i個 數(shù) 據(jù) 元 素 的 存 儲 位 置 LOC(ai)之間 滿 足 下 列 關(guān) 系 ： LOC(ai+1)=LOC(ai)+l 線 性 表 的 第 i個 數(shù) 據(jù) 元 素 ai的 存 儲 位 置 為 ： LOC(ai)=LOC(a1)+(i-1)*l a1 a2 ai an Loc(a1) Loc(ai)+(i-1)* l 圖 2-1 線 性 表 的 順 序 存 儲 表 示 在 高 級 語 言 (如 C語 言 )環(huán) 境 下 ： 數(shù) 組 具 有 隨 機(jī) 存 取的 特 性 ， 因 此 ， 借 助 數(shù) 組 來 描 述 順 序 表 。 除 了 用 數(shù) 組 來存 儲 線 性 表 的 元 素 之 外 ， 順 序 表 還 應(yīng) 該 有 表 示 線 性 表 的長 度 屬 性 ， 所 以 用 結(jié) 構(gòu) 類 型 來 定 義 順 序 表 類 型 。#define OK 1#define ERROR -1#define MAX_SIZE 100typedef int Status ;typedef int ElemType ; typedef struct sqlist ElemType Elem_arrayMAX_SIZE ;int length ; SqList ; 2.2.2 順 序 表 的 基 本 操 作 順 序 存 儲 結(jié) 構(gòu) 中 ， 很 容 易 實 現(xiàn) 線 性 表 的 一 些 操 作 ：初 始 化 、 賦 值 、 查 找 、 修 改 、 插 入 、 刪 除 、 求 長 度 等 。以 下 將 對 幾 種 主 要 的 操 作 進(jìn) 行 討 論 。1 順 序 線 性 表 初 始 化 Status Init_SqList( SqList *L ) L-elem_array=( ElemType * )malloc(MAX_SIZE*sizeof( ElemType ) ) ;if ( !L - elem_array ) return ERROR ; else L-length= 0 ; return OK ; 2 順 序 線 性 表 的 插 入 在 線 性 表 L= (a1， a i-1， ai， ai+1， ， an) 中 的第 i(1 i n)個 位 置 上 插 入 一 個 新 結(jié) 點(diǎn) e， 使 其 成 為 線 性表 ： L=(a1， a i-1， e， ai， ai+1， ， an) 實 現(xiàn) 步 驟(1) 將 線 性 表 L中 的 第 i個 至 第 n個 結(jié) 點(diǎn) 后 移 一 個 位 置 。(2) 將 結(jié) 點(diǎn) e插 入 到 結(jié) 點(diǎn) ai-1之 后 。 (3) 線 性 表 長 度 加 1。 算 法 描 述Status Insert_SqList(Sqlist *L， int i ， ElemType e) int j ;if ( iL-length-1) return ERROR ;if (L-length=MAX_SIZE) printf(“線 性 表 溢 出 !n”); return ERROR ; for ( j=L-length1; j=i-1; -j )L-Elem_arrayj+1=L-Elem_arrayj;/* i-1位 置 以 后 的 所 有 結(jié) 點(diǎn) 后 移 */L-Elem_arrayi-1=e; /* 在 i-1位 置 插 入 結(jié) 點(diǎn) */L-length+ ;return OK ; 時 間 復(fù) 雜 度 分 析 在 線 性 表 L中 的 第 i個 元 素 之 前 插 入 新 結(jié) 點(diǎn) ， 其 時間 主 要 耗 費(fèi) 在 表 中 結(jié) 點(diǎn) 的 移 動 操 作 上 ， 因 此 ， 可 用 結(jié) 點(diǎn)的 移 動 來 估 計 算 法 的 時 間 復(fù) 雜 度 。 設(shè) 在 線 性 表 L中 的 第 i個 元 素 之 前 插 入 結(jié) 點(diǎn) 的 概 率為 Pi， 不 失 一 般 性 ， 設(shè) 各 個 位 置 插 入 是 等 概 率 ， 則Pi=1/(n+1)， 而 插 入 時 移 動 結(jié) 點(diǎn) 的 次 數(shù) 為 n-i+1?？?的 平 均 移 動 次 數(shù) ： Einsert=pi*(n-i+1) (1 i n) E insert=n/2 。 即 在 順 序 表 上 做 插 入 運(yùn) 算 ， 平 均 要 移 動 表 上 一 半 結(jié)點(diǎn) 。 當(dāng) 表 長 n較 大 時 ， 算 法 的 效 率 相 當(dāng) 低 。 因 此 算 法 的平 均 時 間 復(fù) 雜 度 為 O(n)。 3 順 序 線 性 表 的 刪 除 在 線 性 表 L=(a1， a i-1， ai， ai+1， ， an) 中 刪 除結(jié) 點(diǎn) ai(1 i n)， 使 其 成 為 線 性 表 ： L= (a1， ai-1， ai+1， ， an) 實 現(xiàn) 步 驟(1) 將 線 性 表 L中 的 第 i+1個 至 第 n個 結(jié) 點(diǎn) 依 此 向 前 移動 一 個 位 置 。(2) 線 性 表 長 度 減 1。算 法 描 述ElemType Delete_SqList(Sqlist *L， int i) int k ; ElemType x ; if (L-length=0) printf(“線 性 表 L為 空 !n”); return ERROR; else if ( iL-length ) printf(“要 刪 除 的 數(shù) 據(jù) 元 素 不 存 在 !n”) ; return ERROR ; else x=L-Elem_arrayi-1 ; /*保 存 結(jié) 點(diǎn) 的 值 */for ( k=i ; klength ; k+) L-Elem_arrayk-1=L-Elem_arrayk; /* i位 置 以 后 的 所 有 結(jié) 點(diǎn) 前 移 */L-length-; return (x); 時 間 復(fù) 雜 度 分 析 刪 除 線 性 表 L中 的 第 i個 元 素 ， 其 時 間 主 要 耗 費(fèi) 在 表中 結(jié) 點(diǎn) 的 移 動 操 作 上 ， 因 此 ， 可 用 結(jié) 點(diǎn) 的 移 動 來 估 計 算法 的 時 間 復(fù) 雜 度 。 設(shè) 在 線 性 表 L中 刪 除 第 i個 元 素 的 概 率 為 Pi， 不 失一 般 性 ， 設(shè) 刪 除 各 個 位 置 是 等 概 率 ， 則 Pi=1/n， 而 刪 除時 移 動 結(jié) 點(diǎn) 的 次 數(shù) 為 n-i。則 總 的 平 均 移 動 次 數(shù) ： Edelete=pi*(n-i) (1 i n) Edelete=(n-1)/2 。 即 在 順 序 表 上 做 刪 除 運(yùn) 算 ， 平 均 要 移 動 表 上 一 半 結(jié)點(diǎn) 。 當(dāng) 表 長 n較 大 時 ， 算 法 的 效 率 相 當(dāng) 低 。 因 此 算 法 的平 均 時 間 復(fù) 雜 度 為 O(n)。 4 順 序 線 性 表 的 查 找 定 位 刪 除 在 線 性 表 L= (a1， a2， ， an) 中 刪 除 值 為 x的 第 一個 結(jié) 點(diǎn) 。實 現(xiàn) 步 驟(1) 在 線 性 表 L查 找 值 為 x的 第 一 個 數(shù) 據(jù) 元 素 。(2) 將 從 找 到 的 位 置 至 最 后 一 個 結(jié) 點(diǎn) 依 次 向 前 移 動 一個 位 置 。 (3) 線 性 表 長 度 減 1。算 法 描 述Status Locate_Delete_SqList(Sqlist *L， ElemType x) /* 刪 除 線 性 表 L中 值 為 x的 第 一 個 結(jié) 點(diǎn) */ int i=0 , k ; while (ilength) /*查 找 值 為 x的 第 一 個 結(jié) 點(diǎn) */ if (L-Elem_arrayi!=x ) i+ ; else for ( k=i+1; klength; k+) L-Elem_arrayk-1=L-Elem_arrayk; L-length-; break ; if (iL-length) printf(“要 刪 除 的 數(shù) 據(jù) 元 素 不 存 在 !n”) ; return ERROR ; return OK; 時 間 復(fù) 雜 度 分 析 時 間 主 要 耗 費(fèi) 在 數(shù) 據(jù) 元 素 的 比 較 和 移 動 操 作 上 。首 先 ， 在 線 性 表 L中 查 找 值 為 x的 結(jié) 點(diǎn) 是 否 存 在 ;其 次 ， 若 值 為 x的 結(jié) 點(diǎn) 存 在 ， 且 在 線 性 表 L中 的 位 置 為 i ，則 在 線 性 表 L中 刪 除 第 i個 元 素 。 設(shè) 在 線 性 表 L刪 除 數(shù) 據(jù) 元 素 概 率 為 Pi， 不 失 一 般 性 ，設(shè) 各 個 位 置 是 等 概 率 ， 則 Pi=1/n。 比 較 的 平 均 次 數(shù) ： Ecompare=pi*i (1 i n) E compare=(n+1)/2 。 刪 除 時 平 均 移 動 次 數(shù) ： Edelete=pi*(n-i) (1 i n) Edelete=(n-1)/2 。 平 均 時 間 復(fù) 雜 度 ： Ecompare+Edelete=n ，即 為 O(n) 2.3 線 性 表 的 鏈 式 存 儲 2.3.1 線 性 表 的 鏈 式 存 儲 結(jié) 構(gòu) 鏈 式 存 儲 ： 用 一 組 任 意 的 存 儲 單 元 存 儲 線 性 表中 的 數(shù) 據(jù) 元 素 。 用 這 種 方 法 存 儲 的 線 性 表 簡 稱 線 性 鏈表 。 存 儲 鏈 表 中 結(jié) 點(diǎn) 的 一 組 任 意 的 存 儲 單 元 可 以 是 連續(xù) 的 ， 也 可 以 是 不 連 續(xù) 的 ， 甚 至 是 零 散 分 布 在 內(nèi) 存 中的 任 意 位 置 上 的 。 鏈 表 中 結(jié) 點(diǎn) 的 邏 輯 順 序 和 物 理 順 序 不 一 定 相 同 。 為 了 正 確 表 示 結(jié) 點(diǎn) 間 的 邏 輯 關(guān) 系 ， 在 存 儲 每 個 結(jié) 點(diǎn)值 的 同 時 ， 還 必 須 存 儲 指 示 其 直 接 后 繼 結(jié) 點(diǎn) 的 地 址 (或位 置 )， 稱 為 指 針 (pointer)或 鏈 (link)， 這 兩 部 分 組 成 了鏈 表 中 的 結(jié) 點(diǎn) 結(jié) 構(gòu) ， 如 圖 2-2所 示 。 鏈 表 是 通 過 每 個 結(jié) 點(diǎn) 的 指 針 域 將 線 性 表 的 n個 結(jié) 點(diǎn)按 其 邏 輯 次 序 鏈 接 在 一 起 的 。 每 一 個 結(jié) 只 包 含 一 個 指 針 域 的 鏈 表 ， 稱 為 單 鏈 表 。 為 操 作 方 便 ， 總 是 在 鏈 表 的 第 一 個 結(jié) 點(diǎn) 之 前 附 設(shè) 一個 頭 結(jié) 點(diǎn) (頭 指 針 )head指 向 第 一 個 結(jié) 點(diǎn) 。 頭 結(jié) 點(diǎn) 的 數(shù) 據(jù)域 可 以 不 存 儲 任 何 信 息 (或 鏈 表 長 度 等 信 息 )。data next 圖 2-2 鏈 表 結(jié) 點(diǎn) 結(jié) 構(gòu)data ： 數(shù) 據(jù) 域 ， 存 放 結(jié) 點(diǎn) 的 值 。 next ： 指 針域 ， 存 放 結(jié) 點(diǎn) 的 直 接 后 繼 的 地 址 。 3695head fat1100bat1300cat1305eat3700hatNULL1100370013001305bat cat eat fat hat head 圖 2-3 帶 頭 結(jié) 點(diǎn) 的 單 鏈 表 的 邏 輯 狀 態(tài) 、 物 理 存 儲 方 式 單 鏈 表 是 由 表 頭 唯 一 確 定 ， 因 此 單鏈 表 可 以 用 頭 指 針 的 名 字 來 命 名 。例 1、 線 性 表 L=(bat， cat， eat， fat，hat)其 帶 頭 結(jié) 點(diǎn) 的 單 鏈 表 的 邏 輯 狀 態(tài) 和 物 理存 儲 方 式 如 圖 2-3所 示 。 1 結(jié) 點(diǎn) 的 描 述 與 實 現(xiàn) C語 言 中 用 帶 指 針 的 結(jié) 構(gòu) 體 類 型 來 描 述typedef struct Lnode ElemType data; /*數(shù) 據(jù) 域 ， 保 存 結(jié) 點(diǎn) 的 值 */struct Lnode *next; /*指 針 域 */LNode; /*結(jié) 點(diǎn) 的 類 型 */2 結(jié) 點(diǎn) 的 實 現(xiàn) 結(jié) 點(diǎn) 是 通 過 動 態(tài) 分 配 和 釋 放 來 的 實 現(xiàn) ， 即 需 要 時 分配 ， 不 需 要 時 釋 放 。 實 現(xiàn) 時 是 分 別 使 用 C語 言 提 供 的 標(biāo)準(zhǔn) 函 數(shù) ： malloc() ， realloc()， sizeof() ， free() 。 動 態(tài) 分 配 p=(LNode*)malloc(sizeof(LNode);函 數(shù) malloc分 配 了 一 個 類 型 為 LNode的 結(jié) 點(diǎn) 變 量 的 空 間 ，并 將 其 首 地 址 放 入 指 針 變 量 p中 。動 態(tài) 釋 放 free(p) ;系 統(tǒng) 回 收 由 指 針 變 量 p所 指 向 的 內(nèi) 存 區(qū) 。 P必 須 是 最 近 一次 調(diào) 用 malloc函 數(shù) 時 的 返 回 值 。3 最 常 用 的 基 本 操 作 及 其 示 意 圖 結(jié) 點(diǎn) 的 賦 值 LNode *p;p=(LNode*)malloc(sizeof(LNode); p-data=20; p-next=NULL ; p20 NULL 常 見 的 指 針 操 作 q=p ; pa 操 作 前 pa q操 作 后 q=p-next ; bpa 操 作 前 操 作 后 qbpa p=p-next ; bpa 操 作 前 操 作 后 pba q-next=p ; c p bqa 操 作 前 操 作 后q b a c p(a) q-next=p-next ;(a) x y p bqa 操 作 前 操 作 后q b ax y p操 作 前 ypx bqa 操 作 后 ypx bqa(b) 操 作 前 ypx bqa 操 作 后 ypx bqa(b) 2.3.2 單 線 性 鏈 式 的 基 本 操 作1 建 立 單 鏈 表 假 設(shè) 線 性 表 中 結(jié) 點(diǎn) 的 數(shù) 據(jù) 類 型 是 整 型 ， 以 32767作為 結(jié) 束 標(biāo) 志 。 動 態(tài) 地 建 立 單 鏈 表 的 常 用 方 法 有 如 下 兩 種 ：頭 插 入 法 ， 尾 插 入 法 。 頭 插 入 法 建 表 從 一 個 空 表 開 始 ， 重 復(fù) 讀 入 數(shù) 據(jù) ， 生 成 新 結(jié) 點(diǎn) ，將 讀 入 數(shù) 據(jù) 存 放 到 新 結(jié) 點(diǎn) 的 數(shù) 據(jù) 域 中 ， 然 后 將 新 結(jié) 點(diǎn) 插入 到 當(dāng) 前 鏈 表 的 表 頭 上 ， 直 到 讀 入 結(jié) 束 標(biāo) 志 為 止 。 即 每次 插 入 的 結(jié) 點(diǎn) 都 作 為 鏈 表 的 第 一 個 結(jié) 點(diǎn) 。 算 法 描 述LNode *create_LinkList(void) /* 頭 插 入 法 創(chuàng) 建 單 鏈 表 ,鏈 表 的 頭 結(jié) 點(diǎn) head作 為 返 回 值 */ int data ;LNode *head, *p;head= (LNode *) malloc( sizeof(LNode);head-next=NULL; /* 創(chuàng) 建 鏈 表 的 表 頭 結(jié) 點(diǎn) head */ while (1) scanf(“%d”, if (data=32767) break ;p= (LNode *)malloc(sizeof(LNode);pdata=data; /* 數(shù) 據(jù) 域 賦 值 */ pnext=headnext ; headnext=p ; /* 鉤 鏈 ， 新 創(chuàng) 建 的 結(jié) 點(diǎn) 總 是 作 為 第 一 個 結(jié) 點(diǎn) */return (head);(2) 尾 插 入 法 建 表 頭 插 入 法 建 立 鏈 表 雖 然 算 法 簡 單 ， 但 生 成 的 鏈 表中 結(jié) 點(diǎn) 的 次 序 和 輸 入 的 順 序 相 反 。 若 希 望 二 者 次 序 一 致 ，可 采 用 尾 插 法 建 表 。 該 方 法 是 將 新 結(jié) 點(diǎn) 插 入 到 當(dāng) 前 鏈 表的 表 尾 ， 使 其 成 為 當(dāng) 前 鏈 表 的 尾 結(jié) 點(diǎn) 。 算 法 描 述LNode *create_LinkList(void) /* 尾 插 入 法 創(chuàng) 建 單 鏈 表 ,鏈 表 的 頭 結(jié) 點(diǎn) head作 為 返 回 值 */ int data ;LNode *head, *p, *q;head=p=(LNode *)malloc(sizeof(LNode); p-next=NULL; /* 創(chuàng) 建 單 鏈 表 的 表 頭 結(jié) 點(diǎn) head */while (1) scanf(“%d”,if (data=32767) break ;q= (LNode *)malloc(sizeof(LNode); qdata=data; /* 數(shù) 據(jù) 域 賦 值 */qnext=pnext; pnext=q; p=q ; /*鉤 鏈 ， 新 創(chuàng) 建 的 結(jié) 點(diǎn) 總 是 作 為 最 后 一 個 結(jié) 點(diǎn) */return (head); 無 論 是 哪 種 插 入 方 法 ， 如 果 要 插 入 建 立 的 單 線 性鏈 表 的 結(jié) 點(diǎn) 是 n個 ， 算 法 的 時 間 復(fù) 雜 度 均 為 O(n)。 對 于 單 鏈 表 ， 無 論 是 哪 種 操 作 ， 只 要 涉 及 到 鉤 鏈(或 重 新 鉤 鏈 )， 如 果 沒 有 明 確 給 出 直 接 后 繼 ， 鉤 鏈 (或重 新 鉤 鏈 )的 次 序 必 須 是 “ 先 右 后 左 ” 。 2 單 鏈 表 的 查 找(1) 按 序 號 查 找 取 單 鏈 表 中 的 第 i個 元 素 。 對 于 單 鏈 表 ， 不 能 象 順 序 表 中 那 樣 直 接 按 序 號 i訪問 結(jié) 點(diǎn) ， 而 只 能 從 鏈 表 的 頭 結(jié) 點(diǎn) 出 發(fā) ， 沿 鏈 域 next逐 個結(jié) 點(diǎn) 往 下 搜 索 ， 直 到 搜 索 到 第 i個 結(jié) 點(diǎn) 為 止 。 因 此 ， 鏈表 不 是 隨 機(jī) 存 取 結(jié) 構(gòu) 。 設(shè) 單 鏈 表 的 長 度 為 n， 要 查 找 表 中 第 i個 結(jié) 點(diǎn) ， 僅當(dāng) 1 i n時 ， i的 值 是 合 法 的 。 算 法 描 述ElemType Get_Elem(LNode *L ， int i) int j ; LNode *p;p=L-next; j=1; /* 使 p指 向 第 一 個 結(jié) 點(diǎn) */while (p!=NULL j+; /* 移 動 指 針 p , j計 數(shù) */if (j!=i) return(-32768) ;else return(p-data); /* p為 NULL 表 示 i太 大 ; ji表 示 i為 0 */移 動 指 針 p的 頻 度 ：in： n次 。 時 間 復(fù) 雜 度 : O(n)。 (2) 按 值 查 找 按 值 查 找 是 在 鏈 表 中 ， 查 找 是 否 有 結(jié) 點(diǎn) 值 等 于 給 定值 key的 結(jié) 點(diǎn) ? 若 有 ， 則 返 回 首 次 找 到 的 值 為 key的 結(jié) 點(diǎn)的 存 儲 位 置 ； 否 則 返 回 NULL。 查 找 時 從 開 始 結(jié) 點(diǎn) 出 發(fā) ，沿 鏈 表 逐 個 將 結(jié) 點(diǎn) 的 值 和 給 定 值 key作 比 較 。 算 法 描 述LNode *Locate_Node(LNode *L， int key)/* 在 以 L為 頭 結(jié) 點(diǎn) 的 單 鏈 表 中 查 找 值 為 key的 第 一 個 結(jié) 點(diǎn) */ LNode *p=Lnext;while ( p!=NULLif (pdata=key) return p;else printf(“所 要 查 找 的 結(jié) 點(diǎn) 不 存 在 !n”); retutn(NULL); 算 法 的 執(zhí) 行 與 形 參 key有 關(guān) ， 平 均 時 間 復(fù) 雜 度 為 O(n)。 3 單 鏈 表 的 插 入 插 入 運(yùn) 算 是 將 值 為 e的 新 結(jié) 點(diǎn) 插 入 到 表 的 第 i個 結(jié)