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

C++ Programmer's Cookbook

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

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

// ?IntLink.cpp?:?Defines?the?entry?point?for?the?console?application.
 //
//
 /**/ //////////////////////////////////////////////////////////////////////// //
// 作者：夢(mèng)在天涯
 // 單向鏈表類(lèi)
/**/ //////////////////////////////////////////////////////////////////////// //
//
//
 #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)號(hào)是從0開(kāi)始。且第一個(gè)節(jié)點(diǎn)有存有數(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開(kāi)始，即第一個(gè)值也即頭指針為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?為要?jiǎng)h除的值的位置
??????? {??????
???????? 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.

別人寫(xiě)的：
#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ù)項(xiàng)類(lèi)

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

//函數(shù)實(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 夢(mèng)在天涯 閱讀(2472) 評(píng)論(6)  編輯 收藏 引用 所屬分類(lèi): CPlusPlus 、Data Arithmetic

評(píng)論

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

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

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

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

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

樓上的樓上說(shuō)的拷貝構(gòu)造函數(shù)是不是每個(gè)節(jié)點(diǎn)都的重新new，啊？  回復(fù)  更多評(píng)論   

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

請(qǐng)問(wèn)采用template<class T>的方式有什么好處呢?
  回復(fù)  更多評(píng)論   

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

好處當(dāng)然是不言自明咯，算法嚴(yán)謹(jǐn)，安全，可重用性高……
  回復(fù)  更多評(píng)論   

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

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

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

順便多句嘴，鏈表如果>100000項(xiàng)，盡量考慮RedBlackTree或者M(jìn)ap/HashMap，這樣查找的性能比鏈表高的多得多得多得多得多，而插入最末項(xiàng)的性能也并會(huì)不比鏈表慢。尤其如果鏈表需要進(jìn)行按順序插入合適的位置，那么那個(gè)速度- -！我想你看到了，會(huì)以為死機(jī)了。

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

公告

EMail：itech001#126.com

導(dǎo)航

統(tǒng)計(jì)

  • 隨筆 - 461
  • 文章 - 4
  • 評(píng)論 - 746
  • 引用 - 0

常用鏈接

隨筆分類(lèi)

隨筆檔案

收藏夾

Blogs

c#(csharp)

C++(cpp)

Enlish

Forums(bbs)

My self

Often go

Useful Webs

Xml/Uml/html

搜索

  •  

積分與排名

  • 積分 - 1812984
  • 排名 - 5

最新評(píng)論

閱讀排行榜

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

    • <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>
              
99视频一区二区|
一区二区三区在线看|
99精品视频免费观看视频|
欧美华人在线视频|
欧美成人嫩草网站|
亚洲一区二区三区涩|
亚洲午夜精品久久|
国内成+人亚洲|
欧美激情一区二区三区成人|
欧美插天视频在线播放|
亚洲精品乱码久久久久久按摩观|
国产午夜精品全部视频播放
|
欧美二区视频|
一区二区三区欧美日韩|
亚洲一区二区成人在线观看|
国产一区二区三区最好精华液
|
在线亚洲自拍|
亚洲欧美影音先锋|
亚洲国产精品v|
一本色道久久综合亚洲精品小说
|
国产伦精品一区二区三|
欧美11—12娇小xxxx|
欧美日韩福利视频|
欧美一级在线亚洲天堂|
蜜臀久久久99精品久久久久久|
99re这里只有精品6|
午夜精品视频在线观看一区二区|
激情校园亚洲|
亚洲视频www|
91久久亚洲|
羞羞漫画18久久大片|
一道本一区二区|
久久国产精品网站|
亚洲一区二区视频在线|
久久天天躁狠狠躁夜夜爽蜜月|
亚洲视频 欧洲视频|
久久久爽爽爽美女图片|
亚洲欧美另类在线观看|
欧美精品久久久久久久久久|
久久久久久网|
国产日韩欧美精品综合|
91久久国产自产拍夜夜嗨|
国产女主播一区|
亚洲乱码久久|
亚洲国产老妈|
久久乐国产精品|
欧美伊人久久|
国产精品日韩欧美一区二区三区|
亚洲高清在线|
亚洲福利电影|
久久精品夜色噜噜亚洲a∨|
欧美一区二区三区在线视频|
欧美日韩国产小视频在线观看|
欧美激情亚洲另类|
在线免费观看欧美|
久久精品成人一区二区三区|
久久久久看片|
国产一区二区三区视频在线观看|
亚洲欧美国产日韩中文字幕|
性伦欧美刺激片在线观看|
欧美日韩中文字幕在线|
日韩亚洲视频在线|
亚洲专区欧美专区|
国产精品99免费看
|
久久全球大尺度高清视频|
亚洲免费视频网站|
欧美先锋影音|
亚洲一区日韩在线|
欧美一区在线直播|
国语精品中文字幕|
欧美主播一区二区三区|
久久精品国产视频|
激情欧美一区二区|
免费观看成人鲁鲁鲁鲁鲁视频|
免费在线观看精品|
亚洲日本欧美|
欧美日韩精品在线播放|
在线亚洲观看|
久久精品亚洲一区二区三区浴池|
国产一区二区久久|
噜噜噜噜噜久久久久久91|
欧美国产日韩一区二区在线观看|
亚洲精品国产精品乱码不99按摩|
欧美国产日韩精品|
亚洲另类自拍|
久久国产一区二区|
亚洲高清免费在线|
欧美日韩在线精品|
欧美一区永久视频免费观看|
美玉足脚交一区二区三区图片|
亚洲国产精品尤物yw在线观看|
欧美日韩xxxxx|
欧美一区二区高清在线观看|
欧美顶级少妇做爰|
亚洲在线日韩|
精品1区2区|
欧美日韩一区二区在线视频|
欧美一区二区三区在线观看视频|
亚洲国产导航|
欧美一区二区三区免费观看视频
|
亚洲在线播放|
亚洲国产日韩欧美在线图片|
国产精品porn|
久久综合亚州|
亚洲免费网址|
亚洲美女91|
欧美激情视频在线播放|
亚洲欧美在线免费观看|
亚洲国产综合在线|
国产一区二区丝袜高跟鞋图片|
欧美激情精品久久久久|
久久大香伊蕉在人线观看热2|
91久久精品一区二区三区|
久久久久久久综合日本|
亚洲欧美日韩国产一区|
亚洲国产专区|
影音先锋日韩精品|
国产精品亚洲网站|
欧美日韩www|
欧美成人精品一区|
久久久噜噜噜久久|
欧美一区二视频|
亚洲综合日韩在线|
一区二区日韩伦理片|
欧美成va人片在线观看|
久久免费国产精品|
久久不见久久见免费视频1|
在线视频免费在线观看一区二区|
亚洲国产精品久久久久|
国产一区二区视频在线观看|
国产精品久久激情|
欧美日韩国产123|
欧美jizz19性欧美|
欧美成人一区二区三区片免费|
久久久久久九九九九|
尤物网精品视频|
国产亚洲在线观看|
国产精品永久免费观看|
国产精品高清免费在线观看|
欧美精品自拍|
欧美精品一区三区|
欧美区一区二|
欧美视频在线看|
国产精品ⅴa在线观看h|
国产精品国产a|
国产精品一区三区|
国产日韩一区欧美|
国内精品久久久久久久影视麻豆|
国产一区二区三区免费在线观看
|
国产日韩欧美高清|
国产一区二区观看|
国产一级一区二区|
伊伊综合在线|
亚洲欧洲日韩综合二区|
亚洲美女av网站|
亚洲视频综合在线|
久久大综合网|
美女主播一区|
日韩天堂av|
亚洲主播在线播放|
久久精品国产欧美亚洲人人爽|
久久久国产成人精品|
欧美成人蜜桃|
国产精品一级二级三级|
尤物网精品视频|
一区二区三区欧美在线观看|
亚洲免费视频网站|
久热精品在线视频|
亚洲精品免费在线观看|
av成人黄色|
久久精品2019中文字幕|
欧美激情亚洲视频|
国产农村妇女精品一二区|
在线观看一区视频|
在线亚洲欧美视频|
久久久久久噜噜噜久久久精品|
亚洲国产欧美日韩另类综合|
亚洲新中文字幕|
欧美3dxxxxhd|
国产日韩欧美一区二区|
日韩午夜电影|
久久午夜色播影院免费高清|
91久久精品一区二区三区|
性高湖久久久久久久久|
欧美精品乱人伦久久久久久
|
国产在线观看91精品一区|
亚洲精品一区二区三区樱花|
亚洲制服av|
亚洲第一精品福利|
欧美一级久久久|
欧美无砖砖区免费|
亚洲人成网站精品片在线观看|
欧美亚洲视频|
99精品视频免费观看视频|
久久琪琪电影院|
国产精品网站在线|
亚洲一区二区日本|
亚洲国产精品成人综合|
久久久久久伊人|
国产日韩视频|