C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘一
這里,我們 來(lái)說(shuō)一說(shuō)C#的數(shù)據(jù)結(jié)構(gòu)了。
①什么是數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu),字面意思就是研究數(shù)據(jù)的方法,就是研究數(shù)據(jù)如何在程序中組織的一種方法。數(shù)據(jù)結(jié)構(gòu)就是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 程序界有一點(diǎn)很經(jīng)典的話,程序設(shè)計(jì)=數(shù)據(jù)結(jié)構(gòu)+算法。用源代碼來(lái)體現(xiàn),數(shù)據(jù)結(jié)構(gòu),就是編程。他有哪些具體的關(guān)系了,
(1) 集合(Set):如圖 1.1(a)所示,該結(jié)構(gòu)中的數(shù)據(jù)元素除了存在“同屬于一個(gè)集合”的關(guān)系外,不存在任何其它關(guān)系。 集合與數(shù)學(xué)的集合類似,有無(wú)序性,唯一性,確定性。
(2) 線性結(jié)構(gòu)(Linear Structure):如圖 1.1(b)所示,該結(jié)構(gòu)中的數(shù)據(jù)元素存在著一對(duì)一的關(guān)系。我們.net程序員做的最多的工作就是對(duì)數(shù)據(jù)庫(kù)的表crud,二表的最小的數(shù)據(jù)單元是行。每行數(shù)據(jù)是最明顯的線性結(jié)構(gòu)。
(3) 樹形結(jié)構(gòu)(Tree Structure):如圖 1.1(c)所示,該結(jié)構(gòu)中的數(shù)據(jù)元素存在著一對(duì)多的關(guān)系。現(xiàn)實(shí)中,家族關(guān)系中是最明顯的樹形結(jié)構(gòu)。如圖所示
而對(duì)于我們.net程序員來(lái)說(shuō),操作的樹形控件是也是最明顯的樹形結(jié)構(gòu)
(4) 圖狀結(jié)構(gòu)(Graphic Structure):如圖 1.1(d)所示,該結(jié)構(gòu)中的數(shù)據(jù)元素存在著多對(duì)多的關(guān)系。在現(xiàn)實(shí)中,圖應(yīng)用的太多了,如圖所示:
對(duì)于我們。net程序員應(yīng)用的較少,當(dāng)你用C++作一些底層應(yīng)用,如搜索引擎,地圖導(dǎo)航應(yīng)用的蠻多的。
以上是針對(duì)數(shù)據(jù)結(jié)構(gòu)的介紹。
做過(guò)開發(fā)的人員都知道這個(gè)道理,算法與數(shù)據(jù)結(jié)構(gòu)和程序的關(guān)系非常密切。 進(jìn)行程序設(shè)計(jì)時(shí),先確定相應(yīng)的數(shù)據(jù)結(jié)構(gòu),然后再根據(jù)數(shù)據(jù)結(jié)構(gòu)和問題的需要設(shè)計(jì)相應(yīng)的算法。
②那什么是算法了?算法,就是計(jì)算的方法了,就是解決問題的方案,就是對(duì)某一特定類型的問題的求解步驟的一種描述, 是指令的有限序列。 用源代碼體現(xiàn),算法就是編程的體現(xiàn)。一個(gè)算法應(yīng)該具備以下 5個(gè)特性:
1、有窮性(Finity):一個(gè)算法總是在執(zhí)行有窮步之后結(jié)束,即算法的執(zhí)行時(shí)間是有限的。我們初學(xué).net時(shí)候,經(jīng)常寫著死循環(huán),這不是算法,因?yàn)檫@是無(wú)窮的。
2、確定性(Unambiguousness):算法的每一個(gè)步驟都必須有確切的含義,即無(wú)二義,并且對(duì)于相同的輸入只能有相同的輸出。對(duì)于我們.net程序員寫出二義性的源代碼,編譯器根本讓你通不過(guò)。
3、輸入(Input):一個(gè)算法具有零個(gè)或多個(gè)輸入。它即是在算法開始之前給出的數(shù)據(jù)結(jié)構(gòu)這些輸入是某數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)對(duì)象。編程是解決問題的,如果不能輸入的話,怎么解決問題了。
4、 輸出(Output):一個(gè)算法具有一個(gè)或多個(gè)輸出,并且這些輸出與輸入之間存在著某種特定的關(guān)系。 編程就是解決了生活中問題,你不讓用戶看到最后的結(jié)果,這就失去了編程的意義。
5、 能行性(realizability):算法中的每一步都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算的有限次運(yùn)行來(lái)實(shí)現(xiàn)。這與有窮性息息相關(guān)。
那算法的評(píng)價(jià)標(biāo)準(zhǔn)又是什么了?
評(píng)價(jià)一個(gè)算法優(yōu)劣的主要標(biāo)準(zhǔn)如下:1、 正確性(Correctness)。2、可讀性(Readability)3、健壯性(Robustness)。4、運(yùn)行時(shí)間(Running Time)。5、占用空間(Storage Space)。
前3個(gè)性質(zhì),我們很好拿捏。與我們程序員息息相關(guān)的是運(yùn)行時(shí)間與占用空間。然而,隨著硬件越來(lái)越便宜,面對(duì)占用空間,我們無(wú)非增加硬件。面對(duì)海量數(shù)據(jù),我們尤為關(guān)心是運(yùn)行時(shí)間(Running Time)。這此時(shí)的計(jì)算機(jī)的運(yùn)行時(shí)間由以下因素決定:
1、硬件條件。包括所使用的處理器的類型和速度(比如,使用雙核處理器還是單核處理器) 、可使用的內(nèi)存(緩存和 RAM)以及可使用的外存等。
2、實(shí)現(xiàn)算法所使用的計(jì)算機(jī)語(yǔ)言。實(shí)現(xiàn)算法的語(yǔ)言級(jí)別越高,其執(zhí)行效率相對(duì)越低。
3、所使用的語(yǔ)言的編譯器/解釋器。一般而言,編譯的執(zhí)行效率高于解釋,但解釋具有更大的靈活性。
4、所使用的操作系統(tǒng)軟件。操作系統(tǒng)的功能主要是管理計(jì)算機(jī)系統(tǒng)的軟件和硬件資源,為計(jì)算機(jī)用戶方便使用計(jì)算機(jī)提供一個(gè)接口。各種語(yǔ)言處理程序如編譯程序、解釋程序等和應(yīng)用程序都在操作系統(tǒng)的控制下運(yùn)行。
評(píng)價(jià)運(yùn)行時(shí)間就是一個(gè)算法時(shí)間復(fù)雜度, 一個(gè)算法的時(shí)間復(fù)雜度(Time Complexity)是指該算法的運(yùn)行時(shí)間與問題規(guī)模的對(duì)應(yīng)關(guān)系。
算法中的基本操作一般是指算法中最深層循環(huán)內(nèi)的語(yǔ)句,因此,算法中基本操作語(yǔ)句的頻度是問題規(guī)模n的某個(gè)函數(shù)f(n),記作:T(n)=O(f(n))。其中“O”表示隨問題規(guī)模n的增大,算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同,或者說(shuō),用“O”符號(hào)表示數(shù)量級(jí)的概念。 這些 都只是一些理論的概念,我們這里用計(jì)時(shí)器來(lái)證明這個(gè)理論概念。
如:
①x=n; /*n>1*/
y=0;
while(y < x)
{
y=y+1; ①
}
從理論上分析這是一重循環(huán)的程序,while 循環(huán)的循環(huán)次數(shù)為 n,所以,該程序段中語(yǔ)句①的頻度是 n,則程序段的時(shí)間復(fù)雜度是 T(n)=O(n) 。
從程序上驗(yàn)證,當(dāng)n=10時(shí),運(yùn)行結(jié)果如圖所示:
當(dāng)n=100000時(shí),運(yùn)行結(jié)果如圖所示
由此證明,其中算法的時(shí)間復(fù)雜度確實(shí)是接近于O(n)
②
for(i=1;i<n;++i) {
for(j=0;j<n;++j)
{
A[i][j]=i*j; ①
}
}
理論上解釋為這是二重循環(huán)的程序,外層for循環(huán)的循環(huán)次數(shù)是n,內(nèi)層for循環(huán)的循環(huán)次數(shù)為n,所以,該程序段中語(yǔ)句①的頻度為n*n,則程序段的時(shí)間復(fù)雜度
為T(n)=O(n²) 。
從程序上證明,當(dāng)n=10,其運(yùn)行效果如圖所示:
當(dāng)n=100000,其運(yùn)行效果如圖所示:
由此證明,其中算法的時(shí)間復(fù)雜度確實(shí)是接近于O(n²)
③x=n; /*n>1*/
y=0;
while(x >= (y+1)*(y+1))
{
y=y+1; ①
}
這是一重循環(huán)的程序,while 循環(huán)的循環(huán)次數(shù)為 n,所以,該程序段中語(yǔ)句①的頻度是 n,則程序段的時(shí)間復(fù)雜度是 T(n)=O(√n) 。
從程序證明:當(dāng)n=10時(shí),運(yùn)行效果如圖所示:
當(dāng)n=100000時(shí),運(yùn)行效果如圖所示:
由此證明,其中算法的時(shí)間復(fù)雜度確實(shí)是接近于O(√n)
本文一介紹了數(shù)據(jù)結(jié)構(gòu)的基本概念 而介紹了算法的基本概念,并且重點(diǎn)討論了算法時(shí)間復(fù)雜度,并且用程序予以證明。
- C#數(shù)據(jù)結(jié)構(gòu)之順序表(SeqList)實(shí)例詳解
- c#泛型學(xué)習(xí)詳解 創(chuàng)建線性鏈表
- C#常用數(shù)據(jù)結(jié)構(gòu)和算法總結(jié)
- C#模擬鏈表數(shù)據(jù)結(jié)構(gòu)的實(shí)例解析
- C#數(shù)據(jù)結(jié)構(gòu)之雙向鏈表(DbLinkList)實(shí)例詳解
- C#數(shù)據(jù)結(jié)構(gòu)之單鏈表(LinkList)實(shí)例詳解
- C#數(shù)據(jù)結(jié)構(gòu)之循環(huán)鏈表的實(shí)例代碼
- C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘五 棧和隊(duì)列
- C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘四 雙向鏈表
- C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘三 鏈表
- C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘二 線性結(jié)構(gòu)
- C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘二
- C#實(shí)現(xiàn)順序表(線性表)完整實(shí)例
相關(guān)文章
C#實(shí)現(xiàn)讓窗體獲得焦點(diǎn)的方法示例
這篇文章主要介紹了C#實(shí)現(xiàn)讓窗體獲得焦點(diǎn)的方法,涉及C#窗體事件相關(guān)操作技巧,需要的朋友可以參考下2017-06-06C#實(shí)現(xiàn)在listview中插入圖片實(shí)例代碼
這篇文章主要介紹了C#實(shí)現(xiàn)在listview中插入圖片實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-03-03c#使用微信接口開發(fā)微信門戶應(yīng)用中微信消息的處理和應(yīng)答
這篇文章主要介紹了c#使用微信接口開發(fā)微信門戶中的微信消息的處理和應(yīng)答的過(guò)程,需要的朋友可以參考下2014-03-03C#中委托的基礎(chǔ)入門與實(shí)現(xiàn)方法
這篇文章主要給大家介紹了關(guān)于C#中委托的基礎(chǔ)入門與實(shí)現(xiàn)方法的相關(guān)資料,究竟什么是委托,用最通俗易懂的話來(lái)講,你就可以把委托看成是用來(lái)執(zhí)行方法(函數(shù))的一個(gè)東西,需要的朋友可以參考下2021-08-08C#中面向?qū)ο缶幊虣C(jī)制之繼承學(xué)習(xí)筆記
這篇文章主要介紹了C#中面向?qū)ο缶幊虣C(jī)制之繼承學(xué)習(xí)筆記,本文給出一個(gè)簡(jiǎn)單子實(shí)例講解C#中的繼承,并講解了一些C#繼承的知識(shí)技巧,需要的朋友可以參考下2015-01-01