北航计软实验报告实验一

实验报告实验名称线性表的插入语删除班级学号姓名成绩实验概述：【实验目的及要求】掌握线性表在顺序分配下的插入与删除运算；掌握线性表的链式存储结构；掌握插入排序的方法；并掌握一种产生随机数的方法。【实验原理】（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[1000]={0};intb[1000]={0};inti,j,n,m; FILE*fp;start=clock(); 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]);}finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;printf("%fms\n",duration);}【实验四】#include<stdio.h>#include<stdlib.h>#definen1000main(){inta[1001][2];inti,j;FILE*fp; fp=fopen("E:\\file.txt","r");rewind(fp);for(i=0;i<n;i++) { fscanf(fp,"%d",&a[i][1]); a[i][2]=i;if(i==0)continue; for(j=0;j<i;j++) { if(a[j][1]>a[i][1]) { a[j][2]++; a[i][2]--;}} }printf("Theoriginaldata:\n");for(i=0;i<n;i++)printf("%d\t",a[i][1]);printf("\nThefinaldata:\n");for(i=0;i<n;i++) { for(j=0;a[j][2]!=i;j++); printf("%d\t",a[j][1]);}fclose(fp);}（三）运行结果【实验一】【实验二】【实验三】N=200N=400【实验四】【小结】通过此次实验，我掌握了线性表在顺序分配下的插入与删除运算，还有链表的存储结构、插入排序的方法，也对VC++的使用更加熟悉，同时对C语言进行了简单的复习与回顾，学习了产生随机数、文件数据输入输出、计算时间间隔的方法。

虽然在实验过程中遇到了许多困难，开始编程序时存在各种