首页 > 其他分享 >数据结构实验----邻接表和拓扑排序

数据结构实验----邻接表和拓扑排序

时间:2024-08-02 09:26:48浏览次数:13  
标签:return int 拓扑 ---- ++ ArcNode printf 数据结构 vertexs

一.实验目的

1.理解拓扑排序的特性和算法;

2.通过构造图的邻接表,掌握拓扑排序算法。

二.实验内容

1.建立邻接表存储的图;

2.对图进行拓扑排序;

3.输出拓扑排序序列。

三.代码

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h>

#define MAXSIZE 10 
#define OK 1 
#define ERROR 0 
#define TRUE 1 
#define FALSE 0 
#define MAX_VERTEX_NUM 20

typedef int Elemtype;
typedef struct {
	Elemtype data[MAXSIZE];
	int top;
} SqStack;

int InitStack(SqStack &S) {
	S.top = -1;
	return OK;
}

int StackEmpty(SqStack S) {
	return (S.top == -1 ? TRUE : FALSE);
}

int StackFull(SqStack S) {
	return (S.top == MAXSIZE - 1 ? TRUE : FALSE);
}

int Push(SqStack &S, Elemtype e) {
	if (StackFull(S)) return ERROR;
	S.top++;
	S.data[S.top] = e;
	return OK;
}

int Pop(SqStack &S, Elemtype &e) {
	if (StackEmpty(S)) return ERROR;
	e = S.data[S.top];
	S.top--;
	return OK;
}

typedef struct ArcNode {
	int adjvex;
	struct ArcNode *nextarc;
	char *info;
} ArcNode;

typedef struct VNode {
	int data;
	ArcNode *firstarc;
} VNode;

typedef struct {
	VNode vertexs[MAX_VERTEX_NUM];
	int vexnum, arcnum;
	char kind;
} ALGraph;

void FindInDegree(ALGraph G, int indegree[]) {
	for (int i = 0; i < G.vexnum; i++) indegree[i] = 0;
	for (int i = 0; i < G.vexnum; i++) {
		ArcNode *p = G.vertexs[i].firstarc;
		while (p) {
			int k = p->adjvex;
			indegree[k]++;
			p = p->nextarc;
		}
	}
}

int TopologicalSort(ALGraph G) {
	int indegree[MAX_VERTEX_NUM];
	FindInDegree(G, indegree);
	SqStack S;
	InitStack(S);
	int count = 0;
	for (int i = 0; i < G.vexnum; i++) {
		if (indegree[i] == 0) Push(S, i);
	}
	while (!StackEmpty(S)) {
		int n;
		Pop(S, n);
		printf("%d ", G.vertexs[n].data);
		count++;
		ArcNode *p;
		for (p = G.vertexs[n].firstarc; p != NULL; p = p->nextarc) {
			int k = p->adjvex;
			if (!(--indegree[k])) Push(S, k);
		}
	}
	if (count < G.vexnum) return FALSE;
	else return TRUE;
}

void CreateGraph(ALGraph &G) {
	G.kind = 'D';
	printf("请输入顶点数和边数:");
	scanf("%d%d", &G.vexnum, &G.arcnum);
	printf("请输入各个顶点的值:\n");
	for (int i = 0; i < G.vexnum; i++) {
		printf("第 %d 个顶点的值:", i + 1);
		scanf("%d", &G.vertexs[i].data);
		G.vertexs[i].firstarc = NULL;
	}
	int u, v;
	for (int i = 0; i < G.arcnum; i++) {
		printf("请输入第 %d 条边的两个端点:", i + 1);
		scanf("%d%d", &u, &v);
		ArcNode *p = (ArcNode *) malloc(sizeof(ArcNode));
		p->adjvex = v;
		p->info = NULL;
		p->nextarc = G.vertexs[u].firstarc;
		G.vertexs[u].firstarc = p;
	}
}

void PrintAL(ALGraph G) {
	printf("各个顶点的邻接表如下:\n");
	for (int i = 0; i < G.vexnum; i++) {
		printf("[%d] %d ->", i, G.vertexs[i].data);
		ArcNode *p = G.vertexs[i].firstarc;
		while (p != NULL) {
			printf(" %d", p->adjvex);
			p = p->nextarc;
		}
		printf("\n");
	}
}

