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