目錄

數(shù)據(jù)結(jié)構(gòu)的幾個(gè)方面

邏輯結(jié)構(gòu)的描述

邏輯結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)運(yùn)算

數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型

數(shù)據(jù)類型

抽象數(shù)據(jù)類型(ADT)

算法及其描述

什么是算法

算法分析

算法的設(shè)計(jì)目標(biāo)

算法時(shí)間性能分析

計(jì)算算法頻度

算法時(shí)間復(fù)雜度

簡化的算法時(shí)間復(fù)雜度分析

數(shù)據(jù)結(jié)構(gòu)學(xué)科定義：數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科。

數(shù)據(jù)：描述客觀事物的數(shù)值、字符以及所有能被機(jī)器處理的各種符號(hào)集合

數(shù)據(jù)元素：數(shù)據(jù)的基本單位（例如一個(gè)班級(jí)中的每個(gè)學(xué)生記錄為一個(gè)數(shù)據(jù)元素），數(shù)據(jù)元素是組成數(shù)據(jù)的有一定意義的基本單位。數(shù)據(jù)元素通常由若干個(gè)數(shù)據(jù)項(xiàng)組成（學(xué)生記錄的姓名、性別等都是數(shù)據(jù)項(xiàng)）

數(shù)據(jù)項(xiàng)：數(shù)據(jù)的最小單位，也稱域

數(shù)據(jù)對(duì)象：描述相同性質(zhì)數(shù)據(jù)元素的集合，數(shù)據(jù)的子集

數(shù)據(jù)結(jié)構(gòu)：存在某種特定關(guān)系的數(shù)據(jù)元素的集合

數(shù)據(jù)結(jié)構(gòu) = 數(shù)據(jù)對(duì)象+結(jié)構(gòu)（數(shù)據(jù)元素間的關(guān)系構(gòu)成結(jié)構(gòu)）

• 默認(rèn)情況下數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)都指的是數(shù)據(jù)對(duì)象

數(shù)據(jù)結(jié)構(gòu)的幾個(gè)方面

邏輯結(jié)構(gòu) --------- 邏輯層面（數(shù)據(jù)元素之間的邏輯關(guān)系）--獨(dú)立于計(jì)算機(jī)

物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)） --------- 數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)中的存儲(chǔ)方式

數(shù)據(jù)運(yùn)算 --------- 施加在數(shù)據(jù)上的操作

邏輯結(jié)構(gòu)的描述

• 二元組

  數(shù)據(jù)結(jié)構(gòu)={D,R}

  D：數(shù)據(jù)元素的集合

  R: D中數(shù)據(jù)元素之間的關(guān)系，關(guān)系是使用序偶來表示的。

  序偶是由兩個(gè)元素x和y按一定順序排列而成的二元組，記<x,y>。x是它的第一元素，y是它的第二元素。

  x為y的前驅(qū)元素

  y為x的后繼元素

  若某個(gè)元素沒有前驅(qū)元素（稱為開始元素）

  若某個(gè)元素沒有后驅(qū)元素（稱為終端元素）

  • 對(duì)稱序偶

    若<x，y>∈r（r∈R），則<y，x>∈r（x，y∈D），可用圓括號(hào)代替尖括號(hào)，即(x，y)∈r。

• 圖形

  圖形中的點(diǎn)表示數(shù)據(jù)元素，圖形中的弧表示數(shù)據(jù)元素之間的關(guān)系

  如果數(shù)據(jù)元素x和y之間的關(guān)系為<x,y>，則圖形中有從x的點(diǎn)出發(fā)到y(tǒng)的點(diǎn)的一條弧

邏輯結(jié)構(gòu)

按照數(shù)據(jù)元素之間相互關(guān)系的特性來分，可以分為

• 集合
• 線性結(jié)構(gòu)（線性表、棧、隊(duì)列）:若結(jié)構(gòu)非空，則有且僅有一個(gè)開始元素和終端元素，并且所有元素最多只有一個(gè)前驅(qū)元素和一個(gè)后繼元素。
• 樹形結(jié)構(gòu)：若結(jié)構(gòu)是非空的，則有且僅有一個(gè)元素為開始元素（也稱為根結(jié)點(diǎn)），可以有多個(gè)終端元素，每個(gè)元素有零個(gè)或多個(gè)后繼元素，除開始元素外每個(gè)元素有且僅有一個(gè)前驅(qū)元素。
• 圖狀結(jié)構(gòu)：若結(jié)構(gòu)是非空的，則每個(gè)元素可以有多個(gè)前驅(qū)元素和多個(gè)后繼元素。

