《数据结构》课程实验报告_数据结构课内实验报告

《数据结构》课程实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构课内实验报告”。

实验一 基于二叉链表的二叉树的实现

4.1 问题描述

基于二叉链表和队列及其堆栈存储结构，实现二叉链表的二叉树的对数据进行各种必要的操作。

4.2 系统设计

1.2.1提供20个功能，分别是：

1.2.2二叉链表的结构试一堆栈和队列的形式进行储存的分别是：

1.2.3在程序中所定义的数据结构有：

2.3 系统实现

1.3.1 InitTree功能

初始二叉链表，传入的是头结点地址。申请一个存储空间，并用头结点中的首结点指针指向该空间首地址，相应的 时间复杂度为1。具体实现如下：

1.3.2 DestroyTree功能

销毁头结点中首结点址针指向的线性存储空间，传入的是头结点地址。具体实现如下：

1.3.3 CreateBiTree功能

与DestroyBiTree类似但是又有不同，ClearBiTree并不销毁物理空间，而是修改逻辑关系值：

1.3.4 ClearBiTree功能

与DestroyBiTree类似但是又有不同，ClearBiTree并不销毁物理空间，而是修改逻辑关系值

1.3.5 BiTreeEmpty功能

判空功能，判断表是否为空表。时间复杂度为1，因为只需判断一次就可以知道是否为空。实现如下：

1.3.6 BiTreeDepth功能

求二叉链表深度的功能，由于创建过程中已经把表长信息包含在头结点中，所以直接调用并显示即可

1.3.7 Root(BiTree T)功能

获取二叉链表的根节点的元素，通过遍历二叉链表中的元素，来逐个判断，时间复杂度为（n）。

1.3.8 Value(BiTree T,TElemType e)功能

求指定元素的前一个元素的内容，传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。主要思路是递归算法。时间复杂度为O(n)。具体实现如下：

1.3.9 Aign功能

求指定元素的后一个元素的内容，传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。找到后，把新的数据值赋给所找到的节点。时间复杂度为O(n)。具体实现如下：

1.3.10 Parent功能

找双亲节点，找到后输出

1.3.11 LeftChild功能

查找左孩子，利用递归的算法，与遍历的时间复杂度为相同O(n)

1.3.12RightChild功能

查找右孩子，利用递归的算法，与遍历的时间复杂度为相同O(n)

1.3.13 LeftSibling功能

查找节点的左边的堂兄弟的，找到后输出该节点的数据

1.3.14 RightSibling功能

查找节点的右边的堂兄弟的，找到后输出该节点的数据

1.3.15 InsertChild函数 在二叉链表中插入新的节点

1.3.15 DeleteChild功能

删除指定编号的数据元素，传入头结点地址、编号i、表结点类型结构体地址来返回被删除元素内容。执行前先判断传入的编号是否在可寻找范围内。执行删除操作之后，进行“移位”运算。时间复杂度仍为O(n)。如下：

1.3.16 PreOrderTraverse功能

前序遍历二叉链表中的数据，采用先遍历左孩子，再访问根节点，后访问右孩子的思想来实现前序遍历的算法的。

1.3.17 InOrderTraverse功能

中序遍历的函数，对二叉链表的数据进行访问，并且利用PreOrderTraverse函数

1.3.18 PostOrderTraverse功能

采用后续遍历的思想，利用先序遍历的函数进行

1.3.19 LevelOrderTraverse功能

完全遍历二叉链表中的数据，并进行输出的 1.3.20 Point功能 定位节点的函数，在需要查找二叉链表二叉树的节点的时候，可以直接调用该函数，进行处理，相应的代码如下

1.3.21 FILE * fileOpen功能

读取功能，通过fscanf实现格式化读取，同时结合CreateList函数实现顺序

1.3.22 BiTNode * Create(FILE *fp)功能 把二叉链表二叉树的数据写入到文件中去

1.4效率分析

在上面介绍各功能时已经提到时间复杂度的计算了，这里再简单分析一下。

具有同数量级复杂度的功能在实现方法上一般近似。

比如InOrderTraverse，PostOrderTraverse，BiTreeDepth，LevelOrderTraverse 它们都是基于PreOrderTraverse 来设计的，所以效率都是O(n)；

而Root，Value，Aign，Parent，LeftChild，RightChild，LeftSibling RightSibling，InsertChild，DeleteChild 是基于VisitPoint，平均效率为O(n)；

InitTree

