單鏈表環(huán)的判斷及其起始位置定位.ppt

1、單鏈表有環(huán)判斷及其起始位置定位,主講人：劉其強(qiáng) 2016年9月27日,目錄,鏈表的定義及單鏈表 有環(huán)單鏈表 單鏈表有環(huán)判斷及其起始位置定位 C+代碼,鏈表的定義及單鏈表,鏈表是將數(shù)據(jù)元素存放在不連續(xù)的地址空間中的一種線性表。鏈表分為單鏈表、雙鏈表和循環(huán)鏈表幾類。 單鏈表的每一個(gè)結(jié)點(diǎn)包含兩部分?jǐn)?shù)據(jù)域和下一個(gè)結(jié)點(diǎn)的地址即指針域。這里一個(gè)鏈表通常有一個(gè)“表頭”，用來存放第一個(gè)結(jié)點(diǎn)的地址。每一個(gè)結(jié)點(diǎn)的后面一個(gè)結(jié)點(diǎn)稱為該結(jié)點(diǎn)的后繼，鏈表也會(huì)有一個(gè)“表尾”，表尾沒有后繼，所以尾結(jié)點(diǎn)的指針域?yàn)榭罩羔槪∟ULL）。單鏈表結(jié)構(gòu)如下圖1所示。 圖1 單鏈表數(shù)據(jù)結(jié)構(gòu)示意圖,單鏈表具有以下特征,單鏈表結(jié)點(diǎn)的物理位置不

2、一定連續(xù)，單鏈表邏輯上通過指針實(shí)現(xiàn)連續(xù)。 單鏈表有一個(gè)頭結(jié)點(diǎn)和一個(gè)為結(jié)點(diǎn)，并且只有尾結(jié)點(diǎn)沒有后繼點(diǎn)，其它結(jié)點(diǎn)有且僅有一個(gè)后繼結(jié)點(diǎn)。 只要知道了鏈表的頭結(jié)點(diǎn)，就可以遍歷整個(gè)鏈表。,有環(huán)單鏈表,通過圖1可以看出，單鏈表的每一個(gè)存儲(chǔ)結(jié)點(diǎn)（頭結(jié)點(diǎn)和尾結(jié)點(diǎn)除外）在結(jié)構(gòu)上只有一個(gè)前驅(qū)結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)，其頭結(jié)點(diǎn)沒有前驅(qū)并且尾結(jié)點(diǎn)沒有后繼，所以，有環(huán)單鏈表的結(jié)構(gòu)必然如下圖2所示。 圖2 有環(huán)單鏈表,單鏈表有環(huán)只能是指它末尾有環(huán)，不會(huì)是中部，因?yàn)槿绻菢拥脑捑瓦`背了單鏈表只有一個(gè)后繼結(jié)點(diǎn)的要求。所以，我們可以將有環(huán)單鏈表看成是一個(gè)單鏈表與一個(gè)循環(huán)鏈表的組合。,單鏈表有環(huán)判斷及其起始位置定位,判斷一個(gè)單鏈表是否

3、有環(huán)最簡(jiǎn)便的方法就是追逐法。設(shè)置兩個(gè)指針p和q指向鏈表的頭結(jié)點(diǎn)，然后循環(huán)移動(dòng)兩個(gè)指針，p指針每次移動(dòng)一個(gè)節(jié)點(diǎn)，即一步，q指針每次移動(dòng)兩步，如果該單鏈表存在環(huán)，那么這兩個(gè)指針總會(huì)在某個(gè)位置相遇。如果鏈表無環(huán)，則q會(huì)率先指向NULL。具體的過程如圖3所示。 圖3 判斷鏈表有環(huán)運(yùn)行圖,如何找出有環(huán)鏈表中環(huán)的起始位置，通過圖2可知，只要確定了環(huán)的長(zhǎng)度和鏈表的長(zhǎng)度，就能輕松的計(jì)算頭結(jié)點(diǎn)到環(huán)起始位置之間的鏈表長(zhǎng)度，這樣環(huán)的起始位置就呼之欲出了。,C+代碼,1、鏈表有環(huán)判斷 bool isCircleLink(Node *head) If(head=NULL) return false; Node *p,*q; p=q=head; while(q!=NULL,q=q-next-next; If(p=q) break; If(p=q ,2、尋找鏈表環(huán)起始位置 Node circleStar(Node *head) If(head=NULL) return