实验报告
实验名称 线性表的插入与删除
班 级 学 号 姓 名 成 绩
1
实验概述： 【实验目的及要求】 掌握线性表在顺序分配下的插入与删除运算；掌握线性表的链式存储结构；掌握插入排序的方法；并掌握一种产生随机数的方法 【实验原理】 1、产生随机数的方法很多，在本实验中我才用了老师介绍的方法：设m=2，初值y0=0，则递推公式 yi=mod(2053 yi-1+13849，m) 产生0至65535之间的随机整数。如要产生0至999之间的随机整数，只需做运算 xi=INT(1000yi/m) 其中mod（*） 是模运算，INT（*）是取整函数。 产生随机数表 2、在本实验中线性表是动态增长的。插入一个新元素后，为了使线性表仍保持有序，必须要找到新元素应插入的位置。实际上这是一个插入排序的问题。 3. 线性链表的插入排序原理为定义一个二列数组A(1:1000，1:2)，其中A(i,1)(i=1,2,…,1000)依随机数产生的顺序存放1000个数据，A(i,2)(i=1,2,…,1000)为链接指针，将1000个随机数链接成有序链表。 16【实验环境】（使用的软硬件） 本次实验采用Microsoft Visual Studio C++软件进行编程，整个程序使用C语言程序设计编写。 实验内容： 【实验方案设计】 1、产生1000个0至999间的随机整数，并以产生的次序存入一个数据文件中。 2、编制一个程序，依次实现以下功能： （1）定义一个有序（非递减）线性表，其最大容量为1000，初始时为空。 （2）从由1产生的数据文件中依次取前N个随机整数，陆续插入到此线性表中，并要求在每次插入后保持线性表的有序性。最后将此有序线性表打印输出。 （3）在由（2）产生的线性表中，依在1中产生的次序逐个将元素删除，直至表空为止。 3、以N=100及N=400分别运行2的程序，并比较它们的运行时间。 4、编写一个程序，用插入排序依次将1中产生的1000个随机整数链接成有序链表（不改变原随机数在存储空间中的顺序）。 【实验过程】（实验步骤、记录、数据、分析） 实验步骤：1.事先编制好实验内容中1、2、4的程序（可参考本实验中的方法说明），并调试通过。 2.运行1的程序，生成1000个0至999之间的随机整数的数据文件，并打印输出此数据文件。 3.以N=100运行2的程序，并记下运行时间。 4.以N=400运行2的程序，并记下运行时间。 5.运行4的程序。 6.整理程序清单和运行结果，写出实验报告。 记录： 产生随机数
2
#include #include main() {long int x[1000];long int y[2000];long int m;int i;FILE *fp; m=pow(2,16); y[0]=0; for(i=0;i<1000;i++) { y[i+1]=(2053*y[i]+13849)%m; x[i]=int(1000*y[i+1]/m); printf(\"%ld \fp=fopen(\"wlxw\for(i=0;i<1000;i++) {fprintf(fp,\"%d\\n\fclose(fp); return 0; } 线性表: #include #include main() {FILE *fp;int i;long int a[1000];int n=0; int N;int j;int b; printf(\"please input a number for length\\n\" ); scanf(\"%d\ fp=fopen(\"wlxw\for(i=0;i0&a[j]>b;j--) {a[j+1]=a[j];} a[j+1]=b; } n=n+1; } fclose(fp); for(i=1;i<=N;i++) printf(\"%d \ return 0; } 插入与删除：#include #include3
main() {FILE *fp;int i;long int a[1000];int n=0; int N;int j;int b; int d;int k;int t; fp=fopen(\"wlxw\ printf(\"please input a number for length\\n\" ); scanf(\"%d\for(i=0;i0&a[j]>b;j--) {a[j+1]=a[j];} a[j+1]=b; } n=n+1; } for(i=1;i<=N;i++) printf(\"%d \ fclose(fp); for(i=0;;i++) { if(n==0) { printf(\"overflow\");break; } else { printf(\"input the number you want to delete\"); scanf(\"%d\ for(j=1;j<=n&a[j]!=d;j++) {} if(j-1==n) printf(\"not this element\\n\"); else { for(k=j;k #include main() {FILE *fp;int i;int A[2000][3];int k; int N; int b; int h; int j; int temp;int ji; fp=fopen(\"wlxw\printf(\"input a number\");4
scanf(\"%d\fscanf(fp,\"%d\for(i=2;i<=N;i++) { fscanf(fp,\"%d\ if( A[h][1]>=b ) { A[i][2]=h;h=i;} else { for(k=h,j=0;A[k][2]!=0&A[A[k][2]][1]A[i][1]) {temp=A[i][1];ji=i;} } for(i=1;i<=N;i++) { printf(\"%d \ ji=A[ji][2];} return 0; } 结果记录 随机数表（部分） 791 785 952 971 86 670 210 253 328 72 916 663 739 374 5 249 658 562 360 503 520 886 665 726 530 567 906 225 1 837 530 543 166 354 147 544 538 617 181 510 37 753 5 101 327 315 425 993 631 265 650 58 51 655 792 359 5 488 169 878 48 102 972 68 335 402 92 594 933 629 918 950 952 796 710 240 376 828 616 650 687 878 69 627 360 175 525 884 185 378 731 283 465 467 177 388 397 6 227 551 631 598 288 847 29 768 482 32 766 327 1 511 301 660 426 682 182 213 932 118 556 844 96 262 694 3 68 673 200 551 572 427 739 334 67 58 466 821 917 342 129 0 275 951 194 117 950 611 997 286 673 953 423 252 177 225 742 904 653 509 675 830 5 651 781 4 786 849 219 193 810 287 674 848 426 766 6 338 787 218 212 162 817 875 943 208 473 826 28 471 196 397 836 952 220 236 702 91 61 84 652 34 365 233 200 115 445 498 625 996 998 553 469 524 188 115 696 909 234 811 387 291 536 754 617 630 146 774 191 811 752 31 3 581 540 463 583 351 49 940 694 19 727 590 340 972 23 316 674 300 625 503 244 818 768 916 8 330 859 281 23 36 476 544 129 155 210 675 455 555 370 803 767 241 204 382 140 28 809 212 622 241 728 975 434 94 900 470 841 931 966 184 8 653 928 9 324 822 331 987 361 972 794 879 652 755 238 731 602 454 788 782 367 675 45 553 379 570 194 581 232 5695
485 494 734 1 556 951 345 905 112 933 430 268 623 546 239 902 226 28 45 102 614 758 817 9 487 977 84 286 4 3 132 290 186 1 83 558 390 141 308 639 342 793 208 851 76 929 996 938 976 904 33 406 525 788 802 554 723 740 800 862 880 68 223 227 921 804 40 878 875 985 251 176 5 935 9 556 284 241 653 371 56 751 216 883 178 103 9 638 668 749 369 340 377 196 935 427 628 245 965 996 712 929 126 750 231 808 158 460 965 438 845 455 105 39 994 635 2 182 269 327 654 162 375 170 72 722 621 190 161 308 969 221 512 992 299 517 721 778 338 559 924 232 630 533 520 318 854 12 742 921 652 315 929 219 491 558 140 399 874 397 287 256 743 109 138 116 558 878 990 961 743 933 43 250 149 28 279 63 527 779 548 972 878 878 661 911 303 793 508 227 【结论】（结果） 经实验发现：产生随机数表的实验比较成功，成功的产生了1000个随机数表。 在进行线性表的实验时由于对C语言很多知识不够熟悉，在实验过程中遇到一些困难。进运行程序我们发现在排序插入时比较成功但在有序删除时出现一些问题，文件无法打开，后来在老师和同学的帮助下及时解决。 对最后一个实验内容我们在课后进行，虽然经过多次努力写出部分程序但结果不是太好，没能达到要求的效果。 【小结】 此次实验中第一二个实验做得比较顺利成功的产生了随机数表并进行了有序（非降序）排列输入及从线性表中有序删除。在做实验过程中发现对C语言中很多知识掌握的还不够熟练特别是有关文件的打开等各种方法，还需要复习。同时通过对比其他同学我发现我们的程序比较繁琐很容易出错我总结认为这主要是我掌握的方法技巧比较单一，对C语言意外的编程语言不了解，使得我只能选择有限的几种方法编程。 总之第一次软件技术基础的实验课让我认识到我的不足给我以后的学习指出了方向。我将在以后的学习中复习以前的知识、自学还没掌握的争取以后的实验能更好的完成。 指导教师评语及成绩： 成绩： 指导教师签名： 批阅日期： 6
7
