数据结构实验2

PAGE数据结构实验2数据结构实验指导书重庆邮电大学软件工程学院范时平2014年10月-PAGE1-数据结构实验2全文共20页，当前为第1页。

数据结构实验2全文共20页，当前为第1页。实验目的与要求一、实验目的数据结构是软件工程学科中一门非常重要的专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的存储表示及数据的处理，而数据存储表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是为软件方面的课程打下厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构在软件工程学科及相关学科专业的课程体系中具有极其重要的作用。

本课程的任务是：通过实践，学生对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会；能够快速确定数据的逻辑结构、并根据数据处理的类型和频度选择最佳的存储结构和算法组合。二、实验要求1．准备好上机所需要的C++程序，以提高上机效率。对程序中自己有疑问的地方应作记号，以便在上机时给予注意或获取教师指导。不得抄袭他人程序。2．上机输入并调试/运行所编写程序。3．上机结束后，提交实验报告，实验报告应包括但不限于以下内容：（1）题目；（2）实验目的；（3）主要数据结构描述；（4）算法的基本思想描述；（5）算法时间复杂度分析；（6）运行的结果截图；（7）实验体会和收获；数据结构实验2全文共20页，当前为第2页。（8）程序清单数据结构实验2全文共20页，当前为第2页。实验一顺序表的存储与操作一、实验目的1．理解线性表的逻辑结构；2．理解顺序表的存储结构特点，掌握顺序表的存储分配要点；3．掌握顺序表的基本操作及实现，并能正确分析其时间复杂度。二、实验内容1.定义顺序表的存储结构；2.顺序表的基本操作（1）初始化顺序表（无参和有参）；（2）求顺序表长度；（3）按位置查找；（4）按值查找；（5）在位置i插入一个数据元素；（6）删除位置i的数据元素；（7）遍历顺序表；（8）销毁顺序表。三、算法思想和时间复杂度当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。四、参考代码1.顺序表的存储结构和操作接口SeqList.h声明类SeqList,文件名为SeqList.h#ifndefSeqList_H#defineSeqList_HconstintMaxSize=100;//100只是示例性的数据，可以根据实际问题具体定义数据结构实验2全文共20页，当前为第3页。数据结构实验2全文共20页，当前为第3页。classSeqList{public:SeqList();//无参构造函数SeqList(Ta[],intn);//有参构造函数~SeqList();//析构函数为空intLength();//求线性表的长度TGet(inti);//按位查找，取线性表的第i个元素intLocate(Tx);//按值查找，求线性表中值为x的元素序号voidInsert(inti,Tx);//在线性表中第i个位置插入值为x的元素TDelete(inti);//删除线性表的第i个元素voidPrintList();//遍历线性表，按序号依次输出各元素private:Tdata[MaxSize];//存放数据元素的数组intlength;//线性表的长度};#endif顺序表操作的实现//SeqList.cpp#include"SeqList.h"/**前置条件：顺序表不存在*输入：无*功能：构建一个顺序表*输出：无*后置条件：构建一个顺序表*/template<classT>SeqList<T>::SeqList(){数据结构实验2全文共20页，当前为第4页。数据结构实验2全文共20页，当前为第4页。}/**前置条件：顺序表不存在*输入：顺序表信息的数组形式a[],顺序表长度n*功能：将数组a[]中元素建为长度为n的顺序表*输出：无*后置条件：构建一个顺序表*/template<classT>SeqList<T>::SeqList(Ta[],intn){if(n>MaxSize)throw"参数非法";for(inti=0;i<n;i++)data[i]=a[i];length=n;}/**前置条件：无*输入：无*功能：无*输出：无*后置条件：无*/template<classT>SeqList<T>::~SeqList(){}/**前置条件：顺序表存在*输入：插入元素x,插入位置i*功能：将元素x插入到顺序表中位置i处*输出：无*后置条件：顺序表插入新元素数据结构实验2全文共20页，当前为第5页。数据结构实验2全文共20页，当前为第5页。template<classT>voidSeqList<T>::Insert(inti,Tx){intj;if(length>=MaxSize)throw"上溢";if(i<1||i>length+1)throw"位置";for(j=length;j>=i;j--)data[j]=data[j-1];//注意第j个元素存在数组下标为j-1处data[i-1]=x;length++;}/**前置条件：顺序表存在*输入：要删除元素位置i*功能：删除顺序表中位置为i的元素*输出：无*后置条件：顺序表删除元素*/template<classT>TSeqList<T>::Delete(inti){intx,j;if(length==0)throw"下溢";if(i<1||i>length)throw"位置";x=data[i-1];for(j=i;j<length;j++)data[j-1]=data[j];//注意此处j已经是元素所在的数组下标length--;returnx;}/*数据结构实验2全文共20页，当前为第6页。数据结构实验2全文共20页，当前为第6页。*输入：无*功能：输出顺序表长度*输出：顺序表长度*后置条件：顺序表不变*/template<classT>intSeqList<T>::Length(){ returnlength;}/**前置条件：顺序表存在*输入：查询元素位置i*功能：查找位置为i的元素并输出值*输出：查询元素的值*后置条件：顺序表不变*/template<classT>TSeqList<T>::Get(inti){if(i<1&&i>length)throw"查找位置非法";elsereturndata[i-1];}/**前置条件：顺序表存在*输入：查询元素值x*功能：按值查找值的元素并输出位置*输出：查询元素的位置*后置条件：顺序表不变*/template<classT>intSeqList<T>::Locate(Tx){数据结构实验2全文共20页，当前为第7页。数据结构实验2全文共20页，当前为第7页。 if(data[i]==x) returni+1;//下标为i的元素等于x，返回其序号i+1 return0;//退出循环，说明查找失败}/**前置条件：顺序表存在*输入：无*功能：顺序表遍历*输出：输出所有元素*后置条件：顺序表不变*/template<classT>voidSeqList<T>::PrintList(){ for(inti=0;i<length;i++) cout<<data[i]<<endl;}顺序表的调试运行//SeQListMain.cpp#include<iostream.h>//引用输入输出流库函数的头文件#include"SeqList.cpp"//引用顺序表类SeqListvoidmain(){SeqList<int>a;//创建一个空的顺序表cout<<"执行插入操作:"<<endl;try{a.Insert(1,1);a.Insert(2,3);数据结构实验2全文共20页，当前为第8页。数据结构实验2全文共20页，当前为第8页。}catch(char*wrong){cout<<wrong;//如失败提示失败信息}cout<<"已经插入“1，3，4”"<<endl;cout<<endl;cout<<"顺序表a的长度为:";cout<<a.Length()<<endl;//返回单链表长度cout<<endl;cout<<"按位查询第二个元素:"<<endl;cout<<"第二个元素为:";cout<<a.Get(2)<<endl;//查找顺序表中第二个元素cout<<endl;cout<<"按值查询3:"<<endl;cout<<"值为3的元素位置为:";cout<<a.Locate(3)<<endl;//查找元素3，并返回在单链表中位置cout<<endl;try{if(a.Length()){ cout<<"执行删除第一个元素操作:"<<endl; cout<<endl; a.Delete(1);//删除元素1cout<<"已删除成功，顺序表a的长度为:";cout<<a.Length()<<endl;}else{ cout<<"顺序表a长度为0"<<endl;}数据结构实验2全文共20页，当前为第9页。数据结构实验2全文共20页，当前为第9页。catch(char*wrong){cout<<wrong;//如失败提示失败信息}cout<<endl;cout<<"顺序表a中的元素有:"<<endl;a.PrintList();//输出所有元素intr[]={1,2,3,4,5};SeqList<int>b(r,5);//根据数组创建顺序表cout<<"执行插入操作前顺序表b为:"<<endl;b.PrintList();//输出顺序表所有元素cout<<"插入前顺序表b的长度为:";cout<<b.Length()<<endl;try{b.Insert(3,8);}catch(char*wrong){cout<<wrong;//如失败提示失败信息}cout<<"执行插入操作后顺序表b为:"<<endl;b.PrintList();//输出顺序表b所有元素cout<<"插入后顺序表b的长度为:";cout<<b.Length()<<endl;cout<<endl;try{if(a.Length()){ cout<<"执行删除第一个元素操作:"<<endl;数据结构实验2全文共20页，当前为第10页。数据结构实验2全文共20页，当前为第10页。 b.Delete(1);//删除b中第一个元素cout<<"已删除成功，顺序表b的长度为:";cout<<b.Length()<<endl;}else{ cout<<"顺序表b长度为0"<<endl;}}catch(char*wrong){cout<<wrong;//如失败提示失败信息}cout<<"执行插入操作后顺序表b为:"<<endl;b.PrintList();//输出顺序表所有元素}数据结构实验2全文共20页，当前为第11页。

