ممنون از پاسختون، اما تابع Dijkstra آرایه دو بعدی نیاز داره..باید دو بعدی ارجاع بشه...
چون زمانم محدود بود، مجبور شدم کل پایه برنامه رو عوض کنم تا بدون نیاز به این کار آرایه رو به تابع بفرستم.. اما هنوز دوست دارم متوجه بشم که چطئر میشه آزایه دو بعدی رو ریترن کرد..!
یا اصلن مشکل چی بوده؟
برنامه ویرایش شده رو میزارم اینجا..
الگوریتم های BFS DFS DIJKSTRA PRIME رو از روی گراف شبیه سازی شده با لیست پیوندی و ماتریس وزن اجرا میکنه...
البته یه کم اشکال داره... با همه نوع گراف کار نمیکنه و کامل هم نیست-منو ها نیمه کاره موندن(گراف باید همیلتنی باشه)
الگوریتم پرایم هم به صورت کامنت کردم چون گاهی مشکل ایجاد می کرد.
ولی خب اگه کسی نیاز داشته باشه با کمی تغییر خیلی خوب جواب میده.
توابع STACk و queue در حد نیاز نوشته شده اند و از کتابخانه استفاده نشده.
محل همه ی کدها با کامنت جدا و دسته بندی شده.
//pooya amiri
#include <iostream>
#include "conio.h"
#include "stdlib.h"
#include "ctype.h"
using namespace std;
#define M 5
//~~~~~~~~~~~~~~~constants for dijkstra~~~~~~~~~~
#define INFINITY 100
#define MEMBER 1
#define NOMEMBER 0
//~~~~~~~~~~~~~~~~~~~~~~~~END~~~~~~~~~~~~~~~~~~~~~
char node[M + 2];
//~~~~~~~~~~~~~~~~~ADJ LIST~~~~~~~~~~~~~~~~~~~~~~~~~~~
class adjList {
friend class nodeList;
private:
int info;
int weight;
adjList *next;
};
//~~~~~~~~~~~~~~~~~~~~~NODE TYPE~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
class nodeType {
friend class nodeList;
private:
char info;
adjList *listPtr;
nodeType *nextNode;
};
//~~~~~~~~~~~~~~~~~~~~PRIME~~~~~~~~~~~~~~~~~~~~~
class prims
{
public:
int cost[M][M], tree[M][M];
int n;
void spanningtree(int);
void display(int);
};
//~~~~~~~~~~~~~~~~~~~~~~~~NODE LIST~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
class nodeList : public prims //public inheritance from PRIMS class
{
public:
nodeList();
~nodeList();
void makeGraph();
void print();
void depth();
void BFS();
void dijkstra(int w[][M], int , int , int *);
void makeWeightDIJ();
void prime();
private:
nodeType *start;
};
//~~~~~~~~~~~~~~~~~~~QUEUE~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~
class queue {
friend void nodeList::BFS();//friend of BFS function in nodeList clss
public:
queue();
int empty();
void addQ(adjList *);
adjList* qremove(void);
private:
adjList *items[M+1];
int front;
int rear;
};
//~~~~~~~~~~~~~~~STACK~~~~~~~~~~~~~
class stack {
friend void nodeList::depth(); //friend of depth function
public:
stack();
int empty();
private:
int myTop;
adjList *item[M + 1];
};
/*~~~~~~~~~~~~~~~~~DIJKSTRA~~~~~~~~~~~~~~~~~~~~~
IS WRITTEN BY FUNCTION
*/
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include "class header.h"
queue::queue()
{
front = 0;
rear = -1;
}
//~~~~~~~~~~~~~~~~~
int queue::empty()
{
if(rear < front)
return 1;
return 0;
}
//~~~~~~~~~~~~~~~~~~~~~~~~
void queue::addQ(adjList *x)
{
items[++rear] = x;
}
//~~~~~~~~~~~~~~~~~~~~~~
adjList* queue::qremove()
{
return items[front++];
}
//~~~~~~~~~~~~~~~~~~~~~~~~
nodeList::nodeList()
{
start = NULL; //walk around nodes and can access to adjLists
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~
nodeList::~nodeList()
{
nodeType *p;
while(start != NULL)
{
p = start;
start = start -> nextNode;
delete p;
}
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~
int stack::empty()
{
if(myTop == -1)
return 1;
else
return 0;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~
stack::stack()
{
myTop = -1;
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~
void nodeList::makeGraph()
{
nodeType *np, *eofnp = NULL;
adjList *ap, *eofap = NULL;
char data;
int num, i = 0;
int we;
static int counter=0;
while(1)
{
cout << "Enter data of a node:";
data = _getche(); //getche(); get a character not a string
cout << "\n";
if(data == '\r')
break;
else {
node[++i] = data;
np = new nodeType;
counter++;
np -> info = data;
np -> listPtr = NULL;
np -> nextNode = NULL;
if(start == NULL)
start = eofnp = np;
else {
eofnp -> nextNode = np;
eofnp = np;
}
eofap = NULL;
while(1)
{
cout << "Enter adjacy list node( -1 to end):";
cin >> num;
if(num == -1)
break;
ap = new adjList;
ap -> info = num;
ap -> next = NULL;
if(eofap == NULL)
{
eofnp -> listPtr = ap;
eofap = ap;
}
else {
eofap -> next = ap;
eofap = ap;
}//end of else
// Ask weight of adjacy
cout << "Enter weight:";
cin>>we;
ap->weight=we;
} //end of inner while
}//end of else
}//end of while
//~~~~~~~~~~ PASSING WEIGHT MATRIX TO PRIMES ALGORITHM~~~~~~~~~~~~~~~~~~~~~~~~
/* n=counter; //initionalzing for n(nuber of nodes)(N EXIST IN PRIME CLASS)
int j=0;
nodeType *Nodep;
Nodep=start;
adjList *Adjp;
int v[M][M];
while(Nodep!=NULL)
{
for(int i=0;Nodep!=NULL;i++)
{
Adjp=Nodep->listPtr;
j=0;
while(Adjp!= NULL)
{
v[i][j]=Adjp->weight;
Adjp=Adjp->next;
j++;
}
Nodep=Nodep->nextNode;
}
}
cost[M][M]=v[M][M];
spanningtree(1);
*/
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
void nodeList::print()
{
nodeType *np;
adjList *ap;
np = start;
cout << "\nAdjacy list is :\n";
while(np != NULL)
{
cout << np -> info << " -> ";
ap = np -> listPtr;
while(ap != NULL)
{
cout << ap -> info << " ";
ap = ap -> next;
}
cout << "\n";
np = np -> nextNode;
}
cout<<"\n\nmeaning of numbers:";
for(int k=1;k<M+1;k++)
cout<<k<<"="<<node[k]<<" ";
cout<<"\n";
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
void nodeList::depth()
{
stack s;
nodeType *h;
adjList *p, *q;
int status[M + 1];//1=un-visited, 2= pending, 3=visited(printed)
for(int i = 1; i <= M; i++)
status[i] = 1;// assume 1 to all of the nodes' status
p = new adjList;
p -> info = 1;
p -> next = start -> listPtr;
s.item[++(s.myTop)] = p; //push to stack
status[p -> info] = 2;
q = p;
cout << "Depth first traversal is:\n";
while(!(s.empty()))
{
p = s.item[(s.myTop) --]; //pop from stack
status[p -> info] = 3;
cout << node[p -> info] << " ";
h = start;
while(h != NULL) // find poped node inorder to push its adj
{
if(node[p -> info] == h -> info)
break;
h = h -> nextNode;
}
q = h -> listPtr;
while(q != NULL)
{
if(status[q -> info] == 1)
{
status[q -> info] = 2;
s.item[++(s.myTop)] = q; //push to stack
}//end of if
q = q -> next;
} //end of while
}//end of while
}//end of depth
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~
void nodeList::BFS()
{
queue Q;
nodeType *h;
adjList *p, *q;
int status[M + 1];//1=un-visited, 2= pending, 3=visited(printed)
for(int i = 1; i <= M; i++)
status[i] = 1;// assume 1 to all of the nodes' status
p = new adjList;
p -> info = 1;
p -> next = start -> listPtr;
Q.addQ(p);
status[p->info]=2;
q=p;
cout << "\n\n\n(BFS) breadth first traversal is:\n";
while(!(Q.empty()))
{
p=Q.qremove();
status[p->info]=3;
cout<<node[p->info]<<" ";
h=start;
while(h!=NULL)
{
if(node[p->info]==h->info)
break;
h=h->nextNode;
}
q=h->listPtr;
while(q !=NULL)
{
if(status[q->info]==1)
{
status[q->info]=2;
Q.addQ(q);
}
q=q->next;
}
}
}
void nodeList::makeWeightDIJ()
{
//##################--->>> MAKING WEIGHT MATRIX <<<<------###############
int j=0;
nodeType *nodep;
nodep=start;
adjList *adjp;
int v[M][M];
while(nodep!=NULL)
{
for(int i=0;nodep!=NULL;i++)
{
adjp=nodep->listPtr;
j=0;
while(adjp!= NULL)
{
v[i][j]=adjp->weight;
adjp=adjp->next;
j++;
}
nodep=nodep->nextNode;
}
}
//~~~~~~~~~~~~~ PASSING WEIGHT MATRIX TO DIJKSTRA ALGORITHM AND PRINTING VALUES~~~~~~~~~~~~~~~~~~~~
int pd,s=0,t=1;
dijkstra(v,s,t,&pd);
cout << "\nSource is:" << s << ", Destination is:" << t;
cout << "\nLength of shortest path is:" << pd;
}
void nodeList::dijkstra(int w[][M], int s, int t, int *pd)
{
int distance[M], found[M];
int current, i, k, dc;
int smallDist, newDist;
//initialization
for(i = 0; i < M; i++)
{
found[i] = NOMEMBER;
distance[i] = INFINITY;
}
found[s] = MEMBER;
distance[s] = 0;
current = s;
while(current != t)
{
smallDist = INFINITY;
dc = distance[current];
for(i = 0; i < M; i++)
if(found[i] == NOMEMBER)
{
newDist = dc + w[current][i];
if(newDist < distance[i])
distance[i] = newDist;
//determine the smallest distance
if(distance[i] < smallDist)
{
smallDist = distance[i];
k = i;
}
}//end of for, if
found[k] = MEMBER;
current = k;
}//end of while
*pd = distance[t];
}
void prims :: spanningtree(int src)
{
int visited[M], d[M], parent[M];
int i, j, k, min, u, v, stcost;
for (i = 1; i <= n; i++)
{
d[i] = cost[src][i];
visited[i] = 0;
parent[i] = src;
}
visited[src] = 1;
stcost = 0;
k = 1;
for (i = 1; i < n; i++)
{
min = 999;
for (j = 1; j <= n; j++)
{
if (!visited[j] && d[j] < min)
{
min = d[j];
u = j;
}
}
visited[u] = 1;
stcost = stcost + d[u];
tree[k][1] = parent[u];
tree[k++][2] = u;
for (v = 1; v <= n; v++)
if (!visited[v] && (cost[u][v] < d[v]))
{
d[v] = cost[u][v];
parent[v] = u;
}
}
int I;
cout << "\nThe Edges of the Mininum Spanning Tree are\n\n";
for (I = 1; I < n; I++)
cout << tree[i][1] << " " << tree[i][2] << endl;
cout << "\nThe Total cost of the Minimum Spanning Tree is : " << stcost;
}
void ask(void);
int main()
{
nodeList list;
system("cls");
list.makeGraph();
list.print();
list.depth();
list.BFS();
list.makeWeightDIJ();
_getch();
void ask();
_getch();
return 0;
}
void ask(void)
{
int s;
cout<<" please chose one of this algorithms to finde the shortest path";
switch(s)
{
case 1 : cout<<"0";
}
}
درخواست راهنمایی(عدم تطابق تایپ ها هنگام برگرداندن یک آرایه از تابع و استفاده در تابع دیگر)
نقل قول: درخواست راهنمایی(عدم تطابق تایپ ها هنگام برگرداندن یک آرایه از تابع و استفاده در تابع دیگر)
نقل قول: درخواست راهنمایی(عدم تطابق تایپ ها هنگام برگرداندن یک آرایه از تابع و استفاده در تابع دیگر)
قوانین ایجاد تاپیک در تالار
پاسخ با نقل قول