C语言链表、树、图的实现（结构体）

发布时间：2024年01月03日

链表、树、图

链表

树

struct Tree{
	int val;
	struct Tree *left;
	struct Tree *right;
};

在上面的代码中，每一部分都是定义二叉树节点所必需的，所以没有多余的可以删除的部分。但是，如果你想简化代码或使其更加清晰，你可以考虑下面：

使用typedef的同时定义结构体，这样可以避免在结构体内部重复使用struct关键字。这是C语言中常见的做法：

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

在这个例子中，虽然你在结构体内部还是用了struct TreeNode，但是在定义完结构体之后，你可以直接使用TreeNode来声明变量，而不需要再次使用struct关键字。

然而，有些C编译器（如GCC和Clang）支持一种扩展语法，允许你在typedef的同时，也在结构体内部使用新定义的别名，而不需要前缀struct。这种写法在C++中是标准的，但在C中只是某些编译器的扩展：

typedef struct TreeNode {
    int val;
    TreeNode *left;  // 注意这里直接使用TreeNode而不是struct TreeNode
    TreeNode *right; // 同上
} TreeNode;

如果你确定你的编译器支持这种扩展语法，并且你希望代码更加简洁，你可以选择使用这种写法。但是，为了保持代码的可移植性，最好还是坚持使用标准的C语法，即在结构体内部使用struct TreeNode。

总结来说，你的原始代码已经是定义二叉树节点的标准方式，没有任何可以删除的部分，除非你打算使用编译器的特定扩展。

示例

#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode{
	int data;
	TreeNode *left;
	TreeNode *right;
};
void start(TreeNode *p,int a){
	p->data=a;
	p->left=NULL;
	p->right=NULL;
} 
void addleft(TreeNode *p, TreeNode *a,int b){
	p->left=a;
	a->data=b;
	a->left=NULL;
	a->right=NULL;
} 
void addright(TreeNode *p, TreeNode *a,int b){
	p->right=a;
	a->data=b;
	a->left=NULL;
	a->right=NULL;
} 
void Xian(TreeNode *p){
	if(p!=NULL){
		printf("%d",p->data);
	    Xian(p->left);
	    Xian(p->right);
	}
}
void Zhong(TreeNode *p){
	if(p!=NULL){
	    Xian(p->left);
	    printf("%d",p->data);
	    Xian(p->right);
	}
}
void Hou(TreeNode *p){
	if(p!=NULL){
	    Xian(p->left);
	    Xian(p->right);
	    printf("%d",p->data);
	}
}
//判断两棵树是否相同 
bool isSameTree(TreeNode* p, TreeNode* q){
	if(p==NULL&&q==NULL){
		return true;
	}else if(p==NULL||q==NULL){
		return false;
	}else if(p->data!=q->data){
		return false;
	}else{
		return isSameTree(p->left,q->left)&&(p->right,q->right);
	}
}
int main(){	
    TreeNode *root;
    TreeNode *left;
    TreeNode *right;
    root=(TreeNode *)malloc(sizeof(TreeNode));
    left=(TreeNode *)malloc(sizeof(TreeNode));
    right=(TreeNode *)malloc(sizeof(TreeNode));
    start(root,3);
    addleft(root,left,4);
    addright(root,right,5);
    printf("%d\n",root->left->data); 
    Xian(root);
    printf("\n");
    Zhong(root);
    printf("\n");
    Hou(root);
    free(root);
    free(left);
    free(right);
    return 1; 
}

图

对图的定义都需要提前确定定点数或者设置一个较大的定点数，然后不超过此范围即可

邻接矩阵

#define MAXVEX 10
#define MAX 65525//顶点之间不可达一般设为一个很大的数或者零
typedef struct MGraph{
	char vexs[MAXVEX];//设置顶点信息，由于是以为字符串数组所以只有单字母标识顶点即A,B顶点等
	int arc[MAXVEX][MAXVEX];//临界矩阵
	int numVertexes;//定点数
	int numEdge;//边数
}MGraph;

