数据结构实验报告册

实验一线性表的操作实验类型：验证性实验要求：必修实验学时：2学时一、实验目的：参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法。二、实验要求：1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明程序清单、调试情况、设计技巧、心得体会。三、实验内容：1．设计一个静态数组存储结构的顺序表类，要求编程实现如下任务：建立一个线性表，首先依次输人数据元素1,2,3,・・・，10,然后删除数据元素6,最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过10个。第一题源代码：#include<iostream>usingnamespacestd;template<classT>classSeqList{第一题源代码：#include<iostream>usingnamespacestd;template<classT>classSeqList{private:intlength,x,j,data[10];public:public:SeqList(){length=0;}SeqList(Ta[],intn){for(inti=0;i<n;i++)data[i]=a[i];length=n;}~SeqList(){}intLength(){returnlength;//定义模板类SeqList//无参构造函数//有参构造函数//析构函数为空//求线性表的长度}TGet(inti){}}TGet(inti){}intLocate(Tx){}voidInsert(inti,Tx){}TDelete(inti){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]；length--；returnx；}voidPrintList(){for(inti=0；i<length；i++)cout<<data[i]<<""；cout<<endl；}}；voidmain(){intn=10,a[10]={1,2,3,4,5,6,7,8,9,10}；SeqList<int>theseqlist(a,n)；coutvv"删除前元素：";for(inti=0；i<n；i++)cout<<a[i]<<" "；〃按位查找，取线性表的第i个元素〃按值查找，求线性表中值为x的元素序号//在线性表中第i个位置插入值为x的元素//删除线性表的第i个元素〃注意此处j已经是元素所在的数组下标//遍历线性表，按序号依次输出各元素cout<<endl；theseqlist.Delete(6)；theseqlist.PrintList()；}运行结果：

2.设计一个带头结点的单链表类，要求：带头结点单链表类的成员函数包括取数据元素个数、插入元素、删除所有值为k的元素、取数据元素。设计一个测试主函数，实际运行验证所设计循环单链表类的正确性。第二题源代码：#includeviostream>usingnamespacestd;templatevclassT>structNode{Tdata;NodevT>*next;}；template<classT>classLinkList{〃单链表头指针private:〃单链表头指针Node<T>*first;intlength;public:LinkList(){first=newNode<T>;first->next=NULL;}LinkList(Ta[],intn) 〃建立n个节点的指针{〃初始化一个空链表Node<T>*s;first=newNode<T>;first->next=NULL;for(inti=0;ivn;i++)〃初始化一个空链表{s=newNode<T>;

