一個北大學生學習數(shù)據(jù)結(jié)構(gòu)的經(jīng)驗

1、一個北大學生學習數(shù)據(jù)結(jié)構(gòu)的經(jīng)驗1 學習方法因為要準備這個話題， 所以我認真的思考了我的學習方法， 但是我覺得基本上我就是上課前看看書、上課時認真聽課、 下課以后復習復習、當然還有做作業(yè)時很認真的去做。根本談不上什么好方法， 不過我還是有一些話要送給大家。我能行！ 個人覺得這句話非常重要，不知道大家是怎樣看待數(shù)據(jù)結(jié)構(gòu)這門課的， 有多少人覺得數(shù)據(jù)結(jié)構(gòu)很難呢？我知道還是有一些同學這樣覺得的， 有時候我跟我的朋友講要怎樣學，講了一大堆以后， 他就向我抱怨：我以前c都沒有學好， 數(shù)據(jù)結(jié)構(gòu)更學不好了， 這哪跟哪的話啊，數(shù)據(jù)結(jié)構(gòu)與c沒有什么關(guān)系，我想假如抱有這樣的心態(tài)， 自己就不相信自己， 那是不可能學好的

2、， 然后那些覺得數(shù)據(jù)結(jié)構(gòu)很難的同學， 我想他們應(yīng)該會很看重數(shù)據(jù)結(jié)構(gòu)的吧， 然后就一天到晚捧著一本數(shù)據(jù)結(jié)構(gòu)， 這樣不會覺得很累嗎？而且因為覺得很難， 就容易不相信自己， 學的效率也不會很好， 個人認為數(shù)據(jù)結(jié)構(gòu)很好學， 很容易學， 或許這有點妄自菲薄吧， 但是因為我覺得很容易， 當然就會覺得自己沒問題， 學得很輕松， 效果也還可以。大家都是從高考走過來的， 應(yīng)該知道心態(tài)的重要性吧， 兩種不同的心態(tài)， 完全就是兩種不同的效果。 學了這么久數(shù)據(jù)結(jié)構(gòu)了， 我們到底在學些什么呢？ 不知道大家有沒有想過， 那現(xiàn)在我們現(xiàn)在來歸納一下我們學習的內(nèi)容吧， 其實學到現(xiàn)在我們也就學了幾種普通的數(shù)據(jù)結(jié)構(gòu)， 象二叉樹，

3、樹， 圖，還有排序的問題， 前面的線性表和字符串也就是一些概念， 當然還有一個很重要的KMP算法， 然后在每種數(shù)據(jù)結(jié)構(gòu)中我們也就是學到了若干處理的算法， 我想真正數(shù)起來也就是幾十個算法吧。 學習數(shù)據(jù)結(jié)構(gòu)也就是要掌握這幾十種算法， 多簡單。至于如何掌握每個算法呢， 我想就是多看看書， 重要的是能夠理解。我能獨自完成作業(yè)！這里我的定義和老師的不同， 老師是鼓勵大家討論的， 不過我發(fā)現(xiàn)還是有一些同學就是先問好別人算法，然后再自己寫， 雖然這個不算抄襲作業(yè)， 但自己基本上沒有一個思考問題的過程， 雖然要理解算法也會要思考很多， 但是因為沒有自己獨立的思考過程， 要自己寫程序、 寫算法的時候根本寫不出來

4、， 所以我想如果真的想學好數(shù)據(jù)結(jié)構(gòu)的話， 最好是能夠自己思考問題， 不要剛想了一會就覺得做不出來， 然后就去問其他人。其實老師給我們的作業(yè)還是基于我們的水平的， 我絕對相信我們自己能夠獨自想出算法， 雖有可能會比較長時間吧， 但是這樣肯定會比問其他人學到更多的東西。當然我并不是說不要問同學， 有時候就是腦筋轉(zhuǎn)不過來，一問別人就懂了， 當然問了別人不能只是我知道了這個算法， 還應(yīng)該去想如何思考才能得到這個算法，這樣水平會提高很多。多實驗！這個就沒有太多理由了， 我一直覺得編程是一門熟練科學， 多編程，水平肯定會提高， 最重要的是能夠養(yǎng)成一種感覺，就是對程序?qū)λ惴ǖ拿舾校?為什么那些牛人看一個算法