示例

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 10
#define MAX 65525
int visited[MAXVEX];

typedef struct MGraph{
	char vexs[MAXVEX];
	int arc[MAXVEX][MAXVEX];
	int numVertexes;
	int numEdge;
}MGraph; 
//初始化图 
void start(MGraph *G){
	printf("请输入顶点数和边数：\n");
	scanf("%d,%d",&(G->numVertexes),&(G->numEdge));
	getchar();
	int a=0;
	printf("输入各顶点信息：\n");
	for(a;a<G->numVertexes;a++){
		scanf("%c",&(G->vexs[a]));
		getchar();
	}
	int i,j;
	//初始化矩阵 
	for(i=0;i<MAXVEX;i++){
		for(j=0;j<MAXVEX;j++){
			if(i==j){
				G->arc[i][j]=0;
			}else{
				G->arc[i][j]=MAX;
			}
		}
	} 
	int m,n,b;	
	
//	不带权值 
//	printf("输入存在的边：\n");
//	for(b=0;b<G->numEdge;b++){
//		scanf("%d,%d",&m,&n);
//		//无向图，两顶点间互通
//		G->arc[m][n]=G->arc[n][m]=1;
//		//有向图，单向通 
//		//G->arc[m][n]=1;
//	}

//  带权值 
	printf("输入存在的边以及对应的权值：\n");
	for(b=0;b<G->numEdge;b++){
		int q;
		scanf("%d,%d,%d",&m,&n,&q);
		//无向图，两顶点间互通
		G->arc[m][n]=G->arc[n][m]=q;
		//有向图，单向通 
		//G->arc[m][n]=1;
	} 
}
//深度优先搜索 --邻接矩阵 
void DFS(MGraph *G,int i){
	visited[i]=1;
	printf("当前节点为：%c\n",G->vexs[i]);
	int j;
	for(j=0;j<G->numVertexes;j++){
		if(G->arc[i][j]&&visited[j]==0){
			DFS(G,j);
		}
	} 
} 
//深度优先遍历 --邻接矩阵  
void DFSTraverse(MGraph *G,int i){
	if(G->numVertexes<1){
		printf("该图没有顶点。");
		return; 
	}
	int j;
	for(j=0;j<G->numVertexes;j++){
		visited[j]=0;
	}
	for(j=0;j<G->numVertexes;j++){
		if(!visited[j]){
			DFS(G,i);
		}
	}
	printf("遍历结束！");
} 
int main(){
	struct MGraph *G;
	G=(MGraph *)malloc(sizeof(MGraph));
	start(G);
	//遍历图 
	DFSTraverse(G,1);
	return 1;
} 
/*
输入示例: 
邻接矩阵
请输入顶点数和边数：
7,10
输入各顶点信息：
A
B
C
D
E
F
G
输入存在的边：
0,1
0,2
0,3
1,6
1,4
2,4
2,5
3,6
3,5
4,5
带权值 
0,1,1
0,2,4
0,3,10
1,6,7
1,4,6
2,4,9
2,5,2
3,6,5
3,5,8
4,5,11
*/

邻接表

typedef struct EdgeNode{ 
	int data;//存储顶点下标; 
	int weight;//有向图的权值; 
	struct EdgeNode *next; //指向下一个邻接点 
}EdgeNode; 
//顶点数组 
typedef struct VertexNode{
	char data;//存储顶点信息; 
	struct EdgeNode *first;//边表的头节点; 
}VertexNode,AdjList[MAXVEX];
//图的邻接表 
typedef struct GraphAdjList{
	AdjList adjlist;
	int numVertexes,numEdge;//当前顶点数和边数 
}GraphAdjList;

