c語(yǔ)言公共基礎(chǔ) 知識(shí)

《c語(yǔ)言公共基礎(chǔ) 知識(shí)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、公共基礎(chǔ)知識(shí)總結(jié)第一章數(shù)據(jù)結(jié)構(gòu)與算法1.1算法算法：是指解題方案的準(zhǔn)確而完整的描述。算法復(fù)雜度：算法時(shí)間復(fù)雜度和算法空間復(fù)雜度。兩個(gè)之間沒(méi)有聯(lián)系的。算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。1.2數(shù)據(jù)結(jié)構(gòu)的基本基本概念（1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；線性結(jié)構(gòu)條件：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。非線性結(jié)構(gòu)：不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。1．3線性表及其順序存儲(chǔ)結(jié)構(gòu)

2、線性表是由一組數(shù)據(jù)元素構(gòu)成，數(shù)據(jù)元素的位置只取決于自己的序號(hào)，元素之間的相對(duì)位置是線性的。線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：（1）線性表中所有元素的所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。1．4棧和隊(duì)列棧是限定在一端進(jìn)行插入與刪除的線性表。1、先進(jìn)后出FILO;1、支持子程序調(diào)用;2、具有記憶功能；3、可以不用順序存放數(shù)據(jù)；4、只能夠在top首部進(jìn)行操作，bottom是絕對(duì)不動(dòng)的；5、棧的存放數(shù)據(jù)的個(gè)數(shù)為num=（bottom–top）+1；隊(duì)列是指允許在一端（隊(duì)尾）進(jìn)入插入，而在另一端（隊(duì)頭）進(jìn)行刪除的線性表。1

3、、Rear指針指向隊(duì)尾，front指針指向隊(duì)頭。3、先進(jìn)先出FIFO,或者是后進(jìn)后出LILO2、循環(huán)隊(duì)列里面的個(gè)數(shù)計(jì)算方法：A、rear>front的時(shí)候，num=rear–front；B、rear

4、度。樹(shù)的最大層次稱為樹(shù)的深度。二叉樹(shù)的特點(diǎn)：（1）非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。二叉樹(shù)的基本性質(zhì)：必考的題目（1）在二叉樹(shù)的第k層上，最多有2k-1(k≥1)個(gè)結(jié)點(diǎn)；（2）深度為m的二叉樹(shù)最多有2m-1個(gè)結(jié)點(diǎn)；（3）度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)；（4）二叉樹(shù)中n=n0+n1+n2滿二叉樹(shù)是指除最后一層外，每一層上的所有結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，則k層上有2k-1個(gè)結(jié)點(diǎn)深度為m的滿二叉樹(shù)有2m-1個(gè)結(jié)點(diǎn)。完全二叉樹(shù)是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)

5、。二叉樹(shù)存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，對(duì)于滿二叉樹(shù)與完全二叉樹(shù)可以按層序進(jìn)行順序存儲(chǔ)。二叉樹(shù)的遍歷：（一般畫(huà)個(gè)圖要你把順序?qū)懗鰜?lái)）（1）前序遍歷（DLR），根左右（2）中序遍歷（LDR），左根右（3）后序遍歷（LRD）左右根1．7查找技術(shù)順序查找的使用情況：長(zhǎng)度為n的線性表，找出一個(gè)數(shù)據(jù)，最差的情況為比較n次。長(zhǎng)度為n的線性表，找出一個(gè)最大數(shù)據(jù)，最差的情況為比較n-1次。二分法查找只適用于順序存儲(chǔ)的有序表，二分查找：對(duì)于長(zhǎng)度為n的有序線性表，最壞情況只需比較log2n次。1．8排序技術(shù)排序是指將一個(gè)無(wú)序序列整理成按值非遞減順序排列的有序序列。交換類排序法：（1）冒泡排序

6、法，需要比較的次數(shù)為n(n-1)/2；（2）快速排序法，需要比較的次數(shù)為n(n-1)/2；。插入類排序法：（1）簡(jiǎn)單插入排序法，最壞情況需要n(n-1)/2次比較；（2）希爾排序法，最壞情況需要O(n1.5)次比較。選擇類排序法：（1）簡(jiǎn)單選擇排序法,最壞情況需要n(n-1)/2次比較；（2）堆排序法，最壞情況需要O(nlog2n)次比較。第二章程序設(shè)計(jì)基礎(chǔ)2．1程序設(shè)計(jì)設(shè)計(jì)方法和風(fēng)格注釋分序言性注釋和功能性注釋，語(yǔ)句結(jié)構(gòu)清晰第一、效率第二。不要弄反了。程序設(shè)計(jì)方法有兩種，結(jié)構(gòu)化程序設(shè)計(jì)和面向?qū)ο蟪绦蛟O(shè)計(jì)。2．2結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)方法的四條原則是：考試重點(diǎn)

7、都要背下來(lái)1.自頂向下；2.逐步求精；3.模塊化；4.限制使用goto語(yǔ)句。注意，這四個(gè)特點(diǎn)中，最重要的是模塊化。結(jié)構(gòu)化程序的基本結(jié)構(gòu)和特點(diǎn)：順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)2．3面向?qū)ο蟮某绦蛟O(shè)計(jì)面向?qū)ο蟮某绦蛟O(shè)計(jì)：以對(duì)象為核心。面向?qū)ο缶邆淠男┗靖拍睿簩?duì)象、類和實(shí)例、消息、繼承、多態(tài)性、對(duì)象是面向?qū)ο蠓椒ㄖ凶罨镜母拍睿瑢?duì)象是實(shí)體的抽象。面向?qū)ο蟮某绦蛟O(shè)計(jì)方法中的對(duì)象是系統(tǒng)中用來(lái)描述客觀事物的一個(gè)實(shí)體，是構(gòu)成系統(tǒng)的一個(gè)基本單位，由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成。屬性即對(duì)象所包含的信息，操作描述了對(duì)象執(zhí)行的功能，操作也稱為方法或服務(wù)。對(duì)象的基本