一個(gè)北大學(xué)生學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的經(jīng)驗(yàn)

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

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

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

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

5、一下子就看懂了？而自己要看很久才能弄懂， 而且弄懂了過(guò)了一陣子又忘記了？其實(shí)這個(gè)是因?yàn)榕Ｈ藗円郧翱吹某绦蚝芏啵?編得也很多， 所以他們有了那種感覺(jué)，所以我覺(jué)得大家應(yīng)該多看程序， 多寫(xiě)程序， 培養(yǎng)自己的感覺(jué)。2 復(fù)習(xí)和考試的技巧我想大家應(yīng)該都有這樣的感覺(jué)，就是覺(jué)得自己什么都掌握了， 但是在考試的時(shí)候就是會(huì)犯暈， 有時(shí)候一出考場(chǎng)就知道錯(cuò)在哪個(gè)了， 然后考完以后一對(duì)答案，發(fā)現(xiàn)其實(shí)考得很簡(jiǎn)單， 應(yīng)該都是自己會(huì)做的， 這個(gè)就是與自己的復(fù)習(xí)和考試的技巧有關(guān)系了。首先就是復(fù)習(xí)， 前面已經(jīng)說(shuō)過(guò)其實(shí)我們學(xué)的算法也就是幾十個(gè)， 那么我們的任務(wù)也就是理解這幾十個(gè)算法， 復(fù)習(xí)也就是要加深你的理解。如何理解算法， 然后

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

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

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

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

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

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

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

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

14、在本頁(yè)最底下用小字介紹了所謂的“O的形式定義”：若f(n)是正整數(shù)n的一個(gè)函數(shù)，則xn=O(f(n)表示存在一個(gè)正的常數(shù)M，使得當(dāng)nn0時(shí)都滿足|xn|M|f(n)|。也許是我數(shù)學(xué)基礎(chǔ)太差，總之看到這個(gè)定義時(shí)我一頭霧水。不知道為什么作者沒(méi)有花一點(diǎn)篇幅介紹大O估算法的由來(lái)和定義。我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.（以上介紹來(lái)自：Paul E. Black, big-O notation, from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.）另外，這個(gè)帖子也討論了算法的時(shí)間復(fù)雜度估計(jì)，說(shuō)得非常通俗易懂。 說(shuō)明：因我上傳附件受到限制，只能這樣發(fā)帖。讀數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（3）【問(wèn)題描述】 設(shè)計(jì)一個(gè)可進(jìn)行復(fù)數(shù)運(yùn)算的演示程序?！净疽蟆?實(shí)現(xiàn)下列六種基本運(yùn)算：由輸入的實(shí)部和虛部生成

21、一個(gè)復(fù)數(shù)；兩個(gè)復(fù)數(shù)求和；兩個(gè)復(fù)數(shù)求差；兩個(gè)復(fù)數(shù)求積；從已知復(fù)數(shù)中分離出實(shí)部；從已知復(fù)數(shù)中分離出虛部。 運(yùn)算結(jié)果以相應(yīng)的復(fù)數(shù)或?qū)崝?shù)的表示形式顯示。【測(cè)試數(shù)據(jù)】 對(duì)下列各對(duì)數(shù)據(jù)實(shí)現(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” 【實(shí)現(xiàn)提示】 定義復(fù)數(shù)為由兩個(gè)相互之間存在次序關(guān)系的實(shí)數(shù)構(gòu)成的抽象數(shù)據(jù)類型，則可以利用實(shí)數(shù)的操作來(lái)實(shí)現(xiàn)復(fù)數(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語(yǔ)言版）（4）從本節(jié)開(kāi)始討論線性表，這次先討論線性表的順序?qū)崿F(xiàn)。一提到線性表，我們腦子很可能會(huì)出現(xiàn)數(shù)組、鏈表這樣的概念。沒(méi)錯(cuò)，數(shù)組和鏈表都是線性表，但它們只是線性表的兩種實(shí)現(xiàn)，強(qiáng)調(diào)的是線性表的物理結(jié)構(gòu)。我們研究一個(gè)數(shù)據(jù)結(jié)構(gòu)時(shí)，一般先從它的邏輯結(jié)構(gòu)入手，等研究清楚了邏輯結(jié)構(gòu)再考慮具體的物理實(shí)現(xiàn)。在寫(xiě)程序時(shí)，思路也是一樣的，先要分清哪些問(wèn)題是邏輯的，哪些問(wèn)題是物理的，先邏輯后物理是計(jì)算機(jī)解題的一般步驟。如果開(kāi)始不想清楚邏輯，而一頭扎到物理細(xì)節(jié)中，就容易理不清思路或者作出有缺陷的設(shè)計(jì)。當(dāng)然這不是絕對(duì)的，很多情況下物理結(jié)構(gòu)也會(huì)影響邏輯結(jié)構(gòu)的設(shè)計(jì)。簡(jiǎn)單來(lái)說(shuō)，一個(gè)線性表是n個(gè)相

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

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

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