5、一下子就看懂了？而自己要看很久才能弄懂， 而且弄懂了過了一陣子又忘記了？其實這個是因為牛人們以前看的程序很多， 編得也很多， 所以他們有了那種感覺，所以我覺得大家應(yīng)該多看程序， 多寫程序， 培養(yǎng)自己的感覺。2 復習和考試的技巧我想大家應(yīng)該都有這樣的感覺，就是覺得自己什么都掌握了， 但是在考試的時候就是會犯暈， 有時候一出考場就知道錯在哪個了， 然后考完以后一對答案，發(fā)現(xiàn)其實考得很簡單， 應(yīng)該都是自己會做的， 這個就是與自己的復習和考試的技巧有關(guān)系了。首先就是復習， 前面已經(jīng)說過其實我們學的算法也就是幾十個， 那么我們的任務(wù)也就是理解這幾十個算法， 復習也就是要加深你的理解。如何理解算法， 然后

6、理解到什么程度呢？ 是能默出整個算法嗎？其實不是這樣的， 數(shù)據(jù)結(jié)構(gòu)的考試有它的特點， 考過期中考試了， 大家應(yīng)該都發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)其實不要求你把整個算法背出來， 它注重考察你的理解， 那么怎么考察呢？其實也就是兩種方式吧， 一種就是用實例， 就是給你一個例子， 要你用某個算法運行出結(jié)果， 我想這個期末考試的時候仍然會有很多這樣的題目， 比如排序那塊就很好出這樣的題目，要復習這種題目我覺得很簡單，就是每個算法都自己用例子去實踐一下， 以不變應(yīng)萬變，我期中復習的時候就是這樣去做的， 而且考試之前我就覺得那個并查集的題目就很有可能會考， 于是就自己出了幾個例子，做了一下。另外一種考察方式就是算法填空和算

7、法改錯， 可能有一些同學覺得這種題目很難， 其實我們首先可以確定這兩種題目肯定是與書上算法有關(guān)系的， 只要理解了書上的算法就可以了，有人覺得看完書以后什么都懂了， 而且要默也默得出來， 其實不是這樣的，算法改錯和填空主要是考察的細微處， 雖然你覺得你默得出來， 那是能夠默出算法的主體部分， 很多細微的地方你就會很容易忽略。我想大家考過期中考以后應(yīng)該都有這種感覺吧？那要怎樣解決這種問題呢？ 我覺得有兩種方法， 一種就是自己去編程實現(xiàn)， 這種方法比較有意義，還能夠提高編程水平， 另外一種就是用實例分析算法的每句話， 我認為這種方法是最有效的。然后還有一種題目， 就是最后的寫算法的題目， 我覺得這種

8、題目還是很好解決的， 只要是能夠自己做出作業(yè)的， 基本上都會很容易做出來，這也是為什么我前面覺得平時做作業(yè)應(yīng)該自己獨立思考的原因，同時做這種題目千萬要小心， 尤其是題目簡單的時候， 那肯定會有一些小地方要考慮清楚，一不小心就會被扣掉很多分， 這樣很不值。我覺得考試的時候沒有太多要講的， 只要復習好了， 考試的時候細心一點就可以了， 然后就是做一個題目開始就要盡量保證正確，如果覺得留在那里等后面做完了再來檢查，這樣錯誤還是很有可能檢查不出來， 我期中考試的時候就基本上沒有檢查， 因為我做每個題目都是確保正確， 用的時間也挺多的， 然后也覺得沒有檢查的必要了。 一個學生學習數(shù)據(jù)結(jié)構(gòu)的體會（轉(zhuǎn)）讀數(shù)

