数据结构-实验指导书

.数据结构实验指南编辑计算机专业实验中心2020年6月8日列表数据结构机械实验内容和要求3实验I，顺序表的实现和应用5实验2，链表实现和应用8实验三、堆栈实现和应用13实验四、队列实现和应用14实验5，二叉树的操作和应用15实验VI、图表遍历任务和应用20实验7，实现搜索算法27实验8，排序算法29数据结构机械实验内容和要求通过机械实验加深对课程内容的理解，提高感性认识，提高编程、开发和调试能力。序号实证名称内容要冲每个组人数实验时间实验要求实验类别分数(共100分)1顺序表的实现及其应用确定顺序表结构，并实现插入、删除和其他算法。使用顺序表格将两个排序的线性表格合并为一个顺序表格。12一定会做到的设计10分2链表的实现与应用确定单个链接列表结构，并实现插入、删除和查找等算法。使用单个链接列表将两个已排序链接的列表合并为一个已排序链接的列表。12一定会做到的设计10分3堆栈实现和应用了解堆栈的结构，并将堆栈应用于表达式计算问题12一定会做到的设计15分4实施和应用队列了解队列的结构，并将其应用于模拟服务台前面的队列现象问题12一定会做到的设计15分5二叉树操作和应用二叉树存储、三种遍历迭代算法、预序或非递归遍历算法的实现12一定会做到的设计15分6图的遍历任务和应用图存储、深度遍历和宽度遍历算法的实现12一定会做到的设计10分7查找算法的实现实现序列表的二进制搜索算法12一定会做到的设计10分8排序算法的实现直接插入排序、快速排序和其他算法实现12一定会做到的设计15分本实验指南为16小时数据结构实验课，实验项目如下。实验报告要求按照实验教师的要求，及时提交实验报告电子版文件。实验报告格式可以个性化，包括但不限于：1、标题、名字、学号、课程(主页)2，需求分析：指定强调程序将做什么的程序设计的任务：(1)输入表单和输出值的范围；(2)输出的形式；(3)方案能够实现的功能；(4)测试数据：包括正确的输入输出结果和错误的输入输出结果。3，摘要设计：描述使用的数据结构定义、主程序的进程以及每个程序模块之间的调用关系。4，详细设计：提交带有注释的源程序，或以伪代码编写与每个操作相关的算法。5、调试分析：(1)调试过程中出现的问题和解决方法；(2)算法的时空分析；(3)经验和经验。6，用户使用说明：说明如何使用自己设计的程序，详细列出每个步骤的程序。(如果程序工作很简单，则可以省略)7，测试结果：列出为给定输入生成的结果。(如果可能，测试随着输入大小的增加算法的实际运行时间变化)8、摘要实验一、顺序表的实现与应用一、实验目的理解和掌握线性表的顺序存储结构。掌握使用c语言机器调试线性表的基本方法。掌握顺序存储结构和关联存储结构的操作，以及对该算法的性能分析、插入、删除、查找、行表合并等基本操作。二、实验要求如果给定程序代码，程序代码将执行(1)创建线性表的功能。(2)依次输入数据点1，2，3，4，5，6，7，8，9，10。(3)删除数据元素5；(4)依次显示当前路线表中的数据元素。假定此线表的数据元素数在最坏的情况下不超过100，则应使用顺序表。程序有三个错误，也有标志，属于逻辑错误，在书上详细分析了代码后，要求学生改正错误的代码，改正后，机器调试正确执行。三、程序代码#include#define MaxSize 100Typedef int DataTypeTypedef structDataType listMaxSize；Int size SeqListVoid ListInitiate(SeqList *L)/*初始化序列表L*/l-size=0；/*定义初始数据元素数*/Int ListLength(SeqList L)/*序列表L中的当前数据元素数*/return l . size；Int list insert (seq list * l、int I、datatype x)/*在顺序表格l的位置I(0Isize)之前插入数据元素值x*/*插入成功返回1，插入失败返回0*/int j；If(L-size=MaxSize)Printf(顺序表已满，无法插入！ n )；return 0；Else if(i 0 | I L-size)Printf(参数I无效！ n )；return 0；Else/此程序之一包含错误for(j=L-size；j I；j-)l-listj=l-listj；/*准备插入*/l-listI=x；/*插入*/l-size；/*元素数加1*/return 1；Int list delete (seq list * l、int I、datatype * x)/*在删除顺序表l中，位置I(0Isize-1)的数据元素值在参数x中共存*/*如果删除成功，则返回1；如果删除失败，则返回0 *int j；If(L-size=0)Printf(顺序表为空。没有要删除的数据元素！ n )；return 0；Else if(i 0 | I L-size-1)Printf(“无效的参数I”)；return 0；Else/此程序之一出错* x=L-listI；/*将删除的元素储存在参数x中*/for(j=I 1；j=L-size-1；j)L-listj=L-listj-1；/*前移*/l-size-；/*数据元素数减1*/return 1；Int list get (seq list l，int I，datatype * x)/*如果顺序表l中第I个数据元素的值存储在x中，则返回1；如果失败，则返回0 *If(i 0 | I L.size-1)Printf(参数I无效！ n )；return 0；Else* x=l . listI；return 1；Void main(void) SeqList myListInt I、x；list initiate(my list)；for(I=0)；I 10I)插入列表(mylist，I，I 1)；ListDelete(myList，4，x)；for(I=0)；I list length(my list)；I)ListGet(，I，x)；/此程序之一出错printf(“%”，x)；四、实验任务1.更正上述过程中的错误(必需)。2.将两个排序的线性表合并为一个排序的表，并创建在基本函数中测试(选择)的合并函数。完成实验报告的编写。实验二、链表的实现和应用一、实验目的了解和掌握线性表的链存储结构。掌握使用c语言机器调试线性表的基本方法。掌握顺序存储结构和关联存储结构的操作，以及对该算法的性能分析、插入、删除、查找、行表合并等基本操作。二、实验要求如果给定程序代码，程序代码将执行(1)创建线性表的功能。(2)依次输入数据点1，2，3，4，5，6，7，8，9，10。(3)删除数据元素5；(4)依次显示当前路线表中的数据元素。假设此定线表格中资料元素的数目在最坏的情况下不超过100个，并且需要单一连结表格。程序有三个错误，有标志，属于逻辑错误，对书上的代码进行详细分析后，要求学生改正错误的代码，在机器上调试，并取得正确的执行结果。三、程序代码：#include /*此文件包含函数*/，例如pringtf()#include /*此文件包含函数*/，例如exit()#include /*此文件包含函数*，例如malloc()Typedef int DataType/*将DataType定义为int*/Typedef struct NodeDataType dataStruct Node * next SLNodevoid list initiate(sl node * * head)/*初始化*/*如果有内存空间，请请求头节点空间，并将头指针head指向头节点*/if(* head=(sl node *)malloc(size of(sl node)=null)exit(1)；(* head)-next=NULL；/*链尾标签NULL */Int ListLength(SLNode *head) /*单一连结表格的长度*/SLNode * p=head/*p指第一个节点*/int size=0；/*size最初为0*/While(p-next)！=NULL)/*周期数*/p=p-next；SizeReturn sizeInt list insert (slnode * head，int I，datatype x)/*在领导节点的单个链接列表头的数据元素head(0Isize)节点之前*/*插入存储数据元素x的节点*/SLNode *p、* q；int j；P=head/*p指第一个节点*/j=-1；/*j最初为-1*/While(p-next)！=NULL j I-1)/*最终使指针p指向数据元素ai-1节点*/p=p-next；j；If(j！=I-1)Printf(“插入位置参数无效！”)；return 0；/*创建标记为指针q的新节点*/if(q=(sl node *)malloc(size of(sl node)=null)exit(1)；q-data=x；/此程序之一出错p-next=q-next；/*分配给指针q-next */p-next=q；/*重新分配给指针p-next */return 1；Int list delete (slnode * head，int I，datatype * x)/*删除前导节点的单个链接列表头中的数据元素head(0Isize-1)节点*/*删除节点的数据元素字段值来自x。如果删除成功，则返回1。失败返回0 *SLNode *p、* s；int j；P=head/*p指第一个节点*/j=-1；/*j最初为-1*/While(p-next)！=NULL p-next-next！=NULL j I-1)/*最终使指针p指向数据元素ai-1节点*/p=p-next；j；If(j！=I-1)Printf(“插入位置参数无效！”)；return 0；/此程序之一出错s=p-next；/*指向数据元素ai节点的指针s */* x=s-data；/*指针s指向的节点的数据元素字段值为x*/p-next=s-next；/*从单个链接列表中删除数据元素ai节点*/free(s)；/*释放指针s指向的节点的内存空间*/return 1；Int list get (slnode * head，int I，datatype * x)/*导入数据元素ai与删除函数相同，只是不删除数据元素ai节点*/sl node * p；int j；P=headj=-1；While(p-next)！=NULL j I)p=p-next；j；If(j！=I)Printf(无效的元素位置参数！)；return 0；/此程序之一出错* x=p-next；return 1；Vo