数据结构定义结构体(2)
作者:
Item
,
2022-11-29 15:52:18
,
所有人可见
,
阅读 214
//二叉树的链式存储
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
//先序遍历
void PreOrder(BiTree T){
if(T != NULL){
visit(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
bool IsEmpty(LinkQueue Q)
void EnQueue(LinkQueue &Q, ElemType x)
bool DeQueue(LinkQueue &Q, ElemType &x)
//层次遍历
void LevelOrder(BiTree T){
InitQueue(Q);//初始化辅助队列
BiTree p;
EnQueue(Q, T);//根结点入队
while(!IsEmpty(Q)){
DeQueue(Q, p);//队头结点出队
visit(p);//访问出队结点
if(p->lchild!=NULL)
EnQueue(Q, p->lchild);//左子树不空,则左子树根结点入队
if(p->rchild !=NULL)
EnQueue(Q, p->rchild);//右子树不空,则右子树根结点入队
}
}
//多叉树顺序存储--双亲表示法,根结点下标为0,伪指针域为-1
#define MAX_TREE_SIZE 100
typedef struct{//树结点的定义
ElemType data;
int parent;//双亲位置域
}PTNode;
typedef struct{//树的类型定义
PTNode nodes[MAX_TREE_SIZE];//双亲表示
int n;//结点数
}PTree;
//孩子兄弟表示法
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild, *nextsibling;//第一个孩子和右兄弟指针
}CSNode, *CSTree;
//并查集find操作优化--路径压缩
int Find(int S[], int x){
int root = x;
while(S[root] >= 0) root = S[root];
while(x != root){//压缩路径
int t = S[x];//t指向x的父结点
S[x] = root;//x直接挂到根结点下
x = t;
}
return root;//返回根结点编号
}
//邻接矩阵存储结构定义--稠密图
#define MaxVertexNum 100//顶点数目的最大值
typedef char VertexType;//顶点的数据类型
typedef int EdgeType;//带权图中边上权值的数据类型
typedef struct{
VertexType Vex[MaxVertexNum];//顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵,边表
int vexnum, arcnum;//图的当前顶点数和弧数
}MGraph;
//邻接表存储结构定义--稀疏图
#define MaxVertexNum 100
typedef struct ArcNode{//边表结点
int adjvex;//该弧所指向的顶点的位置
struct ArcNode *next;//指向下一条弧的指针
//InfoType info; //网的边权值
}ArcNode;
typedef struct VNode{//顶点表结点
VertexType data;//顶点信息
ArcNode *first;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
AdjList vertices;//邻接表
int vexnum, arcnum;//图的顶点数和弧数
}ALGraph;//ALGraph是以邻接表存储的图类型