是技術(shù),更是藝術(shù)
一心編程,就沒有解決不了的問題
posts - 9, comments - 11, trackbacks - 0, articles - 0
導(dǎo)航
C++博客
首頁
新隨筆
聯(lián)系
聚合
管理
<
2010年9月
>
日
一
二
三
四
五
六
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
常用鏈接
我的隨筆
我的評論
我參與的隨筆
留言簿
給我留言
查看公開留言
查看私人留言
隨筆分類
C++(4)
QT(1)
算法(3)
圖形學(xué)(1)
云平臺
隨筆檔案
2010年10月 (1)
2010年9月 (1)
2010年7月 (3)
2009年12月 (1)
2009年9月 (2)
2009年8月 (1)
搜索
最新評論
1.?re: QT顯示TGA圖片
經(jīng)測試,在Linux下此方法不行。程序有時(shí)候出現(xiàn)異常,有時(shí)候會顯示錯誤的圖像。我的環(huán)境是Ubuntu11.10,Qt4.8.3,Qt Creator2.41。
--彩陽
2.?re: 快速判斷素?cái)?shù)算法
理論依據(jù)是什么?
--aa
3.?re: 快速判斷素?cái)?shù)算法
@某W
謝謝,拋磚引玉而已,期待你提出更優(yōu)秀的方法
--李熙建
4.?re: 判斷單鏈表是否有環(huán)
@kyle
非常感謝你指出其中的錯誤
--李熙建
5.?re: 快速判斷素?cái)?shù)算法
這方法很強(qiáng)大~
謝謝~
--某W
閱讀排行榜
1.?快速判斷素?cái)?shù)算法(4241)
2.?判斷單鏈表是否有環(huán)(3172)
3.?QT顯示TGA圖片(2081)
4.?時(shí)間統(tǒng)計(jì)的幾種方法(1042)
5.?Material Editor(961)
評論排行榜
1.?判斷單鏈表是否有環(huán)(4)
2.?快速判斷素?cái)?shù)算法(3)
3.?Material Editor(3)
4.?QT顯示TGA圖片(1)
5.?temp 對象(0)
判斷單鏈表是否有環(huán)
Posted on 2010-09-24 12:30
李熙建
閱讀(3172)
評論(4)
編輯
收藏
引用
所屬分類:
C++
typedef
struct
LNode
{
int
data;
LNode
*
next;
}
LNode ;
typedef LNode
*
LinkList;
//
單鏈表有環(huán)返回true 否則返回false
bool
is_looplist(LNode
*
head)
{
LNode
*
fast,
*
slow;
if
(head
==
NULL
||
head
->
next
==
NULL)
{
return
false
;
}
slow
=
head;fast
=
head->next;
while
(
true
)
{
if
(
!
fast
||
!
fast
->
next)
return
false
;
//
為了防止fast跨過slow的情況,在每次判斷的時(shí)候比較當(dāng)前節(jié)點(diǎn)和下一節(jié)點(diǎn)
else
if
(fast
==
slow
||
fast
->
next
==
slow)
return
true
;
else
{
slow
=
slow
->
next;
//
一次跳一步
fast
=
fast
->
next
->
next;
//
一次跳兩步
}
}
}
如果要返回環(huán)的入口節(jié)點(diǎn)
一種效率比較低的方法是
一個指針p1從表頭開始,指針p2 初始化為判環(huán)時(shí)找到的指針,p1每前進(jìn)一步,由p2遍歷一次環(huán)中各結(jié)點(diǎn),遍歷過程中每次都要判斷p1是否p2
當(dāng)p2 == fast時(shí)候,p1 = p1.next,繼續(xù)循環(huán)。這樣肯定能找到入口,但是效率為O(n^2)
Feedback
#
re: 判斷單鏈表是否有環(huán)
回復(fù)
更多評論
2010-09-25 08:16 by
Algorics
如果知道鏈表的結(jié)點(diǎn)數(shù)n,那么如果進(jìn)行n+1次找下一個結(jié)點(diǎn)還沒到鏈表的尾部的話就有環(huán)。
#
re: 判斷單鏈表是否有環(huán)
回復(fù)
更多評論
2010-09-26 21:46 by
李熙建
@Algorics
一般情況下,只已知鏈表的頭節(jié)點(diǎn),鏈表元素個數(shù)已知的情況下,你說的方法可以
#
re: 判斷單鏈表是否有環(huán)[未登錄]
回復(fù)
更多評論
2011-05-06 17:49 by
kyle
代碼有錯...永遠(yuǎn)返回TRUE.
在對fast初始化的時(shí)候應(yīng)該是fast=head->next;
#
re: 判斷單鏈表是否有環(huán)
回復(fù)
更多評論
2011-08-01 09:14 by
李熙建
@kyle
非常感謝你指出其中的錯誤
刷新評論列表
只有注冊用戶
登錄
后才能發(fā)表評論。
【推薦】100%開源!大型工業(yè)跨平臺軟件C++源碼提供,建模,組態(tài)!
相關(guān)文章:
cout問題
判斷單鏈表是否有環(huán)
temp 對象
CString,string,char*, int之間的轉(zhuǎn)換
網(wǎng)站導(dǎo)航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
Powered by:
C++博客
Copyright © 李熙建
久久久久久国产精品免费免费
|
婷婷五月深深久久精品
|
久久91精品国产91
|
久久久亚洲欧洲日产国码二区
|
久久99热只有频精品8
|
精品人妻伦一二三区久久
|
久久精品日日躁夜夜躁欧美
|
久久99精品国产麻豆
|
日韩十八禁一区二区久久
|
久久久女人与动物群交毛片
|
久久人人爽人爽人人爽av
|
欧洲成人午夜精品无码区久久
|
久久精品这里只有精99品
|
久久99亚洲网美利坚合众国
|
久久毛片一区二区
|
中文精品久久久久国产网址
|
久久AV高潮AV无码AV
|
久久高清一级毛片
|
9999国产精品欧美久久久久久
|
99精品国产综合久久久久五月天
|
Xx性欧美肥妇精品久久久久久
|
狠狠综合久久综合88亚洲
|
久久久无码精品亚洲日韩软件
|
久久99热只有频精品8
|
伊人色综合久久天天人手人婷
|
久久久艹
|
久久国产一片免费观看
|
九九99精品久久久久久
|
A级毛片无码久久精品免费
|
婷婷久久五月天
|
久久综合色老色
|
久久天天躁狠狠躁夜夜不卡
|
久久精品女人天堂AV麻
|
久久精品国产亚洲AV不卡
|
久久国产福利免费
|
久久久精品日本一区二区三区
|
国产午夜精品久久久久九九电影
|
91久久精品视频
|
国内精品久久久久久中文字幕
|
成人国内精品久久久久影院VR
|
久久se精品一区精品二区
|