C# 數(shù)據(jù)結(jié)構(gòu) 基礎(chǔ) 論述

問題：

信息世界中，計(jì)算機(jī)是加工處理的信息的載體，在這個過程中面臨著三個問題：

1.如何方便高效的組織數(shù)據(jù)

2.如何在計(jì)算機(jī)中存儲數(shù)據(jù)（內(nèi)存和外存）

3.如何對存儲的數(shù)據(jù)進(jìn)行高效的操作

目的：

我們都知道，我們都會表述一件事，老板交代你一件事情，你要陳述給你的員工，讓他們明白你的意思,有些人可能簡要的幾句話

就把事情表達(dá)清楚，可是有的人說了一大堆才明白他說什么，這個比喻不太恰當(dāng)，同樣在面對同一個程序的時候我們就可以出現(xiàn)兩

種程序：有的人寫出來的程序效率很高，有的人卻用復(fù)雜的方法來解決一個簡單的問題。

簡而言之目的有三個：

1.形成自己數(shù)據(jù)結(jié)構(gòu)知識庫

2.提高程序設(shè)計(jì)水平

3.提供程序設(shè)計(jì)者的基本技能

基本概念和術(shù)語

1.數(shù)據(jù)（Data）：能被計(jì)算機(jī)識別的信息的載體，數(shù)值數(shù)據(jù)，聲音，文字等等

2.數(shù)據(jù)元素（Data Element）和數(shù)據(jù)項(xiàng)（Data Item）DE：數(shù)據(jù)的實(shí)體 DI：數(shù)據(jù)的屬性 最常見的是數(shù)據(jù)表的一條記錄（用戶） 和

字段（用戶名，密碼，性別等等）

3.數(shù)據(jù)對象（Data Object）性質(zhì)相同的數(shù)據(jù)元素的集合 例如：{0,1,2,3,4} , {a,b,c,d} , {用戶A，用戶B，用戶C….}

4.數(shù)據(jù)類型（Data Type）int,string等等

5.數(shù)據(jù)結(jié)構(gòu)(Data Structure) 在數(shù)據(jù)集合的基礎(chǔ)上組織起來的有關(guān)系數(shù)據(jù)結(jié)構(gòu)，通常有四類節(jié)本數(shù)據(jù)結(jié)構(gòu)：A集合 B線性結(jié)構(gòu) C樹形結(jié)

構(gòu) D 網(wǎng)狀結(jié)構(gòu)或者圖形結(jié)構(gòu)

A Set B Linear Structure C Tree Structure D Graphic Structure

數(shù)據(jù)結(jié)構(gòu)記做 DS（Data Structure） 是一個二元組 DS=（D，R） D是有限的數(shù)據(jù)元素集合 R 是元素之間關(guān)系

通過例子理解后三種數(shù)據(jù)結(jié)構(gòu)：

B 線性數(shù)據(jù)結(jié)構(gòu) 學(xué)生信息表

一行：數(shù)據(jù)元素 列：數(shù)據(jù)項(xiàng) 元素與元素的關(guān)系：1對1

C 樹形結(jié)構(gòu) 家譜

這個不多解釋。節(jié)點(diǎn)：數(shù)據(jù)元素 關(guān)系：一對多 或者 多對一

D 圖形結(jié)構(gòu)

圖形結(jié)構(gòu)：交通圖 元素：城市 關(guān)系多對多

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

包括數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)，物理結(jié)構(gòu)也叫存儲結(jié)構(gòu)，我們討論數(shù)據(jù)結(jié)構(gòu)的目的是為了在計(jì)算機(jī)中實(shí)

現(xiàn)對它的操作，還要在計(jì)算機(jī)表示和存儲，數(shù)據(jù)存儲結(jié)構(gòu)分為：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，順序存儲結(jié)構(gòu)：是把相鄰

數(shù)據(jù)存儲在物理上相同存儲單元中，在C#中用數(shù)組來實(shí)現(xiàn)順序存儲，最常見的是 數(shù)組；鏈?zhǔn)酱鎯Γ琋ode+Reference