示例

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 100 
#define MAX 65525
int visited[MAXVEX];
//顶点的邻接点
typedef struct EdgeNode{ 
	int data;//存储顶点下标; 
	int weight;//有向图的权值; 
	struct EdgeNode *next; //指向下一个邻接点 
}EdgeNode; 
//顶点数组 
typedef struct VertexNode{
	char data;//存储顶点信息; 
	struct EdgeNode *first;//边表的头节点; 
}VertexNode,AdjList[MAXVEX];
//图的邻接表 
typedef struct GraphAdjList{
	AdjList adjlist;
	int numVertexes,numEdge;//当前顶点数和边数 
}GraphAdjList;
//初始化 
void start(GraphAdjList *G){
	EdgeNode *temp; 
	printf("输入边数和顶点数：\n"); 
	scanf("%d,%d",&(G->numEdge),&(G->numVertexes));
	getchar();
	int i,j,m;
	printf("输入各顶点信息：\n");
	for(i=0;i<G->numVertexes;i++){
		scanf("%c",&(G->adjlist[i].data));
		getchar();
		G->adjlist[i].first=NULL;
	}
//	不带权值的实现 
//	printf("输入存在的边：\n");
//	for(m=0;m<G->numEdge;m++){
//		scanf("%d,%d",&i,&j);
//		//无向图，两顶点互通; 
//		temp=(EdgeNode *)malloc(sizeof(EdgeNode));
//		temp->data=j;
//		temp->next=G->adjlist[i].first;
//		G->adjlist[i].first=temp;
//		
//		有向图不需要下面步骤 
//		temp=(EdgeNode *)malloc(sizeof(EdgeNode));
//		temp->data=i;
//		temp->next=G->adjlist[j].first;
//		G->adjlist[j].first=temp;
//		getchar();
//	}
	printf("输入存在的边：\n");
	for(m=0;m<G->numEdge;m++){
		scanf("%d,%d",&i,&j);
		//无向图，两顶点互通; 有向图只用第一个即可 
		temp=(EdgeNode *)malloc(sizeof(EdgeNode));
		temp->data=j;
//		printf("输入存在的边的权值：\n");
		scanf("%d",&temp->weight); 
		temp->next=G->adjlist[i].first;
		G->adjlist[i].first=temp;
		
		temp=(EdgeNode *)malloc(sizeof(EdgeNode));
		temp->data=i;
		temp->next=G->adjlist[j].first;
		G->adjlist[j].first=temp;
		getchar();
	}
}
//深度优先搜索 --邻接表 
void DFS(GraphAdjList *G,int i){
	EdgeNode *p; 
	visited[i]=1;
	printf("遍历节点为：%c\n",G->adjlist[i].data);
	p=G->adjlist[i].first;
	while(p){
		int j = p->data;
		if(!visited[j]){
			DFS(G,j);
		}
		p=p->next;
	}
} 
//深度优先遍历 --邻接表  
void DFSTraverse(GraphAdjList *G){
	if(G->numVertexes<1){
		printf("该图没有顶点。");
		return; 
	}
	int j;
	for(j=0;j<G->numVertexes;j++){
		visited[j]=0;
	}
	for(j=0;j<G->numVertexes;j++){
		if(!visited[j]){
			DFS(G,j);
		}
	}
}
int main(){
	struct GraphAdjList *G;
	G=(GraphAdjList *)malloc(sizeof(GraphAdjList));
	start(G);
	DFSTraverse(G);
}
/*输入示例
邻接表
请输入顶点数和边数：
10,7
输入各顶点信息：
A
B
C
D
E
F
G
输入存在的边：
0,1
0,2
0,3
1,6
1,4
2,4
2,5
3,6
3,5
4,5
带权值 
0,1
1
0,2
4
0,3
10
1,6
7
1,4
6
2,4
9
2,5
2
3,6
5
3,5
8
4,5
6
*/

文章来源:https://blog.csdn.net/qq_44839044/article/details/135308612
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！