9、據(jù)結(jié)構(gòu)（C語言版）（1）今天開始認真讀這本清華版的數(shù)據(jù)結(jié)構(gòu)，嚴蔚敏和吳偉民編著。也許你會奇怪我為什么會選擇這本C語言描述的數(shù)據(jù)結(jié)構(gòu)書，現(xiàn)在的數(shù)據(jù)結(jié)構(gòu)不都用面向?qū)ο笳Z言描述嗎？其實這本書不是我選的，而是我參加的機試指定的參考書。不過對于本書選用的語言，我倒有自己的看法。用C語言描述顯然有很多不便，但是在一個充斥著用OO描述數(shù)據(jù)結(jié)構(gòu)的世界里，從OO中抽身出來用C看待數(shù)據(jù)結(jié)構(gòu)的思想，也許更能看清數(shù)據(jù)結(jié)構(gòu)的本質(zhì)。好了，言歸正傳。在今天這第一篇文章里，我來探討一下數(shù)據(jù)結(jié)構(gòu)的基本概念。作者一開篇就歸納了計算機解題的一般步驟：“首先要從具體問題抽象出一個適當?shù)臄?shù)學模型，然后設(shè)計一個解此數(shù)學模型的算法，最后編

10、出程序，進行測試、調(diào)試直至得到最終解答?！蔽野阉龠M一步歸納一下，就是：抽象數(shù)學模型設(shè)計算法編寫程序。這個思路非常重要，除了一些非常簡單的問題，所有的程序設(shè)計都應(yīng)該遵循這三個基本步驟。我們平時寫程序常犯的錯誤是忽略第一個或第二個步驟，或者更甚者，前兩個都忽略。在設(shè)計數(shù)學模型的過程中，實際上就引出了數(shù)據(jù)結(jié)構(gòu)的概念。本書中作者給出的定義是：“簡單來說，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等的學科。”國內(nèi)的教材為了語言上的嚴謹常常把話說得很難懂。請大家注意這句話里的這幾個關(guān)鍵詞：1）非數(shù)值計算，這說明了數(shù)據(jù)結(jié)構(gòu)這門學科的應(yīng)用范圍，如果你想解一個線性方程

11、組，大概很難直接找到合適的數(shù)據(jù)結(jié)構(gòu)；2）操作對象，也就是問題中的數(shù)據(jù)及其表示的形式；3）關(guān)系，即數(shù)據(jù)間的關(guān)系；4）操作，即針對數(shù)據(jù)的操作。把以上的定義用公式寫出來，就是Data_Structure = (D, S)其中D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。所以在設(shè)計數(shù)據(jù)結(jié)構(gòu)時，首要的任務(wù)就是找出要操作的數(shù)據(jù)，其次是挖掘出數(shù)據(jù)間的關(guān)系。這兩步完成以后，數(shù)據(jù)的邏輯結(jié)構(gòu)就定下來了。其中數(shù)據(jù)間的結(jié)構(gòu)有以下幾種：集合，這和數(shù)學中的集合概念是一致的；線性結(jié)構(gòu)，即數(shù)據(jù)元素之間一對一的關(guān)系；樹形結(jié)構(gòu)，即數(shù)據(jù)元素之間一對多的關(guān)系；圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)，即數(shù)據(jù)元素之間多對多的關(guān)系。然而只有邏輯結(jié)構(gòu)是不夠的，程