Domain 在.net 中內(nèi)存棧區(qū)和堆區(qū)，棧順序存儲，對應(yīng)的對象在堆中，則指向了堆中的地址。

算法

算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系非常密切。

算法的特性：1有窮性 2確定性 3輸出和輸出 4能行性

評定標(biāo)準(zhǔn)：1正確性 2可讀性 3健壯性 4運(yùn)行時間（時間復(fù)雜度Time Complexity） 5占用空間（空間復(fù)雜度Space Complexity）

影響性能因素：1.硬件條件 2.實(shí)現(xiàn)計(jì)算機(jī)的語言（語言越高級 效率越低） 3編程語言的編譯器和解釋器 4 操作系統(tǒng)

算法的時間復(fù)雜度

算法是由控制結(jié)構(gòu)和原操作構(gòu)成的，其執(zhí)行的時間取決于二者的綜合效果。為了便于比較同一問題的不同算法，通常把算法中基本操作

重復(fù)執(zhí)行的次數(shù)（頻度）作為算法的時間復(fù)雜度。T(n)=0(f(n)),如果一個算法沒有循環(huán)語句，那么算法中的節(jié)本操作的執(zhí)行頻率與問題

無關(guān)，記做0（1），也成為常數(shù)階，如果算法只有一重循環(huán)納悶算法執(zhí)行頻率與問題規(guī)模N呈線性增大關(guān)系，記做 0（n），也叫線性階

常用的還有平方階乘0(n*n) 立方階0（n*n*n）等等

例 1：x=n;

y=0;

while(y<x)

{

y=y+1; // T(n) 時間復(fù)雜度

}

這是一個一重循環(huán)，循環(huán)次數(shù)為N 時間復(fù)雜度為線性：記做T(n)=0(0)

例 2：for(i=1;i<n;i++)

{

for(j=0;j<n;j++)

{

A[i][j]=i*j; //T(n) 時間復(fù)雜度

}

}

雙重循環(huán) 外層循環(huán)的循環(huán)次數(shù)是 N 內(nèi)層for循環(huán)次數(shù)為 N 時間復(fù)雜度 T(n)=0(n*n);

例3 ： x=n;

y=0;

while(x>=(y+1)*(y+1))

{

y=y+1; //T(n) 時間復(fù)雜度

}

一重循環(huán) while 的循環(huán)次數(shù)為 根號 N 所以時間復(fù)雜度 T(n)=0(根號N)

例4 ：for(i=0;i<m;i++)

{

for(j=0;j<t;j++)

{

for(k=0;k<n;k++)

{

c[i][j]=c[i][j]+a[i][k]*b[k][j];//T(n) 時間復(fù)雜度 被執(zhí)行次數(shù)

}

}

}

三重循環(huán)：時間復(fù)雜度 T(n)=0(m*t*j);

數(shù)學(xué)基本概念

想到算法就不得不想到數(shù)學(xué)，集合表示法：窮舉法S={0,5,8,9} 描述法：S={x|x是偶數(shù)，且0<X<10};

集合的特點(diǎn)：確定性，互異性，無序性

1000個不同編碼需要多少位？⌈log21000⌉=10 位

10 位可以表示多少個不同的編碼？ 10 位可以產(chǎn)生 1024 個不同的可用編碼

經(jīng)典的例子：折半算法 打個不靠譜的比喻啊 網(wǎng)線壞了 不知道那個地方壞了 網(wǎng)線為100米（最大了）要查多

少次，才能找到故障點(diǎn)，使用折半算法（也叫二分查找法）log2 100 次

指數(shù)和對數(shù)是基本概念也是相互轉(zhuǎn)化的過程。

C# 知識點(diǎn)：接口 Icomparable,IEnumerable,IEnumberator,ICollection,IDictionary,IList

,裝箱拆箱,泛型

未完待續(xù)……