实验二单链表的存储与操作数据结构实验2全文共20页，当前为第11页。一、实验目的1．理解线性表的逻辑结构；2．理解单链表的存储结构特点，掌握单链表的存储分配要点；3．掌握单链表的基本操作及实现，并能正确分析其时间复杂度。二、实验内容1.定义单链表的存储结构；2.单链表的基本操作（1）初始化单链表（无参和有参）；（2）求单链表长度；（3）按位置查找；（4）按值查找；（5）在位置i插入一个数据元素；（6）删除位置i的数据元素；（7）遍历单链表；（8）销毁单链表。三、算法思想和时间复杂度1.按位置/值查找：顺序查找，平均时间复杂度为O（n）；2.在位置i插入一个数据元素：在序号为i-1的结点后插入结点，平均时间复杂度为O（n）；3.删除位置i的数据元素：删除序号为i-1结点的后继结点，平均时间复杂度为O（n）；4.初始化单链表（有参）：有前插法和尾插法（注意单链表的逻辑关系应与参数数组保持一致），时间复杂度为O（n）；5.遍历单链表、求单链表长度、销毁单链表：顺序处理，时间复杂度为O（n）。四、参考代码数据结构实验2全文共20页，当前为第12页。1.单链数据结构实验2全文共20页，当前为第12页。//LinkList.h声明类LinkList#ifndefLinkList_H#defineLinkList_Htemplate<classT>structNode{Tdata;Node<T>*next;//此处<T>也可以省略};template<classT>classLinkList{public:LinkList();//建立只有头结点的空链表LinkList(Ta[],intn);//建立有n个元素的单链表~LinkList();//析构函数intLength();//求单链表的长度TGet(inti);//取单链表中第i个结点的元素值intLocate(Tx);//求单链表中值为x的元素序号voidInsert(inti,Tx);//在单链表中第i个位置插入元素值为x的结点TDelete(inti);//在单链表中删除第i个结点voidPrintList();//遍历单链表，按序号依次输出各元素private:Node<T>*first;//单链表的头指针};#endif数据结构实验2全文共20页，当前为第13页。2.单链表操作数据结构实验2全文共20页，当前为第13页。//LinkList.cpp#include"LinkList.h"/**前置条件：单链表不存在*输入：无*功能：构建一个单链表*输出：无*后置条件：构建一个单链表*/template<classT>LinkList<T>::LinkList(){first=newNode<T>;first->next=NULL;}/**前置条件：单链表不存在*输入：顺序表信息的数组形式a[],单链表长度n*功能：将数组a[]中元素建为长度为n的单链表*输出：无*后置条件：构建一个单链表*/template<classT>LinkList<T>::LinkList(Ta[],intn){first=newNode<T>;//生成头结点 Node<T>*r,*s;r=first;//尾指针初始化for(inti=0;i<n;i++) {s=newNode<T>;s->data=a[i];//为每个数组元素建立一个结点r->next=s;r=s;//插入到终端结点之后 }r->next=NULL;//单链表建立完毕，将终端结点的指针域置空}/**前置条件：无*输入：无*功能：无*输出：无数据结构实验2全文共20页，当前为第14页。数据结构实验2全文共20页，当前为第14页。*/template<classT>LinkList<T>::~LinkList(){}/**前置条件：单链表存在*输入：查询元素位置i*功能：按位查找位置为i的元素并输出值*输出：查询元素的值*后置条件：单链表不变*/template<classT>TLinkList<T>::Get(inti){Node<T>*p;intj;p=first->next;j=1;//或p=first;j=0;while(p&&j<i){p=p->next;//工作指针p后移j++;}if(!p)throw"位置";elsereturnp->data;}/**前置条件：单链表存在*输入：查询元素值x*功能：按值查找值的元素并输出位置*输出：查询元素的位置*后置条件：单链表不变*/template<classT>intLinkList<T>::Locate(Tx){ Node<T>*p;intj; p=first->next;j=1; if(p&&p->next){ while(p->data!=x) { p=p->next; j++;数据结构实验2全文共20页，当前为第15页。数据结构实验2全文共20页，当前为第15页。 returnj; } elsethrow"位置"; }/**前置条件：单链表存在*输入：插入元素x,插入位置i*功能：将元素x插入到单链表中位置i处*输出：无*后置条件：单链表插入新元素*/template<classT>voidLinkList<T>::Insert(inti,Tx){Node<T>*p;intj;p=first;j=0;//工作指针p初始化while(p&&j<i-1){p=p->next;//工作指针p后移j++;}if(!p)throw"位置";else{ Node<T>*s;s=newNode<T>; s->data=x;//向内存申请一个结点s，其数据域为xs->next=p->next;//将结点s插入到结点p之后p->next=s; }}/**前置条件：单链表存在*输入：无*功能：输出单链表长度*输出：单链表长度*后置条件：单链表不变*/template<classT>intLinkList<T>::Length(){数据结构实验2全文共20页，当前为第16页。数据结构实验2全文共20页，当前为第16页。inti=0;while(p){p=p->next;i++;}returni;}/**前置条件：单链表存在*输入：要删除元素位置i*功能：删除单链表中位置为i的元素*输出：无*后置条件：单链表删除元素*/template<classT>TLinkList<T>::Delete(inti){Node<T>*p;intj;p=first;j=0;//工作指针p初始化while(p&&j<i-1)//查找第i-1个结点{p=p->next;j++;}if(!p||!p->next)throw"位置";//结点p不存在或结点p的后继结点不存在else{ Node<T>*q;intx;q=p->next;x=q->data;//暂存被删结点p->next=q->next;//摘链deleteq;returnx; }}/**前置条件：单链表存在*输入：无*功能：单链表遍历*输出：输出所有元素*后置条件：单链表不变*/template<classT>voidLinkList<T>::PrintList()数据结构实验2全文共20页，当前为第17页。数据结构实验2全文共20页，当前为第17页。 Node<T>*p; p=first->next; while(p) { cout<<p->data<<endl; p=p->next; } }3.调试运行//LinkListMain.cpp#include<iostream.h>//引用输入输出流库函数的头文件#include"LinkList.cpp"//引用单链表的类voidmain(){LinkList<int>a;cout<<"执行插入操作:"<<endl;try{a.Insert(1,4);a.Insert(2,5);a.Insert(3,6);}catch(char*wrong){cout<<wrong;//如失败提示失败信息}cout<<"已经插入“4，5，6”"<<endl;cout<<"单链表a的长度为:"<<endl;cout<<a.Length()<<endl;//返回单链表长度cout<<endl;cout<<"单链表a的元素为:"<<endl;a.PrintList();//显示链表中所有元素cout<<endl;cout<<"按位查找第二个元素:"<<endl;cout<<"第二个元素为:";cout<<a.Get(2)<<endl;//查找链表中第二个元素cout<<endl;cout<<"按值查找5"<<endl;数据结构实验2全