1.數據結構的研究內容
研究數據的特性和數據之間的關系
?用計算機解決一個問題的步驟
1.具體問題抽象成數學模型
實質:
分析問題--->提取操作對象--->找出操作對象之間的關系(數據結構)--->用數學語言描述
操作對象+對象之間的關系
2.設計算法
3.編程,調試,運行
早期計算機主要用于計算數值計算(數據對象關系簡單,但計算復雜)
例:
求解梁架結構的應力(線性方程組)
預報人口增長的情況(微分方程)
當今
計算more often 的用于非數值計算
例1,
學生表
操作對象:每位學生的信息(學號,姓名,性別等)
操作算法:增刪改查
關系:線性關系
數據結構:線性表/線性數據結構
例2:
人機對弈問題
操作對象:各種器具狀態,即描述棋盤的格局信息
算法:走棋,即選擇一種策略使棋局狀態發生變化
關系:非線性關系,樹
數據結構:樹形結構
例3:
地圖最短路徑問題
操作對象:各個地點
算法:方向選擇
關系,非線性關系,圖
數據結構:圖形結構
綜上
以上都是一些非數值計算問題
描述非數值計算問題的數學模型不是數學方程,而是表,樹,圖之類的具有邏輯關系的數據
數據結構是一門研究非數值計算的程序設計中計算機的操作對象以及他們之間的關系和操作的學科額
數據結構的基本概念和基本術語
數據
是能輸入計算機且能被計算機處理的各種符號的集合
(信息的載體
對客觀事物符號化的表示
能夠被計算機識別存儲和加工
)
包括
數值型的數據:整數,實數
非數值型的數據:文字,圖像,聲音等
數據元素:
數據的基本單位,在計算機程序中通常作為一個整體進行考慮和處理
元素/記錄/結點/頂點/(如棋盤的格局)
數據項
構成數據元素的不可分割的最小單位
數據>數據元素>數據項
例
學生表>個人記錄>學號/姓名
數據對象
是性質相同的數據元素的集合,是數據的一個子集.
例如
整數數據對象 集合N={0,(-/+)1,(-/+)2,(-/+)3...}
字母字符數據對象是集合C={A,B,C...Z}
學生表也可以看做一個數據對象
數據元素與數據對象
數據元素是數據的基本單位 是集合的個體
數據對象是性質相同的數據元素的集合 是集合的子集
數據結構
數據元素不是孤立存在的,他們之間存在著某種關系,數據元素相互之間的關系稱之為結構
是指相互之間存在一種或多種特定關系的數據元素集合
也可以說,數據結構是帶結構的數據元素的集合
包括三個內容
1.數據元素之間的邏輯關系,也成為邏輯結構
2.數據元素及其關系在計算機內存中的表示(又稱為映像),稱為數據的物理結構或數據的存儲結構
3.數據的運算和實現,即對數據元素可以施加的操作以及這些操作在相應的存儲結構上的實現
邏輯結構
描述數據元素之間的邏輯關系
與數據的存儲無關,獨立于計算機
是從具體問題抽象出來的數學模型
存儲結構
數據元素及其關系在計算機存儲器中的結構(存儲方式)
是數據結構在計算機中的表示
邏輯結構與數據結構之間的關系
存儲腳骨是邏輯關系的映像與元素元素本身的映像
邏輯結構是數據結構的抽象,存儲結構是數據結構的實現
兩種綜合起來建立了數據元素之間的結構關系
邏輯結構分類
線性結構
有且僅有一個開始和一個終端結點,每個結點只有一個直接前趨和直接后繼
例:線性表,棧,隊列,串
非線性結構
一個節點可能有多個直接前趨和直接后繼
例如:樹,圖
第二種分類
集合機構:?同屬一個集合
線性結構?一對一
樹形結構?一對多
圖狀結構/網狀結構?多對多
存儲結構
順序存儲結構
用一組連續的存儲單元依次存儲數據元素,數據元素之間的邏輯關系由元素的存儲位置來表示
c語言中用數組來實現順序存儲結構
例: int numbers[5] = {1, 2, 3, 4, 5};
鏈式存儲結構
用一組任意的存儲單元存儲數據元素,數據之間的邏輯關系用指針來表示
c語言中用指針來實現鏈式存儲結構
鏈表
索引存儲結構
在存儲結點信息的同時,還建立附加的索引表
散列存儲結構
根據結點的關鍵字直接結算出該結點的存儲地址
數據類型和抽象數據類型
在使用高級程序設計語言編寫程序時,必須對程序中出現的每個變量,常量或表達式,明確說明他們所屬的數據類型
例如:
c語言中,int char,float, double 等基本數據類型
數組,結構,共用體,枚舉等構造數據類型
還有指針,空(void)類型
用戶也可以typedef自己定義數據類型
一些最基本數據結構可以用數據類型來實現,如數組,字符串等
而另一些常用的數據結構,如棧,隊列,樹,圖等,不能直接用數據類型來表示
高級語言中的數據類型明顯地或隱含地規定了在程序執行期間變量和表達的所有可能的取值范圍,以及在這些數值范圍上所允許進行的操作
c語言中定義i 為int類型,就表示i的范圍是整數, 這個整數可以進行+-*\%等操作
數據類型的作用
約束變量或常量的取值范圍
約束變量或常量的操作?
數據類型
定義:數據類型是一組性質相同的值的集合,以及定義于這個值集合上的一組操作的總稱
數據類型=值的集合+值集合上的一組操作
抽象數據類型
是指一個數學模型以及定義在此數學模型上的一組操作
由用戶定義,從問題抽象出數據模型(邏輯結構)
還包括定義在數據模型上的一組抽象運算(相關操作)
不考慮計算機內具體的存儲結構,與運算的具體實現算法
抽象數據類型的形式定義
抽象數據類型可用(D,S,P)三元組表示
其中D是數據對象,S是D上的關系集,P是對D的基本操作
定義格式
ADT 抽象數據類型名{
? ? ? ? 數據對象:<數據對象的定義>
? ? ? ? 數據關系:<數據關系的定義>
? ? ? ? 基本操作:<基本操作的定義>
} ADT 抽象數據類型名
基本操作定義格式
基本操作名(參數表)
初始條件:<初始條件描述>
操作結果:<操作結構描述>
參數表
賦值操作:只為操作提供輸入值.
引用參數 以& 打頭,除可提供輸入值外,還講返回操作結構
scak(&G,n)
初始條件?
描述操作執行之前數據結構和參數應滿足的條件,若不滿足,則操作失敗,并返回相應出錯信息.若初始條件為空,則省略
操作結果
說明操作完成之后,數據結構的變化狀況和應返回的結果
圓 抽象數據類型
ADT?Circle {
? ? ? ? 數據對象:D={r,x,y| r,x,y均為實數}
? ? ? ? 數據關系:R={<r,x,y>|r是半徑,<x,y>是圓心坐標}
? ? ? ? 基本操作:
? ? ? ? Circle(&C,r,x,y)
? ? ? ? ? ? ? ? 操作結果:構造一個圓
? ? ? ? double Area(C)
? ? ? ? ? ? ? ? 初始條件:圓已經存在
? ? ? ? ? ? ? ? 操作結果:計算面積
? ? ? ? double Cirumference(C)
? ? ? ? ? ? ? ? 初始條件:圓已經存在
? ? ? ? ? ? ? ? 操作結構:計算周長
}ADT Circle
ADT?Complex{
? ? ? ? D={r1,r2|r1,r2都是實數}
? ? ? ? S={<r1,r2>|r1是實部,r2是虛部}
? ? ? ? assign(&C,v1,v2)
? ? ? ? ? ? ? ? 初始條件:空的復數C已經存在
? ? ? ? ? ? ? ? 操作結果:構造復數C,r1,r2分別被賦值參數v1,v2的值
? ? ? ? destroy(&C)
? ? ? ? ? ? ? ? 初始條件:復數C已經存在
? ? ? ? ? ? ? ? 操作結果:復數C被銷毀
}ADT complex
小結
數據-(個體)->數據元素?-(性質相同的構成集合)->數據對象-(數據元素之間的關系)->
數據結構->
映像到內存->存儲結構(順序/鏈式/索引/散列)
邏輯模型->邏輯結構(集合/線性/樹形/圖狀)
操作-> 抽象數據類型(數據對象/數據關系/基本操作)
抽象數據類型的實現
抽象數據類型可以通過固有的數據類型來表示和實現
例
c語言實現復數 抽象數據類型
定義結構體,聲明操作函數
#pragma once
typedef struct {float realpart;float imagpart;
}Complex;
void assign(Complex* c, float real, float image);
void add(Complex* c, Complex A, Complex B);
void subtract(Complex* c, Complex A, Complex B);
void multiply(Complex* c, Complex A, Complex B);
void divide(Complex* c, Complex A, Complex B);
void print_complex(Complex A);定義函數
#include "demo2.h"
#include<stdio.h>
void assign(Complex* c, float real, float image) {c->realpart = real;c->imagpart = image;
};
void add(Complex* c, Complex A, Complex B) {c->realpart = A.realpart + B.realpart;c->imagpart = A.imagpart + B.imagpart;
};
void subtract(Complex* c, Complex A, Complex B) {c->imagpart = A.imagpart - B.imagpart;c->realpart = A.realpart - A.realpart;
}
void multiply(Complex* c, Complex A, Complex B) {c->realpart = A.realpart * B.realpart - A.imagpart * B.imagpart;c->imagpart = A.realpart * B.imagpart + A.imagpart * B.realpart;
}
void divide(Complex* c, Complex A, Complex B) {float denominator = B.realpart * B.realpart + B.imagpart * B.imagpart;c->realpart = (A.realpart * B.realpart + A.imagpart * B.imagpart) / denominator;c->imagpart = (A.imagpart * B.realpart - A.realpart * B.imagpart)/ denominator;}
void print_complex(Complex A) {printf("%.2f + %.2fi\n", A.realpart, A.imagpart);}實現復數計算
[(8+6i)(4+3i)]/[(8+6i)+(4+3i)]
#include<stdio.h>
#include "demo2.h"int main() {Complex a1;Complex* a=&a1;assign(a, 8, 6);print_complex(*a);Complex b1;Complex* b=&b1;assign(b, 4, 3);Complex d1;Complex* d=&d1;multiply(d, *a, *b);Complex e1;Complex* e=&e1;add(e, *a, *b);Complex f1;Complex* f=&f1;divide(f, *d, *e);print_complex(*f);}? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??算法和算法分析
算法的定義
對特定問題求解方法和步驟的一種描述,他是指令的有限序列,其中每個指令表述一個或多個操作
簡而言之,算法就是解決問題的方法和步驟
算法的描述
例:求解一元二次方程的根
自然語言:英語,中文
1.輸入方程的系數a,b,c
2.判斷a是否等于0,如果等于,提示不是一元二次方程,反之,執行下一步
3.計算d = b^2 -4ac
4.判斷d 如果d等于0,計算并輸出兩個相等的實根,小于零沒有實根,大于0,輸出兩個實根
5.結束
流程圖:傳統流程圖,NS流程圖
略
偽代碼:類語言:類C語言
程序代碼:C語言程序,java 程序,python
算法與程序
算法是解決問題的一種方法和過程,考慮如何將輸入轉換成輸出,一個問題可以有多種算法.
程序是用某種程序設計語言對算法的具體實現
程序=數據結構+算法
數據結構通過算法實現操作
算法根據數據結構設計程序
算法的特性:
有窮性:一個算法必須總是在執行有窮步之后結束,且在有窮時間內完成
確定性:算法種每一條指令必須有確切的含義,沒有二義性(相同的輸入只能得到相同的輸出)
可行性:算法是可執行的,算法描述的操作可以通過已經實現的基本操作執行有限次來實現
輸入:一個算法有零個或多個輸入
輸出:一個算法有一個或多個輸出
算法設計的要求
正確性
程序對于精心選擇的,典型,苛刻且帶有刁難性的幾組輸入數據能夠得出滿足要求的結果(就認為算法是正確的)
可讀性
易于閱讀和交流,晦澀難懂的算法容易隱藏錯誤,不易調試
健壯性(魯棒性)
當輸入非法數據時,算法恰當的做出反應或進行相應處理,而不是產生莫名奇妙的輸出結果
處理出錯的方法,不應是中斷程序的執行,而應該是返回表示錯誤或錯誤性質的值,以便再更高的抽象層次進行處理
高效性
要求少的時間,少的存儲要求
一個好的算法首先要具備正確性,健壯性,可讀性,在這些方面都滿足的情況下,主要考慮算法的效率,通過算法的效率評判算法的優劣程度
算法效率的兩個方面:
時間效率:算法耗費的時間
空間效率:算法執行過程中耗費的存儲空間
時間效率和空間效率有時候是矛盾的
算法時間效率的度量
算法時間效率可以用依據該算法編制的程序在計算機上執行所消耗的時間來度量
兩種度量方法
事后統計
將算法實現,測算其時間和空間開銷
缺點:編寫程序實現算法將花費較多的時間和精力,所得實驗結構依賴于計算機的軟硬件等環境因素,掩蓋算法本身的優劣
事前分析
對算法所消耗資源的一種估算方法
事前分析方法
算法運行時間=一個簡單操作所需要的時間? *? 簡單操作次數
也即算法中每條語句的執行時間之和
算法運行時間=Σ每一條語句的執行次數(語句頻度) * 該語句執行一次所需要的時間
每條語句執行一次所需的時間一般是由機器決定的和算法無關
可以可以考慮假設執行每條語句所需要的時間均為單位時間,對算法的運行時間就變成討論該算法中所有語句的執行次數,即頻度之和
這就可以獨立于不同機器的軟硬件環境來分析算法的時間性能了
例:
在python中實現兩個N階矩陣相乘
def func(n, a, b):"""兩個n階矩陣相乘,返回計算結果:param n: 矩陣的階數:param a: 矩陣a:param b: 矩陣b:return:"""c = [[0 for _ in range(n)] for _ in range(n)] # 初始化結果矩陣Cfor i in range(n):for j in range(len(b)):for k in range(n):c[i][j] += a[i][k] * b[k][j] # 計算C的元素值return ca = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # 矩陣A
b = [[10, 11, 12], [13, 14, 15], [16, 17, 18]] # 矩陣B
print(func(3, a, b))類C語言
#include <stdio.h>void matrix_multiply(int n, int a[n][n], int b[n][n], int c[n][n]) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {c[i][j] = 0;for (int k = 0; k < n; k++) {c[i][j] += a[i][k] * b[k][j];}}}
}void print_matrix(int n, int matrix[n][n]) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {printf("%d ", matrix[i][j]);}printf("\n");}
}int main() {int n = 3;int a[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};int b[3][3] = {{10, 11, 12}, {13, 14, 15}, {16, 17, 18}};int c[3][3];matrix_multiply(n, a, b, c);print_matrix(n, c);return 0;
}我們把算法所耗費的時間定義為該算法中每條語句的頻度之和,則上述算法的時間消耗T(n)為
T(n)= 2n3 + 3n2 + 2n +1
為了便于比較不同算法的時間效率,我們僅比較他們的數量級
例如兩個不同的算法,時間消耗分別是:
T(n)=10n2? 與Tn(n)= fn3
若有某個輔助函數f(n),使得當n趨于無窮大時,T(n)/f(n)的極限值為不等于零的常數,則稱f(n)是T(n)的同數量級函數記作T(n)=O(f(n))
稱O(f(n))為算法的漸進時間復雜度(O是數量級的符號),簡稱時間復雜度.
對于求解矩陣相乘問題,算法耗費時間:
? ? ? ? T(n)= 2n3 + 3n2 + 2n +1
n趨于無窮大,T(n)/?n3--->2,則T(n)與n3同階/同數量級,記作
????????????????????????????????T(n)=O(n3)
這就是求解矩陣相乘問題的算法的漸進時間復雜度
一般情況下,不必計算所有操作的執行次數,而只考慮算法中基本操作執行次數,它是問題規模n的某個函數,用T(n)表示
算法中基本語句重復執行的次數是問題規模n的某個函數f(n),算法的時間量度記作T(n)=O(f(n))
它表示隨著n的增大,算法執行的時間的增長率和f(n)的增長率相同,稱漸進時間復雜度
基本語句
算法中重復執行次數和算法的執行時間成正比的語句
對算法運行時間的貢獻最大
執行次數最多
問題規模n
n越大算法的執行時間越長
排序:n為記錄數
juzheng:n為矩陣的階數
多項式:n為多項式的項數
集合:n為元素個數
樹,n為樹的結點個數
圖:n為圖的頂點數或邊數
計算定理
分析算法時間復雜度的基本方法
1.找出語句頻度最大的那條語句作為基本語句
2.計算基本語句的頻度得到問題規模n的某個函數f(n)
3.取其數量級用符號O表示
例1
類c
x = 0;
y = 0;
for (int k = 0; k < n; k++)x++;
for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)y++;f(n)= n(n+1)? 第6行代碼執行次數
T(n)=O(n2)
python
x = 0
y = 0
n = int(input("請輸入循環的次數:"))
for k in range(0, n):x += 1
for i in range(0, n):for j in range(0, n):y += 1
print(x, y)T(n)=O(n2)
例2
類c
void exam(float x[][], int m, int n) {float sum[];for (int i = 0; i < m; i++) {sum[i] = 0.0;for (int j = 0; j < n; j++)sum[i] += x[i][j];}for (i = 0; i < m; i++)cout << i << ":" << sum[i] << endl;
}python實現
def exam(x, m, n):sum_l = [0 for i in range(m)]for i in range(m):for j in range(n):sum_l[i] += x[i][j]for i in range(m):print(f"{i}:{sum_l[i]}")x = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
m, n = len(x), len(x[0])
exam(x, m, n)f()= m*n
T(n) = f(m*b)
時間復雜度是由嵌套最深語句的頻度決定的
例3
矩陣相乘
類c
for(i=1;i<=n;i++)for (j = 1; j <= n; j++) {c[i][i] = 0for (k = 1; k <= n; k++)c[i][j] = c[i][j] + a[i][k] * b[k][j];
}python
def func(n, a, b):"""兩個n階矩陣相乘,返回計算結果:param n: 矩陣的階數:param a: 矩陣a:param b: 矩陣b:return:"""c = [[0 for _ in range(n)] for _ in range(n)] # 初始化結果矩陣Cfor i in range(n):for j in range(len(b)):for k in range(n):c[i][j] += a[i][k] * b[k][j] # 計算C的元素值return ca = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # 矩陣A
b = [[10, 11, 12], [13, 14, 15], [16, 17, 18]] # 矩陣B
print(func(3, a, b))算法中的基本操作語句
c[i][j] += a[i][k] * b[k][j] ?# 計算C的元素值
T(n)=O(n3)
例4
類c
for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;python
def func(n): # 定義函數 func，接受一個參數 nglobal x # 聲明全局變量 xfor i in range(len(n)): # 遍歷 n 的第一層for j in range(len(n[i])): # 遍歷 n 的第二層for k in range(len(n[i][j])): # 遍歷 n 的第三層x += 1 # x 加 1n = [[[6, 4, 2], [1, 2]], [[23, 4]]] # 定義一個嵌套列表 n
x = 0 # 初始化 x 為 0
func(n) # 調用函數 func，傳入參數 n
print(x) # 打印 x 的值T(n)=f(n3)
例5
類c
i = 1;
while(i<=n)i=i*2python
def func(n):i = 1num = 0while i <= n:i = i * 2num +=1print(f"基本語句執行次數:{num}")
func(12)做題的關鍵:找出次數x與n的關系
循環一次 i=1*2 =2
循環兩次i=1*2*2 =
循環3次i=1*2*2*2 =?
歸納法可知循x次 i=
有循環條件可知:i<=n,<=n,
當畢業的鐘聲悠然回蕩，青春的樂章輕盈飄揚，愿你的未來如盛開的百花，人生旅程如詩篇般韻味深長。每一陣鐘響都鐫刻著成就，每一段旋律都寄托著夢想，愿你在前行的道路上，繁花滿徑，詩意盎然。
