第一篇：《数据结构》课程实验报告
实验一 基于二叉链表的二叉树的实现
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 Assign功能
求指定元素的后一个元素的内容，传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。找到后，把新的数据值赋给所找到的节点。时间复杂度为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，Assign，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
#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 Assign(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.Assign 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);Assign(T,e,value);if(T==NULL)printf(“n----Assign功能实现！n”);else printf(“n----Assign功能待实现！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 < m_nCount;++i){ printf(“%d ”, m_nList[i]);char number[100] = {};_itoa(m_nList[i], number, 10);strcat(result, “ ”);strcat(result, number);}
//将结果写出到文件：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 Assign(BiTree T,TElemType e,int value){ if(T==NULL)return ERROR;if(T->data==e)T->data=value;else Assign(T->lchild,e,value);Assign(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”);assert(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;}
第二篇：数据结构实验报告
注意：实验结束后提交一份实验报告电子文档
电子文档命名为“学号+姓名”，如：E01214058宋思怡
《数据结构》实验报告
（一）学号：姓名：专业年级：
实验名称：线性表
实验日期：2014年4月14日
实验目的：
1、熟悉线性表的定义及其顺序和链式存储结构；
2、熟练掌握线性表在顺序存储结构上实现基本操作的方法；
3、熟练掌握在各种链表结构中实现线性表基本操作的方法；
4、掌握用 C/C++语言调试程序的基本方法。
实验内容：
一、编写程序实现顺序表的各种基本运算，并在此基础上设计一个主程序完成如下功能：
（1）初始化顺序表L；
（2）依次在L尾部插入元素-1,21,13,24,8；
（3）输出顺序表L；
（4）输出顺序表L长度；
（5）判断顺序表L是否为空；
（6）输出顺序表L的第3个元素；
（7）输出元素24的位置；
（8）在L的第4个元素前插入元素0；
（9）输出顺序表L；
（10）删除L的第5个元素；
（11）输出顺序表L。
源代码
调试分析（给出运行结果界面）
二、编写程序实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能：
„„„„
„„„„
小结或讨论:
（1）实验中遇到的问题和解决方法
（2）实验中没有解决的问题
（3）体会和提高
第三篇：数据结构实验报告
南京信息工程大学实验（实习）报告
实验（实习）名称数据结构实验（实习）日期 2011-11-2得分指导教师周素萍
系公共管理系专业信息管理与信息系统年级10级班次1姓名常玲学号2010230700
3实验一顺序表的基本操作及C语言实现
【实验目的】
1、顺序表的基本操作及 C 语言实现
【实验要求】
1、用 C 语言建立自己的线性表结构的程序库，实现顺序表的基本操作。
2、对线性表表示的集合，集合数据由用户从键盘输入（数据类型为整型），建立相应的顺序表，且使得数据按从小到大的顺序存放，将两个集合的并的结果存储在一个新的线性表集合中，并输出。
【实验内容】
1、根据教材定义的顺序表机构，用 C 语言实现顺序表结构的创建、插入、删除、查找等操作；
2、利用上述顺序表操作实现如下程序：建立两个顺序表表示的集合（集合中无重
复的元素），并求这样的两个集合的并。
【实验结果】
[实验数据、结果、遇到的问题及解决]
一． Status InsertOrderList(SqList &va,ElemType x)
{
}
二． Status DeleteK(SqList &a,int i,int k)
{//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x } //注意i的编号从0开始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK; 三．// 将合并逆置后的结果放在C表中，并删除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驱指针 // 保存pb的前驱指针 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//将当前最小结点插入A表表头 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//将当前最小结点插入A表表头 A->next=qa; } } pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb; 顺序表就是把线性表的元素存储在数组中，元素之间的关系直接通过相邻元素的位置来表达。 优点：简单，数据元素的提取速度快； 缺点：（1）静态存储，无法预知问题规模的大小，可能空间不足，或浪费存储空间；（2）插入元素和删除元素时间复杂度高——O（n） 求两个集合的并集 该算法是求两个集合s1和s2的并集，并将结果存入s引用参数所表示的集合中带回。首先把s1集合复制到s中，然后把s2中的每个元素依次插入到集合s中，当然重复的元素不应该被插入，最后在s中就得到了s1和s2的并集，也就是在s所对应的实际参数集合中得到并集。 数据结构实验报告 一． 题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二． 解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree;intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1;} else if(key InsertBST(T->rChild,key);} else return 0;} BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL;inti=0;while(i //数据域 InsertBST(bst,a[i]); i++;} returnbst;} int Delete(BiTree&T) { BiTreeq,s; } if(!(T)->rChild){ //右子树为空重接它的左子树 q=T;T=(T)->lChild;free(q);}else{ if(!(T)->lChild){ //若左子树空则重新接它的右子树 q=T;T=(T)->rChild;}else{ q=T;s=(T)->lChild;while(s->rChild){ q=s;s=s->rChild;} (T)->data=s->data;//s指向被删除结点的前驱 if(q!=T) q->rChild=s->lChild; else q->lChild=s->lChild; free(s);} } return 1; //删除函数，在T中删除key元素 intDeleteBST(BiTree&T,int key){ if(!T)return 0;else{ if(key==(T)->data)return Delete(T); else{ if(key<(T)->data) returnDeleteBST(T->lChild,key); else returnDeleteBST(T->rChild,key); } } } intPosttreeDepth(BiTree T){//求深度 inthr,hl,max;if(!T==NULL){ hl=PosttreeDepth(T->lChild);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;return max+1;} else return 0; } void printtree(BiTreeT,intnlayer){//打印二叉树 if(T==NULL)return;printtree(T->rChild,nlayer+1);for(inti=0;i ”);} printf(“%dn”,T->data);printtree(T->lChild,nlayer+1);} void PreOrderNoRec(BiTree root)//先序非递归遍历 { BiTree p=root;BiTreestack[50];intnum=0;while(NULL!=p||num>0){ while(NULL!=p) { printf(“%d ”,p->data); stack[num++]=p; p=p->lChild; } num--; p=stack[num]; p=p->rChild;} printf(“n”);} void InOrderNoRec(BiTree root)//中序非递归遍历 { BiTree p=root; } intnum=0;BiTreestack[50];while(NULL!=p||num>0){ while(NULL!=p){ stack[num++]=p; p=p->lChild;} num--;p=stack[num];printf(“%d ”,p->data);p=p->rChild;} printf(“n”);void PostOrderNoRec(BiTree root)//后序非递归遍历 { BiTree p=root;BiTreestack[50];intnum=0;BiTreehave_visited=NULL; while(NULL!=p||num>0){ while(NULL!=p) { stack[num++]=p; p=p->lChild; } p=stack[num-1]; if(NULL==p->rChild||have_visited==p->rChild) { printf(“%d ”,p->data); num--; have_visited=p; p=NULL; } else { p=p->rChild; } } printf(“n”);} int main(){//主函数 printf(“ ---------------------二叉排序树的实现-------------------”);printf(“n”);int layer;inti;intnum;printf(“输入节点个数:”);scanf(“%d”,&num);printf(“依次输入这些整数（要不相等）”);int *arr=(int*)malloc(num*sizeof(int));for(i=0;i scanf(“%d”,arr+i);} BiTreebst=CreateBST(arr,num);printf(“n”);printf(“二叉树创建成功!”);printf(“n”);layer=PosttreeDepth(bst);printf(“树状图为:n”);printtree(bst,layer);int j;int T;int K;for(;;){ loop: printf(“n”);printf(“ ***********************按提示输入操作符************************:”);printf(“n”);printf(“ 1:插入节点 2:删除节点 3:打印二叉树 4:非递归遍历二叉树 5:退出”);scanf(“%d”,&j); switch(j){ case 1: printf(“输入要插入的节点:”); scanf(“%d”,&T); InsertBST(bst,T); printf(“插入成功!”);printf(“树状图为:n”); printtree(bst,layer); break; case 2: } printf(“输入要删除的节点”);scanf(“%d”,&K);DeleteBST(bst,K);printf(“删除成功!”);printf(“树状图为:n”);printtree(bst,layer);break;case 3: layer=PosttreeDepth(bst);printtree(bst,layer);break;case 4: printf(“非递归遍历二叉树”);printf(“先序遍历:n”);PreOrderNoRec(bst);printf(“中序遍历:n”);InOrderNoRec(bst); printf(“后序遍历:n”); PostOrderNoRec(bst); printf(“树状图为:n”); printtree(bst,layer); break;case 5: printf(“程序执行完毕!”); return 0;} goto loop;} return 0;对于第四小问，要储存学生的三个信息，需要把上面程序修改一下，二叉树结构变为 typedefintElemType; //数据类型 typedefstring SlemType; typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ SlemType name;ElemType score;ElemType no; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree;参数不是key,而是另外三个 intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉树函数 if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->no=no;T->name=name;T->score=score; T->lChild=T->rChild=NULL; return 1;} else if(no InsertBST(T->rChild,no,score,name);} else return 0;} 其他含参函数也类似 即可完成50个信息存储 用数组存储50个信息，查看以往代码 #include int main(){ cout<<“ 欢迎来到学生管理系统”< cout<<“该学号信息已经存在，添加失败”< break;} cout<<“重新输入添加的学号”< for(int n=m+1;n<20;n++){ if(ptr[m].average() student a; a=ptr[m]; ptr[m]=ptr[n]; ptr[n]=a; }} ptr[m].show();} break;case 4: cout<<“谢谢使用”< 二叉排序树储存数据界面（储存学生信息略） 创建二叉树： 插入节点： 删除节点： 非递归遍历： 退出： 数组储存学生信息界面 分析查找效率： 因为二叉树查找要创建二叉树，而数组查找只创建一个数组，二叉树的创建时间比较长，所以对于数据量较少的情况下数组的查找效率比较高。但当数据量增加时，二叉树的查找优势就显现出来。所以数据量越大的时候，二叉树的查找效率越高。 四． 总结与改进 这个实验工作量还是很大的，做了很久。树状图形输出还是不美观，还需要改进。 一开始打算用栈实现非递归，但是根据书里面的伪代码发现部分是在C++编译器里运行不了的（即使补充了头文件和数据的定义），所以之后参考了网上的数组非递归，发现其功能和栈相似。 递归遍历的实现比非递归的遍历真的简单很多。 开始时只看到前三问，所以没有写到储存学生数据的代码，里面还可以用clock（）函数加一个计算查找所要数据时间的代码，让二叉树查找与数组查找到效率比较更加直观。 实验报告4 排序 一、实验目的 1、掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。 2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。 3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。 二、实验要求及内容 要求编写的程序所能实现的功能包括： 1、从键盘输入要排序的一组元素的总个数 2、从键盘依次输入要排序的元素值 3、对输入的元素进行快速排序 4、对输入的元素进行折半插入排序 三、实验代码及相关注释 #include typedef struct { int key;}RedType; typedef struct { RedType r[100];int length;}SqList; //1 快速排序的结构体 typedef struct { int data[100]; int last;}Sequenlist;//2 折半插入排序的结构体 int Partition(SqList &L, int low, int high) //1 寻找基准 { L.r[0]=L.r[low];//子表的第一个记录作基准对象 int pivotkey = L.r[low].key;//基准对象关键字 while(low while(low L.r[low] = L.r[high];//小于基准对象的移到区间的左侧 while(low L.r[high] = L.r[low];//大于基准对象的移到区间的右侧 } L.r[low] = L.r[0];return low;} void QuickSort(SqList &L, int low, int high) //1 快速排序 { //在序列low-high中递归地进行快速排序 if(low < high) { int pivotloc= Partition(L, low, high); //寻找基准 QuickSort(L, low, pivotloc-1);//对左序列同样递归处理 QuickSort(L, pivotloc+1, high);//对右序列同样递归处理 } } Sequenlist *Sqlset() //2 输入要折半插入排序的一组元素 { Sequenlist *L; int i; L=(Sequenlist *)malloc(sizeof(Sequenlist)); L->last=0; cout<<“请输入要排序的所有元素的总个数：”; cin>>i; cout< cout<<“请依次输入所有元素的值：”; if(i>0) { for(L->last=1;L->last<=i;L->last++) cin>>L->data[L->last]; L->last--; } return(L);} middlesort(Sequenlist *L) //2 折半插入排序 { int i,j,low,high,mid;for(i=1;i<=L->last;i++){ L->data[0]=L->data[i]; low=1; high=i-1; while(low<=high) { mid=(low+high)/2; if(L->data[0] high=mid-1;//插入点在前半区 else low=mid+1;//插入点在后半区 } for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移 L->data[high+1]=L->data[0];//插入 } return 0;} int main(){ gg: cout<<“请选择功能（1.快速排序 2.折半插入排序 3.退出程序）：”;int m;cin>>m;cout< if(m==1){ SqList L;int n;cout<<“请输入要排序的所有元素的总个数：”;cin>>n;cout< cin>>L.r[i].key; } cout< QuickSort(L,1,L.length); for(int j=1;j<=L.length;j++) { cout< } cout< cout< } if(m==2){ Sequenlist *L; int i; L=Sqlset(); cout< middlesort(L); cout<<“折半插入排序后为：”; for(i=1;i<=L->last;i++) { cout< } cout< cout< goto gg;} if(m==3){ exit(0); cout< 四、重要函数功能说明 1、Sequenlist *Sqlset() 输入要折半插入排序的一组元素 2、int Partition(SqList &L, int low, int high) 寻找快速排序的基准 3、void QuickSort(SqList &L, int low, int high) 快速排序 4、middlesort(Sequenlist *L) 折半插入排序 五、程序运行结果 下图仅为分别排序一次，可多次排序，后面有相关截图： 六、实验中遇到的问题、解决及体会 1、起初编写快速排序的程序时，我是完全按照老师PPT上的算法敲上去的，然后建立了一个SqList的结构体，调试运行时出现错误，仔细查看才意识到Partition函数中L中应该包含元素key，而我建立结构体时没有注意，然后我将key这个元素补充进去，继续调试，又出现错误，提示我Partition没有定义，我就觉得很奇怪，我明明已经写了函数定义，为什么会这样，当我又回过头来阅读程序时，我发现QuickSort函数中调用了Partition函数，但是我的Partition函数的定义在QuickSort函数的后面，于是我将Partition函数放到了QuickSort函数的前面，再次调试运行，就可以正常运行，得出结果了。这让我懂得，编程一定要认真仔细，不可大意马虎，否则又会花很多时间回过头来检查修改程序，得不偿失。 运行程序错误截图： 2、本来我是编写了两个程序，分别实现快速排序和折半插入排序的功能，但我后来想我是否可以将其合二为一，于是我想到用if选择语句用来实现不同的功能，从键盘输入功能选项m，if（m==1），可以进行快速排序，if（m==2），可以进行折半插入排序，于是我继续思考，我是否可以在一次运行程序中，多次对含有不同元素的序列进行排序，于是我用了goto语句，每次排序一次后，自动循环到选择语句，当不需要在排序的时候，可以从键盘输入3，退出程序，这样一来，程序变得更加实用和清晰明朗。这让我懂得，想要编出好的程序，要善于思考，在实现所需功能的前提下，多想问题，看是否能使程序更加实用简便。 修改程序前两个运行结果截图 （两个程序，调试运行两次，每次只能进行一次排序） 1、快速排序程序运行结果截图： 2、折半插入排序程序结果截图： 程序重要模块修改截图： 修改程序后运行截图： （一个程序，调试运行一次，可多次进行不同序列的不同排序）第四篇：数据结构实验报告
第五篇：数据结构实验报告
点击咨询 