算 法 与 数 据 结 构 实 验
班级:学号:姓名:
实验一 单链表建立及相关操作 实验思路
线性链表的存储信息包含两个域,一个是数据域,另一个是指针域,单链表的插入先创立一个新结点再让该结点指向第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]。希尔排序现将整个待排记录序
…… …… 余下全文