s->data=a[i];s->next=first->next;first->next=s;}length=n;}~LinkList(){Node<T>*p=first;while(p){Node<T>*q;q=p;p=p->next;deleteq;}//求单链表长度//求单链表长度〃取单链表第i个节点元素值//求单链表值为x的元素序号//在单链表中第i个位置插入元素值x的节点〃在单链表中删除第i个节点//遍历单链表，按序号依次输出个元素intLength();TGet(inti);intLocate(Tx);voidInsert(inti,Tx);TDelete(inti);voidPrintList();};template<classT>intLinkList<T>::Length(){returnlength;}template<classT>TLinkList<T>::Get(inti){intj;Node<T>*p;p=first->next;j=1;while(p&&j<i){p=p->next;j++;if(!p)throw"位置";elsereturnp->data;}template<classT>intLinkList<T>::Locate(Tx){Node<T>*p;p=first;for(inti=0;i<length;i++){p=p->next;if(p->data==x)returni+1;}}template<classT>voidLinkList<T>::Insert(inti,Tx){Node<T>*p;intj;p=first;j=0;while(p&&j<i-1){p=p->next;j++;}if(!p)throw"位置"；else{Node<T>*s；s=newNode<T>；s->data=x；s->next=p->next；p->next=s；}length++；

template<classT>TLinkList<T>::Delete(inti){Node<T>*p;intj;p=first;j=0;while(p&&j<i-1){p=p->next;j++;}if(!p||!p->next)throw"位置"；else{Node<T>*q；q=newNode<T>；intx；q=p->next；x=q->data；p->next=q->next；deleteq；length--；returnx；}//遍历单链表，按序号依次输出个元素template<classT>voidLinkList<T>::PrintList()//遍历单链表，按序号依次输出个元素Node<T>*p；p=first；for(inti=0；i<length；i++){p=p->next；coutvv"第"vv(i+l)vv"个元素为："vv(p->data)vvendl;}}

voidmain(){intr[]={10,9,8,7,6,5,4,3,2,l};LinkList<int>a(r,10);coutvv"原表为:"vvendl;a.PrintList();coutvvendl;a.Insert(1,-2); 〃执行插入操作；a.Insert(2,-1);a.Insert(3,0);coutvv"执行插入后输出为:"vvendl;a.PrintList();coutvvendl;a.Delete(1);a.Delete(1);a.Delete(1);coutvv"执行删除后输出为:"vvendl;a.PrintList();coutvvendl;coutvv"按位查找元素:"vvendl;coutvv"第5个元素为:";coutvva.Get(5)vvendl; 〃查找链表中第5个元素coutvvendl;}运行结果:日柯日刼Q九^31N日91宁±----S3---JJ_=芻尋为^聂一.-

主T诜十主ryT'v

±.2345;EPaFF5

--,■wgg穽二■个II-.'-rl6.;ba”4,7,ii¥—丄X:F.'-—w'k-'l..Hu'T'i!*】Ef^gggF^kFkFfe-fe^kgFfe-Ef^gggr需kgFfe-fefe-F【uin二r:=mMl=■柯Jp甘亠SIJS""^7>>于>宁-¥>于.j£u^^-=去>■壬畫■aQl-.—11YM」2:t

B9丄丄rlrl心得体会：实验二栈、队列、串的操作实验类型：验证性实验要求：必修实验学时：2学时一、实验目的：参照给定的栈类和队列类的程序样例，验证给出的栈和队列的常见算法，并结合线性表类实现有关串的操作。二、实验要求：1、掌握栈、队列、串的特点。掌握特殊线性表的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明程序清单、调试情况、设计技巧、心得体会。三、实验内容：1.堆栈类测试和应用问题。要求：设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。测试方法为：依次把数据元素1,2,3,4,5入栈，然后出栈堆栈中的数据元素并在屏幕上显示。第一题源代码：#include<iostream>usingnamespacestd;、、、、、、、constintStackSize=10;template<classT>classSeqStack{private:Tdata[StackSize];inttop;public:SeqStack(){top=-1;}~SeqStack(){}voidpush(Tx);Tpop();TGetTop(){if(top!=-1)returndata[top];}boolEmpty(){top=-1?(return1):(return0);}};template<classT>voidSeqStack<T>::push(Tx){if(top==StackSize-1)throw"上溢";top++;data[top]=x;}template<classT>TSeqStack<T>::pop(){Tx;if(top==-1)throw"下溢";x=data[top--];returnx;}/template<classT>structNode{Tdata;Node<T>*next;};template<classT>classLinkStack{private:Node<T>*top;public:LinkStack(){top=NULL;}~LinkStack(){while(top){Node<T>*p;p=top->next;deletetop;top=p;}}voidpush(Tx);Tpop();Tgettop(){if(top!=NULL)returntop->data;}boolEmpty(){top==NULL?return1:return0;}};template<classT>voidLinkStack<T>::push(Tx){Node<T>*s;s=newNode<T>; //没有申请空间时会出现错误s->data=x;s->next=top;top=s;}template<classT>TLinkStack<T>::pop(){Tx;Node<T>*p;if(top==NULL)throw"下溢";x=top->data;p=top；top=top->next;deletep;returnx;}voidmain(){SeqStackvint>aa;LinkStackvint>bb;for(inti=l;iv=5;i++)aa.push(i);coutvv"顺序栈出栈："for(i=0;i<5;i++){intk=0;k=aa.pop();coutvvkvv"";}coutvvendl;for(i=1;i<=5;i++)bb.push(i);coutvv"链式栈出栈："for(i=1;iv=5;i++){intj=0;j=bb.pop();coutvvjvv"";}coutvvendl;}运彳丁结果:2.队列类测试和应用问题。要求：设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为：依次把1,2,3,4,5入队，然后出队中的数据元素并在屏幕上显示。第二题源代码：#include<iostream>#include<string>usingnamespacestd;constintQueueSize=100;template<classT>classCirQueue{public:Tdata[QueueSize];intfront,rear;CirQueue(){front=rear=0;}~CirQueue(){}voidEnQueue(Tx){if((rear+1)%QueueSize==front)throw上"溢";rear=(rear+1)%QueueSize;data[rear]=x;}TGetQueue(){if(rear==front)thTO溢"'；inti=(front+1)%QueueSize;returndata[i];}TDeQueue(){if(rear==front)throw下"溢";front=(front+1)%QueueSize;returndata[front];

};template<classT>structNodeTdata;Node<T>*next;};template<classT>classLinkQueue//队头队尾指针//队头队尾指针〃将x入队//将队头元素出队//取对头元素//判断链队列是否为空Node<T>*front,*rear;public:LinkQueue();~LinkQueue()voidEnQueue(Tx);TDeQueue();TGetQueue()if(front!=rear)returnfront->next->data;boolEmpty()front==rear?return1:return0;};template<classT>LinkQueue<T>::LinkQueue()〃创建头结点s〃创建头结点stemplate<classT>voidLinkQueue<T>::EnQueue(Tx){Node<T>*s;s=newNode<T>;s->data=x;s->next=NULL;rear->next=s;rear=s;、、、、、、、、、、、、、template<classT>TLinkQueue<T>::DeQueue(){Node<T>*p;Tx;if(rear==front)throw"下溢"；p=front->next;x=p->data；front->next=p->next；if(p->next==NULL)rear=front；deletep；returnx；}voidmain(){CirQueue<int>a；LinkQueue<int>b；for(inti=1；i<=5；i++){a.EnQueue(i)；b.EnQueue(i)；}for(i=1；i<=5；i++){intk,j(0)；k=a.DeQueue()；j=b.DeQueue()；"vvjvvendl；coutvv"循环队列输出："vvkvv""<<"链队列输出:"vvjvvendl；}试验结果：C:\DOCU1EKTS1KDSETTIMGS\ABIIMISTRATOK\MWX^据1歹歹歹歹歹