DestroyBiTree所需信息，所以效率为O(1)；

CreateBiTreeClearBiTreeBiTreeEmpty都要对二叉链表，平均效率为O(n)。

实验总结与评价

我做了这个实验发现自己的编程能力很不好，自己的脑袋中有相应的想法和主意，但是因为自己的编程能力很不好也就实现不了自己的想法。

二叉链表的二叉树的时候，实现二叉链表线性的对我来说还可以实现，因为线性的所用到方法和技术，在学习十字链表的时候练习的比较少，实现起来难度是很大。特别是有了老师给的框架以后，我们要做的任务就是向里面填我们自己写的函数，在填写的过程中，我深深的感受到了，认真的重要性，因为我在写好调试的中发现了很多，因为自己的不小心和在敲代码的过程中的不认真而造成的很不应该的错误，这些错误也给自己在调试的过程中也造成了很大的麻烦，因为是不认真而犯的错误，因此调试的过程中也很不好发现。

对我来说，因为我的C语言的功底很不好，运用指针和链表的能力还没有能达到运用自如，理解深刻的地步，所以在顺序链表的链表的实现中，对我来说是一个很大的挑战，我有很多不会的地方通过自己看书，问室友和上网查询，一点一点的写了出来，肯定现在还是会有很多的问题，但是这也是我一直在努力把它做的更好，在调试的中出现了很多的BUG，自己一个个的慢慢的消除掉了，做出了，现在的程序。

如果问自己的体会，那一定是希望我自己以后多多的动手，把以前C语言的书好好再复习一遍，还有就是把现在正在学习的数据结构的书上各个程序，自己要一个个的敲一遍，练习一下自己的熟悉程度。

总的来说，我对这次的实验是很有感触的。因为，这次实验让我认识到了，自己的编程能力的低下，如果自己再不下一下功夫的话，那么数据结构的考试自己就十分的危险了。因此，我要加紧复习C语言的知识和数据结构学过的内容，争取自己能在接下来的学习中能有些进步。

附录：

参考书《数据结构》（C语言版）严蔚敏 吴伟民编著

《C语言程序设计》 曹计昌，李开编著

实验心得体会

对于这两次的实验，我自己的体会是很深刻的，也是记忆深刻的。因为，正是因为这两次的实验深深地让我认识到了自己的水平是多么的低下，以前，自己还有点夜郎自大的认为，自己对所学的东西，自己掌握的还差不多了呢。但是，经过这次的实验，我真的是清楚的发现自己对所学的知识的掌握还差的很多，自己还有很多的功课要补。

第一，以前无论是学习C语言还是数据结构，我的方法是拿着书本看，还有就是拿着练习本写一写，而自己家上机的实践的时间是非常少的，因为我感觉上机得到的结构一定会和自己想的和写的一样呢，显然，我是错误的，因为在这次的实验里我就发现，即使是书上一模一样的代码，在机子上也是有很大 的可能出错的，更不用说是自己写的了，在写线性表，线性链表和二叉链表的时候，我出现了用书上的代码不能用的情况，而且是非常严重的错误。有些声明和指针的问题会出现很大的不同。我的体会是，从现在起，重视上机的过程，多书上的程序一定要在机子上跑一下，然后再分析一下，出现这种结果的原因和整个程序的流程。

第二，就是实验的 时候的规范的问题，由于，自己写代码没有很好的习惯和规则，于是，在自己写好的程序出现错误后自己不能够很快的 找到出现错误的位置，比如，对全局变量声明的时候，全局变量的位置问题，在结构和联合声明指针的时候，指针的形式和指针的命名的形式问题，这些错误都有在自己的实验的过程中出现，而且，也给自己带来了很大的麻烦。我的体会是，以后再写程序的时候一定遵守一定的规则和习惯，例如关键词的命名习惯，指针的使用形式和结构联合中的一些形式的问题，应该遵循一定的规则和习惯，因为，只有这样的自己在写好的调试和检查的过程中才不会走那么多 的弯路，才会把做事的速度提高上去。

最后，就是自己的一些心得体会对这次的实验。做什么事情都要认真对待，无论事情的大小，因为只有这样自己才会养成认真做事的习惯，这次的数据结构的实验让我深深的意识到了这一点。

附录：

实验三代码： #include #include #include #include #include

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASTABLE-1 #define OVERFLOW-2 #define MAX_TREE_SIZE 100

