JSP实验指导书.docx

JSP实验指导书.docx

《JSP实验指导书.docx》由会员分享，可在线阅读，更多相关《JSP实验指导书.docx（13页珍藏版）》请在冰点文库上搜索。

JSP实验指导书

数据结构实验指导书

适用专业：

网络工程学院

指导教师：

王翔

实验一：

线性表的基本操作

实验目的：

掌握线性表的基本操作：

插入、删除、查找以及线性表合并等运算在顺序存储结构的运算。

能从实际问题中抽象出线性表结构及其运算的模型

实验课时：

4课时

实验要求：

1.掌握线性表的顺序存储的基本运算的算法

2.掌握线性表链式存储的基本运算的算法

3.根据算法写出对应程序（使用TC，或C++完成程序）

4.调试成功，并保存程序源代码，以备检查

实验内容：

1.设计——实现用户通过键盘输入一组数，并输入一个需要插入的数，和插入的位置，完成整个插入。

例，输入1，2，3，4再输入5，3。

最后程序运行结果为1，2，5，3，4。

1）先写出完成该操作的算法

2）以程序方式实现算法

3）数的长短自行定义，可以用数组存储。

4）若有能力的同学，可以考虑用链表如何完成该项操作

5）该设计最后以实验报告的形式提交

2．验证——上机实现链表的基本操作程序，并结合对应的算法，了解链表的工作情况。

#include

#include"malloc.h"

#include"conio.h"

structmylist

{intdata;

structmylist*next;

};

structmylist*createlist（void）

{intx;

structmylist*s,*q,*h;

h=（structmylist*）malloc（sizeof（structmylist））;

h->next=NULL;

q=h;

printf（"inputnumber:

"）;

scanf（"%d",&x）;

while（x!

=0）

{

s=（structmylist*）malloc（sizeof（structmylist））;

s->data=x;

q->next=s;

printf（"inputthenumber:

"）;

scanf（"%d",&x）;

s->next=NULL;

q=s;

}

return（h）;

}

intputlist（structmylist*head）

{inti=0;

if（head->next==NULL）

{return0;}

while（head->next!

=NULL）

{i++;

printf（"the%dnumberinlistis:

%d\n",i,head->next->data）;

head=head->next;

}

return1;

}

voidmain（）

{structmylist*my,*temp;

my=createlist（）;

if（putlist（my）==0）

printf（"theinputlistisempty!

"）;

while（my->next!

=NULL）

{temp=my;

my=my->next;

free（temp）;

}

printf（"over,pressanykeytoend"）;

getch（）;

}

3．验证——上机实现一元多项式的加法程序，并结合算法理解链表的工作过程和基本操作的实现。

＃include

＃include

＃include

#define LEN sizeof（node）

typedefstructpolynode  /*用单链表存储多项式的结点结构*/

{

     intcoef; /*多项式的系数*/

     intexp;  /*指数*/

     structpolynode*next;/*next是structpolynode类型中的一个成员，它又指向

                        structpolynode类型的数据，以此建立链表*/

}node;/*若定为"node,*list;"，意即node*与list同为结构指针类型*/

node*create（void） /*指针函数，返回指针类型；用尾插法建立一元多项式的链表的函数*/

{

    node*h,*r,*s;

    intc,e;

    h=（node*）malloc（LEN）; /*建立多项式的头结点，为头结点分配存储空间*/

    r=h;/*r指针始终动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/

    printf（"coef:

"）;

    scanf（"%d",&c）;/*输入系数*/

    printf（"exp:

"）;

    scanf（"%d",&e）;/*输入指针*/

    while（c!

=0） /*输入系数为0时，表示多项式的输入结束*/

   {

         s=（node*）malloc（LEN）;/*申请新结点*/

         s->coef=c; /*申请新结点后赋值*/

         s->exp=e;  /*申请新结点后赋值*/

         r->next=s;/*做尾插，插入新结点*/

         r=s; /*r始终指向单链表的表尾*/

         printf（"coef:

"）;

         scanf（"%d",&c）;

         printf（"exp:

"）;

         scanf（"%d",&e）;

   }

   r->next=NULL;/*将表的最后一个结点的next置NULL，以示表结束*/

   return（h）;

}

voidpolyadd（node*polya,node*polyb）/*一元多项式相加函数，用于将两个多项式相加，然后将和多项式存放在多项式polya中，并将多项式ployb删除*/

