久久精品国产一区,久久SE精品一区二区,热久久这里只有精品

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開始。且第一個節點有存有數據。

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 夢在天涯閱讀(2454) 評論(6) 編輯收藏引用所屬分類: CPlusPlus 、Data Arithmetic

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

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

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

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

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 動態鏈接庫dll 靜態鏈接庫lib 動態導入庫lib 2道C++面試題 .h頭文件 .lib庫文件 .dll動態鏈接庫文件關系 C++強大的背后 Lnuix/Unix上C++開發使用啥工具 C++對象模型 C++的異常[轉載] 《windows via C++》之windows線程同步 dynamic_cast使用的討論 C++ 虛函數表解析（轉）

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

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

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

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

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

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

C++ Programmer's Cookbook

c＋＋單向鏈表（討論應不應該在默認的構造里就分配空間）

評論

公告

導航

統計

常用鏈接

隨筆分類

隨筆檔案

收藏夾

Blogs

c#(csharp)

C++(cpp)

Enlish

Forums(bbs)

My self

Often go

Useful Webs

Xml/Uml/html

搜索

積分與排名

最新評論

閱讀排行榜

C++ Programmer's Cookbook

c＋＋單向鏈表 （討論應不應該在默認的構造里就分配空間）

評論

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

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

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

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

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

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

公告

導航

統計

常用鏈接

隨筆分類

隨筆檔案

收藏夾

Blogs

c#(csharp)

C++(cpp)

Enlish

Forums(bbs)

My self

Often go

Useful Webs

Xml/Uml/html

搜索

積分與排名

最新評論

閱讀排行榜

c＋＋單向鏈表（討論應不應該在默認的構造里就分配空間）

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

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

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

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

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

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