【文章內(nèi)容簡介】 即節(jié)省時間，又節(jié)約空間，更重要的是機內(nèi)表示的數(shù)據(jù)取出來后要完全體現(xiàn)其邏輯結構。什么是算法？算法與程序有何區(qū)別與聯(lián)系？算法就是解決特定問題的的方法。而程序是通過某種語言將算法的具體實現(xiàn)手段。算法的時間復雜度僅與問題的規(guī)模相關嗎？不是。算法的時間復雜度還與算法中的語句頻度、數(shù)據(jù)的狀態(tài)等因素有關。數(shù)據(jù)結構是指邏輯結構和物理結構兩種，通常是指邏輯結構。選擇合適的存儲結構，通常考慮的指標有邏輯結構和數(shù)據(jù)類型兩個因素。數(shù)據(jù)結構按節(jié)點間的關系，可分為4種，分別是集合、線性結構、樹形結構和網(wǎng)狀結構。線性結構反映節(jié)點間的關系是一對一的，樹形結構反映節(jié)點間的關系是一對多的，網(wǎng)狀結構反映節(jié)點間的關系是多對多的。數(shù)據(jù)的邏輯結構是數(shù)據(jù)之間的外在聯(lián)系（與計算機存儲無關）。數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素的相對位置相關。數(shù)據(jù)的邏輯結構與其所含數(shù)據(jù)元素的個數(shù)無關。數(shù)據(jù)元素之間的邏輯關系與存儲單元的相鄰關系無關。在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分為線性結構和非線性結構。數(shù)據(jù)結構是一門研究操作對象以及他們之間的關系和運算等的學科。算法分析的目的是分析算法的效率以求改進。算法分析的兩個主要方面是空間復雜性和時間復雜性。計算機算法是指可讀性科文檔性。線性表簡述單鏈表、循環(huán)單鏈表、循環(huán)雙鏈表的結構特點。（1）單鏈表的結構：由節(jié)點構成，每個節(jié)點有兩個成員：數(shù)據(jù)域和指針域。單鏈表的特點：每個節(jié)點都只有一個指向直接后繼節(jié)點的指針，最后一個節(jié)點的指針域為空，單鏈表是只有一個鏈域的鏈表。（2）循環(huán)單鏈表結構：由節(jié)點構成，每個節(jié)點有兩個成員：數(shù)據(jù)域和指針域。循環(huán)單鏈表特點：鏈表中最后一個節(jié)點的指針域指向頭結點，整個鏈表形成一個環(huán)。（3）循環(huán)雙鏈表結構：由節(jié)點構成，每個節(jié)點包括三個域：數(shù)據(jù)域、前驅指針域和后繼指針域。循環(huán)雙鏈表特點：節(jié)點的next指針域指向后繼節(jié)點，prior指針域指向前驅節(jié)點。簡述順序表和鏈表的主要優(yōu)、缺點及適用范圍。（1）順序表用一組地址連續(xù)的存儲單元存放線性表中的數(shù)據(jù)，表中元素的物理關系和邏輯關系是一致的。表中元素可以隨機存取，但在程序執(zhí)行之前必須給出空間長度，容易造成空間浪費或者空間不夠的情況。鏈表用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素。存儲空間動態(tài)分配，不會產(chǎn)生溢出，但空間利用率低，節(jié)點訪問需要從表頭開始依次訪問。（2）順序表適用于經(jīng)常進行查找運算的數(shù)據(jù)，或者對數(shù)據(jù)量事先固定的問題。鏈表適用于經(jīng)常進行插入、刪除等數(shù)據(jù)量變化較大的動態(tài)問題。比較線性表的順序存儲結構與鏈式存儲結構存儲空間開銷大小，并說明理由。順序存儲結構存儲空間開銷小，鏈式存儲結構存儲空間開銷大。存儲空間開銷大小可以用存儲密度衡量。存儲密度=節(jié)點數(shù)據(jù)域所占空間/節(jié)點所占空間。節(jié)點存儲密度越大，空間利用率越高，則存儲空間開銷越小。順序存儲結構每個節(jié)點占一個空間，即存儲數(shù)據(jù)域的空間，而鏈式存儲結構每個節(jié)點所占兩個空間，即存儲數(shù)據(jù)域的空間和存儲指針域的空間。對于線性表的順序存儲結構與鏈式存儲而言，若線性表的長度基本穩(wěn)定，且很少進行插入與刪除操作，但要盡快地存取表中的數(shù)據(jù)元素，則應該選擇哪種存儲結構？為什么？應該選擇順序存儲結構。因為線性表的長度基本穩(wěn)定，可以預先進行分配，且要求盡快地存取表中的數(shù)據(jù)元素，而順序表中元素可以隨機存取。若頻繁地對線性表進行插入與刪除操作，該線性表應該采取什么存儲結構？為什么？應該選擇鏈式存儲結構。對線性表進行插入與刪除操作，順序表需要大量移動元素，而鏈表只需要修改需要相應的指針域就可以了。有哪些鏈表可僅由一個尾指針來唯一確定，即從尾指針出發(fā)能訪問到鏈表上任意一個節(jié)點？循環(huán)單鏈表和循環(huán)雙鏈表。在單鏈表、循環(huán)單鏈表和循環(huán)雙鏈表中，若僅知道指針p指向某節(jié)點，不知道頭指針，能否將節(jié)點*p從相應的鏈表中刪除？若可以，且時間復雜度各為多少？單鏈表不可以。循環(huán)單鏈表、循環(huán)雙鏈表可以。單鏈表時間復雜度O（n），循環(huán)單鏈表時間復雜度O（n），循環(huán)雙鏈表時間復雜度O（1）。線性表的兩種存儲結構分別為順序表結構和鏈表結構。訪問一個線性表中具有定值元素的時間復雜度為O（n）。對于一個為n的順序存儲的線性表，在表頭插入元素的時間復雜性為O（n），在表尾插入元素的時間復雜性為O（1）。線性表是一個有限序列，可以為空。一個線性表是n個數(shù)據(jù)元素的有限序列。在一個順序表的表尾插入一個元素的時間復雜度為O（1）。在一個單鏈表中，若要在p所指向的節(jié)點插入一個新節(jié)點，則需要相繼修改2個指針域的值。在一個單鏈表中，若要在p所指向的節(jié)點插入一個新節(jié)點，則此算法的時間復雜度為O（n）。在一個帶頭節(jié)點的雙向循環(huán)鏈表中，若要在p所指向的節(jié)點之前插入一個新節(jié)點，則需要相繼修改4個指針域的值。線性結構的特征：有且只有 一個根節(jié)點，它無前件；有且只有一個終端節(jié)點，它無后件；除根節(jié)點和終端節(jié)點以外，其他節(jié)點有且只有一個前件，也有且只有一個后件。在單鏈表中，增加頭節(jié)點的目的是方便運算的實現(xiàn)。用鏈表表示線性表的優(yōu)點是便于插入和刪除操作。在線性表的順序存儲中，元素之間的邏輯關系是通過物理存儲位置決定的；在線性表的鏈接存儲中，元素之間的邏輯關系是通過鏈域的指針值決定的。在雙向鏈表中，每個節(jié)點包含兩個指針域，一個指向前驅結點，另一個指向后繼結點。在線性表的順序存儲中，若一個元素的下標為i，則它的前驅元素的下標為i1，后繼元素的下標為i+1。一個線性表中，第一個元素的存儲地址是100，每個元素的長度是2，則第五個元素的地址是108。棧、隊列和數(shù)組簡述棧和隊列的相同點和不同點。相同點：都是存儲數(shù)據(jù)的線性表。不同點： 棧為LIFO（后進線出）線性表，插入、刪除操作均在表尾進行。隊列為FIFO（先進先出）線性表，插入在表尾進行、刪除在表頭進行。若進棧的數(shù)據(jù)元素序列依次為6，能否得到2和6的出棧列？并舉例說明為什么不能得到或如何得到。（1）不能得到2的出棧列。最先出棧的是4，則此時棧底元素為最先入棧的然后依次向上為3出棧后；5入棧，再出棧；6入棧，再出棧；這時得到序列為6；這時棧頂元素為2,2出棧后，1才能出棧，所以1不可能先于2出棧，因此不能得到此序列。（2）可以得到6的出棧列。1入棧，再出棧，1為第一個出棧元素；2入棧；3入棧，再出棧，3為第二個出棧元素；5一次入棧，此時，棧底元素為1,5成為棧頂元素，則5出棧，然后4出棧，然后2出棧；之后6入棧，再出棧；因此可以得到此出棧序列。向一個順序棧加一個元素時，首先若棧不滿棧頂指針上移，然后將元素加入到棧頂位置。從一個順序棧刪除元素時，首先判斷棧是否為空，然后若不為空棧頂指針下