北航计软实验报告一.doc

北航计算机软件基础实验报告计算机软件基础上机实验报告（一）XXXXXX班 XXX 100211891.实验目的掌握线性表在顺序分配下的插入与删除运算；掌握线性表的链式存储结构；掌握插入排序的方法；并掌握一种产生随机数的方法。2.实验内容1产生1000个0至999间的随机整数，并以产生的次序存入一个数据文件中。2编制一个程序，依次实现以下功能：(1)定义一个有序（非递减）线性表，其最大容量为1000，初始时为空。(2)从由1产生的数据文件中依次取前N个随机整数，陆续插入到此线性表中，并要求在每次插入后保持线性表的有序性。最后将此有序线性表打印输出。(3)在由（2）产生的线性表中，依在1中产生的次序逐个将元素删除，直至表空为止。3以N=100及N=400分别运行2的程序，并比较它们的运行时间。4编写一个程序，用插入排序依次将1中产生的1000个随机整数链接成有序链表（不改变原随机数在存储空间中的顺序）。3.源代码与运行结果#includestdio.h#includestdlib.h#includetime.h/*1_1产生1000个0至999间的随机整数，并以产生的次序存入一个数据文件(1_1.txt)中。*/main() FILE *fo=fopen(1_1.txt,w); int i,j; srand(unsigned)time(0); for (i=0;i=999;i+) fprintf(fo,%dn,rand()%1000); fclose(fo); printf(1000个随机数已输出至目录下1_1.txt文件n); system(pause);输出文件1_1.txt如下：（因输出文本长度缘故，此处只截了一幅图）#includestdio.h#includestdlib.h#includetime.h/*1_2从数据文件(1_1.txt)中读取数据，进行插入排序，然后屏幕输出。再依序删除。 1_3以N=100及N=400分别运行2的程序，并比较它们的运行时间。*/#define N 1000main() int aN=0; int i,j,m,w,num=0; FILE *fi=fopen(1_1.txt,r); clock_t start,finish; double duration;/Part 1 ： start=clock(); m=0; fscanf(fi,%d,num); a0=num; w=m; for (j=1;j=N-1;j+) w=m; fscanf(fi,%d,num); while (awnum)(w=0) w-; w+; for(i=m;i=w;i-) ai+1=ai; aw=num; m+; finish=clock(); duration=(double)(finish - start)/CLOCKS_PER_SEC; printf(执行 %d 个数据插入操作完成！用时：%f 秒，得到线性表如下：n,m+1,duration); for (i=0;iN;i+) printf(%d ,ai); fclose(fi); /Part 2 : start=clock(); for (j=0;j=N-1;j+) w=0; fscanf(fi,%d,num); while (awnum) w+; for(i=m;im;i+) ai=ai+1; am=0; m-; finish=clock(); duration=(double)(finish - start)/CLOCKS_PER_SEC; printf(nn删除操作完成！用时：%f 秒，得到线性表如下：n,duration); for (i=0;iN;i+) printf(%d ,ai); printf(n); fclose(fi); system(pause);程序运行输出结果如下：（因输出文本长度缘故，此处只截了两幅图）#includestdio.h#includestdlib.h/*1_4编写一个程序，用插入排序依次将1_1.txt中的1000个随机整数链接成有序链表（不改变原随机数在存储空间中的顺序）*/#define N 1000main()struct dataint num;struct data *next; ; struct data *n, *head, *temp;FILE *fi=fopen(1_1.txt,rt);int i,a=0;n=(struct data*)malloc(sizeof(struct data); n-next=NULL;fscanf(fi,%d,a);n-num=a;head=n;for (i=1;i=N-1;i+)n=(struct data*)malloc(sizeof(struct data);n-next=NULL;fscanf(fi,%d,a);n-num=a;temp=head;if (n-num)=(temp-num) / n为目前最小值n-next=temp;head=n; elsewhile ( (temp-next)!=NULL) (n-num) (temp-next)-num) ) temp=temp-next;if (temp-next=NULL) temp-next=n; / n为目前最大值else / n插入链表n-next=temp-next;temp-next=n; printf(插入排序完成n); printf(数据最小元素：%dn,head-num); printf(完整数据输出：n); temp=head; while (temp-next!=NULL) printf(%d ,temp-num); temp=temp-next; fclose(fi); system(pause); 程序运行输出结果如下：（因输出文本长度缘故，此处只截了一幅图）4.实验总结通过本次试验，我熟练掌握了线性表在顺序分配下的插入与删除运算，还有链表的存储结构、插入排序的方法，并且学习了产生随机数、文件数据输入输出、取得当前系统时间的方法。 srand函数用来将系统随机种子设定为当前时间（强制转化为unsigned），否则得到的伪随机数每次都相同，而rand()%1000则用来产生1-999的伪随机数。 在添加time.h库函数后，可以使用clock_t类型变量和clock()函数获取当前时间，从而进行程序运行时间计算（但精度貌似较低）。到每过千分之一秒，clock（）函数的返回值就会增加1，而常量CLOCKS_PER_SEC，它用来表示一秒钟有多少个时钟计时单元，故duration=(double)(finish - start)/CLOCKS_PER_SEC