Lab Report of Medical Functional Experimentation

                                                       Date：                            

第二篇：实验报告书写范例

实验一（必做,设计性实验，2学时）

实验题目：顺序表基本操作

1、在非递减有序顺序表中插入一个元素x，保持顺序表有序性(2.11)

2、比较两个顺序表的大小（2.12）

3、顺序表元素的逆置(2.21)

4、两个（有序或无序）顺序表的合并(书上算法2.1和2.2)

实验目的：

1、              熟悉将算法转换成程序代码的过程。

2、              了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。

3、              熟练掌握顺序表的基本操作：查找、插入、删除、合并等，掌握顺序表的随机存取特性。

实验要求：

1、要求用静态分配的一维数组和动态分配的一维数组来完成实验题目。分析静态分配的一维数组和动态分配的一维数组在顺序表基本操作实现上的共同点和区别。

2、对顺序表插入的算法，要求用两种方法实现：

（1）自己编写函数实现；

（2）调用顺序表基本操作ListInsert(SqList &L,int i,ElemType x)，比较使用自己编写的插入函数和调用顺序表基本操作的函数两种实现方法之间的优缺点。

3、对所编写的算法进行时间复杂度分析。

实验内容和实验步骤：

1

动态存储结构

 typedef struct

{        Elemtype *elem;//存储空间的基地址。

          int length;//当前长度

          int listsize;　//当前分配的存储容量

}SqList;

静态分配的存储结构

#define n 100

ElemType L[n];

共同点：都是顺序存储结构，或数组

不同点：存储空间可变与否。

2 方法1

int InsertOrderList1(SqList &L,int x)

{  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; //完成插入，线性表长度增1

  return OK;

}//InsertOrderList1

方法2

int InsertOrderList2(SqList &L,int x)

 {

      　int i;

      　i=1;//数组下标从1开始

      　while((i<=L.length)&&(x>L.elem[i]))

           　i++;//查找i是插入位置

      　ListInsert_Sq(L,i,x);//插在第i个元素之前

      　return OK;

}//InsertOrderList2

方法2更简单，代码复用程度高，但是需要给出明确的接口参数。

3 算法时间复杂度主要由插入元素的位置和移动元素的多少决定，如果表长为n，则时间复杂度为O（n）。

实验用测试数据和相关结果分析：（由学生填写）

第一组：L：1 4 5 6 7      结果：0 1 4 5 6 7

X：0

第二组：L：1 4 5 6 7      结果：0 1 4 5 6 7 8

X：8

第三组：L：1 4 5 6 7      结果：0 1 4 4 5 6 7

X：4

实验总结：（由学生填写）

动态分配的存储结构因为可以人为控制分配空间的大小，所以灵活，既不会浪费空间，也不会产生溢出现象。而静态分配存储空间比较死板，必须事先指定所需空间大小，在存储空间需求不定的时候无法使用。同为数组，其具有随机存取的特性，且存储密度高，但是涉及到插入、删除元素时需要移动大量的元素，时间消耗在元素的移动上。如果涉及到频繁插入、删除等操作时不应使用数组做存储结构。