学期： 20##-2011学年第一学期  指导教师：  杨华莉      成绩：           

实验一 顺序表的基本操作

一、              实验目的

1．掌握使用VC++6.0调试程序的基本方法；

2．掌握线性表的顺序存储结构的类型定义；

3．掌握顺序表的基本操作的实现,如：插入、删除、遍历、查找、排序、修改、合并等；

4．掌握顺序表的应用。

二、              实验要求

1．认真阅读和掌握本实验的示例程序。

2．上机运行示例程序，打印出程序的运行结果，并作必要的说明。

3．对示例程序，按照对线性表的操作需要，在程序中至少添加2个顺序表的相关操作。如：

                        i.              查找并显示分数在区间[a，b）的学生信息；

                      ii.              查找并显示最高分或最低分学生信息；

                    iii.              统计不及格或及格人数及所占比例；

                    iv.              将信息表按学号、姓名或分数升序或降序排列；

                      v.              按学号顺序进行数据元素的插入；

                    vi.              删除指定学号或姓名的学生信息；

                  vii.              修改某个学生的信息；

                viii.              其它。

4．重新改写主函数（要求必需调用自己添加的操作），打印出文件清单（自己添加的函数、修改后的主函数和运行结果）。

5．对修改后的程序，分析每一个算法（函数）的时间复杂度。

6．根据上述要求撰写实验报告，并简要给出算法设计小结和心得。

三、              实验环境

1．台式计算机每人一台；

2．软件：Visual C++6.0

四、              实验内容和实验结果

一．示例程序运行结果及说明

            

             

            

           

二．自己添加的新函数(至少2个)，要求加必要的注释。

SqList  Delete_SqList(SqList &L)//删除学生信息

 {

    Elemtype x;

    int i=0;

    int choice=DMenu();

    char name[25];

    int num,k;

    if(!L.length)

    {

       printf("表为空，无法删除!");

       exit(0);

    }

    switch(choice)

    {

      case 1:  //按姓名删除

           printf("\n请输入要删除的学生的姓名\n");

           scanf("%s",&name);

           k=strcmp(name,L.data[i].name);//比较姓名

            if(k==0)

           {

             x=L.data[i-1];

             for(int m=L.length-1;m>=i-1;--m)

                L.data[i-1]=L.data[i];

                 --L.length;

                break;

           }

      case 2:  //按学号删除

           printf("\n请输入要删除学生的学号\n");

           scanf("%d",&num);

           if(num==L.data[i].num)

           {

            for(int m=L.length-1;m>=i-1;--m)

                L.data[i-1]=L.data[i];

                 --L.length;

                break;

           }

      case 3:break;

              

    }

    return L;

}

void TongJi_SqList(SqList L)//统计信息表中学生的信息

{

  int i;

  int choice=TMenu();//选择所要统计的方式的菜单

  switch(choice)

  {

     case 1: for(i=0;i<L.length;i++)//统计男生信息

               if(L.data[i].sex=='m')

                   PrintElem(L.data[i]);

                   break;

     case 2: for(i=0;i<L.length;i++)//统计女生的信息

               if(L.data[i].sex=='f')

                   PrintElem(L.data[i]);

                   break;

     case 3: for(i=0;i<L.length;i++)//统计不及格的人

               if(L.data[i].score<60)

                  printf(“不及格的为：”);

                   PrintElem(L.data[i]);

                   break;

     case 4: for(i=0;i<L.length;i++)//统计优秀的人

                 if(L.data[i].score>90)

                  printf(“分数在90分以上的为：”);

                   PrintElem(L.data[i]);

                   break;

     case 5: break;

  }

}

void PaiXu_SqList(SqList L)//排序

{

  int i,j,k;

  int choice=PMenu();//选择菜单

  switch(choice)

  {

    case 1: //按序号升序排列

                for(i=0;i<L.length;i++)

                       for(j=0;j<L.length-i;j++)

                        if(L.data[j].num>L.data[j+1].num)

                        {

                          k=L.data[j].num;

                          L.data[j].num=L.data[j+1].num; //冒泡法排序

                             L.data[j+1].num=k;

                        }

                        for(j=0;j<L.length;j++)//输出排序结果

                        PrintElem(L.data[j]);

                        break;

       case 2:  //按分数降序排列

                 for(i=0;i<L.length;i++)

                       for(j=0;j<L.length-i;j++)

                        if(L.data[j].score<L.data[j+1].score)

                        {

                          k=L.data[j].score;

                             L.data[j].score=L.data[j+1].score;

                             L.data[j+1].score=k;

                        }

                        for(j=0;j<L.length;j++)//输出结果

                        PrintElem(L.data[j]);

                        break;

       case 3:  //按分数升序排列

                for(i=0;i<L.length;i++)

                       for(j=0;j<L.length-i;j++)

                        if(L.data[j].score>L.data[j].score)

                        {

                          k=L.data[j].score;

                             L.data[j].score=L.data[j+1].score;

                             L.data[j+1].score=k;

                        }

                        for(j=0;j<L.length;j++)//输出排序结果

                        PrintElem(L.data[j]);

                        break;

    case 4: break;

  }

}

三．改写后的主函数（要求必需调用自己添加的操作）

void main()

{//通过文件input1.txt输入数据,结果输出到文件output1.txt

    //打开输入输出文件

    FILE *in,*out;

   if((in=fopen("input1.txt","r"))==NULL)

   {  printf("cannot open infile\n");

      exit(0);

   }

   if((out=fopen("output1.txt","w"))==NULL)

   {  printf("cannot open infile\n");

      exit(0);

   }

    int choice;

    SqList L;

    Init_SqList(L);//系统文件初始化,构造空表L

    while(1)

    {

       choice=Menu();

       switch(choice)

       {

       case 1:    Creat_SqList(L,in);

              //导入数据,根据文件input.txt读入的数据建立顺序表L

              break;

       case 2:    Traver_SqList(L);//查询,输出顺序表

              break;

       case 3:    Insert_SqList(L);// 在顺序表L中插入一个新元素

              break;

       case 4:    Delete_SqList(L);       

               break;//删除元素

       case 5:    TongJi_SqList(L);   

               break;//统计

       case 6:    PaiXu_SqList(L);        

               break;//排序

       case 7:    Cheng_SqList(L);

               break;//修改

       case 0: SaveList(L,out);fclose(in);fclose(out);exit(-1);break;//保存数据,并退出系统

       }

       getchar();

    }

}

四．改写后程序的运行结果。

          

       

   

      

五．简要给出所选示例程序中算法的时间复杂度分析结果。

void PrintElem(Elemtype  a);//打印输出数据元素a的各数据项

  此函数的

void Init_SqList(SqList &L);//构造一个空的顺序表L

void SaveList(SqList L,FILE *out);//保存顺序表L的数据

//建表,从文件读取数据,以尾插法建立顺序表L

void Creat_SqList(SqList &L,FILE *in)

;

//查询,遍历顺序表L(输出L中的数据序列)

void Traver_SqList(SqList L);

void TongJi_SqList(SqList L);

void PaiXu_SqList(SqList L);

void Cheng_SqList(SqList L);

//添加,在顺序表L中插入一个新元素

SqList  Insert_SqList (SqList  &L);

SqList  Delete_SqList(SqList &L);

六．简要给出算法设计小结和心得。

平时我们学C语言视乎都是为了考试或者做一些比较常规的题目，而这次实训却给我们的将所学知识运用于解决实际问题的机会，让人更有激情，这就是编写软件的在雏形，也让我们感受到了编写软件程序的乐趣。但是不仅仅是如此，更为重要的是在运用所学知识的过程中，记住这些知识，并能够广泛的运用！这一次编写大作业的程序又让我感受到学程序可以锻炼缜密的思维了。因为平时练习的都是小程序，所以句段比较少，一些错误都很容易被检查出来，但是这次实训却是上百段的语句，难以检查，似乎也没有经验去怎么检查，那一刹那感觉到很急，但又不知如何是好，可是又不轻易的向老师询问，因为好像蛮简单，相信自己能够检查出来，所以我一般都是独立思考的完成的，只有少部分是在老师和与同学讨论下完成的。

 

第二篇：数据结构实验报告模板20xx1027

数据结构实验报告

实验名称： 实验X——XXXX

学生姓名：王一达

班    级：2010211118

班内序号： 6

学    号： 10210531

日    期： 2011/10/31

1．实验要求

[正文格式要求]

    字体：汉字宋体、英文Times New Roman

    字号：五号

       颜色：黑色

行距：单倍行距

    [内容要求]

         描述要求的实验目的和具体的实验内容

2. 程序分析

  [正文格式要求] 见1实验要求中的格式要求

2.1 存储结构

     [内容要求]

存储结构：顺序表、单链表或其他存储结构，需要画示意图

2.2 关键算法分析

1声明一个T模板，声明一种新的节点类型，包括数据单元和一个指针单元，也即一个数据域和一个指针域。

2构造函数

在堆中建立新节点

将已有的数组元素逐个赋值到新节点的数据域，具体步骤是建立新节点，把数组元素写入到头指针所指的节点的数据域，然后在第一次初始化数据时也就是最后的尾节点的指针域为空，以后则把每一个新加入的节点的这针域指向上一个声明的节点空间，最后修改头节点的指针域，将新节点加入到链表中。

[内容要求]

1、关键算法：比如插入、删除等基本算法的思想，或是约瑟夫问题的基本思想等，要求使用自然语言描述或伪代码描述。

2、代码详细分析：比如单链表的删除，需要将5句关键代码写清楚，并画出示意图，例如：删除结点示意图：

图1 删除结点示意图

算法步骤：

①从第一个结点开始，查找第i-1个元素，设为p指向该结点；

②设q指向第i个元素：q = p->next;

③摘链，即将q元素从链表中摘除：p->next = q->next;

④保存q元素的数据：x = q->data;

⑤释放q元素：delete q;

说明：如果算法比较复杂，可以将多句代码合成一个步骤进行说明。比如也可以这样写：

①从第一个结点开始，查找第i-1个元素，设为p指向该结点；

②设q指向第i个元素：q = p->next;

③摘链，即将q元素从链表中摘除：

p->next = q->next;  

x = q->data

        delete q;

3、计算关键算法的时间、空间复杂度

2.3 其他

[内容要求]

        1、可选，你认为还需要补充的任何说明都可以

3.  程序运行结果

  [正文格式要求] 见1实验要求中的格式要求

[内容要求]

1、  测试主函数流程：流程图如图2所示

 

图2 流程图示意图

2、  测试条件：比如问题规模n的数量级是多少？插入、删除元素的位置如何选择？

3、  测试结论

4.  总结

[正文格式要求] 见1实验要求中的格式要求

   

[内容要求]

1、  调试时出现的问题及解决的方法

2、  心得体会

3、  下一步的改进

实验报告总字数要求不少于1000字。