北航计软实验报告实验一.docx

实验报告

实验名称线性表的插入语删除

班级
学号
姓名
成绩

实验概述：【实验目的及要求】

掌握线性表在顺序分配下的插入与删除运算；掌握线性表的链式存储结构；掌握插入排序的方法；并掌握一种产生随机数的方法。

【实验原理】

（1）随机整数的产生
设m=216，初值y0=0，则递推公式yi=mod(2053yi-1+13849，m)产生0至65535之间的随机整数。如要产生0至999之间的随机整数，只需做运算xi=INT(1000yi/m)。

（2）线性表的插入与删除
1.插入
输入：数组L(1:m)，有序线性表L(1:n)，需插入的新元素b。其中n<m。
输出：插入b后的有序线性表L(1:n)。

2.删除
输入：线性表L(1:n)，n为线性表的长度，删除的元素b（一定在线性表中）。
输出：删除b后的线性表L(1:n)。

（3）线性链表的插入排序
输入：1000个随机整数。
输出：头指针为H的有序链表。

【实验环境】（使用的软硬件）

硬件：PC
软件：VC++6.0
实验内容：【实验方案设计】

产生1000个0至999间的随机整数，并以产生的次序存入一个数据文件中。
编制一个程序，依次实现以下功能：
定义一个有序（非递减）线性表，其最大容量为1000，初始时为空。
从由1产生的数据文件中依次取前N个随机整数，陆续插入到此线性表中，并要求在每次插入后保持线性表的有序性。最后将此有序线性表打印输出。
在由（2）产生的线性表中，依在1中产生的次序逐个将元素删除，直至表空为止。
以N=100及N=400分别运行2的程序，并比较它们的运行时间。
编写一个程序，用插入排序依次将1中产生的1000个随机整数链接成有序链表（不改变原随机数在存储空间中的顺序）。

【实验过程】（实验步骤、记录、数据、分析）

（一）实验步骤
事先编制好实验内容中1、2、4的程序（可参考本实验中的方法说明），并调试通过。
运行1的程序，生成1000个0至999之间的随机整数的数据文件，并打印输出此数据文件。
以N=100运行2的程序，并记下运行时间。
以N=400运行2的程序，并记下运行时间。
运行4的程序。
整理程序清单和运行结果，写出实验报告。

（二）程序清单
【实验一】
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
voidmain()
{
longintm,a=0;
intb;
FILE*fp;
intc[1000];
fp=fopen("E:\\file.txt","w");
m=pow(2,16);
for(b=0;b<1000;b++)
{
a=(2053*a+13849)%m;
c[b]=(1000*a)/m;
fprintf(fp,"%5d",c[b]);
}
for(b=0;b<1000;b++)
{
printf("%5d",c[b]);
if((b+1)%10==0)
printf("\n");
}
fclose(fp);
}

【实验二】
#include<stdio.h>
#include<stdlib.h>

voidmain()
{
inta[1000]={0};
intb[1000]={0};
inti,j,n,m;
FILE*fp;
fp=fopen("E:\\file.txt","r");
rewind(fp);
printf("\nPleaseinputtheamountyouwanttoreadfromthefile:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
fscanf(fp,"%d",&b[i]);
a[i]=b[i];
if(i==0)
continue;
while(a[i]>a[i-1])
{
m=a[i];
a[i]=a[i-1];
a[i-1]=m;
}
}
printf("\nThefinaldatais:\n");
for(i=0;i<n;i++)
printf("%3d\t",a[i]);
fclose(fp);
for(i=0;i<n;i++)
{
j=-1;
while(a[++j]!=b[i]);
for(;j<n;j++)
a[j]=a[j+1];
printf("\n");
for(m=0;m<n;m++)
printf("%d\t",a[m]);
}
}

【实验三】
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

voidmain()
{
clock_tstart,finish;
doubleduration;
inta