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

C++ Programmer's Cookbook

{C++ 基礎(chǔ)} {C++ 高級} {C#界面,C++核心算法} {設(shè)計模式} {C#基礎(chǔ)}

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

// ?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();
}
;
// 鏈表的標(biāo)號是從0開始。且第一個節(jié)點有存有數(shù)據(jù)。
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 ;
}
以上的析構(gòu)函數(shù),應(yīng)該先判斷為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;?
}
;//單鏈表數(shù)據(jù)項類

//數(shù)據(jù)項類代碼實現(xiàn)
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;
}
;//鏈表類定義

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

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


//公有函數(shù)集合
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 夢在天涯 閱讀(2483) 評論(6)  編輯 收藏 引用 所屬分類: CPlusPlusData Arithmetic

評論

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

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

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

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

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

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

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

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

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

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

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

構(gòu)造拷貝應(yīng)該進行值拷貝。僅僅拷貝外部變量指針,在C++中極易造成內(nèi)存泄漏,構(gòu)成安全隱患。

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

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

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

公告

EMail:itech001#126.com

導(dǎo)航

統(tǒng)計

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

常用鏈接

隨筆分類

隨筆檔案

收藏夾

Blogs

c#(csharp)

C++(cpp)

Enlish

Forums(bbs)

My self

Often go

Useful Webs

Xml/Uml/html

搜索

  •  

