1. 鍊錶合併（兩個非降序迴圈鍊錶的合併）；
（1）首先根據第乙個元素判斷哪個鍊錶作為起始，及確定表頭指標，將首元素較小的鍊錶的頭結點存入head，另乙個鍊錶的頭結點存入_head，並使指標p和r指向head的next，q指向_head 的next；
（2）初始化時，p=p->next；如果p中的資料大於q中的資料，那麼將q鏈結在r後，r與p均向後移，否則，將p連線在r之後，然後r與q同時向後移動，重複這個過程直到p或q中有乙個指標已經指向其原表頭為止。
（3）當有乙個指標指向其頭指標時，另一指標要繼續進行遍歷，重新構成迴圈鍊錶。
2.廣義表的建立和遍歷
（1）定義乙個結構體，用於存放廣義表的元素，有兩種節點
如果tag=1，為表節點，共用體中存放頭指標h，如果tag=0，為原子節點，共用體中存放元素。
（2）廣義表都是以「（」開始的，所以首先開闢乙個節點，將其標誌位置1，使head和pre指向此節點；
讀入字元，並作出判斷
「（」：開闢乙個節點p，用於存放子表元素，將pre指標的tag置1，將p鏈到pre的h中，然後將pre指標入棧，pre指標指向p的位置；
「，」：說明有兄弟關係的節點存在，開闢新節點p，將p鏈在pre的r位置，將pre指向p的位置；
「）」：將棧頂元素賦值給pre，然後出棧；
「a—z」：將元素存入pre的共用體中，然後將tag置0。
（3）廣義表的遍歷。廣義表的遍歷可以按深度訪問遍歷，當遇到子表時，將子表的尾指標入棧，然後繼續沿子表頭指標進行遍歷 ；如果當前節點為原子節點，那麼直接輸出節點中元素，繼續沿尾指標方向遍歷，直到指向空節點，然後出棧，繼續上述過程，直至棧空。
3．二叉樹的建立和遍歷
依次讀入字元，然後判斷
「（」：再讀入乙個字元，看左子樹是不是空，如果讀入的下乙個字元不是「，」說明左子樹不空，那麼開闢乙個新節點，將讀入的元素存入新節點中，如果是根節點，那麼將其入棧，並將head指向它，如果不是，將新節點鏈在棧頂指標的左孩子，將新節點指標入棧。如果讀入的字元是「，」，說明棧頂指標沒有左孩子，將其左孩子指標置空。
「）」：出棧；
「，」出棧；
「a-z」：開闢新節點，將元素存入新節點，並將其鏈在棧頂元素右孩子指標，將新節點指標入棧。
先序遍歷二叉樹：
將根指標入棧；
當棧為空的時候，遍歷結束，否則彈出棧頂元素進行遍歷；
彈出棧頂元素到s中；
當前指標s不為空時，沿左子樹進行遍歷；
輸出當前節點元素值
當前指標所指節點的右指標進棧
沿當前指標s所指節點的左子樹進行遍歷
中序遍歷二叉樹
將根指標入棧；
當棧為空的時候，結束遍歷，否則繼續進行；
令s指向當前節點，沿s所指左子樹遍歷；
當s不空時，將s入棧；
s為空時，輸出棧頂元素，s指向棧頂元素右孩子繼續遍歷，出棧；、
4.樹、森林到二叉樹的轉換
（1）將森林中各樹的根用線連起來；
（2）在樹中將所有兄弟節點之間加一連線；
（3）對每個節點，除了保留與其左兒子節點的連線外，去掉該節點與其他兒子節點的連線；
（4）以根為軸，平面向下順時針方向旋轉一定角度。
注意，在樹對應的二叉樹中，乙個節點的左孩子是它在原樹中的第1個孩子，而右孩子則是她在原樹中位於其右側的兄弟。
5.線索二叉樹
上圖為線索二叉樹的結構體，left和right是指標，ltag和rtag，如果為0，則說明left（right）域是指向其左（右）兒子的節點指標，為1，說明left（right）域是指向其直接前驅（後繼）的左（右）線索；
（1） 建立頭節點；
（2） 二叉樹如果為空，則頭節點左指標回指；
（3） 否則，中序遍歷二叉樹並進行線索化；
使指標pre指向剛訪問過的節點，p指向當前節點，如果當前訪問的節點左指標為空，那沒ltag=1，並將pre鏈到p的left；如果pre的右指標為空，則將pre->rlag=1；
pre->right=p；
先序查詢線索二叉樹直接前驅和後繼
（1） 查詢前驅
（1） 如果ltag=0，說明當前節點有左孩子，如果當前節點是父親結點的左孩子，那麼其前驅為其父親節點；如果當前節點為父親節點的右孩子，那麼如果父親結點有左孩子，那其前驅就是父親節點左子樹的最右的葉子（或者說兄弟節點右優先的第乙個葉子節點），否則為父親節點；
（2） 如果ltag=1，說明沒有左孩子，其前驅就是左指標所指的節點。
（2） 查詢後繼
（1） 如果rtag=0，說明有右孩子，如果當前節點有左孩子，則直接後繼為其左孩子，否則為其右孩子；
（2） 如果rtag=1，說明其右指標指向其直接後繼。
中序查詢線索二叉樹直接前驅和後繼
（1） 查詢前驅
（1） 如果ltag=0，其直接前驅為其沿左子樹右鏈查詢，首個沒有右孩子的節點；
（2） 如果ltag=1，其直接前驅就是左指標所指節點；
（2） 查詢後繼
（1） 如果rtag=0，其直接後繼為其右子樹上沿左指標鏈向下查詢 ，首個沒有左孩子的節點便是其後繼；
（2） 如果rtag=1，其直接後繼為其右指標所指向的節點。
後序查詢線索二叉樹
（1） 查詢前驅
（1） 如果ltag=0，說明當前節點有左孩子，如果當前節點有右孩子，其直接前驅為其右孩子，否則為其左孩子；
（2） 如果ltag=1，說明當前節點沒左孩子，左指標所指節點即其直接前驅。
（2） 查詢後繼
（1） 如果rtag=0，說明當前節點有右孩子。若當前節點為其父節點的右孩子，後繼則為雙親節點；若當前節點為父節點的左孩子，並且當前節點有兄弟節點，當前節點雙親節點的右子樹上最左下的葉節點；若當前節點為父節點左孩子並且當前節點無兄弟節點，則直接後繼為雙親節點；
（2） 如果rtag=1，說明當前節點無右孩子，其直接後繼為右指標所指節點。
6.二叉排序樹
（1）開闢乙個節點，讀入乙個資料，將資料存入新節點；
（2）開闢新節點，將新讀入的資料存入節點；
（3）比較新的資料和頭節點中資料的大小關係，如果比頭節點中資料大，則與其右孩子節點資料比較，如果小於等於頭節點資料，則與其左孩子比較，直至左孩子為空或右孩子為空，如果新讀入資料大於當前節點中資料並且其右孩子空，則將其鏈在當前節點的右孩子指標，如果新讀入資料小於當前節點資料並且當前節點左孩子為空，則將新節點鏈在當前節點左指標；
（4）重複（2,）（3）；
7.哈夫曼樹（最優二叉樹），是指一組帶有權值的葉子節點，構造具有最小帶權路徑長度的二叉樹。
（1）由給定的n個權值構造n棵只有乙個葉子節點的二叉樹，從而得到乙個二叉樹集合f=；
（2）在f中選取權值最小和次小的兩棵二叉樹作為左右子樹構建一顆新的二叉樹，這棵二叉樹的權值為左右子樹權值之和；
（3）在集合f中刪除作為左右子樹的二叉樹，並將新生成的二叉樹加入到f中；
（4）重複（2）、（3），直到f中只剩下一棵二叉樹；
8.圖的相關定義
（1）完全圖：在乙個有n個頂點的無向圖中，若每個頂點到其他（n-1）個頂點都有一條邊，則圖中共有n（n-1）/2條邊，這種圖成為完全圖。
（2）頂點度，入度，初度，入度和初度是對有向圖來說的，度等於入度和初度之和。
（3）連通、連通圖和連通分量：無向圖中從頂點vi到頂點vj之間有路徑，則稱頂點是連通的。如果任意一對頂點都是連通的，則稱是連通圖。連通圖的每乙個極大連通子圖稱為連通分量。
（4）強連通圖和強連通分量：有向圖中，從頂點vi到vj和頂點vj到vi都有路徑，則稱這兩個頂點是強連通的。如果圖中任意一對都是強連通的，則稱此圖為強連通圖。
非強連通圖的每乙個極大強連通子圖稱作強連通分量。
9.圖的建立和遍歷（bfs和dfs）
（1）圖可以用鄰接矩陣和鄰接鍊錶儲存；
（2）bfs使用佇列，每訪問乙個頂點，就將其標誌的陣列中的值置1，說明已經訪問，然後將其有關係的頂點入隊；將已訪問的頂點出隊，繼續上述過程，直至隊空。
（3）dfs使用棧
訪問圖指定的頂點v
從v出發，訪問乙個與v鄰接的p所指的頂點，並將其壓入棧中；
從p所指的頂點出發，訪問與p所指頂點鄰接且未被訪問的頂點，以後從該頂點出發，重複上述過程，直到找不到未訪問的鄰接頂點為止；
出棧，即退回到尚有未被訪問的鄰接點的頂點，從該頂點出發，重複3,4過程，直到棧空。
10．生成樹
如果在乙個無向連通圖中，取它所有頂點和部分邊構成乙個子圖，若取的邊剛好將圖的所有頂點連通但又不形成迴路，我們就稱子圖是原圖的生成樹，其特點是：任意兩個頂點之間有且僅有一條路徑；如果再增加一條邊，就會出現迴路，如果減少乙個邊，就會變成非連通圖。
帶權連通圖中，生成樹權值總和最小的生成樹稱為最小生成樹。
11.最小生成樹的prim演算法
用鄰接矩陣儲存
（1） 從指定的開始節點v0開始，將v0加入頂點集u，再從與v0相關的節點中選取權值最小的邊加入邊集e，並將此邊的另乙個頂點加入u；
（2） 從與u中頂點相關聯的邊且不在集合e中的邊中選取權值最小的邊加入e，並且將此邊的另一頂點加入u；
（3） 重複（2）（3），直到所有頂點都加入到u。
12.最小生成樹kruskal演算法
（1）將n個頂點分成n個頂點集合，每個集合中有一頂點，t=（u，te）是圖g的最小生成樹，u是頂點集合，te是邊集，初始時，u為全集，te為空集；
（2）選取圖中邊的權值最小的邊加入到te，並將如果te邊的兩個頂點屬於不同的集合，則將兩個集合合併；
（3）從剩餘的邊中選取權值最小的邊，如果邊的兩個頂點不在同乙個集合，將此邊加入te，將兩個頂點所在的集合合併，否則捨棄此邊，從新選取邊；
（4）重複（2）——（4），直到所有頂點都在同一集合
13.最短路徑：從圖的某一頂點（源點）經圖的邊到達另一頂點（終點）的路徑不止一條，最短路徑是指兩點之間權值之和最小的路徑。
14．最短路徑的迪克斯特拉演算法
（1）將源點到其他各頂點的距離存入陣列dis中，此時，dis[i]中存放的是源點到頂點vi的距離，將源點加入頂點集s；
（2）在dis[ ]中選取權值最小的邊，並且將此邊對應的頂點vj加入s；
（3）從vj開始，得到vj到其它未被加入到s中的頂點的距離，將此距離與dis[ ]中的資料相加並與元資料相加，如果比原資料小，那麼就替換原資料，否則保留原值；
（4）重複2-4，直到所有頂點都被加入到s，那麼源點到所有頂點的最小距離都找到了。
15.將aov網路中的各頂點（活動）排成乙個線性有序序列，使得所有的前驅和後繼關係都能滿足要求，則稱為拓撲排序。
演算法與資料結構
演算法 是按部就班地解決某個問題的方法，是對特定問題求解步驟的一種描述。偽碼語言是一種包括高階程式語言的3種基本控制結構 順序 選擇和迴圈 和自然語言成分的 物件導向 的語言。演算法的特徵 1 可行性 一是演算法中的每個步驟必須是能實現的 二是演算法執行的結果要能達到預期的目的。2 確定性 演算法的...
資料結構與演算法
課程設計報告 目錄一 問題描述1 二 資料結構1 三 演算法設計思想及流程圖1 四 源程式2 五 測試情況6 參考文獻6 一 問題描述 計算表示式的值 問題描述 對於給定的乙個表示式，表示式中可以包括常數 算術執行符和括號，編寫程式計算表示式的值。基本要求 從鍵盤輸入乙個正確的中綴表示式，將中綴表示...
資料結構部分試題
1 資料的邏輯結構包括四種型別。2 在棧中，訪問資料遵循的原則是 3 二分查詢法，表中元素必須按存放 4 雜湊表一般按儲存方式構造的儲存結構 5 圖有和三種結構 6 評價演算法優劣的主要標準是和 7 在佇列結構中，允許插入的一端成為允許刪除的一端稱為8 順序表相對於鍊錶的優點有和 9 解決佇列假溢位...