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

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

3、有環(huán)最簡便的方法就是追逐法。設(shè)置兩個指針p和q指向鏈表的頭結(jié)點，然后循環(huán)移動兩個指針，p指針每次移動一個節(jié)點，即一步，q指針每次移動兩步，如果該單鏈表存在環(huán)，那么這兩個指針總會在某個位置相遇。如果鏈表無環(huán)，則q會率先指向NULL。具體的過程如圖3所示。 圖3 判斷鏈表有環(huán)運行圖,如何找出有環(huán)鏈表中環(huán)的起始位置，通過圖2可知，只要確定了環(huán)的長度和鏈表的長度，就能輕松的計算頭結(jié)點到環(huán)起始位置之間的鏈表長度，這樣環(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