数据结构实验指导书

{ BTCHINALR *q;

struct node1 *s[30]; int j,i,x;

printf(\建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\\n\\n\ printf(\ scanf(\ while(i != 0 && x != '$')

{q = (BTCHINALR*)malloc(sizeof(BTCHINALR)); /*建立一个新结点q*/ q->data = x; q->lchild = NULL; q->rchild = NULL;

s[i] = q; /*q新结点地址存入s指针数组中*/ if(i != 1) /*i = 1，对应的结点是根结点*/ {j = i / 2; /*求双亲结点的编号j*/

if(i % 2 == 0) s[j]->lchild = q; /*q结点编号为偶数则挂在双亲结点j的左边*/ else s[j]->rchild = q;} /*q结点编号为奇数则挂在双亲结点j的右边*/ printf(\

scanf(\

return s[1]; /*返回根结点地址*/ }

void inorder(BTCHINALR *bt) /*中序遍历二叉树(递归算法)*/ {if(bt != NULL)

{ inorder(bt->lchild); printf(\ inorder(bt->rchild); } }

void inorder_notrecursive(BTCHINALR *bt) /*中序遍历二叉树(非递归算法)*/ {BTCHINALR *q, *s[20]; int top = 0; int bool = 1; q = bt;

do {while(q != NULL)

{ top ++; s[top] = q; q = q->lchild; } if(top == 0) bool = 0; else { q = s[top]; top --;

printf(\ q = q->rchild; } }while(bool); }

21

main( )

{ BTCHINALR *bt; char ch; int i;

bt = createbt(); i = 1; while(i) {

printf(\中序遍历二叉树(递归按y键，非递归按n键): \ fflush(stdin); scanf(\

if(ch == 'y') inorder(bt); else inorder_notrecursive(bt); printf(\

printf(\继续操作吗?(继续按1键，结束按0键): \ fflush(stdin); scanf(\ } }

方法二：按先序遍历序列建立二叉树的二叉链表，已知先序序列为：

A B C φ φ D E φ G φ φ F φ φ φ

#define datatype char typedef struct node {datatype data;

struct node *lchild,*rchild; }JD;

JD *crt_bt_pre(JD *bt) { char ch;

printf(\ scanf(\

if(ch==' ') bt=NULL; else

22

{ bt=(JD *)malloc(sizeof(JD)); bt->data=ch;

bt->lchild=crt_bt_pre(bt->lchild); bt->rchild=crt_bt_pre(bt->rchild); }

return(bt);

}

23

实验三 图的创建与访问算法的设计

一、目的

本实验的目的是通过理解图的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。

二、题目

图的创建与访问算法的设计

三、实验类型

设计性。本实验设计了图的创建与访问算法。 四、要求及提示

说明：以下4个题中，任意选作一题。 1、【问题描述】

设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。 姓 名 项目 1 项目 2 项目 3 丁 一 跳 高 跳 远 100 米 马 二 标 枪 铅 球 张 三 标 枪 100 米 200 米 李 四 铅 球 200 米 跳 高 王 五 跳 远 200 米 【基本要求】

实现以下基本操作： （1） 建立图。

（2） 输出比赛日程表。

（3） 对所建的图进行深度优先遍历，输出深度优先遍历序列。

2、【问题描述】

设有六个比赛项目，规定每个选手至多可参加四个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。 姓名 张一 王二 李三 马四 董六

【基本要求】

实现以下基本操作： （1） 建立图。

（2） 输出比赛日程表。

（3） 对所建的图进行广度优先遍历，输出广度优先遍历序列。

24

项目1 跳高 铅球 标枪 100米 铅球 项目2 100米 跳高 跳远 200米 标枪 项目3 200米 200米 跳高 项目4 跳远