計算機軟件基礎課件：數(shù)據結構概述

數(shù)據結構概述《計算機軟件基礎》本章重點難點本章重點：數(shù)據結構的基本概念；線性結構和非線性結構的特點；數(shù)據的邏輯結構；數(shù)據的物理結構；存儲方法；時間復雜度。本章難點：分析簡單算法的時間復雜度。01.引言02.算法的性能度量主要內容01引言1.基本概念1）數(shù)據

是對客觀事物的符號表示。

在計算機科學中是指所有能輸入到計算機中并被計算機程序識別和處理的符號的集合。數(shù)據大致可分為兩類：數(shù)值型數(shù)據：整數(shù)、浮點數(shù)、雙精度數(shù)等；非數(shù)值型數(shù)據：字符、字符串、文本、圖形、圖像、語音等。2）數(shù)據元素是數(shù)據的基本單位。通常由一個或若干個數(shù)據項組成。數(shù)據項是數(shù)據的不可分割的最小單位。3）數(shù)據對象是性質相同的數(shù)據元素的集合，是數(shù)據的一個子集。

例如，大寫字母字符數(shù)據對象是集合Ω={‘A’,‘B’,…,‘Z’}。4）數(shù)據結構是相互之間存在一種或多種特定關系（稱為結構）的數(shù)據元素的集合?？捎洖椋?/p>

DS=(D,S)

其中，DS表示一種數(shù)據結構，D是數(shù)據元素的有限集合，S是D上關系的有限集合。2.數(shù)據結構的分類1）集合2）線性結構

所有數(shù)據元素都按某種次序排列在一個序列中

根據對線性結構中數(shù)據元素存取方法的不同分為：

直接存取結構

順序存取結構

字典結構線性結構中各數(shù)據元素之間的線性關系除第一個數(shù)據元素外，其他每個數(shù)據元素都有一個且僅有一個直接前驅，第一個數(shù)據元素沒有前驅；除最后一個元素數(shù)據外，其他每個數(shù)據元素都有一個且僅有一個直接后繼最后一個元素沒有后繼。3）樹形結構

結構中的數(shù)據元素之間存在一個對多個的關系。4）圖結構圖結構中的數(shù)據元素之間存在多個對多個的關系。樹形結構和圖結構均為非線性結構：各個數(shù)據元素不再保持在一個線性序列中每個數(shù)據元素可能與多個其他數(shù)據元素發(fā)生聯(lián)系2.數(shù)據的邏輯結構和物理結構1）數(shù)據的邏輯結構簡稱數(shù)據結構描述的是數(shù)據元素之間的邏輯關系它是指從解決問題的需要出發(fā)，為實現(xiàn)必要的功能所建立的數(shù)據結構2）數(shù)據的物理結構又稱存儲結構

是指數(shù)據應該如何在計算機內存放，是數(shù)據的邏輯結構的物理存儲方式（存儲映像）數(shù)據的邏輯結構和存儲結構是密切相關的兩個方面。任何一個算法的設計取決于選定的數(shù)據的邏輯結構，而算法的實現(xiàn)依賴于采用的物理結構。3）存儲方法順序存儲方法數(shù)據元素之間的邏輯關系由存儲單元的鄰接位置關系來體現(xiàn)

通常，可借助程序語言中的一維數(shù)組來描述鏈接存儲方法數(shù)據元素之間的邏輯關系由附加的指針指示通常，要借助程序語言中的指針類型來描述索引存儲方法

該方法在存儲元素信息的同時，還建立附加的索引表索引項的一般形式：（關鍵碼，地址）散列存儲方法根據結點的關鍵碼通過一個函數(shù)計算直接得到該結點的存儲地址02算法的性能度量1.算法的時間復雜度1）是對求解問題算法所消耗執(zhí)行時間的量度。2）取決于下列因素：問題規(guī)模；編程語言；硬件配置；編譯程序；數(shù)據的初始狀態(tài)。3）為突出算法本身，考慮只依賴于問題規(guī)模的n，記作T(n)

4）舉例例7-1計算下列程序段的時間復雜度。intsum=1;/*1次*/for(i=1;i<=n;i++)/*n+1次*/ sum=sum*i;/*n次*/根據各語句的頻度，該程序段的時間復雜度為T(n)=1+