数据结构22-24

第二十二 课

本课主题：实验五 数组实验

教学目的：掌握二维数组的实现方法

教学重点：二维数组的存储表示,二维数组的基本操作

教学难点：二维数组的基本操作

授课内容：

数组的顺序存储表示和实现:

#include<stdarg.h>

#define MAX_ARRAY_DIM 8

typedef struct {

ElemType *base;

int dim;

int *bounds;

int *constants;

}Array;

Status InitArray(Array &A,int dim,...);

Status DestroyArray(Array &A);

Status Value(Array A,ElemType &e,...);

Status Assign(Array &A,ElemType e,...);

基本操作的算法描述:

Status InitArray(Array &A,int dim,...){

if(dim<1||dim>MAX_ARRAY_DIM) return ERROR;

A.dim=dim;

A.bounds=(int *)malloc(dim *sizeof(int));

if(!A.bounds) exit(OVERFLOW);

elemtotal=1;

va_start(ap,dim);

for(i=1;i<dim;++i){

A.bounds[i]=va_arg(ap,int);

if(A.bounds[i]<0) return UNDERFLOW;

elemtotal*=A.bounds[i];

}

va_end(ap);

A.base=(ElemType *)malloc(elemtotal*sizeof(ElemType));

if(!A.base) exit(OVERFLOW);

A.constants=(int *)malloc(dim*sizeof(int));

if(!A.constants) exit(OVERFLOW);

A.constants[dim-1]=1;

for(i=dim-2;i>=0;--i)

A.constants[i]=A.bounds[i+1]*A.constants[i+1];

return OK;

}

Status DestoyArray(Array &A){

if(!A.base) return ERROR;

free(A.base); A.base=NULL;

if !(A.bounds) return ERROR;

free(A.bounds); A.bounds=NULL;

if!(A.constatns) return ERROR;

free(A.constants); A.constants=NULL;

return OK;

}

Status Locate(Array A,va_list ap,int &off){

off=0;

for(i=0;i<A.dim;++i){

ind=va_arg(ap,int);

if(ind<0||ind>=A.bounds[i]) return OVERFLOW;

off+=A.constants[i]*ind;

}

return OK;

}

Status Value(Array A,ElemType &e,...){

va_start(ap,e);

if((result=Locate(A,ap,off))<=0 return result;

e=*(A.base+off);

return OK;

}

Status Assign(Array &A,ElemType e,...){

va_start(ap,e);

if((result=Locate(A,ap,off))<=0) return result;

*(A.base+off)=e;

return OK;

}

回目录上一课下一课

第二十三课

本课主题：二叉树的存储结构

教学目的：掌握二叉树的两种存储结构

教学重点：链式存储结构

教学难点：链式存储二叉树的基本操作

授课内容：

一、复习二叉 树的定义

二叉树的基本特征：每个结点的度不大于２。

二、顺序存储结构

#define MAX_TREE_SIZE 100

typedef TElemType SqBiTree[MAX_TREE_SIZE];

SqBiTree bt;

第i号结点的左右孩子一 定保存在第2i及2i+1号单元中。

缺点：对非完全二叉树而言，浪费存储空间

三、链式存储结构

一个二叉树的结点至少保存三种信息：数据元素、左孩子位置、右孩 子位置

对应地，链式存储二叉树的结点至少包含三个域：数据域、左、右指 针域。

也可以在结点中加上指向父结点的指针域P。

对结点有二个指针域的存储方式有以下表示方法：

typedef struct BiTNode{

TElemType data;

struct BitNode *lchild,*rchild;

}BiTNode,*BiTree;

基于该存储结构的二叉树基本操作有：

Status CreteBiTree(BiTree &T);

//按先序次序输入二叉树中结点的值 （一个字符），空格字符表示空树，

//构造二叉链表表示的二叉树T。

Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e));

//采用二叉链表存储结 构,Visit是对结点操作的应用函数

//先序遍历二叉树T,对每个结点调 用函数Visit一次且仅一次

//一旦visit()失败,则操作 失败

Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e));

//采用二叉链表存储结 构,Visit是对结点操作的应用函数

//中序遍历二叉树T,对每个结点调 用函数Visit一次且仅一次

//一旦visit()失败,则操作 失败

Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e));

//采用二叉链表存储结 构,Visit是对结点操作的应用函数

//后序遍历二叉树T,对每个结点调 用函数Visit一次且仅一次

//一旦visit()失败,则操作 失败

Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e));

//采用二叉链表存储结 构,Visit是对结点操作的应用函数

//层序遍历二叉树T,对每个结点调 用函数Visit一次且仅一次

//一旦visit()失败,则操作 失败

四、总结本课内容

顺序存储与链式存储的优缺点。

回目录上一课下一课

第二十四课

本课主题：遍历二叉树

教学目的：掌握二叉树遍历的三种方法

教学重点：二叉树的遍历算法

教学难点：中序与后序遍历的非递归算法

授课内容：

一、复习二叉树的定义

二叉树由三个基本单元组成：根结点、左子树、右子树

问题：如何不重复地访问二叉树中每一个结点？

二、遍历二叉树的三种方法：

三、递归法遍历二叉树

先序：

Status(PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){

if(T){

if(Visit(T->data))

if(PreOrderTraverse(t->lchild,Visit))

if(PreOrderTraverse(T->rchild,Visit)) return OK;

return ERROR;

}else return OK;

}

遍历结果：1,2,4,5,6,7,3

四、非递归法遍历二叉树

中序一：

Status InorderTraverse(BiTree T,Status(*Visit)(TElemType e)){

InitStack(S);Push(S,T);

while(!StackEmpty(S)){

while(GetTop(S,p)&&p)Push(S,p->lchild);

Pop(S,p);

if(!StackEmpty(S)){

Pop(S,p); if(!Visit(p->data)) return ERROR;

Push(S,p->rchild);

}

}

return OK;

}

中序二：

Status InorderTraverse(BiTree T,Status(*Visit)(TElemType e)){

InitStack(S);p=T;

while(p||!StackEmpty(S)){

if(p){Push(S,p);p=p->lchild;}

else{

Pop(S,p); if(!Visit(p->data)) return ERROR;

p=p->rchild);

}//else

}//while

return OK;

}

五、总结

二叉树遍历的意义

回目录上一课下一课