skyli
C++之夢

隨筆 - 62 文章 - 96 trackbacks - 0

2025年11月

>

日

一

二

三

四

五

六

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

常用鏈接

留言簿(7)

隨筆分類(66)

隨筆檔案(62)

文章分類(31)

文章檔案(32)

友情鏈接

校內(nèi)網(wǎng)

積分與排名

積分 - 237606
排名 - 108

閱讀排行榜

評論排行榜

一道算法題引發(fā)的動態(tài)內(nèi)存管理的思考

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

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;

}

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

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

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

依此算法優(yōu)化后，得到的結(jié)果比較滿意
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;