第一章 緒論
- 前言
- 基本概念和術語
- 基本術語
- 資料結構
- 資料運算
- 資料型別
- 演算法和演算法分析
- 定義和特性
- 評價優劣基本標準
- 演算法分析
- 總結
前言
??早期的計算機主要是用于數值計算,現在,計算機主要用于非數值計算,包括處理字符、表格和影像等具有一定結構的資料，這些資料內容存在著某種聯系,只有分清楚資料的內在聯系,合理地組織資料,才能對它們進行有效的處理,設計出高效的演算法，如何合理地組織資料、高效地處理資料,這就是"資料結構"主要研究的問題，接下來和本博主一起走進這演算法與資料結構,一起揭開這神秘的面紗,了解有關資料結構的基本概念和演算法分析!
基本概念和術語
基本術語
資料:
是客觀事物的符號表示是所有能輸入到計算機中被計算機程式處理的符號的總稱
資料元素:
是資料的基本單位,在計算機中通常作為一個整體進行考慮和處理
資料項:
是組成資料元素、有獨立含義的、不可分割的最小單位
資料物件:
是性質相同的資料元素的集合,是資料的一個子集
資料結構
??邏輯結構
??A.線性結構
線性表
一般線性表
線性表
特殊線性表
堆疊與佇列
字串
線性表的推廣
陣列
廣義表
??B.非線性結構
樹結構
樹
二叉樹
圖結構
有向圖
無向圖
集合結構
??存盤結構
??概念:資料物件在計算機中的存盤表示為資料的存盤結構,也稱物理結構
A.順序存盤結構:
??是借助元素在存盤器中的相對位置來表示資料元素之間的邏輯關系,通常借助程式設計語言的陣列型別來描述
B.鏈式存盤結構:
??無需占用一整快存盤空間,需要給每個結點附加指標欄位,用來存放后繼元素的存盤地址
資料運算
插入
洗掉
修改
查找
排序
資料型別
資料型別:
是一個值的集合和定義在這個值集上的一組操作的總稱
抽象資料型別:
一般指由用戶定義的、表示應用問題的數學模型,以及定義在這個模型上的一組操作的總稱
演算法和演算法分析
定義和特性
演算法定義:
一個有窮的指令集，這些指令為解決某一特定任務規定了一個運算序列
!!!五大特性:
a.有窮性
一個演算法必須總是在執行有窮步后結束,且每一步都必須在有窮時間內完成
b.確定性
對于每種情況下所應執行的操作,在演算法中都有確切的規定,不會產生二義性,使演算法的執行者或閱讀者都能明確其含義及如何執行
c.可行性
演算法中的所有操作都可以通過已經實作的基本操作運算執行有限次來實作
d.輸入
一個演算法有零個或多個輸入
e.輸出
有一個或多個輸出(處理結果)
評價優劣基本標準
1.正確性
2.可讀性
3.健壯性
4.高效性
5.時間代價和空間代價
演算法分析
演算法的效率的度量
演算法效率:
含義:用依據該演算法編制的程式在計算機上執行所消耗的時間來度量
衡量演算法效率方法:
1)事后統計
利用計算機內的計時功能，不同演算法的程式可以用一組或多組相同的統計資料區分
2)事前分析估計
一個高級語言程式在計算機上運行所消耗的時間取決于：
1.依據的演算法選用何種策略
2.問題的規模
3.程式語言
4.編譯程式產生機器代碼質量
5.機器執行指令速度
???時間復雜度
????含義:執行演算法消耗的時間
???空間復雜度
???? 含義:執行演算法消耗的空間
總結
??資料結構是一門研究非數值計算程式設計中操作物件,以及這些物件之間的關系和操作的學科，資料結構無外乎關系資料的邏輯結構和存盤結構,然后后面接觸到演算法分析,包括時間復雜度和空間復雜度了解它的特性和評價標準，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/308742.html
標籤：java
下一篇：類的認識及使用