12、序要能夠運行，必須把數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中表示出來，也就是設(shè)計物理結(jié)構(gòu)。大多數(shù)高級語言都對數(shù)據(jù)的物理結(jié)構(gòu)有較好支持，如各種數(shù)據(jù)類型。作者在解釋數(shù)據(jù)類型的概念時說到：“引入數(shù)據(jù)類型的目的，從硬件的角度看，是作為解釋計算機內(nèi)存中信息含義的一種手段，而對使用數(shù)據(jù)類型的用戶來說，實現(xiàn)了信息的隱蔽，即將一切用戶不必了解的細節(jié)都封裝在類型中?！边@個概括非常精辟，從中可以看出以后的OOP只是在更高層次上對信息的封裝和隱蔽。對數(shù)據(jù)類型進一步擴展，作者引出了抽象數(shù)據(jù)類型的概念。抽象數(shù)據(jù)類型（ADT）是指一個數(shù)學模型以及定義在該模型上的一組操作。在引入抽象數(shù)據(jù)類型后，使邏輯結(jié)構(gòu)更加獨立，從而讓程序員可以更加專注

13、于邏輯結(jié)構(gòu)的設(shè)計。把抽象數(shù)據(jù)類型用公式表示出來，就是(D, S, P)，其中D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集。如果計算機解題一定要遵循一個通用的模式的話，上面這個式子就給出了答案。 讀數(shù)據(jù)結(jié)構(gòu)（C語言版）（2）本節(jié)談一談算法分析和大O估算法（big-O notation）。算法效率的度量一般采用事前分析估算的方法，通常的做法是，“從算法中選取一種對于所研究的問題（或算法類型）來說是基本操作的原操作，以該基本操作重復執(zhí)行的次數(shù)作為算法的時間量度”。談到這里時，作者引出了大O估算法。在本書中，作者對大O估算法的介紹顯得有些草率。一開始就冒出一個式子T(n) = O(n3)，然后

