下载文档原格式
《数据结构》实验报告模板(附实例)---实验一线性表的基本操作实现实验一线性表的基本操作实现及其应用一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现，其中以熟悉各种链表的操作为重点。
2、巩固高级语言程序设计方法与技术，会用线性链表解决简单的实际问题。
二、实验内容√ 1、单链表的表示与操作实现 ( * )2、约瑟夫环问题3、Dr.Kong的艺术品三、实验要求1、按照数据结构实验任务书，提前做好实验预习与准备工作。
2、加“*”题目必做，其他题目任选；多选者并且保质保量完成适当加分。
3、严格按照数据结构实验报告模板和规范，及时完成实验报告。
四、实验步骤（说明：依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作（成员函数）的伪码算法、函数实现、程序编码、调试与分析、总结、附流程图与主要代码）㈠、数据结构与核心算法的设计描述（程序中每个模块或函数应加注释，说明函数功能、入口及出口参数）1、单链表的结点类型定义/* 定义DataType为int类型 */typedef int DataType;/* 单链表的结点类型 */typedef struct LNode{ DataType data;struct LNode *next;}LNode,*LinkedList;2、初始化单链表LinkedList LinkedListInit( ){ // 每个模块或函数应加注释，说明函数功能、入口及出口参数 }3、清空单链表void LinkedListClear(LinkedList L){// 每个模块或函数应加注释，说明函数功能、入口及出口参数}4、检查单链表是否为空int LinkedListEmpty(LinkedList L){ …. }5、遍历单链表void LinkedListTraverse(LinkedList L){….}6、求单链表的长度int LinkedListLength(LinkedList L){ …. }7、从单链表表中查找元素LinkedList LinkedListGet(LinkedList L,int i){ //L是带头结点的链表的头指针，返回第 i 个元素 }8、从单链表表中查找与给定元素值相同的元素在链表中的位置LinkedList LinkedListLocate(LinkedList L, DataType x){ …… }9、向单链表中插入元素void LinkedListInsert(LinkedList L,int i,DataType x) { // L 为带头结点的单链表的头指针，本算法// 在链表中第i 个结点之前插入新的元素 x}10、从单链表中删除元素void LinkedListDel(LinkedList L,DataType x){ // 删除以 L 为头指针的单链表中第 i 个结点 }11、用尾插法建立单链表LinkedList LinkedListCreat( ){ …… }㈡、函数调用及主函数设计（可用函数的调用关系图说明）㈢程序调试及运行结果分析㈣实验总结五、主要算法流程图及程序清单1、主要算法流程图：2、程序清单（程序过长，可附主要部分）说明：以后每次实验报告均按此格式书写。
数据结构实验报告实验5一、实验目的本次实验的主要目的是深入理解和掌握常见的数据结构，如链表、栈、队列、树和图等，并通过实际编程实现，提高对数据结构的操作和应用能力。
同时，培养解决实际问题的思维和编程能力，提高代码的可读性、可维护性和效率。
二、实验环境本次实验使用的编程语言为C+＋，开发环境为Visual Studio 2019。
三、实验内容1、链表的基本操作创建链表插入节点删除节点遍历链表2、栈的实现与应用用数组实现栈用链表实现栈栈的应用：括号匹配3、队列的实现与应用用数组实现队列用链表实现队列队列的应用：排队模拟4、二叉树的遍历前序遍历中序遍历后序遍历5、图的表示与遍历邻接矩阵表示法邻接表表示法深度优先遍历广度优先遍历四、实验步骤1、链表的基本操作创建链表：首先定义一个链表节点结构体，包含数据域和指向下一个节点的指针域。
然后通过动态内存分配创建链表节点，并将节点逐个连接起来，形成链表。
插入节点：根据插入位置的不同，分为在表头插入、在表尾插入和在指定位置插入。
在指定位置插入时，需要先找到插入位置的前一个节点，然后进行节点的连接操作。
删除节点：同样需要根据删除位置的不同进行处理。
删除表头节点时，直接将头指针指向下一个节点；删除表尾节点时，找到倒数第二个节点，将其指针置为空；删除指定位置节点时，找到要删除节点的前一个节点，然后调整指针。
遍历链表：通过从链表头开始，依次访问每个节点，输出节点的数据。
2、栈的实现与应用用数组实现栈：定义一个固定大小的数组作为栈的存储空间，同时用一个变量记录栈顶位置。
入栈操作时，先判断栈是否已满，如果未满则将元素放入栈顶位置，并更新栈顶位置；出栈操作时，先判断栈是否为空，如果不空则取出栈顶元素，并更新栈顶位置。
用链表实现栈：与链表的操作类似，将新元素添加在链表头部作为栈顶。
括号匹配：输入一个包含括号的字符串，使用栈来判断括号是否匹配。
遇到左括号入栈，遇到右括号时与栈顶的左括号进行匹配，如果匹配成功则出栈，否则括号不匹配。
数据结构实验三实验报告数据结构实验三实验报告一、实验目的本次实验的目的是通过实践掌握树的基本操作和应用。
具体来说，我们需要实现一个树的数据结构，并对其进行插入、删除、查找等操作，同时还需要实现树的遍历算法，包括先序、中序和后序遍历。
二、实验原理树是一种非线性的数据结构，由结点和边组成。
树的每个结点都可以有多个子结点，但是每个结点只有一个父结点，除了根结点外。
树的基本操作包括插入、删除和查找。
在本次实验中，我们采用二叉树作为实现树的数据结构。
二叉树是一种特殊的树，每个结点最多只有两个子结点。
根据二叉树的特点，我们可以使用递归的方式实现树的插入、删除和查找操作。
三、实验过程1. 实现树的数据结构首先，我们需要定义树的结点类，包括结点值、左子结点和右子结点。
然后，我们可以定义树的类，包括根结点和相应的操作方法，如插入、删除和查找。
2. 实现插入操作插入操作是将一个新的结点添加到树中的过程。
我们可以通过递归的方式实现插入操作。
具体来说，如果要插入的值小于当前结点的值，则将其插入到左子树中；如果要插入的值大于当前结点的值，则将其插入到右子树中。
如果当前结点为空，则将新的结点作为当前结点。
3. 实现删除操作删除操作是将指定的结点从树中移除的过程。
我们同样可以通过递归的方式实现删除操作。
具体来说，如果要删除的值小于当前结点的值，则在左子树中继续查找；如果要删除的值大于当前结点的值，则在右子树中继续查找。
如果要删除的值等于当前结点的值，则有三种情况：- 当前结点没有子结点：直接将当前结点置为空。
- 当前结点只有一个子结点：将当前结点的子结点替代当前结点。
- 当前结点有两个子结点：找到当前结点右子树中的最小值，将其替代当前结点，并在右子树中删除该最小值。
4. 实现查找操作查找操作是在树中寻找指定值的过程。
同样可以通过递归的方式实现查找操作。
具体来说，如果要查找的值小于当前结点的值，则在左子树中继续查找；如果要查找的值大于当前结点的值，则在右子树中继续查找。
数据结构课程设计开题报告表课程设计1 线性表课程设计一、组长：二、组员：三、实验日期：2010/4/10四、实验任务：集合操作（2分）基本功能要求：（1）从文件中读入集合数据建立单链表。
（2）分别求出集合的交、并、差。
五、实验原理：。
（具体思路看注释）（1）定义单链表结点类型；（2）建立函数，将数组元素以尾插法的方法插入到单链表中；（3）建立函数以指针移动的方式将单链表显示出来；（4）建立求并集的函数，以指针移动的方式将L1和L2中的元素放入L3中；（5）建立求交集的函数，以指针移动的方式将L1和L2中相同的元素放到L4中；（6）建立求差集的函数，以指针移动的方式将L1有而L2中无的元素放到L5中；（7）建立主函数，实现以上功能；六、实验源程序：#include <stdio.h>#include <stdlib.h>typedef struct LNode //定义单链表结点类型{char data;struct LNode *next;} LinkList;LinkList *CreatList(LinkList *L,char a[],int n) /*尾插法插入元素*/{LinkList *p,*r;int i;L=(LinkList*)malloc(sizeof(LinkList));L->next=NULL;r=L;for(i=0;i<n;i++){p=(LinkList*)malloc(sizeof(LinkList));p->data=a[i];r->next=p;r=p;}r->next=NULL;return (L);}void DispList(LinkList *L) /*显示链表*/{int i=0;LinkList *p;p=L->next;while(p!=NULL){printf("%c",p->data);p=p->next;}printf("\n");}LinkList *BingJi(LinkList *L1,LinkList *L2,LinkList *L3) /*求两个集合的并集*/{LinkList *p1=L1->next,*p2=L2->next,*s,*t;L3=(LinkList *)malloc(sizeof(LinkList));t=L3;while (p1!=NULL && p2!=NULL) /*当L1和L2都不为空的情况下比较各自数值的大小*/ {if (p1->data<p2->data) /*先记录较小的数值，并移动其指针*/{s=(LinkList *)malloc(sizeof(LinkList));s->data=p1->data;t->next=s;t=s;p1=p1->next;}else if (p1->data>p2->data){s=(LinkList *)malloc(sizeof(LinkList));s->data=p2->data;t->next=s;t=s;p2=p2->next;}else /*当两个数值相同时仅记录一个，并移动各自的指针*/{s=(LinkList *)malloc(sizeof(LinkList));s->data=p1->data;t->next=s;t=s;p1=p1->next;p2=p2->next;}}while(p1==NULL&&p2!=NULL) /*当有一个单链表已经比较完毕时，将另外一个单链表的剩余数值全部记录下来*/{s=(LinkList *)malloc(sizeof(LinkList));s->data=p2->data;t->next=s;t=s;p2=p2->next;}while (p2==NULL&&p1!=NULL){s=(LinkList *)malloc(sizeof(LinkList));s->data=p1->data;t->next=s;t=s;p1=p1->next;}t->next=NULL;return(L3);}LinkList *JiaoJi(LinkList *L1,LinkList *L2,LinkList *L4) /*求两集合的交集*/{LinkList *p1=L1->next,*p2,*s,*t;L4=(LinkList *)malloc(sizeof(LinkList));t=L4;while (p1!=NULL) /*在L1不为空时求交集，否则交集为空*/{p2=L2->next;while (p2!=NULL && p2->data<p1->data) /*按顺序比较各自数值的大小，若不相等就移动较小数值的指针*/{p2=p2->next;}if (p2!=NULL && p2->data==p1->data)/*若相等就记录下来*/{s=(LinkList *)malloc(sizeof(LinkList));s->data=p1->data;t->next=s;t=s;}p1=p1->next;}t->next=NULL;return(L4);}LinkList *ChaJi(LinkList *L1,LinkList *L2,LinkList *L5) /*求两集合的差集*/{LinkList *p1=L1->next,*p2,*s,*t;L5=(LinkList *)malloc(sizeof(LinkList));t=L5;while (p1!=NULL) /*仅在L1不为空的情况下求差集，否则差集为空*/{p2=L2->next;while (p2!=NULL && p2->data<p1->data) /*若L2的数值小于L1的数值就移动指针*/ {p2=p2->next;}if (!(p2!=NULL && p2->data==p1->data)) /*记录L1中有而L2中无的数值*/{s=(LinkList *)malloc(sizeof(LinkList));s->data=p1->data;t->next=s;t=s;}p1=p1->next;}t->next=NULL;return(L5);}void main() /*主函数，实现上述功能*/{char a[]={'2','4','5','8'};char b[]={'1','2','3','6','8','9'};LinkList *L1,*L2,*L3,*L4,*L5;L1=(LinkList *)malloc(sizeof(LinkList));L2=(LinkList *)malloc(sizeof(LinkList));L3=(LinkList *)malloc(sizeof(LinkList));printf("集合L1为：");L1=CreatList(L1,a,4);DispList(L1);printf("集合L2为：");L2=CreatList(L2,b,6);DispList(L2);L3=BingJi(L1,L2,L3);printf("两个集合的并集为:");DispList(L3);L4=(LinkList *)malloc(sizeof(LinkList));L4=JiaoJi(L1,L2,L4);printf("两个集合的交集为:");DispList(L4);L5=(LinkList *)malloc(sizeof(LinkList));L5=ChaJi(L1,L2,L5);printf("两个集合的差集为:");DispList(L5);}七、实验结果截图：八、实验任务分工：课程设计2 双栈共享空间一、组长：二、组员：三、实验日期：2010/4/20四、实验任务：设STACK[MAXSIZE]为n（n>2）个栈共享。
数据结构实验报告数据结构实验报告精选2篇（一）实验目的：1. 熟悉数据结构的基本概念和基本操作；2. 掌握线性表、栈、队列、链表等经典数据结构的实现方法；3. 掌握数据结构在实际问题中的应用。
实验内容：本次实验主要包括以下几个部分：1. 线性表的实现方法，包括顺序表和链表，分别使用数组和链表来实现线性表的基本操作；2. 栈的实现方法，包括顺序栈和链式栈，分别使用数组和链表来实现栈的基本操作；3. 队列的实现方法，包括顺序队列和链式队列，分别使用数组和链表来实现队列的基本操作；4. 链表的实现方法，包括单链表、双链表和循环链表，分别使用指针链、双向链和循环链来实现链表的基本操作；5. 综合应用，使用各种数据结构来解决实际问题，例如使用栈来实现括号匹配、使用队列来实现马铃薯游戏等。
实验步骤及结果：1. 线性表的实现方法：a) 顺序表的基本操作：创建表、插入元素、删除元素、查找元素等；b) 链表的基本操作：插入节点、删除节点、查找节点等；c) 比较顺序表和链表的优缺点，分析适用场景。
结果：通过实验，确认了顺序表适用于频繁查找元素的情况，而链表适用于频繁插入和删除节点的情况。
2. 栈的实现方法：a) 顺序栈的基本操作：进栈、出栈、判空、判满等；b) 链式栈的基本操作：进栈、出栈、判空、判满等。
结果：通过实验，掌握了栈的基本操作，并了解了栈的特性和应用场景，例如括号匹配。
3. 队列的实现方法：a) 顺序队列的基本操作：入队、出队、判空、判满等；b) 链式队列的基本操作：入队、出队、判空、判满等。
结果：通过实验，掌握了队列的基本操作，并了解了队列的特性和应用场景，例如马铃薯游戏。
4. 链表的实现方法：a) 单链表的基本操作：插入节点、删除节点、查找节点等；b) 双链表的基本操作：插入节点、删除节点、查找节点等；c) 循环链表的基本操作：插入节点、删除节点、查找节点等。
结果：通过实验，掌握了链表的基本操作，并了解了链表的特性和应用场景。
数据结构综合设计实验报告好啦，今天咱们来聊聊“数据结构综合设计实验报告”这事儿。
首先得说，虽然这听上去像是一道艰深的题目，但其实也没想象的那么复杂。
你要知道，数据结构这个东西，说白了就是咱们用来存储和管理数据的各种方式。
就像你家里放东西的柜子，你得知道什么东西放哪个抽屉，啥该挂在墙上，啥放在桌子上。
这样生活起来才方便，对吧？数据结构就相当于是这座“数据大厦”的设计图。
你能想象吗？如果没有一个好的数据结构，处理数据就像是你在找个放杂物的地方找个特定的袜子，根本找不到！好了，说到实验报告，可能大家会想，实验报告嘛，就是写写写，写了半天就是总结总结，结论写个结尾啥的。
其实不然。
做这个实验报告，你得好好思考，得分析背后的每个数据结构为什么选择它，为什么这样设计。
就拿链表来说吧，这种结构可不是随便来的。
它就像是你手里那一串串的钥匙，每一把钥匙能开一个锁，但这些锁之间并不一定是顺序排列的，而是按需拼凑的。
链表的好处就是能根据需要灵活地增删节点，不需要像数组那样，一旦放进去就固定死了。
你说，谁不喜欢灵活性大一点的东西？然后再说说栈吧，这东西一听就让人联想到摞起来的盘子，或者你家的衣服堆成山，最上面的一件衣服总是最容易拿到。
栈的原则就是“先进后出”。
拿盘子来说，你最先放的盘子，是在最下面的，最后放的才是最上面的。
你每次取盘子，都是先拿最上面那一块，其他的都得等着。
这就有点类似我们的“先到先得”原则，但栈可不是那种随便排队的，谁在最上面就先来，其他的得排排队。
接下来聊聊队列。
说到队列，大家肯定就想起了超市的结账排队。
排队的人一个接一个，谁先来，谁就先走。
队列就是按照这个规则来操作的。
就像是排队买个冰淇淋，你不能插队，得等着自己的轮到。
这种“先进先出”的规则让队列变得非常简单有效。
当你需要按顺序处理数据时，队列是最靠谱的选择。
好啦，再讲讲哈希表。
哈希表有点像你家里放东西的那个抽屉柜，里面每个抽屉都有一个标签，可以快速找到你想要的东西。
班级：姓名：学号：实验一线性表的基本操作一、实验目的1、掌握线性表的定义；2、掌握线性表的基本操作;如建立、查找、插入和删除等..二、实验内容定义一个包含学生信息学号;姓名;成绩的顺序表和链表二选一;使其具有如下功能：1 根据指定学生个数;逐个输入学生信息；2 逐个显示学生表中所有学生的相关信息；3 根据姓名进行查找;返回此学生的学号和成绩；4 根据指定的位置可返回相应的学生信息学号;姓名;成绩；5 给定一个学生信息;插入到表中指定的位置；6 删除指定位置的学生记录；7 统计表中学生个数..三、实验环境Visual C++四、程序分析与实验结果#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<string.h>#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status; // 定义函数返回值类型typedef struct{char num10; // 学号char name20; // 姓名double grade; // 成绩}student;typedef student ElemType;typedef struct LNode{ElemType data; // 数据域struct LNode *next; //指针域}LNode;*LinkList;Status InitListLinkList &L // 构造空链表L {L=struct LNode*mallocsizeofstruct LNode; L->next=NULL;return OK;}Status GetElemLinkList L;int i;ElemType &e // 访问链表;找到i位置的数据域;返回给 e{LinkList p;p=L->next;int j=1;whilep&&j<i{p=p->next;++j;}ifp||j>i return ERROR;e=p->data;return OK;}Status SearchLNode L;char str;LinkList &p // 根据名字查找{p=L.next;whilep{ifstrcmpp->;str==0return OK;p=p->next;}return ERROR;}Status ListInsertLinkList L;int i;ElemType e // 在i个位置插入某个学生的信息{LinkList p;s;p=L;int j=0;whilep&&j<i-1{p=p->next;++j;}ifp||j>i-1 return ERROR;s=struct LNode*mallocsizeofLNode;s->data=e;s->next=p->next;p->next=s;return OK;}Status ListDeleteLinkList p;int i // 删除i位置的学生信息{int j=0;whilep->next&&j<i-1{p=p->next;++j;}ifp->next||j>i-1 return ERROR;LinkList q;q=p->next;p->next=q->next;delete q;return OK;}void InputElemType *e{printf"姓名:"; scanf"%s";e->name;printf"学号:"; scanf"%s";e->num;printf"成绩:"; scanf"%lf";&e->grade;printf"输入完成\n\n";}void OutputElemType *e{printf"姓名:%-20s\n学号:%-10s\n成绩:%-10.2lf\n\n";e->name;e->num;e->grade;}int main{LNode L;LinkList p;ElemType a;b;c;d;printf"\n********************************\n\n";puts"1. 构造链表";puts"2. 录入学生信息";puts"3. 显示学生信息";puts"4. 输入姓名;查找该学生";puts"5. 显示某位置该学生信息";puts"6. 在指定位置插入学生信息";puts"7. 在指定位置删除学生信息";puts"8. 统计学生个数";puts"0. 退出";printf"\n********************************\n\n"; int x;choose=-1;whilechoose=0{puts"请选择:";scanf"%d";&choose;switchchoose{case 1:ifInitListpprintf"成功建立链表\n\n";elseprintf"链表建立失败\n\n";break;case 2:printf"请输入要录入学生信息的人数:";scanf"%d";&x;forint i=1;i<=x;i++{printf"第%d个学生:\n";i;Input&a;ListInsert&L;i;a;}break;case 3:forint i=1;i<=x;i++{GetElem&L;i;b;Output&b;}break;case 4:char s20;printf"请输入要查找的学生姓名:";scanf"%s";s;ifSearchL;s;pOutput&p->data;elseputs"对不起;查无此人";puts"";break;case 5:printf"请输入要查询的位置:";int id1;scanf"%d";&id1;GetElem&L;id1;c;Output&c;break;case 6:printf "请输入要插入的位置:";int id2;scanf"%d";&id2;printf"请输入学生信息:\n";Input&d;ifListInsert&L;id2;d{x++;puts"插入成功";puts"";}else{puts"插入失败";puts"";}break;case 7:printf"请输入要删除的位置:";int id3;scanf"%d";&id3;ifListDelete&L;id3{x--;puts"删除成功";puts"";}else{puts"删除失败";puts"";}break;case 8:printf"已录入的学生个数为:%d\n\n";x;break;}}printf"\n\n谢谢您的使用;请按任意键退出\n\n\n"; system"pause";return 0;}用户界面:(1)根据指定学生个数;逐个输入学生信息：(2)逐个显示学生表中所有学生的相关信息：(3)根据姓名进行查找;返回此学生的学号和成绩：(4)根据指定的位置可返回相应的学生信息学号;姓名;成绩：(5)给定一个学生信息;插入到表中指定的位置：(6)删除指定位置的学生记录：(7)统计表中学生个数：五、实验总结数据结构是一门专业技术基础课..它要求学会分析研究计算机加工的数据结构的特性;以便为应用涉及的数据选择适当的逻辑结构;存储结构及相应的算法;并初步掌握算法的时间分析和空间分析技术..不仅要考虑具体实现哪些功能;同时还要考虑如何布局;这次的实验题目是根据我们的课本学习进程出的;说实话;我并没有真正的读懂书本的知识;所以刚开始的时候;感到很棘手;于是又重新细读课本;这一方面又加强了对书本的理解;在这上面花费了一些心血;觉得它并不简单;是需要花大量时间来编写的....在本次实验中;在程序构思及设计方面有了较大的锻炼;能力得到了一定的提高..。
一、实验目的和要求1理解串的一般线性表之间的差异。
2重点掌握在顺序串上和链串上实现串的基本运算算法。
3掌握串的简单匹配算法和KMP算法。
4灵活运用串这种数据结构解决一些综合应用问题。
二、实验环境、内容和方法实验内容：1实现顺序串的各种基本运算。
2实现链串的各种基本运算。
3实现顺序串的各种模式匹配运算。
4求一个串中出现的第一个最长重复串。
实验方法：通过上机操作完成各内容。
实验环境：实验用PC机一台，使用操作系统为Windows XP Professional，安装OFFICE 2003、VC++等软件。
三、实验过程描述实验题4.1实现顺序串各种基本运算的算法编写一个程序algo4-1.cpp，实现顺序串的各种基本运算，并在此基础上设计一个程序exp4-1.cpp 完成如下功能：1建立串谁“abcdefghefghefghijklmn”和串s1=”xyz”;2输出串s;3输出串s的长度；4在串s的第9个字符位置插入串s1而产生串s2;5输出串s2;6删除串s第2个字符开始的5个字符替换成串s1而产生串s2；7输出串s2;8将串s第2个字符开始的5个字符替换成串s1而产生串s2;s2;输出串9．10提取串s的第2个字符开始的10个字符而产生串s3;11输出串s3；12将串s1和串s2连接起来而产生串s4;13输出串s4.解：本工程Proj4_1组成结构如图4.1所示。
algo4-1.cpp文件，其中包含如下函数：StrAssign(SqString &str,char cstr[]):由串常量cstr创建串str. StrCopy(SqString &s,SqString t):将串t复制到串s.StrEqual(SqString s,SqString t):判断两个串s和t是否相同。
StrLength(SqString s):求串s的长度。
Concat(SqString s,SqString t):将串t连接到串s之后产生新串。
数据结构实验报告——实验7一、实验目的掌握二叉链表及二叉树的创建、遍历；二、实验内容1、（必做题）假设二叉树中数据元素类型是字符型，请采用二叉链表实现二叉树的以下基本操作：（1）根据二叉树的先序序列和中序序列构造二叉树；（2）根据先序遍历二叉树；（3）根据中序遍历二叉树；（4）根据后序遍历二叉树。
测试数据包括如下错误数据：先序：1234；中序：12345先序：1234；中序：1245先序：1234；中序：42312、（必做题）对于一棵二叉树，请实现：（1）计算二叉树的叶子数目；（2）计算二叉树的深度。
3、（选做题）给定n个权值，请构造它们的最优二叉树（赫夫曼树）。
三、算法描述（采用自然语言描述）1、分别输入n个先序序列和中序序列，先序序列中第一个字符为根节点，在中序序列中找到根节点所在的位置，在根节点左边的为左子树节点，在根节点右边的为右子树节点，然后采用递归的形式依次对左右子树进行构造；二叉树的遍历也是采用递归的形式，先序遍历二叉树：先序遍历根，先序遍历左子树，先序遍历右子树；中序遍历二叉树：中序遍历左子树，中序遍历根，中序遍历右子树；后序遍历二叉树：后序遍历左子树，后序遍历右子树，后序遍历根。
四、详细设计五、程序代码（给出必要注释）1、#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define N 100typedef char ElementType ;typedef struct node{ElementType data ;struct node * leftChild ;struct node * rightChild ;}BTNode;BTNode *createBT(char *pre , char *in ,int n) {BTNode *b;char *p ;int k ;if(n<=0)return NULL;b=(BTNode *)malloc(sizeof(BTNode));b->data = *pre ;int j=0;for(p=in;p<in+n;p++){if(*p == *pre)break;}k=p-in;b->leftChild = createBT(pre+1,in,k);b->rightChild = createBT(pre+1+k,p+1,n-k-1);return b ;void showBTPreOrder(BTNode *b){if(b != NULL){printf("%c ",b->data);showBTPreOrder(b->leftChild);showBTPreOrder(b->rightChild);}}void showBTInOrder(BTNode *b){if(b!=NULL){showBTInOrder(b->leftChild);printf("%c ",b->data);showBTInOrder(b->rightChild);}}void showBTTailOrder(BTNode *b){if(b==NULL)return;showBTTailOrder(b->leftChild);showBTTailOrder(b->rightChild);printf("%c ",b->data);}int main(){char pre[N];char in[N];int n = 0;char ch;BTNode* b=NULL;printf("请输入先序序列\n");while((ch = getchar())&&ch!='\n')pre[n++] = ch;printf("请输入中序序列\n");n = 0;while((ch = getchar())&&ch!='\n')in[n++] = ch;b=createBT(pre,in,n);printf("先序遍历二叉树:\n");showBTPreOrder(b);printf("\n");printf("中序遍历二叉树:\n");showBTInOrder(b);printf("\n");printf("后序遍历二叉树:\n");showBTTailOrder(b);printf("\n");return 0 ;}2、#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define N 100typedef char ElementType ;typedef struct node{ElementType data ;struct node * leftChild ;struct node * rightChild ;}BTNode;BTNode *createBT(char *pre , char *in ,int n) {BTNode *b;char *p ;int k ;if(n<=0)return NULL;b=(BTNode *)malloc(sizeof(BTNode));b->data = *pre ;int j=0;for(p=in;p<in+n;p++){if(*p == *pre)break;}k=p-in;b->leftChild = createBT(pre+1,in,k);b->rightChild = createBT(pre+1+k,p+1,n-k-1);return b ;}int Count(BTNode * top){if(top == NULL){return 0;}else if ((top->leftChild==NULL) && (top->rightChild==NULL)){ return 1;}else{return Count(top->leftChild)+Count(top->rightChild);}}int TreeDepth(BTNode * top){int rightdep=0;int leftdep=0;if(top==NULL)return -1;if(top->leftChild!=NULL)leftdep=TreeDepth(top->leftChild);elseleftdep=-1;if(top->rightChild!=NULL)rightdep=TreeDepth(top->rightChild);elserightdep=-1;return (rightdep>leftdep) ? rightdep+1 : leftdep+1;}int main(){char pre[N];char in[N];int n = 0;char ch;BTNode* b=NULL;printf("请输入先序序列\n");while((ch = getchar())&&ch!='\n')pre[n++] = ch;printf("请输入中序序列\n");n = 0;while((ch = getchar())&&ch!='\n')in[n++] = ch;b=createBT(pre,in,n);printf("二叉树的叶子数目为：%d\n",Count(b));printf("二叉树的深度为：%d\n",TreeDepth(b));return 0 ;}六、测试和结果（给出测试用例，并给出测试结果）1、2、七、用户手册（告诉用户如何使用程序，使用注意事项等）两个程序只能输入字符，并且两次输入的字符个数要一样，字符个数上限为100。
实验报告格式1、题目:线性表长整数的加减乘除实现2、完成时间起止2010-12-3-----------2010-12-43、实验要求实现线性表长整数的加减乘除（要求最少一千位以上）4、实验目的通过对长整数加减乘除的实现，深入了解线性表的优势与劣势，同时增强对数据结构实践能力的培养，加强计算机动手能力。
5、实验过程5.1 系统的主控模块流程图#include"File1.cpp"int main(){list a,b,c;init(c);init(a);cout<<"两个数a，b:";create(a);init(b);create(b);cout<<a.a<<"+"<<b.a<<"="; add(a,b,c);display(c);cout<<a.a<<"-"<<b.a<<"="; init(c);thus(a,b,c);display(c);cout<<a.a<<"*"<<b.a<<"="; init(c);multipy(a,b,c);display(c);init(c);cout<<a.a<<"/"<<b.a<<"="; division(a,b,c);display(c);system("pause");}5.2 主要模块流程图首先线性表基本函数#include<iostream>using namespace std;const int maxsize=1000; typedef char elemtype; struct list{elemtype* a;int size;};void init(list& m){m.a=new elemtype[maxsize]; m.size=0;}void create(list& m){cout<<"请输入一个长整数:"; cin>>m.a;m.size=strlen(m.a);}int getsize(list m){return m.size;}bool empty(list m){return m.size==0;}void display(list m){for(int i=0;i<m.size;i++)cout<<m.a[i];cout<<endl;}用于下面计算的基础函数void reverse(list& m){for(int i=0;i<m.size/2;i++) {elemtype t=m.a[i];m.a[i]=m.a[m.size-i-1];m.a[m.size-i-1]=t;}bool compare(list a,list b){if(a.size>=b.size)return true;return false;}void copy(list& a,list b){a.size=b.size;for(int i=0;i<b.size;i++)a.a[i]=b.a[i];a.a[a.size]='\0';}void clearfirst(list& a){ //用来清除数组前面的0 int i=0,k=0;bool t=false;if(a.a[0]!='-'&&a.a[0]!='0')return;else if(a.a[0]=='-') {i=1;t=true;}for(;i<a.size;i++)if(a.a[i]=='0')k++;else break;list b;init(b);copy(b,a);init(a);b.a[b.size]='\0';a.size=b.size-k;if(t==false){ //t为false时，说明a为正for(int tz=0;tz<b.size;tz++)a.a[tz]=b.a[tz+k];}else{a.a[0]='-';for(int tz=0;tz<a.size;tz++)a.a[tz+1]=b.a[k+tz+1];}a.a[a.size]=='\0';}void ch(list& a,int x){ //乘以10 相当于移位for(int i=0;i<x;i++)a.a[a.size+i]='0';a.size=a.size+x;a.a[a.size]=0;}void reverse(list& m){//倒置for(int i=0;i<m.size/2;i++){elemtype t=m.a[i];m.a[i]=m.a[m.size-i-1];m.a[m.size-i-1]=t;}}1大整数加法void add(list a,list b,list& c){ //加法//if(!empty(c)){reverse(c);}reverse(a);reverse(b);int i,k,flag=0,sun;if(compare(a,b)){c.size=a.size;for(i=0;i<b.size;i++){sun=a.a[i]-'0'+b.a[i]-'0'+flag;if(sun>=10){flag=sun/10;sun%=10;}else flag=0;c.a[i]=sun+'0'; }for(i=b.size;i<a.size;i++) {sun=b.a[i]-'0'+flag;if(sun>=10){flag=sun/10;sun%=10;}else flag=0;c.a[i]=sun+'0';}if(flag!=0){c.a[c.size++]='0'+flag;flag=0;}}else{c.size=b.size;for(i=0;i<a.size;i++) {sun=a.a[i]-'0'+b.a[i]-'0'+flag;if(sun>=10){flag=sun/10;sun%=10;} else flag=0;c.a[i]=sun+'0'; }for(i=a.size;i<b.size;i++) {sun=a.a[i]-'0'+flag;if(sun>=10){flag=sun/10;sun%=10;} else flag=0;c.a[i]=sun+'0';}if(flag!=0){c.a[c.size++]='0'+flag;flag=0;} }c.a[c.size]='\0';reverse(a);reverse(b);reverse(c);}减法void thus(list wg,list tg,list& c){ //减法bool zf=true;list a,b; //创建临时a，b 用于操作init(a);init(b);copy(a,wg);copy(b,tg);int i,k,flag=0,sun;if(strlen(a.a)>strlen(b.a)) //大数减小数{reverse(a);reverse(b);for(i=0;i<strlen(b.a);i++){ a.a[i]-=flag/10;if(a.a[i]<b.a[i])flag=10;else flag=0;sun=a.a[i]-b.a[i]+flag+'0';c.a[i]=sun; }for(i=strlen(b.a);i<strlen(a.a);i++){ a.a[i]-=flag/10; flag=0;c.a[i]=a.a[i];}c.size=i;c.a[i]='\0';}else if(strlen(a.a)==strlen(b.a)) //位数相等{int w; bool tf=false;for(w=0;w<a.size;w++)if(a.a[w]<b.a[w]){tf=false; break;}else if(a.a[w]==b.a[w])continue;else {tf=true;break; }reverse(a);reverse(b);if(tf==true&& w<a.size)//if(w>=a.size&&d!=a.size) //位数相等，大数减小数{for(i=0;i<strlen(b.a);i++){ a.a[i]-=flag/10;if(a.a[i]<b.a[i])flag=10;else flag=0;sun=a.a[i]-b.a[i]+flag+'0';c.a[i]=sun; }for(i=strlen(b.a);i<strlen(a.a);i++){ a.a[i]-=flag/10; flag=0;c.a[i]=a.a[i]; }c.size=i;c.a[i]='\0';}else if(w>=a.size){init(c);c.size=1;c.a[0]='0';c.a[c.size]='\0';return;}else //位数相等，小数减大数{for(i=0;i<strlen(a.a);i++){ b.a[i]-=flag/10;if(a.a[i]>b.a[i])flag=10;else flag=0;sun=b.a[i]-a.a[i]+flag+'0';c.a[i]=sun; }for(i=strlen(a.a);i<strlen(b.a);i++){ b.a[i]-=flag/10; flag=0;c.a[i]=b.a[i]; }zf=false;c.size=i;c.a[i]='\0';}}else if(strlen(a.a)<strlen(b.a)) {reverse(a);reverse(b);for(i=0;i<strlen(a.a);i++){ b.a[i]-=flag/10;if(a.a[i]>b.a[i])flag=10;else flag=0;sun=b.a[i]-a.a[i]+flag+'0';c.a[i]=sun; }for(i=strlen(a.a);i<strlen(b.a);i++){ b.a[i]-=flag/10;c.a[i]=b.a[i]; }zf=false;c.size=i;c.a[i]='\0';}reverse(c);if(zf==false){ //符号判断list m;init(m);copy(m,c);init(c); c.size=m.size+1;c.a[0]='-';for(i=0;i<m.size;i++)c.a[i+1]=m.a[i];}c.a[i+1]='\0';clearfirst(c);}void multipy(list wg,list tg,list& c ){ //乘法list a,b; //创建临时a，b 用于操作init(a);init(b);copy(a,wg);copy(b,tg);reverse(a);reverse(b);for(int m=0;m<strlen(a.a)+strlen(b.a);m++)c.a[m]='0';c.size=strlen(a.a)+strlen(b.a);int i,k,sum,flag=0;for(i=0;i<strlen(b.a);++i){if(b.a[i]=='0')continue;sum=0;for(k=0;k<strlen(a.a);++k){sum+=(a.a[k]-'0')*(b.a[i]-'0')+(c.a[k+i]-'0');c.a[k+i]=sum%10+'0'; //进位计算sum/=10;flag=sum;}c.a[strlen(a.a)+i]+=sum;}c.a[c.size]='\0';reverse(a);reverse(b);reverse(c);clearfirst(c);}除法void division(list wg,list tg,list& c){ //除法list a,b; //创建临时a，b 用于操作init(a);init(b);copy(a,wg);copy(b,tg);int i,j; list t,v,k,m;if(empty(b)||empty(a))return;if(strlen(a.a)==strlen(b.a)){ //如果a和b长度相等for(i=0;i<9;i++){ init(k); //thus(a,b,k);if(k.a[0]!='-'){init(a);copy(a,k);continue;}else break;}init(c);c.size=1;c.a[0]=i+'0';c.a[c.size]='\0';}else if(strlen(a.a)<strlen(b.a)){ //如果a比b小init(c);c.size=1;c.a[0]='0';c.a[c.size]='\0';return ;}else if(strlen(a.a)>strlen(b.a)){ //如果a比b大int qwt=strlen(a.a)-strlen(b.a);for(j=0;j<=qwt;j++){init(m);int grf=0;thus(a,b,m);if(m.a[0]=='-')grf++;init(v);copy(v,b);ch(v,qwt-j-grf);for(i=0;i<9;i++){ init(k); //thus(a,v,k);if(k.a[0]!='-'){init(a);copy(a,k);continue;}else break;}c.a[j]=i+'0';c.size++;}if(strlen(a.a)==strlen(b.a)){ for(i=0;i<9;i++){ init(k); //thus(a,b,k);if(k.a[0]!='-'){init(a);copy(a,k);continue;}else break;}if(j<qwt){c.a[c.size]=i+'0';c.size++; }}c.a[c.size]='\0'; }clearfirst(c); }5.3 测试例子测试实例普通加法加法进位等位加法等位减法大数减小数小数减大数小数乘大数大数乘小数大数除小数等位数相同除法高位计算千位级别计算（时间大约1s不到）算法性能优良接上面5.4 设计中碰到的问题，如何解决实验过程中多次碰到数组空间内存溢出的问题，除法运算效率问题，还有计算过程中算法重利用不高的问题，我多次实验，并通过完善，通过分模块执行代码进行整合，最终解决了一些已知的问题。
