数据结构实验报告(共12页)

1、精选优质文档-倾情为你奉上长春理工大学数据结构与算法实验报告实验题目： 线性表顺序存储试验 实验时间： 实验地点： 班 级： 学 号： 姓 名： 一、 实验目的及要求 1、掌握用Visual C+6.0上机调试顺序表的基本方法2、 掌握顺序表的基本操作，插入、删除、查找等算法的实现基本要求 要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。二、 实验意义及原理当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。三、 算法

2、分析（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; /假设数据元素为整型 typede

3、f 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); 

4、;   if(L.elem=NULL)        exit(OVERFLOW);    else            L.length=0;        L.listsize=LISTINCREMENT;        return

5、 OK;    （3）插入函数/函数名：ListInsert()/参数：SqList L,int i,ElemType e/初始条件：线性表L已存在，1<=i<=ListLength(L)+1/功能：在线性表中第i个数据元素之前插入数据元素eStatus ListInsert(Sqlist L,int i,ElemType e)    int *q=&(L.elemi-1);    ElemType *newbase,*p;    if(i<1|i&

6、gt;(L.length+1)        return ERROR;    if(L.length>=L.listsize)            newbase=(ElemType*)realloc(L.elem,L.listsize+LISTINCREMENT*sizeof(ElemType);        if

7、(newbase=NULL)            exit(OVERFLOW);        L.elem=newbase;        L.listsize+=LISTINCREMENT;        for(p=&(L.elemL.length-1);p>=q;-

8、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) 

9、60;  if(i<1|(i>L.length)        return ERROR;    ElemType *p,*q;    p=&(L.elemi-1);    e=*p;    q=L.elem+L.length-1;    for(+p;p<=q;+p)      &

10、#160; *(p-1)=*p;    -L.length;    return OK;四、 源代码#include <iostream>using namespace std;#define MAXSIZE 20typedef int ElemType;typedef structElemType dataMAXSIZE;int length;int listsize;SqList;/构造空线性表Listbool InitList(SqList &L)for(int i=0;i<MAXSIZE;i+)L.d

11、atai=0;L.length=0;L.listsize = MAXSIZE;return true;/判断线性表是否为空bool ListEmpty(SqList L)if(L.length=0)return true;elsereturn false; /用ptr返回sql4第pos个元素的值ElemType GetElem(SqList &L,int pos,ElemType &ptr)if(L.length<=0 | pos<1 | pos>L.length)return false;elseptr=L.datapos-1;return ptr;/查询

12、第location位置上的元素void locate(SqList L,int location) if(L.length>=location)cout<<"查询的元素为："<<L.datalocation-1<<endl;elsecout<<"该位置没有元素!"<<endl;/*在Sq中第pos2个位置插入新的数据元素Elem，L的长度加1*/bool ListInsert(SqList &L, int pos2,ElemType Elem )/线性表空间不足，无法插入if (L

13、.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.datai + 1 =

14、L.datai; L.datapos2 - 1 = Elem; /* 将新元素插入 */if(L.datapos2-1=Elem)/cout << "添加元素成功" << endl;L.length+;return true;elsecout << "添加元素失败*" << endl;return false;/删除ps的第pos个数据元素，并用pe返回其值，ps的长度减1bool ListDelete(SqList &L, int pos, ElemType *pe) if (pos < 1

15、 | pos > L.length)cout << "删除位置错误！" << endl;return false;else*pe = L.datapos - 1;/* 将删除位置后继元素前移 */for (int i = pos; i < L.length; i+)L.datai - 1 = L.datai;L.length-;return true; int ListLength(SqList Sq) return Sq.length;/主函数int main()SqList list;cout << "构造线性表

16、List" << endl;InitList(list); /构造线性表if(ListEmpty(list) /判断是否为空cout << "线性表为空" << endl;elsecout << "线性表不为空"int num; /要添加的元素的个数cout<<"输入值的个数："cin>>num;cout << "输入添加元素：" ;ElemType Elem; for (int i = 1 ; i < num+1;

17、 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.datai << ' '

18、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;elsecout << "删除失败！" << endl;if (!ListEmpty(list) cout << "list: " << endl; for (int i = 0 ; i < ListLength(list); i+) cout << list.datai << ' ' cout<<endl<<"