{

      node*p,*q,*pre,*temp;

      intsum;

      p=polya->next;/*令p和q分别指向polya和polyb多项式链表中的第一个结点*/

      q=polyb->next;

      pre=polya;   /*位置指针，指向和多项式polya*/

      while（p!

=NULL&&q!

=NULL）/*当两个多项式均未扫描结束时，执行以下操作*/

     {

           if（p->expexp）          /*若p指向的多项式指数小于q指的指数*/

           {

                  pre->next=p;     /*将p结点加入到和多项式中*/

                  pre=pre->next;

                  p=p->next;

           }

           elseif（p->exp==q->exp）   /*若指数相等，则相应的系数相加*/

           {

                  sum=p->coef+q->coef;

                  if（sum!

=0）

                  {

                       p->coef=sum;

                       pre->next=p;pre=pre->next;p=p->next;

                       temp=q;q=q->next;free（temp）;

                   }

                 else    /*如果系数和为零，则删除结点p与q，并将指针指向下一个结点*/

                {

                      temp=p->next;free（p）;p=temp;

                      temp=q->next;free（q）;q=temp;

                }

          }

         else                     /*若p指数大于q指数*/

         {

                pre->next=q; /*p结点不动，将q结点加入到和多项式中*/

                pre=pre->next;

               q=q->next;

          }

   }

   if（p!

=NULL） /*多项式A中还有剩余，则将剩余的结点加入到和多项式中*/

          pre->next=p;

   else       /*否则将B的结点加入到和多项式中*/

          pre->next=q;                                                        

}

voidprint（node*p）/*输出函数，打印出一元多项式*/

{                                                                                                     

   while（p->next!

=NULL）

   {  

       p=p->next;

       printf（"    %d*x^%d",p->coef,p->exp）;  

   }

}  

main（）      /*主函数*/

{

     node*polya,*polyb;

     printf（"Welcometouse!

\n"）;

     printf（"\nPleaseinputtheployaincludecoef&&exp:

\n"）;

      polya=create（）; /*调用建立链表函数，创建多项式A*/

     print（polya）;

     printf（"\nPleaseinputtheploybincludecoef&&exp:

\n"）;

     polyb=create（）; /*同理，创建B*/

     print（polyb）;

     printf（"\nSumofthepolyis:

\n"）;

     polyadd（polya,polyb）;   /*调用一元多项式相加函数*/

     print（polya）;           /*调用输出函数，打印结果*/

     printf（"\n"）;

}

4．设计——（选做）以程序形式实现A=A∪B的运算

1）可以以顺序存储来实现，也可以用链表实现

2）自己给定A、B的值

3）完成者提交实验报告，可作为加分的依据。

实验二约瑟夫问题

实验目的：

掌握线性表的运用——约瑟夫环模型，能运用该模型进行问题的解决。

实验课时：

4课时

实验要求：

1.掌握线性表的基本操作算法

2.掌握约瑟夫环的基本模型过程

3.能以程序方式实现约瑟夫环的问题

4.调试成功，并保存程序源代码，以备检查

实验内容：

1.完成一个约瑟夫问题的通用算法

2.设计——将该算法以程序实现

1）可以以链表实现，也可以以数组实现

2）已知条件可自行定义（可以将程序定义为20个人的圈子中，报数为3的人退出，也可以完成一个通用的程序）

3）完成程序提交实验报告（包括算法和程序）

3．设计——（选做）给出更进一步的约瑟夫环的算法：

编号为12，……n的n个人按顺时针方向围成一圈，每人持有一个密码（正整数），一开始任选一个正整数作为报数上限值m，从第一个人开始按顺序时针方向自1开始顺序报数，报道m时停止报数，报m的人处列将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

实验三栈和队列的应用

实验目的：

掌握栈和队列的特点，熟悉栈和队列的基本操作，能从实际问题中抽象栈和队列的模型。

能运用栈和队列的不同特点解决实际的问题。

实验课时：

4课时

实验要求：

1.掌握栈和队列的存储形式

2.掌握栈和队列的基本特点和基本运算的算法

3.根据算法写出对应程序（使用TC，或C++完成程序）

4.能够从实际问题中抽象出合适的对象模型

5.调试成功，并保存程序源代码，以备检查