typedef int Status;typedef int TElemType;//数据元素类型定义,注意这里是整型的，可以使char typedef TElemType SqBiTree[MAX_TREE_SIZE];SqBiTree bt;

typedef struct{ TElemType *base;TElemType *top;int stacksize;}SqStack;

Status InitStack(SqStack*S);Status Pop(SqStack*S,TElemType e);Status Push(SqStack*S,TElemType e);Status StackEmpty(SqStack*S);//全局变量的声明

char *m_pCharBuf = NULL;int m_nList[100];int m_nCount = 0;

char* openFileOnlyRead(char * fileName);void writeQuickSortResult(char *pResult);char* openFileOnlyRead(char * fileName){

int nLen = 0;FILE *pFile = fopen(fileName, “r”);//打开文件

fseek(pFile, 0, SEEK_END);//文件指针移到文件尾

nLen = ftell(pFile);//得到当前指针位置, 即是文件的长度 rewind(pFile);//文件指针恢复到文件头位置

//动态申请空间, 为保存字符串结尾标志, 多申请一个字符的空间 m_pCharBuf =(char*)malloc(sizeof(char)* nLen + 1);

if(!m_pCharBuf){ perror(“内存不够!n”);exit(0);}

//读取文件内容//读取的长度和源文件长度有可能有出入，这里自动调整 nLen nLen = fread(m_pCharBuf, sizeof(char), nLen, pFile);

m_pCharBuf[nLen] = '';//添加字符串结尾标志

//printf(“%sn”, pchBuf);//把读取的内容输出到屏幕

fclose(pFile);//关闭文件 //free(pchBuf);//释放空间

return m_pCharBuf;}

//写入排序完成后的结果

void writeQuickSortResult(char *pResult){ FILE *pFile = fopen(“QuickSortResult.txt”, “w”);//打开文件 fputs(pResult, pFile);//写入数据 fclose(pFile);//关闭文件 }

typedef struct BiTNode{ TElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;

typedef BiTree QElemType;typedef struct QNode{ QElemType data;struct QNode *next;}QNode,*QueuePtr;typedef struct LinkQueue

{ QueuePtr front,rear;}LinkQueue;

void InitTree(BiTree*T);void DestroyBiTree(BiTree *T);void CreateBiTree(BiTree *T);Status ClearBiTree(BiTree T);Status BiTreeEmpty(BiTree T);Status BiTreeDepth(BiTree T);Status Root(BiTree T);Status Value(BiTree T,TElemType e);Status Aign(BiTree T,TElemType e,int value);Status Parent(BiTree T,TElemType e);Status LeftChild(BiTree T,TElemType e);Status RightChild(BiTree T,TElemType e);Status LeftSibling(BiTree T,TElemType e);Status RightSibling(BiTree T,TElemType e);Status InsertChild(BiTree T,int LR,BiTree C);Status DeleteChild(BiTree T,int LR);Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e));Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e));Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e));Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e));Status Visit(TElemType e);BiTree Point(BiTree T,TElemType s);//返回二叉树中指向元素值为s的结点的指针

void InitQueue(LinkQueue Q);//构造一个空队列

Status QueueEmpty(LinkQueue Q);//判断队列是否为空

void EnQueue(LinkQueue Q,QElemType e);//插入元素为新的队尾元素 Status DeQueue(LinkQueue Q,QElemType e);//删除队头元素

BiTNode * Create(FILE *fp);FILE * fileOpen();

