《数据结构实验报告C++语言描述》由会员分享，可在线阅读，更多相关《数据结构实验报告C++语言描述（64页珍藏版）》请在金锄头文库上搜索。
1、实 验 报 告实验课程： 数据结构C+语言的描述 学生姓名： 雷聪 学 号： 6100410013 专业班级： 网工101班 2012年 5 月 25 日目 录实验一 顺序表3实验二 非循环单链表12实验三 链队19实验四 排序24南昌大学实验报告 -（1）顺序表学生姓名： 雷聪 学 号： 6100410013 专业班级： 网工101班 实验类型： 验证 综合 设计 创新 实验日期： 实验成绩： 一 实验目的熟悉顺序表的逻辑结构、存储结构，通过顺序表的相关操作深刻理解顺序表的原理及可能的应用领域。实验借助相关编程软件用C+语言编程实现。二 问题描述1、 构造一个空的线性表L。2、 在线性表L的
2、第i个元素之前插入新的元素e；3、 在线性表L中删除第i个元素，并用e返回其值。三 实验要求1、 分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。2、 在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。四 实验环境PC微机，Windows操作系统，Visual Studio 2010五实验步骤1、用学生选择的语言，设计出线性表的顺序和链表存储结构; 2、设计出这两种存储结构下的线性表的插入、删除算法;3、 用所选择的语言实现算法;4、 测试程序,并对不同存储结构下的算法分析。六实验原代码基类:#ifndef MYHEAD_
3、H#define MYHEAD_H#include C：数据结构网络工程雷聪myhead.h#endif#define LIST_MAX_SIZE 100#define LISTINCREMENT 10template class SqListpublic:/顺序表构造函数SqList();/顺序表拷贝构造函数SqList(const SqList& otherL);/顺序表析构函数virtual SqList();/在第i个元素之前插入一个元素Status insert(int i,ElemType e);/判断顺序表是否为空bool isEmpty();/求顺序表中元素的个数int get
4、Length();/取第i个元素Status getElem(int i,ElemType& e);/查找第一个与e满足compare()关系的元素的序号int locateElem(ElemType e,Status (*compare)(ElemType,ElemType);/返回某元素的前驱Status priorElem(ElemType e,ElemType& prior_e);/返回某元素的后驱Status nextElem(ElemType e,ElemType& next_e);/删除第i个元素Status deleteElem(int i,ElemType& e);/重载赋值
5、运算符的定义SqList operator=(SqList rightL);/把顺序表置空void clear();protected:ElemType *elem;int listSize;int n;template SqList:SqList()elem=new ElemTypeLIST_MAX_SIZE;assert(elem!=0);listSize=LIST_MAX_SIZE;n=0;/功能：顺序表拷贝构造函数template SqList:SqList(const SqList& otherL)elem=new ElemTypeotherL.listSize;assert(ele
6、m!=0);listSize=otherL.listSize;n=otherL.n;for(int i=1;i=n;i+)elemi-1=otherL.elemi-1;/功能：顺序表析构函数template SqList:SqList()deleteelem;template Status SqList:insert(int i,ElemType e)ElemType *newbase;if(in+1) return ERROR;if(n=listSize)newbase=new ElemTypelistSize+LISTINCREMENT;assert(newbase!=0);for(int
7、 j=1;j=i;j-)elemj=elemj-1;elemi-1=e;+n;return OK;template bool SqList:isEmpty()return n?false:true;template int SqList:getLength()return n;template Status SqList:getElem(int i,ElemType& e)if(in) return ERROR;e=elemi-1;return OK;template int SqList:locateElem(ElemType e,Status (*compare)(ElemType,Ele
8、mType)int i;for(i=1;i=n & !(*compare)(elemi-1,e);+i);if(i=n)return i;elsereturn 0;template Status SqList:priorElem(ElemType e,ElemType& prior_e)int i=locateElem(e,equal);if(i1)getElem(i-1,prior_e);elsereturn ERROR;return OK;template Status SqList:nextElem(ElemType e,ElemType& next_e)int i=locateElem
9、(e,equal);if(i=n |i=0)return ERROR;elsegetElem(i+1,next_e);return OK;template Status SqList:deleteElem(int i,ElemType& e)if(in)return ERROR;e=elemi-1;for(int j=i+1;j=n;+j)elemj-2=elemj-1;-n;return OK;template SqList SqList:operator=(SqList rightL)if(this!=&rightL)if(listSizerightL.listSize)delete el
10、em;elem=new ElemTyperightL.listSize;assert(elem!=0);listSize=rightL.listSize;n=rightL.n;for(int i=1;i=n;+i)elemi-1=rightL.elemi-1;return *this;template void SqList:clear()n=0;七实验结果(1)顺序表首页(2)随机生成顺序表(3)初始化另一个顺序表(4)输入顺序表(5)在第i个元素之前插入一个元素(6)判断顺序表是否为空(7)求顺序表中元素个数(8)取第i个元素(9)查找第1个与e满足compare()关系的元素(10)返回
11、某元素的前驱,后继(11)删除第i个元素(12)把一个顺序表赋值给另一个顺序表(13)把顺序表置空八实验小结通过实验知道了在main函数中提供菜单选择，根据选项不同调用测试头文件中的相应函数。熟悉了C+数据结构实验的基本形式：创建对应数据类型的基类、派生类、main.cpp文件、测试头文件。测试头文件中的每个操作函数，通过调用传来的数据类型对象的具体操作，实现需要的功能，再在测试头文件中显示相应的效果。南昌大学实验报告-（2）非循环单链表学生姓名： 雷聪 学 号： 6100410013 专业班级： 网工101班 实验类型： 验证 综合 设计 创新 实验日期： 实验成绩： 一. 实验目的掌握非循环单链表的逻辑结构、存储结构。深刻理解
