- 相關推薦
2017年計算機二級C語言公共基礎復習資料
C語言提供多種運算符和表達式值的方法，對問題的表達可通過多種途徑獲得，其程序設計更主動、靈活。下面是小編整理的關于計算機二級C語言公共基礎復習資料，歡迎大家參考!
循環鏈表及其基本運算
在線性鏈表中，雖然對數據元素的插入和刪除操作比較簡單，但由于它對第一個結點和空表需要單獨處理，使得空表與非空表的處理不一致。
循環鏈表，即是采用另一種鏈接方式，它的特點如下：
(1)在循環鏈表中增加一個表頭結點，其數據域為任意或根據需要來設置，指針域指向線性表的第一個元素的結點。循環鏈表的頭指針指向表頭結點。
(2)循環鏈表中最后一個結點的指針域不是空的，而是指向表頭結點。在循環鏈表中，所有結點的指針構成一個環狀鏈。
在循環鏈表中，只要指出表中任何一個結點的位置，均可以從它開始掃描到所有的結點，而線性鏈表做不到，線性鏈表是一種單向的鏈表，只能按照指針的方向進行掃描。
循環鏈表中設置了一個表頭結點，因此，在任何時候都至少有一個結點，因此空表與非空表的'運算相統一。
循環鏈表的特點是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。
【例】在鏈表上實現將兩個線性表(a1，a2，…，an)和(b1，b2，…，bm)連接成一個線性表(a1，…，an，b1，…bm)的運算。
分析：若在單鏈表或頭指針表示的單循環表上做這種鏈接操作，都需要遍歷第一個鏈表，找到結點an，然后將結點b1鏈到an的后面，其執行時間是O(n)。
若在尾指針表示的單循環鏈表上實現，則只需修改指針，無須遍歷，其執行時間是O(1)。
相應的算法如下：
LinkListConnect(LinkListA,LinkListB){
//假設A，B為非空循環鏈表的尾指針
LinkListp=A->next;//①保存A表的頭結點位置
A->next=B->next->next;//②B表的開始結點鏈接到A表尾
free(B->next);//③釋放B表的頭結點
B->next=p;//④
returnB;//返回新循環鏈表的尾指針
}
注意：
�、傺h鏈表中沒有NULL指針。涉及遍歷操作時，其終止條件就不再是像非循環鏈表那樣判別p或p->next是否為空，而是判別它們是否等于某一指定指針，如頭指針或尾指針等。
�、谠趩捂湵碇校瑥囊灰阎Y點出發，只能訪問到該結點及其后續結點，無法找到該結點之前的其它結點。而在單循環鏈表中，從任一結點出發都可訪問到表中所有結點，這一優點使某些運算在單循環鏈表上易于實現。
二叉樹的遍歷
二叉樹的遍歷即是不重復地訪問二叉樹的所有結點。
在遍歷二叉樹時，一般先遍歷左子樹，然后再遍歷右子樹。在先左后右的原則下，二叉樹的遍歷又可分為三種：前序遍歷、中序遍歷和后序遍歷。
1)前序遍歷
前序遍歷即先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。在遍歷左子樹和遍歷右子樹時，依然是先遍歷根結點，然后是左子樹，再是右子樹。
操作的具體方式：
若二叉樹為空，則結束返回。
否則：訪問根結點前序遍歷左子樹前序遍歷右子樹
如上圖所示的完全二叉樹，它的前序遍歷結果是：A、B、D、H、P、Q、I、R、E、J、K、C、F、L、M、G、N、O
2)中序遍歷
中序遍歷，即先遍歷左子樹，然后訪問根結點，最后是遍歷右子樹。
具體的操作方式：
若二叉樹為空，則結束返回。
否則：中序遍歷左子樹訪問根結點 中序遍歷右子樹
這里強調，在遍歷左子樹和右子樹時，仍然要采用中序遍歷的方法。
如上圖所示的.完全二叉樹，它的中序遍歷結果是：P、H、Q、D、R、I、B、J、E、K、A、L、F、M、C、N、G、O
3)后序遍歷
后序遍歷，即選遍歷左子樹，然后是遍歷右子樹，最后訪問根結點。
具體的操作方式：
若二叉樹為空，則結束返回。
否則：前序遍歷左子樹前序遍歷右子樹訪問根結點
如上圖所示的完全二叉樹，它的后序遍歷結果是：P、Q、H、R、I、D、J、K、E、B、L、M、F、N、O、G、C、A
【計算機二級C語言公共基礎復習資料】相關文章：
計算機二級C語言復習資料10-17
2017年計算機二級C語言基礎考試試題10-05
計算機二級C語言考點盤點07-28
計算機二級c語言題庫及答案09-25
計算機二級《公共基礎》模擬試題及答案10-30
計算機二級C++基礎練習題10-28
計算機二級《C語言》模擬試題及答案07-31
計算機二級C語言沖刺試題及答案10-29
計算機二級公共基礎知識試題及答案10-01
計算機二級C語言數據類型08-28