链链链链链o1234Et歹歹歹歹歹

链链链链链o1234Et V出他嵋吧歹歹歹歹歹ahl-j..Jhl-)...・hl-j..JFi-;ly3r、r、3杆杆刁•Erm-m-m-m-m-心得体会：实验三多维数组和广义表的操作实验类型：验证性实验要求：必修实验学时：2学时一、 实验目的：参照给定的多维数组类和广义表类的程序样例，验证给出的多维数组和广义表的常见算法，并实现有关的操作。二、 实验要求：1、 掌握多维数组和广义表的特点。掌握它们的常见算法。2、 提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、 实验内容：设计函数建立一个n*n阶的对称矩阵。要求：（1） 实现将对称矩阵用一维数组存储输出。（2） 实现矩阵转置算法。（3） 实现魔方阵算法。（4） 设计一个测试例子，并编写主程序进行测试。第一题源代码：1.1#includeviostream>usingnamespacestd;inta[10][10];intsave[100];intmain（）{intn,i,j;puts（"输入矩阵的维数N”）；cin>>n;for（i=0;i<n;i++）for（j=0;j<n;j++）{a[i][j]=rand（）%10+1;a[j][i]=a[i][j];

}for(i=0;i<n;i++){for(j=0;j<n;j++)coutvva[i][j]vv"\t";coutvvendl;}puts(”转化后：");intk=0;for(i=0;i<n;i++)for(j=0;j<=i;j++){k=i*(i+1)/2+j;save[k]=a[i][j];k++; }for(i=0;i<n*(n+1)/2;i++)coutvvsave[i]vv""coutvvendl;return0;}运彳丁结果：'=!：l■-^C:kDocu»entsandSel+irkgs\.Ad»iTListratoirY桌63842tocontinue输入矩阵的维数63842tocontinue需侷0 5 9Pi'-essAnykey1.2#includeviostream>usingnamespacestd;constintMaxTerm=100;template<classT>structelement{introw,col;Titem;};structSparseMatrix{element<int>data[MaxTerm];intmu,nu,tu;};voidTrans1(SparseMatrixA,SparseMatrix&B){B.mu=A.nu；B.nu=A.mu；B.tu=A.tu；if(B.tu>0){intpb=0；for(intcol=0；col<A.nu；col++)for(intpa=0；pa<A.tu；pa++)if(A.data[pa].col==col){B.data[pb].row=A.data[pa].col；B.data[pb].col=A.data[pa].row；B.data[pb].item=A.data[pa].item；pb++；}}}intmain(){inti;SparseMatrixAA,BB;puts(”输入行数列数非零元素个数”)；cin>>AA.mu>>AA.nu>>AA.tu;puts("输入三元表:")； 〃puts()与cout一样for(i=0；i<7；i++){cin>>AA.data[i].row；cin>>AA.data[i].col；cin>>AA.data[i].item；}Trans1(AA,BB)；puts("输出三元表心”)；for(i=0；i<7；i++){cout<<BB.data[i].row<<"\t"；cout<<BB.data[i].col<<"\t"；cout<<BB.data[i].item<<"\t"<<endl；}return0；}运行结果："C:\Bocu>ent:sandSettings\Ad|输入行数列数非零元素不矿567輸入三元表：0e15032205-151111123*3£4Q91输出=元表门0Q15491k111*13Q22□260-15Pressany血勺tocontinuc心得体会:实验四树和二叉树实验类型：验证性实验要求：必修实验学时：2学时一、 实验目的：参照给定的二叉树类的程序样例，验证给出的有关二叉树的常见算法，并实现有关的操作。二、 实验要求：1、 掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。2、 提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、 实验内容：1.设计实现二叉树类，要求：编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。实现二叉树层次遍历的非递归算法。假设二叉树采用链式存储结构进行存储，编写一个算法，输出一个二叉树的所有叶子结点，并统计叶子结点个数。编写求二叉树高度的函数编写一主函数来验证算法实现

