2009级数据结构实验指导书(7)

数据结构实验指导书

/*若A的当前项的行号等于B的当前项的行号,则比较其列号,将较小列的项*/ /*存入C中,如果列号也相等,则将对应的元素值相加后存入C中*/ if (A[i][0]==B[j][0]) if (A[i][1]

else if (A[i][1]>B[j][1]) { C[k][0]=B[j][0];C[k][1]=B[j][1];C[k][2]=B[j][2]; k++;j++; } else { C[k][0]=B[j][0];C[k][1]=B[j][1]; C[k][2]=A[i][2]+B[j][2]; k++;i++;j++; }

else if (A[i][0]

/*若A的当前项的行号小于B的当前项的行号,则将A的项存入C中*/ { C[k][0]=A[i][0];C[k][1]=A[i][1];C[k][2]=A[i][2]; k++;i++; } else

/*若A的当前项的行号大于B的当前项的行号,则将B的项存入C中*/ { C[k][0]=B[j][0];C[k][1]=B[j][1];C[k][2]=B[j][2]; k++;j++; }

C[0][0]=A[0][0]; /*产生第0行的结果*/ C[0][1]=A[0][1]; C[0][2]=k-1; }

void matmul(int m,int n,int k,smat A,smat B,smat C) {

int i,j,l,p=1,s; for (i=0;i

- 21 -

数据结构实验指导书

} C[0][0]=m; /*产生第0行的结果*/ C[0][1]=k; C[0][2]=p-1; }

int value(smat C,int i,int j) /*用在matmul函数之中,计算C[i][j]的值*/ {

int k=1;

while (k<=C[0][2] && (C[k][0]!=i || C[k][1]!=j)) k++; if (k<=C[0][2]) return(C[k][2]); /*找到了返回该位置的值*/ else return(0); /*未找到说明该元素为0*/ }

void display(char *s,smat A) {

int i;

printf(\三元组:\\n\\t Row Col Val\\n\ for (i=1;i<=A[0][2];i++) printf(\ }

main() {

int A[M][N]={{0,1,0},{6,0,0},{1,0,0}}; int B[M][N]={{1,2,0},{0,4,0},{0,3,0}}; smat C,D,E,F,G; creatmat(A,C); creatmat(B,D);

display(\矩阵\

printf(\处的值:%d\\n\ printf(\元素3是否存在:%d\\n\ matadd(C,D,E);

display(\ matmul(M,N,K,C,D,F); display(\×B\ trsmat(C,G); display(\

}

三、注意事项

1、三元组中两个矩阵相加，只有同行同列时对应元素才相加。

实验四 二叉树的基本操作

一、实验目的

1、进一步掌握指针变量、动态变量的含义。

2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算。

二、实验内容

- 22 -

数据结构实验指导书

1、以二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。

#define M 10

typedef int DataType;/*元素的数据类型*/ typedef struct node { DataType data;

struct node *lchild,*rchild; }BitTNode,*BiTree; int front=0,rear=0; BitTNode *que[10]; BitTNode *creat() {BitTNode *t; DataType x; scanf(\ if(x==0) t=NULL;

else{ t=(BitTNode *)malloc(sizeof(BitTNode)); t->data=x;

t->lchild=creat(); t->rchild=creat(); }

return(t); }/*creat*/

/* 前序遍历二叉树t */ void preorder(BiTree t) { if(t!=NULL)

{ printf(\ preorder(t->lchild);

preorder(t->rchild); } }

/* 中序遍历二叉树t */ void inorder(BiTree t) { if(t!=NULL)

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

/* 后序遍历二叉树t */ void postorder(BiTree t) { if(t!=NULL)

{ postorder(t->lchild); postorder(t->rchild);

printf(\ }

- 23 -

数据结构实验指导书

}

void enqueue(BitTNode *t) {if (front!=(rear+1)%M) { rear=(rear+1)%M; que[rear]=t; }

}/*enqueue*/

BitTNode * delqueue()

{ if(front==rear)return NULL; { front=(front+1)%M; return (que[front]); }

}/*delqueue*/

/* 按层次遍历二叉树t */

void levorder(BiTree t) { BitTNode *p; if(t!=NULL) { enqueue(t);

while (front!=rear) { p=delqueue();

printf(\

if(p->lchild!=NULL) enqueue(p->lchild); if(p->rchild!=NULL) enqueue(p->rchild); } }

}/* levorder */ main()

{BitTNode *root; root=creat();

printf(\按先序遍历次序生成的二叉树\ printf(\前序遍历二叉树\ preorder(root);

printf(\中序遍历二叉树\ inorder(root);

printf(\后序遍历二叉树\ postorder(root);

printf(\层次顺序遍历二叉树\ levorder(root); }

2、以二叉链表作存储结构，试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法

#include #define MaxSize 100 typedef char ElemType; typedef struct node

- 24 -

数据结构实验指导书

{

ElemType data;

struct node *left,*right; } BTree;

BTree * createbt( ) { BTree *q; struct node1 *s[30]; int j,i,x; printf(\建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\\n\\n\ printf(\ scanf(\ while(i != 0 && x != '$') { q = (BTree*)malloc(sizeof(BTree)); /*建立一个新结点q*/ q->data = x; q->left = NULL; q->right = NULL; s[i] = q; /*q新结点地址存入s指针数组中*/ if(i != 1) /*i = 1，对应的结点是根结点*/ { j = i / 2; /*求双亲结点的编号j*/ if(i % 2 == 0)

s[j]->left = q; /*q结点编号为偶数则挂在双亲结点j的左边*/

else

s[j]->right = q; /*q结点编号为奇数则挂在双亲结点j的右边*/ }

printf(\ scanf(\

} retur …… 此处隐藏：1859字，全部文档内容请下载后查看。喜欢就下载吧 ……