資料結構(9)

第九章 Storage Management

A list is simply a sequence of objects called elements. Associated with each list element is a value.

q=nullelt;

p=first(list);

while(p!=nullelt)

{

if(info(p)=='w')

{

/*remode node(p) from the list*/

p=next(p);

if(q == nullelt)

setnext(q,p);

}

else

{

p=q;

p=next(p);

}

}

#define INTGR 1

#define CH 2

#define LST 3

struct nodetype{

int utype;

union{

int intgrinfo;

char charinfo;

struct nodetype *listinfo;

} info;

struct nodetype *next;

};

typedef struct nodetype *NODEPTR;

NODEPTR tail(NODEPTR list)

{

if(list==NULL)

{

printf(“illegal tail operation”);

exit(1);

}

else

return list->next;

}

struct {

int utype;

union{

int intgrinfo;

char charinfo;

struct nodetype *listinfo;

} info;

} infotype;

typedef struct infotype *INFOPTR;

void head(NODEPTR list,INFOPTR pitem)

{

if(list==NULL)

{

printf(“illegal head operation”);

exit(1);

}

pitem = (INFOPTR) malloc (sizeof(struct infotype));

pitem->utype=list->utype;

pitem->info=list->info;

return;

}

NODEPTR addon(NODEPTR list,struct infotype *pitem)

{

NODEPTR newptr;

newptr=(INFOPTR)malloc(sizeof(struct nodetype));

newptr->utype=pitem->utype;

newptr->info = pitem->info;

newptr->next=list;

return newptr;

}

void settail(NODEPTR *plist,NODEPTR t1)

{

NODEPTR p;

p=*plist->next;

*plist->next=t1;

freelist(p);

}

Reference Count Method

Under this method each node has an additional count field that keeps a count (called the reference count) of the number of pointers(both internal and external) to that node.

Collection and Compaction

for(i=1;i<MAXNODES;i++)

{

node[i].header=0;

node[i].headptr='N';

node[i].infoptr='N';

node[i].nextptr='N';

}

newloc=0;

for(nd=1;nd<MAXNODES;nd++)

if(node[nd].mark==TRUE)

newloc++;

p=node[nd].header;

source = node[nd].headptr;

while(p!=0)

if(source=='I')

{

q=node[p].lstinfo;

source=node[p].infoptr;

node[p].lstinfo=newloc;

node[p].infoptr='N';

p=q;

}

else

{

q=node[p].next;

source=node[p].nextptr;

node[p].next=newloc;

node[p].nextptr='N';

p=q;

}

node[nd].headptr='N';

node[nd].header=0;

if((node[nd].utype==LST)&&(node[nd].lstinfo!=0))

{

p=node[nd].lstinfo;

node[nd].lstinfo=node[p].header;

node[nd].infoptr=node[p].headptr;

node[p].header=nd;

node[p].headptr='I';

}

p=node[nd].next;

node[nd].next=node[p].header;

node[nd].nextptr=node[p].headptr;

if(p!=0)

{

node[p].header=nd;

[node[p].headptr='L';

}

}

newloc=0;

for(nd=1;nd<MAXNODES;nd++)

if(node[nd].mark)

{

newloc++;

p=node[nd].header;

source = node[nd].headptr;

while(p!=0)

if(source=='I')

{

q=node[p].lstinfo;

source=node[p].infoptr;

node[p].lstinfo=newloc;

node[p].infoptr ='N';

p=q;

}

else

{

q=node[p].next;

source=node[p].nextptr;

node[p].next=newloc;

node[p].nextptr ='N';

p=q;

}

node[nd].headptr='N';

node[nd].header=0;

node[nd].mark=false;

node[newloc]=node[nd];

}