实验总结：
数组类型是一种顺序存储结构，在特殊矩阵中，对于对称矩阵，我们可以为唯一对对称元分配一个存储空间，则可将n的平方个元压缩存储到n（n+1）/2个元的空间。
数组可以利用偏移地址来访问元素，效率高，可以使用折半方法查找元素，效率较高 但是其空间连续，存储效率低，插入和删除元素效率比较低，且比较麻烦。
稀疏矩阵的计算速度更快,因为M AT L A B只对非零元素进行操作,这是稀疏矩阵的一个突出的优点.
软件学院上机实验报告
备注：学生应根据实验的要求，设计一个实验过程（包括程序代码、各种定义说明），并根据实验的结论及实验过程中出现的情况（错误、异常等）得出的体会。要求学生每人一台计算机，独立完成实验的全过程。
实验题目： 二叉树的遍历 实验目的： 1.用二叉表表示二叉树 2.掌握二叉树的基本操作 3.掌握二叉树先中后序遍历算法 4.基于二叉树遍历算法实现某些应用 实验要求： 1. 二叉树的抽象数据类型 2. 二叉树的存储结构 3.二叉树基本操作的实现 4. 二叉树的先中后序遍历算法 5.二叉树的应用 实验内容：
1. 二叉树的抽象数据类型
ADT BinaryTree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若D=Φ，则R=Φ，称BinaryTree为空二叉树； 若D≠Φ，则R={H}，H是如下二元关系； （1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱； （2）若D-{root}≠Φ，则存在D-{root}={D1,Dr}，且D1∩Dr =Φ； （3）若D1≠Φ，则D1中存在惟一的元素x1，∈H，且存在D1上的关系H1 ?H；若Dr≠Φ，则Dr中存在惟一的元素xr， ∈H，且存在Dr上的关系Hr ?H；H={,,H1,Hr}； （4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵本定义的二叉树，称为根的右子树。 基本操作： InitBiTree( &T ) 操作结果：构造空二叉树T。 Destroy BiTree( &T ) 初始条件：二叉树T已存在。 操作结果：销毁二叉树T。 CreateBiTree( &T, definition ) 初始条件：definition给出二叉树T的定义。 操作结果：按definiton构造二叉树T。 ClearBiTree( &T ) 初始条件：二叉树T存在。 操作结果：将二叉树T清为空树。 BiTreeEmpty( T ) 初始条件：二叉树T存在。 操作结果：若T为空二叉树，则返回TRUE，否则返回FALSE。 BiTreeDepth( T ) 初始条件：二叉树T存在。 操作结果：返回T的深度。 Root( T ) 初始条件：二叉树T存在。 操作结果：返回T的根。 Value( T, e ) 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的值。 Assign( T, &e, value ) 初始条件：二叉树T存在，e是T中某个结点。 操作结果：结点e赋值为value。 Parent( T, e ) 初始条件：二叉树T存在，e是T中某个结点。 操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”。 LeftChild( T, e ) 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的左孩子。若e无左孩子，则返回“空”。 RightChild( T, e ) 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的右孩子。若e无右孩子，则返回“空”。 LeftSibling( T, e ) 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”。RightSibling( T, e ) 初始条件：二叉树T存在，e是T中某个结点。 操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”。 InsertChild( T, p, LR, c ) 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。 操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结点的原有左或右子树则成为c的右子树。 DeleteChild( T, p, LR ) 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。 操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。 PreOrderTraverse( T, visit() ) 初始条件：二叉树T存在，Visit是对结点操作的应用函数。 操作结果：先序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。 InOrderTraverse( T, visit() ) 初始条件：二叉树T存在，Visit是对结点操作的应用函数。 操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。 PostOrderTraverse( T, visit() ) 初始条件：二叉树T存在，Visit是对结点操作的应用函数。 操作结果：后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。 LevelOrderTraverse( T, visit() ) 初始条件：二叉树T存在，Visit是对结点操作的应用函数。 操作结果：层次遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。 }ADT BinaryTree 操作类型的实现：
int Create(Tree &T) //创建一个二叉树 {
char ch; cin>>ch;
if(ch=='#')T=NULL; else{
T=(Tree)malloc(sizeof(TNode)); //给二叉链表分配一个结点的内存 if(!T) return 0; T->data=ch;
Create(T->lchild); //递归函数的调用 Create(T->rchild); }
return 1; }
int PreOrder(Tree T,int(* visit)(char e)) //先序遍历 {
if(T) { if(visit(T->data)) if(PreOrder(T->lchild,PrintElement)) if(PreOrder(T->rchild,PrintElement)) return 1; return 0; }
else return 1; }
int InOrder(Tree T,int(* visit)(char e)) //中序遍历 {
Stack S; Init(S); Push(S,T); Tree p=T;
while(S.base!=S.top) { while(Get(S,p)&&p)Push(S,p->lchild); //向左走到尽头 Pop(S,p); //空指针出栈 if(S.base!=S.top) { Pop(S,p); PrintElement(p->data); //得到第一个元素 Push(S,p->rchild); //用循环代替递归函数 } }
return 1; }
int PrintElement(char e) //visit的函数，输出元素 {
cout<void PostOrder(Tree T) //后序遍历 {
Stack S; Init (S);