《数据结构实验报告--1.doc》由会员分享，可在线阅读，更多相关《数据结构实验报告--1.doc（12页珍藏版）》请在三一文库上搜索。
1、长春理工大学数据结构与算法实验报告实验题目： 线性表顺序存储试验 实验时间： 实验地点： 班 级： 学 号： 姓 名： 一、 实验目的及要求 1、掌握用Visual C+6.0上机调试顺序表的基本方法2、 掌握顺序表的基本操作，插入、删除、查找等算法的实现基本要求 要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。二、 实验意义及原理当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。三、 算法分析（1）以下为函数运行结
2、果状态代码 #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 *
3、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）插入函数/函数名：
4、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(L.length+1) return ERROR; if(L.length=L.listsize) newbase=(ElemType*)realloc(L.elem,L.listsize+LISTINCREMENT
5、*sizeof(ElemType); if(newbase=NULL) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; for(p=&(L.elemL.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
6、i,ElemType e) if(iL.length) return ERROR; ElemType *p,*q; p=&(L.elemi-1); e=*p; q=L.elem+L.length-1; for(+p;p=q;+p) *(p-1)=*p; -L.length; return OK;四、 源代码#include using namespace std;#define MAXSIZE 20typedef int ElemType;typedef structElemType dataMAXSIZE;int length;int listsize;SqList;/构造空线性表Listb
7、ool InitList(SqList &L)for(int i=0;iMAXSIZE;i+)L.datai=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 | posL.length)return false;elseptr=L.d
8、atapos-1;return ptr;/查询第location位置上的元素void locate(SqList L,int location) if(L.length=location)cout查询的元素为：L.datalocation-1endl;elsecout该位置没有元素!endl;/*在Sq中第pos2个位置插入新的数据元素Elem，L的长度加1*/bool ListInsert(SqList &L, int pos2,ElemType Elem )/线性表空间不足，无法插入if (L.length = MAXSIZE)cout 空间不足，无法插入！ endl;return fal
9、se; if (pos2 L.length + 1)cout 插入位置错误！ endl;return false; if (pos2 = pos2 - 1; i-) L.datai + 1 = 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
10、pos, ElemType *pe) if (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 构造线性表List endl;InitList(list); /构造线性表if(
11、ListEmpty(list) /判断是否为空cout 线性表为空 endl;elsecout 线性表不为空;int num; /要添加的元素的个数coutnum;cout 输入添加元素： ;ElemType Elem; for (int i = 1 ; i 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
12、list.datai ; cout endl;cout ele;locate(list, ele);int result;cout 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 ; coutendllocation;ElemTyp
13、e Elem1;coutElem1;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.datai ; cout endl; return 0;五、 运行结果六、 心得体会1、熟悉了用Visual C+6.0上机调试顺序表的基本方法2、练习了顺序表的基本操作，实现了顺序表基本的构造、插入、删除、查找等算法3、生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储4、借鉴了书上算法的思想，并非完全按照书上的思路构造顺序表，加入了同学还有自己的一部分思想和实现方法