中北大学数据实验报告.doc

算 法 与 数 据 结 构 实 验 班级： 学号： 姓名： 实验一 单链表建立及相关操作 实验思路 线性链表的存储信息包含两个域，一个是数据域，另一个是指针域，单链表的插入先创立一个新结点再让该结点指向第i+1个元素再让第i-1个元素指向该结点;删除第i个结为找到线性表中第i-1个节点修改其指向后继的结点。 运行结果 实验二 二叉树的建立及遍历 实验思路 二叉树的链式存储由一个数据域与分别指向其左右子树的两个分支构成，则表示二叉树的链表中的结点至少包含三个域，数据域左右指针域。先序遍历为先访问根节点再先序遍历左子树后先序遍历右子树；中序遍历为先中序遍历左字数再访问根节点后中序遍历右子树；后序遍历先后序遍历左子树再后序遍历右子树后访问根结点。 运行结果 实验三 图的存储结构及遍历 实验思路 图的深度优先遍历为从图中某个顶点v出发，访问其顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到，若此时尚有顶点未被访问，则另选图中一个未曾被访问的顶点做起始点，重复上诉过程直至图中所有顶点都被访问。广度优先遍历从图中某顶点v出发，在访问v之后依次访问v的各个未被访问的邻接点，然后分别从这些邻接点出发依次访问它的邻接点，直至图中所有的顶点都被访问。 、运行结果 实验四 数据记录的内部排序 实验思路 直接插入排序的基本操作是将一个记录插入到已排好序的序列表中，从而得到一个新的，记录数增一的有序表；折半插入排序在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设low，末元素设high，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素大，则选择low到m-1为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low=high不成立，即将此位置之后所有元素后移一位，并将新元素插入入a[high+1]。希尔排序现将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序；起泡排序首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之然后比较第二和第三个记录的关键字依次类推，其结果使得关键字最大的记录被安置到最后一个记录的位置上，然后进行第二趟，第三趟……起泡排序；快速排序通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 运行结果 总结 通过本次试验我加深了对单链表，二叉树及图的存储结构的理解，也学会了对单链表的插入删除操作，对二叉树和图的遍历操作，及对数组的排序。通过实验，我发现了自己以前的学习误区，通过比较我也能较清楚地知道个排序法的优劣，为以后的进一步学习奠定了基础。