存儲(chǔ)結(jié)構(gòu)

計(jì)算機(jī)中存儲(chǔ)器存儲(chǔ)數(shù)據(jù)的方式

邏輯結(jié)構(gòu) —映射—>存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu):

• 所有元素存放在一片地址連續(xù)的存儲(chǔ)單元中
• 邏輯上相鄰的元素在物理位置上也是相鄰的，所以不需要額外空間表示元素之間的邏輯關(guān)系。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：

• 數(shù)據(jù)元素存放在任意的存儲(chǔ)單元中，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的
• 通過指針域來反映數(shù)據(jù)元素的邏輯關(guān)系

數(shù)據(jù)運(yùn)算

• 將數(shù)據(jù)存放在計(jì)算機(jī)中的目的是為了實(shí)現(xiàn)一種或多種運(yùn)算。
• 運(yùn)算包括功能描述（或運(yùn)算功能）和功能實(shí)現(xiàn)（或運(yùn)算實(shí)現(xiàn)）
• 前者是基于邏輯結(jié)構(gòu)的，是用戶定義的，是抽象的
• 后者是基于存儲(chǔ)結(jié)構(gòu)的，是程序員用計(jì)算機(jī)語言或偽碼表示的，是詳細(xì)的過程，其核心是設(shè)計(jì)實(shí)現(xiàn)某一運(yùn)算功能的處理步驟，即算法設(shè)計(jì)。

注： 同一邏輯結(jié)構(gòu)可以對(duì)應(yīng)多種存儲(chǔ)結(jié)構(gòu)。 同樣的運(yùn)算，在不同的存儲(chǔ)結(jié)構(gòu)中，其實(shí)現(xiàn)過程是不同的。?

數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型

數(shù)據(jù)類型

數(shù)據(jù)類型是一組性質(zhì)相同的值的集合和定義在此集合上的一組操作的總稱。

• 數(shù)據(jù)結(jié)構(gòu)是指計(jì)算機(jī)處理的數(shù)據(jù)元素的組織形式和相互關(guān)系，而數(shù)據(jù)類型是某種程序設(shè)計(jì)語言中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。
• 在程序設(shè)計(jì)語言提供的數(shù)據(jù)類型支持下，就可以根據(jù)從問題中抽象出來的各種數(shù)據(jù)模型，逐步構(gòu)造出描述這些數(shù)據(jù)模型的各種新的數(shù)據(jù)結(jié)構(gòu)。

抽象數(shù)據(jù)類型(ADT)

??抽象數(shù)據(jù)類型（ADT）指的是從求解問題的數(shù)學(xué)模型中抽象出來的數(shù)據(jù)邏輯結(jié)構(gòu)和運(yùn)算（抽象運(yùn)算），而不考慮計(jì)算機(jī)的具體實(shí)現(xiàn)。

抽象數(shù)據(jù)類型 = 邏輯結(jié)構(gòu)+抽象運(yùn)算

表示： 三元組 ADT = (D,S,P) D: 數(shù)據(jù)對(duì)象 S: D上的關(guān)系集 P: 加在D上的一組操作 定義抽象數(shù)據(jù)類型時(shí)，可以使用以下形式： ADT 抽象數(shù)據(jù)類型名{ 數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系： 基本操作： }?

算法及其描述

什么是算法

算法：對(duì)特定問題求解步驟的一種描述，它是指令的有限序列

算法的五個(gè)重要特性

• 有窮性 --- 算法執(zhí)行有限步驟后自動(dòng)結(jié)束，每步在可接受的時(shí)間內(nèi)完成
• 確定性 --- 對(duì)于每種情況下執(zhí)行的操作，在算法中都有確定的含義，不會(huì)出現(xiàn)二義性。并且在任何條件下，算法都只有一條執(zhí)行路徑。
• 可行性 --- 每條指令都是可執(zhí)行的
• 輸入性 --- 零個(gè)或多個(gè)輸入
• 輸出性 --- 一個(gè)或多個(gè)輸出

算法分析

算法的設(shè)計(jì)目標(biāo)

• 正確性

• 可使用性

• 可讀性

• 健壯性

• 高時(shí)間性能與低存儲(chǔ)量需求

算法時(shí)間性能分析

算法由控制結(jié)構(gòu)（順序、分支、循環(huán)）和原操作（基本類型的操作+，-，*，/等）構(gòu)成

