数据结构实验(2)

二 实验要求

1． 认真设计本实验的程序，上机调试运行本程序。

2． 保存或打印出程序的运行结果，记录程序调试过程中出现的问题，对问

题加以分析。

三 实验内容

1． 按先序遍历序列建立链式存储结构的二叉树。 2． 对该二叉树按层次进行遍历，并输出结果。

选作实验：对二叉树按中序或后序进行遍历 #include #include #include #include

typedef struct BiTNode //定义二叉树节点结构 {

char data; //数据域

struct BiTNode *LChild,*RChild; //左右孩子指针域 }BiTNode,*BiTree;

struct link {

struct BiTNode *p; struct link *next; };

//以先序形式建立二叉树 void CreateBiTree(BiTree *bt) {

char ch;

scanf(\ if(ch==' ') *bt=NULL; else {

*bt=(BiTree)malloc(sizeof(BiTNode)); //生成一个新结点 (*bt)->data=ch;

CreateBiTree(&((*bt)->LChild)); //生成左子树

CreateBiTree(&((*bt)->RChild)); //生成右子树 } }

void LevOrder(BiTree root)

/* 层次遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/ {

struct link *head,*tail,*p;

head=(struct link *)malloc(sizeof(struct link)); head->p=root; //root进队列 head->next=NULL; tail=head; do{

if(head->p->LChild!=NULL) //若该根节点左孩子不为空，则左孩子入队列 {

p=(struct link *)malloc(sizeof(struct link)); p->p=head->p->LChild; p->next=NULL; //进队列操作

tail->next=p; tail=p; }

if(head->p->RChild!=NULL) //若该根节点右孩子不为空，则右孩子入队列 {

p=(struct link *)malloc(sizeof(struct link)); p->p=head->p->RChild; p->next=NULL; //进队列操作

tail->next=p; tail=p; }

p=head;

//在将该根节点左右孩子入队列操作完毕后，将该根节点输出，并从队列中除去，根节点就为队列中下一个元素了 printf(\ head=head->next;

free(p);

}while(head!=NULL); }

void main() {

BiTree T;

printf(\请输入二叉树序列!\\n\ CreateBiTree(&T);

printf(\层序遍历序列为:\LevOrder(T); }

实验四 图的建立和基本操作

一 实验目的

1． 掌握图的原理与基本操作方法。

2． 掌握图的基本操作：图的建立,遍历方法。

二 实验要求

1． 认真设计本实验的程序，上机调试运行本程序。

2． 保存或打印出程序的运行结果，记录程序调试过程中出现的问题，对问

题加以分析。

三 实验内容

1． 输入图的顶点数据和邻接矩阵，建立该图的邻接表。 2． 对该图进行深度优先遍历，输出相应结果。

选作实验：对该图进行广度优先遍历 #include

#define MaxVertexNum 100 #define QueueSize 30

typedef enum{FALSE,TRUE}Boolean; Boolean visited[MaxVertexNum]; typedef struct node //边表结点 {

int adjvex; //邻接点域

struct node *next; //域链

//若是要表示边上的权,则应增加一个数据域 }EdgeNode;

typedef struct vnode //顶点边结点 {

char vertex; //顶点域

EdgeNode *firstedge;//边表头指针 }VertexNode;

typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型 typedef struct {

AdjList adjlist; //邻接表

int n,e; //图中当前顶点数和边数

}ALGraph; //对于简单的应用，无须定义此类型，可直接使用AdjList类型

/************************************************************************/ /* 建立无向图的邻接表算法 */

/************************************************************************/

void CreateGraphAL (ALGraph *G) {

int i,j,k;

EdgeNode * s;

printf(\请输入顶点数和边数(输入格式为:顶点数,边数)：\\n\ scanf(\ // 读入顶点数和边数 printf(\请输入顶点信息(输入格式为:顶点号)每个顶点以回车作为结束:\\n\

for (i=0;in;i++) // 立有n个顶点的顶点表 {

scanf(\读入顶点信息

G->adjlist[i].firstedge=NULL; // 点的边表头指针设为空 }

printf(\请输入边的信息(输入格式为:i,j)：\\n\ for (k=0;ke;k++) // 建立边表 {

scanf(\读入边的顶点对应序号 s=new EdgeNode; // 生成新边表结点s s->adjvex=j; // 邻接点序号为j

s->next=G->adjlist[i].firstedge; // 将新边表结点s插入到顶点Vi的边表头部

G->adjlist[i].firstedge=s; s=new EdgeNode; s->adjvex=i;

s->next=G->adjlist[j].firstedge; G->adjlist[j].firstedge=s; } }

/************************************************************************/ /* 深度优先遍历 */

/************************************************************************/

void DFS(ALGraph *G,int i) {

//以vi为出发点对邻接表表示的图G进行深度优先搜索 EdgeNode *p;

printf(\ // 访问顶点vi visited[i]=TRUE; //标记vi已访问 p=G->adjlist[i].firstedge; //取vi边表的头指针 while(p)

{ //依次搜索vi的邻接点vj，这里j=p->adjvex

if (!visited[p->adjvex]) //若vi尚未被访问

DFS(G,p->adjvex); //则以Vj为出发点向纵深搜索 p=p->next; //找vi的下一邻接点 } }

void DFSTraverseM(ALGraph *G) {

int i;

for(i=0;in;i++)

visited[i]=FALSE;

for(i=0;in;i++) if(!visited[i]) DFS(G,i); }

/************************************************************************/ /* 主函数调用 */

/************************************************************************/ int main() {

ALGraph G;

CreateGraphAL(&G);

printf(\深度优先遍历：\\n\ DFSTraverseM(&G); return 0; }

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构实验(2)在线全文阅读。