Dependency
A. First edition
This is first edition of my dependency class.
Can you imagine what is a dependency problem?
1. Suppose you have a sequence of courses to take and each course has 0 or more pre-requisite
courses. I want you to list all dependency relations.
2. Suppose you are writing a compiler, one of basic part is how to solve the forward references.
That is A is defined by B, B is defined by C... So, how to book keep the dependency relations.
3. Suppose you are writing a file to implement the functionality of "makefile". You need to establish
a dependency tree of all files.
It is actually a kind of edge list implementation of graph. Each node of list is actually a struct
which has a string as data, a link list of other strings which depends on it.
C.Further improvement
กก
#include <iostream> using namespace std; const int MaxListSize=40; struct Link { int data; Link* next; }; struct Vertex { char* str; Link* depend; }; class Depend { private: Vertex* lst[MaxListSize]; int size; void addNode(const char* str); void addSon(int index, int son); public: Depend(); ~Depend(); int getSize() { return size;} int find(const char* str); bool append(const char* str); bool remove(const char* str); void readFromFile(const char* fileName); void addDepend(int index, const char* str); void print(); }; int main() { Depend D; D.readFromFile("c:\\depend.txt"); D.print(); return 0; } void Depend::print() { Link* ptr; for (int i=0; i<size; i++) { cout<<"node no."<<i<<":"<<lst[i]->str<<" : "; ptr=lst[i]->depend; while (ptr!=NULL) { cout<<lst[ptr->data]->str<<" "; ptr=ptr->next; } cout<<endl; } } void Depend::addSon(int index, int son) { Link* ptr; ptr= lst[index]->depend; if (ptr==NULL) { ptr=new Link; ptr->data= son; ptr->next=NULL; lst[index]->depend=ptr; return; } while (ptr->next!=NULL) { if (ptr->next->data==son) { return;//already there } ptr=ptr->next; } //add new link ptr->next= new Link; ptr->next->data=son; ptr->next->next=NULL; } void Depend::addDepend(int index, const char* str) { int pos= find(str); Link* ptr; if (pos==-1) { append(str); pos=size-1;//size++ addSon(index, pos); } else { addSon(index, pos); ptr= lst[pos]->depend; while (ptr!=NULL) { addSon(index, ptr->data); ptr=ptr->next; } } } void Depend::addNode(const char* str) { char buffer[100]; int index; strcpy(buffer, str); char* ptr=buffer; ptr=strtok(ptr, " :\n"); index=find(ptr); if (index==-1) { append(ptr); index=size-1; } ptr=NULL; ptr=strtok(ptr, " :\n"); while (ptr!=NULL) { addDepend(index, ptr); ptr=NULL; ptr=strtok(ptr, " :\n"); } } void Depend::readFromFile(const char* fileName) { FILE* stream; char buffer[100]; if ((stream=fopen(fileName, "r"))==NULL) { cout<<"fail to read file "<<fileName<<endl; return; } while (fgets(buffer, 100, stream)!=NULL) { addNode(buffer); } fclose(stream); } Depend::~Depend() { for (int i=0; i<size; i++) { delete [] lst[i]->str; delete lst[i]; } } Depend::Depend() { size=0; } int Depend::find(const char* str) { for (int i=0; i<size; i++) { if (strcmp(str, lst[i]->str)==0) { return i; } } return -1; } bool Depend::append(const char* str) { if (find(str)!=-1) { return false; } lst[size]=new Vertex; lst[size]->depend=NULL; lst[size]->str=new char[strlen(str)+1]; strcpy(lst[size]->str, str); size++; return true; } bool Depend::remove(const char* str) { int index = find(str); if (index==-1) { return false; } delete [] lst[index]->str; lst[index]->str=NULL; delete lst[index]; size--; for (int i=index; i<size; i++) { lst[i]=lst[i+1]; } return true; }
Here is the result:
node no.0:238 : 228 node no.1:228 : node no.2:229 : 228 248 node no.3:248 : node no.4:239 : 238 228 node no.5:249 : 238 228 248 node no.6:352 : 239 238 228 249 248 node no.7:348 : 249 238 228 248 node no.8:335 : 239 238 228 249 248 Press any key to continue
Here is the input file:
238 : 228 229 : 228 248 239 : 238 249 : 238 248 352 : 239 249 348 : 249 335 : 239 249