數(shù)組

????一維數(shù)組a[n]? a[i]的存儲(chǔ)地址為a+i*len

? ? 二維數(shù)組a[m][n]? a[i][j]的存儲(chǔ)地址按行存儲(chǔ)為：a+(i*n+j)*len? ??

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?a[i][j]的存儲(chǔ)地址按列存儲(chǔ)為：a+(j*m+i)*len? ??

稀疏矩陣

????在考試中可以使用代入法來快速選擇

數(shù)據(jù)結(jié)構(gòu)的定義

? ? 數(shù)據(jù)結(jié)構(gòu)的概念：

? ? 從邏輯上可以分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)，非線性結(jié)構(gòu)可以分為樹和圖

? ? 樹和圖? 樹不包含閉環(huán)

線性表的定義

? ? 線性表可以分為順序表和鏈表

? ? 順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)對(duì)比

? ? 隊(duì)列和棧

? ? ? ? 隊(duì)列的基本原則是先進(jìn)先出

? ? ? ? 棧則是先進(jìn)后出

廣義表

????廣義表是由n個(gè)表元素組成的有限序列采缚，是線性表的推廣针炉，通常用遞歸的形式進(jìn)行定義記作

? ? 注：LS是表名，?是表元素扳抽，它可以是表篡帕，也可以是數(shù)據(jù)元素，其中n是廣義表的長度贸呢，n=0的廣義表為空表?

? ? 基本運(yùn)算：取表頭head(Ls)和取表尾tail(Ls)

樹與二叉樹

? ? 基本概念

? ? ????節(jié)點(diǎn)的度指當(dāng)前節(jié)點(diǎn)擁有子節(jié)點(diǎn)的數(shù)量

? ? ????樹的度表示所有節(jié)點(diǎn)含有最高的子元素的節(jié)點(diǎn)

? ? ????葉子節(jié)點(diǎn)表示最后一層節(jié)點(diǎn)（沒有子節(jié)點(diǎn)）

????????分支節(jié)點(diǎn)?含有分支的節(jié)點(diǎn)

????????內(nèi)部節(jié)點(diǎn)非葉子節(jié)點(diǎn)和非根節(jié)點(diǎn)

? ? ????子節(jié)點(diǎn)和父節(jié)點(diǎn)是一個(gè)相對(duì)的概念

? ? ????兄弟節(jié)點(diǎn)屬于用一個(gè)父節(jié)點(diǎn)

? ? 滿二叉樹與完全二叉樹

? ? ? ? 滿二叉樹指整棵樹沒有缺失的節(jié)點(diǎn)

? ? ? ? 完全二叉樹是指除最底一層镰烧，上面的層次都是滿的

? ? 二叉樹遍歷

? ? ? ? 層次遍歷：按二叉樹的層次依次遍歷

? ? ? ? 前序遍歷：先訪問根節(jié)點(diǎn)再訪問左右節(jié)點(diǎn)

? ? ? ? 中序遍歷：先訪問左子樹然后訪問根節(jié)點(diǎn)最后訪問右節(jié)點(diǎn)

? ? ? ? 后序遍歷：先訪問左子樹在訪問右子樹最后訪問根節(jié)點(diǎn)

? ? 查找二叉樹

? ? ? ? 樹的左節(jié)點(diǎn)小于根節(jié)點(diǎn)，右節(jié)點(diǎn)大于根節(jié)點(diǎn)這種樹成為查找(排序)二叉樹?方便查詢比對(duì)

? ? 最優(yōu)二叉樹(哈夫曼樹)

? ? ? ? 用于哈夫曼編碼楞陷，能夠讓原始信息的編碼長度變得更短

圖

? ??基本概念? ??

? ? 圖的存儲(chǔ)-鄰接矩陣

? ? ? ? 用一個(gè)n階方陣來存放圖中個(gè)結(jié)點(diǎn)的關(guān)聯(lián)信息其矩陣元素定義為

? ? 圖的存儲(chǔ)-鄰接表

? ? ? ? 首先把每隔定點(diǎn)的鄰接頂點(diǎn)用鏈表示出來怔鳖，然后用一個(gè)一維數(shù)組來順序存儲(chǔ)上面每個(gè)鏈表的頭指針

? ? 圖的遍歷

? ? 拓?fù)渑判?/b>

? ? ? ? 我們把用有向邊表示活動(dòng)之間開始的先后關(guān)系，這種有向圖稱為用頂點(diǎn)表示活動(dòng)網(wǎng)絡(luò)

算法基礎(chǔ)

????算法的特性

? ? 算法的復(fù)雜度

? ? ? ? 時(shí)間復(fù)雜度是指程序運(yùn)行從開始到結(jié)束所需要的時(shí)間固蛾。通常分析時(shí)間復(fù)雜度的方法是從算法中選取一種對(duì)于所研究問題來說是基本運(yùn)算的操作结执，以該操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。一般來說魏铅，算法中原操作重復(fù)執(zhí)行的次數(shù)是規(guī)模n的某個(gè)函數(shù)T(n)昌犹。由于許多情況下要精確計(jì)算T(n)是困難的，因此引入的漸進(jìn)時(shí)間復(fù)雜度在數(shù)量上估計(jì)一個(gè)算法的執(zhí)行時(shí)間览芳。定義如下

? ? ? ? 如果存在兩個(gè)常數(shù)c和m斜姥，對(duì)于所有的n，當(dāng)nm時(shí)有則有沧竟。也就是說铸敏，隨著n的增大，f(n)漸進(jìn)地不大于g(n)

