北邮数据结构实验报告.doc

精品学习资料范文北邮数据结构实验报告 篇一：北邮数据结构第三次实验-实验报告 数据结构实验报告 实验名称： 实验三栈和队列 学生姓名： 班 级： 班内序号： 学 号： 日 期： 1. 实验要求 1.1 实验目的 通过选择下面两个题目之一进行实现，掌握如下内容： ? ? ? 1.2 实验内容 根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。 二叉树的基本功能： 1、二叉树的建立 2、前序遍历二叉树 3、中序遍历二叉树 4、后序遍历二叉树 5、按层序遍历二叉树 6、求二叉树的深度 7、求指定结点到根的路径 8、二叉树的销毁 9、其他：自定义操作 编写测试main()函数测试线性表的正确性 掌握二叉树基本操作的实现方法 了解赫夫曼树的思想和相关概念 学习使用二叉树解决实际问题的能力 2. 程序分析 2.1 二叉链表 2.2 二叉树的二叉链表存储示意图 2.3 关键算法分析 2.3.1算法1：void create(Binode T * R, T data, int i); 1 算法功能：创建一个二叉树 2 算法基本思想：通过构造函数创建一个二叉树，构造函数通过调用函数 create()创建二叉树，关于函数create()的伪代码： 1.定义根指针，输入节点储存的data，若输入“#”，则该节点为空； 2.申请一个新节点，判断它的父结点是否不为空，如果不为空在判断其为左 或者右孩子，并把地址付给父结点，把data写入。 3 算法空间、时间复杂度：O（n） 4 代码逻辑（可用伪代码描述）：if(datai-1!=0)R = new Binode T R- data = datai-1;R- lch = R- rch = NULL;create(R- lch, data, 2*i);create(R- rch, data, 2*i+1); 2.3.2算法2：void Destroy(Binode T *R); 1 算法功能：二叉树的销毁 2 算法基本思想：采用后序遍历的方法，释放节点。 3 算法空间、时间复杂度： O(n) 4 代码逻辑（可用伪代码描述）： if(R!=NULL)Destroy(R- lch);Destroy(R- rch); delete R; 2.3.3算法3：void preorder(Binode T *R); 1 算法功能：前序遍历二叉树 2 算法基本思想：设置递归边界条件：if root=null则停止递归；2打印起始 节点的值，并先后在左子数右子数上递归调用打印函数 3 算法空间、时间复杂度：O（n) 4 代码逻辑（可用伪代码描述）： if(R!=NULL)cout R- data;preorder(R- lch);preorder(R- rch); 2.3.4算法4：void Inorder(Binode T *R); 1 算法功能：中序遍历二叉树 2 算法基本思想： 1.设置递归边界条件：if root=null则停止递归，2.递归 遍历左子树3.打印根节点数据域内容4.递归遍历右子树 3 算法空间、时间复杂度：O（n) 4 代码逻辑（可用伪代码描述）： if(R!=NULL)Inorder(R- lch);cout R- data; Inorder(R- rch); 2.3.5算法5：void Postorder(Binode T *R); 1 算法功能：后序遍历二叉树 2 算法基本思想：1.设置递归边界条件：if root=null则停止递归2.递归遍历 左子树3.递归遍历右子树4.访问根结点数据域 3 算法空间、时间复杂度：O（n) 4 代码逻辑（可用伪代码描述）： if(R!=NULL)Postorder(R- lch);Postorder(R- rch); cout R- data; 2.3.6算法6：void Levelorder(Binode T *R); 1 算法功能：层序遍历二叉树 2 算法基本思想：1.队列Q及所需指针的定义和初始化2.如果二叉树非空，将 根指针入队3.循环直到队列Q为空3.1 q=队列Q的队头元素出队3.2 访问 节点q的数据域cout q- data 3.3 若节点q存在左孩子，则将左孩 子指针入队 if (q- lchild != NULL) Qrear+ = q- lchild; 3.4若 节点q存在右孩子，则将右孩子指针入队if (q- rchild != NULL) 3 算法空间、时间复杂度：O（n) 4 代码逻辑（可用伪代码描述）：Binode T *queue10000;int f = 0, r = 0;if(R!=NULL) queue+r = R;while(f!=r)Binode T *queue+f;cout p- data;if(p- lch!=NULL) queue+r = p- if(p- rch!=NULL)queue+r = p- 2.3.7算法7：int Depth(Binode T *R, int d); 1 算法功能：计算二叉树深度 2 算法基本思想：1. 定义和初始化计数深度的参数2如果根节点为空，return0 3如果根节点为非空，递归调用自身的到叶子节点到根的路径长度，输出其中 较大的作为树的深度 3 算法空间、时间复杂度：O（n) 4 代码逻辑（可用伪代码描述）：if(R=NULL) return d; if(R- lch=NULL) (R- rch=NULL)return d+1;elseint m = Depth(R- lch, d+1);int n = Depth(R- rch, d+1);return n m?n:m; 2.3.8算法8：void path(Binode T *root, char m); 1 算法功能：输出指定结点到根结点的路径 2 算法基本思想：代码：1.建立一个存储路径结点结构，定义和初始化结构体的数 组2.当root不为空或top为0时，进入循环3.当此时root所指的节点的数据 不为指定数据时，将root指向它的左孩子4.当此时root所指的节点的数据为 指定数据时，访问其数据域并输出 3 算法空间、时间复杂度：O(n) 4 代码逻辑（可用伪代码描述）：Binode T *stack10000;Binode T int tag10000; int top = 0;s = root;dowhile(s!=NULL)top+;stacktop=s;tagtop=0;s=s- if(top 0)if(tagtop = 1)if(stacktop- data = m)cout 路径： t for(int i=1;i =top;i+)cout stacki- data;break;top-;elses=stacktop ;if(top 0)s=s- tagtop=1;while(s!=NULL | top!=0); 3. 程序运行结果 篇二：北京邮电大学 计算机学院数据结构第一次实验报告 实验报告（1） 姓 名：学 号： 实验目的、实验原理和内容： 一、实验目的：熟悉实验环境，掌握线性表动态存储结构的基本特点。 二、实验原理：链表运算，完成有关单链表有关运算的程序。 三、实验内容及要求： 1、 有一个带头结点的单链表，写出在其值为x的结点之后插入m个结点的算法程序。 2、已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写个删除表中所有值大于min且小于max的元素(若表中存在这样的元素)的算法程序。 要求：请同学把步骤、调试好的程序及存在的问题写在下面。 第一题实验程序代码： #include stdio.h #include stdlib.h typedef struct Lnode int data; struct Lnode *next; Lnode,*Linklist;/非头结点结构定义 typedef struct int len; Linklist head; HeadNode;/头结点结构定义 Linklist creatlist(HeadNode *L);/创造含头结点的链表函数 Linklist get(Linklist R,int key);/在链表中寻找值为key的结点，并返回该结点 Linklist invert(HeadNode *L,Linklist S,int num); /在链表中的某个结点之后插入num个结点 void printlist(HeadNode *L,Linklist S);/打印链表中数据域的值 void deletelist(Linklist R);/释放链表 int main() HeadNode *L; Linklist S; int key,num; L=(HeadNode*)malloc(sizeof(HeadNode); if(L=NULL) return 0; L- head=creatlist(L);/含头结点的链表的创建 printlist(L,L- head); if(L- head=NULL)/判断链表中是否只有头结点 printf( The list has no data, can t be inverted!n return 0; printf( Please input the data you want to research:n scanf( %d , key);/提示用户输入需要查找的数值 fflush(stdin);/清空缓冲区，防止读入用户多输入的数据 S=get(L- head,key); if(!S) return 0; printf( Please input the number of the Lnode you want to invert:n /提示用户输入需要插入的结点值 scanf( %d , num); S=invert(L,S,num); printlist(L,L- head); deletelist(L- head); free(L);/释放头结点 system( pause return 0; Linklist creatlist(HeadNode *L)/创造含头结点的链表函数 Linklist S=NULL,R=NULL,H=NULL; int i; printf( Please input the length of the list:n scanf( %d , L- len); fflush(stdin); if(L- len =0) return 0; printf( Please input the data:n for(i=0;i =L- len-1;i+) S=(Linklist)malloc(sizeof(Lnode); if(S!=NULL) if(R=NULL) R=S; H=S; scanf( %d , S- data); R- next=S; R=S; fflush(stdin); R- next=NULL; L- head=H; return L- head; Linklist get(Linklist R,int key)/在链表中寻找值为key的结点，并返回该结点 Linklist S; S=R; while(S S- data!=key) S=S- next; if(!S) printf( Can t find the data %d, the list can t be inverted!n ,key); return NULL; else printf( Find the data successful!n return S; Linklist invert(HeadNode *L,Linklist S,int num)/在链表中的某个结点之后插入num个结点 Linklist R,K,H; int i; R=S; H=S- next; if(num 0) printf( Please input the data of %d inverted Lnode:n ,num); L- len+=num; else printf( Invert failed!n for(i=0;i =num-1;i+) K=(Linklist)malloc(sizeof(Lnode); scanf( %d , K- data); R- next=K; R=K; R- next=H; return S; void printlist(HeadNode *L,Linklist S)/打印链表中数据域的值 if (S=NULL) printf( The list is empty.n else printf( The list has %d Lnodes.n ,L- len); printf( The list is:n while(S!=NULL) printf( %d- ,S- data); S=S- next; printf( NULLn void deletelist(Linklist R)/释放链表 Linklist temp; while(R!=NULL) temp=R; R=R- next; free(temp); 第一题存在的问题: 1.注意头结点与非头结点结构定义的差别，链表的长度由用户输入，需要排除用户错误输入即L- len小于0时的情况，并注意判断链表 中是否只含有头结点； 2. 在进行链表的创建与结点的查找操作时，需要读入每个结点的数据值及num的值，这时候需要清空缓存区，防止读入用户输入的多余的数据。 第二题实验程序代码： #include stdio.h #include stdlib.h typedef struct Lnode int data; struct Lnode *next; Lnode,*Linklist;/非头结点结构定义 typedef struct int len; Linklist head; HeadNode;/头结点结构定义 Linklist creatlist(HeadNode *L);/创造含头结点的链表函数 Linklist get(HeadNode *L,Linklist H,int num,int judge);/在链表中寻找数值小于num的结点并返回 Linklist delete(HeadNode *L,Linklist S,Linklist R,int min);/释放链表中两个节点之间的所有节点空间 int judgelist(Linklist S);/判断链表是否按升序排列 void printlist(HeadNode *L,Linklist S);/打印链表中数据域的值 void deletelist(Linklist S);/释放链表 int main() HeadNode *L=NULL; Linklist S,R; int min,max; L=(HeadNode*)malloc(sizeof(HeadNode); if(L=NULL) return 0; L- head=creatlist(L); printlist(L,L- head); while(judgelist(L- head)=0)/判断链表是否按升序排列，若不是，则提示用户重新输入，直至符合要求 篇三：北邮数据结构实验报告排序 数据结构实验报告 实验名称： 实验四排序 学生姓名： 班 级： 班内序号： 学 号： 日 期： 2014年12月19日 1实验要求 实验目的 通过实现下述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 实验内容 使用简单数组实现下面各种排序算法，并进行比较。 排序算法：1、插入排序2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性。 2. 程序分析 首先，题目要求测试不同的数据，所以可以手动输入待排序元素。其次，由于对一组数据要求用不同的排序算法来处理，所以需要一个复制函数把排序前的无序数组寄存出去，为下一次排序做准备。再次，由于每次排序后都需要把排序后的结果打印出来，代 码是一样的，根据相同的代码可以封装成一个函数的思想，所以还需增加一个打印函数。 2.1 存储结构 本程序采用简单数组来储存输入的待排序数组 2.2 关键算法分析 核心算法思想： 1. 利用教材讲述的基本算法思想，实现七种排序算法，统计其运行相关数据。 2. 将七种排序函数入口地址作为函数指针数组，实现快速调用和统计。使得程序代码可读 性增、结构更加优化。 关键算法思想描述和实现： 关键算法1： 实现七种算法的基本排序功能。 1、 插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。插入排序的思想是：每次从无序区取一元素将其添加到有序区中。 2、 希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序， 待整个序列基本有序时，再对全体记录进行一次直接插入排序。 3、 冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。 4、 快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则 大于基准，然后对两部分重复上述过程，直至整个序列排序完成。 5、 选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中 的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。 2.3 其他 时间复杂度与空间复杂度 理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示： 3. 程序运行结果 程序运行框图： 实际测试和分析： 实际运行结果如下： 1 正序排序 2 倒序排序 3 乱序排序 4. 总结 1、在初期构思代码的时候，首先构造了各种算法的基本实现代码，封装成类，已经能够实现七种排序的基本功能，并且测试无误。后来考虑能否优化本程序，首先考虑到测试算法的需求，需要大量随机数，因为增添了随机函数发生器，满足各种测试条件的需求。之后考虑如何能简化代码以实现多达七种排序算法的简单调用、乱序和顺序以及逆序数据的分别排序和性能指标统计、算法移动次数和比较次数的精确统计。如果设计不合理，将使得主调函数的调用代码冗长，可读性变差。因而采用了函数指针数组和统一的接口函数，采用二维数组存储移动次数和比较次数，调用精确的系统函数实现时间的统计。此外还添加了一些列优化，特别是函数封装的方法，使得程序的结构变得更加合理，版面风格也变得好看，可读性增强。 2、程序的优化是一个艰辛的过程，如果只是实现一般的功能，将变得容易很多，当加上优化，不论是效率还是结构优化，都需要精心设计。这次做优化的过程中，遇到不少阻力。由于优化中用到很多类的封装和访问控制方面的知识，而这部分知识恰好是大一一年学习的薄弱点。因而以后要多花力气学习C+编程语言，必须要加强这方面的训练，这样才能在将编程思想和数据结构转换为代码的时候能得心应手。 3、改进：本程序代码设计时运用了递归的调用方式，效率还可以通过将其转换为栈模拟的方式得以提高。在实现类的封装的时候为了共享数据采用了友元函数的方式，考虑能否使用其他方式使得类的封装更加完善。