void main(void){ int i;//文件内容读取出来

char *pText = openFileOnlyRead(“resource.txt”);printf(“%snn”, pText);

BiTree T;FILE *p;TElemType e;int n;int value;int op=1;while(op){ system(“cls”);printf(“nn”);printf(“ Menu for Linear Table On Sequence Structure n”);printf(“---------------------------n”);printf(“ 1.InitTree 11.LeftChildn”);printf(“ 2.DestroyBiTree 12.RightChildn”);printf(“ 3.CreateBiTree 13.LeftSiblingn”);printf(“ 4.ClearBiTree 14.RightSiblingn”);printf(“ 5.BiTreeEmpty 15.InsertChildn”);printf(“ 6.BiTreeDepth 16.DeleteChildn”);printf(“ 7.Root 17.PreOrderTraversen”);printf(“ 8.Value 18.InOrderTraversen”);printf(“ 9.Aign 19.PostOrderTraversen”);printf(“ 10.Parent 20.LevelOrderTraversen”);printf(“ 0.Exitn”);printf(“---------------------------n”);printf(“ 请选择你的操作[0~20]:”);scanf(“%d”,&op);switch(op){ case 1: InitTree(&T);BiTNode * Create(p);FILE * fileOpen();if(!(T)==NULL)printf(“n----二叉树初始化成功！n”);else

printf(“二叉树创建失败！n”);

getchar();getchar();

break;case 2: printf(“是否要销毁二叉树！(1为是，0是否)n”);scanf(“%d”,&n);if(n==1)DestroyBiTree(&T);else return 0;if(T!=NULL)printf(“n----二叉树成功销毁实现！n”);

else printf(“n---DestroyList功能待实现”);

getchar();getchar();

break;case 3: //InitTree(&T);printf(“Please input the char:e=n”);scanf(“%d”,&e);CreateBiTree(T);if((T)!=NULL)

printf(“n----CreateBiTree功能实现！n”);else printf(“n----CreateBiTree功能待实现！n”);

getchar();getchar();

break;case 4: ClearBiTree(T);if(T)

printf(“n----ClearBiTree功能待实现！n”);

else

printf(“n----ClearBiTree功能实现！n”);0-

getchar();getchar();break;case 5: BiTreeEmpty(T);if(T)printf(“n----BiTreeEmpty功能实现！n”);else printf(“n----BiTreeEmpty功能待实现！n”);getchar();getchar();break;case 6: BiTreeDepth(T);if(T)printf(“n----BiTreeDepth功能实现！n”);else printf(“n----BiTreeDepth功能待实现！n”);getchar();getchar();break;case 7: Root(T);if(T)printf(“n----Root功能实现！n”);else printf(“n----Root功能待实现！n”);getchar();getchar();break;case 8: printf(“Please input the node of you want:e=n”);scanf(“%c”,&e);Value(T,e);if(T==NULL)printf(“n----Value功能实现！n”);else printf(“n----Value功能待实现！n”);getchar();getchar();break;case 9: printf(“Please input the node and number of you want:e=nvalue=n”);scanf(“%c%d”,&e,&value);Aign(T,e,value);if(T==NULL)printf(“n----Aign功能实现！n”);else printf(“n----Aign功能待实现！n”);

getchar();getchar();

break;case 10: printf(“Please input the node of you want:e=n”);scanf(“%c”,&e);Parent(T,e);if(T==NULL)printf(“n----Parent功能实现！n”);

else printf(“n----Parent功能待实现！n”);

getchar();getchar();

break;case 11: printf(“Please input the node of you want:e=n”);scanf(“%c”,&e);

LeftChild(T,e);if(T!=NULL)

printf(“n----LeftChild功能实现！n”);else printf(“n----LeftChild功能待实现n”);

getchar();getchar();

break;case 12: printf(“Please input the node of you want:e=n”);scanf(“%c”,&e);

RightChild(T,e);if(T!=NULL)printf(“n----RightChild功能实现n”);else printf(“n----RightChild功能待实现！n”);

getchar();getchar();

break;case 13: printf(“Please input the node of you want:e=n”);scanf(“%c”,&e);LeftSibling(T,e);if(T!=NULL)printf(“n----LeftSibling功能实现！n”);else printf(“n----LeftSibling功能待实现n”);

getchar();getchar();

break;case 14: printf(“Please input the node of you want:e=n”);scanf(“%c”,&e);RightSibling(T,e);if(T!=NULL)printf(“n----LeftSibling功能实现！n”);else printf(“n----LeftSibling功能待实现！n”);

getchar();getchar();

break;case 15: //printf(“Please input the node of you want:p,e,LR and C=n”);// scanf(“%c”,&e);// InsertChild(T,P,LR,C);printf(“线性表是空表！n”);

getchar();getchar();

break;case 16: printf(“线性表是空表！n”);

getchar();getchar();

break;case 17: printf(“线性表是空表！n”);

getchar();getchar();

break;case 18: printf(“线性表是空表！n”);

getchar();getchar();

break;case 19: printf(“Please input the node of you want:e=n”);scanf(“%c”,&e);PostOrderTraverse(T,e);if(T!=NULL)printf(“功能实现了！n”);

else

printf(“功能待实现了！n”);

getchar();getchar();

break;case 20: printf(“线性表是空表！n”);

getchar();getchar();

break;case 0: break;}//end of switch }//end of while

char result[1000] = { “QuickSortResult:” };for(i = 0;i

//将结果写出到文件：QuickSortResult.txt writeQuickSortResult(result);getchar();free(m_pCharBuf);printf(“欢迎下次再使用本系统！n”);}//end of main()

void InitTree(BiTree *T){ T=(BiTree)malloc(sizeof(BiTNode));(*T)->data=NULL;return OK;}

void DestroyBiTree(BiTree *T){ if(T!=NULL){ DestroyBiTree((*T)->lchild);DestroyBiTree((*T)->rchild);free(T);T=NULL;} return OK;}

void CreateBiTree(BiTree *T){ /* 算法6.4:按先序次序输入二叉树中结点的值（可为字符型或整型，在主程中 */ /* 定义），构造二叉链表表示的二叉树T。变量Nil表示空（子）树。有改动 */ TElemType ch;#ifdef CHAR scanf(“%c”,&ch);#endif #ifdef INT scanf(“%d”,&ch);#endif if(ch==' ')/* 空 */ *T=NULL;else { *T=(BiTree)malloc(sizeof(BiTNode));if(!*T)exit(OVERFLOW);(*T)->data=ch;/* 生成根结点 */ CreateBiTree(&(*T)->lchild);/* 构造左子树 */ CreateBiTree(&(*T)->rchild);/* 构造右子树 */ } }

Status ClearBiTree(BiTree T){ BiTree pl,pr;if(T==NULL)return;if(T){ pl=T->lchild;pr=T->rchild;T->lchild=NULL;T->rchild=NULL;free(T);T=NULL;ClearBiTree(pl);ClearBiTree(pr);} return OK;}

Status BiTreeEmpty(BiTree T){ if(T==NULL)return TRUE;else return FALSE;} Status BiTreeDepth(BiTree T){ int lchildHigh,rchildHigh;if(T==NULL)return 0;else lchildHigh=BiTreeDepth(T->lchild);rchildHigh=BiTreeDepth(T->rchild);return lchildHigh>rchildHigh ?(lchildHigh+1):(rchildHigh+1);}

Status Root(BiTree T){ if(T==NULL)return ERROR;printf(“%c”,T->data);Root(T->lchild);Root(T->rchild);return OK;}

Status Value(BiTree T,TElemType e){ if(T==NULL)return ERROR;else if(T->data==e)return(T->data);Value(T->lchild,e);Value(T->rchild,e);return OK;}

Status Aign(BiTree T,TElemType e,int value){ if(T==NULL)return ERROR;if(T->data==e)T->data=value;else Aign(T->lchild,e,value);Aign(T->rchild,e,value);return OK;}

Status Parent(BiTree T,TElemType e){ if(T==NULL)return ERROR;if(T->data==e)if(T->lchild || T->rchild)return(T->data);else Parent(T->lchild,e);Parent(T->rchild,e);return OK;}

Status LeftChild(BiTree T,TElemType e){ if(T==NULL)return;if(T->data==e){ if(!(T->lchild))printf(“%c”,T->lchild);else return NULL;} else{ T->lchild;LeftChild(T->lchild,e);T->rchild;LeftChild(T->rchild,e);} return OK;}

Status RightChild(BiTree T,TElemType e){ if(T==NULL)return;if(T->data==e){ if(!(T->rchild))printf(“%c”,T->rchild);else return NULL;} else{ T->lchild;RightChild(T->lchild,e);T->rchild;RightChild(T->rchild,e);} return OK;}

Status LeftSibling(BiTree T,TElemType e){ //返回左兄弟 TElemType a;BiTree p;if(T){ a=Parent(T,e);//a为e的双亲 if(a!=NULL){ p=Point(T,a);//p指向结点a的指针

if(p->lchild&&p->rchild&&p->rchild->data==e)//p存在左右孩子而且右孩子是e return p->lchild->data;} } return NULL;}

Status RightSibling(BiTree T,TElemType e){ TElemType a;BiTree p;if(T){ a=Parent(T,e);//a为e的双亲 if(a!=NULL){ p=Point(T,a);//p为指向结点的a的指针

if(p->lchild&&p->rchild&&p->lchild->data==e)return p->lchild->data;} } return NULL;

} Status InsertChild(BiTree T,int LR,BiTree C){

if(T){ if(LR==0){ C->rchild=T->lchild;T->lchild=C;} else{ C->rchild=T->rchild;//T指结点的原有右子树成为C的右子树 T->rchild=C;} return OK;

} return ERROR;}

Status DeleteChild(BiTree T,int LR){ if(T){ if(LR==0)DestroyBiTree(T->lchild);else DestroyBiTree(T->rchild);return OK;} return ERROR;}

Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){ Status PrintElement(TElemType e){ printf(e);return OK;if(T){ if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))return OK;return ERROR;} else return OK;}

}//PreOrderTraaverse

Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){ Status PrintElement(TElemType e){ printf(e);return OK;if(T){ if(PreOrderTraverse(T->lchild,Visit))if(Vist(T->data));if(PreOrderTraverse(T->rchild,Visit))return OK;return ERROR;} else return OK;} }//InOrderTraverse

Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){ Status PrintElement(TElemType e){ printf(e);return OK;if(T){ if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))if(Vist(T->data))return OK;return ERROR;} else return OK;}

}//PostOrderTraverse

Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){ BiTree p,newNode;Status PrintElement(TElemType e){ printf(e);return OK;if(T){ if(p=T->lchild){ newNode=(BiTree)malloc(sizeof(BiTNode));newNode->data=e;newNode->rchild=NULL;newNode->lchild=p;T->lchild=newNode;} else return ERROR;} else return ERROR;} return OK;

}//LevelOrderTraverse

