实验报告书写范例

实验一（必做,设计性实验，2学时）实验题目：顺序表基本操作1、在非递减有序顺序表中插入一个元素x，保持顺序表有序性(2.11)2、比较两个顺序表的大小（2.12）3、顺序表元素的逆置(2.21)4、两个（有序或无序）顺序表的合并(书上算法2.1和2.2)实验目的：熟悉将算法转换成程序代码的过程。了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。熟练掌握顺序表的基本操作：查找、插入、删除、合并等，掌握顺序表的随机存取特性。实验要求：1、要求用静态分配的一维数组和动态分配的一维数组来完成实验题目。分析静态分配的一维数组和动态分配的一维数组在顺序表基本操作实现上的共同点和区别。2、对顺序表插入的算法，要求用两种方法实现：自己编写函数实现；调用顺序表基本操作ListInsert(SqList&L,inti,ElemTypex)，比较使用自己编写的插入函数和调用顺序表基本操作的函数两种实现方法之间的优缺点。3、对所编写的算法进行时间复杂度分析。实验内容和实验步骤：1动态存储结构typedefstruct{Elemtype*elem;//存储空间的基地址。intlength;//当前长度intlistsize;//当前分配的存储容量}SqList;静态分配的存储结构#definen100ElemTypeL[n];共同点：都是顺序存储结构，或数组不同点：存储空间可变与否。2方法1intInsertOrderList1(SqList&L,intx){if(L.length>=L.listsize){newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));if(!newbase) exit(OVERFLOW);//分配不成功L.elem=newbase;L.listsize+=LISTINCREMENT;}p=&(L.elem[L.length-1]);//指向表尾元素位置while(p>=&(L.elem[0])&&*p>x){*(p+1)=*p;--p;}*(p+1)=x; ++L.length;//完成插入，线性表长度增1returnOK;}//InsertOrderList1方法2intInsertOrderList2(SqList&L,intx){ inti; i=1;//数组下标从1开始 while((i<=L.length)&&(x>L.elem[i])) i++;//查找i是插入位置 ListInsert_Sq(L,i,x);//插在第i个元素之前 returnOK;}//InsertOrderList2方法2更简单，代码复用程度高，但是需要给出明确的接口参数。3算法时间复杂度主要由插入元素的位置和移动元素的多少决定，如果表长为n，则时间复杂度为O（n）。实验用测试数据和相关结果分析：（由学生填写）第一组：L：14567结果：014567X：0第二组：L：14567结果：0145678X：8第三组：L：14567结果：0144567X：4LX插入后分析第一组145670014567在特殊位置上的插入情况应考虑到第二组145678145678正常第三组145674144567正常实验总结：（由学生填写）动态分配的存储结构因为可以人为控制分配空间的大小，所以灵活，既不会浪费空间，也不会产生溢出现象。而静态分配存储空间比较死板，必须事先指定所需空间大小，在存储空间需求不定的时候无法使用。