山东理工大学实验报告纸(版).docVIP

山东理工大学实验报告纸 第 1 页 姓名：蔡鹏飞 计算机 院 11级 2班同组者 成 绩_________ 室温： 气压： 课程名称：数据结构 教师签字_________ 实验项目 编号( 1 ) 线性表的顺序表示和实现 指导教师 鞠传香 实 验 目 的 （1）掌握线性表的顺序存储结构； （2）验证顺序表及其基本操作的实现； （3）掌握数据结构及算法的程序实现的基本方法。 实验仪器（编号）材料、工具 计算机 visual C++6.0开发环境 （原理概述） 线性表是最常用的且最简单的一种数据结构。对线性表的主要操作有插入、删除、查找。 线性表的插入操作是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素，就是要长度为n的线性表（a1,..ai-1,ai,…an）变成长度为n+1的线性表（a1,..ai-1,b,ai,…an）。 线性表的删除操作是使长度为n的线性表（a1,..ai-1,ai,ai+1…an）变成长度为n-1的线性表（a1,..ai-1,ai+1…an） （实验内容步骤） 主要代码Status ListInsert_Sq(SqList L,int i,ElemType e) //插入 { int *q,*p; ElemType *newbase; if(i1 || iL.length+1) return ERROR; if(L.length=L.listsize) { newbase=new ElemType[L.listsize+LISTINCREMENT]; if(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; } q=(L.elem[i-1]); for (p=(L.elem[L.length-1]);p=q;--p) {*(p+1)=*p;} *q=e; ++L.length; return OK; }Status ListDelete_Sq(SqList L,int i,ElemType e) //删除 { ElemType *p, *q; if(i1 || iL.length) return ERROR; p=(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for(++p;p=q;++p) *(p-1)=*p; --L.length; return OK;} （数据记录表及处理） 运行程序时如下图选择插入的操作，然后选择需要插入的位置，最后从键盘输入需要插入的数据元素，其结果如下： 运行程序时如下图选择删除的操作，然后选择需要删除的位置，按回车键，其结果如下： （实验结论及问题讨论） 对于线性表在执行插入操作时，数据元素ai-1和ai之间的逻辑关系发生了变化。在线性表的顺序存储结构中，由于逻辑上相邻的数据元素在物理位置上也是相邻的，因此，除非i=n+1;，否则必须移动元素才能反映这个逻辑关系的变化。 一般情况下，在第i个（1=i=n）个元素之前插入一个元素时，需要从第n至第i（共n-1+1）个元素向后移动一个位置。 线性表的删除操作是使长度为n的线性表 （a1,..ai-1,ai,ai+1…an） 变成长度为n-1的线性表 （a1,..ai-1,ai+1…an） 数据元素ai-1,ai和ai+1之间的逻辑关系发生关系，为了在存储结构上反映这个变化，同样需要移动元素。 一般情况下，删除第i个（1=i=n）个元素时需要从第i+1至第n（共n-1）个元素依次向前移动一个位置。