數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)總結(jié)-資料下載頁(yè)
2025-06-22 15:17本頁(yè)面
【正文】 （d*n+d*rd）?！ 「鞣N排序方法的比較和選擇： 待排序的記錄數(shù)目n；n較大的要用時(shí)間復(fù)雜度為O（nlog2n）的排序方法； 記錄的大?。ㄒ?guī)模）；記錄大最好用鏈表作為存儲(chǔ)結(jié)構(gòu)，而快速排序和堆排序在鏈表上難于實(shí)現(xiàn)； 關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)； 對(duì)穩(wěn)定性的要求； 語(yǔ)言工具的條件； 存儲(chǔ)結(jié)構(gòu)； 時(shí)間和輔助空間復(fù)雜度?！ 〉诰耪?查找 查找的同時(shí)對(duì)表做修改操作（如插入或刪除）則相應(yīng)的表稱(chēng)之為動(dòng)態(tài)查找表，否則稱(chēng)之為靜態(tài)查找表。 衡量查找算法效率優(yōu)劣的標(biāo)準(zhǔn)是在查找過(guò)程中對(duì)關(guān)鍵字需要執(zhí)行的平均比較次數(shù)（即平均查找長(zhǎng)度ASL）?！ 【€性表查找的方法： 順序查找：逐個(gè)查找，ASL=（n+1）/2； 二分查找：取中點(diǎn)int（n/2）比較，若小就比左區(qū)間，大就比右區(qū)間。用二叉判定樹(shù)表示。ASL=（∑（每層結(jié)點(diǎn)數(shù)*層數(shù)））/N. 分塊查找。要求“分塊有序”，將表分成若干塊內(nèi)部不一定有序，并抽取各塊中的最大關(guān)鍵字及其位置建立有序索引表?！ 《媾判驑?shù)（BST）定義是：二叉排序樹(shù)是空樹(shù)或者滿(mǎn)足如下性質(zhì)的二叉樹(shù)： 若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； 若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；左、右子樹(shù)本身又是一棵二叉排序樹(shù)?！ 《媾判驑?shù)的插入、建立、刪除的算法平均時(shí)間性能是O（nlog2n）?！《媾判驑?shù)的刪除操作可分三種情況進(jìn)行處理： *P是葉子，則直接刪除*P，即將*P的雙親*parent中指向*P的指針域置空即可?！?P只有一個(gè)孩子*child，此時(shí)只需將*child和*p的雙親直接連接就可刪去*p. *p有兩個(gè)孩子，則先將*p結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)的數(shù)據(jù)到*p，刪除中序后繼結(jié)點(diǎn)?！￡P(guān)于B樹(shù)（多路平衡查找樹(shù)）。它適合在磁盤(pán)等直接存取設(shè)備上組織動(dòng)態(tài)的查找表，是一種外查找算法。建立的方式是從下向上拱起?！∩⒘屑夹g(shù)：將結(jié)點(diǎn)按其關(guān)鍵字的散列地址存儲(chǔ)到散列表的過(guò)程稱(chēng)為散列。散列函數(shù)的選擇有兩條標(biāo)準(zhǔn)：簡(jiǎn)單和均勻。常見(jiàn)的散列函數(shù)構(gòu)的造方法：平方取中法：hash=int（（x^2）%100）除余法：表長(zhǎng)為m，hash=x%m 相乘取整法：hash=int（m*（x*Aint（x*A））；A= 隨機(jī)數(shù)法：hash=random（x）。處理沖突的方法：開(kāi)放定址法： 一般形式為hi=（h（key）+di）%m1≤i≤m1，開(kāi)放定址法要求散列表的裝填因子α≤1. 開(kāi)放定址法類(lèi)型： 線性探查法：address=（hash（x）+i）%m；二次探查法：address=（hash（x）+i^2）%m； 雙重散列法：address=（hash（x）+i*hash（y））%m； 拉鏈法： 是將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一個(gè)單鏈表中?！ ? 拉鏈法的優(yōu)點(diǎn)： 拉鏈法處理沖突簡(jiǎn)單，且無(wú)堆積現(xiàn)象； 鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的適于無(wú)法確定表長(zhǎng)的情況； 拉鏈法中α可以大于1，結(jié)點(diǎn)較大時(shí)其指針域可忽略，因此節(jié)省空間；拉鏈法構(gòu)造的散列表刪除結(jié)點(diǎn)易實(shí)現(xiàn)?！ ±湻ㄒ灿腥秉c(diǎn)：當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí)，用拉鏈法中的指針域也要占用額外空間，還是開(kāi)放定址法省空間?！ 〉谑?文件 文件是性質(zhì)相同的記錄的集合。記錄是文件中存取的基本單位，數(shù)據(jù)項(xiàng)是文件可使用的最小單位，數(shù)據(jù)項(xiàng)有時(shí)稱(chēng)字段或者屬性?！ ∥募∵壿嫿Y(jié)構(gòu)是一種線性結(jié)構(gòu)。 操作有：檢索和維護(hù)。并有實(shí)時(shí)和批量處理兩種處理方式?！ ∥募〈鎯?chǔ)結(jié)構(gòu)是指文件在外存上的組織方式?！ 』镜慕M織方式有：順序組織、索引組織、散列組織和鏈組織?！ 〕Ｓ玫奈募M織方式：順序文件、索引文件、散列文件和多關(guān)鍵字文件?！ ≡u(píng)價(jià)一個(gè)文件組織的效率，是執(zhí)行文件操作所花費(fèi)的時(shí)間和文件組織所需的存儲(chǔ)空間?！ z索功能的多寡和速度的快慢，是衡量文件操作質(zhì)量的重要標(biāo)志?！ №樞蛭募侵赴从涗涍M(jìn)入文件的先后順序存放、其邏輯順序和物理順序一致的文件。主關(guān)鍵字有序稱(chēng)順序有序文件，否則稱(chēng)順序無(wú)序文件?！ ∫磺写鎯?chǔ)在順序存儲(chǔ)器（如磁帶）上的文件都只能順序文件，只能按順序查找法存取?！ №樞蛭募牟迦?、刪除和修改只能通過(guò)復(fù)制整個(gè)文件實(shí)現(xiàn)?！ ∷饕募慕M織方式：通常是在主文件之外建立一張索引表指明邏輯記錄和物理記錄之間一一對(duì)應(yīng)的關(guān)系，它和主文件一起構(gòu)成索引文件?！ ∷饕琼樞蛭募械乃饕頌槌砻芩饕?。索引順序文件中的索引表為稀疏索引?！ ∪粲涗浐艽笫沟盟饕硪埠艽髸r(shí)，可對(duì)索引表再建立索引，稱(chēng)為查找表。是一種靜態(tài)索引。 索引順序文件常用的有兩種： ISAM索引順序存取方法：是專(zhuān)為磁盤(pán)存取文件設(shè)計(jì)的，采用靜態(tài)索引結(jié)構(gòu)。 VSAM虛擬存儲(chǔ)存取方法：采用B+樹(shù)作為動(dòng)態(tài)索引結(jié)構(gòu)，由索引集、順序集、數(shù)據(jù)集組成?！ ∩⒘形募抢蒙⒘写鎯?chǔ)方式組織的文件，亦稱(chēng)為直接存取文件。 散列文件 優(yōu)點(diǎn)是：文件隨機(jī)存放，記錄不需要排序；插入刪除方便；存取速度快；不需要索引區(qū)，節(jié)省存儲(chǔ)空間?！∪秉c(diǎn)是：不能進(jìn)行順序存取，只能按關(guān)鍵字隨機(jī)存取，且詢(xún)問(wèn)方式限地簡(jiǎn)單詢(xún)問(wèn)，需要重新組織文件?！ 《嘀乇砦募簩?duì)需要查詢(xún)的次關(guān)鍵字建立相應(yīng)的索引，對(duì)相同次關(guān)鍵字的記錄建一個(gè)鏈表并將鏈表頭指針、長(zhǎng)度、次關(guān)鍵字作為索引表的索引項(xiàng)?！ 〉古疟恚捍侮P(guān)鍵字索引表稱(chēng)倒排表，主文件和倒排表構(gòu)成倒排文件。
語(yǔ)文相關(guān)推薦
鄂ICP備17016276號(hào)-1