北航计算计软件基础实验一报告答案北航计算计软件基础实验一报告答案.doc

实验报告 答案 实验名称 实验一 线性表的插入与删除 班 级 学 号 姓 名 成 绩 实验概述： 【实验目的及要求】 掌握线性表在顺序分配下的插入与删除运算；掌握线性表的链式存储结构；掌握插入排序的方法；并掌握一种产生随机数的方法。 【实验原理】 1. 产生1000个0至999间的随机整数，并以产生的次序存入一个数据文件中。 2. 编制一个程序，依次实现以下功能： 3. 定义一个有序（非递减）线性表，其最大容量为1000，初始时为空。 4. 从由1产生的数据文件中依次取前N个随机整数，陆续插入到此线性表中，并要求在每次插入后保持线性表的有序性。最后将此有序线性表打印输出。 5. 在由（2）产生的线性表中，依在1中产生的次序逐个将元素删除，直至表空为止。 6. 以N=100及N=400分别运行2的程序，并比较它们的运行时间。 7. 编写一个程序，用插入排序依次将1中产生的1000个随机整数链接成有序链表 （不改变原随机数在存储空间中的顺序）。 【实验环境】（使用的软硬件） VC++6.0编译平台和C++语言。 实验内容： 【实验方案设计】 1. 用rand()函数产生1000个随时间变化的由从0至999伪随机整数，并用fprintf()函数将其按照次序存入一个txt格式的数据文件“./stlist/random_num.txt”中。 2. 建立一个容量为1000的数组。利用插入排序法将生成的前N个数有序排列到数组中。并输出此数据文件“./dstlist/acendlist.txt”。 3. 设计查找删除函数，实现依次删除前M个数据的功能，将删除后的数据输出到数据文件“./dstlist/acendlistAFD.txt”中。 4. 以N=100及N=400分别执行2的程序，用clock（）函数粗略地计算并比较它们的运行时间。 5. 构造一个链表，用插入排序依次将1中产生的1000个随机整数链接成有序链表,并输出至“”文件以便检验。 6. 整理程序清单和运行结果，写出实验报告。 【实验过程】（实验步骤、记录、数据、分析） 1.随机数函数：包含在stdlib.h中 int randNum (int min, int max) {int num; num = rand() % max + min; return num;} 调用该函数之前在主函数中加入以下语句： Srand((long int)time(0)); 2. 顺序表插入算法 int orderSort (int* list, int N, FILE* fp) {for(int i=0; i N; i++) { if(fscanf(fp, %d, list[i]) != 1) { printf(无法读取第%d个数据\n, i + 1); return -1; } j = i - 1; if(j != 0) // 当线性表有一个元素时不执行排序 {while(j = 0){ if(list[i] list[j]) j--; else break;} orderInsert(list, i, j + 2, list[i]);} }} 整体思路就是第一步先找到要插入的位置，第二步再把要插入的元素插入进去。 oderInsert函数原型如下： int orderInsert(int* list, int n, int pos, int elem) { if( pos n+1 || pos 1 ) { printf(插入数据的位置有误\n); return -1; } int i = n-1; while(i + 1 = pos) { list[i + 1] = list[i]; i--; } // i = pos-2时跳出 list[i+1] = elem; return 1; }