14、在本頁最底下用小字介紹了所謂的“O的形式定義”：若f(n)是正整數(shù)n的一個函數(shù)，則xn=O(f(n)表示存在一個正的常數(shù)M，使得當nn0時都滿足|xn|M|f(n)|。也許是我數(shù)學基礎(chǔ)太差，總之看到這個定義時我一頭霧水。不知道為什么作者沒有花一點篇幅介紹大O估算法的由來和定義。我google了一下，發(fā)現(xiàn)了這樣的介紹：Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usu

15、ally the number of items. Informally, saying some equation f(n) = O(g(n) means it is less than some constant multiple of g(n). The notation is read, f of n is big oh of g of n.Formal Definition: f(n) = O(g(n) means there are positive constants c and k, such that 0 f(n) cg(n) for all n k. The values

16、of c and k must be fixed for the function f and must not depend on n.Note: As an example, n2 + 3n + 4 is O(n2), since n2 + 3n + 4 10. Strictly speaking, 3n + 4 is O(n2), too, but big-O notation is often misused to mean equal to rather than less than. The notion of equal to is expressed by (n). The i

17、mportance of this measure can be seen in trying to decide whether an algorithm is adequate, but may just need a better implementation, or the algorithm will always be too slow on a big enough input. For instance, quicksort, which is O(n log n) on average, running on a small desktop computer can beat

18、 bubble sort, which is O(n2), running on a supercomputer if there are a lot of numbers to sort. To sort 1,000,000 numbers, the quicksort takes 20,000,000 steps on average, while the bubble sort takes 1,000,000,000,000 steps! Any measure of execution must implicitly or explicitly refer to some comput

19、ation model. Usually this is some notion of the limiting factor. For one problem or machine, the number of floating point multiplications may be the limiting factor, while for another, it may be the number of messages passed across a network. Other measures which may be important are compares, item

20、moves, disk accesses, memory used, or elapsed (wall clock) time.（以上介紹來自：Paul E. Black, big-O notation, from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.）另外，這個帖子也討論了算法的時間復雜度估計，說得非常通俗易懂。 說明：因我上傳附件受到限制，只能這樣發(fā)帖。讀數(shù)據(jù)結(jié)構(gòu)（C語言版）（3）【問題描述】 設(shè)計一個可進行復數(shù)運算的演示程序?！净疽蟆?實現(xiàn)下列六種基本運算：由輸入的實部和虛部生成

21、一個復數(shù)；兩個復數(shù)求和；兩個復數(shù)求差；兩個復數(shù)求積；從已知復數(shù)中分離出實部；從已知復數(shù)中分離出虛部。 運算結(jié)果以相應(yīng)的復數(shù)或?qū)崝?shù)的表示形式顯示。【測試數(shù)據(jù)】 對下列各對數(shù)據(jù)實現(xiàn)求和：0；0；應(yīng)輸出“0” 3.1，0；4.22，8.9；應(yīng)輸出“7.32+i8.9” -1.33，2.34；0.1，-6.5；應(yīng)輸出“-1.23-i4.16” 0，9.7；-2.1，-9.7；應(yīng)輸出“-2.1” 7.7，-8；-7.7，0；應(yīng)輸出“-i8” 【實現(xiàn)提示】 定義復數(shù)為由兩個相互之間存在次序關(guān)系的實數(shù)構(gòu)成的抽象數(shù)據(jù)類型，則可以利用實數(shù)的操作來實現(xiàn)復數(shù)的操作?！疚业脑创a】#include #include #

22、define MAXLINE 100typedef struct double real; double imag; Complex;Complex InitComplex(double real, double imag) Complex c; c.real = real; c.imag = imag; return c;Complex Add(Complex c1, Complex c2) Complex c; c.real = c1.real + c2.real; c.imag = c1.imag + c2.imag; return c;Complex Subtract(Complex

23、c1, Complex c2) Complex c; c.real = c1.real - c2.real; c.imag = c1.imag - c2.imag; return c;Complex Multiply(Complex c1, Complex c2) Complex c; c.real = c1.real * c2.real - c1.imag * c2.imag; c.imag = c1.real * c2.imag + c1.imag * c2.real; return c;double GetReal(Complex c) return c.real;double GetI

24、mag(Complex c) return c.imag;void Read(Complex *pc) char aMAXLINE; int i, c; for (i = 0; (c = getchar() != , & c != ; i+) ai = c; ai = 0; pc-real = atof(a); if (c = ;) pc-imag = 0; return; for (i = 0; (c = getchar() != ; i+) ai = c; ai = 0; pc-imag = atof(a);void Print(Complex c) if (c.real != 0 & c

25、.imag != 0) printf(%g, c.real); if (c.imag 0) printf(+i%g, c.imag); else printf(-i%g, -c.imag); else if (c.real = 0 & c.imag != 0) if (c.imag 0) printf(i%g, c.imag); else printf(-i%g, -c.imag); else printf(%g, c.real);main() int c; Complex c1, c2, result; clrscr(); while (1) printf(Select an operati

26、on (press 1, 2, 3 or 4):nn); printf(-nn); printf(1. Add a complex to anothernn); printf(2. Subtract a complex from anothernn); printf(3. Multiply a complex to anothernn); printf(4. Quitnn); printf(-nn); while (c = getch() != 1 & c != 2 & c != 3 & c != 4) ; if (c = 4) return; printf(Input two complex

27、es (e.g.: 1.3,2.4;6;):nn); Read(&c1); Read(&c2); printf(nThe result is:t); switch(c) case 1: result = Add(c1, c2); break; case 2: result = Subtract(c1, c2); break; case 3: result = Multiply(c1, c2); break; Print(result); printf(nThe real is:t%g, GetReal(result); printf(nThe imag is:t%gnn, GetImag(re

28、sult); 讀數(shù)據(jù)結(jié)構(gòu)（C語言版）（4）從本節(jié)開始討論線性表，這次先討論線性表的順序?qū)崿F(xiàn)。一提到線性表，我們腦子很可能會出現(xiàn)數(shù)組、鏈表這樣的概念。沒錯，數(shù)組和鏈表都是線性表，但它們只是線性表的兩種實現(xiàn)，強調(diào)的是線性表的物理結(jié)構(gòu)。我們研究一個數(shù)據(jù)結(jié)構(gòu)時，一般先從它的邏輯結(jié)構(gòu)入手，等研究清楚了邏輯結(jié)構(gòu)再考慮具體的物理實現(xiàn)。在寫程序時，思路也是一樣的，先要分清哪些問題是邏輯的，哪些問題是物理的，先邏輯后物理是計算機解題的一般步驟。如果開始不想清楚邏輯，而一頭扎到物理細節(jié)中，就容易理不清思路或者作出有缺陷的設(shè)計。當然這不是絕對的，很多情況下物理結(jié)構(gòu)也會影響邏輯結(jié)構(gòu)的設(shè)計。簡單來說，一個線性表是n個相

29、同特性的數(shù)據(jù)元素的有限序列。這里“n個相同特性的數(shù)據(jù)元素”指的是數(shù)據(jù)對象，“序列”指的是數(shù)據(jù)關(guān)系，每個數(shù)據(jù)元素都有一個確定的位置。從數(shù)據(jù)對象和數(shù)據(jù)關(guān)系入手，就很容易看清一個數(shù)據(jù)結(jié)構(gòu)的本質(zhì)。就線性表來說，只要某些數(shù)據(jù)存在次序關(guān)系，并且各個元素特性相同，就可以認為是一個線性表。下面我們來考慮線性表的順序?qū)崿F(xiàn)。在很多人包括我自己的眼里，線性表的順序?qū)崿F(xiàn)已經(jīng)和數(shù)組畫上了等號。雖然用數(shù)組實現(xiàn)線性表的順序存儲結(jié)構(gòu)天經(jīng)地義，但不應(yīng)該把順序?qū)崿F(xiàn)局限在數(shù)組上。如果有一天你必須用匯編語言實現(xiàn)一個順序存儲的線性表，沒有了數(shù)組你豈不是哭了。如作者所說，線性表的順序表示指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)

