安徽工程大学实验报告样本

             数 据 结 构   实 验 报 告

班级   专业09X      姓名  XXXXXX（学号） 同组者    /    成绩                

                    日期   实验课的日期     指导教师     汪军      

实验名称                           线性表及其应用

一、实验目的：

熟练掌握线性表的顺序、链式存储结构的定义；以及在顺序、链式存储结构下基本操作的实现。熟练掌握线性表的动态分配存储空间的方法，以及指针作为函数参数的使用和应用。 

二、需求分析：

    1、分别定义数据元素为整型的线性结构的顺序存储方式和链式存储方式。

2、在每种存储结构下实现下面的操作：

    （1）创建初始化一个空线性表；

    （2）销毁线性表；

    （3）在线性表插入一个元素；

    （4）在线性表中删除一个元素；

    （5）求线性表的长度；

    （6）按序号检索查找线性表；

    （7）按元素值检索查找线性表；

    （8）按序号检索查找线性表；

    （9）遍历线性表。

3、利用线性表实现两个有序线性表的合并操作（选做）

三、系统设计

1、线性表的逻辑结构

线性表List是n个具有相同数据类型的数据元素的集合。通常描述为：

List =（e1，e2，…，ei-1，ei，ei+1，…，en）（n≥0）

表中相邻元素之间存在着线性关系，第一个元素e1为首元素，无直接前驱；最后一个元素en为尾元素，无直接后继，其余元素都有前驱和后继元素。List表中的数据元素类型相同，元素之间存在前驱与后继关系。

2、线性表的顺序存储结构

线性表的顺序存储是是用内存中的一段地址连续的存储空间顺序存放线性表的每一个元素。它用存放内存中的地址物理上的相邻关系表示线性表中数据元素之间的先后关系。

    #define  MAXSIZE  100

typedef  int  DataType；

typedef  struct  Node 

{ 

DataType  data[MAXSIZE]；

             int  length；

} SeqList；

3、算法流程图

    顺序表的插入操作：在表的第i个位置上插入一个值为x的新元素，

  (1)检查待插入的表是否存在，若不存在退出；

  (2)判断顺序表是否满(即表长length是否大于等于MAXSIZE)？若满，退出；否则执行(3)；

  (3)检查插入位置的合法性( i 满足1<=i<=length+1)。若不满足，退出；否则执行(4)；

  (4)将第i元素到第length元素顺序向下移动一位，为新元素的插入腾出位置；

  (5)将x置入第i位置；

  (6)修改表长； 

4、算法详细设计

顺序表的插入算法：

int  Insert_SeqList(PSeqList SeqListPoint，int i，DataType  x)

{   /*顺序表插入，入口参数：顺序表指针，插入位置，插入元素，返回标志，1表示成功，0表示插入位置不合法，-1表示溢出，-2表示表不存在*/

      int j;

if (!SeqListPoint)

         {

           printf(“表不存在”);

           return(-2); /*表不存在，不能插入*/

          }  

if (SeqListPoint-> length >= MAXSIZE)

          { 

             printf(“表溢出”); 

              return(-1); /*表空间已满，不能插入*/

           } 

if (i<1 || i> SeqListPoint-> length +1) 　/*检查插入位置的合法性*/

{　

              printf(“插入位置不合法”); 

               return(0); 

} 

       for(j= SeqListPoint -> length -1; j>=i-1; j--)

SeqListPoint ->data[j+1]= SeqListPoint ->data[j]; /* 移动元素 */

       SeqListPoint ->data[i-1]=x;　　　　/*新元素插入*/

       SeqListPoint -> length ++; 　　/*表长加 1*/

         return (1);　　　/*插入成功，返回*/

} 

…...

  SeqListOper(PSeqListPoint  SeqListP)

  {    char Op=’’;

       int x,i;

       while(Op!=’q’)

        {

switch(Oper)

       {

         case  ‘i’: 

                printf(“Enter SeqList_Insert Element x and i :”);

                scanf(“%d ,%d”,&i, &x);

                SeqList_Insert(SeqListP,i,x);

         case  ’d’:

                ……;

          default:

             ; 

        }

        ShowSeqSubMenu(void);

      clrscr();

        }

}

/**************************************/

void ShowMainMenu(void)

{

 printf(“*********************************************\\n”);

    printf(“**********Enter Main Operation Code***********\\n”);

    printf(“******** ***l:  LinkList Operation**************\\n”);

    printf(“************s:  SeqList Operation **************\\n”);

    printf(“************q:  Exit System *******************\\n”);

     printf(“**********************************************\\n”);

}

5、主函数设计

int main(int argc, char* argv[])

{    PSeqList  SeqListPoint;

LinkList H;

char Oper;

SeqListPoint =Init_SeqList( );

H =Creat_LinkList();

if(! SeqListPoint || ! H)

 return 0;

      Oper=’’;

while(Oper!=’q’)

{  

switch(Oper)

    {

       case  ‘l’:

             LinkLinkOper(H);

       case  ’s’:

             SeqListOper(SeqListPoint);

       default:

             ; 

    }

   clrscr();

   ShowMainMenu();

 Oper=getch();

 }   

Destroy_SeqList（）

Destroy_LinkList（&H）

return 0;

}

6、程序结构图

四、调试与测试

1、主要是逻辑错误的调试过程记录（说明出错现象和分析原因以及解决的办法，错误直接用红色的笔在详细设计上改正）

    ……

2、测试过程的设计和使用的测试数据及测试结果

（1）插入算法Insert_SeqList的测试：

采用下面的数据，将算法的特殊情况都考虑在内进行全面测试算法

i＝1     插入元素 0

i＝表长  插入元素 -4

i>表长   插入元素 5

i<1 插入元素 12

i＝表长与1之间的数 插入元素124

测试结果：经过测试，Insert_SeqList在上述情况下均是正确，通过测试

……

五、实验小结

……