新曉本已悅人心，故知更加理解深！
目錄
前言：
●本篇博文基于《資料結構》(C語言版）嚴蔚敏教授、吳偉民教授、李冬梅教授編著的教材知識及框架主線，以及參考借閱其他相關資料，結合作者的學習所記錄的筆記分享，
●由于作者水平有限，文章難免存在謬誤之處，敬請讀者斧正，俚語成篇，懇望指教
程式=演算法+資料結構
1.什么是資料結構？
2.為什么要學資料結構？
3. 資料結構的研究內容、應用及方向：
4.基本概念和術語 ：
5. 資料結構的兩個層次：
6.資料型別:
7.演算法和演算法分析：
8.時間復雜度和空間復雜度：
后記：
寫在最后的話：
——By 作者：新曉·故知
2022.01.05
前言：
●本篇博文基于《資料結構》(C語言版）嚴蔚敏教授、吳偉民教授、李冬梅教授編著的教材知識及框架主線，以及參考借閱其他相關資料，結合作者的學習所記錄的筆記分享，
●由于作者水平有限，文章難免存在謬誤之處，敬請讀者斧正，俚語成篇，懇望指教
讓我們先從一個著名的公式開始：
程式=演算法+資料結構
這個公式由圖靈獎獲得者尼古拉斯·沃斯（Niklaus Wirth）（瑞士計算機科學家）所提出，
1.什么是資料結構？
資料結構（Data Structure）是相互之間存在一種或多種特定關系的資料元素的集合，
◆解釋：資料結構是帶“結構”的資料元素的集合，“結構”就是指資料元素之間存在的關系，
2.為什么要學資料結構？
★編程基礎
★計算機及相關專業考研考博課程
★計算機等級考試課程
★程式員考試課程
3. 資料結構的研究內容、應用及方向：
資料結構的研究內容為： 研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關系和操作，
4.基本概念和術語 ：
?資料（data)—所有能輸入到計算機中去的描述客觀事物的符號
◆ 數值性資料
◆非數值性資料（多媒體資訊處理）
?資料元素（data element）—資料的基本單位，也稱結點（node）或記錄（record）
?資料項（data item）—有獨立含義的資料最小單位，也稱域(field)
三者之間的關系：資料 > 資料元素 > 資料項
例：學生表 > 個人記錄 > 學號、姓名……
?資料物件(Data Object)：相同特性資料元素的集合，是資料的一個子集
5. 資料結構的兩個層次：
◆邏輯結構--- 資料元素間抽象化的相互關系，與資料的存盤無關，獨立于計算機，它是從具體問題抽象出來的數學模型，
◆存盤結構（物理結構）---- 資料元素及其關系在計算機存盤器中的存盤方式，
★邏輯結構★
▲劃分方法一
（1）線性結構---- 有且僅有一個開始和一個終端結點，并且所有結點都最多只有一個直接前趨和一個后繼， 例如：線性表、堆疊、佇列、串
（2）非線性結構---- 一個結點可能有多個直接前趨和直接后繼， 例如：樹、圖
▲劃分方法二
集合——資料元素間除“同屬于一個集合”外，無其它關系
線性結構——一個對一個，如線性表、堆疊、佇列
樹形結構——一個對多個，如樹
圖形結構——多個對多個，如圖
★存盤結構★：
◆順序存盤結構——借助元素在存盤器中的相對位置來表示資料元素間的邏輯關系
◆鏈式存盤結構——借助指示元素存盤地址的指標表示資料元素間的邏輯關系
6.資料型別:
6.1定義：在一種程式設計語言中，變數所具有的資料種類
?FORTRAN語言：整型、實型、和復數型
?C語言：
?基本資料型別： char int float double void
?構造資料型別：陣列、結構體、共用體、檔案
資料型別是一組性質相同的值的集合, 以及定義于這個集合上的一組運算的總稱
6.2抽象資料型別 (ADTs: Abstract Data Types)
?更高層次的資料抽象
?由用戶定義，用以表示應用問題的資料模型
?由基本的資料型別組成, 并包括一組相關的操作
6.3抽象資料型別的表示與實作
抽象資料型別可以通過固有的資料型別（如整型、實型、字符型等）來表示和實作，它有些類似C語言中的結構（struct)型別，但增加了相關的操作 教材中用的是類C語言（介于偽碼和C語言之間）作為描述工具
(1) 預定義常量及型別
★函式結果狀態代碼
#define OK 1
#define ERROR 0
#define OVERFLOW -2★Status是函式回傳值型別，其值是函式結果狀態代碼，
typedef int Status;(2)資料元素被約定為ElemType 型別，用戶需要根據具體情況，自行定義該資料型別，
(3)演算法描述為以下的函式形式：
函式型別 函式名（函式引數表）
{
陳述句序列；
}
（4）記憶體的動態分配與釋放
（5）賦值陳述句 （6）選擇陳述句 （7）回圈陳述句
（8）使用的結束陳述句形式有：
函式結束陳述句 return
回圈結束陳述句 break;
例外結束陳述句 exit（例外代碼）；
（9）輸入輸出陳述句形式有： 輸入陳述句
（10）擴展函式有： 求最大值 max 求最小值 min
7.演算法和演算法分析：
7.1演算法定義：一個有窮的指令集，這些指令為解決某一特定任務規定了一個運算序列
7.2演算法的描述：
?自然語言
?流程圖
?程式設計語言
?偽代碼
7.3演算法的特性：
◆輸入 有0個或多個輸入
◆輸出 有一個或多個輸出(處理結果)
◆確定性 每步定義都是確切、無歧義的
◆有窮性 演算法應在執行有窮步后結束
◆有效性 每一條運算應足夠基本
7.3演算法的評價
?正確性
?可讀性
?健壯性
?高效性（時間代價和空間代價）
7.4演算法的效率的度量
?演算法效率：用依據該演算法編制的程式在計算機上執行所消耗的時間來度量
★事后統計
★事前分析估計
?事后統計：利用計算機內的計時功能，不同演算法的程式可以用一組或多組相同的統計資料區分
缺點：
?必須先運行依據演算法編制的程式
?所得時間統計量依賴于硬體、軟體等環境因素，掩蓋演算法本身的優劣
?事前分析估計： 一個高級語言程式在計算機上運行所消耗的時間取決于：
?依據的演算法選用何種策略
?問題的規模
?程式語言
?編譯程式產生機器代碼質量
?機器執行指令速度
同一個演算法用不同的語言、不同的編譯程式、在不同的計算機上運行，效率均不同，———使用絕對時間單位衡量演算法效率不合適
8.時間復雜度和空間復雜度：
8.1時間復雜度：
題例1：
n * n階矩陣加法： for( i = 0; i < n; i++) for( j = 0; j < n; j++) c[i][j] = a[i][j] + b[i][j];題例2：
題例3：
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; }題例4：
N×N矩陣相乘 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; }題例5：
for( i=1; i<=n; i++) for (j=1; j<=i; j++) for (k=1; k<=j; k++) x=x+1;
題例6：
有的情況下，演算法中基本操作重復執行的次數還隨問題的輸入資料集不同而不同
題例7：
8.2空間復雜度:
空間復雜度:演算法所需存盤空間的度量，記作: S(n)=O(f(n)) 其中n為問題的規模(或大小)
演算法要占據的空間
?演算法本身要占據的空間，輸入/輸出，指令，常數，變數等
?演算法要使用的輔助空間
演算法1：S(n) = O(1) 原地作業
演算法2：S(n) = O(n)
后記：
本篇博文是作者對《資料結構》（C語言版）的第一篇學習記錄，并未涉及演算法代碼實作，演算法代碼的實作在《資料結構》學習筆記專欄的后續筆記，
寫在最后的話：
非常榮幸每一位讀者能夠閱讀到此處！你好！來自現在以及未來的朋友！
今天期末考試結束了，這學年真的很難忘，很多地方需要總結， 就到這里吧，收拾行李回家了！
——By 作者：新曉·故知
2022.01.05
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/404138.html
標籤：其他
上一篇：Git分布式版本控制工具