计算机软件基础 上机实验报告（一）
XXXXXX 班 XXX
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);
