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