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

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開始。且第一個節點有存有數據。
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 夢在天涯 閱讀(2471) 評論(6)  編輯 收藏 引用 所屬分類: CPlusPlusData Arithmetic

評論

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

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

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

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

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

樓上的樓上說的拷貝構造函數是不是每個節點都的重新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倍,而且極易留下后患。尤其在對安全性和穩定性較高的領域,寧可犧牲些許性能,也要盡量保證安全。

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

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

公告

EMail:itech001#126.com

導航

統計

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

常用鏈接

隨筆分類

隨筆檔案

收藏夾

Blogs

c#(csharp)

C++(cpp)

Enlish

Forums(bbs)

My self

Often go

Useful Webs

Xml/Uml/html

搜索

  •  

積分與排名

  • 積分 - 1812196
  • 排名 - 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>
              一区二区三区免费看| 久久亚洲影院| 亚洲男人的天堂在线观看| 韩日成人在线| 韩国美女久久| 国产情人综合久久777777| 欧美亚州韩日在线看免费版国语版| 欧美激情一区二区三区成人| 快射av在线播放一区| 美女精品一区| 欧美视频国产精品| 国产精品久久二区| 亚洲欧美一区二区三区久久| 欧美一区二区视频观看视频| 欧美一区二区在线免费播放| 亚洲精品免费观看| 99视频一区二区三区| 久久中文欧美| 亚洲电影免费在线观看| 亚洲午夜精品久久久久久浪潮| 久久在线91| 中文日韩电影网站| 欧美日韩在线视频一区| 亚洲一区二区三区在线看 | 久久久久九九九九| 久久夜色精品亚洲噜噜国产mv| 久久一区二区精品| 国产精品va| 国产亚洲成人一区| 尤物yw午夜国产精品视频明星| 一区二区三区视频免费在线观看| 亚洲欧美日韩成人| 久热re这里精品视频在线6| 日韩一区二区高清| 欧美中文字幕在线观看| 欧美成人免费网站| 黄色精品网站| 妖精视频成人观看www| 99精品国产福利在线观看免费 | 亚洲欧美日韩精品久久久久| 欧美一区二区三区免费观看 | 激情欧美日韩| 99国产成+人+综合+亚洲欧美| 亚洲欧美中文字幕| 亚洲毛片在线观看| 久久精品免费播放| 一二三区精品| 久久久免费观看视频| 国产精品a久久久久| 激情六月综合| 久久九九久精品国产免费直播| 欧美第一黄色网| 亚洲在线播放电影| 国产精品久久7| 亚洲国产一区二区视频| 毛片一区二区三区| 亚洲欧美不卡| 欧美三级免费| 亚洲一区三区电影在线观看| 欧美成人国产va精品日本一级| 亚洲一区二区网站| 国产精品裸体一区二区三区| 亚洲人屁股眼子交8| av成人福利| 日韩一级在线| 免费在线成人| 亚洲精品国产拍免费91在线| 亚洲在线电影| 猛男gaygay欧美视频| 久久久av网站| 久久夜色精品国产| 亚洲午夜一区| 国产精品久久国产精品99gif | 亚洲一区二区成人在线观看| 欧美国产在线视频| 日韩视频久久| 亚洲电影视频在线| 久久亚洲国产精品一区二区| 欧美一区二区三区视频免费| 国产精品一区二区欧美| 久久久国产精品一区二区中文| 亚洲一区二区三区免费在线观看| 欧美理论电影在线观看| 亚洲午夜激情网站| 在线一区二区日韩| 久久久久国产精品厨房| 91久久久久| 91久久精品国产91性色| 欧美色视频在线| 亚洲欧美日韩直播| 午夜精品福利一区二区三区av| 一区在线免费观看| 男人的天堂亚洲在线| 欧美一级午夜免费电影| 影音先锋在线一区| 欧美成人一区二免费视频软件| 欧美女人交a| 亚洲自拍电影| 午夜精品www| 99精品热6080yy久久| 日韩视频一区二区| 欧美理论电影在线播放| 久久另类ts人妖一区二区 | 久久成年人视频| 亚洲精品色婷婷福利天堂| 一区二区三区**美女毛片| 国语精品一区| 亚洲人永久免费| 国产精品裸体一区二区三区| 欧美大片在线观看| 欧美日韩国产一级片| aⅴ色国产欧美| 亚洲免费一在线| 极品少妇一区二区三区| 亚洲免费在线精品一区| 亚洲国产日韩在线一区模特| 亚洲素人一区二区| 久久久午夜电影| 亚洲永久在线| 欧美日本久久| 免费观看久久久4p| 欧美亚洲一区| 午夜精品久久久久久久久久久久久 | 99国产精品99久久久久久| 国产欧美二区| 欧美激情久久久久久| 国内精品福利| 在线综合亚洲| 一本色道久久| 久久影视精品| 999亚洲国产精| 欧美一区二区久久久| 99re6热只有精品免费观看| 欧美在线啊v| 亚洲欧美卡通另类91av| 欧美日韩在线不卡一区| 欧美成人按摩| 伊人久久大香线蕉av超碰演员| 宅男精品视频| 一区二区三区免费看| 欧美午夜电影在线观看| 亚洲高清在线| 亚洲免费激情| 另类国产ts人妖高潮视频| 欧美中在线观看| 国产婷婷成人久久av免费高清| 99精品欧美一区| 亚洲在线视频免费观看| 欧美成人综合一区| 蜜桃久久av一区| 亚洲日本在线视频观看| 久久久久成人精品| 欧美激情一区二区三区蜜桃视频| 国产在线观看91精品一区| 亚洲——在线| 久热综合在线亚洲精品| 国产一区亚洲| 农村妇女精品| 亚洲国产精品成人一区二区 | 在线观看一区二区视频| 久久精品国产亚洲高清剧情介绍| 欧美一区二区黄色| 国产日韩欧美在线| 欧美在线日韩在线| 免费不卡在线观看av| 红桃视频亚洲| 久久精品夜色噜噜亚洲a∨| 亚洲第一偷拍| 亚洲精品久久嫩草网站秘色| 中文亚洲欧美| 久久中文久久字幕| 91久久精品美女高潮| 国产精品久久午夜夜伦鲁鲁| 亚洲综合欧美日韩| 嫩草国产精品入口| 99ri日韩精品视频| 国产精品成人在线观看| 久久在线视频| 亚洲精品在线观看免费| 久久精品国产999大香线蕉| 国产美女一区二区| 久久精品视频在线| 亚洲视频第一页| 久久高清国产| 亚洲视频一二区| 一本一本久久a久久精品综合妖精 一本一本久久a久久精品综合麻豆 | 一区二区三区成人精品| 亚洲激情另类| 欧美中文字幕在线视频| 久久久欧美精品sm网站| 国产日韩在线播放| 亚洲色图制服丝袜| 亚洲午夜国产成人av电影男同| 韩日在线一区| 免费亚洲一区| 久久精品国产亚洲高清剧情介绍| 欧美成年人网站| 亚洲第一中文字幕在线观看| 国产精品一香蕉国产线看观看 | 9i看片成人免费高清|