• 算法執(zhí)行時(shí)間取決于兩者綜合
• 在一個(gè)算法中，執(zhí)行原操作的次數(shù)越少，其執(zhí)行時(shí)間也就相對(duì)地越少；執(zhí)行原操作次數(shù)越多，其執(zhí)行時(shí)間也就相對(duì)地越多。
• 算法中所有原操作的執(zhí)行次數(shù)稱為算法頻度，這樣一個(gè)算法的執(zhí)行時(shí)間可以由算法頻度來計(jì)量。

計(jì)算算法頻度

• 假設(shè)算法的問題規(guī)模為n，例如對(duì)10個(gè)整數(shù)排序，問題規(guī)模為n就是10。算法頻度是問題規(guī)模n的函數(shù)，用T(n)表示。
• 算法執(zhí)行時(shí)間大致等于原操作所需的時(shí)間×T(n)，也就是說T(n)與算法的執(zhí)行時(shí)間成正比。為此用T(n)表示算法的執(zhí)行時(shí)間。比較不同算法的T(n)大小得出算法執(zhí)行時(shí)間的好壞。

例：

// 兩個(gè)n階方陣相加，求T(n)
void matrixadd(int[][] A,int[][] B,int[][] C,int n)
{  for (int i=0;i<n;i++)		//語句①  n+1
      for (int j=0;j<n;j++)		//語句②  n(n+1)
	  C[i][j]=A[i][j]+B[i][j];	//語句③  n^2
}

T（n）= n+1+n(n+1)+n2?= 2n2+2n+1 = O(n2)

算法時(shí)間復(fù)雜度

算法中執(zhí)行時(shí)間T(n)是問題規(guī)模n的某個(gè)函數(shù)f(n),記作：T(n)=O(f(n))

也就是只求出T(n)的最高階，忽略其低階項(xiàng)和常系數(shù)，這樣既可簡化T(n)的計(jì)算，又能比較客觀地反映出當(dāng)n很大時(shí)算法的時(shí)間性能。

一般的

• 一個(gè)沒有循環(huán)的算法的執(zhí)行時(shí)間與問題規(guī)模n無關(guān)，記作O(1)，也稱作常數(shù)階。
• 一個(gè)只有一重循環(huán)的算法的執(zhí)行時(shí)間與問題規(guī)模n的增長呈線性增大關(guān)系，記作O(n)，也稱線性階。
• 其余常用的算法時(shí)間復(fù)雜度還有平方階O(n^2)、立方階O(n^3)、對(duì)數(shù)階O(log2n)、指數(shù)階O(2^n)等。

各種不同算法時(shí)間復(fù)雜度的比較關(guān)系如下:

?時(shí)間復(fù)雜度是總運(yùn)算次數(shù)表達(dá)式中受n的變化影響最大的那一項(xiàng)(不含系數(shù))
a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f
a ！ =0時(shí)，時(shí)間復(fù)雜度就是O(2^n);
a=0,b<>0 =>O(n^3);
a,b=0,c<>0 =>O(n^2)依此類推

eg:
(1)???for(i=1;i<=n;i++)?????????//循環(huán)了n*n次，是O(n^2)
????????????for(j=1;j<=n;j++)
?????????????????s++;
(2)???for(i=1;i<=n;i++)?????????//循環(huán)了(n+n-1+n-2+...+1)≈(n^2)/2 是O(n^2)
????????????for(j=i;j<=n;j++)
?????????????????s++;
(3)???for(i=1;i<=n;i++)?????????//循環(huán)了(1+2+3+...+n)≈(n^2)/2, 是O(n^2)
????????????for(j=1;j<=i;j++)
?????????????????s++;
(4)??
i=1;k=0;?????
while(i<=n-1)
{??????????
k+=10*i;
i++;
}
//循環(huán)了
n-1≈n次，所以是O(n)
(5)
for(i=1;i<=n;i++)
????for(j=1;j<=i;j++)
????????for(k=1;k<=j;k++)
????????????x=x+1;
循環(huán)了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6≈(n^3)/3，是O(n^3)

簡化的算法時(shí)間復(fù)雜度分析

• 僅僅考慮算法中的基本操作

• 基本操作:算法中最深層循環(huán)內(nèi)的原操作

  • 算法的執(zhí)行時(shí)間大致等于基本操作所需時(shí)間X其運(yùn)算次數(shù)

    算法分析時(shí)，計(jì)算T(n)僅僅考慮基本操作的執(zhí)行次數(shù)文章來源地址http://www.zghlxwxcb.cn/news/detail-771843.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)（1）學(xué)科定義、組成、算法的定義、時(shí)間復(fù)雜度比較的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！