线性表的顺序表示和实现

1、数学与计算科学学院实 验 报 告实验项目名称 线性表的顺序表示和实现所属课程名称 数据结构 实 验 类 型 验证型 实 验 日 期 2013.10.17 班 级 信计1201 学 号 201253100109 姓 名 成 绩 一、实验概述：【实验目的】一、了解线性表的逻辑结构特征：总存在第一个和最后一个元素；除第一个元素以外，每个元素总存在唯一一个直接前驱元素；除最后一个元素以外，每个元素总有唯一一个直接后继元素。二、掌握线性表的基本操作在顺序存储结构上的实现【实验原理】1、顺序表的特点：逻辑上相邻物理上相邻；是一种随机存储结构，其存储位置可以用一个简单、直观的公式表示。2、线性表的动态分配顺

2、序存储结构：#define LIST_INIT_SIZE 6 /线性表存储空间的初始分配量#define LISTINCREMENT 2 /线性表存储空间的分配增量Typedef structElemTYpe *elem; /存储空间基址Int length; /当前长度Int listsize; /当前分配的存储容量SqList;【实验环境】VC + 6.0二、实验内容：【实验方案】编写主函数，调用顺序表的初始化建空表、插入和删除算法，调制运行，得出结果。【实验过程】（实验步骤、记录、数据、分析）1、输入顺序表的初始化建空表、插入、删除算法以及主函数：/线性表的动态分配顺序存储结构#defi

3、ne LIST_INIT_SIZE 6/线性表存储空间的初始分配量#define LISTINCREMENT 2/线性表存储空间的分配增量typedef structElemType *elem;/存储空间基址int length;/当前长度int listsize;/当前分配的存储容量SqList;Status InitList_Sq(SqList &L)/构造一个空的线性表L。/ InitList_SqStatus ListInsert_Sq(SqList &L,int i,ElemType e)/在顺序线性表L中第i个位置之前插入新的元素e/ ListInsert_SqS

4、tatus ListDelete_Sq(SqList &L,int i,ElemType &e)/在线性顺序表L中删除第i个元素，并用e返回其值/ ListDelete_Sqvoid main()SqList L;int i; InitList_Sq(L); for(i=0;i<List_INIT_SIZE,i+)scanf("%d",&L.elemi);L.length+;for(i=0;i<L.length;i+)printf("%d ",L.elemi); printf("n"); ElemT

5、ype e; scanf("%d%d",&i,&e); ListInsert_Sq(L,i,e);for(i=0;i<L.length;i+)printf("%d",L.elemi);printf("n"); scanf("%d",&i); ListDelete_Sq(L,i,e); for(i=0;i<L.length;i+)printf("%d ",L.elem(i);2、调试：发现在下列代码中出现错误：Status ListInsert_Sq(SqLis

6、t &L,int i,ElemType e)ListLength_Sq(L)+1if(i<1|i>L.length+1)return ERROR; 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.elemi-1); for(p=&(L.elem

7、L.length-1);p>=q;-p) *(p+1)=*p; *q=e; +L.length; return OK;/ ListInsert_Sq出现的错误为：error C2065: 'newbase' : undeclared identifier error C2065: 'q' : undeclared identifier error C2065: 'p' : undeclared identifier即newbase,q,p无定义，需要在Status ListInsert_Sq(SqList &L,int i,Elem

8、Type e) 给它们进行定义为int *newbase;int *q;int *p;修改之后，继续进行调试，发现出现的错误跟上述错误类似，在使用它们之前忘记定义，修改的方法就是在前面给它们先定义后使用。另外，在调试过程中，还有一些小错误，如：在for循环语句中，少了一个“)”及“；”等，依次修改过来。3.保存，运行：在运行框中依次输入随意六个数字，每个数字间用空格分开，按回车，则实现了顺序表的建立；再输入两个数字，数字用空格隔开，前一数字（应不大于六）表示在第几个元素前插入，后一个数字表示插入的元素，按回车，由此实现了顺序表的插入算法；再输入一个数字（应不大于七）表示把第几个元素删除，再回车

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

10、E 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 6#define LISTINCREMENT 2typedef structElemType *elem;int length;int listsize;SqList;Status InitList_Sq(SqList &L)/构造一个空的线性表L。L.elem=(ElemType *)mall

11、oc(LIST_INIT_SIZE*sizeof(ElemType);if(! L.elem)exit(OVERFLOW); /存储分配失败L.length=0; /空表长度为0L.listsize=LIST_INIT_SIZE; /初始存储容量return OK;/ InitList_SqStatus ListInsert_Sq(SqList &L,int i,ElemType e)/在顺序线性表L中第i个位置之前插入新的元素e,/i的合法值为1iListLength_Sq(L)+1int *newbase;int *p;int *q;if(i<1|i>L.length+

12、1) return ERROR; /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.elemi-1); /q为插入位置for(p=&(L.elemL.length-1);p>=q;-

13、p) *(p+1)=*p;/插入位置及之后的元素右移*q=e; /插入e+L.length; /表长增1return OK;/ ListInsert_SqStatus ListDelete_Sq(SqList &L,int i,ElemType &e)/在线性顺序表L中删除第i个元素，并用e返回其值/i的合法值为1iListLength_Sq(L)int *p;int *q;if(i<1|i>L.length+1)return ERROR; /i值不合法p=&(L.elemi-1); /p为被删除元素的位置e=*p; /被删除元素的值赋给eq=L.elem+

14、L.length-1; /表尾元素的位置for(+p;p<=q;+p)*(p-1)=*p; /被删除元素之后的元素左移-L.length; /表长减1return OK;/ ListDelete_Sqvoid main()SqList L;int i;InitList_Sq(L);for(i=0;i<LIST_INIT_SIZE;i+)scanf("%d",&L.elemi);L.length+;for(i=0;i<L.length;i+)printf("%d ",L.elemi);printf("n");E

15、lemType e;scanf("%d%d",&i,&e);ListInsert_Sq(L,i,e);for(i=0;i<L.length;i+)printf("%d",L.elemi);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实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。对于验证性实验，要写明依据何种原理、操