南昌大学数据结构实验报告.doc

实 验 报 告实验课程： 数据结构C+语言的描述 学生姓名： 学 号： 专业班级： 2012年 6月 1日目 录实验一 顺序表2实验二 非循环单链表19实验三 链队41实验四 排序54南昌大学实验报告 -（1）顺序表学生姓名： 学 号： 专业班级： 实验类型： 验证 综合 设计 创新 实验日期： 实验成绩： 一. 实验目的掌握顺序表的逻辑结构、存储结构、操作，并通过 C+编程实现。二. 问题描述线性表是由n(n0)个元素（结点）a1, a2, , an组成的有限序列，其中ai中的i称为该数据元素的位置（序号），n为数据元素的个数（表的长度），当n等于0时称为空表。按逻辑次序依次把数据元素存放在一组连续的地址存储单元里的线性表称为顺序表。在这里，我们通过C+中的动态数组来实现顺序表的存放，并通过建立顺序表类实现它的各种操作。三. 实验要求实现顺序表的三个框架操作：随机生成，用已有顺序表初始化另一个顺序表，输入顺序表。以及十个基本操作：在第i个元素之前插入元素，判断是否为空，求元素个数，取第i个元素，查找第一个与e满足compare()关系的元素，返回元素的前驱，返回后继，删除第i个元素，把一个顺序表赋值给另一个顺序表，置空顺序表。四. 实验环境PC微机，Windows操作系统，Visual Studio 2010。五 实验代码顺序表基类代码：#ifndef MYHEAD_H #define MYHEAD_H #include D:MY PROGRAM数据结构myhead.h#endif#define LIST_MAX_SIZE 100#define LISTINCREMENT 10/声明template class SqListpublic: void suiji(int n); void shuruSqList(int e); int bin_Search(ElemType key);void clear();Status deleteElem(int i,ElemType& e);Status getElem(int i,ElemType& e);int getLength();int getListSize();Status insert(int i,ElemType e);bool isEmpty();int locateElem(int& i,ElemType e,Status (*compare)(ElemType,ElemType);Status nextElem(ElemType e,ElemType& next_e);SqList operator =(SqList rightL);Status priorElem(ElemType e,ElemType& prior_e);/自动调用构造函数析构函数的声明 SqList();virtual SqList();SqList(const SqList& otherL);int n; int m; int i; int prior_e; int next_e; int e;ElemType *elem;protected:int listSize;/操作的实现templatevoid SqList:suiji(int n)int i=1;for (i=1;i=n;i+)elemi-1=rand()%100;templatevoid SqList:shuruSqList(int e)for(int i=1;ie;elemi-1=e;template void SqList:clear()n=0;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 Status SqList:getElem(int i,ElemType& e)if(in) return ERROR;e=elemi-1;return OK;template int SqList:getLength()return n;template int SqList:getListSize()return listSize;template Status SqList:insert(int i,ElemType e)ElemType *newbase;if(in)return ERROR;if(n=listSize)newbase =new ElemTypelistSize+LISTINCREMENT; assert(newbase!=0); for(int 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:locateElem(int& i,ElemType e,Status (*compare)(ElemType,ElemType)for(int i=1; i=n & !(*compare)(elemi-1,e); +i);if(i=1)return i;else return 0;template Status SqList:nextElem(ElemType e,ElemType& next_e)int i=locateElem(i,e,equal);if(i1|i=n)return ERROR;elsegetElem(i+1,next_e);return OK;/重载运算符的定义template SqList SqList:operator=(SqListrightL)if(this!=&rightL)if(listSizerightL.listSize)delete elem;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 Status SqList:priorElem(ElemType e,ElemType& prior_e)int i=locateElem(i,e,equal);if(in)return ERROR;elsegetElem(i-1, prior_e);return OK;/系统自动调用的构造函数及析构函数的实现template SqList:SqList()elem=new ElemTypeLIST_MAX_SIZE;assert(elem!=0);listSize=LIST_MAX_SIZE;n=8;elem0=20;elem1=85;elem2=45;elem3=51;elem4=15;elem5=95;elem6=66;elem7=62;template SqList:SqList()delete elem;/拷贝初始化构造函数template SqList:SqList(const SqList& otherL)elem=new ElemTypeotherL.listSize;assert(elem!=0);listSize=otherL.listSize;n=otherL.n;for(int i=1;i=n;+i)elemi-1=otherL.elemi-1;派生类代码：/MySqList.h/SqList.h#ifndef SQLIST_H#define SQLIST_H#include D:MY PROGRAM数据结构SHIYANex3_1SqListSqList.h#endiftemplate class MySqList:public SqListpublic:void read(istream& in);void display(ostream& out) const;template void MySqList:read(istream& in)int i=1;inn;cout请输入顺序表中的元素?：;for(i=1;ielemi-1;template istream& operator (istream& in,MySqList & iD)iD.read(in);return in;template void MySqList:display(ostream& out) constout当前顺序表有n个元素，分别为endl;for(int j=1;j=n;j+)out j ;outendl;for(int i=1;i=n;i+)out elemi-1 ;outendl;template ostream& operator (ostream& out,const MySqList & oD)oD.display(out);return out;测试模块代码：/ex3_1_Text.htemplate void displayCurrentObject(MySqList rec)coutendl;coutrec;template void ex3_1_1 (MySqList & rec,char& continueYesNo)int i,e;cout * 在第i个元素前插入一个元素 *endlendl;couti;coute;cout你要在第i个元素前插入元素eendl;rec.insert(i,e);coutrec;cout*endlendl;coutcontinueYesNo;template void ex3_1_2(MySqList & rec,char& continueYesNo)int n;cout * 判断顺序表是否为空 *endl0)cout 当前顺序表不为空endl;elsecout 当前顺序表为空endl;cout*endl;rec.isEmpty();coutrec;cout *endlendl;coutcontinueYesNo;template void ex3_1_3(MySqList rec,char& continueYesNo)int n;cout* 求顺序表中元素的个数 *endlendl;cout 顺序表的元素个数为：rec.nendl;cout*endlendl;coutcontinueYesNo;template void ex3_1_4(MySqList rec,char& continueYesNo)int i,e;cout* 取第i个元素 *endlendl;couti;coutendl;rec.getElem(i,e);coutn 你想取的第i个元素的值为：eendl;cout*endlendl;coutcontinueYesNo;template void ex3_1_5(MySqList rec,char& continueYesNo)int i,e;if(rec.n1)MySqList rec;cout* 查找第1个与某元素满足compare（）关系元素的序号 *endlendl;cout 查找等于某元素的操作endl;coute;rec.locateElem(i,e,equal);cout你想要查找的第一个等于e的元素序号为iendlendl;cout 查找大于某元素的操作endl;cout请输入你要查找的元素：e;rec.locateElem(i,e,great);cout你想要查找的第一个大于e的元素序号为iendlendl;cout 查找小于某元素的操作endl;cout请输入你要查找的元素：e;rec.locateElem(i,e,less);cout你想要查找的第一个小于e的元素序号为iendlendl;cout*endlendl;coutcontinueYesNo;template void ex3_1_6(MySqList rec,char& continueYesNo)int e,prior_e;cout* 返回某元素的前驱 *endlendl;coute;cout你想要查找的元素e的前驱为rec.prior_eendl;rec.priorElem(e,prior_e);cout*endlendl;coutcontinueYesNo;template void ex3_1_7(MySqList rec,char& continueYesNo)int e,next_e;cout* 返回某元素的后继 *endlendl;coute;cout你想要查找的元素e的后继为next_eendl;rec.nextElem(e,next_e);cout*endlendl;coutcontinueYesNo; template void ex3_1_8(MySqList rec,char& continueYesNo)int i,e;cout* 删除第i个元素 *endlendl;couti;rec.deleteElem(i,e);cout你想要删除的元素的值为rec.eendl;cout删除后的顺序：;coutrec;cout*endlendl;coutcontinueYesNo;template void ex3_1_9(MySqList rec,char& continueYesNo)MySqList recother;cout* 把一个顺序表赋值给另一个顺序表 *endlendl;cout 另一个顺序表赋值给当前顺序表为：endl;rec=recother;coutrecother;cout*endlendl;coutcontinueYesNo;template void ex3_1_10(MySqList rec,char& continueYesNo)int n;cout* 把顺序表置空 *endlendl;rec.clear();cout当前顺序表置空后，元素个数为：rec.nendl;cout*endlendl;coutcontinueYesNo;template void ex3_1_11(MySqList rec,char& continueYesNo) int n;MySqList rec11;n=rand()%10;rec11.suiji(n);cout*随机生成顺序表(元素值为0到99之间的整数)*endl;cout 用以下随机数作为当前顺序表的元素:endl;for(int i=1;i=n;i+)coutrec11.elemi-1 ;coutendl;cout随机生成的顺序表为:endl;coutrec11;rec=rec11;cout*endlendl;coutcontinueYesNo;template void ex3_1_12(MySqList rec,char& continueYesNo)MySqList rec12;cout*用已有的顺序表初始化另一个顺序表*endl;cout 当前顺序表初始化另一个顺序表为:endl;rec12=rec;coutrec12;cout*endlendl;coutcontinueYesNo;template void ex3_1_13(MySqList rec,char& continueYesNo)int n,e;MySqList rec13;cout*输入顺序表*endl;coutn;coutendl;coute;rec13.shuruSqList(e);coutendl;cout 新请输入顺序表如下:endl;coutrec13;cout*endlendl;coutcontinueYesNo;主程序模块代码：/main.cpp#include using namespace std;/MySqList.h#ifndef MYSQLIST_H #define MYSQLIST_H #includeD:MY PROGRAM数据结构SHIYANex3_1SqListex3_1SqListMySqList.h#endif/ex3_1_Test_h#ifndef EX3_1_TEST_H #define EX3_1_TEST_H #include D:MY PROGRAM数据结构SHIYANex3_1SqListex3_1SqListex3_1SqListex3_1_Test.h#endifvoid main()MySqList rec;int choose;char continueYesNo=N;while(1)choose=0;system(cls);coutendl;cout * 测 试 顺 序 表 的 操 作 *endlendl;coutt 1.在第i个元素前插入一个元素endl;coutt 2.判断顺序表是否为空endl;coutt 3.求顺序表中元素的个数endl;coutt 4.取第i个元素endl;coutt 5.查找第1个与某元素满足compare（）关系元素的序号endl;coutt 6.返回某元素的前驱endl;coutt 7.返回某元素的后继endl;coutt 8.删除第i个元素endl;coutt 9.把一个顺序表赋值给另一个顺序表endl;coutt 10.把顺序表置空endl;coutt 11.随机生成顺序表 （元素值为0到99只见的整数）endl;coutt 12.用已有的顺序表初始化另一个顺序表endl;coutt 13.输入顺序表endl;cout 其他.结束endlendl; cout /endl;cout当前顺序表有8个元素，分别为：; displayCurrentObject(rec); cout /endlendl; coutchoose; if(choose0 & choose14)system(cls);displayCurrentObject(rec);switch(choose) case 1:ex3_1_1(rec,continueYesNo); break;case 2:ex3_1_2(rec,continueYesNo); break;case 3:ex3_1_3(rec,continueYesNo); break;case 4:ex3_1_4(rec,continueYesNo); break;case 5:ex3_1_5(rec,continueYesNo); break;case 6:ex3_1_6(rec,continueYesNo); break;case 7:ex3_1_7(rec,continueYesNo); break;case 8:ex3_1_8(rec,continueYesNo); break;case 9:ex3_1_9(rec,continueYesNo); break;case 10:ex3_1_10(rec,continueYesNo); break;case 11:ex3_1_11(rec,continueYesNo); break;case 12:ex3_1_12(rec,continueYesNo); break;case 13:ex3_1_13(rec,continueYesNo); break;default: coutn 你选择了结束。endlendl;return;if(continueYesNo=N|continueYesNo=n)break;五实验结果实验结果显示：七实验小结认识并了解到了c+数据结构中组成数据结构的基类、派生类、main.cpp文件、测试头文件。在main函数中提供菜单选择，根据选项不同调用测试头文件中的相应函数。测试头文件中的每个操作函数，通过调用传来的数据类型对象的具体操作，实现需要的功能，再在测试头文件中显示相应的效果。南昌大学实验报告 -（2）非循环单链表学生姓名： 学 号： 专业班级： 实验类型： 验证 综合 设计 创新 实验日期： 实验成绩： 一. 实验目的掌握非循环单链表的逻辑结构、存储结构、操作，并通过 C+编程实现。二. 问题描述以链式结构存储的线性表称为线性链表，若每个结点只有一个指向后继的指针域，则称之为单链表。终端结点无后继，若终端结点的指针域置空即NULL，则为非循环单链表。三. 实验要求实现非循环单链表的三种框架操作，以及十二种基本操作。四. 实验环境PC微机，Windows操作系统，Visual Studio 2010。五 实验代码顺序表基类代码：/myhead.h#ifndef MYHEAD_H#define MYHEAD_H#include D:MY PROGRAM数据结构myhead.h#endif/类声明（基类）templateclass LinkListpublic:class LinkNodepublic:ElemType data;LinkNode *next;typedef LinkNode *NodePointer;void adverse();void clear();Status deleteElem(ElemType e);void deleteRepeat();Status getElem(int i,ElemType& e);NodePointer getHead();int getLength();Status insert(int i,ElemType e);bool isEmpty();Status locateElem(ElemType e,Status (*compare)(ElemType,ElemType),int& i);Status nextElem(ElemType e,ElemType& next_e);LinkList operator=(LinkList rightL);Status priorElem(ElemType e,ElemType& prior_e);LinkList();virtual LinkList();LinkList(const LinkList& otherL);protected:NodePointer head;/C+类实现（基类）templatevoid LinkList:adverse()NodePointer r,p,q;if(!head)return;r=NULL,p=head,q=p-next;while(p)p-next=r;r=p;p=q;if(q)q=q-next;head=r;templatevoid LinkList:clear()NodePointer p,q;p=NULL,q=head;while(q)p=q;q=q-next;delete p;head=NULL;templateStatus LinkList:deleteElem(ElemType e)NodePointer r,p;r=NULL,p=head;while(p & !equal(p-data,e)r=p;p=p-next;if(p=NULL)head=head-next;elser-next=p-next;delete p;return OK;templatevoid LinkList:deleteRepeat()NodePointer r,p;NodePointer s;r=NULL,p=head;while(p)s=head;while(s!=p)if(s-data=p-data)r-next=p-next; delete p; p=r;break;s=s-next;r=p;if(p)p=p-next;templateStatus LinkList:getElem(int i,ElemType& e)int j=1;NodePointer p=head;while(p & jnext;+j;if(!p|ji)return ERROR;e=p-data;return OK;templateint LinkList:getLength()int n=0;NodePointer p=head;while(p)+n;p=p-next;return n;templateStatus LinkList:insert(int i,ElemType e)int j=1;NodePointer p=head;NodePointer s;while(p & jnext;if(!p & ji)return ERROR;s=new LinkNode;assert(s!=0);s-data=e;if(i=1)s-next=head;head=s;elses-next=p-next;p-next=s;return OK;templatebool LinkList:isEmpty()return (head?false:true);templateStatus LinkList:locateElem(ElemType e,Status (*compare)(ElemType,ElemType),int& i)NodePointer p=head;i=1;while(p & !(*compare)(p-data,e)p=p-next;+i;if(!p)return ERROR;return OK;templateStatus LinkList:nextElem(ElemType e,ElemType& next_e)NodePointer p=head;while(p & !equal(p-data,e)p=p-next;if(!p|!p-next)return ERROR;next_e=p-next-data;retur