30、元素。用C語言實現(xiàn)時，由于線性表的長度可變，且所需最大存儲空間隨問題不同而不同，所以通常用動態(tài)分配的一維數(shù)組來實現(xiàn)。#define LIST_INIT_SIZE 100 / 初始長度#define LISTINCREMENT 10 / 分配增量typedef struct ElemType *elem; / 存儲基址 int length; / 當前長度 int listsize; / 存儲容量 SqList;用上述結(jié)構(gòu)在分配存儲空間時，初始分配可以用malloc，空間不夠再分配時可以用realloc，這個函數(shù)保證在原分配基礎(chǔ)上擴大容量時不影響其內(nèi)容。 讀數(shù)據(jù)結(jié)構(gòu)（C語言版）（5）考研終于塵埃

31、落定，這個系列也得以繼續(xù)。查看上篇文章的發(fā)表日期，已一月有余?；叵脒@一個月中的種種經(jīng)歷，仍然心有余悸，聽到看到的種種現(xiàn)象，更是讓人觸目驚心。還好，一切都過去了，我又可以靜靜地寫文章了。上篇談到線性表的順序表示，這次接著談線性表的鏈式表示。順序表示的優(yōu)勢很明顯，它在數(shù)據(jù)的物理位置中隱含了數(shù)據(jù)的邏輯關(guān)系，簡單直接又威力無窮。但缺點也很明顯，在做插入或刪除操作時，需要移動大量數(shù)據(jù)。為了克服這個缺點，可以使用鏈式存儲。鏈式存儲不用物理位置隱含表示數(shù)據(jù)關(guān)系，它增加了一個指針域?qū)ｉT用來描述數(shù)據(jù)間的先后次序關(guān)系。在一個節(jié)點中，數(shù)據(jù)域存儲數(shù)據(jù)信息，而指針域存儲數(shù)據(jù)關(guān)系信息，結(jié)構(gòu)真是“相當?shù)摹鼻逦＿@樣雖然克服了順序表示的缺點，但同時帶來了兩個弊端。一是要存儲的數(shù)據(jù)量變大，二是不能隨機訪問某一個節(jié)點。所以線性表的兩種物理表示沒有好壞之分，只有適用不適用的區(qū)別。作者在介紹