int main() {
	ALGraph G;
	CreateGraph(G);
	printf("初始图:\n");
	PrintAL(G);
	printf("拓扑排序:\n");
	TopologicalSort(G);
	return 0;
}         

标签:return,int,拓扑,----,++,ArcNode,printf,数据结构,vertexs
From: https://blog.csdn.net/2301_79235379/article/details/140863385

相关文章

  • 数据结构实验---散列表
    一.实验目的1.理解散列表的存储结构;2.掌握常用散列函数构造方法和处理冲突方法;3.在散列表上实现查找的算法。二.实验内容为小于n个关键字设计一个散列表,使得查找成功时平均查找长度<2.0,要求完成相应的散列表建立和查找。假设关键字为整型数据,散列函数用除留余数法,采用开放......
  • 【网络安全】LockBit病毒入侵揭秘:如何防范与应对
    文章目录前言主要特征攻击手段演进历程主要威胁防范与对策==如何入门学习网络安全【黑客】==【----帮助网安学习,以下所有学习资料文末免费领取!----】大纲学习教程面试刷题资料领取前言在数字时代,随着科技的飞速发展,网络安全问题愈发凸显。恶意软件和勒索软件等网络......
  • “外挂”——逆向软件的分析与破解
    本文来源无问社区,更多实战内容,渗透思路可前往查看http://www.wwlib.cn/index.php/artread/artid/11458.html#maodian1前言:“外挂”的制作离不开软件的分析破解,这平时做ctf中的逆向题是有⼀定的差别的。最直观的区别体现在两者的⼤⼩。⼀个逆向题⼀般只有⼀两兆⼤⼩,⽽⼀般的软......
  • HTML基础笔记
    1.HTML语法规范1.1基本语法概述1.HTML标签是由尖括号包围的关键词,例如<html>2.HTML通常是成对出现的,叫做双标签,分别是开始标签,结束标签。<html></html>3。有些特殊的标签必须是单标签。<br/>1.2标签关系双标签关系可以分为两类:包含关系和并列关系。<html><head......
  • 连载|浅谈红队中的权限维持(六)-Linux 主机后门与Linux 隐藏文件
    本文来源无问社区,更多实战内容,渗透思路可前往查看http://www.wwlib.cn/index.php/artread/artid/11584.html0x01Linux主机后门1、添加用户一句话添加用户useraddtest;echo-e"123456n123456n"|passwdtest或者使用openssluseradd-popensslpasswd-1-salt'salt'12......
  • 如何在Linux上配置虚拟主机
    在Linux上配置虚拟主机可以通过使用ApacheHTTP服务器来实现。Apache是一个开源的跨平台的Web服务器软件,可以在多种操作系统上运行并支持虚拟主机的配置。以下是在Linux上配置虚拟主机的步骤:安装ApacheHTTP服务器在终端中运行以下命令来安装Apache:sudoapt-getupdatesu......
  • 反序列化漏洞vulhub靶场serial
    环境搭建下载https://download.vulnhub.com/serial/serial.zip解压出来就是这种 你会得到一个这样的文件,这里使用VMware新建一个虚拟机,这里记录比较重要的几部分。这里就是使用我们刚才下过来的。  漏洞过程详解1.信息收集打开靶机,在kali虚拟机中进行主机......
  • PCDN技术如何提高数据传输的可靠性?
    PCDN技术通过以下方式提高数据传输的可靠性:1.负载均衡与故障转移:PCDN系统具备负载均衡的能力,可以根据节点的负载情况动态分配请求,避免单点故障和过载情况。此外,当某个节点发生故障时,PCDN可以迅速将流量转移到其他可用节点,确保数据传输的连续性。2.数据备份与冗余:为了提......
  • Android 11.0 Launcher修改density禁止布局改变功能实现
    1.前言在11.0的系统rom定制化开发中,在关于Launcher3的定制化功能中,在有些功能需要要求改变系统原有的density屏幕密度,这样就会造成Launcher3的布局变化,所以就不符合要求,接下来就来看下如何禁止改变density造成Launcher3布局功能改变的实现2.Launcher修改density禁止布局改......
  • 最短路计数
    //最短路计数.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。///**https://loj.ac/p/10077【题目描述】给出一个N个顶点M条边的无向无权图,顶点编号为1∼N。问从顶点1开始,到其他每个点的最短路有几条。输入格式第一行包含2个正整数N,M,为图的顶......