西安交通大學數(shù)據(jù)結構復習資料(已修改)
2025-04-29 12:21 本頁面
【正文】 第一章 緒 論數(shù)據(jù)結構的主要研究內容①數(shù)據(jù)的邏輯結構數(shù)據(jù)關系之間的邏輯關系 ②數(shù)據(jù)的存儲結構數(shù)據(jù)的邏輯結構在計算機中的表示 數(shù)據(jù)邏輯結構的種類：集合、線性表、樹和圖的性質和特點。v 集合結構中的元素是各自獨立的，元素之間沒有聯(lián)系v 線性結構中的元素是一個接一個串聯(lián)起來的，它有一個頭元素和一個尾元素，其余為中間元素；每個中間元素既有前驅元素，又有后繼元素v 在樹結構中，樹根結點只有后繼結點，而沒有前驅結點；除樹根結點外，每個結點都有唯一一個前驅結點，又稱為是父結點或雙親結點v 在圖結構中，每個結點或稱頂點都可以有任意多個前驅結點和任意多個后繼結點。 v 樹結構是圖結構的特例，線性結構是樹結構的特例。為了區(qū)別于線性結構，時常把樹結構和圖結構稱為非線性結構。數(shù)據(jù)結構的二元組定義，能根據(jù)給出的二元組來判斷數(shù)據(jù)的邏輯結構類型。v 集合結構中的元素集合K和二元關系R分別為： K={A，B，C，D，E，F(xiàn)，G} R={ }v 線性結構中的元素集合K和二元關系R分別為： K={A，B，C，D，E，F(xiàn)，G} R={A,B，B,C，C,D，D,E，E,F，F(xiàn),G}v 樹結構中的元素集合K和二元關系R分別為： K={A，B，C，D，E，F(xiàn)，G} R={A,B，A,C，A,D，C,E，C,F，D,G}v 圖結構中的元素集合K和二元關系R分別為： K={A，B，C，D，E，F(xiàn)，G} R={A,B，A,C，A,G，D,G，D,F，C,E，C,F，G,F}了解數(shù)據(jù)的幾種存儲結構（物理結構）及它們各自的性質和特點。（1）順序的方法: 將邏輯上相鄰的元素存儲到物理上相鄰的存儲位置. 常用于線性的數(shù)據(jù)結構.（2）鏈式結構：給結點附加一個指針字段, 指出其后繼節(jié)點的位置, 即存放結點的存儲單元分為兩部分:數(shù)據(jù)項指針項（3）散列（hashing) 結構：散列的方法是用結點的關鍵字值直接計算出結點的存儲地址。這個取值函數(shù)也稱為散列函數(shù)。 數(shù)據(jù)的邏輯結構、存儲結構和總的數(shù)據(jù)結構之間的關系v 邏輯結構相同，但存儲結構不同，則認為是不同的數(shù)據(jù)結構。 如順序表和鏈表具有相同的邏輯結構，但存儲結構分別為順序結構和鏈表結構算法的設計要求有那些，會結合實際的語言設計來說明這些要求1）正確性：對于合法的輸入產生符合要求的輸出；2）可讀性：算法應該易讀、便于交流， 這也是保證算法正確性的前提；添加注釋也是一種增加可讀性的辦法；3）健壯性：當輸入非法時， 算法還能做出適當?shù)姆磻粫罎ⅲ?如輸出錯誤信息；算法中應該考慮適當?shù)腻e誤處理；4）效率高且內存消耗小：效率高指運行時間短。存儲指算法執(zhí)行過程中所需的最大存儲空間。了解時間復雜度的概念、時間復雜度的度量、時間復雜度的類型，能對實際的程序分析它的時間復雜度。算法的時間復雜度是一個算法運行時間的相對量度。把算法中包含簡單操作次數(shù)的多少叫做該算法的時間復雜度，或者叫做時間復雜性，用它來衡量一個算法的運行時間性能或稱計算性能v 平均復雜度(The Average Case)：．v 最壞情況復雜度 (The Worst Case)：估算最壞情況下時間復雜度的一個上界．這也是通常所指的復雜度．v 最好復雜度 (The Best Case):在最理想輸入情況下的時間復雜度。第二章 線性表了解并掌握線性表的定義及性質線性表是線性結構的一種表現(xiàn)形式，即是具有相同屬性數(shù)據(jù)元素的一個有限序列，序列中的元素是一個接一個在邏輯上是有序的，序列中元素的個數(shù)就是該線性表的長度.v 存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素v 存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素v 除起點元素之外，集合中的每個數(shù)據(jù)元素均只有一個前驅v 除終點元素之外，集合中每個數(shù)據(jù)元素均只有一個后繼v 起點元素只有后繼沒有前驅，終點元素只有前驅沒有后繼 v 對于線性表中的數(shù)據(jù)元素ai1和ai來說，ai1是ai的直接前驅，ai是ai1的直接后繼。v 所有數(shù)據(jù)元素ai在同一個線性表中必須是相同的數(shù)據(jù)類型。熟悉順序線性表（順序存儲的線性表）的存儲方式及其表單元（簡單數(shù)據(jù)類型和記錄數(shù)據(jù)類型）的定位和計算。 線性表的順序存儲指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。線性表的順序存儲結構具有以下兩個基本特點：（1）線性表中所有元素所占的存儲空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的，即前驅元素一定存儲在后繼元素的前面。熟悉順序線性表的插入、刪除和查找的算法思想和程序了解線性表鏈接存儲的結構和特點v 假設數(shù)據(jù)結構中的每一個數(shù)據(jù)結點對應于一個存儲單元，這種存儲單元稱為存儲結點，簡稱結點。v 在鏈式存儲方式中，要求每個結點由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域（或稱為信息域）；另一部分用于存放指針，稱為指針域。其中指針用于指向該結點的前一個或后一個結點，從而可以表示數(shù)據(jù)元素之間的邏輯關系。v 長度可以任意擴充，存儲效率較高；v 物理存儲可以是不連續(xù)的；v 數(shù)據(jù)元素的邏輯次序可以與其存儲的物理次序不一致。v 插入、刪除運算靈活方便，不需移動結點，只要改變結點中指針域的值即可了解單鏈表、雙向鏈表和循環(huán)鏈表的結構和特點通過每個結點的指針域將n個結點按其邏輯順序鏈接在一起的結點序列我們就稱為鏈表。如果這一鏈表中每個結點只有一個指針域，則稱該鏈表為線性鏈表或單鏈表，否則則稱為雙向鏈表。雙向鏈表是指線性鏈表中的每個結點設置兩個指針，一個稱為左指針，用以指向其直接前驅；另一個稱為右指針，用以指
教學教案相關推薦
鄂ICP備17016276號-1