? ? ? ? 空間復(fù)雜度是指對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的度量悟泵。一個(gè)算法的空間復(fù)雜度只考慮在運(yùn)行過程中為局部變量分配的存儲(chǔ)空間的大小

? ? 順序查找

? ? ? ? 順序查找的思想：將查找的關(guān)鍵字為key的元素從頭到尾與表中元素進(jìn)行比較杈笔，如果中間存在關(guān)鍵字為key的元素，則返回成功糕非，否則蒙具，則查找失敗

? ? ? ? 查找成功時(shí)，順序查找的平均查找長度為（等概率情況下）：

? ??????????

? ? 二分查找法（需要先將表變成有序表）

? ? ? ? 二分查找法的基本意思：（設(shè)R[low,...,high]是當(dāng)前的查找區(qū)）

? ? ? ? ? ? (1)確定該區(qū)間的中點(diǎn)位置：mid=[(low+high)/2];

????????????(2)將待查的k值與R[mid].key比較朽肥，若相等禁筏，則查找成功餅返回此位置，否則需確定新的查找區(qū)間衡招，繼續(xù)二分查找篱昔，具體方法如下

????????????????·若R[mid].key>k,則由表的有序性可知R[mid,...,n].key均大于k，因此若表中存在關(guān)鍵字等于k的結(jié)點(diǎn)，則該結(jié)點(diǎn)必定是在位置mid左邊的子表R[low,...,mid-1]中州刽。因此空执，新查找區(qū)間是左子表R[low,...,high]，其中high=mid-1

? ??????????????·若R[mid].key<k,則要查找的k必在mid的右子表R[mid+1,...,high]中穗椅，則新的查找區(qū)間是右子表R[low,...,high],其中l(wèi)ow=mid+1

? ? ? ? ? ? ? ? ·若[mid].key=k辨绊，則查找成功，算法結(jié)束

? ? ? ? ? ? (3)下一次查找是針對(duì)新的查找區(qū)間進(jìn)行房待，重復(fù)步驟(1)和(2).

? ? ? ? ? ? (4)在查找過程中,low逐步增加,而high逐步減少邢羔。如果high<low，則查找失敗桑孩，算法結(jié)束

? ? 散列表

? ? ? ? 散列表查找的基本思想是：已知關(guān)鍵字集合U拜鹤，最大關(guān)鍵字為m，設(shè)計(jì)一個(gè)函數(shù)Hash流椒，它以關(guān)鍵字為自變量敏簿，關(guān)鍵字的存儲(chǔ)地址為因變量，將關(guān)鍵字映射到一個(gè)有限的宣虾、地址連續(xù)的區(qū)間T[0...n-1](n<<m)中惯裕，這個(gè)區(qū)間就稱為散列表，散列查找使用的轉(zhuǎn)換函數(shù)稱為散列函數(shù)

? ? 排序

? ? ? ? 直接插入排序：當(dāng)插入第i個(gè)記錄時(shí)绣硝，均已排好序蜻势，因此，將第i個(gè)記錄依次與進(jìn)行比較鹉胖，找到合適的位置插入握玛。它簡(jiǎn)單明了，但速度很慢

? ? ? ? 希爾排序：先取一個(gè)小于n的整數(shù)作為第一個(gè)增量甫菠，把文件的全部記錄分成個(gè)組挠铲。所有距離為的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序寂诱，然后拂苹，取第二個(gè)增量重復(fù)上述的分組和排序，直至所取的增量,即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹固等鳎摲椒▽?shí)際上是一種分組插入方法瓢棒。

? ? ? ? 直接選擇排序：首先在所有記錄中選出排序碼最小的記錄，把它與第1個(gè)記錄交換丘喻，然后在其余的記錄內(nèi)選出排序碼最小的記錄音羞，與第2個(gè)記錄交換......依次類推，知道所有記錄排完為止

????????堆排序：

????????????先將序列建立堆仓犬，然后輸出堆頂元素，再將剩下的序列建立堆舍肠，然后再輸出堆頂元素搀继，依次類推窘面，知道所有元素均輸出為止，此時(shí)元素輸出的序列就是一個(gè)有序序列

? ? ? ? 冒泡排序：通過相鄰元素之間的比較和交換叽躯，將排序碼較小的元素逐漸從底部移向頂部

? ??????快速排序：采用的是分治法财边，基本思想是將原問題分解成若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問題像素的子問題。通過遞歸解決這些子問題点骑，然后再將這些子問題的解組合成原問題的解

? ? ? ? ? ? 快速排序通常包括兩個(gè)步驟：

? ? ? ? ? ? ? ? 第一步酣难，在待排序的n個(gè)記錄中任取一個(gè)記錄，以該記錄的排序碼為準(zhǔn)黑滴，將所有記錄都分成兩組憨募，第1組都小于該數(shù)，第2組都大于該數(shù)

? ? ? ? ? ? ? ? 第二步袁辈，采用相當(dāng)?shù)姆椒▽?duì)左菜谣、右兩組分別進(jìn)行排序，知道所有記錄都排到相應(yīng)的位置為止

? ? ? ? 歸并排序法

? ? ? ? 基數(shù)排序：借助多關(guān)鍵字排序的思想對(duì)單邏輯關(guān)鍵字進(jìn)行排序的方法晚缩∥膊玻基數(shù)排序不是基于關(guān)鍵字比較的排序方法，它適用于元素很多而關(guān)鍵字較少的序列荞彼，基數(shù)的選擇和關(guān)鍵字的分解是根據(jù)關(guān)鍵字的類型來決定的

? ? ? ? 排序?qū)Ρ?/b>