myapp1.cpp

数据结构168个实验程序,很全面

// myApp1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "iostream.h"

typedef struct node
{
	int indegree ; //节点入度
	int num;       //节点的位置编号
	int newnum;    //排序后的位置编号
}GNode;

typedef struct arc
{
	GNode * adjvex; //弧的临节点
	struct arc * nextarc; //下一个弧
}Arc;

int stackDeep; //记录栈的位置

void initStack(GNode* top)
{
	stackDeep = 0;
	top = new GNode[100];
};

//入栈
void push( GNode* node, GNode** top )
{
	top[stackDeep] = node;
	stackDeep++;
};

//出栈
GNode* pop(GNode** top)
{
	stackDeep --;
	GNode* node;
	node = top[stackDeep];
	top[stackDeep] = NULL;
	return node;
};

//该链表记录每个定点的单链表起点
Arc* link[6];
	
//查找顶点的第一个临节点
GNode * FirstAdj(GNode* node)
{
	if(link[node->num -1] != NULL)
		return (link[node->num -1])->adjvex;
	else return NULL;
};

//查找定点node的下一个临节点
GNode * NextAdj(GNode* top,GNode* node)
{
	Arc* tmp;
	tmp = link[top->num-1];
	while( tmp->adjvex->num != node->num )
	{
		tmp = tmp->nextarc;
	}
	if( tmp->nextarc != NULL)
		return tmp->nextarc->adjvex;
	else return NULL;
};

int main(int argc, char* argv[])
{
	GNode* v1 = new GNode;
	GNode* v2 = new GNode;
	GNode* v3 = new GNode;
	GNode* v4 = new GNode;
	GNode* v5 = new GNode;
	GNode* v6 = new GNode;
	Arc* arc1 = new Arc;
	Arc* arc2 = new Arc;
	Arc* arc3 = new Arc;
	Arc* arc4 = new Arc;
	Arc* arc5 = new Arc;
	Arc* arc6 = new Arc;
	Arc* arc7 = new Arc;
	Arc* arc8 = new Arc;

	v1->indegree = 0;
	v1->num = 1;

	v2->indegree = 2;
	v2->num = 2;

	v3->indegree = 1;
	v3->num = 3;

	v4->indegree = 2;
	v4->num = 4;

	v5->indegree = 3;
	v5->num = 5;

	v6->indegree = 0;
	v6->num = 6;

	arc1->adjvex = v4;
	arc1->nextarc = arc2;
	
	arc2->adjvex = v3;
	arc2->nextarc = arc3;

	arc3->adjvex = v2;
	arc3->nextarc = NULL;

	arc4->adjvex = v5;
	arc4->nextarc = arc5;

	arc5->adjvex = v2;
	arc5->nextarc = NULL;

	arc6->adjvex = v5;
	arc6->nextarc = NULL;

	arc7->adjvex = v5;
	arc7->nextarc = arc8;

	arc8->adjvex = v4;
	arc8->nextarc = NULL;

	link[0] = arc1;
	link[1] = NULL;
	link[2] = arc4;
	link[3] = arc6;
	link[4] = NULL;
	link[5] = arc7;

	//初始化栈
	GNode* top = NULL;
	initStack(top);

	push( v1,&top );
	push( v6,&top );
	int m = 0;
	GNode * v;
	GNode*  w;
    while( stackDeep != 0 )
	{
		v = pop(&top);
		m++;
		v->newnum = m;
		w = FirstAdj(v);
		while( w != NULL)
		{
			w->indegree--;
			if( w->indegree == 0 )
			{
				push(w,&top);
			}
			w = NextAdj(v,w);
		}		
	}
	cout<< "v1 num is: "<<v1->newnum <<endl;
	cout<< "v2 num is: "<<v2->newnum <<endl;
	cout<< "v3 num is: "<<v3->newnum <<endl;
	cout<< "v4 num is: "<<v4->newnum <<endl;
	cout<< "v5 num is: "<<v5->newnum <<endl;
	cout<< "v6 num is: "<<v6->newnum <<endl;

	delete [] top;
	delete v1;
	delete v2;
	delete v3;
	delete v4;
	delete v5;
	delete v6;

	delete arc1;
	delete arc2;
	delete arc3;
	delete arc4;
	delete arc5;
	delete arc6;
	delete arc7;
	delete arc8;

	return 0;
}