歸并排序 二路歸并排序歸并過程 O(n)整個歸并排序需要?log2n?趟(k路歸并需要?logkn?) 空間效率O(n)時間效率O(nlog2n...
基本思想:每一趟(如第i趟)在后面n-i+1(i=1九昧,2...n-1)個待排序元素中選取關(guān)鍵字最小的元素乘凸,作為有序子序列的第i個元素,直到第n-...
冒泡排序 基本思想:從后往前比較相鄰元素良姆,把當(dāng)前序列中最小的元素交換至最前面蚁堤,去掉這個元素在剩下的序列中重復(fù)這個過程。 空間效率 O(1)時間效...
內(nèi)部排序:排序期間元素全部存放在內(nèi)存中外部排序:排序期間元素?zé)o法全部同時放在內(nèi)存中 插入排序 基本思想:每次將一個待排序的記錄按其關(guān)鍵字大小插入...
字符串 串的存儲結(jié)構(gòu) 1.定長順序存儲表示用一組地址連續(xù)的存儲單元 2.堆分配存儲表示仍以一組地址連續(xù)的存儲單元存放刽辙,但存儲空間是在程序執(zhí)行過程...
散列函數(shù):把查找表中的關(guān)鍵字映射成該關(guān)鍵字對應(yīng)的地址窥岩。Hash(key)=Addr這里的地址可以是數(shù)組下標(biāo),索引或內(nèi)存地址等宰缤。沖突:不同的關(guān)鍵字...
順序查找 (線性查找)1.一般線性表的順序查找引入哨兵颂翼,使得循環(huán)時不必判斷是否越界 ASL成功=(n+1)/2ASL失敗=n+12.有序表的順序...
深度優(yōu)先生成樹對于無向圖,處理邊(v, w)時慨灭,若w未被訪問過則將v->w作為樹的一條邊朦乏,否則將v->w畫成虛線表示后向邊,這條邊并不是樹的一部...
拓?fù)渑判?有向無環(huán)圖DAG頂點(diǎn)表示活動的網(wǎng)絡(luò)AOV網(wǎng):用DAG圖表示一個工程氧骤,其頂點(diǎn)表示活動呻疹,有向邊<vi,vj>表示活動vi必須先于活動vj進(jìn)...