積分與排名

  • 積分 - 1816190
  • 排名 - 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>
              免费在线看一区| 国产亚洲欧美一区二区三区| 欧美体内she精视频| 国产日本欧洲亚洲| 亚洲国产免费看| 亚洲少妇一区| 久久婷婷久久一区二区三区| 亚洲人成77777在线观看网| 亚洲午夜精品久久久久久浪潮| 欧美在线亚洲在线| 欧美日韩国产123| 国产综合精品| 亚洲午夜在线观看| 乱中年女人伦av一区二区| 亚洲精品欧洲| 久久久国产精品一区二区三区| 欧美日韩久久| 在线成人av| 午夜精品久久久久99热蜜桃导演| 麻豆久久婷婷| 亚洲婷婷综合久久一本伊一区| 久久免费黄色| 国产精品丝袜xxxxxxx| 亚洲精品久久久久久下一站 | 亚洲成在线观看| 亚洲一区二区av电影| 欧美成人69| 午夜视频在线观看一区二区| 欧美日韩成人综合天天影院| 狠狠综合久久| 午夜欧美精品| 日韩视频一区二区在线观看| 久久久亚洲国产天美传媒修理工| 国产精品进线69影院| 亚洲剧情一区二区| 玖玖精品视频| 午夜精品久久久久久久久久久久| 欧美日韩亚洲网| 91久久综合亚洲鲁鲁五月天| 久久亚洲国产成人| 亚洲欧美日韩在线高清直播| 欧美日韩在线观看一区二区| 91久久精品国产91性色tv| 久久婷婷人人澡人人喊人人爽| 亚洲视频视频在线| 欧美区高清在线| 亚洲人体偷拍| 欧美电影免费观看| 久久精品一区蜜桃臀影院| 国产精品资源| 午夜老司机精品| 一本色道久久加勒比88综合| 男人的天堂亚洲| 1024欧美极品| 欧美69wwwcom| 久久久久一区二区三区| 国内成人精品2018免费看| 久久av资源网站| 午夜久久久久| 国产欧美一区视频| 欧美一区二区三区免费观看视频| 一区二区国产日产| 欧美视频精品在线观看| 在线亚洲自拍| 在线一区视频| 国产精品美女诱惑| 性感少妇一区| 午夜精品一区二区在线观看| 国产亚洲福利社区一区| 久久国产视频网站| 欧美在线日韩精品| 精品成人乱色一区二区| 麻豆av福利av久久av| 狂野欧美激情性xxxx| 亚洲黄色视屏| 亚洲黄色一区二区三区| 欧美国产日韩免费| 日韩一级成人av| 亚洲最黄网站| 国产精品免费看片| 久久se精品一区二区| 欧美一级视频| 一区久久精品| 亚洲激情国产| 欧美午夜电影网| 欧美中文字幕视频| 久久久综合激的五月天| 最新亚洲一区| 亚洲最快最全在线视频| 国产精品入口66mio| 久久久久久一区| 男男成人高潮片免费网站| av成人老司机| 亚洲免费视频在线观看| 黄色成人免费观看| 亚洲国产清纯| 国产精品免费视频观看| 久久精品在线免费观看| 蜜臀久久久99精品久久久久久| 一本一本久久a久久精品牛牛影视| 一区二区国产在线观看| 国产一区二区三区在线免费观看| 免费在线观看日韩欧美| 欧美区国产区| 久久久国产精品亚洲一区| 狼人社综合社区| 国产精品99久久久久久宅男| 香蕉久久一区二区不卡无毒影院 | 久久久久久香蕉网| 日韩午夜电影| 午夜一区不卡| 亚洲精品欧美极品| 亚洲欧美另类国产| 91久久午夜| 亚洲永久免费观看| 亚洲国产裸拍裸体视频在线观看乱了| 日韩视频亚洲视频| 国内一区二区三区在线视频| 亚洲欧洲一区二区三区| 国产精品专区h在线观看| 亚洲国产mv| 国产一区二区三区直播精品电影| 亚洲黄页一区| 韩曰欧美视频免费观看| 日韩午夜激情电影| 伊人久久大香线蕉综合热线| 中国成人黄色视屏| 亚洲激情视频| 性做久久久久久久免费看| 日韩一区二区免费看| 久久九九国产| 午夜在线精品| 欧美喷潮久久久xxxxx| 久久午夜电影网| 国产精品久久久久77777| 亚洲成人在线视频网站| 国产亚洲综合精品| 国产精品99久久久久久久女警| 亚洲国产91| 午夜久久美女| 亚洲资源av| 欧美精品一区二区三区蜜臀 | 欧美成人免费在线| 国产精品影音先锋| 99国产精品久久| 亚洲日本中文字幕| 久久免费高清视频| 久久久久久久波多野高潮日日| 欧美午夜精彩| 亚洲精品美女在线观看| 亚洲国产成人高清精品| 欧美一区二区私人影院日本| 亚洲免费一区二区| 欧美日韩亚洲激情| 亚洲黄色影院| 亚洲人成在线观看| 久久在线播放| 老司机凹凸av亚洲导航| 国产午夜久久久久| 午夜国产欧美理论在线播放 | 久久www成人_看片免费不卡| 国产精品都在这里| 99精品免费视频| 夜夜嗨av一区二区三区四区| 免费成人小视频| 欧美电影资源| 1024精品一区二区三区| 久久亚洲精品一区| 免费成人美女女| 在线日韩欧美| 噜噜噜在线观看免费视频日韩| 免费毛片一区二区三区久久久| 狠狠色狠狠色综合人人| 久久精品国内一区二区三区| 久久久久一本一区二区青青蜜月| 国产亚洲精品福利| 久久爱www久久做| 久久综合色婷婷| 在线成人亚洲| 欧美成人精品一区二区| 亚洲电影在线| aa级大片欧美三级| 欧美日韩国产综合视频在线观看中文 | 亚洲无线视频| 欧美一区二区三区视频免费| 国产日韩欧美在线看| 欧美在线|欧美| 老司机一区二区三区| 亚洲国产精品久久久久婷婷老年 | 亚洲另类一区二区| 宅男噜噜噜66一区二区66| 欧美色区777第一页| 一区二区三区色| 欧美一区二区三区免费观看| 国产一区免费视频| 久久久久一区| 亚洲欧洲日韩综合二区| 亚洲一区二区三区在线视频| 国产精品一级| 久久久久国产精品一区|