一.算法的基本概念
計(jì)算機(jī)解題的過(guò)程實(shí)際上是在實(shí)施某種算法，這種算法稱為計(jì)算機(jī)算法。
1.算法的基本特征：可行性，確定性，有窮性，擁有足夠的情報(bào)。
2.算法的基本要素：算法中對(duì)數(shù)據(jù)的運(yùn)算和操作、算法的控制結(jié)構(gòu)。
3.算法設(shè)計(jì)的基本方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法。
4.算法設(shè)計(jì)的要求：正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求
二.算法的復(fù)雜度
1.算法的時(shí)間復(fù)雜度：指執(zhí)行算法所需要的計(jì)算工作量
2.算法的空間復(fù)雜度：執(zhí)行這個(gè)算法所需要的內(nèi)存空間
三.數(shù)據(jù)結(jié)構(gòu)的定義
1.數(shù)據(jù)的邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間的關(guān)系的數(shù)據(jù)元素集合的表示。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、線形結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)四種。
2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間種的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。
四.數(shù)據(jù)結(jié)構(gòu)的圖形表示：
在數(shù)據(jù)結(jié)構(gòu)中，沒(méi)有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒(méi)有后件的結(jié)點(diǎn)成為終端結(jié)點(diǎn)。插入和刪除是對(duì)數(shù)據(jù)結(jié)構(gòu)的兩種基本運(yùn)算。還有查找、分類、合并、分解、復(fù)制和修改等。
五.線性結(jié)構(gòu)和非線性結(jié)構(gòu)
根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。
線性結(jié)構(gòu)：非空數(shù)據(jù)結(jié)構(gòu)滿足：有且只有一個(gè)根結(jié)點(diǎn)；每個(gè)結(jié)點(diǎn)最多有一個(gè)前件，最多只有一個(gè)后件。非線性結(jié)構(gòu)：如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，稱之為非線性結(jié)構(gòu)。
常見(jiàn)的線性結(jié)構(gòu)：線性表、棧、隊(duì)列
六.線性表的定義
線性表是n 個(gè)元素構(gòu)成的有限序列（A1，A2，A3……）。表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)以外，有且只有一個(gè)前件。除了最后一個(gè)以外有且只有一個(gè)后件。即線性表是一個(gè)空表，或可以表示為（a1,a2,……an）, 其中ai(I=1,2,……n)是屬于數(shù)據(jù)對(duì)象的元素，通常也稱其為線性表中的一個(gè)結(jié)點(diǎn)。
非空線性表有如下一些特征：
（1）有且只有一個(gè)根結(jié)點(diǎn)a1,它無(wú)前件；
（2）有且只有一個(gè)終端結(jié)點(diǎn)an，它無(wú)后件；
（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長(zhǎng)度。當(dāng)n=0時(shí)稱為空表。
七.線性表的順序存儲(chǔ)結(jié)構(gòu)
線性表的順序表指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。
線性表的順序存儲(chǔ)結(jié)構(gòu)具備如下兩個(gè)基本特征：
1.線性表中的所有元素所占的存儲(chǔ)空間是連續(xù)的；
2.線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。
即線性表邏輯上相鄰、物理也相鄰，則已知第一個(gè)元素首地址和每個(gè)元素所占字節(jié)數(shù)，則可求出任一個(gè)元素首地址。
假設(shè)線性表的每個(gè)元素需占用K個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai)之間滿足下列關(guān)系:
LOC(ai+1)=LOC(ai)+K
LOC(ai)=LOC(a1)+(i-1)*K ①
其中，LOC(a1)是線性表的第一個(gè)數(shù)據(jù)元素a1的存儲(chǔ)位置，通常稱做線性表的起始位置或基地址。
因?yàn)樵陧樞虼鎯?chǔ)結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素地址可以通過(guò)公式①計(jì)算得到，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。
在線性表的順序存儲(chǔ)結(jié)構(gòu)下，可以對(duì)線性表做以下運(yùn)算：
插入、刪除、查找、排序、分解、合并、復(fù)制、逆轉(zhuǎn)來(lái)源：www.examda.com
八.順序表的插入運(yùn)算
線性表的插入運(yùn)算是指在表的第I個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x，使長(zhǎng)度為n的線性表（a1,a2 …ai…an）變成長(zhǎng)度為n+1的線性表(a1,a2…x,ai…an).
該算法的時(shí)間主要花費(fèi)在循環(huán)的結(jié)點(diǎn)后移語(yǔ)句上，執(zhí)行次數(shù)是n-I+1。
當(dāng)I=n+1,情況，時(shí)間復(fù)雜度o(1) 當(dāng)I=1, 最壞情況，時(shí)間復(fù)雜度o(n)
算法的平均時(shí)間復(fù)雜度為o(n)
九.順序表的刪除運(yùn)算
線性表的刪除運(yùn)算是指在表的第I個(gè)位置上，刪除一個(gè)新結(jié)點(diǎn)x，使長(zhǎng)度為n的線性表（a1,a2 …ai…an）變成長(zhǎng)度為n-1的線性表(a1,a2…ai-1,ai+1…an).
當(dāng)I=n,時(shí)間復(fù)雜度o(1),當(dāng)I=1,時(shí)間復(fù)雜度o(n) ,平均時(shí)間復(fù)雜度為o(n)
十.棧及其基本運(yùn)算
1.什么是棧？ 棧實(shí)際上也是一個(gè)線性表，只不過(guò)是一種特殊的線性表。棧是只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除這一端為棧頂（），另一端為棧底（BOTTOM）。當(dāng)表中沒(méi)有元素時(shí)稱為空棧。棧頂元素總是后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。
假設(shè)棧S=（a1,a2,a3,……an），則a1 稱為棧底元素，an稱為棧頂元素。棧中元素按a1,a2,a3……an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)該是棧頂元素。即后進(jìn)先出。
2.棧的順序存儲(chǔ)及其運(yùn)算
用S（1：M）作為棧的順序存儲(chǔ)空間。M為棧的容量。
棧的基本運(yùn)算有三種：入棧、退棧與讀棧頂元素。
入棧運(yùn)算：在棧頂位置插入一個(gè)新元素。
首先將棧頂指針進(jìn)一（+1），然后將新元素插入到棧頂指針指向的位置。
退棧運(yùn)算：指取出棧頂元素并賦給一個(gè)指定的變量。
首先將棧頂元素賦給一個(gè)指定的變量，然后將棧頂指針退一（-1）
讀棧頂元素：將棧頂元素賦給一個(gè)指定的變量。棧頂指針不會(huì)改變。
計(jì)算機(jī)解題的過(guò)程實(shí)際上是在實(shí)施某種算法，這種算法稱為計(jì)算機(jī)算法。
1.算法的基本特征：可行性，確定性，有窮性，擁有足夠的情報(bào)。
2.算法的基本要素：算法中對(duì)數(shù)據(jù)的運(yùn)算和操作、算法的控制結(jié)構(gòu)。
3.算法設(shè)計(jì)的基本方法：列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法。
4.算法設(shè)計(jì)的要求：正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求
二.算法的復(fù)雜度
1.算法的時(shí)間復(fù)雜度：指執(zhí)行算法所需要的計(jì)算工作量
2.算法的空間復(fù)雜度：執(zhí)行這個(gè)算法所需要的內(nèi)存空間
三.數(shù)據(jù)結(jié)構(gòu)的定義
1.數(shù)據(jù)的邏輯結(jié)構(gòu)：反映數(shù)據(jù)元素之間的關(guān)系的數(shù)據(jù)元素集合的表示。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、線形結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)四種。
2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間種的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。
四.數(shù)據(jù)結(jié)構(gòu)的圖形表示：
在數(shù)據(jù)結(jié)構(gòu)中，沒(méi)有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒(méi)有后件的結(jié)點(diǎn)成為終端結(jié)點(diǎn)。插入和刪除是對(duì)數(shù)據(jù)結(jié)構(gòu)的兩種基本運(yùn)算。還有查找、分類、合并、分解、復(fù)制和修改等。
五.線性結(jié)構(gòu)和非線性結(jié)構(gòu)
根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。
線性結(jié)構(gòu)：非空數(shù)據(jù)結(jié)構(gòu)滿足：有且只有一個(gè)根結(jié)點(diǎn)；每個(gè)結(jié)點(diǎn)最多有一個(gè)前件，最多只有一個(gè)后件。非線性結(jié)構(gòu)：如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，稱之為非線性結(jié)構(gòu)。
常見(jiàn)的線性結(jié)構(gòu)：線性表、棧、隊(duì)列
六.線性表的定義
線性表是n 個(gè)元素構(gòu)成的有限序列（A1，A2，A3……）。表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)以外，有且只有一個(gè)前件。除了最后一個(gè)以外有且只有一個(gè)后件。即線性表是一個(gè)空表，或可以表示為（a1,a2,……an）, 其中ai(I=1,2,……n)是屬于數(shù)據(jù)對(duì)象的元素，通常也稱其為線性表中的一個(gè)結(jié)點(diǎn)。
非空線性表有如下一些特征：
（1）有且只有一個(gè)根結(jié)點(diǎn)a1,它無(wú)前件；
（2）有且只有一個(gè)終端結(jié)點(diǎn)an，它無(wú)后件；
（3）除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長(zhǎng)度。當(dāng)n=0時(shí)稱為空表。
七.線性表的順序存儲(chǔ)結(jié)構(gòu)
線性表的順序表指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。
線性表的順序存儲(chǔ)結(jié)構(gòu)具備如下兩個(gè)基本特征：
1.線性表中的所有元素所占的存儲(chǔ)空間是連續(xù)的；
2.線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。
即線性表邏輯上相鄰、物理也相鄰，則已知第一個(gè)元素首地址和每個(gè)元素所占字節(jié)數(shù)，則可求出任一個(gè)元素首地址。
假設(shè)線性表的每個(gè)元素需占用K個(gè)存儲(chǔ)單元，并以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai)之間滿足下列關(guān)系:
LOC(ai+1)=LOC(ai)+K
LOC(ai)=LOC(a1)+(i-1)*K ①
其中，LOC(a1)是線性表的第一個(gè)數(shù)據(jù)元素a1的存儲(chǔ)位置，通常稱做線性表的起始位置或基地址。
因?yàn)樵陧樞虼鎯?chǔ)結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素地址可以通過(guò)公式①計(jì)算得到，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。
在線性表的順序存儲(chǔ)結(jié)構(gòu)下，可以對(duì)線性表做以下運(yùn)算：
插入、刪除、查找、排序、分解、合并、復(fù)制、逆轉(zhuǎn)來(lái)源：www.examda.com
八.順序表的插入運(yùn)算
線性表的插入運(yùn)算是指在表的第I個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x，使長(zhǎng)度為n的線性表（a1,a2 …ai…an）變成長(zhǎng)度為n+1的線性表(a1,a2…x,ai…an).
該算法的時(shí)間主要花費(fèi)在循環(huán)的結(jié)點(diǎn)后移語(yǔ)句上，執(zhí)行次數(shù)是n-I+1。
當(dāng)I=n+1,情況，時(shí)間復(fù)雜度o(1) 當(dāng)I=1, 最壞情況，時(shí)間復(fù)雜度o(n)
算法的平均時(shí)間復(fù)雜度為o(n)
九.順序表的刪除運(yùn)算
線性表的刪除運(yùn)算是指在表的第I個(gè)位置上，刪除一個(gè)新結(jié)點(diǎn)x，使長(zhǎng)度為n的線性表（a1,a2 …ai…an）變成長(zhǎng)度為n-1的線性表(a1,a2…ai-1,ai+1…an).
當(dāng)I=n,時(shí)間復(fù)雜度o(1),當(dāng)I=1,時(shí)間復(fù)雜度o(n) ,平均時(shí)間復(fù)雜度為o(n)
十.棧及其基本運(yùn)算
1.什么是棧？ 棧實(shí)際上也是一個(gè)線性表，只不過(guò)是一種特殊的線性表。棧是只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除這一端為棧頂（），另一端為棧底（BOTTOM）。當(dāng)表中沒(méi)有元素時(shí)稱為空棧。棧頂元素總是后被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最后才能被刪除的元素。
假設(shè)棧S=（a1,a2,a3,……an），則a1 稱為棧底元素，an稱為棧頂元素。棧中元素按a1,a2,a3……an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)該是棧頂元素。即后進(jìn)先出。
2.棧的順序存儲(chǔ)及其運(yùn)算
用S（1：M）作為棧的順序存儲(chǔ)空間。M為棧的容量。
棧的基本運(yùn)算有三種：入棧、退棧與讀棧頂元素。
入棧運(yùn)算：在棧頂位置插入一個(gè)新元素。
首先將棧頂指針進(jìn)一（+1），然后將新元素插入到棧頂指針指向的位置。
退棧運(yùn)算：指取出棧頂元素并賦給一個(gè)指定的變量。
首先將棧頂元素賦給一個(gè)指定的變量，然后將棧頂指針退一（-1）
讀棧頂元素：將棧頂元素賦給一個(gè)指定的變量。棧頂指針不會(huì)改變。