第一题源代码：#include<iostream>usingnamespacestd;template<classT>structBiNode{Tdata;BiNode<T>*lchild,*rchild;};template<classT>classBiTree{private:staticinti;//前序建立扩展二叉树//建立一棵空树//前序建立扩展二叉树//建立一棵空树//生成一个结点//递归建立左子树//递归建立右子树voidCreat(BiNode<T>*&root){charch;cin>>ch;if(ch=='#')root=NULL;else{root=newBiNode<T>;root->data=ch;Creat(root->lchild);Creat(root->rchild);}}voidRelease(BiNode<T>*root){if(root!=NULL){Release(root->lchild);Release(root->rchild);deleteroot;}}voidPreOrder(BiNode<T>*root){if(root==NULL)return;else//前序遍历{cout<<root->data;PreOrder(root->lchild);PreOrder(root->rchild);}}voidInOrder(BiNode<T>*root){if(root==NULL)return;else{InOrder(root->lchild);cout<<(root->data);InOrder(root->rchild);}}//中序遍历二叉树voidPostOrder(BiNode<T>*root){if(root==NULL)return;else{InOrder(root->lchild);InOrder(root->rchild);cout<<(root->data);}}voidLevelOrder(BiNode<T>*root){//后序遍历二叉树BiNode<T>*Q[100];intfront=0,rear=0;//采用顺序队列，并假定不会发生上溢if(root==NULL)return;Q[++rear]=root;while(front!=rear){BiNode<T>*q=Q[++front];