青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

C++ Programmer's Cookbook

{C++ 基礎} {C++ 高級} {C#界面,C++核心算法} {設計模式} {C#基礎}

c++單向鏈表 (討論應不應該在默認的構造里就分配空間)

// ?IntLink.cpp?:?Defines?the?entry?point?for?the?console?application.
//
//
/**/ //////////////////////////////////////////////////////////////////////// //
// 作者:夢在天涯
// 單向鏈表類
/**/ //////////////////////////////////////////////////////////////////////// //
//
//
#pragma?once
#include?
< stdio.h >
#include?
< tchar.h >

#include?
< iostream >
using ? namespace ?std;

struct ?NODE
{
???
int ?data;
???NODE?
* ?next;
}
;
class ?CIntLink
{
private :
????NODE?
* ?head;
public :
????CIntLink()
????
{
????????head
= NULL;
????}

????
~ CIntLink()
????
{
????????delete?head;
????}

??
void ?Add(? int ?iValue?);
??
void ??Remove(? int ?iIndex);
??
void ???Insert( int ?iIndex,? int ?iValue?);
??
int ??Find(? int ?iValue?);
??
void ?output();
??
int ?size();
}
;
// 鏈表的標號是從0開始。且第一個節(jié)點有存有數據。
void ??CIntLink::Add( int ?ivalue)
{
????
if (head == NULL)
????
{
???????head
= new ?NODE;
???????head
-> data = ivalue;
???????head
-> next = NULL;
????}

????
else
????
{
???NODE?
* temp = new ?NODE;
???temp
-> data = ivalue;
???temp
-> next = NULL;
???NODE?
* p = head;
???
while (p -> next != NULL)
?????????p
= p -> next;
???p
-> next = temp;
????}

??
}

void ?CIntLink::Remove( int ?iIndex)???? // iIndex?從0開始,即第一個值也即頭指針為iIndex為0
{
????
if (iIndex == 0 )
????
{
????????NODE?
* ?p = head;
???????head
= head -> next;
????????delete?p;
????????p
= NULL;
????}

????
else ? if (iIndex == 1 )
????
{
????????NODE?
* ?p2 = head -> next;
????????head
-> next = p2 -> next;
????????delete?p2;
????????p2
= NULL;
????}

????
else
????
{?
????????NODE?
* pre = head -> next;
????????NODE?
* p = pre -> next;
??????
???????
for ( int ?i = 2 ;p != NULL;i ++ )?? // p?為要刪除的值的位置
??????? {??????
????????
if ?(iIndex == i)?? break ;
????????pre
= p;p = p -> next;
???????}

???????
if (iIndex == i && p != NULL)
???????
{
???????????pre
-> next = p -> next;
??????????delete?p;
??????????p
= NULL;
??????}

??????
else ???????????????????????? // p->NULL
?????? {
??????????cout
<< " remove?fail:no?fond?iIndex " << endl;
??????}

???}

}

?
void ?CIntLink::Insert( int ?iIndex,? int ?iValue)
{
????
if (iIndex == 0 )
????
{
????????NODE?
* ?p1 = new ?NODE;
????????p1
-> data = iValue;
????????p1
-> next = head;
????????head
= p1;
????}

????
else ? if (iIndex == 1 )
????
{
????????NODE?
* ?p2 = new ?NODE;
????????p2
-> data = iValue;
????????p2
-> next = head -> next;
????????head
-> next = p2;
????}

????
else
????
{
????????NODE?
* pre = head -> next;
????????NODE?
* pp = pre -> next;
????????
????????
for ( int ?i = 2 ;pp != NULL;i ++ )?? // i為要插入的值的位置
???????? {
????????????
if ?(iIndex == i)?? break ;
????????????pre
= pp;pp = pp -> next;

????????}

????????
if (iIndex == i && pp != NULL)?
????????
{
????????????NODE?
* q = new ?NODE;
????????????q
-> data = iValue;
????????????q
-> next = pp -> next;
????????????pre
-> next = q;
????????????q
-> next = pp;

????????}

?????????
else ??????????????? // (pp->next=NULL)
???????? {
????????????cout
<< " insert?fail:iIndex?is?out?of?range? " << endl;
????????}

????
????}

}

int ??CIntLink::Find( int ?iValue)
?
{
?????
if (head == NULL)
?????
{
?????????cout
<< " find?fail:no?found?ivalue?,and?it?retrun?is?-1 " << endl;
?????????
return ? - 1 ;
?????}

?????NODE?
* pp = ?head;
????
for ( int ?i = 0 ;pp -> next != NULL;i ++ )
??????
if (pp -> data == iValue)
??????
{
???????
return ?i; // --i;
??????}
?
??????
else
???????pp
= pp -> next;

????cout
<< " find?fail:no?found?ivalue,and?it?return?is?-1 " << endl;?
????
return ? - 1 ;
??????
}

?
void ?CIntLink::output()
?
{
?????NODE?
* ?p = head;
?????cout
<< " the?link?data?is?: " << endl;
?????
for (;p != NULL;p = p -> next)
?????????cout
<< p -> data << endl;
?}

?
int ?CIntLink::size()
?
{
?????NODE?
* ?p = head;
?????
int ?i = 0 ;
?????
for (?;p != NULL;p = p -> next,i ++ );
?????
return ?i;
?????????
?}

int ?_tmain( int ?argc,?_TCHAR * ?argv[])
{
????CIntLink?link;
????link.Add(
10 );
????link.Add(
30 );
????link.Add(
40 );
????link.Add(
50 );
????link.Insert(
5 , 20 );
????link.Remove(
5 );
????
int ?num = link.size();
????cout
<< " the?link?data?number?is?: " << num << endl;
????link.output();
????
int ?re = link.Find( 20 );
????cout
<< re << endl;
?
????
return ? 0 ;
}
以上的析構函數,應該先判斷為NULL,再delete.

別人寫的:
#ifndef?LIST_H
#define?LIST_H
template
<typename?elemtype>class?list_item?
{
public:
?list_item(?elemtype,?list_item
<elemtype>*?);
?list_item(?
const?list_item<elemtype>&?);

?
const?elemtype?date?()?const;
?
const?list_item<elemtype>*?next()?const;?
?
void?get_date?(?const?elemtype?);
?
void?get_next?(?const?list_item<elemtype>*?);

?
void?operator?=(?const?list_item<elemtype>&?);
private:
?elemtype??_date;
?list_item
<elemtype>?*_next;?
}
;//單鏈表數據項類

//數據項類代碼實現
template<typename?elemtype>
?list_item
<elemtype>::list_item(?elemtype?ia?=?0,
???????list_item
<elemtype>?*p?=?0?)?
?
{
???get_date(?ia?);
???
if(?p?==?NULL?)
????get_next(?NULL?);
???
else?
???
{
????get_next(?p
->next()?);
????p
->get_next(?this?);
???}

??}

template
<typename?elemtype>
?
const?elemtype?
?list_item
<elemtype>::date()?const?
?
{
??
return?_date;
?}

template
<typename?elemtype>?const?
?list_item
<elemtype>*?list_item<elemtype>::
?next()?
const??
?
{?
??
return?_next;
?}

template
<typename?elemtype>
?
void?list_item<elemtype>::get_date(?const?elemtype?de?)
?
{
??_date?
=?de;?
?}

template
<typename?elemtype>
?
void?list_item<elemtype>::
?get_next(?
const?list_item<elemtype>?*pev?)
?
{?
??_next?
=?(?list_item<elemtype>*?)pev;?
?}


template
<typename?elemtype>?class?list
{
public:
?list();
?list(?
const?list<elemtype>&?);
?
~list();

?
const?int?size()?const;
?
const?bool?empty()?const;
?
void?insert(?const?elemtype,?const?elemtype?);
?
void?insert_front(?const?elemtype?);
?
void?insert_end(?const?elemtype?);
?
void?remove(?const?elemtype?);
?
void?remove_all();
?
void?remove_front();
?
void?print()?const;
?
const?list_item<elemtype>*?find(?const?elemtype?);

?
void?operator?=(?const?list<elemtype>&?);

private:
?
//
?void?down_size();
?
void?add_size();

?
//
?list_item<elemtype>?*at_front;
?list_item
<elemtype>?*at_end;
?list_item
<elemtype>?*at_move;
?
int???????????????_size;
}
;//鏈表類定義

//函數實現代碼
//私有函數集合
template<typename?elemtype>?
?
void?list<elemtype>::add_size()?
?
{
??
++_size;?
?}

template
<typename?elemtype>
?
void?list<elemtype>::down_size()?
?
{
??
--_size;?
?}


//公有函數集合
template<typename?elemtype>
?list
<elemtype>::list()?{?
??at_front?
=?NULL;
??at_end?
=?NULL;
??_size?
=?0;
?}

template
<typename?elemtype>
?list
<elemtype>::~list()?
?
{
??remove_all();
?}

template
<typename?elemtype>
?
const?bool?list<elemtype>::empty()?const
?
{
??
return?size()?==?0???false?:?true;
?}

template
<typename?elemtype>
?
const?int?list<elemtype>::size()?const
?
{?
??
return?_size;
?}

template
<typename?elemtype>
?
void?list<elemtype>::insert_front(?const?elemtype?iva?)
?
{
??list_item
<elemtype>?*pv?=?
????
new?list_item<elemtype>(?iva,?0?);
??
if(?!at_front?)
??
{
???at_front?
=?at_end?=?pv;
??}

??
else?
??
{
???pv
->get_next(?at_front?);
???at_front?
=?pv;
??}

??add_size();
?}

template
<typename?elemtype>
?
void?list<elemtype>::insert_end(?const?elemtype?iva?)?
?
{
??
if(?at_end?==?NULL)?
??
{
???at_end?
=?at_front?=
?????
new?list_item<elemtype>(?iva,?0?);
??}

??
else?
???at_end?
=?new?list_item<elemtype>(?iva,?at_end?);?
??add_size();
?}

template
<typename?elemtype>?void?list<elemtype>::
?insert(?
const?elemtype?ixa,?const?elemtype?iva?)?
?
{
??list_item
<elemtype>?*pev?=?
????(?list_item
<elemtype>*?)find(?iva?);
??
if(?pev?==?NULL?)
??
{
???cerr?
<<?"err!"?<<endl;
???
return;
??}

??
if(?pev?==?at_front?)?
???insert_front(?ixa?);
??
else?{
???
new?list_item<elemtype>(?ixa,?pev?);
???add_size();
??}

?}

template
<typename?elemtype>?const?
list_item
<elemtype>*?list<elemtype>::
?find(?
const?elemtype?iva?)
?
{
??list_item
<elemtype>?*at_move?=?at_front;
??
while(?at_move?!=?NULL?)?
??
{
???
if(?at_move->date()?==?iva?)
????
return?at_move;
???at_move?
=?(?list_item<elemtype>*?)at_move->next();
??}

???
return?NULL;
?}

template
<typename?elemtype>
?
void?list<elemtype>::remove_front()
?
{
??
if(?at_front?)
??
{
???list_item
<elemtype>?*pev?=?at_front;
???at_front?
=?(?list_item<elemtype>*?)at_front->next();
???delete?pev;
???down_size();
??}

?}

template
<typename?elemtype>
?
void?list<elemtype>::remove(?elemtype?iva?)
?
{
??list_item
<elemtype>?*pev?=?at_front;
??
while(?pev?&&?pev->date()?==?iva?)
??
{
???pev?
=?(?list_item<elemtype>*?)pev->next();
???remove_front();
??}

??
if(?!pev?)
???
return?;
??list_item
<elemtype>?*prv?=?pev;
??pev?
=?(?list_item<elemtype>*?)pev->next();
??
while(?pev?)?
??
{
???
if(?pev->date()?==?iva?)?
???
{
????prv
->get_next(?pev->next()?);???
????down_size();
????delete?pev;
????pev?
=?(?list_item<elemtype>*?)prv->next();
????
if(?pev?!=?NULL?)
????
{
?????at_end?
=?prv;
?????
return;
????}

???}

???
else?
???
{
????prv?
=?pev;
????pev?
=?(?list_item<elemtype>*?)pev->next();
???}

??}

?}

template
<typename?elemtype>
?
void?list<elemtype>::remove_all()
?
{
??
while(?at_front?)
???remove_front();
??_size?
=?0;
??at_front?
=?at_end?=?NULL;
?}

template
<typename?elemtype>
?
void?list<elemtype>::print()?const?
?
{
??list_item
<elemtype>?*pev?=?at_front;
??cout?
<<?'['?<<?size()?<<?']';
??cout?
<<?'{';
??
for(?int?ix?=?0;?pev?&&?ix?<?size();?++ix?)?
??
{
???cout?
<<?pev->date()?<<?'?';
???pev?
=?(?list_item<elemtype>*?)pev->next();
??}

??cout?
<<?'}'?<<?endl;
?}

#endif

posted on 2005-10-28 08:42 夢在天涯 閱讀(2477) 評論(6)  編輯 收藏 引用 所屬分類: CPlusPlus 、Data Arithmetic

評論

# re: c++單向鏈表 (討論應不應該在默認的構造里就分配空間) 2005-11-02 08:12 懷沙

應該要有拷貝構造函數哦,否則在進行
CIntLink link2(link);
這樣的操作時只會復制頭結點的指針,而不是重新初始化一個鏈表哦  回復  更多評論   

# re: c++單向鏈表 (討論應不應該在默認的構造里就分配空間) 2005-11-02 17:28 magician

樓上說的還可以,如果為了使程序更加我完善,有健壯性,我還是喜歡用template<class T>
的方式來創(chuàng)建一個連表,  回復  更多評論   

# re: c++單向鏈表 (討論應不應該在默認的構造里就分配空間) 2005-11-03 16:19 夢在天涯

樓上的樓上說的拷貝構造函數是不是每個節(jié)點都的重新new,???  回復  更多評論   

# re: c++單向鏈表 (討論應不應該在默認的構造里就分配空間) 2005-11-15 16:35 yanfei

請問采用template<class T>的方式有什么好處呢?
  回復  更多評論   

# re: c++單向鏈表 (討論應不應該在默認的構造里就分配空間) 2005-12-10 00:10 寒曙

好處當然是不言自明咯,算法嚴謹,安全,可重用性高……
  回復  更多評論   

# re: c++單向鏈表 (討論應不應該在默認的構造里就分配空間) 2005-12-29 12:34 nanami

構造拷貝應該進行值拷貝。僅僅拷貝外部變量指針,在C++中極易造成內存泄漏,構成安全隱患。

除非你的程序對性能要求極高,或者你的鏈表長度極長(一般>100000項,相對于現在的計算機內存操作性能,才應算做極長,當然,實際情況也要綜合考慮鏈表每一項的長度。),并且你保證外部變量在此類所生成的實例的生存周期內一直有效,那么僅僅傳遞指針是可以的。 不過這樣一來,你DEBUG的時間會高出N倍,而且極易留下后患。尤其在對安全性和穩(wěn)定性較高的領域,寧可犧牲些許性能,也要盡量保證安全。

順便多句嘴,鏈表如果>100000項,盡量考慮RedBlackTree或者Map/HashMap,這樣查找的性能比鏈表高的多得多得多得多得多,而插入最末項的性能也并會不比鏈表慢。尤其如果鏈表需要進行按順序插入合適的位置,那么那個速度- -!我想你看到了,會以為死機了。

單項鏈表,N項,查找其中一個值最大時間O(N)。而對于紅黑樹或MAP,最大時間僅需O(log2(N))次操作,HASHMAP的查找時間恒定,只和HASH函數的速度相關。一般來說,對于極大數據結構操作HASHMAP是最理想的。  回復  更多評論   

公告

EMail:itech001#126.com

導航

統(tǒng)計

  • 隨筆 - 461
  • 文章 - 4
  • 評論 - 746
  • 引用 - 0

常用鏈接

隨筆分類

隨筆檔案

收藏夾

Blogs

c#(csharp)

C++(cpp)

Enlish

Forums(bbs)

My self

Often go

Useful Webs

Xml/Uml/html

搜索

  •  

積分與排名

  • 積分 - 1814985
  • 排名 - 5

最新評論

閱讀排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
      <noscript id="pjuwb"></noscript>
            <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
              <dd id="pjuwb"></dd>
              <abbr id="pjuwb"></abbr>
              亚洲欧美一区二区原创| 欧美激情中文不卡| 久久久伊人欧美| 国产精品久久久久毛片软件| 亚洲久久视频| 欧美国产激情二区三区| 久久久久九九九九| 久久精品国产亚洲a| 欧美亚洲午夜视频在线观看| 亚洲欧美国产高清va在线播| 亚洲一区二区三区免费观看| 中文在线资源观看网站视频免费不卡| 亚洲精品老司机| 日韩午夜精品| 99天天综合性| 国内精品久久久| 国产精品日韩久久久久| 欧美一区二区三区在线观看| 亚洲综合精品| 久久久在线视频| 欧美成人性生活| 欧美日韩视频一区二区三区| 国产精品极品美女粉嫩高清在线 | 国产精品一级| 午夜精品久久久久久久久| 一本大道久久a久久精品综合| 亚洲激情综合| 亚洲精品久久久久| 亚洲精品乱码久久久久久久久| 欧美精品一区二区视频| 久久久噜噜噜久久中文字幕色伊伊| 亚洲激情影院| 一区二区欧美精品| 亚洲欧美日韩在线播放| 久久精品青青大伊人av| 欧美激情免费在线| 国产精品一区二区a| 一区二区在线视频播放| 99精品视频免费观看视频| 午夜在线一区| 亚洲专区一区二区三区| 久久精品国产999大香线蕉| 老司机午夜精品视频| 亚洲国产毛片完整版| 亚洲伊人伊色伊影伊综合网| 久久米奇亚洲| 国产精品成人一区二区网站软件| 国产日韩在线视频| 极品少妇一区二区三区精品视频| 国产亚洲aⅴaaaaaa毛片| 亚洲日本激情| 久久婷婷国产综合尤物精品| 一区二区三区欧美日韩| 久久婷婷一区| 国产精品一区二区你懂得 | 欧美性大战久久久久| 在线电影国产精品| 99视频超级精品| 亚洲精品美女久久久久| 亚洲国产美国国产综合一区二区| 亚洲一区网站| 国语自产在线不卡| 亚洲国产精品ⅴa在线观看| 国产精品99一区二区| 亚洲在线观看免费视频| 欧美va亚洲va日韩∨a综合色| 亚洲综合精品四区| 亚洲电影在线免费观看| 亚洲九九九在线观看| 国产精品久久久一本精品| 久久久国产一区二区| 一本色道久久加勒比精品| 日韩一级精品| 欧美国产视频在线观看| 另类人畜视频在线| 亚洲黄色一区二区三区| 亚洲第一搞黄网站| av成人国产| 蜜桃av久久久亚洲精品| 午夜免费电影一区在线观看| 国产精品日韩精品| 欧美亚洲三级| 亚洲欧美日本国产有色| 国产精品日韩欧美大师| 亚洲国产成人午夜在线一区| 久久久亚洲一区| 久久国内精品自在自线400部| 国产精品揄拍500视频| 亚洲欧美日韩一区二区| 黄色成人在线免费| 欧美大片免费观看| 久久久久综合一区二区三区| 国产自产2019最新不卡| 亚洲破处大片| 亚洲久久视频| 国产精品精品视频| 欧美亚洲视频一区二区| 午夜久久tv| 影音先锋一区| 久久久久久久一区| 久热综合在线亚洲精品| **网站欧美大片在线观看| 欧美二区不卡| 欧美日韩亚洲一区二区三区在线观看| 亚洲在线观看| 久久大逼视频| 亚洲精品乱码久久久久久按摩观| 欧美三级中文字幕在线观看| 欧美成年人视频网站| 亚洲电影免费观看高清完整版在线观看| 欧美电影打屁股sp| 国产精品草莓在线免费观看| 欧美一区二区三区在线看| 在线亚洲欧美视频| 合欧美一区二区三区| 另类天堂av| 美女久久网站| 亚洲乱码日产精品bd| 亚洲自拍偷拍麻豆| 日韩视频免费看| 久久国产精品一区二区三区四区| 亚洲精品乱码久久久久久| 亚洲一区二区三区高清| 亚洲国产一区二区三区a毛片| 夜夜狂射影院欧美极品| 狠狠色噜噜狠狠狠狠色吗综合| 亚洲人www| 黄色在线成人| 亚洲自拍偷拍麻豆| 欧美午夜精彩| 国内外成人免费激情在线视频网站 | 久久精品欧美| 久久精品视频免费播放| 国产精品日本| 亚洲欧美国产va在线影院| 亚洲天堂免费观看| 欧美日韩国产三级| 亚洲精品免费在线观看| 99国产欧美久久久精品| 欧美日韩蜜桃| 艳女tv在线观看国产一区| 亚洲视频视频在线| 国产精品久久久91| 午夜免费久久久久| 久久亚洲综合色一区二区三区| 国内一区二区三区| 久久综合一区二区| 91久久国产综合久久蜜月精品 | 在线观看中文字幕不卡| 久久亚洲欧美| 亚洲人永久免费| 亚洲一区二区在线看| 国产精品久久99| 欧美一级大片在线观看| 免费视频最近日韩| 99在线精品视频| 国产精品免费看片| 久久久99精品免费观看不卡| 欧美国产日本高清在线| 一二三四社区欧美黄| 国产精品免费看片| 久久久久久电影| 日韩一本二本av| 久久国产欧美精品| 亚洲精品韩国| 国产精品日本| 美女视频黄免费的久久| 亚洲视频网在线直播| 美女精品在线| 亚洲自拍偷拍福利| 伊人久久av导航| 欧美亚洲不卡| 女同一区二区| 香港成人在线视频| 日韩亚洲成人av在线| 理论片一区二区在线| 一片黄亚洲嫩模| 在线观看欧美| 国产偷久久久精品专区| 欧美精品日韩三级| 99国产精品99久久久久久| 国产精品久久久久久久电影 | 久久精品二区| 亚洲精品乱码久久久久久蜜桃麻豆 | 国产人成一区二区三区影院| 欧美fxxxxxx另类| 亚洲在线电影| 亚洲精品综合久久中文字幕| 久久一区二区三区超碰国产精品| 在线视频精品一区| 在线免费观看成人网| 国产日韩精品一区二区| 欧美日韩在线观看一区二区三区| 久久久久久久97| 欧美一区二区三区免费看 | 亚洲高清免费| 老巨人导航500精品| 欧美制服第一页| 性欧美办公室18xxxxhd| 亚洲影院色无极综合|