数据结构实验报告C++语言描述

《数据结构实验报告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班 实验类型： 验证 综合 设计 创新 实验日期： 实验成绩： 一. 实验目的掌握非循

12、环单链表的逻辑结构、存储结构。深刻理解非循环单链表的算法,熟练应用非循环单链表的相关操作。二. 问题描述以链式结构存储的线性表称为线性链表，若每个结点只有一个指向后继的指针域，则称之为单链表。终端结点无后继，若终端结点的指针域置空即NULL，则为非循环单链表。三. 实验要求独立实现非循环单链表的十五中操作。四. 实验环境PC微机，Windows操作系统，Visual Studio 2010五. 实验原代码基类:#ifndef MYHEAD_H#define MYHEAD_H#include C:数据结构网络工程雷聪myhead.h#endiftemplateclass LinkListpubl

13、ic:class LinkNodepublic:ElemType data;LinkNode *next;typedef LinkNode *NodePointer;/非循环单链表的构造函数LinkList();/非循环单链表的拷贝初始化构造函数LinkList(const LinkList& otherL);/非循环单链表的析构函数virtual LinkList();/取非循环单链表的第i个结点Status getElem(int i,ElemType& e);/在第i个结点之前插入一个数据域为e的结点Status insert(int i,ElemType e);/判断非循环单链表是否为

14、空bool isEmpty();/求非循环单链表终结点的个数int getLength();/查找第一个与e满足compare()关系的结点Status locateElem(ElemType e,Status (*compare)(ElemType,ElemType),int& i);/返回某结点前驱的数据域Status priorElem(ElemType e,ElemType& prior_e);/返回某结点后继的数据域Status nextElem(ElemType e,ElemType& next_e);/删除非循环单链表中数据域为e的第一个结点Status deleteElem(E

15、lemType e);/删除非循环单链表中重复的值void deleteRepeat();/非循环单链表的逆置void adverse();/把一个非循环单链表赋值给另一个非循环单链表LinkList operator=(LinkList rightL);/把非循环单链表置空void clear();/*/取头指针NodePointer getHead();*/protected:NodePointer head;templateLinkList:LinkList()head=NULL;templateLinkList:LinkList(const LinkList& otherL)NodeP

16、ointer p,s;NodePointer op=otherL.head;head=p=NULL;while(op)s=new LinkNode;assert(s!=0);s-data=op-data;if(!head)head=s;elsep-next=s;p=s;op=op-next;if(head)p-next=NULL;templateLinkList:LinkList()clear();/功能：取非循环单链表的第i个结点templateStatus LinkList:getElem(int i,ElemType& e)int j=1;NodePointer p=head;while

