數(shù)據(jù)結(jié)構(gòu)知識點整理(編輯修改稿)
2025-07-19 14:47 本頁面
【文章內(nèi)容簡介】 先檢查這個元素是否在樹中已經(jīng)存在。在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒有。如果搜索成功，說明樹中已經(jīng)有這個元素，不再插入；如果搜索不成功，說明樹中原來沒有關鍵碼等于給定值的結(jié)點，把新元素加到搜索操作停止的地方。 圖定義：圖是由頂點集合(vertex)及頂點間的關系集合組成的一種數(shù)據(jù)結(jié)構(gòu)：Graph＝( V, E ) 其中 V = { x | x 206。 某個數(shù)據(jù)對象} 是頂點的有窮非空集合； E = {(x, y) | x, y 206。 V } 或E = {x, y | x, y 206。 V amp。amp。 Path (x, y)}，是頂點之間關系的有窮集合，也叫做邊(edge)集合。Path (x, y)表示從 x 到 y 的一條單向通路, 它是有方向的。有向圖與無向圖：在有向圖中，頂點對 x, y 是有序的。在無向圖中，頂點對(x, y)是無序的。完全圖：若有 n 個頂點的無向圖有 n(n1)/2 條邊, 則此圖為完全無向圖。有 n 個頂點的有向圖有n(n1) 條邊, 則此圖為完全有向圖在圖的鄰接矩陣表示中，有一個記錄各個頂點信息的頂點表，還有一個表示各個頂點之間關系的鄰接矩陣。鄰接表是鄰接矩陣的改進形式。為此需要把鄰接矩陣的各行分別組織為一個單鏈表。在鄰接表中，同一個頂點發(fā)出的邊鏈接在同一個邊鏈表中，每一個鏈結(jié)點代表一條邊（邊結(jié)點），結(jié)點中有另一頂點的下標 dest 和指針 link。對于帶權圖，邊結(jié)點中還要保存該邊的權值cost。頂點表的第 i 個頂點中保存該頂點的數(shù)據(jù)，以及它對應邊鏈表的頭指針adj最短路徑問題：如果從圖中某一頂點（稱為源點）另一頂點（稱為終點）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權值總和達到最小。排序：將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。 數(shù)據(jù)表(datalist): 它是待排序數(shù)據(jù)元素的有限集合。排序碼(key): 通常數(shù)據(jù)元素有多個屬性域, 即多個數(shù)據(jù)成員組成, 其中有一個屬性域可用來區(qū)分元素, 作為排序依據(jù)。該域即為排序碼。每個數(shù)據(jù)表用哪個屬性域作為排序碼，要視具體的應用需要而定。插入排序基本方法是：每步將一個待排序的元素，按其排序碼大小，插入到前面已經(jīng)排好序的一組元素的適當位置上, 直到元素全部插入為止。鏈表單鏈表中的插入與刪除第一種情況：在第一個結(jié)點前插入newnode→link = first 。 first = newnode；第二種情況：在鏈表中間插入 newnode→link = p→link。 p→link = newnode；第三種情況：在鏈表末尾插入 newnode→link = p→link。 p→link = last = newnode；鏈表插入算法實現(xiàn)鏈表結(jié)點刪除算法int List::Insert ( const int x, const int i ) {//在鏈表第 i 個結(jié)點處插入新元素 x ListNode *p = first。 int k = 0。 while ( p != NULL amp。amp。 k i 1 ) { p = p→link。 k++。 } //找第i1個結(jié)點 if ( p == NULL amp。amp。 first != NULL ) { cout “無效的插入位置!\n”。 return 0。 } ListNode *newnode= new ListNode(x, NULL)。 //創(chuàng)建新結(jié)點,其數(shù)據(jù)為x,指針為0 if ( first == NULL || i == 0 ) { //插在表前 newnode→link = first。 if ( first == NULL ) last = newnode。 first = newnode。 } else { //插在表中或末尾 newnode→link = p→link。 if ( p→link == NULL ) last = newnode。 p→link = newnode。 } return 1。 }int List::Remove ( int i ) { //在鏈表中刪除第i個結(jié)點Node *p = first, *q。 int k = 0。 while ( p != NULL amp。amp。 k i1 ) { p = p→link。 k++。 } //找第i1個結(jié)點 if ( p == NULL || p→link == NULL ) { cout “無效的刪除位置!\n”。 return 0。 } if ( i
規(guī)章制度相關推薦
鄂ICP備17016276號-1