实验内容：

1.完成将一个10进制正整数变为8进制的程序

1）先写出对应算法

2）写出完整程序，用栈的形式来完成

2.实现判断回文的程序运算

1）回文的含义是回文就是正读、反读均相同的字符序列如：

abba，abcba；

2）解决问题的方法有很多，写出其中任一种算法

3）上机实现这种算法，并提交实验报告

3.验证队列数据的存取程序，从程序中了解队列的特点以及基本操作

#include

#definemaxsize10

Intqueue[maxsize];

Intfront=-1;

Intrear=-1;

/*---------------------*/

输入队列数据

/*---------------------*/

Voidaddqueue（intvalue）

{

If（rear>=maxsize）

Printf（“thequeueisfull”）;

Else

{rear++;

Queue[rear]=value;

}

}

/*---------------------*/

输出队列数据

/*---------------------*/

Intdelqueue（）

{

Inttemp;

If（front==rear）

Return-1;

Else

{

Front++;

Temp=queue[front];

Queue[front]=0;

Returntemp;

}

}

/*---------------------*/

主程序

/*---------------------*/

Voidmain（）

{

For（i=0;i<=maxsize;i++）;

Queue[i]=0;

Printf（“pleaseinputtheinputvalue”）;

Scanf（“%d”,&temp）;

Addqueue（temp）;

Printf（“thecontentofqueue:

”）;

For（i=0;i<=maxsize;i++）

{

If（queue[i]!

=0）

Printf（“%d”,queue[i]）;

}

If（（temp=delqueue（））==-1）

Printf（“thequeueisempty\n”）;

Else

{

For（i=0;i<=maxsize;i++）

{

If（queue[i]!

=0）

Printf（“[%d]”,queue[i]）;

}

}

}

4（选做）以程序实现完成循环队列的插入删除操作

实验四串的应用

实验目的：

熟悉串的基本操作和具体操作过程

实验课时：

4课时

实验要求：

1.掌握串的基本操作过程、步骤

2.掌握串的操作的实现过程，有些串函数能自行编写

3.先写出算法，再根据算法写出对应程序（使用TC，或C++完成程序）

4.调试成功，并保存程序源代码，以备检查

实验内容：

1.编写一程序，实现从字符串s中，返回第I个字符开始，长度为len的子串（s，I，len都可以从键盘输入）

要求：

写出算法，再以程序实现，最后递交实验报告。

2.完成两个字符串连接的操作（不要使用函数）。

3．巩固前面线性表、栈、队列的知识

实验五查找

实验目的：

掌握各种查找方法的过程和算法，能对不同的情况采用不同的查找方法，分析各种方法的性能。

实验课时：

4课时

实验要求：

1.掌握各种查找算法及查找过程、实现的时间复杂度

2.能将各种查找算法以程序实现，并在程序中能看到查找的次数

3.写出对应程序（使用TC，或C++完成程序）

4.调试成功，并保存程序源代码，以备检查

实验内容：

1.已知一个有序序列，先要求插入一个元素，使其序列仍然有序。

1）序列的长短可预先设置

2）插入的元素由键盘输入

3）插入的方法可以使用顺序插入，也可以使用折半插入（最好使用折半插入）

4）完成该程序、递交实验报告

2．（选做）将课本上讲过的其他算法，试着写成程序运行成功。

实验六排序

实验目的：

掌握多种排序的方式方法，了解各种方法的算法表示，以及性能分析和适用场合。

实验课时：

4课时

实验要求：

1.掌握各种排序的方法和过程

2.了解各种排序方法的性能分析，找到合适的场合下使用

3.把排序方法转化为程序实现

4.调试成功，并保存程序源代码，以备检查

实验内容

1．用“选择法”对10个整数进行排序

1）先写出对应算法

2）根据你所写的算法，写出完整程序。

3）该设计最后递交实验报告（1、2两题任一题提交实验报告）

2．完成用“冒泡法对输入的10个字符从小到大排序

1）先写出对应算法（从头找到尾，或是从尾找到头）

2）可以考虑在程序中显示查找该数所比较的次数。

（选做）

3）根据你所写的算法，写出完整程序。

4）该设计最后递交实验报告（1、2两题任一题提交实验报告）

3．（选做）选择书上的其他排序算法，以程序方式实现