17、(p&jnext;+j;if(!p|ji)return ERROR;e=p-data;return OK;/功能：在第i个结点之前插入一个数据域为e的结点templateStatus LinkList:insert(int i,ElemType e)int j=1;NodePointer s,p=head;while(p&jnext;+j;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;/功能：判断非

18、循环链表是否为空templatebool LinkList:isEmpty()return (head?false:true);/功能：求非循环链表结点的个数templateint LinkList:getLength()int n=0;NodePointer p=head;while(p)p=p-next;+n;return n;/功能：查找第一个数据域与e满足compare()关系的结点templateStatus LinkList:locateElem(ElemType e,Status (*compare)(ElemType,ElemType),int& i)NodePointer p

19、=head;i=1;while(p&!(*compare)(p-data,e)p=p-next;+i;if(!p)return ERROR;elsereturn OK;/功能：返回某结点（数据域为e）前驱的数据域 templateStatus LinkList:priorElem(ElemType e,ElemType& prior_e)NodePointer r=NULL,p=head;while(p&!equal(p-data,e)r=p;p=p-next;if(!p|!r)return ERROR;prior_e=r-data;return OK;/功能：返回某结点（数据域为e）后继的数

20、据域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;return OK;/功能：删除非循环单链表中数据域为e的第一个结点templateStatus LinkList:deleteElem(ElemType e)NodePointer r=NULL,p=head;while(p&p-data!=e)r=p;p=p-next;if

21、(p=NULL)return ERROR;if(r=NULL)head=head-next;elser-next=p-next;delete p;return OK;/功能：删除非循环单链表中重复的值templatevoid LinkList:deleteRepeat()NodePointer r=NULL,s,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;/功能：非循环单链表的逆置templatevoid LinkLi

22、st: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;/功能：重载赋值运算符的定义（把一个非循环单链表赋值给另一个非循环单链表）templateLinkList LinkList:operator=(LinkList rightL)NodePointer s,p=NULL;NodePointer rp=rightL.head;if(this!=&rightL)clear();while(rp)s=new LinkNod

23、e;assert(s!=0);s-data=rp-data;if(!head)head=s;elsep-next=s;p=s;rp=rp-next;if(p) p-next=NULL;return *this;/功能：把非循环单链表置空templatevoid LinkList:clear()NodePointer p=NULL,q=head;while(q)p=q;q=q-next;delete p;head=NULL;/*/功能：取头指针templateLinkList:NodePointer LinkList:getHead()return head;派生类:#ifndef LINKLI

24、ST_H#define LINKLIST_H#include C:数据结构网络工程雷聪LinkList.h#endiftemplate class MyLinkList:public LinkListpublic:void randomLinkList();void randLinkList();void read(istream& in);void display(ostream& out) const;template void MyLinkList:randomLinkList()int n;ElemType elem12;NodePointer s,p=head;srand(unsig

25、ned) time(NULL);n=rand()%10+1;cout 用如下的随机数生成非循环单链表：endl;for(int i=0;in;i+)elemi=rand()%100;coutsetw(4)elemi;clear();for(int i=0;idata=elemi;if(!head)head=s;elsep-next=s;p=s;if(p)p-next=NULL;coutendlendl 随机生成的非循环单链表为：endl;for(int i=1;i=n;i+)cout i ;coutnext=NULL)coutdatax5E;break;cout data;p=p-next;t

26、emplate void MyLinkList:randLinkList()int n;ElemType elem12;NodePointer s,p=head;srand(unsigned) time(NULL);n=rand()%10+1;for(int i=0;in;i+)elemi=rand()%100;clear();for(int i=0;idata=elemi;if(!head)head=s;elsep-next=s;p=s;if(p)p-next=NULL;template void MyLinkList:read(istream& in)int n;ElemType elem

27、12;NodePointer p=head;NodePointer s;coutn;cout 请输入你要设定的各结点的数据域分别是：endl;for(int i=0;isetw(3)elemi;if(head)clear();for(int i=0;idata=elemi;if(!head)head=s;elsep-next=s;p=s;if(p)p-next=NULL;template istream& operator(istream& in,MyLinkList &iD)iD.read(in);return in;template void MyLinkList:display(ostr

28、eam& out) constNodePointer p=head;for(int i=1;p;i+)out inext;outnext=NULL)outsetw(3)datax5E;break;outsetw(3)data;p=p-next;template ostream& operator(ostream& out,const MyLinkList &oD)oD.display(out);return out;六. 实验结果(1) 非循环单链表首页(2) 随机生成非循环单链表(3) 初始化另一个非循环单链表(4) 输入非循环单链表(5) 取非循环单链表的第i个结点(6) 在第i个结点之前

29、插入一个数据域为e的结点(7) 判断非循环单链表是否为空(8) 求非循环单链表中结点的个数(9) 查找第1个与e满足compare()关系的结点(10)返回某结点前驱,后继的数据域(11)非循环单链表的逆置(12)把非循环单链表置空七. 心得体会不同实验的测试头文件和main文件几乎可以通用，复制几行后，在VS中批量替换一下，比重新编写会快一些,所以不能做完实验后就把它删除。随机生成的操作可以写在派生类里，通过调用循环生成随机数并基类的插入函数加入对应数据类型的示例中。没必要单独设置elem或者每个Node。循环调用基类的插入函数的话，只要数据类型的插入操作变化不大，随机生成的代码可以直接使用

30、。南昌大学实验报告 -（3）链队学生姓名： 雷聪 学 号： 6100410013 专业班级： 网工101班 实验类型： 验证 综合 设计 创新 实验日期： 实验成绩： 一. 实验目的掌握非循环链队的逻辑结构、存储结构、操作，并通过 C+编程实现。二. 实验要求实现非循环链队的随机生成和拷贝初始化两个框架操作，以及进出队列、读队头结点等七个基本操作。三. 问题描述队列的非循环链式存储结构简称为非循环链队，它是限制尽在表头删除和表尾插入的非循环单链表。需要队头指针front和队尾指针rear分别指向非循环链队的第一个和最后一个结点，以便在队尾做插入，队头做删除操作。四. 实验环境PC微机，Wind

31、ows操作系统，Visual Studio 2010五. 实验代码基类:#ifndef MYHEAD_H#define MYHEAD_H#include C:数据结构网络工程雷聪myhead.h#endiftemplateclass LinkQueueprotected:class LinkNodepublic:ElemType data;LinkNode* next;typedef LinkNode* NodePointer;public:void clear();Status deQueue(ElemType& e);void enQueue(ElemType e);Status getF

32、ront(ElemType& e);bool isEmpty();int getLength();/重载运算符LinkQueue operator=(LinkQueue rightQ);/构造及析构函数LinkQueue();LinkQueue();LinkQueue(const LinkQueue& otherQ);protected:NodePointer rear;NodePointer front;/基本操作templatevoid LinkQueue:clear()NodePointer q;NodePointer p=front;while (p)q=p;p=p-next;dele

33、te q;front=rear=NULL;templateStatus LinkQueue:deQueue(ElemType& e)if(!front)return ERROR;NodePointer s=front;e=s-data;front=front-next;delete s;if(!front)rear=NULL;return OK;templatevoid LinkQueue:enQueue(ElemType e)NodePointer s;s=new LinkNode;assert(s!=0);s-data=e;s-next=NULL;if(!front)front=rear=

34、s;elserear-next=s;rear=s;templateStatus LinkQueue:getFront(ElemType& e)if(!front)return ERROR;e=front-data;return OK;templatebool LinkQueue:isEmpty()return front?false:true;templateint LinkQueue:getLength()int length=0;NodePointer p=front;while (p)length+;p=p-next;return length;/重载运算符templateLinkQue

35、ue LinkQueue:operator=(LinkQueue rightQ)NodePointer s;NodePointer rp=rightQ.front;if(this!=&rightQ)clear();while (rp)s=new LinkNode;assert(s!=0);s-data=rp-data;s-next=NULL;if(!front)front=rear=s;else rear-next=s;rear=s;rp=rp-next;return *this;/构造及析构函数templateLinkQueue:LinkQueue()front=rear=NULL;temp

36、lateLinkQueue:LinkQueue()clear();templateLinkQueue:LinkQueue(const LinkQueue& otherQ)NodePointer s;NodePointer op=otherQ.front;rear=front=NULL;while (op)s=new LinkNode;assert(s!=0);s-data=op-data;s-next=NULL;if(!front)front=rear=s;elserear-next=s;rear=s;op=op-next;派生类：#ifndef LINKQUEUE_H#define LINK

37、QUEUE_H#include C:数据结构网络工程雷聪LinkQueue.h#endiftemplateclass MyLinkQueue:public LinkQueuepublic:void randomLinkQueue();void randLinkQueue();void read(istream& in);void display(ostream& out)const;templatevoid MyLinkQueue:randomLinkQueue()int n;ElemType e;n=rand()%10;if(n=0)front=rear=NULL;return;cout 用

38、如下随机数生成非循环链队的各结点：endl;for(int i=0;in;i+)e=rand()%100;coutsetw(4)e;enQueue(e);coutendlendl 随机生成的非循环链队为：endl;cout*this;templatevoid MyLinkQueue:randLinkQueue()int n;ElemType e;srand(unsigned) time(NULL);n=rand()%10;if(n=0)front=rear=NULL;return;for(int i=0;in;i+)e=rand()%100;enQueue(e);templatevoid My

39、LinkQueue:read(istream& in)int n;ElemType e;coutn;if(n=0)front=rear=NULL;return;for(int i=0;in;i+)coute;enQueue(e);templateistream& operator(istream& in,MyLinkQueue& sQ)sQ.read(in);return in;templatevoid MyLinkQueue:display(ostream& out)constNodePointer p=front;if (p)if (front=rear)out setw(2)dataen

40、dl;out x18endl;outfront/rear;elseoutnext)if(p=rear)outsetw(2)dataendl;elseoutsetw(2)datax1A;outnext;p;p=p-next)out ;outx18endl;outnext;p!=rear;p=p-next)out ;outrearendl;六. 实验结果（1）非循环链队首页（2）随机生成非循环链队（3）初始化另一个非循环链队（4）进队列（5）出队列（6）读非循环链队队首到e（7）求非循环链队结点个数（8）将一个非循环链队赋值给另一个链队（9）把非循环链队置空七. 心得体会非循环链队实际上就是之前的

41、非循环单链表，只不过限制了很多操作，只剩下队列规则的操作。为了实现这些操作，在front(head)外又添加了rear指针指向队尾，免去每次出队列都要从头遍历一边队列的麻烦。南昌大学实验报告 -（4）排序学生姓名： 雷聪 学 号： 6100410013 专业班级： 网工101班 实验类型： 验证 综合 设计 创新 实验日期： 实验成绩： 一. 实验目的了解排序的基本概念，理解什么是排序算法的稳定性。掌握基本的五类排序方法，即插入排序、交换排序、选择排序、归并排序和分配排序。并通过C+编程实验它们。二. 实验要求实现插入排序中的：直接插入排序、折半插入排序、静态链表插入排序、希尔排序。交换排序中

42、的：冒泡排序、快速排序。选择排序中的：直接选择排序、堆排序。归并排序以及分配排序中的：箱排序、基数排序（箱排序包含在基数排序例子中）。三. 问题描述文件由一组记录组成，记录则由若干个数据项（或域）组成。所谓排序，就是要整理文件中的记录，使之按某数据项递增（或递减）次序排列起来，即输入n个记录R1, R2, , Rn，其相应的排序数据项的值分别为K1, K2, , Kn，排序后输出Ri1, Ri2, , Rin，使得Ki1Ki2Kin（或Ki1Ki2Kin）。四. 实验环境PC微机，Windows操作系统，Visual Studio 2010。五 实验代码基类：#ifndef SQLIST_H#

43、define SQLIST_H#include SqList.h#endif#ifndef MYSEQTREE_H#define MYSEQTREE_H#include C：数据结构网络工程雷聪MySeqTree.h#endif#define KEYNUM 3#define RADIX 10templateclass SqListSort:public SqListpublic:int getIndex(int i);void insertSort();void binaryInsertSort();void staticLinkListSort();void shellSort();void

44、 bubbleSort();void quickSort();void selectSort();void heapSort();void mergeSort();void radixSort();private:void shellSort_aux(int dk);void quickSort_aux(int low,int high);int quickSortPartition_aux(int low,int high);void heapSortAdjust_aux(int s,int m);void mergeSort_aux(int s,int t);void mergeSortOn_aux(int i,int m,int n);void radixSortCollect_aux(int front,int end,int time);void radixSortDistribute_aux(i