//Status Visit(TElemType e)//{ printf(“%c”,e);//} BiTree Point(BiTree T,TElemType s)//返回二叉树T中指向元素值为S的结点指针 { LinkQueue q;QElemType a;if(T){ InitQueue(q);//初始化队列 EnQueue(q,T);//根指针入队 while(!QueueEmpty(q))//队不空

{ DeQueue(q,a);//出队，队列元素赋给e if(a->data==s)//a所指结点为的值为s return a;if(a->lchild)//有左孩子

EnQueue(q,a->lchild);//入队左孩子 if(a->rchild)//有右孩子

EnQueue(q,a->rchild);//入队右孩子 } } return NULL;} void InitQueue(LinkQueue Q){//初始化一个队列

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)//生成头结点失败 exit(OVERFLOW);Q.front->next=NULL;} Status QueueEmpty(LinkQueue Q){ //判断队列是否为空 if(Q.front->next==NULL)return TRUE;else return FALSE;}

void EnQueue(LinkQueue Q,QElemType e){ //插入元素e为队列Q的新的队尾元素 QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));//动态生成新结点 if(!p)exit(OVERFLOW);p->data=e;//将e的值赋给新结点 p->next=NULL;//新结点的指针为空

Q.rear->next=p;//原队尾结点的指针域为指向新结点 Q.rear=p;//尾指针指向新结点 } Status DeQueue(LinkQueue Q,QElemType e){ //若队列不为空，删除Q的队头元素，用e返回其值 QueuePtr p;if(Q.front==Q.rear)//队列为空 return ERROR;p=Q.front->next;//p指向队头结点 e=p->data;//队头元素赋给e Q.front->next=p->next;//头结点指向下一个结点 if(Q.rear==p)//如果删除的队尾结点

Q.rear=Q.front;//修改队尾指针指向头结点 free(p);return OK;}

FILE * fileOpen(){ FILE *fp;

fp = fopen(“test.txt”, “r”);aert(fp!= NULL);return fp;}

BiTNode * Create(FILE *fp){ char ch;BiTNode * bt = NULL;

if((ch = fgetc(fp))== EOF){ return NULL;}

if('#'!= ch){ bt =(BiTNode *)malloc(sizeof(BiTNode));bt->data = ch;bt->lchild = Create(fp);bt->rchild = Create(fp);}

return bt;}

Status InitStack(SqStack*S){ S->base=(TElemType*)malloc(MAX_TREE_SIZE*sizeof(TElemType));if(!(S->base))exit(OVERFLOW);S->top=S->base;S->stacksize=MAX_TREE_SIZE;return OK;}

Status Pop(SqStack*S,TElemType e){ if(S->top==S->base)return ERROR;e=*--S->top;return OK;} Status Push(SqStack*S,TElemType e){ if(S->top-S->base>=S->stacksize){

S->base=(TElemType*)malloc(((S->stacksize)+MAX_TREE_SIZE)*sizeof(TElemType));if(!(S->base))exit(OVERFLOW);S->top=S->base+S->stacksize;S->stacksize+=MAX_TREE_SIZE;}

*S->top++=e;return OK;} Status StackEmpty(SqStack*S){ if(S==NULL)return OK;else return FALSE;}