实验报告实验名称线性表的插入与删除班级学号姓名成绩【实验过程】（实验步骤、记录、数据、分析）实验一：源代码：/*实验1:产生1000个0至999间的随机整数，并以产生的次序存入一个数据文件中。

*/#include<stdio.h>#include<stdlib.h>#include<math.h>int main(){long m = 65536, y = 0;int x, i;//定义一个文件类型的指针FILE *fp;//用fopen函数新建一个文件，失败则返回0if ((fp = fopen("D:\\data.txt", "w")) == NULL){fprintf(stderr, "Error opening file.");exit(0);}printf("The data has been output to D:\\data.txt!\n");printf("All data is as follows!\n\n");//递归创造1000个0~999之间的随机数for (i = 0; i<1000; i++){y = (2053 * y + 13849) % m;x = (int)(1000 * y / m);fprintf(fp, "%d\n", x);printf("%d:%d\t", i + 1, x);}//关闭文件fclose(fp);exit(1);}运行结果：实验二、实验三：源代码：/*实验2:编制一个程序，依次实现以下功能：1.定义一个有序非递减线性表,其最大容量为1000,初始时为空。

2.从由1产生的数据文件中依次取前N个随机整数陆续插入到此线性表中,并要求在每次插入后保持线性表的有序性。

最后将此有序线性表打印输出。

3.在由2产生的线性表中，依在1中产生的次序逐个将元素删除直至表空为止。

实验3:以N=100及N=400分别运行2的程序，并比较它们的运行时间。

*/#include<stdio.h>#include<stdlib.h>#include<time.h>#define N 1000void main(){//新建时钟变量，得到程序从开始运行到某时刻经过的时钟周期数clock_t start, finish;FILE *fp;int a[1000];int i, j, n, temp;double duration;//Part 1:创建一个有序线性表start = clock();if ((fp = fopen("D:\\data.txt", "r")) == NULL){fprintf(stderr, "Error opening file.");exit(0);}//判断插入顺序是否合理else if (n = N>1000){printf("Data overflow!Please try again!");exit(0);}//比较插入元素与有序表中元素位置并插入else for (n = 0; n<N; n++){fscanf(fp, "%d", &temp);if (n == 0)a[0] = temp;//将比a[i]大的数向后移动一格，将a[i]放入线性表else{for (i = n; (i>0) && (a[i - 1]>temp); i--)a[i] = a[i - 1];a[i] = temp;}}for (i = 0; i<n; i++)printf("%d\t", a[i]);fclose(fp);finish = clock();//计算程序运行时间duration = (double)(finish - start) / CLOCKS_PER_SEC;printf("\n\n");printf("A sorted linear list has been created!\n");printf("The length of it is %d.\n", n);printf("Time taken:%fs\n\n", duration);//Part 2:按创建顺序删除线性表start = clock();if ((fp = fopen("D:\\data.txt", "r")) == NULL){fprintf(stderr, "Error opening file.");exit(0);}//判断删除位置是否合理if (n == 0){printf("Data underflow!Please try again!");exit(0);}//在线性表中利用顺序查找法找到元素位置else for (; n>0; n--){fscanf(fp, "%d", &temp);for (i = 0; i<n&&a[i] != temp; i++);if (i >= n)printf("This element CANNOT be found!");//若要删除元素不是位于顺序表最后一位，则将后面的元素前移一位；若位于最后一位，直接令n--即可，不必再移动else if (i<n - 1)for (j = i; j<n; j++)a[j] = a[j + 1];else;}//打印清空后的顺序表实验二：（此图将原程序中for (; n>0; n--)改成了for (; n>20; n--)，即删除至剩20个数据的线性表，目的为验证删除一些元素后线性表仍保持有序）实验三：1.N=100t1=0.005000s t2=0.001000s 2.N=400t1=0.049000s t2=0.001000s 实验四：源代码：实验4:编写一个程序，用插入排序依次将1中产生的1000个随机整数链接成有序链表,不改变原随机数在存储空间中的顺序。

*/#include<stdio.h>#include<stdlib.h>#define N 1000int main(){FILE *fp;int a[N][2];int H, i, k, x;if ((fp = fopen("D:\\data.txt", "r")) == NULL){fprintf(stderr, "Error opening file.");exit(0);}//定义头节点位置H = 0;fscanf(fp, "%d", &x);a[0][0] = x;//定义链表结束标志a[0][1] = -1;//逐一插入元素并与原链表内元素比较以确定位置for (k = 1; k<N; k++){fscanf(fp, "%d", &x);a[k][0] = x;//在链表头结点插入元素if (a[k][0]<a[H][0]){a[k][1] = H;H = k;}//在链表某一位置插入一个元素else{i = H;while ((a[i][1] != -1) && (a[a[i][1]][0]<x))i = a[i][1];a[k][1] = a[i][1];a[i][1] = k;}printf("A linked list containing %d numbers has beencreated!\n", N);printf("Its head pointer is %d,its value is %d.\n", H, a[H][0]);printf("The data is as follows.\n\n");i = H;//按大小顺序打印链表do{printf("%d\t", a[i][0]);i = a[i][1];} while (a[i][1] != -1);exit(1);}运行结果：【结论】（结果）1.实验1中利用函数递归的方法得到随机数的方法是可行的，要得到(0,a)之间的随机数只需加x i=INT(a*y i/m)语句即可。

2.实验2中利用插入排序法可以成功将一组无序数据按从小到大顺序排好并放入线性表中，利用顺序查找法可以成功找到、删除任意元素。

第四个结果图说明删除一些元素后线性表顺序保持不变3. 实验3中N=100时插入时间t1=0.005000s，清空时间t2=0.001000s；N=400时插入时间t1=0.049000s，清空时间t2=0.001000s。

当表中已经有n个数时，再插入一个数时，若比较i次，则需要移动i次（1<= i <=n)。

假设他们的概率相等，则平均需要比较 (n+1) / 2次，移动 (n+1) / 2次。

即顺序表中已经有n个数的时候，再进行插入排序运算的算法复杂度为O(n)。

那么假设题目要求一共读取N个数，则程序平均要执行(N+1)*N/2，即算法的时间复杂度为O(n^2)。

同理，删除这N个数的算法的时间复杂度也为O(n^2)。

在此程序中N=400时插入时间约为N=100时的10倍，基本符合，误差是由于运行时电脑环境及计时误差引起的4.实验4中用二维数组模拟静态链表成功实现了数据的插入及排序功能【小结】在完成这份实验报告后，感慨良多。