数据结构(c语言版本)

苏州科技学院数据结构（C语言版）实验报告专业班级测绘1012学号1020115223姓名周兵兵实习地点系机房指导教师史守正实验一线性表一、程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明等）1.定义数据结构，Sqlist顺序结构，并定义该类型的指针变量*L。2.初始化顺序表，长度为0。并输入10个整数，通过选择菜单来打印输出3.通过函数的调用分别进行插入、删除、修改操作二、源程序及注释（打包上传）：三、运行输出结果：四、调试和运行程序过程中产生的问题及采取的措施：查找元素是函数不会调用，后详细了解了变量的意思和用途之后问题得以解决。删除功能不能实现，自习检查程序才发现程序代码写错。还有函数的调用也会出现问题。五、对算法的程序的讨论、分析，改进设想，其它经验教训：这道实验题是最基本的实验，所用算法也是书上给出的，编程过程中没遇到太大的问题，只是C的小细节没有把握，所以经常报错。今后一定要加强巩固以前的知识点。实验二栈和队列一、程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明等）该程序主要有输入输出、查找、插入、删除等功能。这些功能是通过建立线性链表来实现。线性链表就是以结点的形式将数据连接起来，每个结点包括数据域和指针域，通过指针的后继指向将数据组织起来。首先开辟一个内存空间，然后初始化数据，并且根据要求将这些数据逆向存储在指针所指向的地址里，之后进行查找、插入、删除、转换单链表为循环链表、合并单链表的操作即可。二、源程序及注释（打包上传）：三、运行输出结果：四、调试和运行程序过程中产生的问题及采取的措施：值传递和址传递易出错，复习C之后重新编写，问题得以解决五、对算法的程序的讨论、分析，改进设想，其它经验教训：在栈和队列在实际问题的运用方面还比较模糊。还有针对不同版本的C编写程序时应当注意其中一些符号的表示方法。实验三数和二叉树一、程序设计的基本思想，原理和算法描述：二叉树是由3个基本单元组成：根结点、左子树和右子树。本例采用二叉链表作为存储结构，但是在输入时用的是先序序列的方式。程序包含了二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。二、源程序及注释（打包上传）：三、运行输出结果：四、调试和运行程序过程中产生的问题及采取的措施：调试的时候在参数之间的传递时出现的错误，由于对于二叉树的结构还没有彻底的了解在传值传址时很模糊，通过多次的尝试来完成程序。五、对算法的程序的讨论、分析，改进设想，其它经验教训：三种二叉树链表的遍历是递归的实现方式，对于在理解方面比较困难，但是可以以正常的思维去理解，不必拘泥过深的探讨。另外，第五项功能节点赋值有点问题，目前还未解决。总的来说这次试验有难度。实验四图一、程序设计的基本思想，原理和算法描述：1)有向图从某个定点出发沿以该顶点为尾的弧进行深度优先搜索遍历，并按其所有邻接点的搜索都完成的顺序将顶点排列起来。从最后完成搜索的顶点出发，沿着以该顶点为头的弧作为逆向的深度优先搜索遍历，若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成搜索的那个顶点出发，继续作逆向的深度优先搜索遍历，以此类推，直至有向图中所有顶点都被访问到为止。2)无向图对无向图进行遍历时，至于连通图，仅需从图中任一顶点出发，进行深度优先搜索或者广度优先搜索，便可访问到图中的所有顶点。对非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。二、源程序及注释（打包上传）：三、运行输出结果：四、调试和运行程序过程中产生的问题及采取的措施：对顶点进行深度和广度遍历时，需要分析清楚各个顶点的搜索顺序，通过对指针的正确分析可以解决这一问题。五、对算法的程序的讨论、分析，改进设想，其它经验教训：本程序第二个功能尚未实现，关于有向网的程序没运行起来，如果能将其完善会更好，另外，本程序在实现一种功能时需退出，不然不能进行其他功能的操作。实验五查找一、程序设计的基本思想，原理和算法描述：中序遍历二叉树的方法是：中序遍历左子树；访问跟结点；中序遍历右子树。第一个问题在实验三中已提及；中序遍历二叉排序树时，其算法思想是：p指向二叉树的根结点；while（p不为NULL或栈不为空），当前结点指针p不断进栈，左移直至最左下结点为止。若栈不为空，则退栈，访问跟结点，使p=p-rchild，遍历右子树。在二叉排序树上查找其关键字等于给定值的结点过程，恰是走过了一条根结点到该结点的路径的过程，和给定值比较的关键字个数等于路径长度加1，因此，与折半查找类似，与给定值比较的关键字个数不超过树的深度。然而，折半查找长度为n的表的判定树是唯一的，而含有n个结点的二叉排序树却不唯一二、源程序及注释（打包上传）：三、运行输出结果：四、调试和运行程序过程中产生的问题及采取的措施：中序遍历非递归算法时，循环条件top=0不可能满足，因为是在top1时执行top；二叉树中各结点在栈中所处层次的规律是，每个结点的深度与其右孩子的深度相等，每个结点的深度比其左孩子的深度少1。五、对算法的程序的讨论、分析，改进设想，其它经验教训：栈顶记录中的指针其实就是指栈顶，每次push()进去或者pop()出来的那个p。他代表的是正在访问的节点得下一个节点。比如，访问一个树t的左子树t-lchild时，栈顶就是t；访问t-lchild-lchild时，栈顶就是t-lchild。访问t-rchild时，栈顶为NULL；访问t-lchild-rchild时，栈顶为t；访问t-rchild-lchild时，栈顶也是t；访问t-rchild-rcchild时，栈顶仍为NULL。他的意义就是，在访问完了当前的子树之后，就会去访问栈顶记录的指针对应的节点的数据。实验六排序一、程序设计的基本思想，原理和算法描述：直接插入的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排序好的子表中的适当位置，直到全部记录插入完成为止。直接插入排序：假设待排序的记录存放在数组R[0…n-1]中，排序过程的某一中间时刻，R被划分成两个子区间R[i…n-1],其中：前一个子区间是已排好序的有序区；后一个子区间则是当前未排序的部分。直接插入排序的基本操作是将当前无序区的第一个记录R[i]插入到有序区R[0…i-1]中的适当位置上，使R[1…i]变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加一个记录。其时间复杂度为o（n2）。（2）交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行排序，直到没有反序的记录为止。①冒泡排序：通过无序区中相邻记录关键字间的比较和位置的交换，使关键字最小的记录如气泡一般逐渐往上漂移直至水面。整个算法是从最下面的记录开始，对每两个相邻的关键字进行比较，且使关键字较小的记录换至关键字较大的记录之上，使得经过一趟冒泡排序后，关键字最小的记录到达最上端，接着，再在剩下的记录中找关键字次小的记录，并把它换在第二个位置上。依次类推，一直到所有记录都有序为止。②快速排序：在待排序的n个记录中任取一个记录（通常取第一个记录），把该记录放入最终位置后，数据序列被此记录分割成两部分。所有关键字比该记录关键字小的记录放置在前一部分，所有比它大的记录放置在后一部分，并把该记录排在这两部分的中间。之后对所有的两部分分别重复上述过程，直至每部分内只有一个记录为止。简而言之，每趟使表的第一个元素入终位，将表一分为二，对子表按递归方式继续这种划分，直至划分的子表长为1。（3）选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子表的最后，直到全部记录排序完毕。直接选择排序：第i趟排序开始时，当前有序区和无序区分别为R[0…i-1]和R[i...n-1](0=in-1),该趟排序则是从当前无序区中选出关键字最小的记录R[k],将它与无序区的第一个记录R[i]交换，使R[0…i-1]和R[i+1…n-1]分别变为新的有序区和新的无序区。因为每趟排序均使有序区中增加了一个记录，且有序区中的记录关键字均不大于无序区中记录的关键字，即第i趟排序之后R[0…n-2]的所有关键字小于等于R[i+1…n-1]中的所有关键字，所以进行n-1趟排序之后有R[0…i]的所有关键字小于等于R[n-1].key，也就是说，经过n-1趟排序之后，整个表R[0…n-1]递增有序。二、源程序及注释（打包上传）：三、运行输出结果：四、调试和运行程序过程中产生的问题及采取的措施：不同的排序方法原理上的差异体现在程序上只是核心代码的一点差异，因此，注意几种排序原理的本质差异在编写代码的时候引起足够的重视就可以避免一些错误的发生，保证程序的顺利运行。五、对算法的程序的讨论、分析，改进设想，其它经验教训：当实现插入排序过程中，可以用二分查找来确定第i个元素在前i-1个元素中的可能插入位置，但这样做并不能改善插入排序的时间复杂度。因为在这里，二分查找只减少了关键字间的比较次数，而记录的移动次数不变，时间复杂度仍为O（n2）。