数据结构实验报告--1.docx

长春理工大学

数据结构与算法
实验报告

实验题目：
线性表顺序存储试验
实验时间：

实验地点：

班 级：

学 号：

姓 名：

一、 实验目的及要求
1、掌握用Visual C++6.0上机调试顺序表的基本方法
2、 掌握顺序表的基本操作，插入、删除、查找等算法的实现
[基本要求] 要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。
二、 实验意义及原理
当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。

三、 算法分析
（1）以下为函数运行结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
（2）线性表的动态分配顺序存储结构
#define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间分配增量
typedef int Status; //函数类型，其值为为函数结果状态代码
typedef int ElemType; //假设数据元素为整型
typedef struct
{
    ElemType *elem; //存储空间基址
    int length; //当前长度
    int listsize; //当前分配的存储容量
}Sqlist;
（2）构造函数
//函数名：InitList()
//参数：SqList L
//初始条件：无
//功能：构造一个空线性表
Status InitList(Sqlist L)
{
    L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(L.elem==NULL)
        exit(OVERFLOW);
    else
    {
        L.length=0;
        L.listsize=LISTINCREMENT;
        return OK;
    }
}
（3）插入函数
//函数名：ListInsert()
//参数：SqList L,int i,ElemType e
//初始条件：线性表L已存在，1<=i<=ListLength(L)+1
//功能：在线性表中第i个数据元素之前插入数据元素e
Status ListInsert(Sqlist L,int i,ElemType e)
{
    int *q=&(L.elem[i-1]);
    ElemType *newbase,*p;
    if(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==NULL)
            exit(OVERFLOW);
        L.elem=newbase;
        L.listsize+=LISTINCREMENT;
    }
    for(p=&(L.elem[L.length-1]);p>=q;--p)
        *(p+1)=*p;
    *q=e;
    ++L.length;
    return OK;
}
（4）删除函数
//函数名：ListDelete()
//参数：SqList L,int i,Elemtype e
//初始条件：线性表L已存在，1<=i<=ListLength(L)
//功能：将线性表L中第i个数据元素删除
Status ListDelet(Sqlist L,int i,ElemType e)
{
    if(i<1||(i>L.length))
        return ERROR;
    ElemType *p,*q;
    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;
}
四、 源代码
#include <iostream>
using namespace std;
#define MAXSIZE 20
typedef int ElemType;
typedef struct{
ElemType data[MAXSIZE];
int length;
int listsize;
}SqList;

//构造空线性表List
bool InitList(SqList &L){
for(int i=0;i<MAXSIZE;i++){
L.data[i]=0;}
L.length=0;
L.listsize = MAXSIZE;
return true;
}
//判断线性表是否为空
bool ListEmpty(SqList L){
if(L.length==0){return true;}
else
return false; }

//用ptr返回sql4第pos个元素的值
ElemType GetElem(SqList &L,int pos,ElemType &ptr){
if(L.length<=0 || pos<1 || pos>L.length){
return false;
}
else{
ptr=L.data[pos-1];
return ptr;
}
}

//查询第location位置上的元素
void locate(SqList L,int location)
{
if(L.length>=location)
cout<<"查询的元素为："<<L.data[location-1]<<endl;
else
cout<<"该位置没有元素!"<<endl;
}
/*在Sq中第pos2个位置插入新的数据元素Elem，L的长度加1*/
bool ListInsert(SqList &L, int pos2,ElemType Elem )
{
//线性表空间不足，无法插入
if (L.length == MAXSIZE){
cout << "空间不足，无法插入！" << endl;
return false;
}
if (pos2 < 1 || pos2 > L.length + 1){
cout << "插入位置错误！" << endl;
return false;
}
if (pos2 <= L.length)
{
/* 将要插入位置之后的数据元素向后移动一位 */
for (int i = L.length - 1; i >= pos2 - 1; i--)
{
L.data[i + 1] = L.data[i];
}
}
L.data[pos2 - 1] = Elem; /* 将新元素插入 */
if(L.data[pos2-1]==Elem){
//cout << "添加元素成功" << endl;
L.length++;
return true;
}
else{
cout << "添加元素失败***" << endl;
return false;
}
}

//删除ps的第pos个数据元素，并用pe返回其值，ps的长度减1
bool ListDelete(SqList &L, int pos, ElemType *pe)
{
if (pos < 1 || pos > L.length){
cout << "删除位置错误！" << endl;
return false;
}else{

*pe = L.data[pos - 1];
/* 将删除位置后继元素前移 */
for (int i = pos; i < L.length; i++)
L.data[i - 1] = L.data[i];
L.length--;
return true;
}
}
int ListLength(SqList Sq)
{
return Sq.length;
}

//主函数
int main(){
SqList list;
cout << "构造线性表List" << endl;
InitList(list); //构造线性表
if(ListEmpty(list)) //判断是否为空
{
cout << "线性表为空" << endl;
}
else
cout << "线性表不为空";

int num; //要添加的元素的个数
cout<<"输入值的个数：";
cin>>num;
cout << "输入添加元素：" ;
ElemType Elem;

for (int i = 1 ; i < num+1; i++) //添加元素
{
cin>>Elem;
ListInsert(list, i, Elem);
}
if(list.length<=list.listsize)
cout<<"添加元素成功!"<<endl;
if (!ListEmpty(list)) //展示表内容
{
cout << "list: " << endl;
for (int i = 0 ; i < ListLength(list); i++)
cout << list.data[i] << ' ';
}
cout << endl;
cout << "请输入要查询元素的位置：";
int ele;
int pre;
cin >> ele;
locate(list, ele);
int result;
cout << "输入要删除元素的位置：";
cin >> pre;
bool re = ListDelete(list, pre, &result);
cout << "delete: " << result << endl;
if(re){
cout << "删除成功！" << endl;
}else{
cout << "删除失败！" << endl;
}
if (!ListEmpty(list))
{
cout << "list: " << endl;
for (int i = 0 ; i < ListLength(list); i++)
cout << list.data[i] << ' ';
}
cout<<endl<<"插入新的数据元素!\n请输入插入位置：";
int location; //插入元素的位置
cin>>location;
ElemType Elem1;
cout<<"输入要插入的元素：";
cin>>Elem1;
int Length = list.length; //记录插入之前的表长度
ListInsert(list,location,Elem1);
if(list.length == Length+1)
cout<<"插入元素成功!"<<endl;
if (!ListEmpty(list))
{
cout << "list: " << endl;
for (int i = 0 ; i < ListLength(list); i++)
cout << list.data[i] << ' ';
}
cout << endl;
return 0;
}
五、 运行结果

六、 心得体会
1、熟悉了用Visual C++6.0上机调试顺序表的基本方法
2、练习了顺序表的基本操作，实现了顺序表基本的构造、插入、删除、查找等算法
3、生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储
4、借鉴了书上算法的思想，并非完全按照书上的思路构造顺序表，加入了同学还有自己的一部分思想和实现方法

Welcome To
Download !!!

欢迎您的下载，资料仅供参考！