欧美人在线观看,午夜精品电影,蜜桃av一区二区三区

友情鏈接

最新評論

1.?re: 優先隊列用法
評論內容較長,點擊標題查看
--tanti
2.?re: 優先隊列用法
給力！！
--***
3.?re: pow函數的性能測試
Pow 函數要處理各種非整數次冪情況，比如0.5就等于開根號了，0.2就等于開5次方了。當然比直接乘慢的多。
--YYX
4.?re: istringstream用法[未登錄]
@gong
cin是標準輸入，在std中已經聲明了。
--mm
5.?re: istringstream用法[未登錄]
您好，為什么這里的getline(cin, line）中的cin沒有定義就直接使用了呢？
--gong

閱讀排行榜

評論排行榜

一道算法題引發的動態內存管理的思考

在做PKU2762時，需要建鄰接表。
于是按部就班寫了下面一個插入邊到鄰接表中的函數：

const int VMAX = 1010;

typedef struct Graph

{

int vex;

Graph* next;

}Graph;

Graph ArcGraph[VMAX];

void insert(int u, int v)

{

Graph* t = new Graph;

Graph* p = ArcGraph[u].next;

t->vex = v;

t->next = p;

ArcGraph[u].next = t;

}

完成完整的程序提交上去，得到結果
Memory:25796K Time:375MS
Language:C++ Result:Accepted

再對比別人的程序
Memory:296K Time:109MS

無論是時間還是空間都相差很大。
于是就考慮怎么優化自己的程序。
第一個問題：規模只有1000，為什么會用那么多內存呢？
仔細一想數據是多case的，每次插入新節點時都要動態創建一個節點。
一來動態創建耗時間，二來每個case結束的鄰接表中的節點沒有釋放，故耗費大量內存。
然后就想到了下面的算法，首先初始化一塊內存Graph use[100*VMAX];這樣每次需要新節點時，
就從use中獲取。如果use使用完畢就再動態創建。

依此算法優化后，得到的結果比較滿意
Memory:1000K Time:218MS
Language:C++ Result:Accepted

const int VMAX = 1010;

typedef struct Graph

{

int vex;

Graph* next;

}Graph;

Graph ArcGraph[VMAX];

Graph use[100*VMAX];

int size = 0;

void insert(int u, int v)

{

Graph* t;

if(size < 100*VMAX)

{

t = &use[size];

size++;

}

else t = new Graph;

Graph* p = ArcGraph[u].next;

t->vex = v;

t->next = p;

ArcGraph[u].next = t;

}

posted on 2007-08-13 00:29 beyonlin 閱讀(1564) 評論(0) 編輯收藏引用所屬分類: acm之路、C++之路

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

相關文章: pow函數的性能測試一道算法題引發的動態內存管理的思考篩法求素數字符串hash函數插入排序泛型算法最大匹配匈牙利算法最小生成樹Prim算法 itoa函數歸并排序求逆序數單源最短路徑Dijkstra算法

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

常用鏈接

留言簿(7)

隨筆分類(66)

隨筆檔案(62)

文章分類(31)

文章檔案(32)

友情鏈接

最新隨筆

積分與排名

最新評論

閱讀排行榜

評論排行榜