第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 計算機(jī)導(dǎo)論 揚州職業(yè)大學(xué) 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 第十章 數(shù)據(jù)結(jié)構(gòu) 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 學(xué)習(xí)目標(biāo) 了解數(shù)據(jù)結(jié)構(gòu)的基本概念 掌握數(shù)據(jù)結(jié)構(gòu)的典型應(yīng)用 熟悉常見的查詢和排序算法 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 1： 了解數(shù)據(jù)結(jié)構(gòu)的基本概念 數(shù)據(jù)結(jié)構(gòu)的基本概念 算法 算法的基本要素 算法效率的度量 算法設(shè)計的要求 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 1： 了解數(shù)據(jù)結(jié)構(gòu)的基本概念 數(shù)據(jù)結(jié)構(gòu)的基本概念 數(shù)據(jù) 數(shù)據(jù)元素 數(shù)據(jù)項 數(shù)據(jù)類型 數(shù)據(jù)結(jié)構(gòu) 邏輯結(jié)構(gòu) 集合數(shù)據(jù) 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖形結(jié)構(gòu) 圖 10輯結(jié)構(gòu)的基本類型 存儲結(jié)構(gòu) 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 1： 了解數(shù)據(jù)結(jié)構(gòu)的基本概念 算法 算法的概念：是對特定問題求解操作步驟的準(zhǔn)確而完整的描述 。 算法的特性： 可行性 確定性 有窮性 輸入 輸出 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 1： 了解數(shù)據(jù)結(jié)構(gòu)的基本概念 算法的基本要素 算法對數(shù)據(jù)的運算和操作 運算和操作有：算術(shù)運算 、 邏輯運算 、 關(guān)系運算 、 數(shù)據(jù)傳輸四類 。 算法的控制結(jié)構(gòu) 算法的功能不僅取決于所選用的操作 ， 還與算法的控制結(jié)構(gòu)有很大關(guān)系 。 算法的控制結(jié)構(gòu)指的是算法中各操作之間的執(zhí)行順序 。一般一個算法中可以有順序 、 選擇和循環(huán)三種基本控制結(jié)構(gòu)組合而成 。 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 1： 了解數(shù)據(jù)結(jié)構(gòu)的基本概念 算法效率的度量 衡量算法性能的過程叫算法分析 ， 通過對算法的分析可以獲知完成同一任務(wù)的不同算法的優(yōu)劣 。 對算法的性能分析主要集中在對算法時間復(fù)雜度和空間復(fù)雜度的衡量 。 算法的時間復(fù)雜度 算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量 。 算法的空間復(fù)雜度 算法的空間復(fù)雜度 ， 一般指執(zhí)行這個算法所需要的內(nèi)存空間 。 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 1： 了解數(shù)據(jù)結(jié)構(gòu)的基本概念 算法設(shè)計的要求 正確性 可讀性 容錯性 高效率和低存儲量 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 2： 掌握數(shù)據(jù)結(jié)構(gòu)的典型應(yīng)用 線性表 棧 隊列 樹和二叉樹 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 2： 掌握數(shù)據(jù)結(jié)構(gòu)的典型應(yīng)用 線性表 線性表概念 線性表特點 線性表的基本運算 線性表的順序存儲結(jié)構(gòu) 順序表的運算：插入結(jié)點的運算；刪除結(jié)點的運算 線性表鏈?zhǔn)酱鎯Y(jié)構(gòu) 線性鏈表的運算：線性鏈表結(jié)點的插入；線性鏈表的結(jié)點刪除 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 2： 掌握數(shù)據(jù)結(jié)構(gòu)的典型應(yīng)用 棧 棧的概念 棧是一種特殊的線性表 ， 棧的插入和刪除操作均在線性表的一端進(jìn)行 。 允許進(jìn)行插入和刪除操作的一端稱為棧頂 （ ， 另一端稱為棧底 （ 。 棧的順序存儲和運算 入棧 退棧 讀取棧頂元素 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 2： 掌握數(shù)據(jù)結(jié)構(gòu)的典型應(yīng)用 隊列 隊列簡稱隊，它也是一種特殊的線性表。隊列允許在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除，允許插入的一端稱為隊尾，通常有一個隊尾指針 許刪除的一端稱為隊首。 通常有一個隊首指針 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 2： 掌握數(shù)據(jù)結(jié)構(gòu)的典型應(yīng)用 樹和二叉樹 樹的基本概念：是一種非常重要的非線性結(jié)構(gòu) 。 樹的幾個特點 樹的定義是一個遞歸定義； 樹的根結(jié)點沒有前件，其他結(jié)點有且只有一個前件，稱為父結(jié)點； 樹中任何一個結(jié)點，可以有 0個或多個后件，稱為子結(jié)點。 樹的術(shù)語 度：在樹中 ， 一個節(jié)點擁有的后件數(shù)稱為該結(jié)點的度 。 層次：結(jié)點的層次表示結(jié)點在樹中的相對位置 。 樹的深度：樹的最大層次稱為樹的深度 。 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 2： 掌握數(shù)據(jù)結(jié)構(gòu)的典型應(yīng)用 樹和二叉樹 二叉樹：二叉樹是重要的樹型結(jié)構(gòu) 。 、 二叉樹的特點： 二叉樹可以為空樹，不含有任何結(jié)點； 非空二叉樹只有一個根結(jié)點； 二叉樹是有序樹，每個結(jié)點最多有兩棵子樹，分別稱為左子樹和右子樹，允許樹只有左或右子樹。 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 3： 熟悉常見的查詢和排序算法 查找技術(shù) 排序技術(shù) 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 3： 熟悉常見的查詢和排序算法 查找技術(shù) 順序查找 順序查找是最簡單、最基本的查找方法。線性順序查找方式適用于順序存儲和鏈接存儲的線性表。 二分查找 線性順序查找方式適用于順序存儲的線性表。 在最壞的情況下，二分查找法需比較 順序查找需比較 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 3： 熟悉常見的查詢和排序算法 排序技術(shù) 所謂排序，是把一組無序數(shù)據(jù)整理成按值遞增（或遞減）的次序重新排列，使其成為一個按值大小排列的有序序列。 冒泡排序 簡單插入排序 簡單選擇排序 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 3： 熟悉常見的查詢和排序算法 冒泡排序 冒泡排序?qū)儆诮粨Q類排序方法。它是通過相鄰數(shù)據(jù)元素中的比較，使得較小的值上升，較大的值沉到底部，逐步將線性表從無序調(diào)整為有序線性表。 冒泡排序方法如下： 對于 2，若逆序（ 2）則交換之，然后比較 直到 n。這時最大值到了最后（第 這稱為一趟排序，其進(jìn)行了 重復(fù)，但只比較到第 稱為第二趟比較； 共進(jìn)行 比較，完成整個排序。 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 3： 熟悉常見的查詢和排序算法 簡單插入排序 簡單插入排序?qū)儆谑遣迦腩惻判?。所謂插入排序，就是將無序序列中的各個元素插入到已經(jīng)有序的線性表中。 簡單插入排序的基本思路：首先將待排序數(shù)據(jù)序列中的第一個數(shù)據(jù)元素作為一個有序表，從第二個數(shù)據(jù)元素開始，依次將數(shù)據(jù)元素插入到前邊已排好序的序列中，直至全部數(shù)據(jù)序列有序。在最壞情況下，簡單插入排序需要進(jìn)行 n（ 。 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 任務(wù) 3： 熟悉常見的查詢和排序算法 簡單選擇排序 簡單選擇排序的基本思想是：排序過程中，依次從待排序的數(shù)據(jù)序列中選擇出值最小的元素、值次小的元素、 ，并分別將它們定位到序列左側(cè)的第一個位置、第二個位置、 ，最后剩下一個值最大的數(shù)據(jù)元素位于序列的最后一個位置，從而使待排序的數(shù)據(jù)序列成為按值由小到大排列的有序序列。 第十章 數(shù)據(jù)結(jié)構(gòu) 面向職業(yè) 體現(xiàn)系統(tǒng) 重視實踐 強(qiáng)化應(yīng)用 小結(jié)： 數(shù)據(jù)結(jié)構(gòu)和算法是程序設(shè)計中兩個重要問題。 線性表是最簡單、最常用的一種數(shù)據(jù)結(jié)構(gòu) 。 棧是一種特殊的線性表，采用“先進(jìn)后出”或者“后進(jìn)先出”方式操作。 隊列是另一種特殊的線性表 ，允許在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除。