北航计软实验报告一
————————————————————————————————作者: ————————————————————————————————日期：
计算机软件基础上机实验报告（一)
ＸXXXＸX班XXX
１.实验目的
掌握线性表在顺序分配下的插入与删除运算；掌握线性表的链式存储结构;掌握插入排序的方法;并掌握一种产生随机数的方法。
2.实验内容
1．产生１000个0至999间的随机整数，并以产生的次序存入一个数据文件中。
2．编制一个程序,依次实现以下功能：
（1)ﻩ定义一个有序(非递减）线性表,其最大容量为１0０0,初始时为空。
(2)ﻩ从由１产生的数据文件中依次取前N个随机整数，陆续插入到此线性表中，并要求在每次插入后保持线性表的有序性。
最后将此有序线性表打印输出。
(３)ﻩ在由（2）产生的线性表中，依在1中产生的次序逐个将元素删除，直至表空为止。
3. 以N＝１0０及N＝400分别运行2的程序,并比较它们的运行时间。
４. 编写一个程序，用插入排序依次将1中产生的１000个随机整数链接成有序链表(不改变原随机数在存储空间中的顺序）。
３.源代码与运行结果
#incｌｕdｅ<ｓｔdｉo.h>
#ｉnclude<ｓｔｄliｂ.h＞
＃include<time.h>
/＊＊
1_1
产生1000个０至９９９间的随机整数,并以产生的次序存入一个数据文件（1_1．tｘt)中。
**/
main()
{
ＦILE *fo＝fopｅn（"1_1.txｔ","w＂);
int i,j;
srand(（ｕnsiｇned）tiｍe（0)）;
foｒ（i＝0;ｉ<=99９;i+＋）fprｉntｆ（ｆｏ,＂%d＼n"，rand()%10０0);
fclｏｓｅ(fo);
ｐriｎｔf("１00０个随机数已输出至目录下1＿1．tｘt文件\n＂);
system("pause"）;
}
输出文件1_１．ｔxｔ如下:（因输出文本长度缘故,此处只截了一幅图)
#inｃludｅ<stdio.ｈ＞
#ｉnclude＜stdｌib.h>
＃iｎcｌｕde＜tｉme．ｈ>
/**
１＿2
从数据文件（1_1．txt)中读取数据，进行插入排序，然后屏幕输出。
再依序删除。
1_3
以Ｎ＝1０0及N=400分别运行２的程序，并比较它们的运行时间。
*＊／
#dｅｆine N １0０0
maiｎ()
{
int a[Ｎ］={0}；
int i，ｊ，ｍ,w,num=0;
FＩＬE *fi＝ｆopen(＂１_1.txt"，"r")；
clock＿t start，fiｎish;
dｏublｅdｕｒation;
/／Part 1 ：
ｓtarｔ=cｌock()；
m=0;
fｓｃａnｆ（fi，"%d",&num）；
a［０]=num；
w=m;
for (ｊ=１;j<＝N-1;j＋+）
{
w=ｍ；
fscａnf(fi，＂%d",&ｎum）;
whiｌe ((ａ[w]>num)&＆（w＞＝0)）w-－；
ｗ+＋；
ｆｏr(i＝m；i>＝w;i--）a[ｉ+1]＝ａ[ｉ];
a[w］=num;
ｍ++;
}
fｉnish=clock();
duｒation=(doubｌe)(fｉｎiｓh －sｔaｒt)／CＬOＣKＳ_PER＿ＳEＣ；
priｎtf("执行%d 个数据插入操作完成！用时：%f 秒,得到线性表如下：＼n"，m+1，durａtion);
ｆoｒ（i=0;i<Ｎ；ｉ++) ｐrｉｎｔf("%ｄ"，a[ｉ]）;
fｃｌose(fi);
／/Part ２:
stａrｔ=ｃlｏck();
for （j=0;j<=N-1;ｊ++)
{
w=0;
fscａｎｆ（fｉ,＂%d"，＆num);
wｈile （ａ［w]<num) w++；
ｆor(i=ｍ;i<ｍ;ｉ++) a[i］=a[i＋1］；
ａ[m]＝0;
ｍ--；
}
fｉｎisｈ=clock();
dｕｒａtion=（dｏuble）(ｆinｉsh －staｒｔ)/CLOCKS_PEＲ＿ＳEC;
pｒintf("＼n\n删除操作完成！用时：％f秒，得到线性表如下:\n＂，duration);
for (ｉ=0；i<N;ｉ+＋) priｎtf("％d ",a[i］);
printf("\n")；
fcloｓe(fi);
ｓysｔeｍ("pause"）;
}
程序运行输出结果如下:(因输出文本长度缘故,此处只截了两幅图)
#include<stdio.h＞
#inｃｌuｄｅ<ｓtdlｉb.h>
/＊*
1_4
编写一个程序,用插入排序依次将1_１.txt中的１00０个随机整数链接成有序链表
(不改变原随机数在存储空间中的顺序)
**/
#dｅｆiｎｅN 10０0
mａｉn（)
{
stｒuct data
ﻩ{
ﻩiｎt ｎum;
ﻩｓtruct data *neｘt；
}；
struct datａ＊n,*ｈeａｄ，*temp;
ﻩＦILＥ*fi＝fopen("1_1.txt","ｒt"）;
ﻩiｎt i,a=0;
n=（stｒuct data*)malloc(ｓiｚｅoｆ（strｕcｔdａta））;
n－>next=NＵLL;
ｆscanf(ｆi,"%d",＆a)；
ﻩn->num=a;
ﻩhead=n;
fｏr (i=1;i<=N-1;i++）
｛
ﻩﻩn=(ｓtｒuｃt ｄata*)malｌoc(sizｅｏf(ｓtructｄａta));n－>next=ＮＵＬL;
ﻩfsｃanｆ(fi,"％d",&a）;
ﻩﻩn－＞ｎuｍ=a;
ﻩteｍｐ＝hｅａd；
ｉf （(n->nuｍ)＜=(teｍp->num)) // n为目前最小值
ﻩ｛
ｎ-＞ｎexｔ=temp;
ﻩﻩｈead=n；
ﻩﻩ}
ﻩﻩelse
ﻩ｛
ﻩﻩwhile （((temp-＞ｎext)!=NULL）&＆（(n->num) > （(ｔemp->next)->nｕm)) ) ﻩteｍｐ＝teｍｐ->neｘt;
ﻩﻩﻩｉf （temｐ-＞next==NＵＬL）ｔemｐ－>ｎext=ｎ; // n为目前最大值ﻩﻩelse //n插入链表
ﻩﻩ{
ｎ-＞nｅxt=ｔemｐ->nｅxt;
ﻩﻩﻩｔemp->next=ｎ;
ﻩﻩ}
ﻩ}
}
prｉntｆ（＂插入排序完成\n");
printｆ("数据最小元素:%ｄ＼n"，heaｄ->num);
priｎtｆ("完整数据输出:\ｎ＂);
teｍp=heaｄ;
while (tｅmp-＞neｘｔ！=NＵLL）{priｎtf("％d ＂,ｔemｐ->nｕｍ);temp=tｅｍｐ->ｎｅxt;}
ｆｃloｓｅ(fｉ);
ｓyｓtem("pause");
}
程序运行输出结果如下：（因输出文本长度缘故，此处只截了一幅图）
４.实验总结
通过本次试验，我熟练掌握了线性表在顺序分配下的插入与删除运算，还有链表的存储结构、插入排序的方法,并且学习了产生随机数、文件数据输入输出、取得当前系统时间的方法。
➢sｒand函数用来将系统随机种子设定为当前时间（强制转化为unsigned）,否则得到的伪随机数每次都相同，而ranｄ()％1000则用来产生1-999的伪随机数。
➢在添加ｔimｅ.h库函数后，可以使用cｌock_ｔ类型变量和cｌｏｃk（)函数获取当前时间，从而进行程序运行时间计算(但精度貌似较低)。
到每过千分之一秒，clock（)函数的返回值就会增加１，而常量CLOCKS_ＰER_SEC,它用来表示一秒钟有多少个时钟计时单元,故ｄuration=(doubｌｅ）(fiｎish－s ｔart）/ＣLＯCKS_PEＲ＿SEC即可得到程序运行的时间(秒)。
➢文件读取输出可以通过以下语句简单完成:ＦILＥ*fｉ=fｏpeｎ（"fi．ｔxt＂,"ｒ"）;
ＦILＥ*fo=foｐｅn（"fｏ.txt",＂ｗ");
fscanf(fi，"%d",int)；
fｐｒintf(fo,＂文件输出＼ｎ");
fcloｓe(fi);
fｃloｓe(fｏ);。