线性表的顺序表示和实现

数学与计算科学学院实验报告实验项目名称线性表的顺序表示和实现所属课程名称 数据结构 实验类型 验证型 实验日期 2013.10.17 班 级 信计1201 学 号 201253100109姓 名 成 绩 一、实验概述：【实验目的】一、 了解线性表的逻辑结构特征：总存在第一个和最后一个元素；除第一个元素以外，每个元素总存在唯一一个直接前驱元素；除最后一个元素以外，每个元素总有唯一一个直接后继元素。二、 掌握线性表的基本操作在顺序存储结构上的实现【实验原理】1、 顺序表的特点：逻辑上相邻物理上相邻；是一种随机存储结构，其存储位置可以用一个简单、直观的公式表示。2、 线性表的动态分配顺序存储结构：#defineLIST_INIT_SIZE6//线性表存储空间的初始分配量#defineLISTINCREMENT2 //线性表存储空间的分配增量Typedefstruet{ElemTYpe*elem; //存储空间基址Intlength; //当前长度Intlistsize; //当前分配的存储容量}SqList;【实验环境】VC++6.0二、实验内容：【实验方案】编写主函数，调用顺序表的初始化建空表、插入和删除算法，调制运行，得出结果。【实验过程】（实验步骤、记录、数据、分析）1、输入顺序表的初始化建空表、插入、删除算法以及主函数://线性表的动态分配顺序存储结构#defineLIST_INIT_SIZE6//线性表存储空间的初始分配量#defineLISTINCREMENT2//线性表存储空间的分配增量typedefstruet{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量}SqList;StatusInitList_Sq(SqList&L){//构造一个空的线性表L。}//InitList_SqStatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序线性表L中第i个位置之前插入新的元素e}//ListInsert_SqStatusListDelete_Sq(SqList&L,inti,ElemType&e){//在线性顺序表L中删除第i个元素，并用e返回其值}//ListDelete_Sqvoidmain(){SqListL;inti;InitList_Sq(L);for(i=0;i<List_INIT_SIZE,i++){seanf("%d"，&L.elem[i]);L.length++;}for(i=0;i<L.length;i++)printf("%d ",L.elem[i]);printf("\n");ElemTypee;seanf("%d%d",&i,&e);ListInsert_Sq(L,i,e);for(i=0;i<L.length;i++)printf("%d",L.elem[i]);printf("\n");seanf("%d"，&i);ListDelete_Sq(L,i,e);for(i=0;i<L.length;i++)printf("%d",L.elem(i);

}2、调试:发现在下列代码中出现错误:StatusListlnsert_Sq(SqList&L,inti,ElemTypee){ListLength_Sq(L)+lif(i<l||i>L.length+l)returnERROR;if(L.length>二L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem二newbase;L.listsize+二LISTINCREMENT;}q=&(L.elem[iT]);for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)二*p;*q二e;++L.length;returnOK;}//ListInsert_Sq:errorC2065:'newbase':undeclaredidentifiererrorC2065:'q':undeclaredidentifiererrorC2065:'p':undeclaredidentifiernewbaseStatusListInsert_Sq(SqList&L,inti,ElemTypee){newbaseStatusListInsert_Sq(SqList&L,inti,ElemTypee){它们进仃定乂为int*newbase;int*q;int*p;修改之后，继续进仃调试，发现出现的错误跟上述错误类似，在使用它们之前忘记定义，修改的方法就是在前面给它们先定义后使用。另外，在调试过程中，还有一些小错误，如：在for循环语句中，少了一个“）”及“；等，依次修改过来。保存，运行：在运行框中依次输入随意六个数字，每个数字间用空格分开，按回车，则实现了顺序表的建立；再输入两个数字，数字用空格隔开，前一数字（应不大于六）表示在第几个元素前插入，后一个数字表示插入的元素，按回车，由此实现了顺序表的插入算法；再输入一个数字（应不大于七）表示把第几个元素

删除，再回车，贝U实现了顺序表的删除算法，最终，完成了运行。【实验结论】（结果）【实验小结】（收获体会）在此次上机操作中，编写主函数和相关算法完成线性表的顺序表示和实现，慢慢地学会一些基本的调试，也加深了顺序表的创建，插入，删除算法的理解。三、指导教师评语及成绩:评语评语等级优良中及格不及格1.实验报告按时完成，字迹清楚,文字叙述流畅，逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细，记录完整，数据合理,分析透彻）4实验结论正确.成绩:指导教师签名:

批阅日期：附录1：源程序#include<stdio.h>#include<stdlib.h>#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;typedefintElemType;#defineLIST_INIT_SIZE6#defineLISTINCREMENT2typedefstruct{ElemType*elem;intlength;

intlistsize;}SqList;StatusInitList_Sq(SqList&L){//构造一个空的线性表L。L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW); //存储分配失败L.length=O; //空表长度为0L.listsize二LIST_INIT_SIZE;//初始存储容量returnOK;}//InitList_SqStatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序线性表L中第i个位置之前插入新的元素e,//i的合法值为lWiWListLength_Sq(L)+lint*newbase;int*p;int*q;if(i<l||i>L.length+1)returnERROR; //i值不合法if(L.length>二L.listsize){ //当前存储空间已满，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW); //存储分配失败L.elem二newbase; //新基址L.listsize+二LISTINCREMENT; //增加存储容量}q二&(L.elem[i-1]); //q为插入位置for(p=&(L.elem[L.lengthT]);p>二q;—p)*(p+1)二*p;//插入位置及之后的元素右移*q=e; //插入e++L.length; //表长增1returnOK;}//ListInsert_SqStatusListDelete_Sq(SqList&L,inti,ElemType&e){//在线性顺序表L中删除第i个元素，并用e返回其值//i的合法值为1WiWListLength_Sq(L)int*p;int*q;//i值不合法//i值不合法//p为被删除元素的位置//被删除元素的值赋给e//表尾元素的位置//被删除元素之后的元素e二*p;q二L.elem+L.lengthT;for(++p;p<=q;++p)*(p-1)二*p;左移//表长减1――L.length;//表长减1returnOK;}//ListDelete_Sqvoidmain(){SqListL;inti;InitList_Sq(L);for(i=O;i<LIST_INIT_SIZE;i++){scanf("%d"，&L.elem[i]);L.length++;}for(i=0;i<L.length;i++)printf("%d ",L.elem[i]);printf("\n");ElemTypee;scanf("%d%d",&i,&e);ListInsert_Sq(L,i,e);for(i=0;i<L.length;i++)printf("%d",L.elem[i]);printf("\n");scanf("%d"，&i);ListDelete_Sq(L,i,e);for(i=0;i<L.length;i++)printf("%d ",*(L.elem+i));printf("\n");}附录2：实验报告填写说明1．实验项目名称：要求与实验教学大纲一致。2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。3．实验原理：简要说明本实验项目所涉及的理论知识。4．实验环境：实验用的软、硬件环境。5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程对于验证性实验，要写明依据何种原理、操作方法进行实验，