南昌大学数据结构实验报告(c ).pdf

1实验报告实验课程：实验课程：数据结构数据结构学生姓名：学生姓名：学学号：号：专业班级：专业班级：网络工程网络工程班班20142014 年年6 6 月月3030 日日2目目录录一、 实验一 长方形长方形-------------------------3二、 实验二 循序表循序表------------------13------------------13三、 实验三 链表链表--------------------29--------------------29四、 实验四 循环双链表循环双链表---------------51---------------513南昌大学实验报告南昌大学实验报告---（1）长方形数据结构 C++类学生姓名：学号：专业班级：实验类型：□验证 ■ 综合 □ 设计 □ 创新实验日期： 2014-6-25实验成绩：【【实验实验题目】题目】长方形数据结构 C++类【【实验实验步骤】步骤】1.需求分析需求分析为实现长方形的输入输出和其他操作，我们进行如下需求分析： 长方形相关数据的输出 重载赋值运算符的定义 输出长方形的面积 测试数据2.概要设计概要设计为了实现上述功能，需要设定以下模块：主程序模块 ↓ 测试长方形模块 ↓ 派生长方形模块 ↓ 抽象长方形模块设置长 设置宽 .各模块之间调用关系如图3.详细设计详细设计①①长方形数据结构基类长方形数据结构基类4template class Rectangle { public:class RectangleNo { public: int no; }; Rectangle operator=(Rectangle rightR);void setLength(ElemType l);void setWidth(ElemType z);void setNo(int i);ElemTypeArea(ElemType);Rectangle();Rectangle(const Rectanglevirtual~Rectangle(); protected: ElemType length; ElemType width; RectangleNo myNo; }; template Rectangle Rectangle::operator = (Rectangle rightR) { if(this!= width=rightR.width; myNo=rightR.myNo; cout void Rectangle::setLength(ElemType l)5{ length=1; } template void Rectangle::setWidth(ElemType z) { width=z; } template ElemType Rectangle::Area(ElemType) { return length*width; } template void Rectangle::setNo(int i) { myNo.no=i; }template Rectangle ::Rectangle() { length=width=0; cout Rectangle::Rectangle(const Rectangle width =otherD.width; myNo = otherD.myNo; cout Rectangle:: ~Rectangle() { cout6class MyRectangle: public Rectangle { public: void read(istream void diaplay(ostream }; template void MyRectangle::read(istream cout>width; } templateistream return in; } template void MyRectangle::diaplay(ostream return out; }③③主程序模块主程序模块 void main() { MyRectangle rec; int choose; char continueYesNo='N';while(1)7{ choose=0; system(“cls“); cout>choose;if(choose>0 //有序顺序 表折半查找void clear();//把顺序表 置空Status deleteElem(int i,ElemType//删除第i个元 素Status getElem(int i,ElemType//取第 i 个元 素int getLength();//求顺序表 中元素的个数int getListSize();//取顺序表 空间的大小Status insert(int i,ElemType e);//在第 i 个元素 之前插入一个元素bool isEmpty();//判断顺 序表是否置空15int locateElem(ElemType e,Status (*compare)(ElemType,ElemType)); //Status nextElem(ElemType e,ElemTypeSqList operator =(SqList rightL);Status priorElem(ElemType e,ElemTypeint sequentialSearch(ElemType e);//******************************系统自动调用构造函数及析构函数声明 ************************************//SqList();virtual ~SqList();SqList(const SqListprotected: ElemType *elem; int listSize; int n; };/////////////////////////////////////////////////////////////////////////////////////顺序表数据结构 C++类的实现////////////////////////////////////////////////////////////////////////////////////折半查找 template int SqList::bin_Search(ElemType key) { int low,mid,high; low=o,high=n-1; while(low void SqList::clear() { n=0; }//删除第 i 个元素 template Status SqList::deleteElem(int i,ElemType e=elem[i-1]; for(int j=i+1;j Status SqList::getElem(int i,ElemTypee=elem[i-1]; return OK; }//求顺序表中元素个数 template int SqList::getLength() { return n; }//取顺序表存储空间的大小 template 17int SqList::getListSize() { return ListSize; }//在第 i 个元素之前插入一个元素 template Status SqList::insert(int i,ElemType e) { ElemType *newbase;if(in+1) return ERROR;if(n>=listSize) { newbase=new ElemType[listSize+LISTINCREMENT]; assert(newbase!=0); for(int j=1;j=i;--j) elem[j]=elem[j-1]; elem[i-1]=e; ++n; return OK; } //判断顺序表是否为空 template bool SqList::isEmpty() { return n?false:true; }//查找第 i 个与额满足 compare（）关系的元素 template int SqList::locateElem(ElemType e,Status (*compare)(ElemType,ElemType)) { int i=1; for( i=1;i Status SqList::nextElem(ElemType e,ElemType if(i SqList SqList::operator=(SqListrightL) { if(this!=19if(i int SqList::sequentialSearch(ElemType key) { for(int i=1;i SqList::SqList() { elem=new ElemType[LIST_MAX_SIZE]; assert(elem!=0); listSize=LIST_MAX_SIZE; n=0; }//顺序表析构函数 template SqList::~SqList() { delete[] elem; }//顺序表初始化构造函数 template SqList::SqList(const SqList20assert(elem!=0); listSize=otherL.listSize; n=otherL.n; for(int i=1;i class MySqList:public SqList { public: void read(istreamvoid display(ostreamvoid randSqList();};/////////////////////////////////////////////////////////////////////////////////////////输入顺序表 template void MySqList::read(istream cout>elem[i];}//功能： 重载输入运算符的定义21template istream return in; }// 功能：输出顺序表template void MySqList::display(ostream return out; }//随机生成顺序表template void MySqList::randSqList() { srand((unsigned)time(NULL)); n=rand()%8+1; cout using namespace std;#ifndef MYSQLIST_H #define MYSQLIST_H #include“Test Include\MySqList.h“ #endif#ifndef EX3_1_TEXT_H #define EX3_1_TEXT_H #include“ex3_1_Test.h“ #endifvoid main() { MySqList sql; int choose; char continueYesNo='N'; sql.randSqList(); while(1) { choose=0; system(“cls“); cout>choose;if(choose>0 LinkNode *next; }; typedef LinkNode * NodePointer; voidadverse(); //非循环单链表的逆置voidclear(); //把循环单链表置空StatusdeleteElem(ElemTypee); //删除循环单链表中数据域为 e 的第一个节点voiddeleteRepeat(); //删除非循环单链表中的重复值Status getElem(int i,ElemType//31取费循环单链表的第 i 个节点NodePointergetHead(); //取第一个节点。