緒論資料基本單位資料元素，資料項最小單位。
資料結構：邏輯、儲存、運算
演算法特性：有窮，確定，可行、輸入、輸出。
好演算法：正確、可讀、健壯、效率儲存
線性表順插n/2,刪(n-1)/2時ｏ(n)，查詢時間為ｏ(1)，隨機訪問；
鏈移動0時ｏ(1) ，查詢時間ｏ(n)，順序訪問。
插s = (lnode *)malloc(sizeof(lnode));s->data = x;//新結點
串模式匹配：子串的定位操作
陣列廣義表順序儲存陣列鏈式儲存廣義表
二叉樹終端結點數n0，度為2結點數為n2，則n0＝n2＋1。
2i>n，則i為葉結，無左孩子；否則，其左孩子是結點2i。
1000個結點，全部葉子數500個。度為2＝葉子數－1=499個。
孩子兄弟表示法：指左孩子，左孩指兄弟和左孩子
圖 路徑長度路徑上邊或弧的數目。
鄰接矩陣空o(n2) 時o(n2+e*n)
鄰接表(鄰接多重表) 空o(n+2e)或o(n+e) 時o(n+e*n)
十字鍊錶時o(n+e*n)
prim 時n2 克魯斯時elge dj n3
查詢順序從後向前成功(n+1)/2;不成功3/4(n+1);比n+1
折半low,mid,high,比|log2n|+1；(n+1)/nlog2(n+1) -1 順存有序表
分塊（索引）lb+lw=1/2(n/s+s)+1 分塊有序表
二叉排序樹：邊找邊查，左大右小等，2(1+1/n)ln n
二叉平衡樹：log2n 相差不大於1。
二叉排序刪p（葉子刪，或左或右移至雙親子，左移為雙親左，右到低端右，或者s替p，s為p左子樹右）
二叉平衡樹：ll,rr,lr,
雜湊表：雜湊表查詢——解決衝突：開位址和鏈位址法
開放定址法為產生衝突的位址 h(key) 求得乙個位址序列： h0, h1, h2, …, hs 1≤s≤m-1，hi = ( h(key) + di ) mod m，其中： i=1, 2, …, s
h(key)為雜湊函式;m為雜湊表長;di為增量序列；
排序法最好平均時間最壞輔助儲存穩定性
簡單 o(n) o(n2) o(n2o(1
快速 nlog2n nlog2n n2log2n
堆 nlog2n nlog2n nlog2n 1
歸併 nlog2n nlog2n nlog2n n
基數 d(n+rd) d(n+rd) d(n+rd) rd
簡單選擇n2 n2n21
直接插入nn2n21
折半插入nlog2n nlog2 n nlog2n 1
冒泡 n n2n21
希爾n2 < x < nlog2n
直接插入：第乙個有序，第二個一次插入。二路插入：由兩邊向中間
希爾排序：縮小增量，最後增量為1。快速排序：第一趟排，左小右大。
簡單選擇排序：第乙個後比，找到比自己小的，兩個交換位置
競標賽：兩兩比較得到最值
堆排序：從下到上，從右向左，依次調整雙親和葉子變成大根堆，然後將第乙個數調到最後，再次將其調整為大根堆，再把它後調，在剛之前。
歸併：22排序，44排序基數：不同關鍵字，個十百位。
葉子計數
void countleaf (bitree t, int &count) }
int countleaf (bitree t) }
int count (bitree t)}
深度廣度遍歷圖
void dfs1(a, n, v) // dfs1
bfs1(list, n, v)
p=nextarc(p); } }return } // bfs1
快速轉置陣列
status fasttran**atrix ( t**atrix m, t**atrix &t) }return ok; }
線性表順序表lc=la∪lb
void mergelist(list la，list lb，list &lc)
else } while(i<=la_len)while(j<=lb_len)}
資料結構整理
else 二 二叉樹 1.二叉樹的前中後層4種遍歷 前序 template void bitree preorder binode root 中序 2 1 3 後序 2 3 1 層序 了解即可 template void bitree levelorder binode root 2.二叉樹的應用 ...
資料結構整理
第四章串 1 下面關於串的的敘述中，哪個是不正確的？a 串是字元的有限序列 b 空串是由空格構成的串 c 模式匹配是串的一種重要運算 d 串既可以採用順序儲存，也可以採用鏈式儲存 2串是一種特殊的線性表，下面哪個敘述體現這種特殊性？a.資料元素是乙個字元 b.可以順序儲存 c.資料元素可以是多個字元...
資料結構整理
20 用鄰接表表示圖進行廣度優先遍歷時，通常採用 來實現演算法。21 用鄰接表表示圖進行深度優先遍歷時，通常採用 來實現演算法。22 在乙個圖中，所有頂點的度數之和等於所有邊數和的 倍 23 在乙個有向圖中，所有頂點的入度之和等於所有頂點的出度之和的 倍。24 乙個有n個頂點的無向圖最多有 條邊 2...