实习报告一

班级:信息1102 姓名：贾孟涛 ======== 实习报告一 “顺序表类的定义”演示程序 ==================

（一）、程序的功能和特点

该程序不仅可以显示输出线性表，求出线性表的长度，还拥有对线性表的

元素进行添加、删除、修改以及查找操作；它还可以定位元素的前驱和后继，判断线性表是否为空表或为满表。

（二）、程序的算法设计 “顺序表类的定义”算法：

1.【逻辑结构与存储结构设计】

逻辑结构：每个元素之间是相邻的

存储结构：通过数组存放，每个元素之间也是相邻的

2.【基本操作设计】

数组在计算机内存中可用于存放一串连续的元素，线性表在逻辑结构上是连续的，所以可以用数组存放线性表中的元素，使其在物理结构上也是连续的。

3.【算法设计】 查找固定元素 i=0 否 i<=last i++ 是

i=-1 是

data[i]!=x

否 i

在表中第i个位置插入新元素

x ， i IsFull()||i<0|| i>last+1 是 last++ j=last

j>i

是

data[j]=data[j-1]

j--

否 false 否 data[i]=x true 删除表中已有的元素

x i=Find(x) 是 i<0 否 j=i true

否 j是

last-- data[j]=data[j+1]

true j--

4.【高级语言代码】 查找

public int Find( float x ) { //参数：待查元素 int i = 0;

while ( i <= last && data[i] != x ) i++;

if ( i > last ) return -1; //没有查找到 else return i; //返回x的序号 } 插入

public boolean Insert( float x, int i ) { //参数：待插入的元素，插入位置

if ( IsFull( ) ) return false; //表满

if ( i < 0 || i > last+1 )

return false; //插入位置不合适 //有不允许元素重复的要求时

if ( Find ( x ) >= 0 ) return false;

last++; //可以插入元素 for ( int j = last; j > i; j-- ) data[j] = data[j-1]; data[i] = x;

return true; //插入成功 }

删除

public boolean Remove ( float x ) { //参数：待删元素 int i = Find (x); //查找x的位置

if ( i < 0 ) return false; //表中没有 x for ( int j = i; j < last; j++ ) data[j] = data[j+1]; last--;

return true; //成功删除 }

（三）、程序中类的设计 “SeqList”类：

1.【逻辑结构与存储结构】

逻辑结构：每个元素之间是相邻的

存储结构：通过数组存放，每个元素之间也是相邻的

2.【主要成员变量说明】

float data[]; //float型数组的顺序存储结构

int MaxSize; //数组空间长度(能容纳的元素数) int last; //当前数组最后元素下标(从0起)

3.【主要成员方法说明】 /*求线性表的长度*/

public int Length()

/*求线性表的空间*/

public int getMaxSize()

/*查找固定元素*/

public int Find(float x) //参数：待查元素x

/*获取第i个元素*/

public float GetElement(int i)

//参数：元素的下标

/*在表中第i个位置插入新元素x*/

public boolean Insert(float x,int i)

//参数：待插元素，插入位置

/*删除表中已有的元素x*/

public boolean Remove(float x) //参数：待删元素

/*定位到元素x的后继*/

public int Next(float x) //参数：当前元素

/*替换第i个元素为x*/

public boolean Replace(int i,float x) //参数：需要替换的元素下标，替换为x

4.【高级语言代码】 顺序表(cSeqList)类

public class cSeqList{ //顺序表类

float data[]; //float型数组的顺序存储结构 int MaxSize; //数组空间长度(能容纳的元素数) int last; //当前数组最后元素下标(从0起) //构造函数（参数：空间大小） public cSeqList(int size) {

if ( size <= 0 ) return; //参数不合理 MaxSize = size; //空间大小 last = -1; //约定空表的标志 data = new float[MaxSize];

if ( data == null ) //分配失败 MaxSize = 0; }

//求线性表的长度

public int Length() { return last+1; } //求线性表的空间

public int getMaxSize() { return MaxSize; } //在表中从前向后顺序查找 x

public int Find( float x ) { //参数：待查元素 int i = 0;

while ( i <= last && data[i] != x ) i++;

if ( i > last ) return -1; //没有查找到 else return i; //返回x的序号 }

//得到第i个元素

public float GetElement ( int i ) { //参数：元素序号 //返回第i个元素的值

return i < 0 || i > last ? null : data[i]; }

//在表中第 i 个位置插入新元素 x

public boolean Insert( float x, int i ) { //参数：待插入的元素，插入位置

if ( IsFull( ) ) return false; //表满 if ( i < 0 || i > last+1 )

return false; //插入位置不合适 //有不允许元素重复的要求时

if ( Find ( x ) >= 0 ) return false;

last++; //可以插入元素 for ( int j = last; j > i; j-- ) data[j] = data[j-1]; data[i] = x;

return true; //插入成功 }

//删除表中的已有元素 x

public boolean Remove ( float x ) { //参数：待删元素 int i = Find (x); //查找x的位置

if ( i < 0 ) return false; //表中没有 x for ( int j = i; j < last; j++ ) data[j] = data[j+1]; last--;

return true; //成功删除 }

//定位到元素x的后继

public int Next ( float x ) { //参数：元素x int i = Find (x); //查找x的位置

return ( i == -1 || i == last ) ? -1 : i+1; //返回元素x的后继的地址 }

//定位到元素x的前驱

public int Prior ( float x ){ //参数：元素x int i = Find (x); //查找x的位置 return ( i <= 0 ) ? -1 : i-1; //返回元素x的后继的地址 }

//替换第i个元素为x

public boolean Replace ( int i , float x ){ //参数：序号i , 元素x

if ( i <0 || i > last) return false; data[i]=x; return true; }

//判断线性表是否为空表

public boolean IsEmpty ( ) { return last ==-1; } //判断线性表是否为满表

public boolean IsFull ( ) { return last == MaxSize-1; } //显示输出线性表

public void display () {

System.out.println(\"MaxSize=\"+MaxSize); System.out.println(\"last=\"+last); for(int i=0;i<=last;i++)

System.out.print(\" \"+data[i]); System.out.println();; }

public static void main(String args[]){ }

} //顺序表cSeqList类定义完毕

（四）、程序的输入输出和运行结果截屏

输入1、2、5.1、16、13，输出结果如下图所示