计算机软件基础上机实验报告（一）
XXXXXX班XXX 10021189
1.实验目的
掌握线性表在顺序分配下的插入与删除运算；掌握线性表的链式存储结构；掌握插入排序的方法；并掌握一种产生随机数的方法。
2.实验容
1．产生1000个0至999间的随机整数，并以产生的次序存入一个数据文件中。
2．编制一个程序，依次实现以下功能：
(1) 定义一个有序（非递减）线性表，其最大容量为1000，初始时为空。
(2) 从由1产生的数据文件中依次取前N个随机整数，陆续插入到此线性表中，并要求在每次插入后保持线性表的有序性。
最后将此有序线性表打印输出。
(3) 在由（2）产生的线性表中，依在1中产生的次序逐个将元素删除，直至表空为止。
3．以N=100及N=400分别运行2的程序，并比较它们的运行时间。
4．编写一个程序，用插入排序依次将1中产生的1000个随机整数成有序链表（不改变原随机数在存储空间中的顺序）。
3.源代码与运行结果
#include<stdio.h>
#include<stdlib.h>
#include<time.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,"%d\n",rand()%1000);
fclose(fo);
printf("1000个随机数已输出至目录下1_1.txt文件\n");
system("pause");
}
输出文件1_1.txt如下：（因输出文本长度缘故，此处只截了一幅图）
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
/**
1_2
从数据文件(1_1.txt)中读取数据，进行插入排序，然后屏幕输出。
再依序删除。
1_3
以N=100及N=400分别运行2的程序，并比较它们的运行时间。
**/
#define N 1000
main()
{
int a[N]={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);
a[0]=num;
w=m;
for (j=1;j<=N-1;j++)
{
w=m;
fscanf(fi,"%d",&num);
while ((a[w]>num)&&(w>=0)) w--;
w++;
for(i=m;i>=w;i--) a[i+1]=a[i];
a[w]=num;
m++;
}
finish=clock();
duration=(double)(finish - start)/CLOCKS_PER_SEC;
printf("执行%d 个数据插入操作完成！用时：%f 秒，得到线性表如下：\n",m+1,duration);
for (i=0;i<N;i++) printf("%d ",a[i]);
fclose(fi);
//Part 2 :
start=clock();
for (j=0;j<=N-1;j++)
{
w=0;
fscanf(fi,"%d",&num);
while (a[w]<num) w++;
for(i=m;i<m;i++) a[i]=a[i+1];
a[m]=0;
m--;
}
finish=clock();
duration=(double)(finish - start)/CLOCKS_PER_SEC;
printf("\n\n删除操作完成！用时：%f 秒，得到线性表如下：\n",duration);
for (i=0;i<N;i++) printf("%d ",a[i]);
printf("\n");
fclose(fi);
system("pause");
}
程序运行输出结果如下：（因输出文本长度缘故，此处只截了两幅图）
#include<stdio.h>
#include<stdlib.h>
/**
1_4
编写一个程序，用插入排序依次将1_1.txt中的1000个随机整数成有序链表
（不改变原随机数在存储空间中的顺序）
**/
#define N 1000
main()
{
struct data
{
int 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;
}
else
{
while ( ((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("数据最小元素：%d\n",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即可得到程序运行的时间（秒）。
➢文件读取输出可以通过以下语句简单完成：FILE *fi=fopen("fi.txt","r");
FILE *fo=fopen("fo.txt","w");
fscanf(fi,"%d",int);
fprintf(fo,"文件输出\n");
fclose(fi);
fclose(fo);。