數(shù)據(jù)結(jié)構(gòu)講義01col dsintro計(jì)算機(jī)系數(shù)據(jù)庫與信息系統(tǒng)

學(xué)會(huì)合理地組織數(shù)據(jù),有效地表示數(shù)據(jù),有效地處理數(shù)據(jù) 譯,《數(shù)據(jù)結(jié)構(gòu)與算法 1.11.21.31.41.51.1 數(shù)學(xué),硬件,軟件之 結(jié)構(gòu)批數(shù)據(jù),按一定的 計(jì)算機(jī)中,并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)(1B=(K RK上的有窮關(guān)系的集合一般Rr}表–例如rki-1ki>|Ki∈K1in(2)常見邏輯關(guān)系有:線性(線性表，棧，隊(duì)列，向量，字符串， =(K,R)，其–K＝｛k0,k1,…,kn-–R={r}，r={<ki-1,ki>|Ki∈K,1<i<n??…了）B={K,R}R={r}r滿足下列條件：有且僅有一個(gè)稱為根了）圖：B={K,R},R={r},K中結(jié)點(diǎn)相對(duì)于r前驅(qū)和后繼個(gè)數(shù)左圖邏輯 =(K,R)，其R={r}，r={<A, <A,E>,<E,A>, <C,F>,<F,C>,<D,FR={r}，r={(A,C),(A,E),(B,C),(B,F),(C,D),(C,F),(D,F),(E,F)}

∧…∧ 密度(≤1)=數(shù)據(jù)本身 鏈表：rn·E/n(P+E)E 437321533Pointerlistof 據(jù)結(jié)構(gòu)不同.例如,棧與隊(duì)列數(shù)據(jù)抽象與過程抽象實(shí)現(xiàn)信息隱蔽和局部化以一個(gè)嚴(yán)格定義的過程接口的方式數(shù)抽象數(shù)據(jù)類型,定義了一組運(yùn)算的數(shù)學(xué)模型.與物理 結(jié)構(gòu)無關(guān),使軟件系統(tǒng)建立在數(shù)據(jù)之上(面向?qū)ο?邏輯定義：線性表list是由叫做元素 =(K,R)，其 R={r}，r={<ki-1,ki>|Ki∈K,1<i<nclasslist{ //ListclassADTlist(constint voidinsert(constELEM&);voidappend(constELEM&);ELEMremove();voidvoidnext(); voidprev();intlength()const;voidsetPos(constvoidsetValue(constELEM&);ELEMcurrValue()const;boolisEmpty()const;boolisInList()boolfind(const (1(2(3遞歸法分治法(二分法檢索(4回溯法(八皇后(8)typedefstructelem{intkey;datatype}#defineUNSUCCESSFUL- 性表array中順序檢索，查找關(guān)鍵碼i為關(guān)鍵碼K在表中的下標(biāo)，i值為-1表示檢索intseqsrch(intK,ELEM*array,intn){inti=n-1;while(i>=0&&array[i].key!=K)i--;returni;}1假設(shè)檢索每個(gè)關(guān)鍵碼是等概率的，Pi=n-Pi·(n-i)i=

1n-(n-ni== i=n+12

i= ） –如果kmid=k，–當(dāng)kmid>k時(shí)，檢索繼 –相反地，若kmidk，就可以忽略mid以前的那部–Kmidk。該過程至多需要重復(fù) n次intbinary(intK,ELEM*array,intleft,intright)返回值為K//landrarebeyondtheboundsofintl=left-1;intr=right+1;while(l+1!=r){ //Stopwhenlandrmeetintmid=(l+r)/2; //Lookatmiddleif(K<array[mid].key)r= //Inleftif(K==array[mid].key)returnmid;//Founditif(K>array[mid].key)l=mid; //Inrighthalf}returnUNSUCCESSFUL;//valueKnotin} 1011121314(1)(4) 檢索關(guān)鍵碼45。l=0;r=15;K=45第一次：mid=7;l=7;第二次：mid=11;array[11]=56>45r=11;(l=7)第三次：mid=9;r=9;第四次：mid=8;array[8]=45==45；return7352 2 n2)失敗的檢索長度是 或 n二分法檢索性能分析（續(xù)E(n)

ji2i-(ni=( (n+1)- 4)

(n+1)-2

(n>–缺點(diǎn)：要排序、順 時(shí)解決該問題所占用的時(shí)間1增至f(n),則稱該算法的時(shí)間代價(jià)為f(n)。時(shí)解決該問題所占用的空間1增至f(n),則稱該算法的空間代價(jià)為f(n)。大O表示法稱某程序的時(shí)間(或空間)代價(jià)O(f(n)),若存在正常數(shù)c和n0,當(dāng)問題的規(guī)模n≥n0后,該算法的時(shí)間(或空間)代價(jià)T(n)≤c·f(n),也稱該算法的時(shí)間(或空間)對(duì)于所有足夠大的輸入數(shù)據(jù)集（n≥n0），算 則:f1(n)+f2(n)=Ｏ(max(f1(n), 則:f1(n)·f2(n)=for,whiledo-whilesum=for(i=1;i<=n;i++)for(j=1;j<=n;j++)T(n)=c１＋c2n2例：假設(shè)CPU每秒處理106個(gè)指令，對(duì)21016106例：假設(shè)CPU每秒處理106個(gè)指令，對(duì)于輸入規(guī)模為n=108的問題，時(shí)間代價(jià)T(n)=T(108)=1082.66109106對(duì)T(n2n2￡3600·n￡42,T(n)=nlogn￡3600·n￡133,000,處理輸入規(guī)